We can prove the truth of some assertion by proving the contrapositive of the assertion instead. It might be easier to attack the contrapositive, for example.
Consider this assertion which will call R: P => Q
This says
"if P is true, then Q is true",
or more simply
"P implies Q".
An example with words is
"if this car is mine, then this car is blue".
The contrapositve of R is this assertion: ~Q => ~P
This says
"if Q is not true, then P is not true",
or more directly
"not Q implies not P".
In our word example, the contrapositive is
"if this car is not blue, then it is not mine".
Proof by contrapositive works because of this fact:
If R is true, then contrapos(R) is also true; If contrapos(R) is true, then R is also true.
We say this result this way:
R if and only if contrapos(R)
which is written symbolically as
R <==> contrapos(R)
We sometimes shorten "if and only if" to "iff".
For an example, check this link:
http://zimmer.csufresno.edu/~larryc/proofs/proofs.contrapositive.html
In class, I proved the truth of this assertion R:
if x and y are two integers for which even(x+y), then x and y have the same parity.I did it by proving instead this assertion contrapos(R):
if x and y are two integers with opposite parity, then ~even(x+y).
Finally, since contrapos(R) is true, we conclude R is true.
QED