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

Question

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!

Answer 1

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}$$

Answer 2

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$.