1

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.

xxsl
  • 99

1 Answers1

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.

Mauro ALLEGRANZA
  • 94,169
  • Thank you for your answer. I got as far as you on the RHS using De Morgan. I can also understand your conclusion, but the way I have to prove it, is to convert one side of the equation in a way that it matches the other side (without modifying it). It would really help me, if you could show that too. – xxsl Nov 12 '14 at 16:54
  • Thank you very much, that helped me a lot to understand boolean algebra. – xxsl Nov 12 '14 at 17:06