# Prove the identity in this boolean equation

$$AD'+A'B+C'D+B'C=(A'+B'+C'+D')(A+B+C+D)$$

Don't know where to begin with this.

-

## 1 Answer

The right-hand side is true unless none or all of the variables are true. The left-hand side is also not true if none or all of the variables are true, so it remains to be shown only that the left-hand side is true if not none or all of the variables are true, that is, if one to three of them are true. If exactly one of the variables is true, or exactly one isn't (and thus three are), then the summand containing a true factor containing the odd one out is true. Checking the case where exactly two variables are true is only slightly more involved.

If you prefer a proof using the axioms of Boolean algebra, check out this answer for how to eliminate terms in the sum you get when you multiply out the product on the right-hand side.

-
By the same reasoning the LHS could be $XY'+YZ'+ZT'+TX'$ as soon as $\{X,Y,Z,T\}=\{A,B,C,D\}$ since this also encodes the set [no unanimity amongst $X$, $Y$, $Z$, $T$] which obviously coincides with [no unanimity amongst $A$, $B$, $C$, $D$]. –  Did Feb 20 '13 at 7:01
I tried that method but ended up going nowhere joriki –  Aaron Feb 20 '13 at 7:14
@Aaron: Which of the two methods are you referring two? If you describe where you got stuck, more might be said. –  joriki Feb 20 '13 at 7:16
Axioms of boolean algebra –  Aaron Feb 21 '13 at 2:25
@Aaron: All you need is in the answer I linked to. I won't be writing any more here unless you state specifically what's causing you trouble. –  joriki Feb 21 '13 at 2:27