Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

Any clues? Thanks in advance.

share|cite|improve this question
Have you tried one of the two distributive laws. – Rob Arthan Mar 20 '12 at 23:49
up vote 0 down vote accepted

$\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.

share|cite|improve this answer
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)$.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.