← Table of contents →

Select a white background

Proving A → B

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.

Example

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 even
(2) x+y is even
The product of two odd integers is odd. So, in order for (1) to be true, it is required that
(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.

♦

Using the contrapositive

By propositional logic, A → B is equivalent to ¬B → ¬A. So, proving ¬B → ¬A is just as good as proving A → B.

Example

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.

♦