Page 69 - Discrete Mathematics and Its Applications

48 1 / The Foundations: Logic and Proofs

EXAMPLE 22 Show that ¬Hx(P (x) → Q(x)) and ∃x(P (x) ∧¬Q(x)) are logically equivalent.

Solution: By De Morgan’s law for universal quantifiers, we know that ¬Hx(P (x) → Q(x))
and ∃x(¬(P (x) → Q(x))) are logically equivalent. By the fifth logical equivalence in Table 7
in Section 1.3, we know that ¬(P (x) → Q(x)) and P(x) ∧¬Q(x) are logically equivalent
for every x. Because we can substitute one logically equivalent expression for another in a
logical equivalence, it follows that ¬Hx(P (x) → Q(x)) and ∃x(P (x) ∧¬Q(x)) are logically
equivalent. ▲

Translating from English into Logical Expressions

Translating sentences in English (or other natural languages) into logical expressions is a crucial
task in mathematics, logic programming, artificial intelligence, software engineering, and many
other disciplines. We began studying this topic in Section 1.1, where we used propositions to
express sentences in logical expressions. In that discussion, we purposely avoided sentences
whose translations required predicates and quantifiers. Translating from English to logical ex-
pressions becomes even more complex when quantifiers are needed. Furthermore, there can
be many ways to translate a particular sentence. (As a consequence, there is no “cookbook”
approach that can be followed step by step.) We will use some examples to illustrate how to
translate sentences from English into logical expressions. The goal in this translation is to pro-
duce simple and useful logical expressions. In this section, we restrict ourselves to sentences
that can be translated into logical expressions using a single quantifier; in the next section, we
will look at more complicated sentences that require multiple quantifiers.

EXAMPLE 23 Express the statement “Every student in this class has studied calculus” using predicates and
quantifiers.

Solution: First, we rewrite the statement so that we can clearly identify the appropriate quantifiers
to use. Doing so, we obtain:
“For every student in this class, that student has studied calculus.”

Next, we introduce a variable x so that our statement becomes
“For every student x in this class, x has studied calculus.”

Continuing, we introduce C(x), which is the statement “x has studied calculus.” Consequently,
if the domain for x consists of the students in the class, we can translate our statement as ∀xC(x).
However, there are other correct approaches; different domains of discourse and other
predicates can be used. The approach we select depends on the subsequent reasoning we want
to carry out. For example, we may be interested in a wider group of people than only those in
this class. If we change the domain to consist of all people, we will need to express our statement
as

“For every person x, if person x is a student in this class then x has studied calculus.”
If S(x) represents the statement that person x is in this class, we see that our statement can be
expressed as ∀x(S(x) → C(x)).[Caution! Our statement cannot be expressed as ∀x(S(x) ∧
C(x)) because this statement says that all people are students in this class and have studied
calculus!]
Finally, when we are interested in the background of people in subjects besides calculus,
we may prefer to use the two-variable quantifier Q(x, y) for the statement “student x has
studied subject y.” Then we would replace C(x) by Q(x, calculus) in both approaches to obtain
∀xQ(x, calculus) or ∀x(S(x) → Q(x, calculus)). ▲