1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Truth table. ${}{}{}$ $\endgroup$ Commented Jun 16, 2021 at 17:08
  • $\begingroup$ Specifically without a truth table. I'll add this to the question. My apologies. $\endgroup$ Commented Jun 16, 2021 at 17:09
  • $\begingroup$ Please use MathJax. Here's a tutorial. Also, please provide context for your query. You can find information on how to ask questions here. $\endgroup$ Commented Jun 16, 2021 at 17:13
  • $\begingroup$ Thank you. I have added my workings in an edit. $\endgroup$ Commented Jun 16, 2021 at 19:14
  • $\begingroup$ I feel like I should make a "propositional-calculus-without-truth-tables" tab like I did "limits-without-lhopital" hah. $\endgroup$ Commented Jun 16, 2021 at 19:56

1 Answer 1

Reset to default
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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$$ $\endgroup$ Commented Jun 17, 2021 at 2:40
  • $\begingroup$ 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. $\endgroup$ Commented Jun 17, 2021 at 8:02
  • $\begingroup$ Thank you! My frustration blinded myself from seeing something this simple. Your help is greatly appreciated! $\endgroup$ Commented Jun 17, 2021 at 23:25
  • $\begingroup$ I accepted the answer, but since I'm a new user, I don't meet the 15 rep required to upvote. $\endgroup$ Commented Jun 18, 2021 at 8:27

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.