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.

I am stuck on the following problem:

Without using a truth table, show for statements $P$ and $Q$ that $$\neg (P\vee((\neg P)\wedge Q)) \equiv (\neg P)\wedge(\neg Q)$$

Using De Morgan's laws I simplify the left side to $(\neg P)\wedge(\neg((\neg P)\wedge Q))$

Which then, using De Morgan's once again, simplifies to $(\neg P)\wedge(P\vee(\neg Q))$.

Then, using the distributive law, I get $((\neg P)\wedge P)\vee((\neg P)\wedge(\neg Q))$.

(In the solution section in the book, at this step the book has $((\neg P)\wedge P)\vee((\neg P)\vee(\neg Q))$, which I don't really understand how it gets $((\neg P)\vee(\neg Q))$. I am not sure if I am misunderstanding something, making an error, or if it's a typo in the book.)

After this step, I am not really sure how to simplify any further. How can I get from $((\neg P)\wedge P)\vee((\neg P)\wedge(\neg Q))$ to $(\neg P)\wedge(\neg Q)$?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

The solution in the book clearly has a typo; $\neg P\land\neg Q$ is right, and $\neg P\lor\neg Q$ is wrong. The last step is to notice that $\neg P\land P\equiv\bot$ (or whatever symbol you use for a contradiction), and $\bot\lor R\equiv R$ for any $R$.

share|improve this answer

Hint: $\neg P \wedge P = F{}{}$

share|improve this answer
    
That's what I was thinking, but I thought I might need to show my steps in detail. –  SherMM Sep 27 '13 at 2:05
    
I thought this is pretty much an identity. After all, the negation of a statement and a statement cannot hold at the same time. –  peterwhy Sep 27 '13 at 2:08
    
I think the typo in the book messed me up, and I started over-thinking the problem. –  SherMM Sep 27 '13 at 2:16

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.