Maggie Johnson Handout #18

CS103A

Multiple Quantifiers

Key Topics

· Multiple Uses of a Single Quantifier

· Mixed Quantifiers

· Another Perspective: Nested Loops

· Translation

Some Practice from Lewis Carroll:

All hummingbirds are richly colored.

No large birds live on honey.

Birds that do not live on honey are dull in color.

Hummingbirds are small.

What are good definitions for our predicates?

How would you translate these to FOL?

Is the fourth a valid conclusion given the first three as premises?

Multiple Uses of a Single Quantifier

$x $y (boy(x) ^ girl(y) ^ likes(x,y))

"x "y (tet(x) ^ dodec(y) ® smaller(x,y))

Let P(x,y) mean “x has taken class y”. The domain of discourse for x is the set of all students in your class and for y is the set of all CS classes at Stanford. How would you translate the following?

$x $y P(x,y)

"x "y P(x,y)

Mixed Quantifiers

Continue with the P(x,y) example above (“x has taken class y”). How would you translate the following?

$x "y P(x,y)

"x $y P(x,y)

Order of the quantifiers matters!

$y "x P(x,y)

"y $x P(x,y)

Order of the variables matters!

Q(x,y): x + y = 0. What are the truth values of the quantifications $y "x Q(x,y) and

"x $y Q(x,y) if the universe is all real numbers?

$y "x Q(x,y) means there is a real number y such that for every possible real number x, Q(x,y) is true. No matter what value of y is chosen, there is one and only one value of x which will make x+y=0 true, so this quantification is false.

"x $y Q(x,y) means for every possible real number x, there exists a real number y such that x+y = 0. In this case, y = -x, and the quantification is true.

Summary of Quantifiers in Arity-Two Predicates

Statement When true? When false?

"x "y P(x,y) P(x,y) is true for every pair (x,y) a pair (x,y) exists where

P(x,y) is false

"x $y P(x,y) For every x, there is a y for which There is an x such that P(x,y)

P(x,y) is true is false for every y

$x "y P(x,y) There is an x for which P(x,y) is For every x, there is a y for

true for every y which P(x,y) is false

$x $y P(x,y) There is a pair (x,y) for which P(x,y) is false for all pairs

P(x,y) is true (x,y)

Another Perspective: Nested Loops

In working with quantifications of more than one variable it is sometimes useful to think in terms of nested loops. Of course, if the universe is infinite this won’t quite work, but it’s still useful.

To check:

1) "x "y P(x,y): loop through all the values of x and for each x, loop through all the values of y. If P(x,y) is true for all these iterations, we have determined "x "y P(x,y) is true. If we ever hit an x value for which we hit a y value for which P(x,y) is false, then we know "x "y P(x,y) is false.

2) "x $y P(x,y): loop through all the values of x and for each x, loop through all the values of y until we find one y value for which P(x,y) is true. If for all x, we find such a y value, then we have determined "x $y P(x,y) is true. If for some x, we never find a y value for which P(x,y) is true, then we know "x $y P(x,y) is false.

3) $x "y P(x,y): What is the analogy for this one?

4) $x $y P(x,y): loop through the values for x, where for each x, we loop through the values for y until we hit an x for which we hit a y for which P(x,y) is true. If we can never find an x for which we hit a such a y, then it’s false.

Translations

1) Let Q(x,y,z) be the statement x + y = z. What are the truth values of the statements: "x "y $z Q(x,y,z) and $z "x "y Q(x,y,z)?

2) Let L(x,y) be the statement “x loves y” where the domain of discourse for both x and y is the set of all people in the world. Translate the following into FOL:

a. Everybody loves Fred.

b. Everybody loves somebody.

c. There is someone whom no one loves.

d. Everyone loves himself or herself.

3) If someone is female and is a parent, then this person is someone’s mother.

4) There is a woman who has taken a flight on every airline in the world.