[Part 8] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles Second example

In this post, we will solve our second Knights and Knaves puzzle, both informally and formally.

For our second example, we will use the sixth puzzle in Chapter 3 (or the \(31^{st}\) puzzle overall) of Raymond Smullyan's 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles". As stated on page 21 of the 2011, paperback Dover Recreational Math edition [ISBN: 9780486481982], the puzzle reads:

[...] we have three people, A, B, C, each of whom is either a knight or a knave. A and B make the following statements:

A: All of us are knaves.
B: Exactly one of us is a knight. 

What are A, B, C?

As was the case for our first puzzle, our informal, yet systematic approach to solving it is to reason by cases. Since each inhabitant is either a knight or a knave, there are only two possible cases for each inhabitant.

Since this puzzle involves three inhabitants, we must pick one of them as a starting point. We'll start with A. [Exercise for the reader: Solve this puzzle with a case analysis based on B instead. It would be hard to start with C, since we do not have a statement from C on which to base our analysis.]

Case 1: A is a knight

If A were a knight, her statement would be true, which means that A (as well as B and C) would have to be a knave. Therefore, this case is impossible. 

Case 2: A is a knave [This case must hold] 

Since A lied, we know that at least one of the three inhabitants is a knight. Since A is a knave, it must be the case that one of B and C is a knight, or both B and C are knights.

To decide which, we turn to B's statement. 

Again, we consider two cases for B (as sub-cases of Case 2).

Case 2a: B is a knave (and A is still a knave)

In this case, B's statement must be false. Since it does not hold that "exactly one of us is a knight" and both A and B are knaves, it must be the case that C is also a knave (otherwise, C would be the only knight).

But then all three of them would be knaves, which would make A's statement true, which in turn would make A a knight. 

This sub-case is thus impossible.  

Case 2b: B is a knight (and A is still a knave)

In this case, B's statement must be true.

Since B is a knight, B must be the only knight. 

Therefore, C is a knave.

This fact does not contradict either of the statements.

Finally, only Case 2b is possible, which leads us to the only conclusion:

Solution to the puzzle: A and C are knaves, whereas B is a knight.

We will now formally prove that this solution is correct using the truth table approach that we described and applied (in Part 6) to the first puzzle.

We must start by translating the puzzle statement into propositional logic as follows.

First, A's statement becomes:

\(-A\ \&\ {-B}\ \&\ {-C}\)

Since this formula will become part of a longer formula, we will refer to it with the symbol \(A_{statement}\).

Now, the fact that A made this statement becomes:

\(A \leftrightarrow A_{statement}\)

Second, B's statement becomes:

\( (A\ \&\ {-B}\ \&\ {-C})\ |\ ({-A}\ \&\ {B}\ \&\ {-C})\ |\ ({-A}\ \&\ {-B}\ \&\ {C}) \) 

Since this formula is quite long, we will refer to it with the symbol \(B_{statement}\).

Now, the fact that B made this statement becomes:

\(B\leftrightarrow B_{statement} \)

Therefore, the complete, formal representation of the puzzle statement is the conjunction of the two statements, namely the formula \(\varphi\) defined as:

\(\varphi = (A \leftrightarrow A_{statement})\ \&\ (B\leftrightarrow B_{statement})\)

Finally, we build a truth table for this formula:

\(A\)	\(B\)	\(C\)	\(A_{statement}\)	\(A\leftrightarrow A_{statement}\)	\(B_{statement}\)	\(B\leftrightarrow B_{statement}\)	\(\varphi\)
\(F\)	\(F\)	\(F\)	\(T\)	\(F\)	\(F\)	\(T\)	\(F\)
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)	\(F\)
\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)

The third row in this table (highlighted above) proves that the only way to make \(\varphi\) True is to have the propositions \(A\), \(B\), and \(C\) assigned the truth values, \(F\), \(T\), and \(F\), respectively.

This confirms the correctness of our informal solution: A and C must be knaves, whereas B is a knight.