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

Predicates
• Predicates can have more arguments which represent the
relations between objects
Example:
• Older(John, Peter) denotes ‘John is older than Peter’
– this is a proposition because it is either true or false
• Older(x,y) - ‘x is older than y’
– not a proposition, but after the substitution it becomes one
Predicates
• Predicates can have more arguments which represent the
relations between objects
Example:
• Let Q(x,y) denote ‘x+5 >y’
– Is Q(x,y) a proposition? No!
– Is Q(3,7) a proposition? Yes. It is true.
– What is the truth value of:
– Q(3,7) T
– Q(1,6) F
– Q(2,2) T
– Is Q(3,y) a proposition? No! We cannot say if it is true or
Compound statements in predicate logic
Compound statements are obtained via logical connectives
Examples:
Student(Ann) ? Student(Jane)
• Translation: “Both Ann and Jane are students”
• Proposition: yes.
Country(Sienna) ? River(Sienna)
• Translation: “Sienna is a country or a river”
• Proposition: yes.
CS-major(x) ? Student(x)
• Translation: “if x is a CS-major then x is a student”
Predicates
Important:
• statement P(x) is not a proposition since there are more objects
it can be applied to
This is the same as in propositional logic …
… But the difference is:
• predicate logic allows us to explicitly manipulate and substitute
for the objects
• Predicate logic permits quantified sentences where variables are
substituted for statements about the group of objects
Quantified statements
Predicate logic lets us to make statements about groups of
objects
• To do this we use special quantified expressions
Two types of quantified statements:
• universal
Example: ‘ all CS Upitt graduates have to pass cs441”
– the statement is true for all graduates
• existential
Example: ‘Some CS Upitt students graduate with honor.’
Universal quantifier
Defn: The universal quantification of P(x) is the proposition:
"P(x) is true for all values of x in the domain of discourse." The
notation ?x P(x) denotes the universal quantification of P(x),
and is expressed as for every x, P(x).
Example:
• Let P(x) denote x > x - 1.
• What is the truth value of ?x P(x)?
• Assume the universe of discourse of x is all real numbers.
• Answer: Since every number x is greater than itself minus 1.
Universal quantifier
Quantification 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.
• Is P(x) a proposition? No. Many possible substitutions.
• Is ?x P(x) a proposition? Yes. True if for all x from the
Universally quantified statements
Predicate logic lets us make statements about groups of objects
Universally quantified statement
• CS-major(x) ? Student(x)
– Translation: “if x is a CS-major then x is a student”
– Proposition: no.
• ?x CS-major(x) ? Student(x)
– Translation: “(For all people it holds that) if a person is a
CS-major then she is a student.”
– Proposition: yes.