# $p\to\neg q, q \vdash \neg p$- natural deduction

I have the following proposition:

$$p\to\neg q, q\vdash \neg p$$

Using the following formulas on propositions is easy enough:

$$\frac{\psi \qquad \psi\to\varphi}{\varphi}\quad \to_e$$

$$\frac{\psi\to\varphi \qquad \neg\varphi}{\neg\psi}\quad \to_{\rm MT}$$

However the statement $p\to\neg q$ above has a negation on $q$, so I'm not sure how to apply these formulas. Can someone help me out?

• I'm having trouble parsing your notation. Is it perhaps intended to be $\dfrac{\psi\quad \psi\to\phi}{\phi}\ \to_e$ and $\dfrac{\phi \to \phi\quad \neg \phi}{\neg \psi} \ \to_{MT}$? – Lord_Farin Jan 28 '15 at 20:39
• @Lord_Farin yes thats it, i couldn't figure out how to write it that way. – Bolboa Jan 28 '15 at 20:39

1) $p → ¬q$ --- premise

2) $q$ --- premise

3) $p$ --- assumed [a]

4) $\lnot q$ --- from 1) and 2) by $\rightarrow$-elimination

5) $\bot$ --- from 3) and 4) by $\rightarrow$-introduction

6) $\lnot p$ --- from 2) and 5) by $\lnot$-introduction, discharging assumption [a].

Thus, from 1), 2) and 8) we have :

$p → ¬q, q \vdash \lnot p$.

If you have the MT rule available, you have simply to apply it :

1) $p \rightarrow \lnot q$ --- premise

2) $q$ --- premise

3) $\lnot \lnot q$ --- from 2) by Double Negation

4) $\lnot p$ --- from 1) and 3) by MT.

• I do like this answer, but can it also be done without the use of assumption? If not, this will do. – Bolboa Jan 28 '15 at 20:44