CS 173: Discrete Mathematical StructuresCS 173 AnnouncementsCS 173 Predicates - free and bound variablesCS 173 Predicates - multiple quantifiersCS 173 Predicates - the meaning of multiple quantifiersSlide 6CS 173 Proofs - how do you know?Slide 8Slide 9CS 173 Proofs - Modus PonensCS 173 Proofs - Modus TollensCS 173 Proofs - AdditionCS 173 Proofs - SimplificationCS 173 Proofs - Disjunctive SyllogismCS 173 Proofs - Hypothetical SyllogismCS 173 Proofs - A little quiz…CS 173 Proofs - A little proof…Slide 18Slide 19CS 173 Proof Techniques - direct proofsSlide 21CS 173 Proofs - FallaciesCS 173 Proofs - valid arg or fallacy?Slide 24CS 173:Discrete Mathematical StructuresCinda [email protected] 2213 Siebel CenterOffice Hours: T 1:30-3:30pCs173 - Spring 2004CS 173 AnnouncementsHomework 1 due 2/1 (2/3) in class. Follow format guidelines from web.Homework 2 available tonight, due 2/15 (2/17)Quiz 2 available, due Sunday 2/6, 11:30p.POD?Cs173 - Spring 2004CS 173 Predicates - free and bound variablesA variable is bound if it is known or quantified. Otherwise, it is free.Examples:P(x) x is freeP(5) x is bound to 5x P(x) x is bound by quantifierReminder: in a proposition, all variables must be bound.Cs173 - Spring 2004CS 173 Predicates - multiple quantifiersTo bind many variables, use many quantifiers.Example: P(x,y) = “x > y”x P(x,y)xy P(x,y)xy P(x,y)x P(x,3)not a propositionfalse propositiontrue propositionfalse propositionThe statement is:a) Not a propositionb) A false propositionc) A true propositionCs173 - Spring 2004CS 173 Predicates - the meaning of multiple quantifiers“xy P(x,y)” means P(x,y) is true for every possible combination of x and y.“xy P(x,y)” means P(x,y) is true for some choice of x and y (together).“xy P(x,y)” means for every x we can find a (possibly different) y so that P(x,y) is true.“xy P(x,y)” means there is a(t least one) particular x for which P(x,y) is always true.Notice: quantifier order is not commutative!Cs173 - Spring 2004CS 173 Predicates - the meaning of multiple quantifiersExample: N(x,y) = “x is sitting next to y”xy N(x,y) - everyone is sitting next to everyone else.xy N(x,y) - there are two people sitting next to each other.xy N(x,y) - every person is sitting next to somebody.xy N(x,y) - a particular person is sitting next to everyone else.FalseTrue?True?FalseCs173 - Spring 2004CS 173 Proofs - how do you know?The following statements are true:I am Mila.If I am Mila, then I am a great swimmer.What do we know?I am a great swimmer!How do we know it?Cs173 - Spring 2004CS 173 Proofs - how do you know?A theorem is a statement that can be shown to be true.A proof is the means of doing so.Axioms, postulates, hypotheses, & previously proven theoremsRules of InferenceProofCs173 - Spring 2004CS 173 Proofs - how do you know?The following statements are true:I am Mila.If I am Mila, then I am a great swimmer.What do we know?I am a great swimmer!How do we know it? What rule of inference can we use to argue?Cs173 - Spring 2004CS 173 Proofs - Modus PonensI am Mila.If I am Mila, then I am a great swimmer. I am a great swimmer!pp  q qTautology:(p  (p  q))  q Inference Rule:Modus PonensCs173 - Spring 2004CS 173 Proofs - Modus TollensI am not a great skater.If I am Erik, then I am a great skater. I am not Erik!qp  q pTautology:(q  (p  q))  p Inference Rule:Modus TollensCs173 - Spring 2004CS 173 Proofs - AdditionI am not a great skater. I am not a great skater or I am tall.p p  qTautology:p  (p  q)Inference Rule:AdditionCs173 - Spring 2004CS 173 Proofs - SimplificationI am not a great skater and you are sleepy. you are sleepy.p  q pTautology:(p  q)  pInference Rule:SimplificationCs173 - Spring 2004CS 173 Proofs - Disjunctive SyllogismI am a great eater or I am a great skater.I am not a great skater. I am a great eater!p  q q pTautology:((p  q)  q)  p Inference Rule:Disjunctive SyllogismCs173 - Spring 2004CS 173 Proofs - Hypothetical SyllogismIf you are an athlete, you are always hungry. If you are always hungry, you have a snickers in your backpack. If you are an athlete, you have a snickers in your backpack.p  q q  r p  rTautology:((p  q)  (q  r))  (p  r) Inference Rule:Hypothetical SyllogismCs173 - Spring 2004CS 173 Proofs - A little quiz…Amy is a computer science major. Amy is a math major or a computer science major.Addition If Ernie is a math major then Ernie is geeky.Ernie is not geeky! Ernie is not a math major.Modus TollensCs173 - Spring 2004CS 173 Proofs - A little proof…Here’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MCs173 - Spring 2004CS 173 Proofs - A little proof…1. 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 Proofs - A little proof…1. M  C Given2. D  C Given3. D  S Given4. M Given 5. C Disjunctive Syllogism (1,4)6. C  D Contrapositive of 27. C  S Hypothetical Syllogism (6,3)8. S Modus Ponens (5,7)Ellen is smart!Cs173 - Spring 2004CS 173 Proof Techniques - direct proofsA totally different example:Prove that if n = 3 mod 4, then n2 = 1 mod 4. HUH?7 = 3 mod 437 = 1 mod 494 = 2 mod 416 = 0 mod 4Cs173 - Spring 2004If n = 3 mod 4, then n = 4k + 3 for some int k.But then, A totally different example:Prove that if n = 3 mod 4, then n2 = 1 mod 4. CS 173 Proof Techniques - direct proofs= (4k + 3)(4k + 3)n2= 16k2 + 24k + 9= 16k2 + 24k + 8 + 1= 4(4k2 + 6k + 2) + 1= 4j + 1 for some int j= 1 mod 4.Cs173 - Spring 2004CS 173 Proofs - FallaciesRules of inference, appropriately applied give valid arguments.Mistakes in applying rules of inference are called fallacies.Cs173 - Spring 2004CS 173 Proofs - valid arg or fallacy? If I am Bonnie Blair, then I skate fast I skate fast! I am Bonnie BlairI’m Eric HeidenIf you don’t give me $10, I bite your ear. I bite your ear! You didn’t give me $10.I’m just mean.Affirming the conclusion.((p  q)  q)  pNot a tautology.Cs173 - Spring 2004CS 173 Proofs - valid arg or fallacy? If it rains then it is cloudy. It does not rain. It is not