المحاضرة الثانية هياكل متقطعة

Propositional logic
• Definition:
– A proposition is a statement that is either true or false.
• Examples:
– Pitt is located in the Oakland section of Pittsburgh.
– 5 + 2 = 8.
– It is raining today
– 2 is a prime number
– If (you do not drive over 65 mph) then (you will not get a
speeding ticket).
• Not a proposition:
– How are you?
– x + 5 = 3
Limitations of the propositional logic
Propositional logic: the world is described in terms of
elementary propositions and their logical combinations
Elementary statements:
• 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 them
John a Upitt student
object a property
CS 441 Discrete mathematics for CS M. Hauskrecht
Limitations of the propositional logic
(1) Statements that must be repeated for many objects
– In propositional logic these must be exhaustively enumerated
• Example:
– If John is a CS UPitt graduate then John has passed cs441
Translation:
– John is a CS UPitt graduate ? John has passed cs441
Similar statements can be written for other Upitt graduates:
– Ann is a CS Upitt graduate ? Ann has passed cs441
– Ken is a CS Upitt graduate ? Ken has passed cs441
– …
• What is a more natural solution to express the above
knowledge?
8
CS 441 Discrete mathematics for CS M. Hauskrecht
Limitations of the propositional logic
(1) Statements that must be repeated for many objects
• Example:
– If John is a CS UPitt graduate then John has passed cs441
Translation:
– John is a CS UPitt graduate ? John has passed cs441
Similar statements can be written for other Upitt graduates:
– 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
– If x is a CS Upitt graduate then x has passed cs441
– x is a CS UPitt graduate ? x has passed cs441
CS 441 Discrete mathematics for CS M. Hauskrecht
Limitations of the propositional logic
(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 honors.
• 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 property
9
CS 441 Discrete mathematics for CS M. Hauskrecht
Predicate logic
Remedies the limitations of the propositional logic
• Explicitly models objects and their properties
• Allows to make statements with variables and quantify them
Basic building blocks of the predicate logic:
• Constant –models a specific object
Examples: “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 objects
Examples: Red(car23), student(x), married(John,Ann)
CS 441 Discrete mathematics for CS M. Hauskrecht
Predicates
Predicates 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 discourse
Example:
• 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)
• …
10
CS 441 Discrete mathematics for CS M. Hauskrecht
Predicates
Assume a predicate P(x) that represents the statement:
• x is a prime number
What are the truth values of:
• P(2) T
• P(3) T
• P(4) F
• P(5) T
• P(6) F
• P(7) T
All statements P(2), P(3), P(4), P(5), P(6), P(7) are propositions