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

Question

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?

Answer 1

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). $$

Answer 2

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))}$$