المحاضرة الرابعة

Translation 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. Hauskrecht
Nested 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.
• Translation:
– Assume:
• a real number is denoted as x and its negative as y
• A predicate P(x,y) denotes: “x + y =0”
• Then we can write:
?x ? y P(x,y)
9
M. Hauskrecht
Nested quantifiers
• More than one quantifier may be necessary to capture the
meaning of a statement in the predicate logic.
Example:
• There is a person who loves everybody.
• Translation:
– Assume:
• Variables x and y denote people
• A predicate L(x,y) denotes: “x loves y”
• Then we can write in the predicate logic:
? x ?y L(x,y)
M. Hauskrecht
Order of quantifiers
The order of nested quantifiers matters if quantifiers are of
different type
• ?x?y L(x,y) is not the same as ?y?x L(x,y)
Example:
• Assume L(x,y) denotes “x loves y”
• Then: ?x?y L(x,y)
• Translates to: Everybody loves somebody.
• And: ?y ?x L(x,y)
• Translates to: There is someone who is loved by everyone.
The meaning of the two is different.
10
M. Hauskrecht
Order of quantifiers
The order of nested quantifiers does not matter if quantifiers
are of the same type
Example:
• For all x and y, if x is a parent of y then y is a child of x
• Assume:
– Parent(x,y) denotes “x is a parent of y”
– Child(x,y) denotes “x is a child of y”
• Two equivalent ways to represent the statement:
– ?x ?y Parent(x,y) ? Child(y,x)
– ?y ?x Parent(x,y) ? Child(y,x)
M. Hauskrecht
Translation exercise
Suppose:
– Variables x,y denote people
– L(x,y) denotes “x loves y”.
Translate:
• Everybody loves Raymond. ?x L(x,Raymond)
• Everybody loves somebody. ?x?y L(x,y)
• There is somebody whom everybody loves. ?y?x L(x,y)
• There is somebody who Raymond doesn t love.
?y¬L(Raymond,y)
• There is somebody whom no one loves.
?y ?x ¬L(x,y)