Raymond Smullyan‘s logic puzzles frequently involve Knights (who always tell the truth) and Knaves (who always lie).
In his book Logical Labyrinths (really a first course in propositional logic) he introduced islands where the lying or truth-telling habits can vary from day to day—that is, an inhabitant might lie on some days and tell the truth on other days, but on any given day, he or she lies the entire day or tells the truth the entire day.
An island is said to be Boolean if is satisfies the following conditions:
- $\mathbf{N}$ : For any inhabitant $A$ there is an inhabitant who tells the truth on all and only those days on which $A$ lies.
- $\mathbf{M}$ : For any inhabitants $A$ and $B$ there is an inhabitant $C$ who tells the truth on all and only those days on which $A$ and $B$ both tell the truth.
- $\mathbf{J}$ : For any inhabitants $A$ and $B$ there is an inhabitant $C$ who tells the truth on all and only those days on which either $A$ tells the truth or $B$ tells the truth (or both). (In other words, $C$ lies on those and only those days on which $A$ and $B$ both lie.)
On any given day there are only Knights and Knaves on the island, but these two populations may vary from one day to the other. The subsets (of all days) for which there is an inhabitant who is a Knight then and a Knave on all other days form a Boolean algebra with operations $\wedge = \cap$ ($\mathbf{M}$eet), $\vee= \cup$ ($\mathbf{J}$oin) and $\neg=$ set-complement ($\mathbf{N}$egation).
Here’s a nice puzzle from Smullyan’s book:
Solomon’s Island also turned out to be quite interesting. When Craig arrived on it, he had the following conversation with the resident sociologist:
Craig : Is this island a Boolean island?
Sociologist : No.
Craig : Can you tell me something about the lying and truth-telling habits of the residents here?
Sociologist : For any inhabitants $A$ and $B$, there is an inhabitant $C$ who tells the truth on all and only those days on which either $A$ lies or $B$ lies (or both).
Show that the sociologist didn’t go native, and that his research is lousy.
(My wording, not Smullyan’s)
Smullyan’s version: This interview puzzled inspector Craig; he felt that something was wrong. After a while he realized for sure that something was wrong, the sociologist was either lying or mistaken!
Extending Smullyan’s idea, we can say that an island is Heyting if, in addition to $\mathbf{M}$ and $\mathbf{J}$ is satisfies the following rules
- $\mathbf{T}$ : at least one inhabitant tells the truth on all days.
- $\mathbf{F}$ : at least one inhabitant lies on all days.
- $\mathbf{I}$ : For any inhabitants $A$ and $B$ there is an inhabitant $C$ sharing Knight-days with $A$ only when $B$ tells the truth, and there are no inhabitants doing this while telling the truth on more days than $C$.
Let’s give an example of an Heyting island which is not Boolean.
On Three-island there are only three kinds of people: Knights, Knaves and Alternates, who can neither lie nor tell the truth two days in a row. All Alternates tell the truth on the same days.
Here’s a riddle:
You meet John, who is a Knight, James, an Alternate, and William, a Knave. You don’t know who is who. You can only ask one question containing at most four words, giving you a Yes or No answer, to just one of the three. The answer must tell you whether that person is James or not.
You may like to watch Smullyan on the Carson show for a hint.
Or, you might just watch it reminiscing long forgotten times, when talkshow-hosts still listened to their guests, and could think for themselves…
Comments