# Equivalent formula - how do I go from $\neg (P \wedge \neg Q) \vee (\neg P \wedge Q)$ to $\neg P \vee Q$?

This is item "c" of question 11 from section 1.2 in Daniel J. Velleman's "How to Prove It - A Structured Approach" (great book).

The question asks that I find a simpler formula equivalent to $\neg (P \wedge \neg Q) \vee (\neg P \wedge Q)$, and the answer at the end of the book is $\neg P \vee Q$. I've tried DeMorgan and the associative and commutative laws, to no avail. I'm at my wit's end. All I got was $(\neg P \vee Q) \vee (\neg P \wedge Q)$.

-
Have you tried one of the two distributive laws. – Rob Arthan Mar 20 '12 at 23:49

$\neg (P \wedge \neg Q) \vee (\neg P \wedge Q)$

(de Morgan's)

$(\neg P \lor Q) \lor (\neg P \land Q)$

(distributivity; associativity)

$(\neg P \lor Q \lor \neg P) \land (\neg P \lor Q \lor Q)$

Should be easy to see from here.

-
Great, and now I see I overlooked the idempotent law. Thanks! – Georger Mar 20 '12 at 23:59
@Georger Make sure to understand Alex Becker's answer as well. – user2468 Mar 21 '12 at 0:00
I understand. It's just that the point of the question is to find a simpler equivalent formula using solely the laws. – Georger Mar 21 '12 at 0:07

Note that if $(\neg P \wedge Q)$ holds then $(\neg P \vee Q)$ holds, so $(\neg P \vee Q) \vee (\neg P \wedge Q)\iff (\neg P \vee Q)$.

-

Hint: Try $\neg(P\wedge \neg Q)$ first and then use the distributive law.

-