Labyrinths of Reason (17 page)

Since Ben is a Liar, his second statement (“Charlie is a Liar”) must also be false. Charlie must be a Truth Teller.

That leaves Charlie’s statement. He says that Alice is a Truth Teller. We already know that Charlie is a Truth Teller, so this must be the case. The solution is that Alice is a Truth Teller, Ben is a Liar, and Charlie is a Truth Teller.

Is there a method to this solution? Well, sort of. The realization that no one says he’s a Liar helped. That revealed that Ben was a Liar, and then things fell into place.

But this method, if you can call it that, doesn’t apply to any and all Liars and Truth Tellers problems. Take this simple but novel Liars and Truth Tellers problem of Raymond Smullyan’s: A person of unknown tribe says, “I am a Liar, or 2 + 2 = 5.” What is the person’s tribe?

Now, the person is not saying he is a Liar. He is linking two statements with “or,” which means that at least one of the statements is true—
if
the speaker is telling the truth.

There are two possible hypotheses about the speaker: that he is a Truth Teller and that he is a Liar. If the speaker is a Truth Teller, what he says is true. We can depend on the statement that the speaker is a Liar or 2 + 2 = 5.

This
can’t
be the case. At least one of the two statements joined by “or” must hold for the compound statement to be true. There’s no way that 2 + 2 = 5 can be true so the Part about the speaker being a Liar would have to be true. That contradicts the assumption that the speaker is telling the truth.

All right, try the other hypothesis. Assume the speaker is a Liar. Then it is
not
the case that the speaker is a Liar or 2 + 2 = 5. For an
or
statement to be false, both of the component statements must be false. If just one were true, the
or
statement would be true. Therefore, saying “A or B is false” is the same as saying “both A
and
B are false.” If the speaker is a Liar, both these statements must
be false: “the speaker is a Liar” and “2 + 2 = 5.” Again we have a contradiction. If the speaker is Truth Teller, he must be Liar, and if he’s a Liar, he must be a Truth Teller.

In fact, Smullyan’s puzzle is a cleverly disguised form of the liar paradox. The “solution” is that no solution is possible. (Or as Smullyan put it, the only possible conclusion is that the problem’s author is not a Truth Teller.)

There is a method that works for any Liars and Truth Tellers problem, even those that turn out to be insoluble like Smullyan’s. For each of the islanders mentioned, there are two possible tribes: Truth Teller and Liar. Call any guess about each of the islanders’ tribes (like “Alice is a Liar, Ben is a Liar, and Charlie is a Truth Teller”) a “complete hypothesis.” For any problem, there is a fixed number of complete hypotheses about the islanders (2×2×2 or 8 in Goodman’s problem). All you need do is run through the hypotheses and see which are allowed by the statement of the puzzle.

In each case, you look for a contradiction, a reductio ad absurdum. For instance, in Goodman’s problem the assumption that all three are truthful leads to the conclusion that Ben would say something other than what he did say. That’s wrong, so cross that hypothesis off the list. After running through the eight possibilities, you would find that only one does not lead to contradiction: Truth Teller/Liar/Truth Teller for Alice, Ben, and Charlie, respectively. The problem is solved by the process of elimination.

“How often have I said to you that when you have eliminated the impossible, whatever remains, however improbable, must be the truth?” asked Sherlock Holmes in
The Sign of Four
. The process of elimination will solve many types of problems. But it is not always practical.

The trouble is, the process of elimination is slow. It’s slow because the number of hypotheses is often overwhelming.

A Boolean variable can be only true or false. That’s two possibilities per unknown. Each unknown doubles the total number of complete hypotheses. In a problem with three Boolean unknowns, the number of possible hypotheses is
2
³
or 8. In general, when there are
n
true-or-false unknowns, there are 2
ⁿ
possible complete hypotheses. For a Liars and Truth Tellers with a couple dozen islanders, the number of hypotheses would number in the millions.

We arrive now at the heart of deductive reasoning. The anecdotal structure of logic problems—what the problems seem to be “about”—is irrelevant to solution. Abstract away the window dressing, and what remains behind?

It is SATISFIABILITY. To complexity theory, this is the fundamental, irreducible kernel of logic. It is a “skeleton” that exists inside every problem of deduction.

We appreciate that the problem of adding 273 apples to 459 apples is essentially the same as the problem of adding 273 oranges to 459 oranges or that of adding 273 croquet mallets to 459 croquet mallets. The realization that all such problems are fundamentally the same is the basis of arithmetic.

Complexity theory was founded on the realization that many more complex problems are really the same. Arithmetic arose in the accounting problems of the ancients. Adding and subtracting bushels of wheat, someone realized, wasn’t any different from adding and subtracting mules or gold coins. Complexity theory was motivated by the problems confronting computer programmers in the 1960s and 1970s. These programmers discovered that many seemingly different problems were equivalent.

By convention, SATISFIABILITY is phrased as a yes-or-no question: Given a set of premises, are they compatible? Or: Do they describe a possible world? Or: Do they contain an irresolvable paradox?

A complete SATISFIABILITY problem includes a set of Boolean variables—fundamental statements whose truth or falsehood is initially unknown—and a set of logical statements about the Boolean variables. These statements may use the standard logical relations such as “or,” “and,” “not,” and “if … then.”

Often, each statement describes a single, ambiguous observation. Take Goodman’s Liars and Truth Tellers puzzle. Symbolize the three Boolean variables by the individuals’ names. The problem in essence says,

The first and trickiest statement corresponds to Ben’s assertion that Alice said she was a Liar. Alice is not a Truth Teller, provided that both Ben and Alice are Truth Tellers so that the statement can be trusted.

SATISFIABILITY problems can be difficult indeed. Lewis Carroll constructed ponderous logic puzzles in which the solver is required to deduce a single valid conclusion from a dozen or more nonsensical premises. Several are included in his unfinished textbook,
Symbolic Logic
. The problems are absurd travesties of scientific or mathematical reasoning, and amazingly difficult as well. The more difficult problems are beyond the limits of most people’s patience (though they have been solved by computer). The most difficult, discovered in his notes and not published until 1977, contains fifty premises.

One that has been extensively analyzed by hand and by computer is the notorious “pork-chop problem.” The puzzle is to derive the “complete conclusion,” a hypothesis that is compatible with and demanded by all the other statements.

We are used to thinking of logic as something that comes naturally. You expect to hit on a logic problem’s answer without really thinking about how you arrive at it. In Carroll’s problems, the statements are much too numerous and illogical to grasp at once. You have to resort to algorithms such as the tree diagrams and registers that Carroll described (or to computer programs).

The pork-chop problem has 11 Boolean variables (being earnest; eating pork chops; being a gambler; getting up at
5
A.M
.; having lost money; having a ravenous appetite; being likely to lose money; being lively; being a logician; being a man who had better take to cab-driving; sitting up till
4
A.M
.). There are
2
¹¹
or 2,048 distinct hypotheses about an arbitrary individual.

In asking for a conclusion, the pork-chop problem resembles a scientific investigation. It seems rather different from SATISFIABILITY, a yes-or-no question. That SATISFIABILITY is a yes-or-no question does not limit its generality, though. As in the game “20 Questions,” any information can be imparted by a series of yes-or-no answers. A logic problem posing an arbitrary question can be rephrased as one or more yes-or-no problems.

Let’s say you want to test the conclusion: “A man who eats pork chops is lively.” Step one is to take the original 15 premises as a SATISFIABILITY problem. Are they mutually compatible? The answer should be yes. Otherwise it’s not a fair problem. Then add the proposed conclusion as a 16th statement. Ask if the amended list of statements is still compatible (a second SATISFIABILITY problem). If so, the new statement is at least permitted by the original premises.

That doesn’t necessarily mean it is a valid conclusion. You could test “The moon is made of green cheese” as the 16th statement, and the set would of course be satisfiable. Since it says nothing about logicians, gamblers, or the other elements of Carroll’s nonsense, it cannot possibly introduce a contradiction.

A third SATISFIABILITY problem is needed to make sure that a hypothesis is
demanded
by the original premises. Replace the hypothesis with its negation, its logical opposite: “Not all men who eat pork chops are lively.” With this negation as the new 16th statement, check to see if the set is compatible.

If a hypothesis
or
its exact negation can be added to the premises without contradiction, then clearly the hypothesis is irrelevant. Both “The moon is made of green cheese” and “The moon is not made of green cheese” are compatible with the pork-chop problem, so neither is a valid deduction.

If instead a hypothesis is compatible with the premises and its negation is not, then it is a proper conclusion. (If a hypothesis is not compatible but its negation is, then the negation is a valid conclusion.)
²

Like all general problems, SATISFIABILITY is easy
sometimes
. It can be easy even when the number of Boolean variables and clauses is huge.

It is not always necessary to check every possibility, or even most of them. Often, many statements can be linked into sorites. If this is so, then that is so, and if that is so, then this is so … Such deduction has great power to “make sense” of a large number of statements.

Each link of a sorites can be expressed as an if …
then
statement concerning two Boolean unknowns. When the statements of a SATISFIABILITY problem mention just two Boolean variables each, the problem is easy. There are efficient methods for solving
the problem that are much faster than running through every possible hypothesis to find the right one.

Not all logic problems are so easy. When statements connect three or more Boolean unknowns, there is no general solution significantly faster than the process of elimination. Carroll’s pork-chop problem is notably hard because the premises link three or four Boolean variables (such as logicians, pork chop eaters, and money losers).

The increase in difficulty once statements concern three unknowns is evident in the “elevator problem”:

Six people are in an elevator. At least three of them are mutual acquaintances,
or
at least three are complete strangers to one another. Can you prove that this is
always
so?

This is true, but it is difficult to prove it “logically.” Common-sense reasoning about strangers and acquaintances doesn’t get you anywhere. You cannot deduce that A knows B from B knows C, since the problem says nothing about pairs of persons, only triplets.