Section 2.1 Proof Techniques
101
Direct Proof
In general (where exhaustive proof won’t work), how can you prove that P S Q
is true? The obvious approach is the direct proof—assume the hypothesis P and
deduce the conclusion Q. A formal proof would require a proof sequence leading
from P to Q.
Example 4 shows a formal proof that if two numbers are even (that’s the
hypothesis P), then their product is even (that’s the conclusion Q). Recall that an
even number is a number that is an integral multiple of 2, for example, 18 is even
because 18 = 2(9). An odd number is 1 more than an integral multiple of 2, for
example, 19 = 2(9) + 1.
PrACTiCe 2
a. Prove the conjecture “For any positive integer less than or equal to 5, the square of the integer
is less than or equal to the sum of 10 plus 5 times the integer.”
b. Disprove the conjecture “For any positive integer, the square of the integer is less than or equal
to the sum of 10 plus 5 times the integer.”
eXAMPLe 3
Prove the conjecture, “It is not possible to trace all the lines in Figure 2.1 without
lifting your pencil and without retracing any lines.”
There is only a finite number of different ways to trace
the lines in the figure. By careful bookkeeping, each of the
possibilities can be attempted, and each will fail. In Chapter 7, we will learn a much less tedious way to solve this
problem than proof by exhaustion.
Figure 2.1
■
eXAMPLe 4
Consider the conjecture
x is an even integer ` y is an even integer S the product xy is an even integer
A complete formal proof sequence might look like the following:
1. x is an even integer ` y is an even integer
hyp
2. (4x)[x is even integer S
number fact ( definition
(Ek)(k an integer ` x = 2k)]
of even integer)
3. x is even integer S (Ek)(k an integer ` x = 2k)
2, ui
4. y is even integer S (Ek)(k an integer ` y = 2k)
2, ui
5. x is an even integer
1, sim
6. (Ek)(k is an integer ` x = 2k)
3, 5, mp
7. m is an integer ` x = 2m
6, ei
8. y is an even integer
1, sim
9. (Ek)(k an integer ` y = 2k)
4, 8, mp
10. n is an integer and y = 2n
9, ei
11. x = 2m
7, sim
12. y = 2n
10, sim
101
Direct Proof
In general (where exhaustive proof won’t work), how can you prove that P S Q
is true? The obvious approach is the direct proof—assume the hypothesis P and
deduce the conclusion Q. A formal proof would require a proof sequence leading
from P to Q.
Example 4 shows a formal proof that if two numbers are even (that’s the
hypothesis P), then their product is even (that’s the conclusion Q). Recall that an
even number is a number that is an integral multiple of 2, for example, 18 is even
because 18 = 2(9). An odd number is 1 more than an integral multiple of 2, for
example, 19 = 2(9) + 1.
PrACTiCe 2
a. Prove the conjecture “For any positive integer less than or equal to 5, the square of the integer
is less than or equal to the sum of 10 plus 5 times the integer.”
b. Disprove the conjecture “For any positive integer, the square of the integer is less than or equal
to the sum of 10 plus 5 times the integer.”
eXAMPLe 3
Prove the conjecture, “It is not possible to trace all the lines in Figure 2.1 without
lifting your pencil and without retracing any lines.”
There is only a finite number of different ways to trace
the lines in the figure. By careful bookkeeping, each of the
possibilities can be attempted, and each will fail. In Chapter 7, we will learn a much less tedious way to solve this
problem than proof by exhaustion.
Figure 2.1
■
eXAMPLe 4
Consider the conjecture
x is an even integer ` y is an even integer S the product xy is an even integer
A complete formal proof sequence might look like the following:
1. x is an even integer ` y is an even integer
hyp
2. (4x)[x is even integer S
number fact ( definition
(Ek)(k an integer ` x = 2k)]
of even integer)
3. x is even integer S (Ek)(k an integer ` x = 2k)
2, ui
4. y is even integer S (Ek)(k an integer ` y = 2k)
2, ui
5. x is an even integer
1, sim
6. (Ek)(k is an integer ` x = 2k)
3, 5, mp
7. m is an integer ` x = 2m
6, ei
8. y is an even integer
1, sim
9. (Ek)(k an integer ` y = 2k)
4, 8, mp
10. n is an integer and y = 2n
9, ei
11. x = 2m
7, sim
12. y = 2n
10, sim