Non-Classical Knights and Knaves

Recently I mentioned my new book Four Lives: A Celebration of Raymond Smullyan. I see the Kindle version is now available, so if you preferred an e-version, now's your chance!

The book is a tribute volume to mathematician Raymond Smullyan. He is best known for his numerous books of logic puzzles. In particular, he took puzzles about knights and knaves to a high art. He did not invent the genre, but he definitely elevated it. (I've been trying to trace the history of puzzles of this sort, so if anyone knows any good references then let me know.)

We are to imagine that on a particular island, all of the natives are either knights or they are knaves. Knights only make true statements, and knaves only make false statements. Knights and knaves are visually indistinguishable, meaning the only way to determine who is who is to ferret out the logical consequences of their rather cryptic statements.

A typical such puzzle might unfold like this:

You come to a fork in the road. You know that exactly one of the paths leads to the city, but you do not know which one. You see three natives, named Alan, Beth and Carl, standing nearby, and you ask them which path you should take. They make the following statements.

Alan: You should take the left fork.
Beth: No! You should take the right fork.
Carl: If there are at least two knights among us, then you should listen to Alan.

Which path will take you to the city?

One way to solve this is note that since Alan and Beth contradict each other, they are of different types. One is a knight, and one is a knave. Now let's suppose, for the sake of argument, that Carl is a knave. That means there are two knaves and one knight among them. This implies that the first part of Carl's if-then statement is false. That implies the entire if-then statement is automatically true. But this is a contradiction, since it would entail a knave making a true statement. We conclude, therefore, that Carl is a knight. Thus, there are two knights and one knave among the three of them. Since Carl is a knight, his statement must be true. Since the first part is true, the second part must be true as well. So you should listen to Alan and take the left fork.

Smullyan presented these puzzles not just for their entertainment value, but also as a device for introducing principles of classical logic. He introduced numerous variations on the basic theme. Some of his puzzles involved “Normals,” who sometimes lie and sometimes tell the truth. (Just like normal people!) He introduced day-knights and night-knights. The former tell the truth during the day and lie at night, while the latter do the reverse. He also introduced the idea of sane and insane people. Everything a sane person believes is true, while everything an insane person believes is false. So, an insane knave behaves like a knight. He wants to lie, but since everything he believes is false he inadvertently tells the truth.

That's just a taste. For more, I recommend reading all of his books.

As I reread all of Smullyan's books while preparing Four Lives, I got to wondering what knight/knave puzzles might look like for various non-classical logics. Now, if you are unfamiliar with such things, the word “logics” might seem very strange. Surely there is only one logic.

Well, not so fast. The modern development of logic has much in common with the modern development of geometry. At one time Euclidean geometry was viewed simply as the truth. Non-Euclidean geometry, to the extent it was even logically consistent, could never be more than a pointless exercise. But no mathematician would make that claim today. Instead we speak of different systems of geometry. The proper question to ask of a given system is not, “Correct or incorrect?” Rather, you should ask, “Useful or not useful?”

So it is with logic. There are many possible systems of logic, and classical logic is only one of them. Different systems of logic can be useful in different contexts.

Let's consider an example. Classical logic is based on the premise that there are only two truth values. Every proposition is either true or false, and those are the only options. Sometimes, though, that can be a bit too limiting. Some statements are vague, suggesting that it's not so simple to declare them definitively true or definitively false. Perhaps we need a third truth value, one that indicates the statement is vague. We might refer to the resulting system as three-valued logic, for what I trust are obvious reasons.

So, let's imagine that biologists visiting the island of knights and knaves have discovered that knight-hood and knave-hood are not permanent conditions. Instead, the natives cycle, repeatedly and unpredictably, between the two states. They are knights for a while, then they enter a transitional phase during which they are partly knight and partly knave, and then they emerge on the other side as knaves.

This presents a problem. If Joe is in the transitional phase, and you say, “Joe is a knight,” or “Joe is a knave,” what truth value should we assign to your statement? Since Joe is partly knight and partly knave, neither of the classical truth values seems appropriate. So we shall assign a third truth value, “N” to such statements. Think of N as standing for “neutral” or “neither true nor false.” On the island, vague statements are assigned the truth value N.

Just to be clear, it's not just any statement that can be assigned the truth value N. It is only vague statements that receive that truth value, and for now our only examples of such statements are attributions of knight-hood and knave-hood to people in the transitional phase.

For the natives, entering the transitional phase implied a disconcerting loss of identity. Uncertain of how to behave, they hedged their bets by only making statements with truth value N. People in the transitional phase were referred to as neutrals. So there are now three kinds of people: Knights, who only make true statements; Knaves, who only make false statements; and Neutrals, who only make statements with the truth value N.

As you might imagine, this can lead to some confusion.

Suppose you meet three people, named Dave, Evan and Ford. They make the following statements:

Dave: Evan is a knight.
Evan: Ford is a knave.
Ford: Dave is a neutral.

Can you determine the types of all three people?

Mull that over and feel free to discuss the solution in the comments. I've just started playing around with this, but it's a lot of fun, I think. I have a large stockpile of puzzles for three-valued logic, and I've also been exploring puzzles for fuzzy logic. There are many other systems of propositional logic to consider, so perhaps this will keep me busy for a while.

More like this

Here's a logic puzzle for you: Suppose I offer you a million dollars, in return for which you agree to answer a certain yes/no question. You can answer either truthfully or falsely as you desire. That's it. Should you accept that offer? Solution below the fold. Those of you reading this who…
The commenting problems are proving harder to fix than I expected. The overlords have assured me that this is a high priority problem and that they are working on it. Apparently there is only one other blog around here that has been similarly affected. I don't want to return to regular blogging…
In logic, a conditional is an if-then statement. “If it rains, then I will go to the movies,” that's a conditional. The question is, how should we assign a truth value to such a statement? This is a question of some importance to mathematicians, since every theorem is ultimately an if-then…
Raymond Smullyan is name that is probably familiar to a lot of readers of this blog. In addition to being a mathematician and philosopher, he is known for being a master of using brainteasers and other puzzles to illuminate sometimes deep ideas in logic, especially Godel's theorems. He is perhaps…

Well, Ford is lying, because Dave did not make an neutral statement, so he is a knave.

This means that Evan's statement is true, so he is a knight, and this in turn means that Dave's statement is true, so he is a Knight too.

By Valhar2000 (not verified) on 26 Mar 2014 #permalink

I agree with Valhar2000. So I wonder if it's possible for a neutral to make a statement that is not obviously neutral at first. Or, to put that another way, a statemnt that's only neutral in context. Maybe like this?

Obvious Neutral: This statement is false.
Non-Obvious Neutral: My neighbor's statement was false. (Althernatively: My neighbors statement was true.)

Or this?

Non-Obvious Neutral Two: My neighbor's next statement will be true.
Non-Obvious Neutral Three: My neighbor's statement just now was false.

This presents a problem. If Joe is in the transitional phase, and you say, “Joe is a knight,” or “Joe is a knave,” what truth value should we assign to your statement? Since Joe is partly knight and partly knave, neither of the classical truth values seems appropriate. So we shall assign a third truth value, “N” to such statements. Think of N as standing for “neutral” or “neither true nor false.” On the island, vague statements are assigned the truth value N.

If "Joe is a knight" can be a neutral statement if in fact Joe is in the transitional phase, then it's a bit harder to solve Jason's puzzle:

Dave: Evan is a knight.
Evan: Ford is a knave.
Ford: Dave is a neutral

Ford is the only one here making a statement that isn't potentially neutral (unless "Joe is a neutral" is T in case of neutral and N in other cases* -- but I think it's F in those other cases).

So. Assume Ford is a knight, and that Dave is in fact a neutral. Dave says Evan is a knight, so if Dave is a neutral as Ford claims, then Evan must also be a neutral. If Evan is a neutral, then Ford must also be a neutral, which contradicts the assumption.

If Ford is a knave, then Valhar2000's analysis holds.

* If "is a neutral" can only ever be T or N, then we have to check if Ford is a neutral, because he couldn't be a knave. If he is a neutral, then Dave is either a knave or a knight. If Dave is a knight, then Evan is a knight, which contradicts the assumption that Ford is a neutral. If Dave is a knave, then Evan is also a knave, but Evan has made a statement that is N in case Ford is a neutral, so Evan can't be a knave. Thus, Ford can't be a neutral. But now we're in a bind, because Ford can't be a knight or a knave either, so these particular statements could never have happened on this island.

By Another Matt (not verified) on 26 Mar 2014 #permalink

Your all tapped

By Brainwashed idiots (not verified) on 26 Mar 2014 #permalink

Brainwashed idiots: Let us know when our next upkeep phase happens and we're untapped.

Am I right that a neutral person can never say "X is neutral"? In other words, it's been set up that "X is a knight" and "X is a knave" are neutral statements when X is in the transition period, but if X is a knave or knight "X is neutral" is false and if X is neutral, then "X is neutral" is true. So "X is neutral" is never neutral, right? (And I've now typed "neutral" so many times it doesn't look like a word anymore). I can imagine this observation might simplify some number of such problems. At least it eliminates certain possibilities immediately.

Greg, right. I think "X is neutral" is always either T or F, or it is either T or N. One could make the case for the latter, though -- if "X is a neutral" is never neutral, then neutrals have no way to refer to the knights and knaves on the island.

A lot of these logic problems require you to ask questions of the islanders. What happens if you ask them about Jack, who happens to be a knave? The neutral can't say "Jack is a knave" or "Jack is a knight," so what can they say? "Jack is a neutral" is one possibility, if the rule is that they have to say one of the three. Another would be to allow them hedges, like "Jack might be a knave." Another would be a new rule: suppose that, as part of their transition, neutrals have "knight blindness": they can't tell knights from knaves from neutrals, and from their perspective, all the categories are equally vague -- any response would be neutral to them no matter its truth value (in which case questions about the categories themselves would be useless).

The composer of the problem would have to be up front and specific about the rules.

By Another Matt (not verified) on 26 Mar 2014 #permalink

I think Greg is right, "X is neutral" is never a neutral statement.
Then Ford is not neutral.
Which means Evan's statement, and thus Evan, are not neutral.
Which means Dave's statement, and thus Dave, are not neutral.
Which means Ford's statement is false.
Which means Evan's statement is true.
Which means Dave's statement is true.
So I get the same answer as Valhar2000, even though I think he(?) has misinterpreted the truth table.

"For more, I recommend reading all of his books." - since this is a rather daunting suggestion, and since one has to start somewhere, may I suggest just starting with "What is the name of this book?"? I'm only familiar with a few of his books, but of those it's the most introductory, and the one that's directly relevant to the content of this post.

The way I've set things up, “X is a neutral” must have a classical truth value. You cannot be partly a neutral and partly not a neutral. So, in the problem, we know immediately that Ford is either a knight or a knave. However, the statements made by Dave and Evan are not obviously anything. Taken in a vacuum they could be either true, false or neutral.

Another Matt and Warren have both analyzed things the way I intended.

Another Matt, your point about what a neutral can say when asked a direct question is well-taken. As things stand, there's a rather small supply of potentially neutral statements.

Here's a different way of motivating such puzzles. In opposition to Russell's theory of descriptions, P. F. Strawson suggested that sentences with definite descriptions that fail to refer lack truth values: "The present king of France is fat" is neither true nor false, simply because there is no present king of France. Let's suppose that Strawson was right about this, and let's say that neutrals are islanders who always utter sentences that lack truth values (as opposed to have a third truth value). Then we can pose a puzzle like this:

You meet three islanders, Gavin, Harry, and Isaac, and you ask them if any of them are neutrals. They answer as follows:

Gavin: The neutral among us is Harry.
Harry: The most handsome neutral among us is Isaac.
Isaac: None of us are neutrals.

Which of them are knights, neutrals, knaves? Which if any is the most handsome?

By Glenn Branch (not verified) on 26 Mar 2014 #permalink

Actually, ignore the second question; there isn't enough information to answer it.

By Glenn Branch (not verified) on 26 Mar 2014 #permalink

Hi Glenn. That's an interesting approach. I'm not sure if I fully understand your intention, though, since I seem to be getting a contradiction however I try to look at it.

If there are no neutrals among Gavin, Harry and Isaac, then all three of them always make statements with truth values. But in this scenario, neither Harry's statement nor Gavin's statement refers to anything, and therefore would lack a truth value. That's already a contradiction, so there must be at least one neutral.

That implies that Isaac's statement is false, making him a knave.

But here's where things get a little murky. We know there is at least one neutral among them, and that Isaac is not him. The question now is whether “the most handsome neutral among us” refers to anything. If it does, then Harry's statement is just false. Since Isaac is not any kind of neutral, he certainly is not the most handsome neutral among them. That makes Harry a knave. But that immediately makes Gavin a knave as well. This is a contradiction, since there would then be no neutrals among them after all.

If we assume instead that Harry's statement does not refer to anything then he must be a neutral. In this case, Gavin's statement is true, making him a knight. But then Harry would be the only neutral among them, meaning he must be the most handsome neutral just by default. So his statement refers to something after all, and is true.

What have I missed?

Jason and Glenn

I ran into the same contradictions that Jason outlined very well. The only way around it that I can see is that "The most handsome neutral among us is Isaac" is to be regarded as having no truth value unless: 1. There is at least one netural among the three, and 2. Isaac is a neutral. If that's the premise, then this statement is a neutral one, so Harry is a neutral. That would make Isaac a knave and Gavin a knight, without any contradictions. It doesn't seem intuitive to me to say that Harry's statement lacks a truth value in this case, but it would render the system noncontradictory if we did indeed regard Harry's statement as lacking a truth value.

The intention was to have Gavin, Harry, and Isaac be a knight, a neutral, and a knave, respectively, The puzzle still works -- you just have to conclude that Harry is so hideous that he can't be deemed to be handsome at all (and so a fortiori not the most handsome neutral) -- but only awkwardly. I intended it more as a proof-of-concept than as a finished puzzle. Originally, I was going to have Harry say, "The neutral among us is Gavin," which would entail that Harry and Gavin were both neutrals (and Isaac still a knave), but I couldn't resist the temptation to try to fiddle with it...

By Glenn Branch (not verified) on 28 Mar 2014 #permalink

What if Harry said, "Isaac is the loveliest female neutral among us"?

There's something a little fishy in the last contradiction Jason pointed out, though, in something like the way the Gettier cases are fishy. It's as though Harry is a neutral, but thinking Isaac was a fellow neutral, he tried and failed to make a neutral statement in which the referent of the sentence happened to be different from what he had in mind when he uttered it. Intension-with-an-s doesn't generally figure into knights and knaves, but it does in our analysis of natural language.

The following is perfectly clear in everyday language, but in a logic problem there isn't enough information to answer the question:

I have four dogs. One of them is a poodle. I also have pugs, but no other breeds. How many of each breed do I have?

By Another Matt (not verified) on 28 Mar 2014 #permalink

If anyone ever comes up with puzzles like these based on dialetheism, we'll have to give up on Knights and instead call them Priests.

By Steven Reilly (not verified) on 31 Mar 2014 #permalink