Page 58 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 37

No rules of propositional logic allow us to conclude the truth of the statement

“MATH3 is functioning properly,”

where MATH3 is one of the computers connected to the university network. Likewise, we cannot
use the rules of propositional logic to conclude from the statement

“CS2 is under attack by an intruder,”

where CS2 is a computer on the university network, to conclude the truth of

“There is a computer on the university network that is under attack by an intruder.”

In this section we will introduce a more powerful type of logic called predicate logic.We
will see how predicate logic can be used to express the meaning of a wide range of statements
in mathematics and computer science in ways that permit us to reason and explore relationships
between objects. To understand predicate logic, we first need to introduce the concept of a
predicate.Afterward, we will introduce the notion of quantifiers, which enable us to reason with
statements that assert that a certain property holds for all objects of a certain type and with
statements that assert the existence of an object with a particular property.

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.
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. Consider
Examples 1 and 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. ▲