Page 81 - Discrete Mathematics and Its Applications

60 1 / The Foundations: Logic and Proofs

TABLE 1 Quantifications of Two Variables.
Statement When True? When False?
∀x∀yP (x, y) P (x, y) is true for every pair x, y. There is a pair x, y for
∀y∀xP (x, y) which P (x, y) is false.
∀x∃yP (x, y) For every x there is a y for There is an x such that
which P (x, y) is true. P (x, y) is false for every y.

∃x∀yP (x, y) There is an x for which P (x, y) For every x there is a y for
is true for every y. which P (x, y) is false.
∃x∃yP (x, y) There is a pair x, y for which P (x, y) is false for every
∃y∃xP (x, y) P (x, y) is true. pair x, y.

is true. The order of the quantification here is important, because the quantification

∃z∀x∀yQ(x, y, z),
which is the statement

“There is a real number z such that for all real numbers x and for all real numbers y it is
true that x + y = z,”

is false, because there is no value of z that satisfies the equation x + y = z for all values of x
and y. ▲

Translating Mathematical Statements into Statements
Involving Nested Quantifiers

Mathematical statements expressed in English can be translated into logical expressions, as
Examples 6–8 show.
EXAMPLE 6 Translate the statement “The sum of two positive integers is always positive” into a logical
expression.

Solution:Totranslatethisstatementintoalogicalexpression,wefirstrewriteitsothattheimplied
quantifiers and a domain are shown: “For every two integers, if these integers are both positive,
then the sum of these integers is positive.” Next, we introduce the variables x and y to obtain “For
all positive integers x and y, x + y is positive.” Consequently, we can express this statement as

∀x∀y((x > 0) ∧ (y > 0) → (x + y> 0)),
where the domain for both variables consists of all integers. Note that we could also translate
this using the positive integers as the domain. Then the statement “The sum of two positive
integers is always positive” becomes “For every two positive integers, the sum of these integers
is positive. We can express this as

∀x∀y(x + y> 0),

where the domain for both variables consists of all positive integers. ▲

EXAMPLE 7 Translate the statement “Every real number except zero has a multiplicative inverse.” (A mul-
tiplicative inverse of a real number x is a real number y such that xy = 1.)