Predicates and QuantifiersTerminology reviewPropositional functionsPropositional functions 2Anatomy of a propositional functionPropositional functions 3So, why do we care about quantifiers?QuantifiersUniversal quantifiers 1Universal quantifiers 2Universal quantifiers 3Universal quantification 4Universal quantification 5Existential quantification 1Existential quantification 2Existential quantification 3Existential quantification 4A note on quantifiersBinding variablesBinding variables 2Negating quantificationsNegating quantifications 2Translating from EnglishTranslating from English 2Translating from English 3Translating from English 4Translating from English 5Translating from English 6Translating from English 7Translating from English 8PrologProlog 2Multiple quantifiersOrder of quantifiersNegating multiple quantifiersNegating multiple quantifiers 2Translating between English and quantifiersSlide 40Negation examplesSlide 42Rules of inference for the universal quantifierRules of inference for the existential quantifierExample of proofSlide 46Slide 47Slide 481Predicates and QuantifiersCS 202, Spring 2007Epp, Sections 2.1 and 2.2Aaron Bloomfield2Terminology review•Proposition: a statement that is either true or false–Must always be one or the other!–Example: “The sky is red”–Not a proposition: x + 3 > 4•Boolean variable: A variable (usually p, q, r, etc.) that represents a proposition3Propositional functions•Consider P(x) = x < 5–P(x) has no truth values (x is not given a value)–P(1) is true•The proposition 1<5 is true–P(10) is false•The proposition 10<5 is false•Thus, P(x) will create a proposition when given a value4Propositional functions 2•Let P(x) = “x is a multiple of 5”–For what values of x is P(x) true?•Let P(x) = x+1 > x–For what values of x is P(x) true?•Let P(x) = x + 3–For what values of x is P(x) true?5Anatomy of a propositional functionP(x) = x + 5 > xvariable predicate6Propositional functions 3•Functions with multiple variables:–P(x,y) = x + y == 0•P(1,2) is false, P(1,-1) is true–P(x,y,z) = x + y == z•P(3,4,5) is false, P(1,2,3) is true–P(x1,x2,x3 … xn) = …7So, why do we care about quantifiers?•Many things (in this course and beyond) are specified using quantifiers–In some cases, it’s a more accurate way to describe things than Boolean propositions8Quantifiers•A quantifier is “an operator that limits the variables of a proposition”•Two types:–Universal–Existential9Universal quantifiers 1•Represented by an upside-down A: –It means “for all”–Let P(x) = x+1 > x•We can state the following:x P(x)–English translation: “for all values of x, P(x) is true”–English translation: “for all values of x, x+1>x is true”10Universal quantifiers 2•But is that always true?x P(x)•Let x = the character ‘a’–Is ‘a’+1 > ‘a’?•Let x = the state of Virginia–Is Virginia+1 > Virginia?•You need to specify your universe!–What values x can represent–Called the “domain” or “universe of discourse” by the textbook11Universal quantifiers 3•Let the universe be the real numbers.–Then, x P(x) is true•Let P(x) = x/2 < x–Not true for the negative numbers!–Thus, x P(x) is false•When the domain is all the real numbers•In order to prove that a universal quantification is true, it must be shown for ALL cases•In order to prove that a universal quantification is false, it must be shown to be false for only ONE case12Universal quantification 4•Given some propositional function P(x)•And values in the universe x1 .. xn•The universal quantification x P(x) implies:P(x1)  P(x2)  …  P(xn)13Universal quantification 5•Think of  as a for loop:x P(x), where 1 ≤ x ≤ 10•… can be translated as …for ( x = 1; x <= 10; x++ )is P(x) true?•If P(x) is true for all parts of the for loop, then x P(x)–Consequently, if P(x) is false for any one value of the for loop, then x P(x) is false14Existential quantification 1•Represented by an bacwards E: –It means “there exists”–Let P(x) = x+1 > x•We can state the following:x P(x)–English translation: “there exists (a value of) x such that P(x) is true”–English translation: “for at least one value of x, x+1>x is true”15Existential quantification 2•Note that you still have to specify your universe–If the universe we are talking about is all the states in the US, then x P(x) is not true•Let P(x) = x+1 < x–There is no numerical value x for which x+1<x–Thus, x P(x) is false16Existential quantification 3•Let P(x) = x+1 > x–There is a numerical value for which x+1>x•In fact, it’s true for all of the values of x!–Thus, x P(x) is true•In order to show an existential quantification is true, you only have to find ONE value•In order to show an existential quantification is false, you have to show it’s false for ALL values17Existential quantification 4•Given some propositional function P(x)•And values in the universe x1 .. xn•The existential quantification x P(x) implies:P(x1)  P(x2)  …  P(xn)18A note on quantifiers•Recall that P(x) is a propositional function–Let P(x) be “x == 0”•Recall that a proposition is a statement that is either true or false–P(x) is not a proposition•There are two ways to make a propositional function into a proposition:–Supply it with a value•For example, P(5) is false, P(0) is true–Provide a quantifiaction•For example,  x P(x) is false and x P(x) is true–Let the universe of discourse be the real numbers20Binding variables•Let P(x,y) be x > y•Consider: x P(x,y)–This is not a proposition!–What is y?•If it’s 5, then x P(x,y) is false•If it’s x-1, then x P(x,y) is true•Note that y is not “bound” by a quantifier21Binding variables 2•(x P(x))  Q(x)–The x in Q(x) is not bound; thus not a proposition•(x P(x))  (x Q(x))–Both x values are bound; thus it is a proposition•(x P(x)  Q(x))  (y R(y))–All variables are bound; thus it is a proposition•(x P(x)  Q(y))  (y R(y))–The y in Q(y) is not bound; this not a proposition22Negating quantifications•Consider the statement:–All students in this class have red hair•What is required to show the statement is