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$

2 Answers 2

Reset to default
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, 2013 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, 2013 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, 2013 at 2:16

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .