[Part 2] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #2

For our second puzzle, we will solve Problem 2 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:

On another occasion I came across a native who said, "I am an uncertified knight." Is this the same situation as the last problem? Is it now possible to tell whether or not he is a knight? Can one tell whether or not he is certified?

Recall the "last puzzle", that is, our puzzle #1:

I once came across a native of the island who said, "I am not a certified knight." Was he a knight or a knave? Was he certified?

Neither one of these puzzles is hard but, to answer the first question:

Is this the same situation as the last problem?

no, this is not the same as the first puzzle. In fact, these puzzles highlight why we need to be careful with the meaning of negation in English statements.

The old statement, "I am not a certified knight.", means that it is not the case that I am both a knight and certified.

In contrast, the new statement, "I am an uncertified knight.", means that I am definitely both a knight and not certified.

The logic formulas are therefore different, namely:

-(A & Acert) [Puzzle #1]

versus

A & -Acert [Puzzle #2]

assuming again that the native in the puzzle is referred to as A and that the propositions A and Acert mean "A is a knight" and "A is certified", respectively.

I trust that you can solve this second puzzle informally. Smullyan's answer is a simple case analysis given on page 44.

We can solve it formally, by building a truth table, as follows:

\(A\)	\(Acert\)	\(A\ \&\ {-Acert}\)	\(A \leftrightarrow (A\ \&\ {-Acert})\)
\(F\)	\(F\)	\(F\)	\(T\)
\(F\)	\(T\)	\(F\)	\(T\)
\(T\)	\(F\)	\(T\)	\(T\)
\(T\)	\(T\)	\(F\)	\(F\)

Note that the formula in the last column is the representation of the native's statement, according to our usual representation principle.

Since the top three rows contain True, this puzzle has three solutions:

1. A is an uncertified knave (row 1)
2. A is a certified knave (row 2)
3. A is an uncertified knight (row 3)

So the answers to the puzzle's questions:

• Is it now possible to tell whether or not he is a knight? 
• Can one tell whether or not he is certified?

are both negative!

If we did not want to build the truth table manually, we could have used Mace4 with the following input:

Mace4's output, namely:

proves that the three solutions we identified earlier are correct.

Finally, we could have used Prover9 to prove that our solution is correct.

The solution to the puzzle could be represented as:

(-A & -Acert) | (-A & Acert) | (A & -Acert)

as the disjunction of the three possible scenarios.

However, it would be more concise to state, equivalently, that the last scenario is NOT possible, namely:

-(A & Acert)

or equivalently:

-A | -Acert

(by one of De Morgan's laws), which we feed as a goal to Prover9:

to get the following proof by contradiction:

This is a short proof indeed!