Logic Puzzle: Who is the knave?

Problem:

In [Sm78] Smullyan posed many puzzles about an island that has two kinds of inhabitants, Extra ­ knights, who always ­ell 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 that 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) V (-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, which 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.