Proof by Contrapositive - Proof by Contraposition
- you assume that the conclusion is false and prove that the hypothesis is also false
- for example, the contrapositive of “If it is raining then the grass is wet” is “If the grass is not wet then it is not raining”
Proof by Contrapositive - Why it Works
conditional statements and contrapositive statements are tautological
|
Name |
antecedent (hypothesis) |
consequent |
conditional |
contrapositive | |||
|---|---|---|---|---|---|---|---|
|
Syntax |
𝑃 |
𝑄 |
¬𝑃 |
¬𝑄 |
𝑃 → 𝑄 |
¬𝑄 → ¬𝑃 | |
|
Given |
0 |
0 |
1 |
1 |
then |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
1 | ||
|
1 |
0 |
0 |
1 |
0 |
0 | ||
|
1 |
1 |
0 |
0 |
1 |
1 |
Proof by Contrapositive - Example #1
the contrapositive of “If it is raining then the grass is wet” is “If the grass is not wet then it is not raining”
Proof by Contrapositive - Example #2
exp
Let 𝑥 be an integer.
To prove: If 𝑥2 is even, then 𝑥 is even.
Although direct proof can be given, we choose to prove this statement by contraposition. The contrapositive of the above statement is:
If 𝑥 is not even, then 𝑥2 is not even.
This latter statement can be proven as follows: suppose that 𝑥 is not even, then 𝑥 is odd. The product of two odd numbers is odd, hence 𝑥2=𝑥⋅𝑥 is odd. Thus 𝑥2 is not even.
Having proved the contrapositive, we can then infer that the original statement is true