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.

Copyright 2018 by Bruce Ikenaga