Créer une présentation
Télécharger la présentation

Télécharger la présentation
## Methods of Proof

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -

**Methods of Proof**CS 202 Rosen section 1.5 Aaron Bloomfield**In this slide set…**• Rules of inference for propositions • Rules of inference for quantified statements • Ten methods of proof**Proof methods in this slide set**• Logical equivalences • via truth tables • via logical equivalences • Set equivalences • via membership tables • via set identities • via mutual subset proof • via set builder notation and logical equivalences • Rules of inference • for propositions • for quantified statements • Pigeonhole principle • Combinatorial proofs • Ten proof methods in section 1.5: • Direct proofs • Indirect proofs • Vacuous proofs • Trivial proofs • Proof by contradiction • Proof by cases • Proofs of equivalence • Existence proofs • Constructive • Non-constructive • Uniqueness proofs • Counterexamples • Induction • Weak mathematical induction • Strong mathematical induction • Structural induction**Modus Ponens**• Consider (p (p→q)) → q**Modus Ponens example**• Assume you are given the following two statements: • “you are in this class” • “if you are in this class, you will get a grade” • Let p = “you are in this class” • Let q = “you will get a grade” • By Modus Ponens, you can conclude that you will get a grade**Modus Tollens**• Assume that we know: ¬q and p → q • Recall that p → q = ¬q →¬p • Thus, we know ¬q and ¬q →¬p • We can conclude ¬p**Modus Tollens example**• Assume you are given the following two statements: • “you will not get a grade” • “if you are in this class, you will get a grade” • Let p = “you are in this class” • Let q = “you will get a grade” • By Modus Tollens, you can conclude that you are not in this class**Quick survey**• I feel I understand moduls ponens and modus tollens • Very well • With some review, I’ll be good • Not really • Not at all**Addition & Simplification**• Addition: If you know that p is true, then p q will ALWAYS be true • Simplification: If p q is true, then p will ALWAYS be true**Example of proof**• “It is not sunny this afternoon and it is colder than yesterday” • “We will go swimming only if it is sunny” • “If we do not go swimming, then we will take a canoe trip” • “If we take a canoe trip, then we will be home by sunset” • Does this imply that “we will be home by sunset”? • “It is not sunny this afternoon and it is colder than yesterday” • “We will go swimming only if it is sunny” • “If we do not go swimming, then we will take a canoe trip” • “If we take a canoe trip, then we will be home by sunset” • Does this imply that “we will be home by sunset”? • “It is not sunny this afternoon and it is colder than yesterday” • “We will go swimming only if it is sunny” • “If we do not go swimming, then we will take a canoe trip” • “If we take a canoe trip, then we will be home by sunset” • Does this imply that “we will be home by sunset”? • “It is not sunny this afternoon and it is colder than yesterday” • “We will go swimming only if it is sunny” • “If we do not go swimming, then we will take a canoe trip” • “If we take a canoe trip, then we will be home by sunset” • Does this imply that “we will be home by sunset”? • “It is not sunny this afternoon and it is colder than yesterday” • “We will go swimming only if it is sunny” • “If we do not go swimming, then we will take a canoe trip” • “If we take a canoe trip, then we will be home by sunset” • Does this imply that “we will be home by sunset”? • Example 6 of Rosen, section 1.5 • We have the hypotheses: • “It is not sunny this afternoon and it is colder than yesterday” • “We will go swimming only if it is sunny” • “If we do not go swimming, then we will take a canoe trip” • “If we take a canoe trip, then we will be home by sunset” • Does this imply that “we will be home by sunset”? ¬p q r → p ¬r → s s → t t p q r s t**Example of proof**• ¬p q 1st hypothesis • ¬p Simplification using step 1 • r → p 2nd hypothesis • ¬r Modus tollens using steps 2 & 3 • ¬r → s 3rd hypothesis • s Modus ponens using steps 4 & 5 • s → t 4th hypothesis • t Modus ponens using steps 6 & 7**So what did we show?**• We showed that: • [(¬p q) (r → p) (¬r → s) (s → t)] → t • That when the 4 hypotheses are true, then the implication is true • In other words, we showed the above is a tautology! • To show this, enter the following into the truth table generator at http://sciris.shu.edu/~borowski/Truth/: ((~P ^ Q) ^ (R => P) ^ (~R => S) ^ (S => T)) => T**More rules of inference**• Conjunction: if p and q are true separately, then pq is true • Disjunctive syllogism: If pq is true, and p is false, then q must be true • Resolution: If pq is true, and ¬pr is true, then qr must be true • Hypothetical syllogism: If p→q is true, and q→r is true, then p→r must be true**Example of proof**• Rosen, section 1.5, question 4 • Given the hypotheses: • “If it does not rain or if it is not foggy, then the sailing race will be held and the lifesaving demonstration will go on” • “If the sailing race is held, then the trophy will be awarded” • “The trophy was not awarded” • Can you conclude: “It rained”? (¬r ¬f) → (s l) s → t ¬t r**Example of proof**• ¬t 3rd hypothesis • s → t 2nd hypothesis • ¬s Modus tollens using steps 2 & 3 • (¬r¬f)→(sl) 1st hypothesis • ¬(sl)→¬(¬r¬f) Contrapositive of step 4 • (¬s¬l)→(rf) DeMorgan’s law and double negation law • ¬s¬l Addition from step 3 • rf Modus ponens using steps 6 & 7 • r Simplification using step 8**Quick survey**• I feel I understand that proof… • Very well • With some review, I’ll be good • Not really • Not at all**Fallacy of affirming the conclusion**Modus Badus • Consider the following: • Is this true? Not a valid rule!**Modus Badus example**• Assume you are given the following two statements: • “you will get a grade” • “if you are in this class, you will get a grade” • Let p = “you are in this class” • Let q = “you will get a grade” • You CANNOT conclude that you are in this class • You could be getting a grade for another class**Fallacy of denying thehypothesis**Modus Badus • Consider the following: • Is this true? Not a valid rule!**Modus Badus example**• Assume you are given the following two statements: • “you are not in this class” • “if you are in this class, you will get a grade” • Let p = “you are in this class” • Let q = “you will get a grade” • You CANNOT conclude that you will not get a grade • You could be getting a grade for another class**Quick survey**• I feel I understand rules of inference for Boolean propositions… • Very well • With some review, I’ll be good • Not really • Not at all**Bittersweets: Dejected sayings**• I MISS MY EX • PEAKED AT 17 • MAIL ORDER • TABLE FOR 1 • I CRY ON Q • U C MY BLOG? • REJECT PILE • PILLOW HUGGIN • ASYLUM BOUND • DIGNITY FREE • PROG FAN • STATIC CLING • WE HAD PLANS • XANADU 2NITE • SETTLE 4LESS • NOT AGAIN**Bittersweets: Dysfunctional sayings**• RUMORS TRUE • PRENUP OKAY? • HE CAN LISTEN • GAME ON TV • CALL A 900# • P.S. I LUV ME • DO MY DISHES • UWATCH CMT • PAROLE IS UP! • BE MY YOKO • U+ME=GRIEF • I WANT HALF • RETURN 2 PIT • NOT MY MOMMY • BE MY PRISON • C THAT DOOR?**What we have shown**• Rules of inference for propositions • Next up: rules of inference for quantified statements**Rules of inference for the universal quantifier**• Assume that we know that x P(x) is true • Then we can conclude that P(c) is true • Here c stands for some specific constant • This is called “universal instantiation” • Assume that we know that P(c) is true for any value of c • Then we can conclude that x P(x) is true • This is called “universal generalization”**Rules of inference for the existential quantifier**• Assume that we know that x P(x) is true • Then we can conclude that P(c) is true for some value of c • This is called “existential instantiation” • Assume that we know that P(c) is true for some value of c • Then we can conclude that x P(x) is true • This is called “existential generalization”**Example of proof**• Rosen, section 1.5, question 10a • Given the hypotheses: • “Linda, a student in this class, owns a red convertible.” • “Everybody who owns a red convertible has gotten at least one speeding ticket” • Can you conclude: “Somebody in this class has gotten a speeding ticket”? C(Linda) R(Linda) x (R(x)→T(x)) x (C(x)T(x))**Example of proof**• x (R(x)→T(x)) 3rd hypothesis • R(Linda) → T(Linda) Universal instantiation using step 1 • R(Linda) 2nd hypothesis • T(Linda) Modes ponens using steps 2 & 3 • C(Linda) 1st hypothesis • C(Linda) T(Linda) Conjunction using steps 4 & 5 • x (C(x)T(x)) Existential generalization using step 6 Thus, we have shown that “Somebody in this class has gotten a speeding ticket”**Example of proof**• Rosen, section 1.5, question 10d • Given the hypotheses: • “There is someone in this class who has been to France” • “Everyone who goes to France visits the Louvre” • Can you conclude: “Someone in this class has visited the Louvre”? x (C(x)F(x)) x (F(x)→L(x)) x (C(x)L(x))**Example of proof**• x (C(x)F(x)) 1st hypothesis • C(y) F(y) Existential instantiation using step 1 • F(y) Simplification using step 2 • C(y) Simplification using step 2 • x (F(x)→L(x)) 2nd hypothesis • F(y) → L(y) Universal instantiation using step 5 • L(y) Modus ponens using steps 3 & 6 • C(y) L(y) Conjunction using steps 4 & 7 • x (C(x)L(x)) Existential generalization using step 8 Thus, we have shown that “Someone in this class has visited the Louvre”**How do you know which one to use?**• Experience! • In general, use quantifiers with statements like “for all” or “there exists” • Although the vacuous proof example on slide 40 is a contradiction**Quick survey**• I feel I understand rules of inference for quantified statements… • Very well • With some review, I’ll be good • Not really • Not at all**Proof methods**• We will discuss ten proof methods: • Direct proofs • Indirect proofs • Vacuous proofs • Trivial proofs • Proof by contradiction • Proof by cases • Proofs of equivalence • Existence proofs • Uniqueness proofs • Counterexamples**Direct proofs**• Consider an implication: p→q • If p is false, then the implication is always true • Thus, show that if p is true, then q is true • To perform a direct proof, assume that p is true, and show that q must therefore be true**Direct proof example**• Rosen, section 1.5, question 20 • Show that the square of an even number is an even number • Rephrased: if n is even, then n2 is even • Assume n is even • Thus, n = 2k, for some k (definition of even numbers) • n2 = (2k)2 = 4k2 = 2(2k2) • As n2 is 2 times an integer, n2 is thus even**Quick survey**• These quick surveys are really getting on my nerves… • They’re great - keep ‘em coming! • They’re fine • A bit tedious • Enough already! Stop!**Indirect proofs**• Consider an implication: p→q • It’s contrapositive is ¬q→¬p • Is logically equivalent to the original implication! • If the antecedent (¬q) is false, then the contrapositive is always true • Thus, show that if ¬q is true, then ¬p is true • To perform an indirect proof, do a direct proof on the contrapositive**Indirect proof example**• If n2 is an odd integer then n is an odd integer • Prove the contrapositive: If n is an even integer, then n2 is an even integer • Proof: n=2k for some integer k (definition of even numbers) • n2 = (2k)2 = 4k2 = 2(2k2) • Since n2 is 2 times an integer, it is even**Which to use**• When do you use a direct proof versus an indirect proof? • If it’s not clear from the problem, try direct first, then indirect second • If indirect fails, try the other proofs**Example of which to use**• Rosen, section 1.5, question 21 • Prove that if n is an integer and n3+5 is odd, then n is even • Via direct proof • n3+5 = 2k+1 for some integer k (definition of odd numbers) • n3 = 2k+6 • Umm… • So direct proof didn’t work out. Next up: indirect proof**Example of which to use**• Rosen, section 1.5, question 21 (a) • Prove that if n is an integer and n3+5 is odd, then n is even • Via indirect proof • Contrapositive: If n is odd, then n3+5 is even • Assume n is odd, and show that n3+5 is even • n=2k+1 for some integer k (definition of odd numbers) • n3+5 = (2k+1)3+5 = 8k3+12k2+6k+6 = 2(4k3+6k2+3k+3) • As 2(4k3+6k2+3k+3) is 2 times an integer, it is even**Quick survey**• I feel I understand direct proofs and indirect proofs… • Very well • With some review, I’ll be good • Not really • Not at all**Proof by contradiction**• Given a statement p, assume it is false • Assume ¬p • Prove that ¬p cannot occur • A contradiction exists • Given a statement of the form p→q • To assume it’s false, you only have to consider the case where p is true and q is false**Proof by contradiction example 1**• Theorem (by Euclid): There are infinitely many prime numbers. • Proof. Assume there are a finite number of primes • List them as follows: p1, p2 …, pn. • Consider the number q = p1p2 … pn + 1 • This number is not divisible by any of the listed primes • If we divided pi into q, there would result a remainder of 1 • We must conclude that q is a prime number, not among the primes listed above • This contradicts our assumption that all primes are in the list p1, p2 …, pn.**Proof by contradiction example 2**• Rosen, section 1.5, question 21 (b) • Prove that if n is an integer and n3+5 is odd, then n is even • Rephrased: If n3+5 is odd, then n is even • Assume p is true and q is false • Assume that n3+5 is odd, and n is odd • n=2k+1 for some integer k (definition of odd numbers) • n3+5 = (2k+1)3+5 = 8k3+12k2+6k+6 = 2(4k3+6k2+3k+3) • As 2(4k3+6k2+3k+3) is 2 times an integer, it must be even • Contradiction!**A note on that problem…**• Rosen, section 1.5, question 21 • Prove that if n is an integer and n3+5 is odd, then n is even • Here, our implication is: If n3+5 is odd, then n is even • The indirect proof proved the contrapositive: ¬q → ¬p • I.e., If n is odd, then n3+5 is even • The proof by contradiction assumed that the implication was false, and showed a contradiction • If we assume p and ¬q, we can show that implies q • The contradiction is q and ¬q • Note that both used similar steps, but are different means of proving the implication**How the book explains proof by contradiction**• A very poor explanation, IMHO • Suppose q is a contradiction (i.e. is always false) • Show that ¬p→q is true • Since the consequence is false, the antecedent must be false • Thus, p must be true • Find a contradiction, such as (r¬r), to represent q • Thus, you are showing that ¬p→(r¬r) • Or that assuming p is false leads to a contradiction**A note on proofs by contradiction**• You can DISPROVE something by using a proof by contradiction • You are finding an example to show that something is not true • You cannot PROVE something by example • Example: prove or disprove that all numbers are even • Proof by contradiction: 1 is not even • (Invalid) proof by example: 2 is even**Quick survey**• I feel I understand proof by contradiction… • Very well • With some review, I’ll be good • Not really • Not at all