Knight-Knave Problems


Suppose you go for your vacation to the Island of Knights and Knaves – will you be able to converse with the natives, and make your way around the island?  Thanks to your Logic training, the answer is yes.  Formal Logic provides all the tools you need to handle Knights and Knaves.

Here is the basic rule of the Island of Knights and Knaves: Knights always tell the truth, and Knaves always lie.  As you might expect, this makes communication a little complicated.  Knights and Knaves look the same, so it’s not immediately clear if a person is one or the other.  Of course, you can ask the person which he or she is – but they’ll say “I’m a Knight” either way!  (Knights will say this because it’s true, Knaves because it’s false.)  So how can you tell who is who, and which sentences to believe?  Formal Logic is the key.

For example, suppose on the beach you meet two natives of the island, named “P” and “Q”; and P says “Either I am a knave or Q is a knight”.

The first step in sorting out such a situation is to translate the claim into formal language.  Let’s use the following translation table:

P: P is a knight
Q: Q is a knight

Now, what if we want to say that P is a knave?  Do we need another sentence letter for that sentence (maybe “R”)?  NO – because on the island of Knights and Knaves everybody is either one or the other.  So saying that P isn’t a Knight, is on the island equivalent to saying that P is a Knave.  Using our translation table, “P isn’t a Knight” would be “~P”.  And we know that this is equivalent to saying “P is a Knave”.  The same trick works if you want to say that Q is a Knave: that’s the same as saying that Q isn’t a Knight.

P: P is a Knight
Q: Q is a Knight

~P: P is a Knave
~Q: Q is a Knave.

Now we can translate what P said into formal notation.  P said:  

Either I am a knave or Q is a knight

This translates as:

But what do we do with this sentence?  We apply the two laws of the Island to it.

The First Law of the island is this: if P is a knight, then what P says really is so.  And what P says is: “Either P is a Knave, or Q is a Knight.”  So, according to the First Law: if P is a Knight, then (Either P is a Knave, or Q is a Knight).  Using the same translation table, we translate the First Law into formal notation: 

The Second Law of the island is the reverse of the first law: if what P says really so, then P is a Knight.  In formal notation:

Now, both of these laws are guaranteed to be true: on the island, Knights always tell the truth (First Law), and if someone tells the truth, that person is a Knight (Second Law).  So, in the current situation, we know that both of these sentences must be true:

With our semantic methods, we can use sentences (1) and (2) to figure out what P and Q are.  Using truth tables, we can figure out the situations where both of these sentences are true.

It turns out that the only valuation where sentences (1) and (2) are both true, is the first valuation.

And in the first valuation, the sentences “P” and “Q” are both true.  Remember: by our translation table, “P” means “P is a Knight,”  and “Q” means “Q is a Knight”.  So in a situation making sentences (1) and (2) true, both P and Q are Knights.  But we know that in the situation we’re in here, sentences (1) and (2) must be true.  So: in this situation, P and Q are both Knights.

That’s how to solve a Knight-Knave problem.

1. Translate what the speaker said into formal language.

2. Build two conditional ‘law-sentences’ which are guaranteed to be true:

  If that person is a Knight, then [sentence the person said].
  If [sentence the person said], then that person is a Knight.

3. Then use the semantic rules to figure out where those two sentences are both true.  You are there.