Truth Teller or Liar Problems

These problems will illustrate some of the logical concepts we've looked at, as well as illustrating some proof techniques that we'll look at in more detail later. These proofs are written entirely in words, so for the moment we don't need to worry about the presentation details associated with mathematical symbols.

The general setup: You're on an island where each inhabitant is a truth-teller or a liar. Truth-tellers always tell the truth; liars always lie. You're given some information about some people, usually in the form of statements they make. You're asked to determine whether each person is a truth-teller or a liar. In some cases, it may be impossible to determine what everyone is, or the situation may be impossible.

Example. You're on an island where each inhabitant is a truth-teller or a liar. Truth-tellers always tell the truth; liars always lie. Calvin and Phoebe are on the island.

Phoebe says: "If 34 is odd, then I am a truth-teller."

Calvin says: "Phoebe is a liar."

Determine whether each person is a truth-teller or a liar.

(In this problem, I notice that I can determine the truth or falsity of the statement "34 is odd" without knowing anything about Phoebe or Calvin. So I'll start with it and see what follows from it.)

Since "34 is odd" is false, the "if" part of Phoebe's statement is false. Hence, Phoebe's statement is true. Therefore, Phoebe must be a truth-teller.

Now Calvin says "Phoebe is a liar", and that is false, since I just showed that Phoebe is a truth-teller. Therefore, Calvin is a liar.

Thus, Phoebe is a truth-teller and Calvin is a liar.

Example. You're on an island where each inhabitant is a truth-teller or a liar. Truth-tellers always tell the truth; liars always lie. Calvin and Phoebe are on the island.

Calvin says: "One or both of us is a liar."

Determine whether each person is a truth-teller or a liar.

Suppose Calvin is a liar. Then the statement "One or both of us is a liar" is true, contradicting the fact that Calvin is a liar.

Hence, Calvin is a truth-teller. Therefore, his statement is true, and at least one of them is a liar. Since it isn't Calvin, it must be Phoebe.

Thus, Calvin is a truth-teller and Phoebe is a liar.

Here are some general ideas for solving these problems.

1. If there are statements whose truth value you know (like "34 is odd"), begin with that information and see what you can conclude. In the first example, pursuing that led to the conclusion that Phoebe had to be a truth teller. I did not need to take cases, as I did in the second example.

2. If there are no statements whose truth values you know, you can take cases: that is, you assume in a first case that one of the statements is true, then you assume in a second case that it is false. Equivalently, you assume a statement for a first case, and assume its negation for a second case. In the last example, I considered the cases "Calvin is a liar" and "Calvin is a truth teller".

In fact, assuming that "Calvin is a liar" leads to a contradiction, which means the first case is impossible. So I know the only possible case is "Calvin is a truth teller". I don't make any assumptions about Phoebe until I've determined all I can based on the assumption I'm making about Calvin.

3. You must ensure that all possibilities are covered. For example, the cases "Calvin is a liar" and "Calvin is a truth teller" cover all possibilities. Regardless of whether Phoebe is a truth teller or a liar, one of these two things is true about Calvin.

4. Observe that these solutions are written entirely in words: We aren't using truth tables here. You should avoid using symbols unless they are necessary. Mathematics does not necessarily require the use of symbols!

It is possible that a problem like this can't be solved, for either of the following reasons:

(a) There isn't enough information to determine what all the characters are.

(b) The given situation is impossible: All the cases lead to contradictions.

See if you can come up with problems of these two types.

Truth-teller and liar problems (and more complicated variants) were popularized by the logician Raymond Smullyan, who wrote a number of books with problems like this (see [1], for example).

[1] Raymond Smullyan, What is the name of this book. New York: Dover Publications, 2011.

Contact information