# Natural deduction proof of $p \rightarrow q \vdash \lnot(p \land \lnot q)$

So yeah, the entire question is pretty much in the title. $$p \rightarrow q \vdash \lnot(p \land \lnot q)$$

I've been able to derive the reverse, but I don't how to logically go from the premise to the conclusion using natural deduction only. I can see that the two formulas are equal using transformations.

These are the rules I'm allowed to use:

$1.$ $p \rightarrow q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ -- (Premise)

$2.$ $p \wedge \neg q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ -- (Assume the contrary to what has to be proved in the conclusion)

$3.$ $p \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ -- ($\wedge E$ on $2.$)

$4.$ $\neg q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ -- ($\wedge E$ on $2.$)

$5.$ $q \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ -- (Modus ponens on $1.$ and $3.$)

$6.$ $\bot \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ -- (bot introduction due to contradiction on $4.$ and $5.$)

$7.$ $\neg(p \wedge \neg q) \ \ \ \ \ \ \ \ \ \ \$ --(assumption wrong due to arrival of contradiction)

• Fantastic, thank you. I knew I need to show $p \land \lnot q$ is false based on steps 3, 4 and 5, but I just couldn't think of the process. – Shiny_and_Chrome Jan 12 '17 at 6:06