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.

The only task that now remains is to translate the formal solution, which we have stated as a set of predicates of form (in zeroth-order logic), into natural language. Since the first question to ask is invariably the most intricate, and the second or third must be conditional on previous answer(s) in some way, it makes sense only to consider the verbal representation of the first as an exercise.

George Boolos (the populariser of the puzzle) proposed asking the following initial question.

Does da mean yes iff you are True iff B is Random?

When we recall that iff (if and only if), i.e. the biconditional connective, is logically equivalent to the XNOR operator, it is quite straightforward to see that this is of the above proposed form for . (Note that a triple of formulas connected either by a pair of XOR or pair of XNOR operators form the equivalent expression.)

The Wikipedia entry for the logic puzzle gives only a slight variation on the above that is fully equivalent;

Are an odd number of the following statements true: you are False, da means yes, B is Random.

Start by considering how the operations and change the truth value of . The former clearly inverts the value, while the latter leaves it unchanged. In order words, each XOR with a formula that is true inverts the overall truth value. Hence, considering an arbitrary number of formulae XORed together, we must deduce that if an odd number of statements are true, then the entire expression must in fact be true (and conversely if an even number of statements are true then the entire expression is false).

We now come to a somewhat different form of verbal solution, first proposed by T. S. Roberts (Journal of Philosophical Logic, 2001);

If I asked you Q’, would you say ja?

(We do not assume for now that is the same variable as used in the formal solution given above.)

A counterfactual may be thought of as a nested question; that is, an ‘if-then’ style of statement/predicate. Let us first consider the slightly simpler question: “If I asked you Q’, what would you answer?”. It should not be hard to see that this essential form of the counterfactual is equivalent to . The additional “would you say ja?” (as opposed to simply “what would you say?”) may be evaluated as a post-condition, equating to . Formally, we may infer

Since represents “ja” under our labelling, this formula is clearly equivalent to the expression for reached at the end of the previous section. Hence by equating the separate expressions, the two originally assumed to be independent are in fact rendered identical.

This concludes my article on The Hardest Logic Puzzle ever. I hope that I’ve given readers some appreciation for a formal (mathematical) solution to this intriguing puzzle, and indeed an insight into the equivalence of the various forms of solutions that one might posit from thinking about the problem holistically. No doubt, an exhaustive truth table would have proven the isomorphisms just as well, except that I felt they added little to overall understanding. If anyone has an additional alternative solution or general comments on the preceding, by all means please share via the comments section.