Proving $\neg(p \to q)$ equivalent to $p \wedge \neg q$ using natural deduction

I need some help proving $$\neg(p \to q)\vdash p \wedge \neg q$$ using natural deduction.

So far I've tried using the Law of excluded middle ($p \lor \neg p$). With this approach, I can complete the first half but have no clue how to finish the rest.

The solution can make use of and, or, not, implies introduction/elimination and the law of excluded middle.

Any idea or help is appreciated!

• I don't know the exact inference rules you are allowed to work with, but if you were able to get $p$ using $p \lor \neg p$, you should be able to get $\neg q$ from $q \lor \neg q$ – Bram28 Jan 28 '17 at 21:42
• What is $\vdash$? – zoli Jan 28 '17 at 21:51
• In this context I use it with the meaning: the right-hand side is provable from the left-hand side – David Jan 28 '17 at 21:53
• If you can use LEM, then break the proof into 4 cases, of $p$, $q$ being true / false. Then stitch the cases together with Or-Elimination. – DanielV Jan 28 '17 at 22:07

Hint:

first prove that $$\neg p\vdash p\rightarrow q$$ and $$q\vdash p\rightarrow q.$$

From here it must be easy to show that $$\neg(p \to q)\vdash p$$ and $$\neg(p \to q)\vdash \neg q.$$

Then the result follows from $\wedge I$.

To prove $\neg p\vdash p\rightarrow q$, assuming $\neg p$ we have to deduce $p \rightarrow q$. assuming $p$ and using $\neg E$ we get $\bot$, and from there using $\bot$ law, we can deduce $q$, and then deduce $p\rightarrow q$ by $\rightarrow I$ and discharge the assumption $p$. The proof is complete.

• Thank you for the hint. However, this is exactly where I ran out of ideas ($\neg p \vdash p \to q$) – David Jan 28 '17 at 21:56
• I'll edit the answer. – SSepehr Jan 28 '17 at 21:56
• Thanks. I now see that the solution is very straightforward. I am using some software to do these proofs and it has some constraints, but I've been able to eventually work around them. – David Jan 28 '17 at 22:19