Study the Proofs slides and read Rosen chapters 1.6 and 1.7.
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.
Theorem: if m and n are perfect squares (i.e., m = s2 and n=t2, where s and t are integers) then mn is a perfect square.
Proof. The premise is that m=s2 and n = 2t. Therefore mn = s2t2 = (st)2, and therefore mn is a perfect square.
(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.
Show that "if n is an integer and n2+1 is odd, then n is even", using contraposition.
Proof using contraposition. We must show that if n is odd (n is not even), n2+1 is
even. That is easy: if n is odd, n2 is odd,
and therefore n2+1 is
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 n2+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 n2 > 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.
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 2b2 = a2. Therefore a2 is even, and therefore a is even. ( If you do not believe that, you need to prove the lemma: if a2 is even, then a is even).
So a is even or a = 2c. But then 2b2 = a2 = 4c2 , and thus b2 = 2c2 . So b2 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.
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.
Show that "if n is an integer and n2+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 n2+1 is odd. But if n is odd, then n2 is odd,
and therefore n2+1 is
even. Thus, a contradiction with our assumption.
Show that "if n is an integer and n3+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, n2 ≥ n.
Proof by cases: n is either less than zero or equal to 0 or greater than zero.
Case 1: n<0 then n2 ≥ n because n<0 and n2 > 0
Case 2: n=0 then n2 = 0 and hence n2 = n, so n2 ≥ n
Case 3: n>0 then because n is an integer n ≥ 1, and hence n2 ≥ n
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.
Prove the equivalence ¬(p → q) ↔ (p ∧ ¬ q).
Direct proof. We need to prove both [¬(p → q) → (p ∧ ¬ q)]
|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|
|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|
Show that these statements about the integer x are equivalent: (1) 3x+2 is even, (2) x+5 is odd, (3) x2 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.
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|
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:
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.)