0
$\begingroup$

I need to prove the above sequent using natural deduction. I did the first half already i.e. I proved $(p\rightarrow\neg q)\rightarrow \neg (p \wedge q)$, but I'm stuck on where to start for the reverse i.e. proving $\neg (p \wedge q) \rightarrow (p\rightarrow\neg q)$. I figured I would start by assuming $\neg (p \rightarrow \neg q)$ and then working towards a contradiction, but I'm still at a dead end. Can someone point me in the right direction? Thanks.

$\endgroup$
6
  • $\begingroup$ Hint 1: what exact contradiction do you come up with when you evaluate $\neg (p \rightarrow \neg q)$? Hint 2: The contrapositive is your friend a lot of times with natural deduction. Give these a try and let us know what you come up with. $\endgroup$
    – ShyPerson
    Oct 15 '20 at 4:02
  • $\begingroup$ Hint 3: try to apply the techniques you applied proving the other direction of the conditional. Hint 4: try simplifying the expression to be proved by maybe removing terms or changing operators while still coming up with a correct valid expression. Then apply the proof techniques from the simpler problem to the hard one. $\endgroup$
    – ShyPerson
    Oct 15 '20 at 4:13
  • $\begingroup$ If nothing helps there is this neat online tool for helping you to prove intermediate steps. $\endgroup$
    – plshelp
    Oct 15 '20 at 5:54
  • $\begingroup$ @ShyPerson thanks so much! Hints 1 + 3 did the trick :) $\endgroup$
    – Smiley
    Oct 15 '20 at 6:47
  • $\begingroup$ @plshelp that's a great resource! definitely bookmarking for later on $\endgroup$
    – Smiley
    Oct 15 '20 at 6:48
0
$\begingroup$

Can we use that $a \to b$ is same as $\neg a \lor b$? If yes then: $$\neg (p \wedge q) \rightarrow (p\rightarrow\neg q) $$ is same as $$(\neg p \lor \neg p) \rightarrow (\neg p \lor \neg q) $$

$\endgroup$
0
$\begingroup$

As a hint, note that $\neg p$ means $p \rightarrow \hbox{False}$. (In some logics, this is the definition of negation.)

Therefore $\neg (p \wedge q) \leftrightarrow (p \rightarrow \neg q)$ means: $$\left( \left(p \wedge q\right) \rightarrow \hbox{False} \right)\leftrightarrow \left(p \rightarrow q \rightarrow \hbox{False}\right)$$

This is just Currying.

$\endgroup$
0
$\begingroup$

One of the ways is this:

LHS

We already know that

(𝑝→¬𝑞) = (¬𝑝 + ¬𝑞)

RHS

By demorgan's law,

¬(𝑝∧𝑞) = (¬𝑝 + ¬𝑞)

Since LHS and RHS are same, so they are equivalent.

$\endgroup$

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.