[Part 3] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles First example - Informal solution

In this post, we will solve our first Knights and Knaves puzzle in a systematic but informal way (the next post in this series will provide a formal proof of this solution).

For our first example, we will use the third puzzle in Chapter 3 (or the \(28^{th}\) 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:

A makes the following statement, "At least one of us is a knave."  What are A and B?

One informal, yet systematic approach to solving such a puzzle 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 two 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.]

Case 1: A is a knave

In this case, at least one of the two inhabitants (namely A) is a knave, and thus A's statement is true.

However, it is impossible for A, who is a knave, to make a true statement.

Therefore, this case is impossible.

We could stop here and infer that Case 2 must therefore hold. However, what if Smullyan's alter ego "Sneaky Ray" inserted an unsolvable puzzle into the book without the editor noticing it...

So, we must check that Case 2 is indeed possible!

Case 2: A is a knight 

Since A cannot lie, the statement "At least one of us is a knave." must be true. 

The only way to make it true is for B to be a knave (since A is not one).

Finally, Case 2 is indeed possible and implies that B is a knave.

Solution to the puzzle: A is a knight and B is a knave.

In the next post, we will use propositional logic to demonstrate that this solution is correct using a formal proof.