Logic – Solving Spy, Liar, and Truthteller Puzzle

logicpuzzle

I watched a recent video from MindYourDecisions. One of its problems is:

ALice, Bob, and Charlie are one of each type: a truth-teller (always tell a truth), a liar (always lies), and a spy (can lie or tell a truth). Alice says she is not a truth teller; Bob says he is not a spy; and Charlie says he is not a liar. What type is Charlie?

It reminds me of Knight and Knaves puzzle. I wish to solve this problem symbolically.

I introduce three propositional variables: $A$, $B$, and $C$. $A$ represents "Alice is a truth-teller," $B$ represents "Bob is a truth-teller" and $C$ represents "Charlie is a truth-teller." I am not sure how to translate the problem statement into symbols. I think it would be:

$$A\longleftrightarrow\lnot A$$
$$B\longleftrightarrow\lnot (B\lor\lnot B)$$
$$C\longleftrightarrow\lnot C$$

They look contradictory… Any better ideas?

Best Answer

You can do it with propositional logic ... but it's not as straightforward as with the Knight and Knaves puzzles.

OK, so let's define a bunch of atomic statements:

$A_T$: Alice is a truth-teller

$A_S$: Alice is a spy

$A_L$: Alice is a liar

$B_T$: Bob is a truth-teller

$B_S$: Bob is a spy

$B_L$: Bob is a liar

$C_T$: Charlie is a truth-teller

$C_S$: Charlie is a spy

$C_L$: Charlie is a liar

Now, Alice is either a truth-teller, spy, or liar, so we have all of the following statements:

  1. $A_T \leftrightarrow (\neg A_S \land \neg A_L)$

  2. $A_S \leftrightarrow (\neg A_T \land \neg A_L)$

  3. $A_L \leftrightarrow (\neg A_S \land \neg A_T)$

Same with Bob and Charlie:

  1. $B_T \leftrightarrow (\neg B_S \land \neg B_L)$

  2. $B_S \leftrightarrow (\neg B_T \land \neg B_L)$

  3. $B_L \leftrightarrow (\neg B_S \land \neg B_T)$

  4. $C_T \leftrightarrow (\neg C_S \land \neg C_L)$

  5. $C_S \leftrightarrow (\neg C_T \land \neg C_L)$

  6. $C_L \leftrightarrow (\neg C_S \land \neg C_T)$

Also, when it says: "Alice, Bob, and Charlie are one of each type" I assume they mean that there is 1 truth-teller, 1 spy, and 1 liar between them. So, we can also add:

  1. $A_T \leftrightarrow (\neg B_T \land \neg C_T)$

  2. $A_S \leftrightarrow (\neg B_S \land \neg C_S)$

  3. $A_L \leftrightarrow (\neg B_L \land \neg C_L)$

  4. $B_T \leftrightarrow (\neg A_T \land \neg C_T)$

  5. $B_S \leftrightarrow (\neg A_S \land \neg C_S)$

  6. $B_L \leftrightarrow (\neg A_L \land \neg C_L)$

  7. $C_T \leftrightarrow (\neg A_T \land \neg B_T)$

  8. $C_S \leftrightarrow (\neg A_S \land \neg B_S)$

  9. $C_L \leftrightarrow (\neg A_L \land \neg B_L)$

OK, now for the statements they give. Alice says "I am not a truth-teller"

This means that the statement is true if Alice is a truth teller, and the statement is false if Alice is a liar:

  1. $A_T \to \neg A_T$

  2. $A_L \to A_T$

Bob says: "I am not a spy" becomes:

  1. $B_T \to \neg B_S$

  2. $B_L \to B_S$

Charlie: "I am not a liar":

  1. $C_T \to \neg C_L$

  2. $C_L \to C_L$

OK, so now let's infer (I'll use a mix of fairly standard inference and equivalence rules)

  1. $\neg A_T \lor \neg A_T$ (Implication 19)

  2. $\neg A_T$ (Idempotence 25)

  3. $\neg A_L$ (Modus Tollens 20,26)

  4. $\neg A_T \land \neg A_L$ ($\land$ Intro 26,27)

  5. $A_S$ ($\leftrightarrow$ Elim 2,28)

  6. $\neg B_S \land \neg C_S$ ($\leftrightarrow$ Elim 11,29)

  7. $\neg B_S$ ($\land$ Elim, 30)

  8. $\neg B_L$ (Modus Tollens, 22,31)

  9. $\neg B_S \land \neg B_L$ ($\land$ Intro 31,32)

  10. $B_T$ (\leftrightarrow Elim 4,33)

  11. $\neg A_T \land \neg C_T$ ($\leftrightarrow$ Elim 13,34)

  12. $\neg C_S$ ($\land$ Elim 30)

  13. $\neg C_T$ ($\land$ Elim 35)

  14. $\neg C_S \land \neg C_T$ ($\land$ Intro 36,37)

  15. $C_L$ ($\leftrightarrow$ Elim 9,38)

Related Question