Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
Have you tried one of the two distributive laws. –  Rob Arthan Mar 20 '12 at 23:49
add comment

3 Answers

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|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
add comment

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

share|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.