Page 38 - Discrete Mathematics and Its Applications

1.2 Applications of Propositional Logic 17

often ambiguous. Translating sentences into compound statements (and other types of logical
expressions, which we will introduce later in this chapter) removes the ambiguity. Note that
this may involve making a set of reasonable assumptions based on the intended meaning of the
sentence. Moreover, once we have translated sentences from English into logical expressions
we can analyze these logical expressions to determine their truth values, we can manipulate
them, and we can use rules of inference (which are discussed in Section 1.6) to reason about
them.
To illustrate the process of translating an English sentence into a logical expression, consider
Examples 1 and 2.

EXAMPLE 1 How can this English sentence be translated into a logical expression?

“You can access the Internet from campus only if you are a computer science major or you
are not a freshman.”

Solution: There are many ways to translate this sentence into a logical expression.Although it is
possible to represent the sentence by a single propositional variable, such as p, this would not be
useful when analyzing its meaning or reasoning with it. Instead, we will use propositional vari-
ables to represent each sentence part and determine the appropriate logical connectives between
them. In particular, we let a, c, and f represent “You can access the Internet from campus,”
“You are a computer science major,” and “You are a freshman,” respectively. Noting that “only
if” is one way a conditional statement can be expressed, this sentence can be represented as

a → (c ∨¬f). ▲

EXAMPLE 2 How can this English sentence be translated into a logical expression?
“You cannot ride the roller coaster if you are under 4 feet tall unless you are older than 16
years old.”

Solution: Let q, r, and s represent “You can ride the roller coaster,” “You are under 4 feet tall,”
and “You are older than 16 years old,” respectively. Then the sentence can be translated to

(r ∧¬s) →¬q.

Of course, there are other ways to represent the original sentence as a logical expression,
but the one we have used should meet our needs. ▲

System Specifications

Translatingsentencesinnaturallanguage(suchasEnglish)intologicalexpressionsisanessential
part of specifying both hardware and software systems. System and software engineers take
requirements in natural language and produce precise and unambiguous specifications that can
be used as the basis for system development. Example 3 shows how compound propositions
can be used in this process.

EXAMPLE 3 Express the specification “The automated reply cannot be sent when the file system is full”
using logical connectives.

Solution: One way to translate this is to let p denote “The automated reply can be sent” and
q denote “The file system is full.” Then ¬p represents “It is not the case that the automated