Knights and Knaves

Topics

Truth tables, meaning of and, or, not, and if…then in logical reasoning; difference between or and exclusive-or

Overview

This problem is the best-known simple example of a knight-knave problem, in which you come to a fork in the road and you do not know which way to go. In one direction lies happiness, in the other, disaster. Fortunately, there is a guide sitting at the fork to direct you; unfortunately, you do not know whether the guide is a knight (always tells the truth) or a knave (always lies). The challenge is to devise a single yes-no question that will tell you which way is happiness. A powerful tool, truth tables, gives you a technique for dealing with many problems of this type. P>

Learning Objectives:

• Develop facility with logical reasoning.
• Analyze one of the most formidable language puzzles, the Knights and Knaves problem.
• Prepare students to apply logical arguments to geometry and other areas of mathematics.

The "Hook"

You are walking along a path on an island and you come to a fork in the road.  You know that one path leads safely to a fabulous village and the other path leads into an impassable swamp where you will surely die.  But you do not know which path is which.  There is a man standing at the fork, and you can ask him one question to help you choose the path to take.  You also know that this is the famous island on which live two kinds of men, knights and knaves.  Knights always tell the truth and knaves always lie.  Of course, in situations like this you can never tell knights from knaves. 

Explain why your question is guaranteed to resolve your dilemma.

The Investigation

Students will probably pose simple questions first, such as, “Are you a liar?”  or “Does the left path go to the village?” Be sure to have students write down the exact question they will ask, so they know exactly what they are answering. They will quickly decide that such simple questions will not give them the information that they need, and they will be able to see why these questions will not work.

You will need to convince students that if they are deciding whether a question will work, they have to know exactly what the question means in order to know how it would be answered in all possible situations.

1.     The left path goes to the village, and the man tells the truth.

2.     The left path goes to the village, and the man is a liar.

3.     The right path goes to the village, and the man tells the truth.

4.     The right path goes to the village, and the man is a liar.

Let students discuss the following question: 

This is a subtle point.  All you need to know is which is the correct path.  You do not need to know whether the man is a liar so long as you learn which path to take.  So, good responses from the man would be, for example, “Yes” whenever the left path happens to go to the village, and “No” whenever the right path goes to the village. The meaning of the simple question, “Are you a liar?” is clear enough.  It will be answered, “No” whenever the man tells the truth.  Unfortunately it will also be answered “No” by any liar.  So you will always get “No” for an answer and you will never get any information about which is the path to the village.

“Does the left path go to the village?” is flawed, too.

If the left path goes to the village, and the man tells the truth, he will reply, “Yes.”

If the left path goes to the village, and the man is a liar, he will reply, “No.”

If the right path goes to the village, and the man tells the truth, he will reply, “No.”

If the right path goes to the village, and the man is a liar, he will reply, “Yes.”

So no matter which path goes to the village you can get a reply of either “Yes” or “No” and you cannot tell which path to take unless you know whether the man tells the truth or lies.  But you get no information about what kind of man he is.

Students will quickly decide that such simple questions will not give them the information they need, and they will be able to informally analyze them to see why they will not work.

After dismissing the simplest of questions, students will probably come up with posing compound questions, such as, “Are you a liar and does the left path go to the village?” or “Are you a liar or does the left path go to the village?”  Then, if those do not work they might come up with questions like, “Are you a liar and if I asked you if the left path goes to the village, would you reply yes?”

Introduce the idea of truth tables with a simple example.

Examine the truth or falsity of several statements (without worrying right now about the circumstances that will get you the answers “yes” and “no”).

Suppose that the left path goes to the village, and the man lies.  Then the statement, “The left path goes to the village” is true (abbreviated T). “The right path goes to the village” is  false (F). “You are a liar” is T. “You tell the truth” is F.

What about “The left path goes to the village and you lie”?  Both parts are T and so the statement as a whole is T.  But if either part had been F or both parts had been F, then the statement as a whole would have been F.  For instance, “The left path goes to the village and you tell the truth” is F.  This leads to the idea of having a truth table for “and.”  In this analysis, “The left path goes to the village” and “You are a liar” are just stand-ins for any two statements  p, q, either of which could be true or false.  Whether the compound statement  p and q is true or false can be determined by the following truth table for and.

and:       p         q      p and q

            T          T          T            

            T          F          F

            F          T          F

            F          F          F

You see that if you pick out the truth or falsity of the statements  p  and  q  and read across the appropriate row in the table, the truth or falsity of the compound statement  p and q is in the last column.

Let’s see how fares the compound question, “Does the left path go to the village and are you a liar?”  We do not know whether the left or the right path goes to the village, and we do not know whether the man lies.  We list all four of the possible situations and figure out how the question will be answered in each of them.  Let’s also agree to ask the question in a form that makes it easier to understand even more complicated questions.

Ask, “Is it true that the left path goes to the village and you are a liar?”

p:  left to village    q: you are a liar     p and q      answer

            T                      T                   T           no (a lie)

            T                      F                   F           no (the truth)

            F                      T                   F           yes (a lie)         

            F                      F                   F           no (the truth)     

So, this question does not work, because you would like to get the same answer from either type of man whenever the left path goes to the village and the opposite answer from each type of man when the left path does not.

You can make a truth table for or, too.  But before doing that, students need to realize that there are two meanings of the word “or” used in ordinary English.  The more common usage is that found in precise writing, such as (forgive the example) instructions for filling out federal tax forms.  Here is an example from page 66 of the instructions for filing Form 1040 for the tax year 2006.  Watch for the first “or.”

A frivolous tax return is one that does not contain information needed to figure the correct tax or shows a substantially incorrect tax because you take a frivolous position or desire to delay or interfere with the tax laws.

This means that a return will be considered frivolous if one or both of the following statements is true:

“does not contain information needed…”

“shows a substantially incorrect tax because…”

This is the usual meaning of the word “or.”

Contrast that to the decree of a parent to a child, “You can have a piece of cake or (emphasis on or) a piece of pie.”  The parent means that the child can have cake or pie but not both.  The parent will ignore linguistic arguments made by the child that using  “or” does not exclude having both.  This parental use of “or” is called an “exclusive-or.” But in most ordinary discourse the word “or” will not be interpreted as forbidding both possibilities.  And in logical analysis, which is what we are doing here, the word “or” should never be used in the exclusive sense without a warning to the reader or listener that the exclusive-or is being used.  In a technical situation in which both types of or are going to be used, you can agree to write “or” for the usual or and “xor” for exclusive-or.

We will ban exclusive-or from this problem, and here is a truth table for the ordinary or.

or:         p         q        p or q

            T         T           T            

            T         F           T

            F         T           T

            F         F           F

Probably the simplest truth table is the one for not. “Not” is the logical word used to negate a statement.  For example, if  p  is the statement, “The left path leads to the village,”  then  not p  is the statement, “the left path does not lead to the village.”  And if one of the statements is true, the other is false, and vice versa.  So the truth table for not is:

not:       p        not p      

            T           F           

            F           T

Next we take up implies.  Its analysis allows you to analyze questions like, “Are you a liar and if I asked you if the left path goes to the village, would you reply yes?”  This is a nicely complicated statement.

The logical term “implies” takes the place of  “If … , then … ,” which is commonly used in ordinary English.   For example, examine the statement, “If that car is a 1960 model, then it is worn out.”

This compound statement has two parts: 

p:  that car is a 1960 model

q:  that car is worn out

If that car really is a 1960 model and it really is worn out, so that both p  and  q  are true, then the compound statement is true.  But if the car is a 1960 model and is not worn out, then the compound statement is not true at all—it is false.  Now we have analyzed both situations when the car is a 1960 model.  What if it is not a 1960 model?  Suppose the car is a 2000 model and it still runs fine.  Now the compound statement does not apply to the car at all, because it only asserts something in case the car is a 1960 model. 

In the logic we are discussing, any statement is either true or false.  We are not working with “three-valued” logic here, and there is no “maybe.”  We are just trying to put easily analyzable statements on a solid logical foundation (and we are ignoring all of the paradoxes and subtle difficulties that logicians love to discuss at length). 

Getting back to the compound statement again, have a look at that 2000 model car that still runs fine.  Now, we say about it, “If it is a 1960 model, it is worn out.”  There is nothing contradictory about saying that.  So our statement is definitely not false.  If it is not false, it is true.  Same thing if the model 2000 car is worn out.  The compound statement says nothing at all about the car in that case, and therefore is not false, so it is true. 

This is where logical thinking diverges a little from ordinary thinking.  Ordinarily we might just shrug and say that the compound statement is neither true nor false because it does not apply.  In logic we think instead, ”The statement does not have any consequences at all if the car is a 2000 model, so it cannot be false, therefore, it is true. Well, you know now how logicians think.  Just remember that the man standing at the fork in the road to whom you address your single life-saving question is an expert in logic and he will interpret your question is a strictly logical manner.

Before seeing the truth table for  “implies” let’s reword the compound statement using the word implies.  “The car is a 1960 model implies that the car is worn out.”  Here is the truth table for implies.

implies:  p        q          p implies q

           T         T               T            

           T         F               F 

           F         T               T

           F         F               T

Now you are in position to analyze, “Is it true that you are a liar and if I ask you if the left path goes to the village, you will reply yes?” The statement that you are inquiring about  is a compound statement using “and.”  So let’s start by using:

p: You are a liar

q: If I ask you if the left path goes to the village, you will reply yes

Statement q  is not the same as the following simpler statement:

r: The left path goes to the village

We now analyze all four possible situations.  Note that the answer to the question depends on whether the man lies or tells the truth (the first column).

   p            r           q      p and q      answer to the question

   T           T           F          F                     yes                        

   T           F           T          T                     no                         

   F           T           T          F                     no                        

   F           F           F          F                     no                         

So this complicated question does not work because we can get answers of either yes or no when the left path goes to the village.  But we have unwittingly almost come across a question that does work. 

Casting about for good questions to ask is pretty frustrating, but analysis of such questions using truth tables is good practice in logical thinking.   It would be nice to have a systematic way to approach such problems, rather than relying on serendipity to rescue you.  Here are more situations for which serendipity might not get you where you want to go.

1.  What if the path to the village must cross a river, and if the water is high, you will be swept away if you try to cross it, but during high water you can safely use the other path and take a boat through the swamp to reach the village?  The man at the fork always knows whether the river is high, but you do not.

2.  The people who live on this island understand every word of your language.  They also speak your language, except for the two words yes and no.  Their words for yes and no are up and down, but you do not know which one of them means yes and which means no.  Can you find a question that you can ask the man at the fork and know from his answer which is the good path?

3.  What if there are three paths?  Can you get by with one question if the answer to it must be “yes” or “no”?  Can you get by with two “yes or no” questions? Can you get by with one question if you allow three possible answers? 

One such way is set out in the solution file.

Teaching Tips

• Expect some push-back when you discuss the truth table for implies:  p implies q.  The fact that the statement as a whole is true whenever  p  is false is not quite intuitive.  By the way, the statement  p implies q  is equivalent to the statement  q or not p. Equivalent statements are those with the same truth table in all possible situations.  Your students can work out the following truth table.  The fact that the last two columns turn out to be identical means that  q or not p  and  p implies q  are equivalent statements. 

             p     q      not p      q or not p    p implies q

            T     T        F               T                  T

            T     F        F               F                  F

            F     T        T               T                  T

            F     F        T               T                  T

• There is a danger in being enticed to do too much logic in a systematic way.  The amount given in this problem ought to make the students more comfortable doing deductive geometry.  More logic could be done in geometry as needed by your students.  But more on this problem might simply bore them.

Supporting Resources

An excellent book which treats Knights and Knaves and other topics in logic is the book by Raymond Smullyan, What Is the Name of This Book?  Prentice-Hall, 1978. Reissued 1986 by Touchstone. It is out of print and missing from many libraries, but might be available used.

Citation

From the teaching files of Robert B. Brown.