Page 78 - Discrete Mathematics and Its Applications

1.5 Nested Quantifiers 57

62. Let P(x), Q(x), R(x), and S(x) be the statements “x b) No officers ever decline to waltz.
is a duck,” “x is one of my poultry,” “x is an officer,” c) All my poultry are ducks.
and “x is willing to waltz,” respectively. Express each of
these statements using quantifiers; logical connectives; d) My poultry are not officers.
and P(x), Q(x), R(x), and S(x). ∗ e) Does (d) follow from (a), (b), and (c)? If not, is there
a) No ducks are willing to waltz. a correct conclusion?

1.5 Nested Quantifiers

Introduction

In Section 1.4 we defined the existential and universal quantifiers and showed how they can
be used to represent mathematical statements. We also explained how they can be used to
translate English sentences into logical expressions. However, in Section 1.4 we avoided nested
quantifiers, where one quantifier is within the scope of another, such as

∀x∃y(x + y = 0).

Note that everything within the scope of a quantifier can be thought of as a propositional function.
For example,

∀x∃y(x + y = 0)

is the same thing as ∀xQ(x), where Q(x) is ∃yP (x, y), where P (x, y) is x + y = 0.
Nested quantifiers commonly occur in mathematics and computer science.Although nested
quantifiers can sometimes be difficult to understand, the rules we have already studied in
Section 1.4 can help us use them. In this section we will gain experience working with nested
quantifiers. We will see how to use nested quantifiers to express mathematical statements such
as “The sum of two positive integers is always positive.” We will show how nested quantifiers
can be used to translate English sentences such as “Everyone has exactly one best friend” into
logical statements. Moreover, we will gain experience working with the negations of statements
involving nested quantifiers.

Understanding Statements Involving Nested Quantifiers

To understand statements involving nested quantifiers, we need to unravel what the quantifiers
and predicates that appear mean. This is illustrated in Examples 1 and 2.
EXAMPLE 1 Assume that the domain for the variables x and y consists of all real numbers. The statement

∀x∀y(x + y = y + x)

says that x + y = y + x for all real numbers x and y. This is the commutative law for addition
of real numbers. Likewise, the statement

∀x∃y(x + y = 0)
says that for every real number x there is a real number y such that x + y = 0. This states that
every real number has an additive inverse. Similarly, the statement

∀x∀y∀z(x + (y + z) = (x + y) + z)

is the associative law for addition of real numbers. ▲