Raymond Smullyan's Knight and Knave Word Problem

• April 24, 2005
• James Skemp
• article, philosophy

According to David Gries (via his site), logician Raymond Smullyan stated the following word problem in one of his many books, which regards lying knaves and truthful knights.

A group of three people, each of which is a knight (tells the truth all the time) or a knave (lies all the time) are talking. B says that C and D are the same type (both knaves or both knights). Someone then asks D, “Are B and C the same type?” What does D answer?

While Dr. Gries states that case analysis is confusing, I beg to differ. According to this, we look at what would happen if a number of cases were true. In logic books, this is most often done by way of a truth table.

First, we must determine our variables. We have, as given in the problem itself, B, C, and D, each of which can be either a knight or a knave.

Second, we must determine our equations. We have two different equations. For the first, does C = D according to B. For the second, does B = C according to D. Of course, if B or D is lying, then they will give us the opposite answer.

B	C	D	B, C = D?	D, B = C?
Knight	Knight	Knight	True	True
Knight	Knight	Knave	False	False
Knight	Knave	Knight	False	False
Knight	Knave	Knave	True	True
Knave	Knight	Knight	False	False
Knave	Knight	Knave	True	True
Knave	Knave	Knight	True	True
Knave	Knave	Knave	False	False

Now, we are given that B says that C and D are the same. We can therefore look at just those that have ‘True’ in our ‘B, C = D?’ column.

B	C	D	B, C = D?	D, B = C?
Knight	Knight	Knight	True	True
Knight	Knave	Knave	True	True
Knave	Knight	Knave	True	True
Knave	Knave	Knight	True	True

We see now that D would say that B and C are the same as well. We also see that either one of them is a knight and the other two are knaves, or they are all knights.

Of course, the question is not what the type of each is, but rather is a question of what D answers. So, if one is able to find at least one of these cases, they can answer the question – the answer does not require all possibilities to be found, assuming that the question does not bring about contradictory answers.

Let us, for our own benefit, now ask what C would say to the question of whether B is the same type as D.

B	C	D	B, C = D?	D, B = C?	C, B = D?
Knight	Knight	Knight	True	True	True
Knight	Knight	Knave	False	False	False
Knight	Knave	Knight	False	False	False
Knight	Knave	Knave	True	True	True
Knave	Knight	Knight	False	False	False
Knave	Knight	Knave	True	True	True
Knave	Knave	Knight	True	True	True
Knave	Knave	Knave	False	False	False

We see that C would give the same reasons as the others when asked the question. This is really quite interesting, if not only because it at first appears we’re asking the question of whether C = D and B = C, and therefore if B = D. We presume that if someone tells us that C = D, and that another tells us that B = C, then B = D. However, if we bring lying, or more broadly, doubt into the equation, we find that that is not necessarily the case.

We can expand upon this same example. For example, let us take some individual E, which we know is either a knight or a knave. Let us ask this individual if they are a knight.

E	E, E = Knight?
Knight	True
Knave	True

Now let us look at what would have been the case if we had asked them if they were a knave, instead.

E	E, E = Knave?
Knight	False
Knave	False

We can, therefore, get nowhere if simply ask an individual whether or not they always lie or always tell the truth, just as we cannot ask an individual if they ever lie, for they may lie or may tell the truth when they answer the question.

But, does having two people help our quest for the truth? Let us take F and G, which are each either a knight or a knave. Now let us ask one if they are of the same type, similar to what was asked in the original question, and he answers that they are.

F	G	F, F = G?
Knight	Knight	True
Knight	Knave	False
Knave	Knight	True
Knave	Knave	False

At the very least we know that G is a Knight. We can then ask G if they are the same.

F	G	G, F = G?
Knight	Knight	True
Knight	Knave	True
Knave	Knight	False
Knave	Knave	False

However, this requires two questions. Can we do it in one? If we were to ask F is G is a knight, and they say yes, we see that they are at least the same class (and if they say no, that they are of a different class).

F	G	F, G = Knight?
Knight	Knight	True
Knight	Knave	False
Knave	Knight	False
Knave	Knave	True

We could ask a more difficult question of F; if you were G, would you say that F is a knight? If he said yes, we would at least know that G is a knight. Here, the third column contains the answer, and the fourth/last is for assistance while reading the table.

F	G	F, if G, F = Knight?	(G, F = Knight?)
Knight	Knight	True	True
Knight	Knave	False	False
Knave	Knight	True	False
Knave	Knave	False	True

This gives us the idea of asking the following question of F to find out F’s status. If you were F, and you were asked if F would say that F was a knight, what would you say?

F	F, F = Knight?	F, if F, F = Knight?
Knight	True	True
Knave	True	False

Therefore, if we look at the question that originally got us going on this thread, the better question would be to ask B first whether or not if they were B, whether they would tell us if they were a knight. If they say that if they were B they would tell us that they would tell us that they were a knight, then we know that they are a knight. On the other hand, if they were to tell us that they would not tell us that B was a knight, if they were B, then we know that they are a knave. For if B were a liar they would lie and say that they were a knight if they were asked if they were a knight, but, because B is asked whether B would lie if they were B and asked, they would have to say that B would not say that.

Note

While the problem and solution are found at http://www.cs.cornell.edu/Info/People/gries/Logic/Neatsolution.html, I have gone about solving the problem my own particular way, by expanding out the possible cases in a table.