[Part 1] Raymond Smullyan's Knights, Knaves, and Normals puzzles Limitations of propositional logic

Raymond Smullyan introduced the Knights and Knaves puzzles in chapter 3 of his 1978 book entitled "What Is the Name of This Book?: The Riddle of Dracula and Other Logical Puzzles".

We discussed these puzzles at length in an earlier series.

In this series, we discuss  the second kind of puzzle that Smullyan introduced later in that same chapter, called the "Knights, Knaves, and Normals" puzzles, starting on page 23 of the 2011, paperback Dover Recreational Math edition [ISBN: 9780486481982].

On this new island, there are three types of inhabitants: "knights, who always tell the truth; knaves, who always lie; and normal people, who sometimes lie and sometimes tell the truth."

The existence of "normals" makes the puzzle a bit more complex and thus more rewarding to solve. It also illustrates weaknesses of propositional logic, as we used it in our previous series.

Back then, when solving the knights and knaves puzzles (without normals), we used a single proposition for each inhabitant involved in the puzzle. For example, the proposition \(A\) represented the fact that the inhabitant whose name is A was a knight.

It was very convenient that each inhabitant on that island always was of one type and that there were exactly two possible types: knight or knave. In this scenario, proving that someone is not a knight was the same as proving that this person was a knave, and vice versa.

In logical terms, a single proposition was enough to represent the type an inhabitant: 

• if \(A\) is true, then person A is a knight;
• otherwise (that is, when \(A\) is false, or equivalently, \(-A\) is true), person A is a knave.

Things are not so neat on the new island because of the third possible type (normal). In this scenario, proving that someone is not a knight is NOT the same as proving that this person is a knave. Instead, it proves that this person is a knave or a normal.

More generally, disproving one type is not enough to establish a person's type.

This difficulty also has consequences for the way that puzzles are represented in formal logic. 

First difficulty

On the old island, there was no need to include, as axioms, formulas of the form:

\(A\ |\ {-A}\)

to represent the fact that A must be a knight or a knave, since this formula is a tautology (i.e., it is always true) in any logic that follows the law of excluded middle, one of the three laws of thought.

On the new island, this law still applies. So, if we know that \(A\) is false, we can infer that \(-A\) is true. However, \(-A\) now means that "A is not a knight", which is not the same as "A is a knave" any longer.

Instead, \(-A\) means that "A is a knave or a normal."

But then, we cannot use the proposition \(A\) (nor its negation) to represent "A is knave" or "A is (a) normal".

We are forced to introduce new propositions to represent the separate facts that "A is knave" or "A is normal".

Let's assume we use the three propositions \(AKni\), \(AKna\), and \(ANor\) to represent the facts that "A is a knight", "A is a knave", and "A is normal", respectively.

Now, to accurately represent the facts of life on the new island, we must add axioms of the form:

\(AKni \rightarrow (-AKna\ \&\ {-ANor})\)

\(AKna \rightarrow (-AKni\ \&\ {-ANor})\)

\(ANor \rightarrow (-AKni\ \&\ {-AKna})\)

Second difficulty

The three previous axioms are needed to represent the fact that A has (at most) one type, and cannot be, for example, both a knight and a knave (which follows from the first axiom above).

To be clear, the law of excluded middle still applies: it is still true that either A is a knight or A is not a knight. Unfortunately, knowing that A is not a knight does not give us any information about whether A is a knave or a normal.

Worse, since we use three distinct propositions for the three possible types of A, there is no connection at all among these three variables in propositional logic.

On the old island, the two types (i.e., Knight and Knave) were automatically connected (as opposites), since one being true automatically meant that the other one was false (and vice versa). It was a given that exactly one of them had to be true (again, by the law of excluded middle).

On the new island, the connection among the three types is lost in the representation. The propositions \(AKni\) and \(AKna\) are no more (semantically) related than if they were named \(P\) and \( Q\), respectively, which is to say that they are NOT semantically related at all.

For this reason, we must now explicitly represent this semantic relationship with the new axiom:

\(AKni\ |\ AKna\ |\ ANor\)

which encodes the fact that person A's type must be one of the three possible types.

More precisely, this axiom states that A must be of at least one of these types, whereas the three axioms introduced earlier together state that A must be of at most one of these types.

To recap, we need three propositions and four axioms to represent the possible types for person A.

What about the other inhabitants of the island?

Third difficulty

All of the propositions and axioms described so far pertain to person A only. If the puzzle involves other inhabitants of the new island, we are going to need a new set of three propositions and four axioms to represent the possible types of each one of them.

For example, for person B, we would need the propositions \(BKni\), \(BKna\), and \(BNor\) and the axioms:

\(BKni\ |\ BKna\ |\ BNor\)

\(BKni \rightarrow (-BKna\ \&\ {-BNor})\)
\(BKna \rightarrow (-BKni\ \&\ {-BNor})\)

\(BNor \rightarrow (-BKni\ \&\ {-BKna})\)

This representation scheme may quickly get out of hand.

In the next post, we will use these limitations of propositional logic to motivate the use of first-order logic that involves predicates and quantifiers.