Page 41 - Discrete Mathematics and Its Applications

20 1 / The Foundations: Logic and Proofs

EXAMPLE 8 A father tells his two children, a boy and a girl, to play in their backyard without getting dirty.
However, while playing, both children get mud on their foreheads. When the children stop
playing, the father says “At least one of you has a muddy forehead,” and then asks the children
to answer “Yes” or “No” to the question: “Do you know whether you have a muddy forehead?”
The father asks this question twice. What will the children answer each time this question is
asked, assuming that a child can see whether his or her sibling has a muddy forehead, but cannot
see his or her own forehead? Assume that both children are honest and that the children answer
each question simultaneously.

Solution: Let s be the statement that the son has a muddy forehead and let d be the statement that
the daughter has a muddy forehead. When the father says that at least one of the two children
has a muddy forehead, he is stating that the disjunction s ∨ d is true. Both children will answer
“No” the first time the question is asked because each sees mud on the other child’s forehead.
That is, the son knows that d is true, but does not know whether s is true, and the daughter
knows that s is true, but does not know whether d is true.
After the son has answered “No” to the first question, the daughter can determine that d
must be true. This follows because when the first question is asked, the son knows that s ∨ d is
true, but cannot determine whether s is true. Using this information, the daughter can conclude
that d must be true, for if d were false, the son could have reasoned that because s ∨ d is true,
then s must be true, and he would have answered “Yes” to the first question. The son can reason
in a similar way to determine that s must be true. It follows that both children answer “Yes” the
second time the question is asked. ▲

Logic Circuits

Propositional logic can be applied to the design of computer hardware. This was first observed
in 1938 by Claude Shannon in his MIT master’s thesis. In Chapter 12 we will study this topic
in depth. (See that chapter for a biography of Shannon.) We give a brief introduction to this
application here.
A logic circuit (or digital circuit) receives input signals p 1 ,p 2 ,...,p n , each a bit [either
0 (off) or 1 (on)], and produces output signals s 1 ,s 2 ,...,s n , each a bit. In this section we will
restrict our attention to logic circuits with a single output signal; in general, digital circuits may
In Chapter 12 we design
some useful circuits. have multiple outputs.

RAYMOND SMULLYAN (BORN 1919) Raymond Smullyan dropped out of high school. He wanted to study
what he was really interested in and not standard high school material. After jumping from one university to
the next, he earned an undergraduate degree in mathematics at the University of Chicago in 1955. He paid
his college expenses by performing magic tricks at parties and clubs. He obtained a Ph.D. in logic in 1959 at
Princeton, studying under Alonzo Church. After graduating from Princeton, he taught mathematics and logic at
Dartmouth College, Princeton University, Yeshiva University, and the City University of New York. He joined
the philosophy department at Indiana University in 1981 where he is now an emeritus professor.
Smullyan has written many books on recreational logic and mathematics, including Satan, Cantor, and
Infinity; What Is the Name of This Book?; The Lady or the Tiger?; Alice in Puzzleland; To Mock a Mockingbird;
Forever Undecided; and The Riddle of Scheherazade: Amazing Logic Puzzles, Ancient and Modern. Because his logic puzzles are
challenging, entertaining, and thought-provoking, he is considered to be a modern-day Lewis Carroll. Smullyan has also written
several books about the application of deductive logic to chess, three collections of philosophical essays and aphorisms, and several
advanced books on mathematical logic and set theory. He is particularly interested in self-reference and has worked on extending
some of Gödel’s results that show that it is impossible to write a computer program that can solve all mathematical problems. He is
also particularly interested in explaining ideas from mathematical logic to the public.
Smullyan is a talented musician and often plays piano with his wife, who is a concert-level pianist. Making telescopes is one
of his hobbies. He is also interested in optics and stereo photography. He states “I’ve never had a conflict between teaching and
research as some people do because when I’m teaching, I’m doing research.” Smullyan is the subject of a documentary short film
entitled This Film Needs No Title.