1

How do I prove that $$\neg(\neg p\to (q\wedge p)) \equiv p\to (\neg q\wedge \neg p)$$

Edit 1: I need to do this prove without using a truth table. A table does indeed show that they are equivalent, but I cannot think of any basic or derivative laws that can help me do this. I believe I must be missing something here.

Edit 2: I started from $$(p\rightarrow\lnot q)\land\lnot p$$ $$\equiv (\lnot p\lor\lnot q)\land\lnot p$$ $$\equiv\lnot (p\land q)\land\lnot p$$ $$\equiv\lnot ((p\land q)\lor p)$$ $$\equiv\lnot (\lnot p\rightarrow (q\land p))$$ and got stuck right there.

Bcr20c
  • 13

1 Answers1

1

The sure way to solve problems like that is to build normal forms. Thus,

$\neg(\neg p\rightarrow(q\land p))\equiv\neg p\land\neg(q\land p)\equiv\neg p\land(\neg q\vee\neg p).$

This is the CNF of the left formula. Similarly, for the formula in the right we get

$p\rightarrow(\neg q\land\neg p)\equiv\neg p\vee(\neg q\land\neg p)\equiv(\neg p\vee\neg p)\land(\neg q\vee\neg p)\equiv\neg p\land(\neg q\vee\neg p).$

Both of them are equivalent to $\neg p\land(\neg q\vee\neg p)$, hence, they are equivalent.

Maxim Nikitin
  • 1,323
  • Thank you. This was what I needed, but may I know if there is a derivative "law" that tells us $$\lnot (P\rightarrow Q)\equiv P\land\lnot Q$$ Could this be related to the Reductio ad absurdum law? If so, I am unsure of that particular law. All I know is that $$p\rightarrow q\equiv (p\land\lnot q)\rightarrow contradiction$$ – Bcr20c Jun 17 '21 at 02:40
  • This follows from a chain of equivalences $\neg(P\rightarrow Q)\equiv\neg(\neg P\vee Q)\equiv(\neg\neg P\land\neg Q)\equiv(P\land\neg Q)$. The first step based on a well-known equivalence $P\rightarrow Q\equiv\neg P\vee Q$ and second one on De Morgan's law. – Maxim Nikitin Jun 17 '21 at 08:02
  • Thank you! My frustration blinded myself from seeing something this simple. Your help is greatly appreciated! – Bcr20c Jun 17 '21 at 23:25
  • I accepted the answer, but since I'm a new user, I don't meet the 15 rep required to upvote. – Bcr20c Jun 18 '21 at 08:27