Page 83 - Discrete Mathematics and Its Applications

62 1 / The Foundations: Logic and Proofs

into English, where F(a,b) means a and b are friends and the domain for x, y, and z consists of
all students in your school.

Solution: We first examine the expression (F(x, y) ∧ F(x, z) ∧ (y = z)) →¬F(y, z). This
expression says that if students x and y are friends, and students x and z are friends, and
furthermore, if y and z are not the same student, then y and z are not friends. It follows that
the original statement, which is triply quantified, says that there is a student x such that for all
students y and all students z other than y,if x and y are friends and x and z are friends, then y
and z are not friends. In other words, there is a student none of whose friends are also friends
with each other. ▲

Translating English Sentences into Logical Expressions

In Section 1.4 we showed how quantifiers can be used to translate sentences into logical expres-
sions. However, we avoided sentences whose translation into logical expressions required the
use of nested quantifiers. We now address the translation of such sentences.
EXAMPLE 11 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: The statement “If a person is female and is a parent, then this person is someone’s
mother” can be expressed 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)).

Using the null quantification rule in part (b) of Exercise 47 in Section 1.4, we can move ∃y to
the left so that it appears just after ∀x, because y does not appear in F(x) ∧ P(x). We obtain
the logically equivalent expression

∀x∃y((F(x) ∧ P(x)) → M(x, y)). ▲

EXAMPLE 12 Express the statement “Everyone has exactly one best friend” as a logical expression involving
predicates, quantifiers with a domain consisting of all people, and logical connectives.
Solution: The statement “Everyone has exactly one best friend” can be expressed as “For every
person x, person x has exactly one best friend.” Introducing the universal quantifier, we see
that this statement is the same as “∀x(person x has exactly one best friend),” where the domain
consists of all people.
To say that x has exactly one best friend means that there is a person y who is the best friend
of x, and furthermore, that for every person z, if person z is not person y, then z is not the best
friend of x. When we introduce the predicate B(x, y) to be the statement “y is the best friend
of x,” the statement that x has exactly one best friend can be represented as

∃y(B(x, y) ∧∀z((z = y) →¬B(x, z))).

Consequently, our original statement can be expressed as

∀x∃y(B(x, y) ∧∀z((z = y) →¬B(x, z))).