# Logical proof using sentential logic $\Big(\big(A \& B \big) \lor \big((\neg{}A \& B) \lor (A \& \neg{}B)\big)\Big)$

I have a premise $$(A \lor B)$$ and need to achieve the conclusion $$\Big(\big(A \& B \big) \lor \big((\neg{}A \& B) \lor (A \& \neg{}B)\big)\Big)$$

This intuitively makes sense since $$(A \lor B)$$ means at least one of them is true. I just can't figure out how the conclusion can be achieved formally. I tried assuming the conclusion is false and achieving a falsum, but that didn't get anywhere. I also tried using disjunction introduction rule backwards but that didn't work either.

Any strategies on how to attack this proof?

• Why don't you try to simplify $((A\land B)\lor ((\lnot A\land B)\lor (A\land \lnot B)))$ first? – Isa Oct 10 '18 at 4:18
• Don't use the disjunction introduction rule backwards. Use it forwards. – Graham Kemp Oct 11 '18 at 10:29

I have a premise $$(A \lor B)$$ and need to achieve the conclusion $$\Big(\big(A \& B \big) \lor \big((\neg{}A \& B) \lor (A \& \neg{}B)\big)\Big)$$

This intuitively makes sense since $$(A \lor B)$$ means at least one of them is true.

Exactly, so use a proof by cases. Here, I'll start it off in the Fitch system. Add the justifications and fill in the dots.$$\def\fitch#1#2{\quad\begin{array}{|l} #1\\\hline #2\end{array}} \fitch{A\lor B}{\fitch{A}{B\lor\lnot B\\\fitch{B}{A\land B\\(A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B))}\\B\to((A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B)))\\\quad\vdots\\\lnot B\to((A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B)))\\(A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B))}\\A\to ((A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B)))\\\quad\vdots\\B\to((A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B)))\\(A\land B)\lor((\lnot A\land B)\lor(A\land\lnot B))}$$

You can always check the truth table to see the relation between two logical statements. All the well known / widly used relations are based on this.

Truth table of $$A\vee B$$ : $$\begin{array}{|c|c|c|} \hline B\backslash A&1&0\\\hline 1&1&1\\\hline 0&1&0\\\hline \end{array}$$

Truth table of $$\Big(\big(A \& B \big) \lor \big((\neg{}A \& B) \lor (A \& \neg{}B)\big)\Big)$$ : $$\begin{array}{|c|c|c|} \hline B\backslash A&1&0\\\hline 1&1\vee0\vee0=1&0\vee1\vee0=1\\\hline 0&0\vee0\vee1=1&0\vee0\vee0=0\\\hline \end{array}$$

and you can see the two logical statements are actually equivalent, that is, $$A\vee B\Leftrightarrow\Big(\big(A \& B \big) \lor \big((\neg{}A \& B) \lor (A \& \neg{}B)\big)\Big).$$