Logical Liars, Paradoxical Politicians

April 3, 2011 -- Lies, lies, lies. Prone to stretching logic, alleging deceit, and passing on gossip, politicians and the media that report on them are a natural setting for a few classic puzzles involving lying and self-reference.

Superficially political scenarios are also a bit easier to relate to than are the original ones, so I've dressed up some of these conundrums in this more modern garb.

Proceeding from simple to more difficult examples, I'll start with the very well-known liar paradox.

It can result, for example, if a news anchor were simply to announce, "This very statement I'm making is false." If his statement is true, then it's false, and if it's false, then it's true.

Less obvious and more realistic occurrences involving two or more people can also easily arise.

If Senator S says that Senator T's comment about the health care bill is false, there is nothing paradoxical about her statement. If Senator T says that Senator S's remark about the issue is true, there is nothing paradoxical about this statement either. But if we combine these two statements, we have a paradox.

It's not too hard to imagine a larger collection of such comments from a variety of people, each individually plausible, yet leading to an equally potent paradox.

Who's Telling the Truth?

Another old puzzle, again in a slightly different setting, concerns the reporter who has two very knowledgeable and sources, A and B.

In crucial political situations, A always tells the truth, B always lies, but the reporter has forgotten who is who. The reporter wants to know if Senator S is involved in a certain scandal and for whatever reason can ask only one of his sources, say by email, a single Yes or No question. What should it be?

Answer: One solution (there are others) is to ask either source the following question: Are the two statements -- 1) you are a truth-teller, and 2) the Senator is involved in this scandal -- either both true or both false? The remarkable thing about this question is that both truth-teller and liar will answer Yes if the Senator is involved.

If the source is a truth-teller, the source will answer Yes since both statements are true, and if the source is a liar, the source will answer Yes since only one of the two statements is true. A similar argument shows that both sources will answer No if the Senator is not involved.

Note that a completely useless question in this situation is, "Are you telling the truth about the Senator?" since both liars and truth-tellers would answer Yes.

Complicating the Situation

The answer above gives rise to a general principle. If you want to know if any proposition P is true and your source is a liar or a truth-teller, ask him if the two statements -- you are a truth-teller, and proposition P -- are either both true or both false. You can trust the answer even if you don't know whether it was given by a truth-teller or a liar.

The reporter might confront an intriguing, but more difficult problem, originally formulated in a slightly different scenario by logician Ray Smullyan. Assume the reporter again wants to know if Senator S is implicated in the scandal, but this time he has three knowledgeable informants, A, B, and C.

One is a truth-teller, one a liar, and one a normal person who sometimes lies and sometimes tells the truth. (They all know each other's status.) The reporter doesn't know who is who, but this time he can ask two Yes or No questions, each directed to a single informant, to determine Senator S's involvement. What questions should he ask and of whom should he ask them?

Answer: Since the previous puzzle showed that we can handle situations with truth-tellers and liars, our goal here is to use one of our questions to find an informant who isn't normal. Once we've located him, we've reduced the problem to the previous one.

Thus, the first question should be directed toward A and it should be: Are the following two statements -- you are a truth-teller, and B is normal -- either both true or both false?

Assume A answers Yes. If A is a truth-teller or a liar, then we know we can trust the answer, and B must be normal and hence C is not normal. If A is not a truth-teller or a liar, then he must be normal and again we conclude that C is not normal. Either way a Yes answer means C is not normal.

On the other hand, if A answers No and he is a truth-teller or a liar, then we can trust his answer and conclude that B is not normal. If A is not a truth-teller or a liar, then again we know that B is not normal since A is.

Either way a No means that B is not normal. If we get a Yes, we ask C the second question; if we get a No, we ask B the second question.

And what is the second question? It's the one posed in the first scenario involving only a truth-teller and a liar. Are the two statements -- 1) you are a truth-teller, and 2) the Senator is involved in this scandal -- either both true or both false?

Would There Were a Completely Dishonest Person

The moral of the story is that complete liars can be as informative as truth-tellers. Diogenes, who, as Greek legend had it, spent his life looking for a totally honest man, should have expanded the object of his search. A totally dishonest man would have done just as well. The problem is with those pesky critters who sometimes lie and sometimes tell the truth.

John Allen Paulos, a professor of mathematics at Temple University in Philadelphia, is the author of several best-selling books, including "Innumeracy," "A Mathematician Reads the Newspaper," and "Irreligion." He's on Twitter and his "Who's Counting?" column on ABCNews.com usually appears the first weekend of every month.