CS122 Tutorial 4 (Proof Techniques)

cs122

Tutorial 4: Proof Techniques

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

Terminology

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

Quick Test

Given the statement to prove: "All primes are odd."

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

Direct Proof

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² and n=t², where s and t are integers) then mn is a perfect square.

Proof. The premise is that m=s² and n = ²t. Therefore mn = s²t² = (st)², 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.)

Self Check:

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

Proof by Contraposition

The next category of proof technique is that of indirect proofs. The idea here is to 'sneak up' on what you want to prove by casting the conjecture in a different way or showing that you cannot prove the opposite. The first indirect technique is "proof by contraposition": to prove p → q we assume ¬q and show that ¬p holds. This is based on the following equivalence: p → q ≡ ¬q → ¬p.

Self Check:

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

Example 2:
Show that "if n is an integer and n²+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²+1 is even. That is easy: if n is odd, n² is odd, and therefore n²+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²+1 is odd (or is it?).

Quick Test

Suppose we want to prove "If the average of four different integers is 10, then one of the integers is greater than 11." using proof by contraposition.

Self Check:

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.

Self Check:

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

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

Quick Test

Proof by Contradiction

Remember, proof by contraposition can be used to prove an implication. Another proof technique: proof by contradiction also uses a negation but can be used in cases other than implications.

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² = a². Therefore a² is even, and therefore a is even. ( If you do not believe that, you need to prove the lemma: if a² is even, then a is even).

So a is even or a = 2c. But then 2b² = a² = 4c² , and thus b² = 2c² . So b² 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²+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²+1 is odd. But if n is odd, then n² is odd, and therefore n²+1 is even. Thus, a contradiction with our assumption.
QED

Quick Test

Self Check:

Show that "if n is an integer and n³+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.)

Proof by Cases

To prove p → q we can sometimes break p into a number of cases: p ≡ p1 ∨ p2 ∨ … ∨ pn. Proving p → q is equivalent with proving p1 ∨ p2 ∨ … ∨ pn → q, which is equivalent with proving ( p1 → q ) ∧ ( p2 → q ) ∧ … ( pn → q )

Example 5: Prove that every for integer n, n² ≥ n.

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

Case 1: n<0 then n² ≥ n because n<0 and n² > 0

Case 2: n=0 then n² = 0 and hence n² = n, so n² ≥ n

Case 3: n>0 then because n is an integer n ≥ 1, and hence n² ≥ n

Q.E.D.

Quick Test

Answer the following questions about using proof by cases to prove the triangle inequality: if x and y are real numbers then |x| + |y| ≥ |x + y| (where |x| represents the absolute value of x).

Self Check:

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

and [(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

QED

Self Check:

Show that these statements about the integer x are equivalent: (1) 3x+2 is even, (2) x+5 is odd, (3) x² 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

By examining all possible cases, we can prove that a selfish criminal is best off in the worst case when he/she chooses "betray".

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.

Since 5 years is less than 10 years, the best self-interested strategy for both prisoners is to betray.

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.

Quick Test

For each of the following statements, determine whether it is true or whether a counterexample exists.

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.

Proof Strategies and Mistakes

Read the last part of Section 1.6 in Rosen to learn about mistakes in proofs. Certain mistakes happen occur because one of the steps does not (always) follow from those that precede it. For instance, when a division occurs the proof may quietly assume that the divider is not zero, but this assumption is incorrect.

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.

Once you have decided on a proof technique, it can still be difficult to know how to proceed. One strategy is to look for a proof of a similar statement and then adapt that proof. For example, you will see in the book several proofs involving odd and even numbers where these numbers are re-written as 2k for even or 2n+1 for odd. This is a well known approach for relating these numbers.

Quick Test

What kind of proof technique should you select to prove the following statements?

Self Check:

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