The famous logician Raymond Smullyan (see his biography -by the way, he once visited PSU) is the author of many puzzles that are an excellent way to assess our understanding of Predicate Logic. Two of his books, What is the Name of This Book?, and Forever Undecided play an important role in the CSC217 Discrete Mathematics course, because some of those problems are analyzed in class and tend to pop up in quizzes and exams. Some of these problems have been included in textbooks, anyway.
These problems are very imaginative and rich, yet for their solution they require nothing more than an elementary knowledge of Predicate Calculus. In guise of introduction to this interesting subject I will quote some of these problems along with a solution for each of them. Try to figure them out before you see the solution. They are usually not too hard.
McGregor, the census taker, visits the island of Bahava which is populated only by knights and knaves. Knights always tell the truth and knaves always lie. McGregor goes down the street knocking on doors when one little shy old man opens the door. ``I am a census taker and need some information about you and your wife. Are both of you knaves?''-McGregor asks. The little shy fellow answers ``At least one of us is.'' What can McGregor infer about the type of each member of this couple?
| 1. |
 |
The man may be a knight or a knave. |
| 2. |
 |
This is what the man says. |
| 3. |
 |
Let's assume he is a knave. |
| 4. |
 |
If he's a knave, then the negation of what he says must be true. |
| 5. |
 |
But this contradicts our assumption! |
| 6. |  |
Therefore, he must be a knight, |
| 7. |
 |
so what he says is true, therefore |
| 8. |
 |
from 6, 7 and the elimination rule. |
Solution. In English, the man can be a knight or a knave. Let's assume he's a knave, then he must be lying and his assertion ``At least one of us is (a knave)'' must be false, so it must be true that he and his wife are knights. But this contradicts our assumption, so he must be a knight. Since knights always tell the truth his assertion must be true, therefore his wife must be a knave.
McGregor knocked on one door; the husband partly opened it and asked McGregor his business. ``I'm a census taker,'' replied McGregor, ``and I need information about you and your wife. Which, if either, is a knight, and which, if either, is a knave?''
``We are both knaves!'' said the husband angrily as he slammed the door.
What type is the husband and what type is the wife?
Solution. If the husband were a knight, he would never have claimed that he and his wife were both knaves. Therefore he must be a knave. Since he is a knave, his statement is false; so they are not both knaves. This means his wife must be a knight. Therefore he is a knave and she is a knight.
The next home visited by McGregor proved more of a puzzler. The door was opened timidly by a rather shy man. After McGregor asked him to say something about himself and his wife, all the husband said was: ``If I am a knight, then so is my wife.''
McGregor walked away none too pleased. ``How can I tell anything about either of them from such a noncommittal response?'' he thought. He was about to write down ``Husband and wife both unknown'', when he suddenly realized an old logic lesson from his Oxford undergraduate days. ``Of course,'' he realized, ``I can tell both their types!''
What type is the husband and what type is the wife?
Solution. Suppose the man is a knight. Then it is true what he said-namely, that if he is a knight, so is his wife-and hence his wife must also be a knight. This proves that if the husband is a knight, so is his wife. Well, that's exaclty what the husband said; he said that if he is a knight, then so is his wife. Therefore he made a true statement and so he must be a knight. We know that he is a knight, and we have already proved that if he is a knight, so is his wife. Therefore the husband and wife must both be knights.