[Part 3] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #3 - Going backwards

For our third puzzle, we will solve Problem 3 on page 41 of the 2013 Dover edition [ISBN: 978-0486497051] of Raymond Smullyan's 2013 book entitled "The Gödelian Puzzle Book - Puzzles, Paradoxes & Proofs". 

This puzzle reads:

I once came across a native who made a statement from which I could deduce that he must be a[n] uncertified knave. What statement would work?

In the previous puzzles, we were given a statement S and were asked to determine the type and certified status of the speaker.

In such puzzles (with a native called A, say), we converted S to a logical formula \(\varphi\) and then built a truth table for the formula \(A \leftrightarrow \varphi\) to figure out which row(s) of the table contained the value True. 

This puzzle introduces a new twist: we are given the type and certified status of a native and must find a statement that the native could have made to allow us to make those deductions.

We must therefore find a formula \(\varphi\), corresponding to a statement S, that makes the native both uncertified and a knave.

More precisely, since only one native is involved, we call him A and build our table based on the usual two propositions \(A\) and \(Acert\).

The first two columns of the table list all of the possible combinations of truth values for these two propositions, while the last column contains the expected truth value of the formula representing the native's statement, yielding the table:

\(A\)	\(Acert\)	\(\varphi\) = ?	\(A \leftrightarrow \varphi\)
\(F\)	\(F\)		\(T\)
\(F\)	\(T\)		\(F\)
\(T\)	\(F\)		\(F\)
\(T\)	\(T\)		\(F\)

Note that the only True value in the last column represents the fact that A must be a knave (so \(A\) is False) and uncertified (so \(Acert\) is False).

Solving the puzzle now means finding a formula \(\varphi\) that correctly completes this table.

Since the main connective in \(A \leftrightarrow \varphi\) is a biconditional, \(\varphi\) must have the same truth value as \(A\) in the first row (where the biconditional is true) and a different truth value from \(A\) in the last three rows (where the biconditional is false).

Therefore, the almost-full table must look like:

\(A\)	\(Acert\)	\(\varphi\) = ?	\(A \leftrightarrow \varphi\)
\(F\)	\(F\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(F\)	\(F\)

Finally, the table will be complete (and the puzzle solved!) once we have found a formula \(\varphi\) that works:

\(A\)	\(Acert\)	\(\varphi\) = ?	\(A \leftrightarrow \varphi\)
\(F\)	\(F\)	\(F\)	\(T\)
\(F\)	\(T\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(F\)	\(F\)

In the most general case, we can assume that \(\varphi\) will depend on the two propositions in this puzzle, namely \(A\) and \(Acert\).
Since these two propositions can be combined into a single formula using conjunction, disjunction, conditional, biconditional, etc., we need to pick one of these logical connectives. This choice will determine the type of statement made by the native A.
Since Smullyan's answer is a conjunction, we will pick a different kind of statement, say, a conditional.
Finally, we consider possible ways to combine \(A\) and \(Acert\) with a conditional and optional negations, to get the table:

\(A\)	\(Acert\)	\({A} \rightarrow {Acert}\)	\({-A} \rightarrow {Acert}\)	\({A} \rightarrow {-Acert}\)	\({-A} \rightarrow {-Acert}\)	Target
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(T\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(T\)	\(T\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)

We observe that none of the conditionals match the target column.

However, the next-to-last column contains, on each row, the negation of the value in the target column:

\(A\)	\(Acert\)	\({A} \rightarrow {Acert}\)	\({-A} \rightarrow {Acert}\)	\({A} \rightarrow {-Acert}\)	\({-A} \rightarrow {-Acert}\)	Target
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(T\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(F\)	\(T\)	\(T\)	\(T\)	\(F\)
\(T\)	\(T\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)

Therefore, a possible statement by native A could he encoded with the formula:

\({-({-A} \rightarrow {-Acert})}\)
which could have come from the English statement: 

 "Do not believe anyone who says that, if I am a knave, then I must be uncertified."

This formulation being a bit heavy, we could use the fact that the formula:

\({-({-A} \rightarrow {-Acert})}\)

is logically equivalent to the disjunction:

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

which in turn could have come from the English statement:

"Anyone who says that I am a knight or uncertified is a liar."
Note that the solution given by Smullyan on page 44 of his book is a more concise conjunction that is equivalent to both formulas above.

[Part 3] Raymond Smullyan's Knights, Knaves, and Normals puzzles Representing statements made by islanders

Now that we understand the advantages of using predicates and quantifiers, we can represent the fact that each and every inhabitant of this island must have exactly one type using the following axioms:

\(∀x\ (Kni(x)\ |\ Kna(x)\ |\ Nor(x))\)

\(∀x\ (Kni(x) \rightarrow (-Kna(x)\ \&\ {-Nor(x)}))\)

\(∀x\ (Kna(x) \rightarrow (-Kni(x)\ \&\ {-Nor(x)}))\)

\(∀x\ (Nor(x) \rightarrow (-Kni(x)\ \&\ {-Kna(x)}))\)

While this is knowledge about the island world itself that is shared by all puzzles, we now turn our attention to the statements that islanders make as part of each specific puzzle.

First, the contents of each statement can also be represented with the same predicates and constants. For example, the statement "If A is a knave, then B is normal", is represented by the following formula of our first-order predicate calculus:

\(Kna(A) \rightarrow Nor(B)\)

In general, we will represent any such statement using some formula \(\varphi\). 

Second, how do we represent the fact that a specific inhabitant made that statement?

Back on the other island, when propositional logic was adequate, we used the following representation principle for statements.

---

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

---

Refer back to this earlier post for a discussion of this principle. Briefly: back then, we saw that \(P\) (representing the fact that P is a knight) has the same truth value as \(S\) because:

• If \(P\) is true, then P is a knight and all of its statements, including S, are true.
• If \(P\) is false, then P is a knave and all of its statements, including S, are false.

If two formulas \(P\) and \(S\) always have the same truth value, we say that they are equivalent, which can be represented in propositional logic using the formula:

\(P \leftrightarrow S\)

This approach will not work in our predicate calculus because:

• each islander is now represented by a constant, not a true/false proposition, and
• there is now a third type (i.e., normal) to consider.

However, we can get around these two issues and extend the applicability of our representation principle to predicate logic using a case-by-case reasoning similar to the two-type scenario of the previous island. 

Note that the formula:

\(P \leftrightarrow S\)

is equivalent to:

\((P\ \&\ S)\ |\ ({-P}\ \&\ {-S})\)

reflecting the two cases discussed above, that is, P being either a knight or a knave.

To extend this approach to our new island with three types, we simply need to add the third case.

Assume that person P made statement S. 

First, we will represent statement S with a predicate logic formula \(\varphi\).

Second, we will consider three cases:

• If P is a knight, then each one of P's statements, including S, is true; this is represented by the formula: \(Kni(P)\ \&\ \varphi\)
• If P is a knave, then each one of P's statements, including S, is false; this is represented by the formula: \(Kna(P)\ \&\ {-\varphi}\)
• If P is normal, then each one of P's statements, including S, is either true or false; since we have no information on the truth value of S, this case is represented by the formula: \(Nor(P)\).

In conclusion, when using predicate calculus to represent statements made by inhabitants of our new island, we will apply the following principle.

---

 Representation principle for Knights, Knaves, and Normals puzzles

For any person P living on this island and any statement S
(with P represented by constant \(P\) 
and S represented by formula \(\varphi\)),
the fact that P said S
will be represented by the formula:

\((Kni(P)\ \&\ \varphi)\ |\ (Kna(P)\ \&\ {-\varphi})\ |\ Nor(P)\)

---

Coming back to our earlier example, the fact that inhabitant C made the statement "If A is a knave, then B is normal" would be represented by the following formula of first-order predicate calculus:

\((Kni(C)\ \&\ (Kna(A) \rightarrow Nor(B)))\ |\ (Kna(P)\ \&\ {-(Kna(A) \rightarrow Nor(B))})\ |\ Nor(P)\)