CS 173: Discrete Mathematical StructuresCS 173 AnnouncementsCS 173 Proof Techniques - direct proofsSlide 4Slide 5CS 173 Proof Techniques - vacuous proofsCS 173 Proof Techniques - trivial proofsCS 173 Proof Techniques - indirect proofsCS 173 Proof Techniques - proof by contradictionSlide 10Slide 11Slide 12Slide 13CS 173 Proof Techniques - proof by casesSlide 15CS 173 Proofs - something for everyone…Slide 17CS 173:Discrete Mathematical StructuresCinda [email protected] 2213 Siebel CenterOffice Hours: T 1:30-3:30pCs173 - Spring 2004CS 173 AnnouncementsHomework 1 still accepted today.Homework 2 available? Due 2/15 (2/17) in class.Quiz #2 available now! Go to compass.uiuc.edu enter cs173, assessments. Due 2/6, 11:30p.WCS general meeting tonight: Morgan Stanley, food. Siebel Center room 2405.Cs173 - Spring 2004CS 173 Proof Techniques - direct proofsHere’s what you know:Ellen is a math major or a CS major.If Ellen does not like discrete math, she is not a CS major.If Ellen likes discrete math, she is smart.Ellen is not a math major.Can you conclude Ellen is smart?M  CD  CD  SM((M  C)  (D  C)  (D  S)  (M))  S?Cs173 - Spring 2004CS 173 Proof Techniques - direct proofsIn general, to prove p  q, assume p and show that q follows. ((M  C)  (D  C)  (D  S)  (M))  S?Cs173 - Spring 2004CS 173 Proof Techniques - direct proofs1. M  C Given2. D  C Given3. D  S Given4. M Given 5. C DS (1,4)6. D MT (2,5)7. S MP (3,6)Ellen is smart!Cs173 - Spring 2004CS 173 Proof Techniques - vacuous proofsIn general, to prove p  q, assume p and show that q follows. But p  q is also TRUE if p is FALSE.Suggests proving p  q by proving p.Ex. p: it’s 75 degrees outsideq: we’ll have a swim partySince p is FALSE, p  q is TRUE (but we don’t know a thing about q)Cs173 - Spring 2004CS 173 Proof Techniques - trivial proofsIn general, to prove p  q, assume p and show that q follows. But p  q is also TRUE if q is TRUE.Suggests proving p  q by proving q.Ex. p: it’s 75 degrees outsideq: I’m drinking coffeeSince q is TRUE, p  q is TRUE (the truth or falsity of p is irrelevant)Cs173 - Spring 2004CS 173 Proof Techniques - indirect proofsRecall that p  q  q  p (the contrapositive)So, we can prove the implication p  q by first assuming q, and showing that p follows.Example: Prove that if a and b are integers, and a + b ≥ 15, then a ≥ 8 or b ≥ 8.(a + b ≥ 15)  (a ≥ 8) v (b ≥ 8) (Assume q) Suppose (a < 8)  (b < 8).(Show p) Then (a ≤ 7)  (b ≤ 7),and (a + b) ≤ 14,and (a + b) < 15.What logical equivalence was applied?a) Identityb) Distributivityc) Idempotentd) DeMorgan’sCs173 - Spring 2004CS 173 Proof Techniques - proof by contradictionTo prove a proposition p, assume not p and show a contradiction.Suppose the proposition is of the form p  q, and recall that p  q  q v p  (q  p). So assuming the opposite is to assume q  p.Cs173 - Spring 2004CS 173 Proof Techniques - proof by contradictionExample:Rainy days make gardens grow.Gardens don’t grow if it is not hot.When it is cold outside, it rains.Prove that it’s hot.Given: R  GH  GH  RShow: HCs173 - Spring 2004CS 173 Proof Techniques - proof by contradictionGiven: R  GH  GH  RShow: H1. R  G Given2. H  G Given3. H  R Given4. H assume to the contrary5. R MP (3,4)6. G MP (1,5)7. G MP (2,4)8. G  G contradictionHCs173 - Spring 2004CS 173 Proof Techniques - proof by contradictionClassic proof that 2 is irrational.Suppose 2 is rational. Then 2 = a/b for some integers a and b (relatively prime). 2 = a/b implies2 = a2/b2 2b2 = a2a2 is even, and so a is even (a = 2k for some k)b2 = 2k22b2 = (2k)2 = 4k2b2 is even, and so b is even (b = 2k for some k)But if a and b are both even, then they are not relatively prime!Cs173 - Spring 2004CS 173 Proof Techniques - proof by contradictionYou’re going to let me get away with that? a2 is even, and so a is even (a = 2k for some k)??So a really is even.contradictionSuppose to the contrary that a is not even.Then a = 2k + 1 for some integer kThen a2 = (2k + 1)(2k + 1) = 4k2 + 4k + 1and a2 is odd.Cs173 - Spring 2004CS 173 Proof Techniques - proof by casesSuppose we want to prove a theorem of the form: p1 v p2 v … v pn  qWe can prove it in pieces corresponding to the cases, but which must be true? A: (p1  q) v (p2  q) v … v (pn  q) B: (p1  q)  (p2  q)  …  (pn  q)Cs173 - Spring 2004CS 173 Proof Techniques - proof by casesProof for n=2: (p1  q)  (p2  q)  …  (pn  q) (p1 v p2)  q  (p1 v p2) v q Defn of   (p1  p2) v q DeMorgan’s  (p1 v q)  (p2 v q) Distributivity  (p1  q)  (p2  q) Defn of Cs173 - Spring 2004CS 173 Proofs - something for everyone…“if x is a perfect square, and x is even, then x is divisible by 4.”Formally: (p  q)  r Contrapositive: r  (p  q) Suppose x is not divisible by 4. Then x = 4k + 1, or x = 4k + 2, or x = 4k + 3. r  (p v q)Now structure looks like (u1 v u2 v u3)  (p v q)Case 1 (&3): x = 4k + 1, odd, corresponds to qCase 2: x = 4k + 2, even, so must not be a perfect square.Cs173 - Spring 2004CS 173 Proofs - something for everyone…“if x is a perfect square, and x is even, then x is divisible by 4.”contradictionSubgoal, prove Case 2:Case 2: x = 4k + 2, even (so we have to show not square).Suppose to the contrary that x is a perfect square.Then x = j2 for some integer j.But x = 4k + 2 = 2(2k + 1)Then j = 2 (2k+1)Finally, since (2k+1) is odd, j is not an integer.So, x is not a perfect