## Lewis Carroll's Five Liar Problem[From There are 5 friends, A, B, C, D and E, each of whom makes 2 assertions, so that it is possible for him to tell 2 Truths, or a Truth and Lie, or 2 Lies. A says: What is the condition, as to truth-telling and lying, of each of these five painfully-candid friends? [It is assumed that 'Either p or q' means that either p is the case and q is not; or q is the case and p is not.] There are ten assertions in the problem, each of which may be true or false. Our task is to assign truth-values to the assertions in a consistent fashion. The difficulty is as follows: taking (for example) A's first assertion, its truth (or otherwise) is There are 2 Consider this: there is A's first assertion - 'Either B or D tells a truth and a lie' - and there is the 'truth or otherwise' of this assertion. These are two different things. We can represent the 'truth or otherwise' of the assertion by what is called (by computer programming languages, for example) a So a=_ means 'A's first assertion is true'; a=O means 'A's first assertion is false'. In just the same way, let us assign Boolean variables to each of the remaining nine assertions, as follows: to A's second assertion, f; to B's two assertions, b and g; to C's, c and h; to D's, d and i; to E's, e and j. The assertion 'B tells a truth and a lie' can then be translated as either b=_ and g=O; or b=O and g=_ . This statement may be translated into an even more concise form, if we avail ourselves of the equivalence expression (see Development of the Equivalence Expression). Our more concise statement is simply [b|(g)] = _ ; this is shorthand for (bg)((b)(g)) = _ . Taking this a stage further, the assertion 'Either B or D tells a Truth and a Lie' can be converted, firstly, into the form either [b|(g)]=_ and [d|(i)]=O; or [b|(g)]=O and [d|(i)]=_ , and then, more concisely, into [ [b|(g)] | ([d|(i)]) ] = _ . Now for the 'tying in'. A's first assertion is true if and only if the statement just made is true. Since the only values that may be taken by the expression on the left-hand side of that statement are _ and O, the 'tying in' may be expressed by the following equation: a = [ [b|(g)] | ([d|(i)]) ] , or, [a| [ [b|(g)] | ([d|(i)]) ] ] = _ . The advantage of this last way of putting it may not be immediately apparent (but will emerge as we go on). For any assignment of values to the ten variables, this equation is one of the things we have to check. We may go on to treat A's second statement in a similar fashion. The value of the assertion 'C tells two lies' is (c)(h); for this expression takes the value _ if and only if both c and h take the value O (=false). The value of the assertion 'Either C or E (but not both) tells 2 lies' is ([(c)(h)|(e)(j)]); and f is tied in by the equation [f| ([(c)(h)|(e)(j)]) ] = _ . Eight more equations may be derived in a similar manner:
[b| ([ [a|(f)] | [c|(h)] ]) ] = _ We may now simplify each of these expressions by deploying the technology of the multiple equivalence expressions (see Development of the Equivalence Expression):
[a|b|g|d|(i)] = _ The condition that all ten of these expressions are void (i.e. have value _ ) can be re-expressed as the condition that the expression E that is their product is void. Here is a pictorial representation of E: The problem is to find the values of the variables (if any) that make E equivalent to no mark. You must admit that it would be hard to find a more parsimonious representation of the conditions of the problem! We now proceed to simplify E, as far as possible, using the methods of the CL-calculus. The idea is to avoid the wearisome task of going through all the 1024 possible assignments to the variables. To this end, we first apply the 'Case Analysis' Lemma, with respect to the letter a. (We chose a just because it happens to come first in the alphabet - and first in the problem!) E = ((a E We recall that E Simplifying, using the properties of the multiple equivalence expression, we get: From here on we treat E We do the same sort of thing, again and again. In each case we use the latest version of the factor as catalyst, so the steps describe a sort of ongoing evolution of the expression E The steps marked A and B make use of a couple of lemmas, both of which have the effect of reducing the number of compartments in an equivalence expression by one. These are as follows:
[a|ab] = (a(b)) .
[a|ab] = (a(ab)) ((a)ab) = (a(b)) (()ab) = (a(b)) ◊ Note the relationship of this lemma to Lemma 4 of Mutual Dominance. There are many variant forms of Lemma A, obtained by applying the identities [(a)|b] = ([a|b]) = [a|(b)]. For example, [a|(a)(b)] = ([(a)|(a)(b)]) = (((a)((b)))) = (a)b.
[ab|a(b)] = (a) .
Here now are the steps involved in the evolution of E With this last step we are really getting somewhere: one of our factors has been reduced to a simple CL-expression (no longer an equivalence expression), which turns it into a still more powerful catalyst. For now the letter j can be uncopied from any other factor, and likewise the expression (e). In other words, in the presence of factor 8, any occurrence of j can be replaced by _ , and any occurrence of e can be replaced by O. Before we exploit this power, we have a bit of tidying up to do. Factors 10 and 2 can both be transformed into the empty expression. Each of them vanishes: they have nothing more to tell us! So now our expression E This is We now set about simplifying the second expression, E Thus E Finally, E as a whole has been transformed into E = ((aE It will be seen that it is not impossible for E to be void (i.e. to reduce to the empty expression). It suffices for one or other of the inner expressions to be void. This gives rise to two solutions of the problem:
A's first assertion is true, their second, false; Thus A, B, C, E each tell a Truth and a Lie;
A's first assertion is false, their second, true; Thus A and E each tell a Truth and a Lie; It will be found that both solutions are indeed consistent with the conditions of the problem. With hindsight, we can see that our choice of a as the letter to use for 'case analysis' was actually rather fortunate, in that a= _ leads to one of the solutions, a = O to the other. If we had chosen c instead, c = _ would have led to no solution. Indeed, from our final form for E we can see that E ## Self-referenceNone of the friends makes a statement that refers directly to himself. But if A made a statement about B, and B made a statement about A, taken together the statements would amount to 'indirect' self-reference; and could amount to A says: B tells a Truth; Translated into symbols this says: [a|[b|_]] [b|[a|O]]. Transforming this 'problem-expression' by the usual rules it turns into: [a|b] [b|(a)] There are no values for a and b which can make the expression take the value _ . It's value is categorically O, indicating False. The conditions of the problem cannot be satisfied. This could have happened in the actual problem, but it didn't. Although there is plenty of self-reference in the problem, it is not vicious or ## AcknowledgementThis page was inspired by, and is really no more than a footnote to, William Bricken's article Lewis Carroll's Five Liars Puzzle. Bricken's purpose is to show that the problem, once translated into the language of Laws of Form, can be solved automatically by something called the 'LOSP Boolean Minimization Engine'. Mine is to show how it may be done manually by anyone who is sufficiently dedicated. I would describe the task as quite difficult, but not at all boring - not, at least, for anyone who is even a little entranced by the magic of the circle-and-letter form.
[1]Lewis Carroll, |