Boolean Arithmetic Simplification

1. Sep 25, 2011

BraedenP

1. The problem statement, all variables and given/known data

I am asked to prove that $(\sim x)\vee z = \sim(x\vee y)\vee\sim(y\vee\sim z)\vee\sim(x\vee\sim y)\vee\sim(\sim y\vee\sim z)$.

I've tried using all combinations of DeMoran's rule, the distributive rule to get the y terms together, and the absorption rule to get rid of the y (which is required in order to simplify it down in terms of x and z.

2. Relevant equations

DeMorgan's Rule: $\sim(p\wedge q) = \sim p\vee\sim q$
Absorption Rule: $p\vee(p\wedge q) = p$

3. The attempt at a solution

I can post some of the steps I've taken, but none really lead anywhere. Where is a good place to start for a question like this?

2. Sep 26, 2011

Staff: Mentor

Convert the OR's contained within brackets to AND's using DeMorgan's rules.

3. Sep 26, 2011

BraedenP

Thanks -- yeah, I was trying that before, but couldn't get it simplified down enough.

I got the solution now (and it wasn't too hard). I just had to use DeMorgan's and the distributive rule to get rid of all the Ys first, and then everything else just fell into place without much effort.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook