[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.