[Part 2] A Propositional Logic approach to Raymond Smullyan's Knights and Knaves puzzles From puzzles to logical formulas

In this post, we discuss how to translate Knights and Knaves puzzles into the formalism of propositional logic, so that, in upcoming posts, we will be able to solve them in a formal way.

As a simple example for this post, we will consider the following puzzle statement:

A said "If B is a knave, then I am a Knight."

If needed, now would be a good time to review the basics of propositional logic given in the first post in this series.

Representing the puzzle in propositional logic

Using the formalism of propositional logic, we can represent the statement "A is a knight." with the proposition \(A\). The choice of this letter for the proposition is completely arbitrary but easy to remember: proposition \(A\) is about person A and it is true when A always tells the truth (i.e., when A is a knight).

Then the negation of \(A\), that is, \(-A\), represents the fact that A is not a knight. Since each inhabitant can only be a knight or a knave, \(-A\) represents the statement "A is a knave.".

Similarly, and for the same reason, we will use the proposition \(B\) to represent the statement "B is a knight." and the formula \(-B\) to represent the statement "B is a knave."

Now, we need to represent A's statement "If B is a knave, then I am a Knight.", in which "I" refers to "A".

This is the conditional \(-B \rightarrow A\).

However, we may NOT add this conditional by itself to our problem statement because we do not know whether or not this formula is true. All we know is that the inhabitant named A said it.

Instead, we must represent the fact that A is the one who made that statement.

Generally speaking, we need a way to represent the fact that person P made statement S. How should we do this? One simple approach is as follows.

Since P is either a knight or a knave, we have two cases to consider: if P is a knight, then everything P says is true, including S. If P is a knave, then everything P says is false, including S.

In other words, the truth value of the proposition \(S\) is always the same as the truth value of the proposition \(P\). They are either both true or both false. 

In propositional logic, we represent this fact with the formula \(P \leftrightarrow S\).

This is the general approach that we will use to represent statements by inhabitants of the island. Hence the following general rule.

---

 Representation principle for Knights and Knaves puzzles

For any person P living on this island and any statement S,
the fact that P said S
will be represented by the formula:

\(P \leftrightarrow S\)

---

Applying this principle to A's statement in our example, we get the formula:

\(A \leftrightarrow (-B \rightarrow A)\)

which is all that we need to represent our puzzle statement in propositional logic.

Solving puzzles with proofs in propositional logic

Next, we will focus on how to use formal reasoning in propositional logic to solve such puzzles, that is, to infer whether A and B are knights or knaves based only on the information given in the puzzle. 

To solve this particular puzzle, we must:

• prove that either \(A\) or \(-A\) is true (and similarly for proposition \(B\)),
• assuming only that \(A \leftrightarrow (-B \rightarrow A)\).

In other words, starting from \(A \leftrightarrow (-B \rightarrow A)\) as an assumption, we must prove that exactly one of the four following formulas is true:

1. \(A\ \&\ B\)
2. \(-A\ \&\ B\)
3. \(A\ \&\ {-B}\)
4. \(-A\ \&\ {-B}\)

In upcoming posts, we will discuss how to solve such puzzles both informally and formally.