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