# Boolean Algebra equivalency

Which Boolean algebra laws are required to show that

$$(\lnot y \land \lnot z) \lor (x \land ((\lnot y \land z) \lor (y \land \lnot z))) = (\lnot y \land \lnot z) \lor (x\land (\lnot (y \land z)))$$

I don't want to solve by computing for all possible values. No luck for me with distributive properties, absorption, idempotence, or DeMorgan's.

## 2 Answers

Sorry to disappoint, but if you want to "algebraically" prove the equivalence, you are going to need to use distributivity and DeMorgan's, and a couple more identities.

Since each side of the equivalence has the term $\;(\lnot y \land \lnot z) \lor,\;$

we can first focus on:

$$x \land ((\lnot y \land z) \lor (y \land \lnot z))) \equiv x\land (\lnot (y \land z)))$$

And now you see each side has an equivalent conjunct: $x \land\;$

Indeed, to prove: $$(\lnot y \land \lnot z) \lor (x \land (\lnot y \land z) \lor (y \land \lnot z))) \equiv (\lnot y \land \lnot z) \lor (x \land (\lnot (y \land z)))$$

we first focus on the following to check for equivalence:

$$\lnot (y \land z) \equiv^? (\lnot y \land z) \lor (y \land \lnot z)$$

There is no getting around using the distributive properties, absorption, and DeMorgan's, etc. but this breaks it down so as to make such applications relatively transparent.

$$\lnot (y \land z)\; \equiv^? \;(\lnot y \land z) \lor (y \land \lnot z)$$ $$\equiv\; [(\lnot y \land z) \lor y] \land [(\lnot y \land z )\lor \lnot z]\tag{distributivity}$$ $$\equiv [(\lnot y \lor y) \land (z \lor y)] \land [(\lnot y \lor \lnot z) \land (z \lor \lnot z)]\tag{?}$$

$$\equiv T \land (z \lor y) \land (\lnot y \lor \lnot z) \land T\tag{?}$$

$$\equiv (z \lor y) \land (\lnot y \lor \lnot z)\tag{?}$$

$$\vdots$$ $$\vdots$$

Don't forget that each side of the original equivalence is also also true whenever $\lnot y \land \lnot z \equiv \lnot (y \lor z)$ is true, as it is a disjunct to the expressions on each side, so if it holds, the equivalence holds.

So, e.g., if $x$ is false, then the expressions on the RHS and LHS are equivalent because then, the truth values of each expression is equivalent to the truth value of $\lnot p \land \lnot q$: i.e., each side evaluates to the equivalent truth value.

To prove algebraically, just keep the "disjunct" and $x \land$ "riding along" (operating only as you would above) until you can safely eliminate $x$ and/or make use of $\lnot p \land \lnot q$ to establish the equivalence.

Final Note Using the "$=$"-sign isn't really appropriate in logic. I have used the symbol for logical equivalence: "$\equiv$", which means (equivalently) $\iff$: "if and only if". It can be viewed as a logical connective in its own right. I'll include the truth-table displaying its truth-functional definition: • I looked at this but didn't think it works because don't we have $$\lnot (0 \land 0) = 1 \not= (\lnot 0 \land 0) \lor (0 \land \lnot 0) = ( 1 \land 0) \lor (0 \land 1) = 0$$ – Matt Munson Jan 21 '13 at 18:27
• Recall that we have the disjunct on each side to work with: $(\lnot y \land \lnot z)\lor...$ – amWhy Jan 21 '13 at 18:37
• Yeah, which is how I know the equations are equivalent. I just don't know how to use that to do an algebraic proof. Btw, what is a disjunct? Perhaps I should note that I've only learned my boolean algebra from an intro to comp sci class, and we have perhaps not gone very deep into the subject. – Matt Munson Jan 21 '13 at 18:39
• A disjunct is a term that is "or'ed" to another expression. $p \lor q$: both p and q are disjuncts in the expression. – amWhy Jan 21 '13 at 18:44
• To prove algebraically, just keep the "disjunct" and $x \land$ "riding along" (operating only as you would above) until you can safely eliminate $x$ and make use of $\lnot p \land \lnot q$ to establish the equivalence. – amWhy Jan 21 '13 at 18:49

$$(\lnot y \land \lnot z) \lor (x \land ((\lnot y \land z) \lor (y \land \lnot z)))$$

try to make it a disjunction of conjunctions (same idea as multiply out brackets of a polynomial)

$$(\lnot y \land \lnot z) \lor (x \land \lnot y \land z) \lor (x \land y \land \lnot z)$$

and the other side is

$$(\lnot y \land \lnot z) \lor (x\land (\lnot (y \land z)))$$

push negation in

$$(\lnot y \land \lnot z) \lor (x\land (\lnot y \lor \lnot z))$$

try to make it a disjunction of conjunctions

$$(\lnot y \land \lnot z) \lor (x\land \lnot y) \lor (x\land \lnot z)$$

to make the two terms equal we can use $a\lor b = a \lor (\lnot a \land b)$.

note $\lnot (\lnot y \land \lnot z) = y \lor z$ so we can make the LHS

$$(\lnot y \land \lnot z) \lor ((y \lor z) \land x\land \lnot y) \lor ((y \lor z) \land x\land \lnot z)$$

which simplifies to

$$(\lnot y \land \lnot z) \lor (z \land x\land \lnot y) \lor (y \land x\land \lnot z)$$

which is easily equal to the other side.