Page 72 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 51

Solution: We can express these statements as:

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

Notice that the second statement cannot be written as ∃x(P (x) →¬R(x)). The reason is that
P(x) →¬R(x) is true whenever x is not a lion, so that ∃x(P (x) →¬R(x)) is true as long as
there is at least one creature that is not a lion, even if every lion drinks coffee. Similarly, the
third statement cannot be written as
▲
∃x(Q(x) →¬R(x)).

EXAMPLE 27 Consider these statements, of which the first three are premises and the fourth is a valid conclu-
sion.
“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)).
¬Px(Q(x) ∧ R(x)).
∀x(¬R(x) →¬S(x)).
∀x(P (x) →¬Q(x)).

(Note we have assumed that “small” is the same as “not large” and that “dull in color” is the
same as “not richly colored.” To show that the fourth statement is a valid conclusion of the first
three, we need to use rules of inference that will be discussed in Section 1.6.) ▲

Logic Programming

An important type of programming language is designed to reason using the rules of predicate
logic. Prolog (from Programming in Logic), developed in the 1970s by computer scientists
working in the area of artificial intelligence, is an example of such a language. Prolog programs
include a set of declarations consisting of two types of statements, Prolog facts and Prolog
rules. Prolog facts define predicates by specifying the elements that satisfy these predicates.
Prolog rules are used to define new predicates using those already defined by Prolog facts.
Example 28 illustrates these notions.

EXAMPLE 28 Consider a Prolog program given facts telling it the instructor of each class and in which classes
students are enrolled. The program uses these facts to answer queries concerning the professors
who teach particular students. Such a program could use the predicates instructor(p, c) and