Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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.

share|improve this answer
    
Excellent answer! –  jyim Oct 21 '12 at 15:58
    
@jonathan: Glad it helped! –  Brian M. Scott Oct 21 '12 at 16:01
add comment

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.

share|improve this answer
    
That makes so much sense...thanks! :D –  jyim Oct 21 '12 at 15:54
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.