0

When asked to show that Modus Tollens is sound in the propositional calculus, I tried to do this by enumerating all interpretations using a truth table. However I am unsure that my deductions are correct:

$\begin{array}{cc|ccc} P&Q&P\to Q&\overline{Q}&\overline{P}\\ \hline T&T&T&F&F\\ F&F&T&T&T\\ T&F&F&T&F\\ F&T&T&F&T \end{array}$

My understanding is the Modus Tollens is sound, because under the interpretation when $\neg Q$ (rows 1 and 4) and when the implication is true (rows1 and 4), then we can infer $\neg P$. For rows 1 and 2, P is T and F respectively, and the negation here also holds.

I feel that this is insufficient. But I am unsure as to what I am missing.

Martin Sleziak
  • 53,687
user1658296
  • 95

2 Answers2

1

We're missing two, so using your table:

$$\begin{align*}&(P\rightarrow Q)\wedge\neg Q\\&\;\;\;\;\;\;\;\;\;\;F\\&\;\;\;\;\;\;\;\;\;\;T\\&\;\;\;\;\;\;\;\;\;\;F\\&\;\;\;\;\;\;\;\;\;\;T\end{align*}$$

and finally

$$\begin{align*}&\left[(P\rightarrow Q)\wedge\neg Q\right]\rightarrow\neg P\\&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;T\\&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;T\\&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;T\\&\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;T\end{align*}$$

and we get tautology.

  • No, modus tollens doesn't involve a conjunction. It involves two propositions. – Doug Spoonwood Jul 04 '16 at 14:00
  • @DougSpoonwood As you can check wherever you like, it is the same: modus tollens requires that $;P\rightarrow Q;$ and $;\neg Q;$ are true so that $;\neg P;$ will be true. –  Jul 04 '16 at 14:11
  • @AntoineNemesioParras I think is correct, and I've seen this form of Modus Tollens in a couple of textbooks. One other question, with an inference rule, are we trying to infer the value of a proposition or it's Truth? By that I mean, do we care about inferring only Truth or whatever the proposition is, either T or F? --edit, 'sound' means true under every interpretation ... right? – user1658296 Jul 04 '16 at 15:48
  • @user1658296 I've seen it in both equivalent forms, indeed. In this special case we're trying to prove that whenever $;P\rightarrow Q;$ and $;\neg Q;$ are given, then we can infere $;\neg P;$ . As shown above (in the second table) , no matter what the truth values of the atoms $;P,Q;$ are, we get a tautology. –  Jul 04 '16 at 16:36
  • No, it's not the same. Modus tollens requires that (P -> Q) as well as $\lnot$P hold true. That means that we have two propositions holding true. What you wrote in the post consists of a single proposition with $\land$. $\land$ might not exist in the language, and there might not exist any other symbol for conjunction. We might have a system with just $\lnot$ and -> without any definitions, or work in the definition-free part of the language. – Doug Spoonwood Jul 05 '16 at 01:50
  • @DougSpoonwood It is my knowledge that in Prop. calculus all the basic connectives are assumed to exist unless otherwise stated. This, and the truth table the poster wrote in his question makes it clear that the connective $;\wedge;$ exists. Anyway, even if not we could use connectives equivalence as, for example, the set $;{\rightarrow,,\neg};$ is complete, though I think this is too much for a very elementary question. –  Jul 05 '16 at 06:04
  • The truth table doesn't mention $\land$. So, no, it doesn't make it clear that $\land$ exists. Additionally, NO formal proof (by which I mean a proof where every step is an axiom, a substitution instance of an axiom, or follows from the rules of inference specified) that uses modus tollens as a rule of inference has an inference from a conjunction ((p -> q) $\land$ $\lnot$q) to $\lnot$ p. They all have an infererence from two formulas one a substitution instance of (p -> q) and another a substitution instance of $\lnot$q. Consequently, modus tollens doesn't involve a conjunction. – Doug Spoonwood Jul 05 '16 at 09:45
  • As you wish, I don't intend to convince you. –  Jul 05 '16 at 10:39
  • @Doug Spoonwood \ The following is abstracted from the Wikipedia article "modus tollens": Formal notation The modus tollens rule may be written in sequent notation:

    $P\to Q$,$\neg Q\vdash \neg P$ where $\vdash$ is a metalogical symbol meaning that $\neg P$ is a syntactic consequence of $P\to Q$ and $\neg Q$ in some logical system;

    or as the statement of a functional tautology or theorem of propositional logic:

    $((P\to Q)\land \neg Q)\to \neg P$ where P and Q are propositions expressed in some formal system;

     – Senex Ægypti Parvi Jul 06 '16 at 08:41
0

By definition, an inference rule is sound if every expression produced by the rule from a set S of expressions also logically follows from S. Using your truth table, you may show that the expression ¬P logically follows from the set S = {(P→Q),¬Q} by pointing out that every interpretation that satisfies the expressions in S, in this case only row 2, also satisfies the inferred expression ¬P. Therefore, the inference by modus tollens is sound.

Chris D
  • 1