Page 108 - Discrete Mathematics and Its Applications

1.7 Introduction to Proofs 87

√
We have now shown that the assumption of ¬p leads to the equation 2 = a/b, where a
and b have no common factors, but both a and b are even, that is, 2 divides both a and b. Note
√
that the statement that 2 = a/b, where a and b have no common factors, means, in particular,
that 2 does not divide both a and b. Because our assumption of ¬p leads to the contradiction
that 2 divides both a and b and 2 does not divide both a and b, ¬p must be false. That is, the
√ √
statement p,“ 2 is irrational,” is true. We have proved that 2 is irrational. ▲

Proof by contradiction can be used to prove conditional statements. In such proofs, we first
assume the negation of the conclusion. We then use the premises of the theorem and the negation
of the conclusion to arrive at a contradiction. (The reason that such proofs are valid rests on the
logical equivalence of p → q and (p ∧¬q) → F. To see that these statements are equivalent,
simply note that each is false in exactly one case, namely when p is true and q is false.)
Note that we can rewrite a proof by contraposition of a conditional statement as a proof
by contradiction. In a proof of p → q by contraposition, we assume that ¬q is true. We then
show that ¬p must also be true. To rewrite a proof by contraposition of p → q as a proof by
contradiction, we suppose that both p and ¬q are true. Then, we use the steps from the proof
of ¬q →¬p to show that ¬p is true. This leads to the contradiction p ∧¬p, completing the
proof. Example 11 illustrates how a proof by contraposition of a conditional statement can be
rewritten as a proof by contradiction.

EXAMPLE 11 Give a proof by contradiction of the theorem “If 3n + 2 is odd, then n is odd.”

Solution: Let p be “3n + 2 is odd” and q be “n is odd.” To construct a proof by contradiction,
assume that both p and ¬q are true. That is, assume that 3n + 2 is odd and that n is not odd.
Because n is not odd, we know that it is even. Because n is even, there is an integer k such
that n = 2k. This implies that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). Because 3n + 2is
2t, where t = 3k + 1, 3n + 2 is even. Note that the statement “3n + 2 is even” is equivalent to
the statement ¬p, because an integer is even if and only if it is not odd. Because both p and
¬p are true, we have a contradiction. This completes the proof by contradiction, proving that if
3n + 2 is odd, then n is odd. ▲

Note that we can also prove by contradiction that p → q is true by assuming that p and
¬q are true, and showing that q must be also be true. This implies that ¬q and q are both
true, a contradiction. This observation tells us that we can turn a direct proof into a proof by
contradiction.

PROOFS OF EQUIVALENCE To prove a theorem that is a biconditional statement, that is,
a statement of the form p ↔ q, we show that p → q and q → p are both true. The validity of
this approach is based on the tautology

(p ↔ q) ↔ (p → q) ∧ (q → p).

2
EXAMPLE 12 Prove the theorem “If n is an integer, then n is odd if and only if n is odd.”
Solution: This theorem has the form “p if and only if q,” where p is “n is odd” and q is “n 2
is odd.” (As usual, we do not explicitly deal with the universal quantification.) To prove this
theorem, we need to show that p → q and q → p are true.
We have already shown (in Example 1) that p → q is true and (in Example 8) that q → p
is true.
Because we have shown that both p → q and q → p are true, we have shown that the
theorem is true. ▲