[Math] Showing that Modus Tollens is sound

propositional-calculus

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.

Best Answer

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.

Related Question