Lesson goal: Knights and Knaves Logic Puzzles

Previous: Euclid's GCD and reducing fractions | Home | Next: Truth-tellers, Liars, and Alternators

On the mythical Island of Knights and Knaves invented by mathematician and logician Raymond Smullyan:
  • Knights always tell the truth. Everything they say is true.
  • Knaves always lie. Everything they say is false.
Every inhabitant is either a knight or a knave.

Suppose you arrive on the island and encounter two inhabitants, $A$ and $B$.

$A$ makes the following statement:
"We are both knaves."


Can you deduce what $A$ and $B$ are?

Deductive Reasoning:

  1. Suppose $A$ were a knight. Then $A$'s statement must be true, which would mean $A$ is a knave. But a knight cannot be a knave! Therefore, our hypothesis is contradictory: $A$ cannot be a knight.
  2. Since $A$ is not a knight, $A$ must be a knave!
  3. Because $A$ is a knave, his statement "We are both knaves" is a lie (false).
  4. For the statement "both are knaves" to be false, at least one of them must NOT be a knave. Since we already know $A$ is a knave, $B$ must be a knight!
Let's see how Prolog's inference engine solves this logic puzzle automatically!
person(knight). person(knave).
% A knight tells truth: Replace ???? with Statement is_true(knight, Statement) :- ???? .
is_true(knave, Statement) :- \+ Statement.
solve(A, B) :- person(A), person(B), is_true(A, (A = knave, B = knave)).
goal: solve(A, B).
Move the mouse over a dotted box for more information.

  • Negation as Failure: In Prolog, \+ P means "it is not provable that P is true". This is Prolog's way of expressing logical NOT.
  • Constraint Exploration: Prolog generates each possibility ($A=\text{knight}, B=\text{knight}$, etc.) and tests the statement. Any contradiction fails immediately, leaving only the mathematically consistent truth!

Now you try. Run the code to see Prolog's answer, then try the puzzles in the Examples below!

Type your code here:


See your results here: