Knights and knaves: Who are B and C? (task 26 from "What Is the Name of This Book?")

Question

I have the following issue #26 from What Is the Name of This Book? of R. Smullyan:

There is a wide variety of puzzles about an island in which certain inhabitants called "knights" always tell the truth, and others called "knaves" always lie. It is assumed that every inhabitant of the island is either a knight or a knave. I shall start with a well-known puzzle of this type and then follow it with a variety of puzzles of my own.

According to this old problem, three of the inhabitants — A, B, and C — were standing together in a garden. A stranger passed by and asked A, "Are you a knight or a knave?" A answered, but rather indistinctly, so the stranger could not make out what he said. The stranger than asked B, "What did A say?" B replied, "A said that he is a knave." At this point the third man, C, said, "Don't believe B; he is lying!" The question is, what are B and C?

I supposed that truth tables can be used, and composed the following:

   |   |   |      F1      |   F2   |    G       
===|===|===|==============|========|=========
 A | B | C | B ↔ (A ↔ ¬A) | C ↔ ¬B | F1 ^ F2 
===|===|===|==============|========|=========
 1 | 1 | 1 |      0       |   0    |    0
 1 | 1 | 0 |      0       |   1    |    0
 1 | 0 | 1 |      1       |   1    |    1
 1 | 0 | 0 |      1       |   0    |    0
 0 | 1 | 1 |      0       |   0    |    0
 0 | 1 | 0 |      0       |   1    |    0
 0 | 0 | 1 |      1       |   1    |    1
 0 | 0 | 0 |      1       |   0    |    0

Provided that:

1. We use $A$, when A is a knight, and $\neg A$, when A is a knave.
2. $F1$ is what B said ($A \leftrightarrow \neg A$), i. e. B said that A said he's knave. Therefore, B is telling the truth if and only if he's a knight ($B$).
3. $F2$ means that C is a knight if and only if he's telling the truth, i. e. B is a knave ($\neg B$).
4. $G$ allows us to select only those claims amongst $F1$ and $F2$ which are true.

can I safely say that we have only two cases, when $G$ is true and the following conclusions can be made:

1. B is a knave, because there are $0$s (false) in the appropriate rows.
2. C is a knight, because B is telling lies, and there are $1$s (true) in the appropriate rows.
3. We cannot say what is A exactly, because we couldn't make out what he said, and there are two cases in the table with $0$ and $1$ in the appropriate rows, where $G$ is true.

Please tell me if my calculations and the truth table are right, not only the conclusion. The best answer is one, which either explains what I'm missing in my truth table, or contains a correct one instead of mine, being supposedly wrong. I'm trying to figure out how they can be used, and I guess this issue is quite simple to play with, after all you have the same reasoning in your mind.

Thanks in advance.

Answer 1

Your table is incorrect in the F1 column in that $A \vee B \vee C$ should evaluate to 0 when all three are 0 (the bottom line). Otherwise your calculations are OK. Edit: this column has been removed.

The definition of F1 is not what you want. F1 is supposed to represent whether A spoke the truth, so should just be A. Edit: as this column has been removed, this does not apply.

Edit: this is incorrect as I misread the table. See the paragraph below. The definition of G is the biggest error. G should be $(A \leftrightarrow F1) \wedge (B \leftrightarrow F2) \wedge (C \leftrightarrow F3)$. This is the heart of the matter. You want A to have spoken the truth if and only if A is a knight, and the same for B and C. G should always be of this form (maybe more terms if you have more individuals involved) and will pick out the lines where the truth value of the statements matches the type of the individuals.

Added: G is correct. Your F1 says "B spoke properly for his type" and F2 says "C spoke properly for his type". So you want to find the cases both spoke properly. The fact that the 1's appear opposite B=0, C=1 both times says that B is a knave and C is a knight.

Answer 2

A truth table is really the wrong tool for this; and your table contains errors. For example, you assert that A v B v C is always true, even in the case when A, B, and C are all false! Truth tables (when correctly filled out) are useful in some situations, but the proper approach to this problem is to take a more direct deductive route.

First, we adopt the rule that knights always speak true statements, and knaves never do, and everyone is either a knight or a knave (and not both, unless they never speak!).

Under these assumptions, no one can say "I am a knave": a knight cannot say it, because it would not be a true statement; and a knave cannot say it because it would be a true statement.

Therefore, when B states "A said 'I am a knave'", then it is immediately the case that B is stating a falsehood, and thus we have proven that B is a knave.

Since C states a truth (i.e., that B has stated a falsehood), C cannot be a knave; therefore we have proven C is a knight.

That is much simpler and clearer than a logic table... in my humble opinion!

Answer 3

I agree with Chas Brown that the truth table is more work-intensive than required, but it can be used. What you need to do is (correctly) calculate the truth value of the statements for each possibility of knight/knave assignment. Then see if the truth value corresponds to the type for each person. This is a poor selection of a problem to demonstrate the method.

But we will try. The first column would be A's statement, which as Chas points out, is "I am a knight" regardless of his status. The second column would be the truth value of B's statement, which as Chas says is always false. The third column would be the truth value of C's statement, which is always true. Then the fourth column would be whether the truth value in the second column corresponds to B's type. This is correct if B is a knave. Similarly the fifth column would be whether the truth value in the third column corresponds to C's type, which is true if C is a knight. The sixth column would be the and of the fourth and fifth. Lines where the sixth column shows true are possible assignments.

Answer 4

To learn about how to use truth tables, and formal logic in general, to solve Smullyan's puzzles on Knights and Knaves you can read Smullyan's own "Logical Labyrinths" esp. chapter 8: Liars, Truth-tellers and propositional logic. (Publisher's link; Google Books link; Amazon link.)

If I am not mistaken, I think he also explains a bit about this stuff in "Forever undecided".

Answer 5

The problem is this:

We have three inhabitants A, B and C.

B said "A said "A is a knave"", and C said "B is a knave".

So the information we have is (if you read the first paragraph of the chapter I referred to in my previous answer and carefully follow the instructions):

$k_B \leftrightarrow (k_A \leftrightarrow \neg k_A)$

$k_C \leftrightarrow \neg k_B$

Your truth table for both formulas (as it is now written) is correct, you simply used A instead of $k_A$, but that's all. To know which are the possible situations under the givens, you just look for the rows that give simultaneously a value 1 for both formulas. These are the two rows with a 1 in the last column of your table.

What the table is telling you, then, is that there are only two possible situations. In both of them B is a knave and C is a knight. So that's true no matter the situation. Instead, you cannot tell what A is because A can either be a knight or a knave.