# Boolean Algebra

There seems to be some discrepancy between my answer and the solution's. Can somebody please tell me what I have done wrong? Thanks!

\begin{align} \left(A \lor B\right) \land \left(B \lor C\right) \land \left(\lnot A \lor C \right) & = \left(A+B \right)\left(B + C\right)\left( !A+C \right) \\ & = (A+B)(B!A+BC+C!A+CC) \\ & = (A+B)(B!A+BC+!AC+C) \\ &=(A+B)(B!A+C) \\ &=AB!A+AC+BB!A+BC\\ &=F+AC+B!A+BC \\ &=(A \land C) \lor (B \land \lnot A) \lor (B \land C) \text{ My answer}\\ \\ & \text{But solution says:} \\ &(A\land C)\lor(B \land \lnot A) \end{align}

-

If you work out the truth tables, you’ll see that the two answers are equivalent. Here’s a computational reduction:

\begin{align*} B\land C&=B\land C\land T\\ &=B\land C\land(A\lor\lnot A)\\ &=(B\land C\land A)\lor(B\land C\land\lnot A)\;, \end{align*}

so

\begin{align*} (A\land C)\lor(B\land\lnot A)\lor(B\land C)&=(A\land C)\lor(B\land\lnot A)\lor(B\land C\land A)\lor(B\land C\land\lnot A)\\ &=\Big((A\land C)\lor(B\land C\land A)\Big)\lor\Big((B\land\lnot A)\lor(b\land C\land\lnot A)\Big)\\ &=(A\land C)\lor(B\land\lnot A)\;. \end{align*}

The trick is to realize that one of $A$ and $\lnot A$ must be true, so if $B\land C$ is true, then either $B\land C\land A$ is true, or $B\land C\land\lnot A$ is true $-$ but these are both absorbed into the other two disjuncts, $A\land C$ and $B\land\lnot A$, that we already had.

-
Excellent answer! –  jyim Oct 21 '12 at 15:58
@jonathan: Glad it helped! –  Brian M. Scott Oct 21 '12 at 16:01

Both answers are good, but the $(B \land C)$ term is not necessary. If both $B$ and $C$ are true, then one of $(A \land C)$ or $(B \land \neg A)$ are satisfied too, depending on whether $A$ is true or not. Nevertheless, the result of the whole expressions is the same.

-
That makes so much sense...thanks! :D –  jyim Oct 21 '12 at 15:54

The $B \land C$ at the end of your answer is already satisfied by the previous parts, so it is not needed. So it is good, but it can be further simplified.

-