Page 105 - Discrete Mathematics and Its Applications

84 1 / The Foundations: Logic and Proofs

to show that n is odd? We see that 3n + 1 = 2k, but there does not seem to be any direct way
to conclude that n is odd. Because our attempt at a direct proof failed, we next try a proof by
contraposition.
The first step in a proof by contraposition is to assume that the conclusion of the conditional
statement “If 3n + 2 is odd, then n is odd” is false; namely, assume that n is even. Then, by
the definition of an even integer, n = 2k for some integer k. Substituting 2k for n, we find
that 3n + 2 = 3(2k) + 2 = 6k + 2 = 2(3k + 1). This tells us that 3n + 2 is even (because it
is a multiple of 2), and therefore not odd. This is the negation of the premise of the theorem.
Because the negation of the conclusion of the conditional statement implies that the hypothesis
is false, the original conditional statement is true. Our proof by contraposition succeeded; we
have proved the theorem “If 3n + 2 is odd, then n is odd.” ▲

√ √
EXAMPLE 4 Prove that if n = ab, where a and b are positive integers, then a ≤ n or b ≤ n.
√ √
Solution: Because there is no obvious way of showing that a ≤ n or b ≤ n directly from
the equation n = ab, where a and b are positive integers, we attempt a proof by contraposition.
The first step in a proof by contraposition is to assume that the conclusion of the conditional
√ √
statement “If n = ab, where a and b are positive integers, then a ≤ n or b ≤ n” is false. That
√ √
is,weassumethatthestatement(a ≤ n) ∨ (b ≤ n)isfalse.Usingthemeaningofdisjunction
√ √
together with De Morgan’s law, we see that this implies that both a ≤ n and b ≤ n are false.
√ √
This implies that a> n and b> n. We can multiply these inequalities together (using the
√ √
fact that if 0 <s <t and 0 <u< v, then su<tv) to obtain ab > n · n = n. This shows
that ab = n, which contradicts the statement n = ab.
Because the negation of the conclusion of the conditional statement implies that the hypoth-
esis is false, the original conditional statement is true. Our proof by contraposition succeeded;
√ √
we have proved that if n = ab, where a and b are positive integers, then a ≤ n or b ≤ n. ▲

VACUOUS AND TRIVIAL PROOFS We can quickly prove that a conditional statement
p → q is true when we know that p is false, because p → q must be true when p is false.
Consequently, if we can show that p is false, then we have a proof, called a vacuous proof,of
the conditional statement p → q. Vacuous proofs are often used to establish special cases of
theorems that state that a conditional statement is true for all positive integers [i.e., a theorem
of the kind ∀nP (n), where P (n) is a propositional function]. Proof techniques for theorems of
this kind will be discussed in Section 5.1.

2
EXAMPLE 5 Show that the proposition P(0) is true, where P (n) is “If n> 1, then n >n” and the domain
consists of all integers.
2
Solution: Note that P(0) is “If 0 > 1, then 0 > 0.” We can show P(0) using a vacuous
proof. Indeed, the hypothesis 0 > 1 is false. This tells us that P(0) is automatically true. ▲

2
Remark: The fact that the conclusion of this conditional statement, 0 > 0, is false is irrelevant
to the truth value of the conditional statement, because a conditional statement with a false
hypothesis is guaranteed to be true.

We can also quickly prove a conditional statement p → q if we know that the conclusion
q is true. By showing that q is true, it follows that p → q must also be true. A proof of p → q
that uses the fact that q is true is called a trivial proof. Trivial proofs are often important when
special cases of theorems are proved (see the discussion of proof by cases in Section 1.8) and
in mathematical induction, which is a proof technique discussed in Section 5.1.