Raymond Smullyan's Knights and Knaves

Bruce Ediger

Raymond Smullyan, my favorite mathematician, posed a large number of questions involving the Isle of Knights and Knaves. Inhabitants are either knights, who always tell the truth, or knaves, who always tell falsehoods.

One of the best Knight and Knave problems is Og and Bog from Smullyan’s book Logical Labyrinths

Og and Bog are brothers living on the Isle of Knights and Knaves, and one of them is the chief.

  • Og says: Bog is the chief and he is a knave!
  • Bog says: Og is not the chief, but he is a knight.

Which one is the chief?

When you think about this problem, it seems hopelessly tangled. Bog says two things about Og, and Og says two things about Bog. Og says Bog is the chief, and Bog says Og is not chief, so both brothers seem to agree that Bog is the chief. But there’s more, since we don’t know if either brother is a knight or a knave. Each brother says a complicated statement about the other brother, and the interpretation of both statements depends on the other brother’s category (knight or knave).

Smullyan has a clever solution in the back of Logical Labyrinths, but I’m going to whittle the puzzle down to a size I can hold in my head, because I like procedures to solve puzzles. Having a procedure keeps me from making mistakes, and developing the procedure helps me understand the underpinnings of all problems.

First, collapse some of the English into short phrases:

  • Use Kx to mean “x is a knight”
  • Use Cx to mean “x is the chief”.

I’ll use & for “and”. When Og says “Bog is a knave”, I can write “Bog is not a knight”. I’ll use ~ to make the next thing “not”. The word “but” in the English versions of the brothers’ statements is semantically equivalent to “and”.

I can write the statements symbolically as:

  • (CBog & ~KBog)
  • (~COg & KOg)

At this point, I’ve got no idea if either statement is true or false. If both Og and Bog are knaves, both statements are false. If both Og and Bog are knights, both statements are true. If Og is one type, and Bog another, we’ve got a mix of true and false statements. There’s no way to tell.

I can logically equate (=) what either Og or Bog says with the assertion that Og or Bog is a knight. If Og is a knight, what he says is true. If Og is a knave, what he says is false. Either way, saying “Og is a knight” logically equates with whatever Og says. Now I have two, slightly more complicated, statements, both of which are known to be true.

  • KOg = (CBog & ~KBog)
  • KBog = (~COg & KOg)

That’s really the key to solving knight and knave puzzles. Combining what Og says with the assertion that Og is a Knight makes a true statement. This is Smullyan’s “Nelson Goodman Principle” in a nutshell.

These versions of Og’s and Bog’s statements must be true. But neither of them alone is enough. I need to capture that each brother says something about the other brother.

I can combine the two statements with an & (for logical AND), since I know both statements evaluate to true. That gives me a single, complicated, true statement.

All I have to do is write out a truth table for:

(KOg = (CBog & ~KBog)) & (KBog = (~COg & KOg))

When I’ve got the truth table, I look at what values of CBog and COg make the whole statement true. Let’s just hope that the values aren’t “both Og and Bog are chief”, or “neither Og nor Bog is chief”.

Just for completeness’ sake, there’s 4 logical variables in that formula:

  1. KOg
  2. CBog
  3. KBog
  4. COg

Luckily, I have written software that can make truth tables.

CBog COg KBog KOg (KOg = (CBog & ~KBog)) & (KBog = (~COg & KOg))
true true true true false
true true true false false
true true false true TRUE
true true false false false
true false true true false
true false true false false
true false false true false
true false false false false
false true true true false
false true true false false
false true false true false
false true false false TRUE
false false true true false
false false true false false
false false false true false
false false false false TRUE

Darn, 3 lines where the two brothers’ statements could be true.

Only 1 of the 3 lines makes sense, since we know that only one brother is chief. The first true line has both brothers as chief, The last true line has neither brother as chief. Only the line where Og is chief, and both brothers are knaves makes sense.

The truth table above has “neither”, “both” and a “true” line for who is chief. I think this is similar to four-value logic, where variables and be true, false, neither or both. “Neither” might also correspond to “over constrained”, and “both” might correspond to “under constrained”. Let’s fix that.

We know that only one brother is chief, so the two logical variables COg and CBog are not independent. Saying “Og is not chief” is the same as saying “Bog is chief” When one of the two logical variables is true, the other is false. I’m not constraining the variables to fit the “reality” of the question. I’m allowing nonsensical conditions, and weeding them out when manually examining the truth table.

I can encode the condition of “only one brother is chief” by eliminating one logical variable. I’m getting rid of COg. When Bog says “Og is not the chief” (symbolized by ~COg), the equivalent is “Bog is the chief”. Getting rid of the negated variable makes the combined statement cleaner.

(KOg = (CBog & ~KBog)) & (KBog = (CBog & KOg))
CBog KBog KOg (KOg = (CBog & ~KBog)) & (KBog = (CBog & KOg))
true true true false
true true false false
true false true false
true false false false
false true true false
false true false false
false false true false
false false false TRUE

Only one row exists where the combined statements are true, Bog is not chief, which means Og is chief, both Og and Bog are knaves.

I could also make a really complicated, 4-variable proposition that encodes “only 1 brother is chief” explicitly:

CBog COg KBog KOg ((KOg = (CBog & ~KBog)) & (KBog = (~COg & KOg))) & ((CBog & ~COg) | (~CBog & COg))
true true true true false
true true true false false
true true false true false
true true false false false
true false true true false
true false true false false
true false false true false
true false false false false
false true true true false
false true true false false
false true false true false
false true false false TRUE
false false true true false
false false true false false
false false false true false
false false false false false

Same result: Og is the chief, both Og and Bog are knaves. Shoot, I was rooting for Bog.

I really like this particular puzzle, I think because the words “Og” and “Bog” feel so comical. What Og and Bog say looks simple at first glance, but upon examination, becomes very complicated. There’s a dramatic contrast with the comical names.

I grudgingly have to note that having a knave as the chief seems unwise. Always negating what Og says would cause a lot of cognitive burden.