Predicates and Quantifiers

Introduction
Propositional logic, studied in previous lecture, cannot adequately
express the meaning of all statements in mathematics and in natural
language.
Predicates
Statements involving variables, such as
“x > 3,” “x = y + 3,” “x + y = z,”
and
“computer x is under attack by an intruder,”
and
“computer x is functioning properly,”

are often found in mathematical assertions, in computer programs, and in system

specifications. These statements are neither true nor false when the values of the
variables are not specified. In this section, we will discuss the ways that
propositions can be produced from such statements.
1
✔The statement “x is greater than 3” has two parts. The first part, the
variable x, is the subject of the statement. The second part—the
predicate, “is greater than 3”—refers to a property that the subject of
the statement can have. We can denote the statement “x is greater than
3” by P(x), where P denotes the predicate “is greater than 3” and x is
the variable.

✔The statement P(x) is also said to be the value of the propositional

function P at x. Once a value has been assigned to the variable x, the
statement P(x) becomes a proposition and has a truth value.

2
EXAMPLE 1 Let P(x) denote the statement “x > 3.” What are the
truth values of P(4) and P(2)?

Solution: We obtain the statement P(4) by setting x = 4 in the

statement “x > 3.” Hence, P(4), which is the statement “4 > 3,” is
true. However, P(2), which is the statement “2 > 3,” is false.

3
EXAMPLE 2 Let Q(x, y) denote the statement “x = y + 3.” What
are the truth values of the propositions Q(1, 2) and Q(3, 0)?

Solution: To obtain Q(1, 2), set x = 1 and y = 2 in the statement

Q(x, y). Hence, Q(1, 2) is the statement “1 = 2 + 3,” which is false.
The statement Q(3, 0) is the proposition “3 = 0 + 3,” which is true.

4
EXAMPLE 5 What are the truth values of the propositions R(1, 2, 3)
and R(0, 0, 1)?
Solution: The proposition R(1, 2, 3) is obtained by setting x = 1, y =
2, and z = 3 in the statement R(x, y, z). We see that R(1, 2, 3) is the
statement “1 + 2 = 3,” which is true. Also note that R(0, 0, 1), which
is the statement “0 + 0 = 1,” is false.

5
 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.
6
 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 x P(x).” An element for which P(x) is false is
called a counterexample of ∀xP(x).

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. 7
EXAMPLE 6 Let P(x) be the statement “x + 1 > x.” What is the
truth value of the quantification ∀xP(x), where the domain consists
of all real numbers?

Solution: Because P(x) is true for all real numbers x, the

quantification
∀xP(x)
is true.

8
EXAMPLE 7 Let Q(x) be the statement “x < 2.” What is the truth
value of the quantification ∀xQ(x), where the domain consists of
all real numbers?

Solution: Q(x) is not true for every real number x, because, for
instance, Q(3) is false. That is, x = 3 is a counterexample for the
statement ∀xQ(x). Thus
∀xQ(x)
is false.

9
The truth value of ∀xP(x) depends on the domain:

When all the elements in the domain can be listed—say, x1, x2, . . .,
xn—it follows that the
universal quantification ∀xP(x) is the same as the conjunction
P(x1) ∧ P(x2) ∧ · · · ∧ P(xn),
because this conjunction is true if and only if P(x1), P(x2), . . . , P (xn)
are all true.

10
EXAMPLE 8 What is the truth value of ∀xP(x), where P(x) is the
statement “x2 < 10” and the domain consists of the positive integers
not exceeding 4?

Solution: The statement ∀xP(x) is the same as the conjunction

P(1) ∧ P(2) ∧ P(3) ∧ P(4),
because the domain consists of the integers 1, 2, 3, and 4. Because
P(4), which is the statement “42 < 10,” is false, it follows that
∀xP(x) is false.

11
The existential quantification of P(x) is the proposition
“There exists an element x in the domain such that P(x).”
We use the notation ∃xP(x) for the existential quantification of
P(x). Here ∃ is called the existential quantifier.

EXAMPLE 9 Let P(x) denote the statement “x > 3.” What is the
truth value of the quantification ∃xP(x), where the domain consists
of all real numbers?

Solution: Because “x > 3” is sometimes true—for instance, when x =

4—the existential quantification of P(x), which is ∃xP(x), is true.

12
EXAMPLE 10 Let Q(x) denote the statement “x = x + 1.”What is
the truth value of the quantification ∃xQ(x), where the domain
consists of all real numbers?

Solution: Because Q(x) is false for every real number x, the

existential quantification of Q(x), which is ∃xQ(x), is false.

13
The truth value of ∃xP(x) depends on the domain:

When all elements in the domain can be listed—say, x1, x2, . . . ,

xn—the existential quantification
∃xP(x) is the same as the disjunction
P(x1) ∨ P(x2) ∨ · · · ∨ P(xn),
because this disjunction is true if and only if at least one of P(x1),
P(x2), . . . , P (xn) is true.

14
EXAMPLE 11 What is the truth value of ∃xP(x), where P(x) is
the statement “x2 > 10” and the universe of discourse consists of
the positive integers not exceeding 4?

Solution: Because the domain is {1, 2, 3, 4}, the proposition

∃xP(x) is the same as the disjunction
P(1) ∨ P(2) ∨ P(3) ∨ P(4).
Because P(4), which is the statement “42 > 10,” is true, it follows
that ∃xP(x) is true.

15
EXAMPLE 12 Express the statement “Every student in this class
has studied calculus” using predicates and quantifiers.

Solution:
Let us introduce a variable x so that our statement becomes

“For every student x in this class, x has studied calculus.”

Continuing, we introduce C(x), which is the statement “x has

studied calculus.”

Consequently, if the domain for x consists of the students in the

class, we can translate our statement as ∀xC(x).

16
EXAMPLE 13 Express the statements “Some student in this class
has visited Mexico” and “Every student in this class has visited either
Canada or Mexico” using predicates and quantifiers.

Solution: The statement “Some student in this class has visited

Mexico” means that

“There is a student x in this class having the property that x has visited
Mexico.”

We introduce M(x), which is the statement “x has visited Mexico.” If

the domain for x consists of the students in this class, we can translate
this first statement as ∃xM(x).

We let C(x) be “x has visited Canada.”

The second statement can be expressed as ∀x(C(x) ∨ M(x)).
17
EXAMPLE 14 Consider these statements. The first two are called premises and the
third is called the conclusion. The entire set is called an argument.
“All lions are fierce.”
“Some lions do not drink coffee.”
“Some fierce creatures do not drink coffee.”

Let P(x), Q(x), and R(x) be the statements “x is

a lion,” “x is fierce,” and “x drinks coffee,” respectively. Assuming that the domain
consists of all creatures, express the statements in the argument using quantifiers
and P(x), Q(x), and R(x).

Solution:We can express these statements as:

∀x(P(x) → Q(x)).
∃x(P(x) ∧ ￢R(x)).
∃x(Q(x) ∧ ￢R(x)).

18
EXAMPLE 15 Consider these statements, of which the first three
are premises and the fourth is a valid conclusion.
“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.”
Let P(x), Q(x), R(x), and S(x) be the statements “x is a hummingbird,”
“x is large,” “x lives on honey,” and “x is richly colored,”
respectively. Assuming that the domain consists of all birds, express
the statements in the argument using quantifiers and P(x), Q(x), R(x),
and S(x).

Solution:We can express the statements in the argument as

∀x(P(x) → S(x)).
￢∃x(Q(x) ∧ R(x)).
∀x(￢R(x)→￢S(x)).
∀x(P(x)→￢Q(x)). 19
Example-16
What are the negations of the statements ∀x(x2 > x) and ∃x(x2 = 2)?

Solution: The negation of ∀x(x2 > x) is the statement ￢∀x(x2 > x), which is
equivalent to ∃x￢(x2 > x). This can be rewritten as ∃x(x2 ≤ x).
The negation of ∃x(x2 = 2) is the statement ￢∃x(x2 = 2), which is equivalent to
∀x￢(x2 = 2). This can be rewritten as ∀x(x2 = 2). The
truth values of these statements depend on the domain.

20
Understanding Statements Involving Nested Quantifiers

21
EXAMPLE 19 Let Q(x, y) denote “x + y = 0.” What are the truth
values of the quantifications ∃y∀xQ(x, y) and ∀x∃yQ(x, y), where
the domain for all variables consists of all real numbers?
Solution: The quantification, ∃y∀xQ(x, y)
denotes the proposition
“There is a real number y such that for every real number x, Q(x, y).”
No matter what value of y is chosen, there is only one value of x for
which x + y = 0. Therefore the statement ∃y∀xQ(x, y) is false.

The quantification ∀x∃yQ(x, y) denotes the proposition

“For every real number x there is a real number y such that Q(x, y).”
Given a real number x, there is a real number y such that x + y = 0;
namely, y = −x. Hence, the statement ∀x∃yQ(x, y) is true.

22
EXAMPLE 20
Let Q(x, y, z) be the statement “x + y = z.” What are the truth values
of the statements ∀x∀y∃zQ(x, y, z) and ∃z∀x∀yQ(x, y, z),
where the domain of all variables consists of all real numbers?

Solution:
The quantification ∀x∀y∃zQ(x, y, z), which is the statement
“For all real numbers x and for all real numbers y there is a real
number z such that x + y = z,” is true.

∃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.
23
Example-21
Let A = {1, 2, 3, 4, 5}. Determine the truth value of each of the
following statements:
(a) (∃x ∈ A)(x + 3 = 10) (c) (∃x ∈ A)(x + 3 < 5)
(b) (∀x ∈ A)(x + 3 < 10) (d) (∀x ∈ A)(x + 3 ≤ 7)
Ans.
(a) False. For no number in A is a solution to x + 3 = 10.
(b) True. For every number in A satisfies x + 3 < 10.
(c) True. For if x = 1, then x + 3 < 5, i.e., 1 is a solution.
(d) False. For if x = 5, then x + 3 is not less than or equal 7. In other
words, 5 is not a solution to the given condition.

24
Example-22
Determine the truth value of each of the following statements where
U = {1, 2, 3} is the universal set.

Ans.
(a) ∃x∀y, x2 < y + 1; (b) ∀x∃y, x2 + y2 < 12; (c) ∀x∀y, x2 + y2
< 12.
(a) True. For if x = 1, then 1, 2, and 3 are all solutions to 1 < y + 1.
(b) True. For each x, let y = 1; then x2 + 1 < 12 is a true statement.
(c) False. For if x = 2 and y = 3, then x2+ y2 < 12 is not a true
statement.

25
EXAMPLE 24
Express the statement “If a person is female and is a parent, then this
person is someone’s mother” as a logical expression involving
predicates, quantifiers with a domain consisting of all people, and
logical connectives.

Solution: We can express as, “For every person x, if person x is female

and person x is a parent, then there exists a person y such that person x
is the mother of person y.” We introduce the propositional functions
F(x) to represent “x is female,” P(x) to represent “x is a parent,” and
M(x, y) to represent “x is the mother of y.” The original statement can
be represented as
∀x((F (x) ∧ P(x)) → ∃yM(x, y)).

26