Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.