0

Let A, B and C be digital inputs. Prove that the following boolean equation holds true for any given values for inputs.

(A AND B) OR (A AND (NOT B) AND C) OR (B AND (NOT C)) = (A AND C) OR (B AND (NOT C))

This is a question with no solution in my circuit design book, I've googled and tried simplifying the equation to no avail.

Gerry Myerson
  • 179,216
user1075375
  • 115
  • 3
  • What kind of proof do you want? You can argue semantically, do a truth table prove it formally... – Git Gud Aug 05 '14 at 13:25
  • You can simplify the LHS by distributing $(A\land B)$ ($\land$ meaning AND) over the second monomial. If you don't manage to simplify, there still remains the possibility of checking the eight different inputs and see that the equality is valid. – zarathustra Aug 05 '14 at 13:26
  • @GitGud, I know truth table works for all such problems but it (book) asks for a simplification using the boolean identities and simplification. – user1075375 Aug 05 '14 at 13:38
  • @FPE, If only there wasn't a 'AND C' involved in the second monomial. – user1075375 Aug 05 '14 at 13:45

1 Answers1

1

Let us simplify the LHS, by taking $A$ out of the first two monomials.

$$\begin{align} (A\wedge B)\vee(A\wedge \neg B\wedge C)\vee(B\wedge\neg C) &= [A\land (B \lor (\neg B\land C))] \lor (B\land \neg C)\\ &= [A\land (B\lor C)]\lor (B\land\neg C)\\ &= (A\land B) \lor (A\land C)\lor (B\land \neg C). \end{align}$$

Note that this is not exactly the answer you were supposed to have. For the last step, suppose that $A\land B$ is true. If $C$ is true, then we have $A\land C$, and if $C$ is false, we have $B\land \neg C$. Hence we may rewrite the last line as $(A\land C)\lor (B\land\neg C)$. This reasoning could be done "internally", only by computation, by writing $A\land B$ as $A\land B\land(C\lor \neg C)$, as in the following:

$$\begin{align} (A\wedge B)\vee(A\wedge \neg B\wedge C)\vee(B\wedge\neg C) &=(A\land B) \lor (A\land C)\lor (B\land \neg C) \quad\text{from above}\\ &= (A\land B\land(C\lor\neg C))\lor (A\land C)\lor (B\land\neg C)\\ &= (A\land B\land C)\lor (A\land B\land\neg C)\lor (A\land C)\lor (B\land\neg C)\\ &= (A\land C)\lor (B\land \neg C) . \end{align}$$

zarathustra
  • 4,891