PredicateLogic andQuantifiersCSE235Predicate Logic and QuantifiersSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.3–1.4 of [email protected] / 1PredicateLogic andQuantifiersCSE235IntroductionConsider the following statements:x > 3, x = y + 3, x + y = zThe truth value of these statements has no meaning withoutspecifying the values of x, y, z.However, we can make propositions out of such statements.A predicate is a property that is affirmed or denied about thesubject (in logic, we s ay “variable” or “argument”) of astatement.“ x|{z}subjectis greater than 3”|{z }predicateTerminology: affirmed = holds = is true; denied = does nothold = is not true.2 / 1PredicateLogic andQuantifiersCSE235Propositional FunctionsTo write in predicate logic:“ x|{z}subjectis greater than 3”| {z }predicateWe introduce a (functional) symbol for the predicate, and putthe subject as an argument (to the functional symbol): P (x)Examples:Father(x): unary predicateBrother(x,y): binary predicateSum(x,y,z): ternary predicateP(x,y,z,t): n-ary predicate3 / 1PredicateLogic andQuantifiersCSE235Propositional FunctionsDefinitionA statement of the form P(x1, x2, . . . , xn) is the value of thepropositional function P . Here, (x1, x2, . . . , xn) is an n-tupleand P is a predicate.You can think of a propositional function as a function thatEvaluates to true or false.Takes one or more arguments.Expresses a predicate involving the argument(s).Becomes a proposition when values are assigned t o thearguments.4 / 1PredicateLogic andQuantifiersCSE235Propositional FunctionsExampleExampleLet Q(x, y, z) denote the statement “x2+ y2= z2”. What isthe truth value of Q(3, 4, 5)? What is the truth value ofQ(2, 2, 3)? How many values of (x, y, z) make the predicatetrue?Since 32+ 42= 25 = 52, Q(3, 4, 5) is true.Since 22+ 22= 8 6= 32= 9, Q(2, 2, 3) is false.There are infinitely many values for (x, y, z) that make thispropositional function true—how many right triangles arethere?5 / 1PredicateLogic andQuantifiersCSE235Propositional FunctionsExampleExampleLet Q(x, y, z) denote the statement “x2+ y2= z2”. What isthe truth value of Q(3, 4, 5)? What is the truth value ofQ(2, 2, 3)? How many values of (x, y, z) make the predicatetrue?Since 32+ 42= 25 = 52, Q(3, 4, 5) is true.Since 22+ 22= 8 6= 32= 9, Q(2, 2, 3) is false.There are infinitely many values for (x, y, z) that make thispropositional function true—how many right triangles arethere?5 / 1PredicateLogic andQuantifiersCSE235Universe of DiscourseConsider the previous example. Does it make sense to assign tox the value “blue”?Intuitively, the universe of discourse is the set of all things wewish to talk about; that is, the set of all objects that we cansensibly assign to a variable in a propositional function.What would be the universe of discourse for the propositionalfunction P (x) = “The test will be on x the 23rd” be?6 / 1PredicateLogic andQuantifiersCSE235Universe of DiscourseMultivariate FunctionsMoreover, each variable in an n-tuple may have a differe ntuniverse of discourse.Let P (r, g, b, c) = “The rgb-value of the color c is (r, g, b)”.For example, P (255, 0, 0, red) is true, while P (0, 0, 255, green)is false.What are the universes of discourse for (r, g, b, c)?7 / 1PredicateLogic andQuantifiersCSE235QuantifiersIntroductionA predicate becomes a proposition when we assign it fixedvalues. However, another way to make a predicate into aproposition is to quantify it. That is, the predicate is true (orfalse) for all possible values in the universe of discourse or forsome value(s) in the universe of discourse.Such quantification can be done with two quantifiers: theuniversal quantifier and the existential quantifier.8 / 1PredicateLogic andQuantifiersCSE235Universal QuantifierDefinitionDefinitionThe universal quantification of a predicate P (x) is theproposition “P (x) is true for all values of x in the universe ofdiscourse” We use the notation∀xP (x)which can be read “for all x”If the universe of discourse is finite, say {n1, n2, . . . , nk}, thenthe universal quantifier is simply the conjunction of allelements:∀xP (x) ⇐⇒ P (n1) ∧ P (n2) ∧ · · · ∧ P (nk)9 / 1PredicateLogic andQuantifiersCSE235Universal QuantifierExample ILet P (x) be the predicate “x must take a discretemathematics course” and let Q(x) be the predicate “x is acomputer science student”.The universe of discourse for both P (x) and Q(x) is allUNL students.Express the statem ent “E very c omputer sc ience studentmust take a discrete mathematics course”.∀x(Q(x) → P (x))Express the statem ent “E verybody must take a discretemathematics course or be a computer science student”.∀x(Q(x) ∨ P (x))Are hetse statements true or false?10 / 1PredicateLogic andQuantifiersCSE235Universal QuantifierExample ILet P (x) be the predicate “x must take a discretemathematics course” and let Q(x) be the predicate “x is acomputer science student”.The universe of discourse for both P (x) and Q(x) is allUNL students.Express the statem ent “E very c omputer sc ience studentmust take a discrete mathematics course”.∀x(Q(x) → P (x))Express the statem ent “E verybody must take a discretemathematics course or be a computer science student”.∀x(Q(x) ∨ P (x))Are hetse statements true or false?10 / 1PredicateLogic andQuantifiersCSE235Universal QuantifierExample ILet P (x) be the predicate “x must take a discretemathematics course” and let Q(x) be the predicate “x is acomputer science student”.The universe of discourse for both P (x) and Q(x) is allUNL students.Express the statem ent “E very c omputer sc ience studentmust take a discrete mathematics course”.∀x(Q(x) → P (x))Express the statem ent “E verybody must take a discretemathematics course or be a computer science student”.∀x(Q(x) ∨ P (x))Are hetse statements true or false?10 / 1PredicateLogic andQuantifiersCSE235Universal QuantifierExample ILet P (x) be the predicate “x must take a discretemathematics course” and let Q(x) be the predicate “x is acomputer science student”.The universe of discourse for both P (x) and Q(x) is allUNL students.Express the statem ent “E very c omputer sc ience studentmust take a discrete mathematics course”.∀x(Q(x) → P (x))Express the statem ent “E verybody must take a discretemathematics course or be a computer
View Full Document
Unlocking...