simplify(~(~(x | y) & ~(y | z)))

I don't understand why it is equivalent to x | y | z . Can someone please help to explain this to me?

Answer 1

[Jan]

Remember these equivalences ( De Morgan's laws ):

 ~(x | y) <==>  ~x & ~y
 ~(x & y) <==>  ~x | ~y

Then

~(~(x | y) & ~(y | z))         ==>
~((~x & ~y) & (~y & ~z))       ==>
~(~x & ~y) | ~(~y & ~z)        ==>
~~x | ~~y | ~~y | ~~z          ==>
x | y | y | z                  ==>
x | y | z

Applying the operations from the outside to the inside is faster:

~(~(x | y) & ~(y | z))         ==>
~~(x | y) | ~~(x | z)          ==>
x | y | y | z