## Proof by Contrapositive

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.

### What is the contrapositive?

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".

### How does a proof work?

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".
### Example

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**