1M. HauskrechtCS 441 Discrete mathematics for CSCS 441 Discrete Mathematics for CSLecture 4Milos [email protected] Sennott SquarePredicate logicM. HauskrechtCS 441 Discrete mathematics for CSAnnouncements• Homework assignment 1 due today• Homework assignment 2:– posted on the course web page– Due on Thursday January 23, 2013• Recitations today and tomorrow:– Practice problems related to assignment 22M. HauskrechtCS 441 Discrete mathematics for CSPropositional logic: limitationsPropositional logic: the world is described in terms of elementary propositions and their logical combinations Elementary statements/propositions:• Typically refer to objects, their properties and relations. But these are not explicitly represented in the propositional logic– Example:• “John is a UPitt student.”• Objects and properties are hidden in the statement, it is not possible to reason about themJohn a Upitt studentobject a propertyM. HauskrechtCS 441 Discrete mathematics for CSPropositional logic: limitations(1) Statements that hold for many objects must be enumerated• Example:– John is a CS UPitt graduate  John has passed cs441– Ann is a CS Upitt graduate  Ann has passed cs441– Ken is a CS Upitt graduate  Ken has passed cs441– …• Solution: make statements with variables– x is a CS UPitt graduate  x has passed cs4413M. HauskrechtCS 441 Discrete mathematics for CSPropositional logic: limitations(2) Statements that define the property of the group of objects• Example:– All new cars must be registered. – Some of the CS graduates graduate with honor. • Solution: make statements with quantifiers – Universal quantifier –the property is satisfied by all members of the group– Existential quantifier – at least one member of the group satisfy the propertyM. HauskrechtCS 441 Discrete mathematics for CSPredicate logicRemedies the limitations of the propositional logic• Explicitly models objects and their properties• Allows to make statements with variables and quantify themPredicate logic: • Constant –models a specific objectExamples: “John”, “France”, “7” • Variable – represents object of specific type (defined by the universe of discourse)Examples: x, y (universe of discourse can be people, students, numbers)• Predicate - over one, two or many variables or constants. – Represents properties or relations among objectsExamples: Red(car23), student(x), married(John,Ann)4M. HauskrechtCS 441 Discrete mathematics for CSPredicatesPredicates represent properties or relations among objects• A predicate P(x) assigns a value true or false to each x depending on whether the property holds or not for x.• The assignment is best viewed as a big table with the variable x substituted for objects from the universe of discourseExample:• Assume Student(x) where the universe of discourse are people• Student(John) …. T (if John is a student)• Student(Ann) …. T (if Ann is a student)• Student(Jane) ….. F (if Jane is not a student)• …M. HauskrechtCS 441 Discrete mathematics for CSPredicatesAssume a predicate P(x) that represents the statement:• x is a prime numberTruth values for different x:• P(2) T• P(3) T•P(4) F• P(5) T• P(6) FAll statements P(2), P(3), P(4), P(5), P(6) are propositions…But P(x) with variable x is not a proposition5M. HauskrechtCS 441 Discrete mathematics for CSQuantified statementsPredicate logic lets us to make statements about groups of objects• To do this we use special quantified expressionsTwo types of quantified statements:• universalExample: ‘ all CS Upitt graduates have to pass cs441” – the statement is true for all graduates• existentialExample: ‘Some CS Upitt students graduate with honor.’– the statement is true for some peopleM. HauskrechtCS 441 Discrete mathematics for CSUniversal quantifierQuantification converts a propositional function into a proposition by binding a variable to a set of values from the universe of discourse. Example: • Let P(x) denote x > x - 1. Assume x are real numbers. • Is P(x) a proposition? No. Many possible substitutions.•Is x P(x) a proposition? Yes.• What is the truth value for x P(x) ?– True, since P(x) holds for all x.6M. HauskrechtCS 441 Discrete mathematics for CSExistential quantifierQuantification converts a propositional function into a proposition by binding a variable to a set of values from the universe of discourse. Example:• Let T(x) denote x > 5 and x is from Real numbers. • Is T(x) a proposition? No. •Is x T(x) a proposition? Yes. • What is the truth value for x T(x) ?– Since 10 > 5 is true. Therefore, x T(x) is true.M. HauskrechtCS 441 Discrete mathematics for CSSummary of quantified statements• When x P(x) and x P(x) are true and false?Suppose the elements in the universe of discourse can be enumerated as x1, x2, ..., xN then:• x P(x) is true whenever P(x1)  P(x2)  ...  P(xN) is true• x P(x) is true whenever P(x1)  P(x2)  ...  P(xN) is true. Statement When true? When false?x P(x)P(x) true for all xThere is an x where P(x) is false.x P(x) There is some x for which P(x) is true.P(x) is false for all x.7M. HauskrechtTranslation with quantifiersSentence:• All Upitt students are smart. • Assume: the domain of discourse of x are Upitt students• Translation:• x Smart(x) • Assume: the universe of discourse are students (all students):• x at(x,Upitt)  Smart(x)• Assume: the universe of discourse are people:• x student(x)  at(x,Upitt)  Smart(x)M. HauskrechtTranslation with quantifiersSentence: • Someone at CMU is smart.• Assume: the domain of discourse are all CMU affiliates• Translation:•  x Smart(x) • Assume: the universe of discourse are people:•  x at(x,CMU)  Smart(x)8M. HauskrechtTranslation with quantifiers• Assume two predicates S(x) and P(x)Universal statements typically tie with implications• All S(x) is P(x)– x ( S(x)  P(x) )• No S(x) is P(x)– x( S(x)  ¬P(x) )Existential statements typically tie with conjunctions• Some S(x) is P(x)– x (S(x)  P(x) )• Some S(x) is not P(x) – x (S(x)  ¬P(x) )M. HauskrechtNested quantifiers • More than one quantifier may be necessary to capture the meaning of a statement in the predicate logic.Example:• Every real number has its corresponding negative. •