Logic

The question a liar answers truthfully

On an island where knights always tell the truth and knaves always lie, one question gets an honest answer from both: ask not whether something is so, but whether the islander would say yes if asked. The knave lies about his lie. Written as truth functions, the trick is the identity (Q ↔ K) ↔ K = Q, it is the only one of the sixteen possible questions that works, and applied a second time it strips out an unknown language too — enough to solve Boolos's puzzle of the three gods, checked here against every case.

Worth reading first: A formula is a corner of a cube · One connective is enough.

A traveller reaches a fork in a road. One path leads to the village, the other into the swamp, and at the fork stands one of the island’s inhabitants, who is either a knight, who always tells the truth, or a knave, who always lies. The traveller does not know which, and may ask one question that can be answered yes or no. Which question finds the village?

Puzzles of this kind are old — Raymond Smullyan gave them their island and their names in the 1970s, and versions with two guards at two doors are older — and their solutions are usually presented as clever tricks. This essay presents them as truth tables. A formula is a corner of a cube treated a logical formula as a function from true-or-false inputs to a true-or-false output; an islander is such a function too, and so is every question. The famous trick turns out to be one specific truth function, the only one of sixteen that does the job; and the same function, applied twice, solves a puzzle with an unknown language and a god who answers at random, which George Boolos called the hardest logic puzzle ever.

Asking about the answer

The question a liar answers truthfully. knight/yes/yes/yes; knight/no/no/no; knave/yes/no/yes; knave/no/yes/no
Fig. 1 A knight’s answer is the truth and a knave’s the opposite, so the answer to Q is Q ↔ K. Asked whether it would answer yes to Q, every resident answers Q, in all four rows.

Write KK for “the resident is a knight” and QQ for the proposition the traveller wants to know about — “the left path leads to the village”. A knight answers “yes” exactly when QQ is true; a knave answers “yes” exactly when QQ is false. In one formula, the answer to QQ is Q↔KQ \leftrightarrow K: yes when QQ and KK agree, no when they differ. That is useless on its own, because the traveller knows neither.

Now ask a different question: whether the resident would say yes if asked whether the left path leads to the village. The truth value of this new question is whatever the resident would answer to QQ, which is Q↔KQ \leftrightarrow K. The resident answers the new question as it answers everything: truthfully if a knight, falsely if a knave. So the answer is (Q↔K)↔K(Q \leftrightarrow K) \leftrightarrow K.

And ↔\leftrightarrow is associative, with K↔KK \leftrightarrow K always true, so (Q↔K)↔K=Q(Q \leftrightarrow K) \leftrightarrow K = Q. The figure checks the four cases. A knight asked about the left path tells the truth about its truthful answer; a knave, whose answer to QQ would be a lie, is asked about that lie and lies about it, which comes back round to the truth. The knave lies about his lie. Whoever stands at the fork, a yes means the left path.

Sixteen questions, one that works

Sixteen questions, one that works. 0000->0011 0001->0010 0010->0001 0011->0000 0100->0111 0101->0110 0110->0101 0111->0100 1000->1011 1001->1010 1010->1001 1011->1000 1100->1111 1101->1110 1110->1101 1111->1100
Fig. 2 Every yes-or-no question that depends only on K and Q, and the answer each draws, at the same four cases. Exactly one question draws the answer Q every time, Q ↔ K, and exactly one draws not Q.

Is the embedded question the only way? Any question the traveller can ask whose truth depends only on whether the resident is a knight and whether the left path is right is a truth function of KK and QQ, and there are exactly 24=162^4 = 16 of them — one connective is enough listed them all. Asking a question with truth value f(K,Q)f(K, Q) draws the answer f(K,Q)↔Kf(K, Q) \leftrightarrow K. The figure works through all sixteen, writing each question’s truth at the four cases and the answers it draws there.

Exactly one question draws the answer QQ in every case: the function f=Q↔Kf = Q \leftrightarrow K, which asks the resident whether it is a knight exactly when the left path leads to the village. It is the same truth function as asking whether it would say yes to QQ, since that question’s truth value was also Q↔KQ \leftrightarrow K. The two famous formulations of the trick — the embedded question and the biconditional — are not two tricks but two English sentences for one function. Exactly one other question, f=¬(Q↔K)f = \neg(Q \leftrightarrow K), draws ¬Q\neg Q every time, which is just as useful; the remaining fourteen draw answers that depend on KK, and from them the traveller learns something about the resident rather than about the road.

The uniqueness has a clean reason. The map from a question to the answer it draws, f↦f↔Kf \mapsto f \leftrightarrow K, is a bijection on the sixteen functions — applying it twice gives ff back — so exactly one question is sent to QQ. The answer is then forced: the question that works is Q↔KQ \leftrightarrow K, because that is what ↔K\leftrightarrow K sends to QQ.

The two-guard version, as the same algebra

The best-known form of the puzzle has two guards at two doors, one a knight and one a knave, and the traveller may ask one of them one question. The classical answer is to ask either guard “which door would the other guard say leads to freedom?” and then take the opposite door. In the algebra of this essay, the other guard’s answer to QQ is Q↔K2Q \leftrightarrow K_2, and the guard asked reports it as (Q↔K2)↔K1(Q \leftrightarrow K_2) \leftrightarrow K_1. Since exactly one of the two guards is a knight, K1↔K2K_1 \leftrightarrow K_2 is false, and the report is ¬Q\neg Q whichever guard is asked: one negation from the knave, passed through or added by the other, exactly once. Taking the opposite door undoes it.

So the two-guard trick is the one-resident trick with the second application of the lie supplied by a different person, and it works only because the two guards are known to differ. If both might be knaves, the report would be QQ or ¬Q\neg Q depending on which pair the traveller faced, and the question would be useless; the one-resident form, which applies the same resident’s nature twice, needs no such guarantee. That is the sense in which the embedded question is the more fundamental form: it does not rely on a fact about the population, only on the resident being consistent with itself.

Statements are equations

Three statements, decided by their tables. knave/knight; knight/knight|knave/knight; knight/knave
Fig. 3 Three statements by an islander A about A and B. Each of the four possible pairs is kept if A’s statement is true exactly when A is a knight. One pair survives the first and third puzzles, two the second.

The same algebra decides the classic puzzles in which an islander says something and the listener must work out who is what. When A makes a statement SS, the statement is true if and only if A is a knight: A’s utterance imposes the equation A↔SA \leftrightarrow S. Every puzzle of this kind is a system of such equations, and a truth table decides it by checking every assignment of knight and knave.

The figure does three. If A says that A and B are both knaves, the statement ¬A∧¬B\neg A \wedge \neg B must be equivalent to AA: a knight could not say it, because it would then be false; so A is a knave, the statement is false, and B is not a knave. One row survives: A a knave, B a knight. If A says that the two are the same kind, two rows survive — A could be either — but B is a knight in both, so the listener learns B’s kind and not A’s. If A says that at least one of the two is a knave, A must be a knight and B a knave.

Statements built only from ↔\leftrightarrow and ¬\neg, like the second, are linear over the two-element field: A↔BA \leftrightarrow B is A+B+1(mod2)A + B + 1 \pmod 2, so every puzzle using only such statements is a system of linear equations that elimination solves directly, exactly as a plane through the cube found the parity functions sitting on flat slices of the cube. Statements with “and” or “or” are not linear, and puzzles built from many of them are satisfiability problems, which is why some knights-and-knaves puzzles are easy and some can be made as hard as one likes.

Why the trick lives inside a small corner of logic

Every operation used so far — negation and the biconditional — belongs to a very restricted part of logic, and the restriction is what makes the trick reliable. What an incomplete set of connectives can say found that ↔\leftrightarrow and ¬\neg together cannot express every truth function: every formula built from them alone is affine, a sum of variables modulo 2 plus a constant, and so it cannot express “and” or “or”. On a Karnaugh map, which the map that puts neighbours side by side introduced, an affine function is a chequerboard or the complement of one: flipping any input it depends on flips the output, everywhere.

That is precisely the property a liar has. A knave is the identity followed by a negation, and a negation that is applied twice disappears; a statement made by a knave and then reported by a knave comes out true. Everything that is cancelled in these puzzles is cancelled because it enters twice through an affine operation. The embedded question is the observation that the traveller can make the unknown enter twice, by asking the resident to apply itself to its own answer. If the island had residents whose answers were not affine in the truth — residents who said “yes” whenever QQ was true or the weather was fine, say — no question would cancel them, because their errors could not be undone by repetition.

The same structure explains why the simplest puzzles are linear and the hardest are not. A system of statements built from ↔\leftrightarrow and ¬\neg is a system of linear equations over the two-element field, solvable by elimination in a handful of steps however many islanders speak. As soon as an islander says “A or B is a knave”, the system acquires a non-affine equation, and the general problem of deciding such systems is the satisfiability problem, for which no efficient method is known. The knights-and-knaves puzzles in books are almost all small enough that the difference does not show.

Not the liar’s paradox

The embedded question looks as if it should run into the paradox of the liar, since it asks a resident about its own answer. It does not, and the reason is worth stating. The question whether the resident would say yes to QQ refers to the resident’s answer to a different question, QQ, which does not mention the resident at all. Its truth value is settled before it is asked, and the resident only has to report it, honestly or not. The liar’s sentence, “this sentence is false”, refers to itself, and has no truth value to report.

The distinction between referring to another statement and referring to oneself has been a recurring line in this collection. A liar without a loop followed Stephen Yablo’s paradox, an infinite sequence of sentences each saying that all the later ones are false, which produces a contradiction without any sentence referring to itself — so the line is subtler than it looks. And the program that prints itself showed how to build genuine self-reference safely, by quoting a description and then applying it to its own quotation, a construction with the same two-step shape as the embedded question. The traveller’s question stays one step short of self-reference, and that step is exactly the difference between a puzzle with an answer and a paradox without one.

An unknown language

A question that works in an unknown language. True/yes/yes/ja/ja; True/yes/no/da/da; True/no/yes/da/ja; True/no/no/ja/da; False/yes/yes/da/ja; False/yes/no/ja/da; False/no/yes/ja/ja; False/no/no/da/da
Fig. 4 A god who always tells the truth or always lies, answering ja or da in a language whose words mean yes and no in an unknown order. Asked whether it would answer ja if asked Q, the god answers ja exactly when Q is true, in all eight rows.

Boolos’s puzzle, published in 1996 and credited by him to Smullyan, adds a second uncertainty. Three gods called A, B and C are, in some order, True, who always speaks truly, False, who always speaks falsely, and Random, whose answers are random. They understand the traveller’s language but answer only in their own, in which the words for yes and no are ja and da — in an unknown order. The traveller must determine the identities of all three gods by asking three yes-or-no questions, each put to one god.

The language is a second unknown of exactly the same kind as the lie. Write JJ for “ja means yes”. A god’s word is ja exactly when the answer it means to give agrees with JJ, so the language is another ↔\leftrightarrow applied to the answer, and the same trick removes it. Ask the god whether it would answer ja if asked QQ. The figure works through the eight combinations of god, language and the truth of QQ. The plain answer to QQ depends on all three; the embedded answer is ja exactly when QQ is true, every time. Algebraically, the answer word encodes Q↔T↔JQ \leftrightarrow T \leftrightarrow J, the embedded question applies the same two parities a second time, and each cancels with its copy. Two unknown negations cost nothing more than one, so long as each is applied twice.

Three gods, three questions

Three gods, three questions. 96 cases identified; e.g. TFR:000 TRF:100 FTR:010
Fig. 5 Boolos’s three gods identified with three questions. The first finds a god who is certainly not Random; the strategy is checked against all 6 arrangements, both meanings of ja and every sequence of the random god’s answers: 96 cases, all identified.

Random is the real difficulty, because the embedded question tames lies and languages but not randomness: a random answer to a cleverly built question is still random. The solution uses the first question to find a god who is not Random. Ask A, in the embedded form, “is B Random?”. If A is True or False, the answer is reliable: ja means B is Random, so C is not; da means B is not Random. If A is Random, the answer is noise — but then B and C are both not Random, so whichever of them the answer points to is safe anyway. Either way, the traveller now knows a god X who is not Random, and X’s embedded answers are reliable.

The second question asks X whether X is True, which identifies X, and the third asks X whether A is Random, which places Random; the third god is what is left. The figure draws the strategy and records its verification: every one of the six arrangements of the gods, with ja meaning yes and meaning no, and every way Random could answer whichever question it is asked — 96 cases, each played out with the answers computed word by word from the gods’ natures — and in every case the three gods are identified correctly.

Three questions are also necessary. Each answer is one of two words, so two questions can distinguish at most four situations, and there are six arrangements of the gods. That count, 22<3!≤232^2 < 3! \le 2^3, is the information-theoretic floor, the same argument as for any search by yes-or-no questions; the order of the questions studied how the order in which such questions are asked changes how many are needed to decide a function.

What the tables cannot show

The truth tables are exhaustive — four rows, sixteen questions, eight cases of language and lie, 96 cases for the three gods — and that is their strength and their limit. They verify that particular questions work; they do not show where the questions come from, which is the algebra of ↔\leftrightarrow, and they say nothing about questions that do not reduce to a truth function of the unknowns. A question asking a god whether its own answer to that very question will be da refers to itself, and a god of truth cannot answer it either way, just as the word that cannot describe itself cannot be classified. The tables assume every question has a definite truth value, and the puzzles’ cleverest variants violate that assumption deliberately.

The model of Random is also a choice. Here Random’s answer to each question is a fair coin, independent of the question. Boolos’s original wording allowed other readings, and the counting argument that three questions are needed depends on the gods answering every question with ja or da.

Still open in the variants: how few questions a paradox can buy

That counting argument has a loophole, and exploiting it is where the subject is still moving. If a question can be built that True and False cannot answer — because any answer would be self-refuting — then a god might fall silent, or explode, and silence is a third outcome. Brian Rabern and Landon Rabern showed in 2008 that with such questions Boolos’s puzzle can be solved in two questions, three outcomes each giving nine possibilities against six arrangements; Gabriel Uzquiano then posed harder variants, in which Random answers by choosing at random whether to lie, and asked how many questions those need. How many questions suffice when questions may be paradoxical depends on exactly what a god does when it cannot answer, and for several natural readings the minimum is not settled. The truth tables here sit at the boundary of that question: they decide everything a truth function can ask, and nothing a paradox can.

Lying twice

A knight’s answer to QQ is Q↔KQ \leftrightarrow K, so asking whether one would answer yes to QQ draws (Q↔K)↔K=Q(Q \leftrightarrow K) \leftrightarrow K = Q from knight and knave alike. Among the sixteen questions that depend on KK and QQ, exactly one does this, and the embedded question and the biconditional are two names for it. Every islander’s statement is the equation A↔SA \leftrightarrow S, decided by a table and, when built from biconditionals alone, by linear algebra mod 2. An unknown language is one more ↔\leftrightarrow, cancelled by the same trick, and three questions built on it — the first finding a god who is not Random — identify True, False and Random in all 96 cases. Two lies make a truth, and two parities cancel.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

Exclusive-orExhaustive searchInformationSelf-referenceTruth functionTruth table