# Discrete Mathematics - Logical Equivalence

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

-

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

-

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

-
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