[Math] Boolean Algebra equivalency

boolean-algebralogicpropositional-calculus

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.

Best Answer

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:

enter image description here