Page 70 - Discrete Mathematics and Its Applications

1.4 Predicates and Quantifiers 49

In Example 23 we displayed different approaches for expressing the same statement using
predicates and quantifiers. However, we should always adopt the simplest approach that is
adequate for use in subsequent reasoning.

EXAMPLE 24 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 in this class with the property that the student has visited Mexico.”

We can introduce a variable x, so that our statement becomes

“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).
However, if we are interested in people other than those in this class, we look at the statement
a little differently. Our statement can be expressed as

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

In this case, the domain for the variable x consists of all people. We introduce S(x) to represent
“x is a student in this class.” Our solution becomes ∃x(S(x) ∧ M(x)) because the statement is
that there is a person x who is a student in this class and who has visited Mexico. [Caution! Our
statement cannot be expressed as ∃x(S(x) → M(x)), which is true when there is someone not
in the class because, in that case, for such a person x, S(x) → M(x) becomes either F → T or
F → F, both of which are true.]
Similarly, the second statement can be expressed as

“For every x in this class, x has the property that x has visited Mexico or x has visited
Canada.”

(Note that we are assuming the inclusive, rather than the exclusive, or here.) We let C(x) be “x
has visited Canada.” Following our earlier reasoning, we see that if the domain for x consists of
the students in this class, this second statement can be expressed as ∀x(C(x) ∨ M(x)). However,
if the domain for x consists of all people, our statement can be expressed as

“For every person x,if x is a student in this class, then x has visited Mexico or x has visited
Canada.”

In this case, the statement can be expressed as ∀x(S(x) → (C(x) ∨ M(x))).
Instead of using M(x) and C(x) to represent that x has visited Mexico and x has visited
Canada, respectively, we could use a two-place predicate V (x, y) to represent “x has visited
country y.” In this case, V(x, Mexico) and V(x, Canada) would have the same meaning as M(x)
and C(x) and could replace them in our answers. If we are working with many statements that
involve people visiting different countries, we might prefer to use this two-variable approach.
Otherwise, for simplicity, we would stick with the one-variable predicates M(x) and C(x). ▲