Study the Proofs slides and read Rosen chapters 1.6 and 1.7.

**Theorem:**- Statement that can be proved to be
*true* -
**Proof:** - valid argument establishing the truth of a theorem
**Axioms:**- statements we assume to be true without proof
**Lemma:**- helper theorem used in the proof of a larger theorem
**Corollary:**- theorem that can be established directly from a theorem that has been proved
**Conjecture:**- statement that is
*proposed*to be true

In this tutorial, we will go over four proof techniques along with examples and strategies for doing proofs.

So far we have used one proof technique: the direct proof, where we have premises and use inference rules and equivalences to prove a conclusion.

*Example 1*

Theorem: if m and n are perfect squares (i.e., m = s^{2}
and n=t^{2}, where s and t are integers) then mn is a perfect square.

Proof. The premise is that m=s^{2} and n = ^{2}t. Therefore mn =
s^{2}t^{2} = (st)^{2}, and therefore mn is a perfect square.

QED.

(QED or Q.E.D.: a Latin term "quod erat demonstrandum" or "what was to be proved", sometimes used to indicate the end of a proof.)

Use a direct proof to show that the sum of two odd integers is even.

(Note: This is exercise 1 in Section 1.6 in the Rosen text.)

show this equivalence, p → q ≡ ¬q → ¬p, by truth table.

*Example 2:*

Show that "if n is an integer and n^{2}+1 is odd,
then n is even", using contraposition.

Proof using contraposition. We must show that if n is odd (n is not even), n^{2}+1 is
even. That is easy: if n is odd, n^{2} is odd,
and therefore n^{2}+1 is
even.

QED

Note: because we had two premises in the example connected with "and", we only have to show that the negation of one of them is true -- it was not necessarily to negate "n is an integer".

A direct proof of example 2 would be more complicated because it
is hard to derive a property of n from the fact that n^{2}+1 is odd (or
is it?).

Finish the proof started in the Quick Test above... Prove by contraposition the conjecture:

If the average of four different integers is 10, then one of the integers is greater than 11.

Use a proof by contraposition to show that if x + y ≥ 2, where x and y are real numbers, then x ≥ 1 or y ≥ 1.

(Note: This is exercise 15 in Section 1.6 in the Rosen text.)

The process of finding a proof is somewhat like trial and error. First we may attempt a direct proof of p→q, but we may not get there. So then we try it "from the other end": ¬q and we may get to the finish line: ¬p.

Why would we not start from q?

Notice that we had
to prove an implication. Remember false → true, but also false →
false.
So how do we prove: "if bananas are straight, then apples are cubes"?
By simply pointing out that bananas are not straight. This is called a
** vacuous ** proof: we can draw ** any
conclusion ** from a false antecedent. To
show that if 0=1 then pigs fly, we simply point out that 0 ≠ 1. Vacuous
proofs occur often as part of a larger proof. For example, we want to
prove P(n) = "if n is an integer and n>1 then n^{2} > n".

To show P(0), we simply point out that 0 is not larger than 1.

*Example 3:* Suppose I have blue socks, white socks and red socks. Then at
least two out of four of my socks have the same color.

Proof by contradiction. Suppose that not at least two socks are the same color. That means that all four socks are a different color. But I only have three different color socks, so I arrive at a contradiction. That must mean that my assumption: not at least two socks are the same color was false, and hence the opposite is true: at least two out of four of my socks are the same color.

QED

Proof by contradiction works as follows: to prove p, we assume ¬p and derive a contradiction, meaning we deduce something to be true that we know from the premises is false (or vice versa with the true and false). Here is a very famous proof that √2 is irrational, i.e. there are no integers p and q such that √2 = p/q.

Proof by contradiction.

Assume that there are
integers p and q such that √2 = p/q. We can take all common factors out of p
and q arriving at √2 = a/b, where a and b have no common
factors. Now we are going to show a contradiction, namely that a and b have common
factors. If √2 = a/b then 2b^{2} = a^{2}.
Therefore a^{2} is even, and therefore a is even. (
If you do not believe that, you need to prove the lemma: if a^{2}
is even, then a is even).

So a is even or a = 2c. But then 2b^{2} = a^{2} = 4c^{2} ,
and thus b^{2} = 2c^{2} . So b^{2} is even,
so b is even. But if both a and
b are even then they have a common factor 2, which is the
contradiction we were hunting for. Because we have arrived at a
contradiction, our assumption "there are integers p and q such that √2 = p/q"
was false, hence there are no integers p and q such that √2 = p/q.

QED

A proof by contraposition can be converted into a proof by contradiction by adding the assumption that the premise is true and then showing that there is a contradiction.

*Example 4:*

Show that "if n is an integer and n^{2}+1 is odd,
then n is even" is true, using proof by contradiction.

Proof using contradiction. We assume that n is odd (the conclusion) and
that n^{2}+1 is odd. But if n is odd, then n^{2} is odd,
and therefore n^{2}+1 is
even. Thus, a contradiction with our assumption.

QED

Show that "if n is an integer and n^{3}+5 is odd, then n is even" using a proof by contradiction.

(Note: This is exercise 17b in Section 1.6 in the Rosen text.)

*Example 5:* Prove that every for integer n, n^{2} ≥ n.

Proof by cases: n is either less than zero or equal to 0 or greater than zero.

Case 1: n<0 then n^{2} ≥ n because n<0 and
n^{2} > 0

Case 2: n=0 then n^{2} = 0 and hence n^{2} = n, so n^{2} ≥ n

Case 3: n>0 then because n is an integer n ≥ 1, and hence n^{2} ≥ n

Q.E.D.

Complete the proof by cases started in the Quick Test above.

(Note: This is exercise 5 in Section 1.7 in the Rosen text.)

**Proofs of Equivalence**

So far, we have used truth tables to prove equivalence. Instead, we could convert equivalence (or the biconditional) into the two conditionals and use the proof techniques we have covered to prove that both are true. This is based on the tautology: (p ↔ q) ↔ [(p → q) ∧ (q → p)]. So this is a particular type of proof by cases.

*Example 6:*

Prove the equivalence ¬(p → q) ↔ (p ∧ ¬ q).

Direct proof. We need to prove *both* [¬(p → q) →
(p ∧ ¬ q)]

Step | Statement | Reason |
---|---|---|

1. | ¬(p → q) → (p ∧ ¬ q) | Given |

2. | ¬(¬p ∨ q) → (p ∧ ¬ q) | Equivalence of 1 |

3. | (p ∧ ¬ q) → (p ∧ ¬ q) | DeMorgan's Law of 2 |

4. | ¬ (p ∧ ¬ q) ∨ (p ∧ ¬ q) | Equivalence of 3 |

5. | T | Negation Law of 4 |

Step | Statement | Reason |
---|---|---|

1. | (p ∧ ¬ q) → ¬(p → q) | Given |

2. | (p ∧ ¬ q) → ¬(¬p ∨ q) | Equivalence of 1 |

3. | (p ∧ ¬ q) → (p ∧ ¬q) | DeMorgan's Law of 2 |

4. | ¬(p ∧ ¬ q) ∨ (p ∧ ¬q) | Equivalence of 3 |

5. | T | Negation Law of 4 |

QED

Show that these statements about the integer x are equivalent: (1) 3x+2 is even, (2) x+5 is odd, (3) x^{2}is even.

(Note: This is exercise 31 in Section 1.6 in the Rosen text.)

**Exhaustive proofs** proceed by proving all possible cases, when there are a small number of cases.

*Example 7:*

A version of the famous game theory problem Prisoner's Dilemma can be explained as follows.

Two people have been arrested for a crime. They are put in separate cells, and each is offered a chance to betray the other for a reduced sentence. Naturally the prisoners are not allowed to talk to each other. The offers can be summarized in this table:

Prisoner B Stays Silent | Prisoner B Betrays | |
---|---|---|

Prisoner A Stays Silent | Each serves 6 months | Prisoner A: 10 years Prisoner B: goes free |

Prisoner A Betrays | Prisoner A: goes free Prisoner B: 10 years | Each serves 5 years |

- Prisoner A Stays Silent: in the worst case, Prisoner B betrays and A gets 10 years.
- Prisoner A Betrays: in the worst case, Prisoner B also betrays and each serves 5 years.
- Prisoner B cases are symmetric with above two.

**Proofs by Counterexample:**

The idea of counter examples was discussed in the second tutorial. We can turn it into a proof technique -- assume we want to prove some statement false, we can do so by finding an example that violates the statement.

The example in the second tutorial can be made into a proof be re-stating it as follows:

Prove that ∀x ∈ R x≥ 0 is false.

This statement can be proven by finding an example of a Real number that is negative, which is pretty easy.

**Existence Proofs** are like proofs by counterexample. The idea is to prove statements that "there exists some value such that" by finding a value that has the property. So for example, we can prove that prime numbers exist by giving an example of one.

Finding a proof can be difficult. Some famous conjectures (such as Fermat's last theorem -- see Section 1.7 in Rosen for more on this one) have been taken without proof for a considerable length of time. We can suggest some rules of thumb (called *heuristics* in the artificial intelligence community) for selecting proof techniques are:

- If the statement is a conditional, you should first try a direct proof.
- If that doesn't work, you can try either a proof by contraposition or proof by contradiction. Which of these you pick depends on whether it is easier to posit the negation of the premises or the conclusion of the conditional.
- If the statement is a disjuntion (explicitly or implicitly) of propositions/predicates (i.e., p = p1 ∨ p2 ∨ ... ∨ pn), then try a proof by cases.
- If you need to prove a statement false, you might look for a counterexample.
- If you are proving the existence of some property, you can form an existence proof.

Prove the three statements listed in the quick test above.

(Note: The first is exercise 1 and the third is exercise 11 in Section 1.7 in the Rosen text.)