1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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