Boolean Algebra equivalency

2.6k Views Asked by At

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

There are 2 best solutions below

9
On 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

0
On

$$(\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.