← | Table of contents | → |
To prove A → B, assume that A is true and prove that B is true. That is, add A to the fact bank and then proceed to prove B.
Theorem. For all integers x and y, if xy is even and x+y is even then both x and y are even.
Proof. Select arbitrary integers x and y. Our goal is now to prove the implication for those particular arbitrary values x and y, namely: if xy is even and x+y is even then both x and y are even. Add the left-hand side of the implication to the fact bank.
(1) xy is evenThe product of two odd integers is odd. So, in order for (1) to be true, it is required that
(2) x+y is even
(3) x and y are not both odd.In order for x+y to be even, either x and y are both odd or both even. (The sum of an odd number and an even number is odd.) So, from (2),
(4) Either x and y both even or x and y are both odd.But since x and y are not both odd (fact (3)), the only available choice in (4) is
(5) x and y are both even.
♦
By propositional logic, A → B is equivalent to ¬B → ¬A. So, proving ¬B → ¬A is just as good as proving A → B.
Let's prove the same theorem as above using its contrapositive.
Theorem. For all integers x and y, if xy is even and x+y is even then both x and y are even.
Proof. Select arbitrary integers x and y. Our goal is to show the implication: if at least one of x and y is odd then either xy is odd or x+y is odd.
(Note. The negation of "x is even and y is even" is "either x is odd or y is odd." The negation of "xy is even and x+y is even" is "either xy is odd or x+y is odd.)To prove the implication, add its left-hand side to the fact bank.
(1) x is odd or y is odd.So either both x and y are odd or one of them is even and the other is odd. We break the proof down into cases.
Case 1. (both x and y are odd). Since x and y are odd, their product xy is also odd. So the right-hand side of the implication is true because one part of the or is true.
Case 2. (one of x and y is even and the other is odd). In this case, the sum x + y is the sum of an even number and an odd number, which is always odd. So the right-hand side of the implication is true in this case too.
♦