Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Your calculation of F1 is wrong, and I also think you don't need it (why assume that there must be a knight?). Besides, you can reason that B must be lying (since A must have said he's a knight), and so C must be telling the truth. –  Yuval Filmus Jan 5 '11 at 7:13

6 Answers 6

up vote 0 down vote accepted
+50

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.

share|improve this answer
    
I suspect all are clear that we don't know what A said, we only know what he could've said and what couldn't. Because if he would have said something like "I have bananas in my ears", we wouldn't even consider his claims, or even would be unable to answer what B and C are. –  Yasir Arsanukaev Jan 7 '11 at 14:44
    
That is true, but we know the truth value of what he said matches his type. This is why I said F1 should be A. If you follow it through, this is not contributing to the solution at all, because we don't know what A is at the end. I was trying to stay in the spirit of your table. The heart of the other arguments that B is a knave comes out in your table under F2 when you say $B \leftrightarrow (A \leftrightarrow \neg A)$. As $(A \leftrightarrow \neg A)$ is always false, this requires B to be false. –  Ross Millikan Jan 7 '11 at 15:00
    
A could have said a lot of things. The one thing he cannot have said is "I am a knave", which marks B as a liar. If B claimed A said "I have bananas in my ears", even observing no bananas in A's ears would only tell us that (at least) one is a liar. –  Ross Millikan Jan 7 '11 at 15:02
    
I just got rid of $F1$ in the question, it has actually been put there because of one of the next issues after #26 (this one) stating that there would be at least one knight amongst inhabitants. Nothing seems to confuse me any more. –  Yasir Arsanukaev Jan 7 '11 at 15:22
    
@Yasir Arsanukaev: Looking at your table again, I see that you put the equivalence I said you should have in G into the F1 and F2 columns. So F1 represents "B spoke in conformance with his type", not "B told the truth". In that case your G is correct. I will edit my response. –  Ross Millikan Jan 7 '11 at 17:58

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!

share|improve this answer
    
The book has explanation similar to yours. I'd like to know how the truth table should look like though, so that I know what I'm missing besides $F1$ is not needed as @Yuval and you already mentioned. –  Yasir Arsanukaev Jan 5 '11 at 7:35
    
I edited to indicate that your calculation of F1 is incorrect. It's still, in my opinion, not a particularly fruitful way to approach this problem. –  Chas Brown Jan 5 '11 at 7:40

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.

share|improve this answer
    
Actually, I think we are only given $k_B \boxed\rightarrow (k_A \leftrightarrow \neg k_A)$, but logically that is of course equivalent. –  Marnix Klooster Feb 4 at 21:19

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".

share|improve this answer

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.

share|improve this answer

Here is a solution that does not use truth tables, but instead we calculate the solution.

Let's write $\;T(x)\;$ for "$\;x\;$ is a knight", so that $\;\lnot T(x)\;$ stands for "$\;x\;$ is a knave": I chose $\;T\;$ as a mnemonic for 'always speaks the Truth'.

The 'axiom' underlying many of these puzzles is: \begin{align} \newcommand{\says}[2]{#1\text{ says }\unicode{x201C}#2\unicode{x201D}}(0) \;\;\; & \says{x}{\phi} \;\Rightarrow\; (T(x) \;\equiv\; \phi) \\ \newcommand{\cansay}[2]{#1\text{ can say }\unicode{x201C}#2\unicode{x201D}} \end{align}

Formalizing the story, you are given that \begin{align} (1) \;\;\; & \says{B}{\says{A}{\lnot T(A)}} \\ (2) \;\;\; & \says{C}{\lnot T(B)} \\ \end{align}

From $(1)$ we can derive \begin{align} & \says{B}{\says{A}{\lnot T(A)}} \\ \Rightarrow & \;\;\;\;\;\text{"by $(0)$"} \\ & T(B) \;\equiv\; \says{A}{\lnot T(A)} \\ \Rightarrow & \;\;\;\;\;\text{"weaken -- otherwise we cannot apply $(0)$ again"} \\ & T(B) \;\Rightarrow\; \says{A}{\lnot T(A)} \\ \Rightarrow & \;\;\;\;\;\text{"by $(0)$ and transitivity"} \\ & T(B) \;\Rightarrow\; (T(A) \;\equiv\; \lnot T(A)) \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ (1') \;\;\; \phantom{\equiv} & \lnot T(B) \\ \end{align} In other words, $\;B\;$ is a knave.

From $(2)$ we can now derive \begin{align} & \says{C}{\lnot T(B)} \\ \Rightarrow & \;\;\;\;\;\text{"by $(0)$"} \\ & T(C) \;\equiv\; \lnot T(B) \\ \equiv & \;\;\;\;\;\text{"by $(1')$; simplify"} \\ (2') \;\;\; \phantom{\equiv} & T(C) \\ \end{align}

In other words, $\;C\;$ is a knight.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.