Noldorin's Blog

Some time ago I wrote a post about the well-known logic puzzle of The Traveller’s Paradox and attempted to derive and justify a solution using the formal methods of propositional calculus (zeroth order logic). I return today to another intriguing and somewhat challenging problem within the realm of mathematical logic, albeit with what I hope is a much clearer approach and argument.

Although “The Hardest Logic Puzzle Ever” is scarcely a logically verifiable statement, the puzzle does indeed have a reputation as a rather tricky logic puzzle (at least among those encountered by laymen) and in any case has a non-trivial solution. The problem has some notable names attached to it, having originally been published in The Harvard Review of Philosophy by the logician George Boolos, but originating with the popular mathematician Raymond Smullyan, and altered slightly by the late computer scientist and AI pioneer John McCarthy.

The puzzle is commonly stated as follows.

Three gods A, B, and C are called, in no particular order, True, False, and Random. True always speaks truly, False always speaks falsely, but whether Random speaks truly or falsely is a completely random matter. Your task is to determine the identities of A, B, and C by asking three yes-no questions; each question must be put to exactly one god. The gods understand English, but will answer all questions in their own language, in which the words for yes and no are da and ja, in some order. You do not know which word means which.

At first glance, the problem may appear insurmountable due to the behaviour of god C, yet when we notice that his behaviour is not truly random, but rather only his veracity is — he otherwise follows all rules of logic. Boolos clarified: “Whether Random speaks truly or not should be thought of as depending on the flip of a coin hidden in his brain: if the coin comes down heads, he speaks truly; if tails, falsely.”.

Encountering this puzzle for the first time just in the past week, I made an effort to solve it on my own using a formal approach, as much as possible. As it turns out, I had some success, and hence thought I might share my reasoning here in the form of an article.

Let us begin by setting up the puzzle in the standard language of propositional logic (that is, Boolean algebra). We first define our useful propositional variables and predicates, which are

• , whether the da response corresponds to yes (absolute truth). $R$ is thus true if da means yes and ja means no, and false if da means no and ja means yes;
• , whether a given god (we consider them independently) is telling the truth. Note, this has a well-defined value even for Random (god C), since the context is a specific question and corresponding response.
• , the question (propositional predicate) that is asked to a given god.

Note that the latter two variables are semantically valid within only within individual questions. However, because we shall only utilise them within the context of question-response pairs, we need not concern ourselves with this.

There is a number of ways to convert the verbal problem statement into a set of formal logical expressions, but I shall adopt a fairly direct and unambiguous one here. We start by noting two simple facts regarding the truthfulness of a particular yes-no response .

Note that the biconditional () can be interpreted as material (syntactic) equality. This is precisely equivalent to the non-fundamental XNOR () operator in propositional logic. With a bit of manipulation it can be shown that

In other words, the yes-no of any response shall be the absolute (true) answer to the question XNOR whether one is asking a truth-teller.

We must then note the complication to the puzzle introduced by the fact we do not understand the language of the gods. ‘da’ could mean either yes or no and ‘ja’ conversely. To account for this, we can write two more statements specifically about the da-ja response (denoted ), which take virtually identical forms to before;

Unsurprisingly, this can be rewritten in the same way to use the XNOR operator;

Note that the value of represents the actual response; that is, it is the single observable of the logical system we have constructured to represent the puzzle.

While we could restrict ourselves to the use of the primitive Boolean operators (AND, OR, and NOT), the use of the XOR operator here facilitates things considerably, due to its special properties (notably commutativity and associativity) and the simplicity it gives our theorems.

Now, combining the two expressions (theorems) for and (this can be seen easily by considering the biconditional as equality), we can factor out the negations and use associativity of the XOR operator to write

We now have an easily manageable form for the da-ja response of a given god. The question now becomes, how do we extract the absolute truth value of the response from this observable variable? Clearly, one has no control over the and variables, which are predetermined by god being asked the question (and possibly by the flip of a coin) as well as the language of the gods. However, we do have direct and full control over the question to ask, the predicate .

In order to extra meaningful (absolute) truth value we first note that any propositional variable XNOR itself is false, thus disappearing from its containing expression. Given that we wish to eliminate the variables and from the final expression, we can decompose the predicate ; that is, give it an explicit form.

Let . Hence, we can say

At this point we almost have a solution to the puzzle. We have shown that one can obtain an accurate true-false response to any question we wish to ask any god. As long as we ask a question of the form , then a response (effectively to question ) of ‘da’ always corresponds to truth and ‘ja’ always to falsehood.

There are a number of ways to use this to reveal the identities of the three gods. The simplest and most direct, I feel, is to ask gods A and B whether they are Random. This definitively indicates the Random god (since if both answer in the negative, then it must be god C by elimination). One can then simply ask either of the remaining gods (not Random) whether he is True, deducing the identities of the True and False gods in a single question. Hence, we have totally and provably solved the puzzle within the desired three questions.

Read the rest of this entry »