Page 61 - Discrete Mathematics and Its Applications

40 1 / The Foundations: Logic and Proofs

Solution: For the precondition, we need to express that x and y have particular values before
we run the program. So, for this precondition we can use the predicate P (x, y), where P (x, y)
is the statement “x = a and y = b,” where a and b are the values of x and y before we run the
program. Because we want to verify that the program swaps the values of x and y for all input
values, for the postcondition we can use Q(x, y), where Q(x, y) is the statement “x = b and
y = a.”
To verify that the program always does what it is supposed to do, suppose that the precon-
dition P (x, y) holds. That is, we suppose that the statement “x = a and y = b” is true. This
means that x = a and y = b. The first step of the program, temp := x, assigns the value of x to
the variable temp, so after this step we know that x = a, temp = a, and y = b. After the second
step of the program, x := y, we know that x = b, temp = a, and y = b. Finally, after the third
step, we know that x = b, temp = a, and y = a. Consequently, after this program is run, the
postcondition Q(x, y) holds, that is, the statement “x = b and y = a” is true. ▲

Quantifiers

When the variables in a propositional function are assigned values, the resulting statement
becomes a proposition with a certain truth value. However, there is another important way, called
quantification, to create a proposition from a propositional function. Quantification expresses
the extent to which a predicate is true over a range of elements. In English, the words all, some,
many, none, and few are used in quantifications. We will focus on two types of quantification
here: universal quantification, which tells us that a predicate is true for every element under
consideration, and existential quantification, which tells us that there is one or more element
under consideration for which the predicate is true. The area of logic that deals with predicates
and quantifiers is called the predicate calculus.

THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is
true for all values of a variable in a particular domain, called the domain of discourse (or
the universe of discourse), often just referred to as the domain. Such a statement is expressed
using universal quantification. The universal quantification of P(x) for a particular domain is the
proposition that asserts that P(x) is true for all values of x in this domain. Note that the domain
specifies the possible values of the variable x. The meaning of the universal quantification
of P(x) changes when we change the domain. The domain must always be specified when a
universal quantifier is used; without it, the universal quantification of a statement is not defined.

DEFINITION 1 The universal quantification of P(x) is the statement

“P(x) for all values of x in the domain.”

The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the
universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element
for which P(x) is false is called a counterexample of ∀xP(x).

The meaning of the universal quantifier is summarized in the first row of Table 1. We
illustrate the use of the universal quantifier in Examples 8–13.