80-110: The Nature of Mathematical Reasoning

Spring 1998

Class 17: 3/12/98

1. Fun with Knights, Knaves, and Portia

Truth tables are a beautiful illustration of a technique that make the confusing part of a logical brain twisters completely disappear. Raymond Smullyan is a logician who has analyzed hundreds of brain twisters like this one. On Smullyan's Island, everyone you will meet is either a Knight or a Knave. Knights always tell the truth, and Knaves always lie, but they cannot be distinguished by outward appearance.

Suppose you meet two fellows called A and B. A says: At least 1 of us is a Knave. What are A and B? This is hard to solve and confusing to present to someone even when you have. But with a truth table things are simple.

Let A stand for the sentence: A is a Knight

Let B stand for the sentence: B is a Knight

Then we can set up a truth table that reflects all the possibilities about A and B as well as the truth value of the claim A spoke in each situation.

Rows 1, 3, and 4 in this table are spurious, i.e., impossible, for the reasons I list to the right of the rows, and therefore row 2 is the only possibility left. So A must be a Knight and B a Knave.

Same set up, but this time A says: I am a Knave, or B is a Knight.

This time only row 1 is non-spurious, so both A and B are Knights.

In Shakespeare's Merchant of Venice, Portia has three caskets: one gold, one silver, and one lead. She tells prospective suitors that her portrait is in one of them, and that they must find which. In the first problem her caskets have the following inscriptions:

She tells the suitors that at most one of the inscriptions is true. One way to reason through this problem is to hypothesize each possibility and see which inscriptions are true. The portrait cannot be in the Gold casket, for if it were then the Gold inscription is true and the Silver inscription is true and then more than one inscription is true. If it is in the Lead casket, then the Lead inscription is true and the Silver inscription is true, which is impossible. If it is in the Silver casket, then only the Lead inscription is true, so it must actually be in the Silver casket.

Another way to see this reasoning is with a table that captures the logic of the situation:

The rows of this table, like a truth table, are exclusive and they exhaust all the possibilities. The columns are the statements, and the T and F represent the truth of the statements in the possible world(s) represented by the row. Thus, in rows 1 and 3, two inscriptions are true, and in row 2, only one if true. Thus row 2 is the only one consistent with Portia’s remarks, and if we were a clever suitor we would pick Silver. Here is another table (Table 2) that represents an entire truth table analysis.

Although I have mechanically generated all 8 rows of the truth table, many are spurious. Since the portait can only be in one casket, only rows 4, 6, and 7 need be considered, and they correspond, of course, to rows 1, 2, and 3 in Table 1.. In rows 4 and 7, more than one inscription is true, so row 6 must be the actual situation, and in row 6 the portrait is in the silver casket.

In the second Portia problem, the inscriptions are as follows:

And the corresponding truth table is:

This time Portia tells her suitors that at least one inscription is true and one false, and only row 4 satisfies this condition. Therefore the portrait is in the Gold casket.