Rule of Transposition

Theorem

A statement and its contrapositive have the same truth value:

$p \implies q \dashv \vdash \neg q \implies \neg p$

Its abbreviation in a tableau proof is $\textrm{TP}$.

It is also known as the Rule of Contraposition.

Alternative Renditions

This can alternatively be rendered as:

• $\vdash \left({p \implies q}\right) \implies \left({\neg q \implies \neg p}\right)$

• $\vdash \left({\neg p \implies \neg q}\right) \implies \left({q \implies p}\right)$

or:

• $\vdash \left({p \implies q}\right) \iff \left({\neg q \implies \neg p}\right)$

They can be seen to be logically equivalent to the forms above by application of the Extended Rule of Implication.

Proof

Proof by Natural deduction

These are proved by the Tableau method.

This follows directly from Modus Tollendo Tollens:

$p \implies q \vdash \neg q \implies \neg p$

Line		Pool	Formula	Rule	Depends upon
1		1	$p \implies q$	P	(None)
2		2	$\neg q$	A	(None)
3		1, 2	$\neg p$	MTT	1, 2
4		1	$\neg q \implies \neg p$	$\implies \mathcal I$	2, 3

$\blacksquare$

$\neg q \implies \neg p \vdash p \implies q$

Line		Pool	Formula	Rule	Depends upon
1		1	$\neg q \implies \neg p$	P	(None)
2		2	$p$	A	(None)
3		2	$\neg \neg p$	$\neg \neg \mathcal I$	2
4		1, 2	$\neg \neg q$	MTT	1, 3
5		1, 2	$q$	$\neg \neg \mathcal E$	4
6		1	$p \implies q$	$\implies \mathcal I$	2, 5

$\blacksquare$

Comment

Note that the second part of this proof requires the use of double negation elimination, which depends on the Law of the Excluded Middle. This axiom is not accepted by the intuitionist school.

---

Proof by Truth Table

We apply the Method of Truth Tables to the proposition.

As can be seen by inspection, the truth values under the main connectives match for all models.

$\begin{array}{|ccc||ccccc|} \hline p & \implies & q & \neg & q & \implies & \neg & p \\ \hline F & T & F & T & F & T & T & F \\ F & T & T & F & T & T & T & F \\ T & F & F & T & F & F & F & T \\ T & T & T & F & T & T & F & T \\ \hline \end{array}$

$\blacksquare$

Sources

• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{I}: \S 5$: Theorem $\text{T13}, \ \text{T16}$
• Donald Kalish and Richard Montague: Logic: Techniques of Formal Reasoning (1964): $\text{II}: \S 5$: Theorem $\text{T111}$
• E.J. Lemmon: Beginning Logic (1965): $\S 1.2$: Theorem $9$
• Alan G. Hamilton: Logic for Mathematicians (1978): $\S 1.2$: Exercise $6 \ \text{(a)}$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 4$
• D.J. O'Connor and Betty Powell: Elementary Logic (1980): $\S 1.13$: Exercise $\text{(A)} \ 7$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): $\S 1.13$
• Michael R.A. Huth and Mark D. Ryan: Logic in Computer Science: Modelling and reasoning about systems (2000): $\S 1.2.1$: Exercises $1.4: 2 \ \text{(m)}, \ 1.5: 1 \ \text{(a)}$