# How to prove $\lnot(p\to q)\vdash p \land\lnot q$

This is the first time I post anything on the forum. I started with Tomassi's Logic and unfortunately I have been unable to solve some of its problems. One I get immediately stuck with is this one:

$$\lnot(p\to q)\vdash p \land\lnot q$$

I have to solve it by natural deduction and the only rules I know are: assumptions, modus ponendo ponens, modus tollendo tollens, double negation, reductio ad absurdum, conditional proof, v-introduction, v-elimination, introduction, and elimination. Tomassi's proof consists of 12 steps.

Moreover, I don't see how to proceed because of the negations on the outside of the parentheses.

Thanks for the help!

• Are you able to prove $p\to q ⊢ \neg p \lor q$? – Javi Aug 2 '18 at 21:18

I used http://proofs.openlogicproject.org/ to construct a more or less Fitch-style natural deduction proof. Overview of the idea that this proof is just formalizing:

Suppose we have $\lnot (P \to Q)$. Then we first prove $P$. Suppose, to the contrary, that we have $\lnot P$; then assuming $P$, we have a contradiction which also allows to conclude $Q$ via ex falso quodlibet. Thus, if $P$ were false, then $P \to Q$ would be true, giving a contradiction with the assumption $\lnot (P \to Q)$. Therefore, $P$ must be true. Likewise, we also need to prove $\lnot Q$. So, suppose $Q$ were true; then we would automatically have $P \to Q$, again contradicting the assumption $\lnot (P \to Q)$. Finally, since we have proved $P$ and we have also proved $\lnot Q$, we conclude $P \wedge \lnot Q$. You wish to prove the negation of a conditional entails a conjunction.   Your strategy should therefore be to prove the conditional is entailed by the negation of each of the conjuncts.

That requires two negation introductions with their supproofs containing a conditional introduction, then double negation elimination where needed, and conjunction introduction.

$\def\fitch#1#2{~~\begin{array}{|l} #1\\\hline #2\end{array}} \fitch{\neg(p\to q)}{\fitch{q}{\fitch{p}{\vdots\\q}\\p\to q\\\bot}\\\neg q\\\fitch{\neg p}{\fitch{p}{\vdots\\q}\\p\to q\\\bot}\\\neg\neg p\\p\\ p\wedge\neg q}$

I'll leave to you, how to introduce that conditional under each assumption.

You could also try showing that the conditional is entailed by negating the conjunction.   Show that if $\neg(p\wedge\neg q)$ and $p$ then $q$.

$$\fitch{\neg (p\to q)}{\fitch{\neg(p\wedge \neg q)}{\fitch{p}{\vdots\\q}\\p\to q\\\bot}\\\neg\neg(p\wedge\neg q)\\p\wedge\neg q}$$

• Many thanks for your answer. However I cannot get those conditionals yet. Could you please clarify me more on this? – Diego Ruiz Haro Aug 2 '18 at 22:31
• Upvoted because I believe your answer with the outline and hints should be seen before mine with the full solution. – Daniel Schepler Aug 2 '18 at 22:45
• @DiegoRuizHaro You cannot see why $q$ would hold under the assumption of $q$ and $p$? Or under the assumption of $\neg p$ and $p$? – Graham Kemp Aug 2 '18 at 23:09
• Ah... Do you have access to Ex Falso Quodlibet ? – Graham Kemp Aug 3 '18 at 0:52
• @GrahamKemp I have no access to Ex Falso Quodlibet. I only know: · assumptions, · modus ponendo ponens, · modus tollendo tollens, · double negation, · reductio ad absurdum, · conditional proof, · v-introduction, v-elimination, · &-introduction, and &-elimination – Diego Ruiz Haro Aug 3 '18 at 5:46