Page 71 - Discrete Mathematics and Its Applications

50 1 / The Foundations: Logic and Proofs

Using Quantifiers in System Specifications

In Section 1.2 we used propositions to represent system specifications. However, many system
specifications involve predicates and quantifications. This is illustrated in Example 25.

EXAMPLE 25 Use predicates and quantifiers to express the system specifications “Every mail message larger
than one megabyte will be compressed” and “If a user is active, at least one network link will
be available.”

Solution: Let S(m, y) be “Mail message m is larger than y megabytes,” where the variable x has
the domain of all mail messages and the variable y is a positive real number, and let C(m) denote
“Mail message m will be compressed.” Then the specification “Every mail message larger than
one megabyte will be compressed” can be represented as ∀m(S(m, 1) → C(m)).
Remember the rules of
precedence for quantifiers Let A(u) represent “User u is active,” where the variable u has the domain of all users,
and logical connectives! let S(n, x) denote “Network link n is in state x,” where n has the domain of all network
links and x has the domain of all possible states for a network link. Then the specifica-
tion “If a user is active, at least one network link will be available” can be represented by
∃uA(u) →∃nS(n, available). ▲

Examples from Lewis Carroll

Lewis Carroll (really C. L. Dodgson writing under a pseudonym), the author of Alice in Wonder-
land, is also the author of several works on symbolic logic. His books contain many examples
of reasoning using quantifiers. Examples 26 and 27 come from his book Symbolic Logic; other
examples from that book are given in the exercises at the end of this section. These examples
illustrate how quantifiers are used to express various types of statements.

EXAMPLE 26 Consider these statements.The first two are called premises and the third is called the conclusion.
The entire set is called an argument.
“All lions are fierce.”
“Some lions do not drink coffee.”
“Some fierce creatures do not drink coffee.”
(In Section 1.6 we will discuss the issue of determining whether the conclusion is a valid conse-
quence of the premises. In this example, it is.) Let P(x), Q(x), and R(x) be the statements “x is
a lion,” “x is fierce,” and “x drinks coffee,” respectively.Assuming that the domain consists of all
creatures, express the statements in the argument using quantifiers and P(x), Q(x), and R(x).

CHARLES LUTWIDGE DODGSON (1832–1898) We know Charles Dodgson as Lewis Carroll—the
pseudonym he used in his literary works. Dodgson, the son of a clergyman, was the third of 11 children,
all of whom stuttered. He was uncomfortable in the company of adults and is said to have spoken without
stuttering only to young girls, many of whom he entertained, corresponded with, and photographed (sometimes
in poses that today would be considered inappropriate). Although attracted to young girls, he was extremely
puritanical and religious. His friendship with the three young daughters of Dean Liddell led to his writing Alice
in Wonderland, which brought him money and fame.
Dodgson graduated from Oxford in 1854 and obtained his master of arts degree in 1857. He was appointed
lecturer in mathematics at Christ Church College, Oxford, in 1855. He was ordained in the Church of England
in 1861 but never practiced his ministry. His writings published under this real name include articles and books on geometry,
determinants, and the mathematics of tournaments and elections. (He also used the pseudonym Lewis Carroll for his many works
on recreational logic.)