1
$\begingroup$

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.

  • 1
    Have you tried one of the two distributive laws.2012-03-20

3 Answers 3

0

For an alternative approach you can make the truth table of both logical expressions. $ \begin{array}{|c|c| c|c| c|c| c|c| c|} \hline P & Q & \neg P & \neg Q & \neg (P \wedge \neg Q) & (\neg P \wedge Q) & \neg (P \wedge \neg Q) \vee (\neg P \wedge Q) \\\hline V & V & F & F & V & F & V \\\hline V & F & F & V & F & F & F \\\hline F & V & V & F & V & V & V \\\hline F & F & V & V & V & F & V \\\hline \end{array} $ and $ \begin{array}{|c|c| c|c|} \hline P&Q&\neg P& \neg P \vee Q \\\hline V&V&F& V \\\hline V&F&F& F \\\hline F&V&V& V \\\hline F&F&V& V \\\hline \end{array} $

1

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

0

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

  • 0
    I understand. It's just that the point of the question is to find a simpler equivalent formula using solely the laws.2012-03-21