Page 40 - Discrete Mathematics and Its Applications

1.2 Applications of Propositional Logic 19

Next, to find pages that deal with universities in New Mexico or Arizona, we can search
for pages matching (NEW AND MEXICO OR ARIZONA) AND UNIVERSITIES. (Note: Here
the AND operator takes precedence over the OR operator. Also, in Google, the terms used for
this search would be NEW MEXICO OR ARIZONA.) The results of this search will include
all pages that contain the word UNIVERSITIES and either both the words NEW and MEXICO
or the word ARIZONA. Again, pages besides those of interest will be listed. Finally, to find
Web pages that deal with universities in Mexico (and not New Mexico), we might first look
for pages matching MEXICO AND UNIVERSITIES, but because the results of this search will
include pages about universities in New Mexico, as well as universities in Mexico, it might be
better to search for pages matching (MEXICO AND UNIVERSITIES) NOT NEW. The results
of this search include pages that contain both the words MEXICO and UNIVERSITIES but
do not contain the word NEW. (In Google, and many other search engines, the word “NOT” is
replaced by the symbol “-”. In Google, the terms used for this last search would be MEXICO
UNIVERSITIES -NEW.) ▲

Logic Puzzles

Puzzles that can be solved using logical reasoning are known as logic puzzles. Solving logic
puzzles is an excellent way to practice working with the rules of logic.Also, computer programs
designed to carry out logical reasoning often use well-known logic puzzles to illustrate their
capabilities. Many people enjoy solving logic puzzles, published in periodicals, books, and on
the Web, as a recreational activity.
We will discuss two logic puzzles here.We begin with a puzzle originally posed by Raymond
Smullyan, a master of logic puzzles, who has published more than a dozen books containing
challenging puzzles that involve logical reasoning. In Section 1.3 we will also discuss the
extremely popular logic puzzle Sudoku.

EXAMPLE 7 In [Sm78] Smullyan posed many puzzles about an island that has two kinds of inhabitants,
knights, who always tell the truth, and their opposites, knaves, who always lie. You encounter
two people A and B. What are A and B if A says “B is a knight” and B says “The two of us are
opposite types?”

Solution: Let p and q be the statements that A is a knight and B is a knight, respectively, so that
¬p and ¬q are the statements that A is a knave and B is a knave, respectively.
We first consider the possibility that A is a knight; this is the statement that p is true. If A is
a knight, then he is telling the truth when he says that B is a knight, so that q is true, and A and B
are the same type. However, if B is a knight, then B’s statement that A and B are of opposite
types, the statement (p ∧¬q) ∨ (¬p ∧ q), would have to be true, which it is not, because A
and B are both knights. Consequently, we can conclude that A is not a knight, that is, that p is
false.
If A is a knave, then because everything a knave says is false, A’s statement that B is
a knight, that is, that q is true, is a lie. This means that q is false and B is also a knave.
Furthermore, if B is a knave, then B’s statement that A and B are opposite types is a lie,
which is consistent with both A and B being knaves. We can conclude that both A and B are
knaves. ▲

We pose more of Smullyan’s puzzles about knights and knaves in Exercises 19–23. In
Exercises 24–31 we introduce related puzzles where we have three types of people, knights and
knaves as in this puzzle together with spies who can lie.
Next, we pose a puzzle known as the muddy children puzzle for the case of two children.