Section 2.1 Proof Techniques
103
Contraposition
If you have tried diligently but failed to produce a direct proof of your conjecture
P S Q, and you still feel that the conjecture is true, you might try some variants
on the direct proof technique. If you can prove the theorem Q′ S P′, you can
conclude P S Q by making use of the tautology (Q′ S P′) S (P S Q). Q′ S P′
is the contrapositive of P S Q, and the technique of proving P S Q by doing a
direct proof of Q′ S P′ is called proof by contraposition. (The contraposition
rule of inference in propositional logic (Table 1.14) says that P S Q can be derived
from Q′ S P′.)
eXAMPLe 6
Prove that if the square of an integer is odd, then the integer must be odd.
The conjecture is n
2
odd S n odd. We do a proof by contraposition, and prove
n even S n
2
even. Let n be even. Then n
2
= n(n) is even by Example 5.
eXAMPLe 7
Prove that if n + 1 separate passwords are issued to n students, then some student
gets ≥ 2 passwords.
Here the conclusion Q has the form (Ex)R(x), so Q′ is [(Ex)R(x)]′, which is
equivalent to (4x)[R(x)]′. The contrapositive Q′ S P′ is, “If every student gets
< 2 passwords, then it is false that n + 1 passwords were issued.” Suppose every
student has < 2 passwords; then every one of the n students has at most 1 password. The total number of passwords issued is at most n, not n + 1, so it is false
that n + 1 passwords were issued.
Example 7 is an illustration of the pigeonhole principle, which we will see in
Chapter 4.
Practice 7 of Chapter 1 showed that the wffs A S B and B S A are not
equivalent. B S A is the converse of A S B. If an implication is true, its converse
may be true or false. Therefore, you cannot prove P S Q by looking at Q S P.
PrACTiCe 4 Write the contrapositive of each statement in Practice 5 of Chapter 1.
■
eXAMPLe 8
The implication “If a > 5, then a > 2” is true, but its converse, “If a > 2, then
a > 5,” is false.
PrACTiCe 3 Give a direct proof (informal) of the theorem “If an integer is divisible by 6, then twice
that integer is divisible by 4.”
■
103
Contraposition
If you have tried diligently but failed to produce a direct proof of your conjecture
P S Q, and you still feel that the conjecture is true, you might try some variants
on the direct proof technique. If you can prove the theorem Q′ S P′, you can
conclude P S Q by making use of the tautology (Q′ S P′) S (P S Q). Q′ S P′
is the contrapositive of P S Q, and the technique of proving P S Q by doing a
direct proof of Q′ S P′ is called proof by contraposition. (The contraposition
rule of inference in propositional logic (Table 1.14) says that P S Q can be derived
from Q′ S P′.)
eXAMPLe 6
Prove that if the square of an integer is odd, then the integer must be odd.
The conjecture is n
2
odd S n odd. We do a proof by contraposition, and prove
n even S n
2
even. Let n be even. Then n
2
= n(n) is even by Example 5.
eXAMPLe 7
Prove that if n + 1 separate passwords are issued to n students, then some student
gets ≥ 2 passwords.
Here the conclusion Q has the form (Ex)R(x), so Q′ is [(Ex)R(x)]′, which is
equivalent to (4x)[R(x)]′. The contrapositive Q′ S P′ is, “If every student gets
< 2 passwords, then it is false that n + 1 passwords were issued.” Suppose every
student has < 2 passwords; then every one of the n students has at most 1 password. The total number of passwords issued is at most n, not n + 1, so it is false
that n + 1 passwords were issued.
Example 7 is an illustration of the pigeonhole principle, which we will see in
Chapter 4.
Practice 7 of Chapter 1 showed that the wffs A S B and B S A are not
equivalent. B S A is the converse of A S B. If an implication is true, its converse
may be true or false. Therefore, you cannot prove P S Q by looking at Q S P.
PrACTiCe 4 Write the contrapositive of each statement in Practice 5 of Chapter 1.
■
eXAMPLe 8
The implication “If a > 5, then a > 2” is true, but its converse, “If a > 2, then
a > 5,” is false.
PrACTiCe 3 Give a direct proof (informal) of the theorem “If an integer is divisible by 6, then twice
that integer is divisible by 4.”
■