Page 66 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 45

The part of a logical expression to which a quantifier is applied is called the scope of this
quantifier. Consequently, a variable is free if it is outside the scope of all quantifiers in the
formula that specify this variable.

EXAMPLE 18 In the statement ∃x(x + y = 1), the variable x is bound by the existential quantification ∃x,but
the variable y is free because it is not bound by a quantifier and no value is assigned to this
variable. This illustrates that in the statement ∃x(x + y = 1), x is bound, but y is free.
In the statement ∃x(P (x) ∧ Q(x)) ∨∀xR(x), all variables are bound. The scope of the first
quantifier, ∃x, is the expression P(x) ∧ Q(x) because ∃x is applied only to P(x) ∧ Q(x), and
not to the rest of the statement. Similarly, the scope of the second quantifier, ∀x, is the expression
R(x). That is, the existential quantifier binds the variable x in P(x) ∧ Q(x) and the universal
quantifier ∀x binds the variable x in R(x). Observe that we could have written our statement
using two different variables x and y,as ∃x(P (x) ∧ Q(x)) ∨∀yR(y), because the scopes of
the two quantifiers do not overlap. The reader should be aware that in common usage, the same
letter is often used to represent variables bound by different quantifiers with scopes that do not
overlap. ▲

Logical Equivalences Involving Quantifiers

In Section 1.3 we introduced the notion of logical equivalences of compound propositions. We
can extend this notion to expressions involving predicates and quantifiers.

DEFINITION 3 Statements involving predicates and quantifiers are logically equivalent if and only if they
have the same truth value no matter which predicates are substituted into these statements
and which domain of discourse is used for the variables in these propositional functions.
We use the notation S ≡ T to indicate that two statements S and T involving predicates and
quantifiers are logically equivalent.

Example 19 illustrates how to show that two statements involving predicates and quantifiers
are logically equivalent.

EXAMPLE 19 Show that ∀x(P (x) ∧ Q(x)) and ∀xP (x) ∧∀xQ(x) are logically equivalent (where the same
domain is used throughout). This logical equivalence shows that we can distribute a universal
quantifier over a conjunction. Furthermore, we can also distribute an existential quantifier over
a disjunction. However, we cannot distribute a universal quantifier over a disjunction, nor can
we distribute an existential quantifier over a conjunction. (See Exercises 50 and 51.)

Solution: To show that these statements are logically equivalent, we must show that they always
take the same truth value, no matter what the predicates P and Q are, and no matter which
domain of discourse is used. Suppose we have particular predicates P and Q, with a common
domain. We can show that ∀x(P(x) ∧ Q(x)) and ∀xP(x) ∧∀xQ(x) are logically equivalent
by doing two things. First, we show that if ∀x(P(x) ∧ Q(x)) is true, then ∀xP(x) ∧∀xQ(x)
is true. Second, we show that if ∀xP(x) ∧∀xQ(x) is true, then ∀x(P(x) ∧ Q(x)) is true.
So, suppose that ∀x(P(x) ∧ Q(x)) is true. This means that if a is in the domain, then
P(a) ∧ Q(a) is true. Hence, P(a) is true and Q(a) is true. Because P(a) is true and Q(a) is
true for every element in the domain, we can conclude that ∀xP(x) and ∀xQ(x) are both true.
This means that ∀xP(x) ∧∀xQ(x) is true.
Next, suppose that ∀xP(x) ∧∀xQ(x) is true. It follows that ∀xP(x) is true and ∀xQ(x) is
true. Hence, if a is in the domain, then P(a) is true and Q(a) is true [because P(x) and Q(x)
are both true for all elements in the domain, there is no conflict using the same value of a here].