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
  • 2
    $\begingroup$ Are you able to prove $p\to q ⊢ \neg p \lor q$? $\endgroup$
    – Javi
    Aug 2, 2018 at 21:18
  • 2
    $\begingroup$ Already asked and answered in PhilSE $\endgroup$ Aug 3, 2018 at 6:03

2 Answers 2

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$
6
  • $\begingroup$ Many thanks for your answer. However I cannot get those conditionals yet. Could you please clarify me more on this? $\endgroup$ Aug 2, 2018 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$ Aug 2, 2018 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$ Aug 2, 2018 at 23:09
  • $\begingroup$ Ah... Do you have access to Ex Falso Quodlibet ? $\endgroup$ Aug 3, 2018 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$ Aug 3, 2018 at 5:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .