# Prove (p → ¬q) is equivalent to ¬(p ∧ q)

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.

• 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. – ShyPerson Oct 15 '20 at 4:02
• 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. – ShyPerson Oct 15 '20 at 4:13
• If nothing helps there is this neat online tool for helping you to prove intermediate steps. – plshelp Oct 15 '20 at 5:54
• @ShyPerson thanks so much! Hints 1 + 3 did the trick :) – Smiley Oct 15 '20 at 6:47
• @plshelp that's a great resource! definitely bookmarking for later on – Smiley Oct 15 '20 at 6:48

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)$$

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.

One of the ways is this:

LHS