Predicates and Quantification 135not fixed for all time. We want to allow variables (or variable symbols), such as p and q,
which represent elements of some nonempty universal set. These variables are not propo-
sition letters, because they do not evaluate to T or F. Rather, after an assignment of values
to the variables, such as 2 to x and 5 to y, the predicates, such as x = 3 or x > y, become
2 = 3 and 2 > 5, both of which are F. We can think of similar instances in natural language
when we assert "He is tall and she is of average height." The pronouns he and she can be
thought of as placeholders or variables representing a range of particular men or women.
2.71 Predicates
A property or relationship between objects is called a predicate. A description of a predi-
cate in logic is called a formula.
A formula such as x < 3 is an atomic formula, built with the predicate <. An atomic
formula is a formula for which the terms do not involve any of the logical operations (and,
or, implication, biconditional, negation), only proposition letters and constants from the
universal set. The predicate < is binary or (2-ary); it represents a relationship between
two objects. The first object is a variable x; the second is a constant 3. If a specific value
x0 is substituted into the predicate for x, it becomes x0 < 3. Now, if x0 = -37, then x0 < 3
evaluates to T. If x0 = 6, then x0 < 3 evaluates to F. When a predicate involves n argu-
ments, it is said to be n-ary; we write an n-ary formula P(xl, x2, ... Xn).
Example 1. The following are predicates:
(a) Let P(x, y, z) denote "x + y = z."
(b) Let Q(x 1 , X2) denote "xl - x2 > 0."
(c) Let M(x, y) denote "x is married to y."
(d) Let E(x, y) denote "x = y."
Once we are given a group of predicates, we may refer to them in formulas. So,
P(x, y, z), Q(x 1 , x2), M(x, y), and E(x, y) are all atomic formulas. The variable names
are not important, so P(xI, z, x2) and Q(y, y) are also atomic formulas. Just as in usual
notation, Q(y, y) denotes "y - y > 0."
In normal uses of logic, the universal set U and the meanings of all predicates, such
as < or a variable P, are specified. We limit ourselves to this understanding.
2.72 Quantification
If we have a predicate, such as <, that is defined on two objects, then logic gives us two
ways to specify what objects we mean. One way is to specify values from the universal
set, such as 3 < 6. Another way is called quantification. It comes in two forms: universal
quantification, denoted by the symbol V; and existential quantification, denoted by the
symbol 3.
The first form is universal quantification for the predicate P, such as.
Vx (P(x)) read "For all x, P(x)"is defined to mean "For all values x in the universal set U, the assertion P(x) is true."