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!

  • $\begingroup$ 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$ $\endgroup$ – Bram28 Jan 28 '17 at 21:42
  • $\begingroup$ What is $\vdash$? $\endgroup$ – zoli Jan 28 '17 at 21:51
  • $\begingroup$ In this context I use it with the meaning: the right-hand side is provable from the left-hand side $\endgroup$ – David Jan 28 '17 at 21:53
  • $\begingroup$ 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. $\endgroup$ – DanielV Jan 28 '17 at 22:07


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.

  • $\begingroup$ Thank you for the hint. However, this is exactly where I ran out of ideas ($\neg p \vdash p \to q $) $\endgroup$ – David Jan 28 '17 at 21:56
  • $\begingroup$ I'll edit the answer. $\endgroup$ – SSepehr Jan 28 '17 at 21:56
  • $\begingroup$ 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. $\endgroup$ – David Jan 28 '17 at 22:19

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.