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.
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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) $$
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
