CS 173: Discrete Mathematical StructuresCS 173 AnnouncementsCS 173 Predicate Logic - Everybody loves somebodySlide 4Slide 5CS 173 Predicates - The efficiency of predicates.Slide 7CS 173 PredicatesSlide 9CS 173 Predicates - Some (boring) examples.CS 173 Predicates - The universal quantifierSlide 12Slide 13CS 173 Predicates - The existential quantifierSlide 15Slide 16CS 173 Predicates - not so boring examplesSlide 18CS 173 Predicates - quantifier negationSlide 20Slide 21Slide 22CS 173 Predicates - free and bound variablesCS 173 Predicates - multiple quantifiersCS 173 Predicates - the meaning of multiple quantifiersSlide 26CS 173:Discrete Mathematical StructuresCinda [email protected] 2213 Siebel CenterOffice Hours: T 1:30p-3:30pCs173 - Spring 2004CS 173 AnnouncementsHomework 1 available, due 2/1 (2/3) in class. Follow format guidelines from web.POD submissions: www-courses.cs.uiuc.edu/pod/login.phpreport problems to: [email protected] (ta)Raise your hand if you bought a new book without a coupon.Cs173 - Spring 2004CS 173 Predicate Logic - Everybody loves somebodyProposition, YES or NO?Isaak loves ice cream.X loves ice cream.Everyone loves ice cream.Someone loves ice cream.YESNOYESYESCs173 - Spring 2004CS 173 Predicate Logic - Everybody loves somebodyProposition, YES or NO?3 + 2 = 5X + 2 = 5X + 2 = 5 for any choice of X in {1, 2, 3}X + 2 = 5 for some X in {1, 2, 3}YESNOYESYESCs173 - Spring 2004CS 173 Predicate Logic - Everybody loves somebodyProposition, YES or NO?12 > 4X > 4X > 4 for any choice of X in {3, 4, 5}X > 4 for some X in {1, 2, 3}YESNOYESYESCs173 - Spring 2004CS 173 Predicates - The efficiency of predicates.Eileen eats pizza at least once a week.Suhil eats pizza at least once a week.Greg eats pizza at least once a week.Adam eats pizza at least once a week.Lee eats pizza at least once a week.Ed eats pizza at least once a week.Jake eats pizza at least once a week.…Cs173 - Spring 2004CS 173 Predicates - The efficiency of predicates.Eileen eats pizza at least once a week.Define:EP(x) = “x eats pizza at least once a week.”Universe of Discourse - x is a student in cs173A predicate, or propositional function, is a function that takes some variable(s) as arguments and returns True or False.Note that EP(x) is not a proposition, EP(Lee) is.…Cs173 - Spring 2004CS 173 PredicatesSuppose Q(x,y) = “x > y”Proposition, YES or NO?Q(x,y)Q(3,4)Q(x,9)NOYESNOCs173 - Spring 2004CS 173 PredicatesSuppose Q(x,y) = “x > y”Predicate, YES or NO?Q(x,y)Q(3,4)Q(x,9)YESNOYESCs173 - Spring 2004CS 173 Predicates - Some (boring) examples.P(x) = “x > 3”P(1) = F P(3) = F P(3.02) = TQ(x,y) = “x - y = y - x”Q(x,y) = T if x = yF if x  yCs173 - Spring 2004CS 173 Predicates - The universal quantifierAnother way of changing a predicate into a proposition.Suppose P(x) is a predicate on some universe of discourse.The universal quantifier of P(x) is the proposition:“P(x) is true for all x in the universe of discourse.”We write it x P(x), and say “for all x, P(x)”x P(x) is TRUE if P(x) is true for every single x.x P(x) is FALSE if there is an x for which P(x) is false.Cs173 - Spring 2004CS 173 Predicates - The universal quantifierExamples:x x will get an A in this class. (x getA(x))x if x works hard, x will get an A in this class. (x WkHard(x)  getA(x))x x is awake.FalseTrue???Cs173 - Spring 2004CS 173 Predicates - The universal quantifierIn the special case that the universe of discourse, U, is finite, (U = {x1, x2, x3, …, xn})x P(x)corresponds to the proposition:P(x1)  P(x2)  …  P(xn)We can write a program to loop through the elements in the universe and check each for truthfulness. If all are true, then the proposition is true. Otherwise it is false!Cs173 - Spring 2004CS 173 Predicates - The existential quantifierYet another way of changing a predicate into a proposition.Suppose P(x) is a predicate on some universe of discourse.The existential quantifier of P(x) is the proposition:“P(x) is true if it is true for at least one x in the universe of discourse.”We write it x P(x), and say “for some x, P(x)”x P(x) is FALSE if P(x) is false for every single x.x P(x) is TRUE if there is an x for which P(x) is true.Cs173 - Spring 2004CS 173 Predicates - The existential quantifierExamples:x x will get an A in this class. (x getA(x))x if x works hard, x will get an A in this class. (x WkHard(x)  getA(x))x x is awake.TrueTrueTrueCs173 - Spring 2004CS 173 Predicates - The existential quantifierIn the special case that the universe of discourse, U, is finite, (U = {x1, x2, x3, …, xn})x P(x)corresponds to the proposition:P(x1)  P(x2)  …  P(xn)We can write a program to loop through the elements in the universe and check each for truthfulness. If all are false, then the proposition is false. Otherwise, it is true!Cs173 - Spring 2004CS 173 Predicates - not so boring examplesSuppose the universe of discourse is all creatures, and define the following:L(x) = “x is a lion.”F(x) = “x is fierce.”C(x) = “x drinks coffee.”All lions are fierce.Some lions don’t drink coffee.Some fierce creatures don’t drink coffee.x (L(x)  F(x))x (L(x)  C(x)) x (F(x)   C(x))Cs173 - Spring 2004CS 173 Predicates - not so boring examplesAnother:B(x) = “x is a hummingbird.”L(x) = “x is a large bird.”H(x) = “x lives on honey.”R(x) = “x is richly colored.”All hummingbirds are richly colored.No large birds live on honey.Birds that do not live on honey are dully colored.x (B(x)  R(x))x (L(x)  H(x)) x (H(x)  R(x))Cs173 - Spring 2004CS 173 Predicates - quantifier negationNo large birds live on honey.x P(x) means “P(x) is true for every x.”What about x P(x) ?Not[“P(x) is true for every x.”]“There is an x for which P(x) is not true.”x P(x)So, x P(x) is the same as x P(x).x (L(x)  H(x))Cs173 - Spring 2004CS 173 Predicates - quantifier negationNo large birds live on honey.x P(x) means “P(x) is true for some x.”What about x P(x) ?Not[“P(x) is true for some x.”]“P(x) is not true for all x.”x P(x)So, x P(x) is the same as x P(x).x (L(x)  H(x))Cs173 - Spring 2004CS 173 Predicates - quantifier negationNo large birds live on honey.So, x P(x) is the same as x P(x).So, x P(x) is the same as x P(x).General rule: to negate a