[Part 9] Raymond Smullyan's Certified Knights and Knaves puzzles Puzzle #6 - (At least) nine distinct solutions

Recall our sixth puzzle:

On another particularly interesting occasion I came across two natives A and B each of whom made a statement such that I could infer that at least one of them must be an uncertified knight, but there was no way to tell which one it was. From neither statement alone could one have deduced this.

What two statements would work? [This problem is not easy!]

and the nine solutions that our JavaScript program found:

Solution #1            Solution #4           Solution #7 
 A <-> (A | Bc)         A <-> (B | -A)        A <-> (-Bc | -A)
 B <-> (-B | -Ac)       B <-> (-Bc | -Ac)     B <-> (A & Ac) 

Solution #2            Solution #5           Solution #8
 A <-> (Ac | Bc)        A <-> (B | -Ac)       A <-> (-Bc | -A)
 B <-> (-B | -Ac)       B <-> (-Bc | -A)      B <-> (Ac | B)

Solution #3            Solution #6           Solution #9
 A <-> (B & Bc)         A <-> (-B | -Ac)      A <-> (-Bc | -B)
 B <-> (-Ac | -A)       B <-> (A | -Bc)       B <-> (A & Ac)

Solution #3 is the one that Smullyan discusses for this puzzle on page 45 of his book, namely:

 A: "B is a certified knight."
 B: "A is not a certified knight."

Note that B's statement can be more directly translated into propositional logic as:

B <-> -(Ac & A)

which, by De Morgan's law, is equivalent to the formula output by our program, namely:

B <-> (-Ac | -A)

Note that Solution #9 is equivalent to Solution #3 if we switch the names of the two natives.

These two solutions are the only ones in which each native only talks about the other native.

In Solution #7, B only talks about A but A describes both natives:

 A: "Either I am a knave or B is uncertified."
 B: "A is a certified knight."

In all other solutions, each native refers to both of them.

When translating these solution formulas into English statements, we can vary the grammatical structure using the following logical equivalences:

1. "-x | -y" is equivalent to "-(x & y)"
2. "-x | y" is equivalent to "x -> y"
3. "x | y" is equivalent to "--x | y" is equivalent to "-x -> y"

B's statement in Solution #3 discussed above is an example of the first equivalence.

We can use the second equivalence to translate A's statement in Solution #4:

 A: "If I am a knight, then so is B."

 B: "At least one of us is uncertified."

Note that we used the commutativity of disjunction when translating A's statement.

We can use the third equivalence to translate A's statement in Solution #1:

 A: "If I am a knave, then B is certified."

 B: "If I am a knight then A is uncertified."

To conclude this discussion, it is worth emphasizing that all of these solutions are logically distinct.

Recall that each solution (i.e., each formula \(\varphi\)), is encoded by an integer (see the JavaScript program that we discussed earlier) and that the program removes duplicates.

This means that, in addition to the many ways to express them in grammatically correct English, these solutions ALL describe different scenarios.

This can be demonstrated easily by building a truth table for all of these solutions:

\(A\)	\(Ac\)	\(B\)	\(Bc\)	\(S1\)	\(S2\)	\(S3\)	\(S4\)	\(S5\)	\(S6\)	\(S7\)	\(S8\)	\(S9\)
\(F\)	\(F\)	\(F\)	\(F\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(F\)	\(F\)	\(F\)	\(T\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(F\)	\(F\)	\(T\)	\(F\)	✓	✓	✓	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	only B
\(F\)	\(F\)	\(T\)	\(T\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(F\)	\(T\)	\(F\)	\(F\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(F\)	\(T\)	\(F\)	\(T\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(F\)	\(T\)	\(T\)	\(F\)	\(\)	\(\)	✓	\(\)	\(\)	✓	\(\)	\(\)	\(\)	only B
\(F\)	\(T\)	\(T\)	\(T\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(T\)	\(F\)	\(F\)	\(F\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	✓	✓	✓	only A
\(T\)	\(F\)	\(F\)	\(T\)	\(\)	\(\)	\(\)	\(\)	✓	\(\)	\(\)	\(\)	✓	only A
\(T\)	\(F\)	\(T\)	\(F\)	✓	\(\)	\(\)	✓	✓	✓	\(\)	✓	\(\)	both A and B
\(T\)	\(F\)	\(T\)	\(T\)	✓	✓	✓	✓	\(\)	✓	\(\)	\(\)	\(\)	only A
\(T\)	\(T\)	\(F\)	\(F\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(T\)	\(T\)	\(F\)	\(T\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)
\(T\)	\(T\)	\(T\)	\(F\)	\(\)	\(\)	\(\)	✓	✓	\(\)	✓	✓	✓	only B
\(T\)	\(T\)	\(T\)	\(T\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)	\(\)

In the table above, in each solution column, I used a checkmark instead of a True value and omitted the False values in order to make the relevant cases easier to pick out.

It is now easy to check that no two solutions pick out the same scenario.

For example, solutions 1, 4, 5, 6, and 8 make it possible for both natives to be uncertified knights, but none of the other solutions do.

Even solutions that allow exactly one native to be an uncertified knight are all distinct:

• In Solution 2, the "other one" is either an uncertified knave (A) or a certified knight (B).
• Solution 3 differs from solution 2 in that it allows for an extra possibility, namely for the other one (A) to be a certified knave.
• Solution 7 only allows for two possibilities that are different from the ones in Solution 2.
• Solution 9 allow for three possibilities that do not overlap with those in Solution 3.

Finally, there is one aspect of the puzzle that we have not discussed yet, namely, the condition that:

"From neither statement alone could one have deduced this."

Homework:

• Do all nine solutions above satisfy this extra requirement?
• Can you modify our program to check this automatically?