How can I prove that (x and ¬y) or (¬x and y) = ¬((x and y) or (¬x and ¬y))?

Question

I'm stuck at this problem:

(x and ¬y) or (¬x and y) = ¬((x and y) or (¬x and ¬y))

Basically what I have to do is to convert the right side of the equation to the left side using boolean algebra. I tried using De Morgan and other theorems, but I can not get the x and ¬y into the same brackets.

Answer 1

For the LHS :

(x and ¬y) or (¬x and y) = [(x and ¬y) or ¬x] and [(x and ¬y) or y]

by Distributivity.

Then, by Distributivity again :

= [(x or ¬x) and (¬x or ¬y)] and [(x or y) and (¬y or y)]

But : (x or ¬x) = (¬y or y) = 1.

Thus :

= [1 and (¬x or ¬y)] and [(x or y) and 1]

and 1 and a = a; so that :

= (¬x or ¬y) and (x or y).

Now, apply Double Negation :

= ¬(¬[(¬x or ¬y) and (x or y)]) = ¬(¬(¬x or ¬y) or ¬(x or y))

by De Morgan, and then :

=¬((x and y) or (¬x and ¬y))

by De Morgan again.