[Part 5] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #5 - With two natives and a two-step solution

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

[Note that we skipped Problem 5 in the book because it is very similar to the two previous problems in this series. We also skipped Problem 6 because it is quite a bit harder; we will devote the next couple of posts to that problem.]

Now, Problem 7 reads:

On another occasion I came across two natives A and B. I was curious to know of each one whether he was a knight or a knave and whether or not he was certified. They made the following statements:

A: "B is an uncertified knight." 

B: "A is a certified knave." 

I thought awhile and could solve part of the problem, but not all of it, because I had no way of knowing whether B was a knight or a knave. I later found out whether B was a knight or a knave, and then could solve the entire problem! What is the solution?

This problem involves two natives. We will use the proposition \(A\) (respectively, \(B\)) to represent the fact that A (respectively, B) is a knight. And we will use the proposition \(Ac\) (respectively, \(Bc\)) to represent the fact that A (respectively, B) is a certified.

Then we represent A's statement with the formula:

\(B\ \&\ {-Bc}\)

and B's statement with the formula:

\({-A}\ \&\ Ac\)

Therefore, the entire puzzle is represented by the formula \(\varphi\):

\((A \leftrightarrow (B\ \&\ {-Bc}))\ \&\ (B \leftrightarrow ({-A}\ \&\ Ac))\)

which represents the fact that each native made one of the statements.

We now build the truth table for \(\varphi\) as follows:

\(A\)	\(Ac\)	\(B\)	\(Bc\)	\(B\ \&\ {-Bc}\)	\(A \leftrightarrow (B\ \&\ {-Bc})\)	\({-A}\ \&\ Ac\)	\(B \leftrightarrow ({-A}\ \&\ Ac)\)	\(\varphi\)
\(F\)	\(F\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)
\(F\)	\(F\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)
\(F\)	\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)
\(F\)	\(T\)	\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)
\(F\)	\(T\)	\(T\)	\(T\)	\(F\)	\(T\)	\(T\)	\(T\)	\(T\)
\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(T\)	\(F\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(T\)	\(T\)	\(F\)	\(T\)	\(F\)	\(F\)	\(F\)	\(T\)	\(F\)
\(T\)	\(T\)	\(T\)	\(F\)	\(T\)	\(T\)	\(F\)	\(F\)	\(F\)
\(T\)	\(T\)	\(T\)	\(T\)	\(F\)	\(F\)	\(F\)	\(F\)	\(F\)

The only three rows in which \(\varphi\) is True are highlighted. 
In all three rows, A is a knave. So this part of the puzzle is solved.
However, B is a knave in the two blue rows and a knight in the green row. This is the part of the puzzle that Smullyan needed more info about.
If this new info were that B is a knave, then the two blue rows would be compatible with the puzzle statement and we could not narrow down the answer to a single solution.
Therefore, to meet the requirement of the puzzle that finding out the type of B would allow us to solve the entire puzzle, the new info must be that B is a knight.
This leaves us with a single row, namely the green one, according to which:

• A is a certified knave.
• B is a certified knight.

And that is the unique solution to this puzzle.

Of course, Smullyan's solution (given on pages 45-46) is the same as ours, but his informal reasoning is wordier than our truth table!