1
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ Are you able to prove $p\to q ⊢ \neg p \lor q$? $\endgroup$ – Javi Aug 2 '18 at 21:18
  • 2
    $\begingroup$ Already asked and answered in PhilSE $\endgroup$ – Mauro ALLEGRANZA Aug 3 '18 at 6:03
2
$\begingroup$

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

Natural deduction proof of ~(P -> Q) |- P /\ ~Q

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Many thanks for your answer. However I cannot get those conditionals yet. Could you please clarify me more on this? $\endgroup$ – Diego Ruiz Haro Aug 2 '18 at 22:31
  • $\begingroup$ Upvoted because I believe your answer with the outline and hints should be seen before mine with the full solution. $\endgroup$ – Daniel Schepler Aug 2 '18 at 22:45
  • $\begingroup$ @DiegoRuizHaro You cannot see why $q$ would hold under the assumption of $q$ and $p$? Or under the assumption of $\neg p$ and $p$? $\endgroup$ – Graham Kemp Aug 2 '18 at 23:09
  • $\begingroup$ Ah... Do you have access to Ex Falso Quodlibet ? $\endgroup$ – Graham Kemp Aug 3 '18 at 0:52
  • $\begingroup$ @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 $\endgroup$ – Diego Ruiz Haro Aug 3 '18 at 5:46

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.