Solving spy, liar, and truthteller puzzle using propositional calculus

Question

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?

Answer 1

It's not so straightforward to formalize this with propositional logic (But it's possible as @Bram28 answered). In your attemption, you made $A,B,C$ represents that Alice, Bob, Charlie is a truth-teller respectively while the problem is that whether someone is a lair or a spy cannot simply expressed in terms of if they are a truth-teller or not. That Bob and Charlie's words cannot be expressed within this setting.

Let $A,B,C$ be the collection of all possible sentences said by Alice, Bob, Charlie respectively. Given that

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

\begin{align*} (\forall \varphi\in S,\varphi)\lor(\forall\varphi\in S,\lnot\varphi)\lor(\exists\varphi\in S,\varphi\land\exists\varphi\in S,\lnot \varphi)\tag{1} \end{align*}

where $S=A,B$ or $C$.

Alice: $\color{blue}{\lnot(\forall \varphi\in A,\varphi)}$ (I'm not a truth-teller.)

Bob: $\lnot(\exists\varphi\in B,\varphi\land\exists\varphi\in B,\lnot\varphi)$ (I'm not a spy.)

Charlie: $\lnot(\forall \varphi\in C,\lnot \varphi)$ (I'm not a lair.)

1. Suppose Alice is a lair i.e. $\forall\varphi\in A,\lnot \varphi$ that anything said by Alice must be false gives \begin{align*} \lnot\color{blue}{\lnot(\forall \varphi\in A,\varphi)}\equiv\forall\varphi\in A,\varphi \end{align*} However, that says Alice is a truth-teller, a contradiction. Alice is not a lair.

2. Suppose Alice is a truth-teller i.e. $\forall\varphi\in A,\varphi$ that anything said by Alice must be true gives $$\color{blue}{\lnot(\forall \varphi\in A,\varphi)}$$ However, that says Alice is not a truth-teller, a contradiction. Alice is not a truth-teller.

By $(1)$ have $\exists\varphi\in A,\varphi\land \exists\varphi\in A,\lnot \varphi$ that Alice is a spy. Follows Bob is a truth-teller and Charlie is a lair.

Answer 2

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:

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

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

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

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

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

9. $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:

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

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

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

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

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

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

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

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

18. $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:

19. $A_T \to \neg A_T$

20. $A_L \to A_T$

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

21. $B_T \to \neg B_S$

22. $B_L \to B_S$

Charlie: "I am not a liar":

23. $C_T \to \neg C_L$

24. $C_L \to C_L$

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

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

26. $\neg A_T$ (Idempotence 25)

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

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

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

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

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

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

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

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

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

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

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

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

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