# Knights and Knaves, from Rocky Humbert

July 28, 2011 |

My friend Russ Sears and I were talking, and he was differentiating between "crooks" who behave with rational motives and "pathological liars."

He told me, "in 6th Grade I had a friend that was a pathological liar. He would lie even when telling the truth would have been more beneficial to him. He simply could not help himself, when he was asked a question he had to lie. He had a platform to showcase his "talent" and he could not tell the truth no matter what."

Without regard to whether politicians are necessarily pathological liars, his 6th grade friend brings to mind Smullyan's "Knights and Knaves " logic puzzle — which (as opposed to a meal for a lifetime) can cause indigestion for a lifetime. That is because a pathological liar is vastly preferable to an "alternator" who alternates between lying and telling the truth; and is also preferable to a "normal" who says whatever they want.

Knights and Knaves is a type of logic puzzle devised by Raymond Smullyan.

On a fictional island, all inhabitants are either knights, who always tell the truth, or knaves, who always lie. The puzzles involve a visitor to the island who meets small groups of inhabitants. Usually the aim is for the visitor to deduce the inhabitants' type from their statements, but some puzzles of this type ask for other facts to be deduced. The puzzle may also be to determine a yes/no question which the visitor can ask in order to discover what he needs to know.An early example of this type of puzzle involves three inhabitants referred to as A, B and C. The visitor asks A what type he is, but does not hear A's answer. B then says "A said that he is a knave" and C says "Don't believe B: he is lying!" To solve the puzzle, note that no inhabitant can say that he is a knave. Therefore B's statement must be untrue, so he is a knave, making C's statement true, so he is a knight. Since A's answer invariably would be "I'm a knight", it is not possible to determine whether A is a knight or knave from the information provided.In some variations, inhabitants may also be alternators, who alternate between lying and telling the truth, or normals, who can say whatever they want (as in the case of Knight/Knave/Spy puzzles).

A further complication is that the inhabitants may answer yes/no questions in their own language, and the visitor knows that "bal" and "da" mean "yes" and "no" but does not know which is which. These types of puzzles were a major inspiration for what has become known as "the hardest logic puzzle ever".

# Comments

Name

Email

Website

Speak your mind

3 Comments so far

1. Don Chu on July 28, 2011 8:48 pm

Nice, the Knights & Knaves puzzle; a combinatorial logic dream for over-imaginative kids.

In 4th grade, I watched the amazing David Bowie as a riddling dark Prince and a young luminescent Jennifer Connelly in the fascinating Labyrinth (great Bowie music and good old Escher-ian steps paradoxes and perspectives here);
and of course with its very colourful and entertaining presentation of the Knights & Knaves puzzle:
Labyrinth — Door Knobs puzzle
http://www.youtube.com/watch?v=2dgmgub8mHw

Before diving straight into a very messy and tedious solution by using and sorting through the basic Wittgensteinian/Boolean truth-tables, we can take a step back and recast the puzzle into its general form in predicate logic.

Like most logic puzzles of higher ‘difficulty’ level, solutions for the K&K puzzle requires resolution through Second-order Logic, that is, to extend beyond just considering variables ranging over the domain set (for First-order logic) and include both the individual domain elements as well as variables ranging over the sets of individuals.
In this case of the K&K puzzle above, it means that the solution or correct query to be asked, must elucidate an answer that contains more than one result/information/parameter/argument for the enquirer; that is, the correct query must return 2 arguments/info, one from the initial first-order sets of variables and the 2nd from the extended second-order sets over the first.

If I remember correctly, back in school then when we tackled the Knights & Knaves puzzle, the general solution of this particular version of the problem can be reduced into the notation form:

∃§Q∀x[K(x)⊃(Q(x)≡D(x))]∧[¬K(x)⊃(Q(x)≡¬D(x))]

where x = Inhabitant of the island,
K(x) = Inhabitant who is a Knight,
¬K(x) = Inhabitant who is not a Knight: ie is a Knave,
D(x) = Inhabitant x claims that the chosen Door is correct,
¬D(x) = Inhabitant x claims that the chosen Door is incorrect,
Q(x) = The Solution Query or correct query.

And which in natural language, reads as:
Are you a Knight and the chosen door is the right door or are you a Knave and the chosen door is the wrong door?

But of course, later in college computational classes and with access to labs with high-performance machines, elegant forms and niceties can be forgone with and solutions to childhood puzzles rudely generated with ‘brute-force’ algorithms and raw computational power.

An entertaining exercise for the inquiring mind may be to translate the general solutions of the various Knights & Knaves puzzles from run-of-the-mill predicate logic or mathematical notation form, into other more ‘exotic’ and illustrative+pictorial logic formalisms, like Charles Sanders Peirce’s Logical Graphs or even more ambitious, into Law of Forms notation.

2. vic on August 1, 2011 12:43 am

if don chu were to be available […] , we would be honored by his presence for our annual spec party and he should contact linda at xxx xxx-xxxx for details or lap at mantr.com
vic

[edited Aug 2]

3. Don Chu on August 2, 2011 2:07 pm

Thank you for the invitation, but unfortunately I would not be available during that period. A pity.
Again, thanks and best regards.

Don