-1
$\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$
  • $\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.