1 Logic 1.6 Useful logical equivalences 1.8 Adequacy

1.7 The contrapositive

The following logical equivalence shows us that every WFF that uses $\implies$ can be written with $\neg$ and $\vee$ instead.

Theorem 1.7.1.

Let $\phi$ and $\psi$ be WFFs. Then

(\phi\implies\psi)\equiv(\neg\phi\vee\psi).

Here is the truth table that proves this result:

$\phi$	$\psi$	$(\phi\implies\psi)$	$(\neg\phi\vee\psi)$
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

This equivalence is commonly used when proving a statement like “ $a$ implies $b$ .” Proofs of statements in this form are often carried out by assuming that $a$ is true and then deducing that $b$ is also true. Why is that sufficient to prove $(a\implies b)$ ?

Suppose that if $a$ is true, so is $b$ . If $a$ is false then $\neg a$ is true, so $(\neg a\vee b)$ is true no matter what the statements $a$ and $b$ were. On the other hand if $a$ is true we know $b$ is true as well, so $(\neg a\vee b)$ is true in that case too. So regardless of the truth value of $a$ , the formula $(\neg a\vee b)$ is true. Because this is logically equivalent to $(a\implies b)$ , we’re done.

1.7.1 The contrapositive

The contrapositive of an implication $(a\implies b)$ is by definition $(\neg b\implies\neg a)$ . For example, the contrapositive of “if it’s Monday, then it’s raining” is “if it’s not raining, then it’s not Monday.” We are going to use the logical equivalence of the previous section to show that an implication is logically equivalent to its contrapositive.

Theorem 1.7.2.

Let $\phi$ and $\psi$ be WFFs. Then

(\phi\implies\psi)\equiv(\neg\psi\implies\neg\phi).

Proof.

You can check the truth tables for these two statements, or you can do this:

$\displaystyle(\phi\implies\psi)$	$\displaystyle\equiv(\neg\phi\vee\psi)$	Theorem 1.7.1
	$\displaystyle\equiv(\neg\phi\vee\neg\neg\psi)$	Theorem 1.6.2
	$\displaystyle\equiv(\neg\neg\psi\vee\neg\phi)$	Theorem 1.5.1
	$\displaystyle\equiv(\neg\psi\implies\neg\phi)$	Theorem 1.7.1

∎

Again this is very useful as a proof technique. If you want to prove $(a\implies b)$ , it is logically equivalent to prove the contrapositive $(\neg b\implies\neg a)$ , and this is sometimes easier. An example is

$x^{2}$ is an irrational number implies $x$ is an irrational number.

This statement is true, but the contrapositive “ $x$ is rational implies $x^{2}$ is rational” is easier to prove because $x$ being rational actually tells you something specific (that $x=p/q$ for some whole numbers $p$ and $q$ ) which you can use to make the proof work. There are further examples given in this blog post by Timothy Gowers.

1.7.2 The converse

Don’t confuse the contrapositive of an implies statement with its converse. The converse of $(\phi\implies\psi)$ is defined to be $(\psi\implies\phi)$ , and these two are not in general logically equivalent. (You should think of a truth assignment to show that $(p\implies q)$ and $(q\implies p)$ are not logically equivalent.)