Forever Undecided
Page 3
2. If either one is a knight, then the statement he made is true, from which it in turn follows that Oona is on the island. Therefore, if either one is a knight, Oona is on the island. Thus the statement they both made is true, hence both are knights, so surely at least one is a knight. From this and the truth of the statement they made, it follows that Oona is on the island.
3. This is an example of what I call a metapuzzle: You are not told what B said, but you are told that from what A and B said, the logician was able to determine whether Oona was on the island. (If I had not told you that, then you couldn’t possibly solve the problem!)
I will first show you that if B had said: “A is a knave, and Oona is not on this island,” then the logician couldn’t possibly have solved the problem. So suppose that B had said that. Now, A couldn’t possibly be a knight, for if he were, then B would be a knight (as A said), which would make A a knave (as B said). Therefore A is definitely a knave. But now it could either be that B is a knight and Oona isn’t on the island, or that B is a knave and Oona is on the island, and there is no way to tell which. So if B had said that, the logician couldn’t have known whether Oona was on the island. But we are given that the logician did know, hence B didn’t say that. He must have said: “A is a knave and Oona is on this island.” Now let’s see what happens.
A must be a knave for the same reason as before. If Oona is on the island, we get the following contradiction: It is then true that A is a knave and Oona is on the island, hence B made a true statement, which makes B a knight. But then A made a true statement in claiming that B is a knight and Oona is on the island, contrary to the fact that A is a knave! The only way out of the contradiction is that Oona is not on the island. So Oona is not on this island (and, of course, A and B are both knaves).
4. Since all six natives said the same thing, then they are either all knights or all knaves (all knights, if what they said is true, and all knaves otherwise). Suppose they were all knights. Then it would be true that at least one knave on the island had seen Oona land, but this would be impossible, since none of them are knaves. Therefore they must all be knaves. Hence what they said is false, which means that no knave on the island saw Oona land that evening. But since all the natives are knaves, then no native at all saw Oona land that evening.
5. We will show that if A is a knave, we get a contradiction: Suppose A is a knave. Then his second statement was false, hence E must be a knight and C must be a knave. Since E is a knight, his statement is true, hence either D is a knave or C is a knight. But C isn’t a knight, so D must be a knave. Hence D’s statement was false, so either Oona is here today or she was here yesterday. But Oona was not here yesterday (because C said she was and C is a knave), hence she is here today. But this makes A’s first statement true, contrary to the assumption that A is a knave! Then A can’t be a knave; he must be a knight. Therefore A’s first statement was true, so Oona is on this island.
• 5 •
An Interplanetary Tangle
ON GANYMEDE—a satellite of Jupiter—there is a club known as the Martian-Venusian Club. All the members are either from Mars or from Venus, although visitors are sometimes allowed. An earthling is unable to distinguish Martians from Venusians by their appearance. Also, earthlings cannot distinguish either Martian or Venusian males from females, since they dress alike. Logicians, however, have an advantage, since the Venusian women always tell the truth and the Venusian men always lie. The Martians are the opposite; the Martian men tell the truth and the Martian women always lie.
One day Oona and her logician-husband visited Ganymede and were told about this club. “I’ll bet you I can tell the men from the women and the Martians from the Venusians,” said the husband proudly to his wife.
“How?” asked Oona.
“We’ll visit the club tonight, which is visitors’ night, and I’ll show you!” said the husband (whose name, by the way, was George).
1
They visited the club that night. “Now, let’s see what you can do,” said Oona somewhat skeptically. “That member over there. Can you tell whether he or she is male or female?” George then went over to the member and asked him or her a single question answerable by yes or no. The member answered, and George then determined whether the member was male or female, though he could not determine whether the member was from Mars or Venus.
What question could it have been?
2
“Very clever!” said Oona, after George had explained the solution.
“Now, suppose that instead of wanting to find out whether the member was male or female, you had wanted to find out whether he or she was from Mars or Venus. Could you have done that by asking only one yes-no question?”
“Of course!” said George. “Don’t you see how?”
Oona thought about it for a bit and suddenly saw how. How?
3
“If you are really clever,” said Oona, “you should be able to find out in only one question whether a given member is male or female and where the member is from. Let’s see you do both things at once using only one yes-no question!”
“Nobody is that clever!” replied George. Why did George say that? (This is essentially a repetition of the last puzzle of Chapter 2 of my book To Mock a Mockingbird.)
4
Just then a member walked by and made a statement from which George and Oona (who was by now getting the hang of things) could deduce that the member must be a Martian female. What statement could it have been?
5
The next member who walked by made a statement from which George and Oona could deduce that the member must be a Venusian female. What statement could it have been?
6
What statement could be made by either a Martian male, a Martian female, a Venusian male, or a Venusian female?
News soon spread through the club of George and Oona’s cleverness in applying logic to determine the sex and/or race of various members. The owner of the club, an American entrepreneur named Fetter, came over to George and Oona’s table to congratulate them. “I would like to try you on still other members,” said Fetter, “and see what you can do.”
7
Just then two members walked by. “Come join us,” said Fetter, who introduced them as Ork and Bog. George asked them to tell him something about themselves, and the two made the following statements.
ORK: Bog is from Venus.
BOG: Ork is from Mars.
ORK: Bog is male.
BOG: Ork is female.
From this information, George and Oona could successively identify both the sex and the race of each of them. What is Ork and what is Bog?
8
“You know,” said Fetter, after Ork and Bog had left, “that Martians and Venusians often intermarry, and we have several mixed couples in this club. Here is a couple approaching us now. Let’s see if you can tell whether or not it is a mixed couple.”
I don’t remember the couple’s first names, so I will simply call them A and B.
“Where are you from?” Oona asked A.
“From Mars,” was the reply.
“That’s not true!” said B.
Is this a mixed couple or not?
9
“Here comes another couple,” said Fetter. “Again I won’t tell you whether they are a mixed couple or not. Let’s see if you can figure out which one is the husband.”
We will call the two A and B. George asked: “Are you both from the same planet?” Here are their replies.
A: We are both from Venus.
B: That is not true!
Which one is the husband?
10
“Here is another couple,” said Fetter. “Again, I won’t tell you whether it is a mixed couple or not. Let’s see what will happen!”
This time I happen to remember their first names—they were Jal and Tork.
“Where are you each from?” asked George.
“My spouse is from Mars,” replied Tork.
“We are both from Mars,” said Jal.
This enabled George and Oona to classify both of them completely. Which is the husband and which is the wife, and which planet is each of them from?
SOLUTIONS
1. The simplest question that works is: “Are you Martian?” Suppose you get the answer yes. The speaker is either telling the truth or lying. If the former, then the speaker is really Martian, and being a truth-telling Martian, must be male. If the speaker is lying, then the speaker is really Venusian, hence is a lying Venusian, hence is again male. So in either case, a yes answer indicates that the speaker is male. A similar analysis (which I leave to the reader) shows that a no answer indicates that the speaker is female.
Of course the question “Are you Venusian?” works equally well; a yes answer then indicates that the speaker is female, and a no answer indicates male.
2. The question, “Are you male?” works. (I leave the verification to the reader.) Alternatively the question, “Are you female?” works as well.
3. The reason that it is impossible to design a yes-no question that will definitely determine whether a given member is male or female and whether the member is Martian or Venusian is that there are four possibilities for the member—a Martian male, a Martian female, a Venusian male, a Venusian female—but there are only two possible responses to the question: yes or no. And so with only two possible responses, one cannot determine which of four possibilities holds.
4. A simple statement that would work is: “I am a Venusian male.” Obviously the statement can’t be true, or we would have the contradiction of a Venusian male making a true statement. Hence the statement is false, which means that the speaker is not a Venusian male. Since the statement is false, the speaker must then be a Martian female.
5. This is a bit trickier: One statement that works is: “I am either female or Venusian.” (Note: Remember that either-or means at least one and possibly both; it does not mean exactly one.)
If the statement is false, then the speaker is neither female nor Venusian, hence must be a male Martian. But a male Martian does not make false statements, and so we get a contradiction. This proves that the statement must be true, hence the speaker must be either female or Venusian and possibly both. However, if she is female, she must also be Venusian, and if Venusian, also female, because truth-telling females are Venusian and truth-telling Venusians are female. Therefore the speaker must be both Venusian and female.
Incidentally, if the speaker had made the stronger statement, “I am female and Venusian,” it would be impossible to determine either the sex or the race of the speaker (all that could be inferred is that the speaker is not a Martian male).
6. One such statement is, “I am either a Martian male or a Venusian female”—or, even more simply, “I always tell the truth.” Any liar or truth teller could say that.
7. Suppose Ork told the truth. Then Bog would be both male and Venusian, hence Bog must have lied. Suppose, on the other hand, that Ork lied. Then Bog is neither male nor Venusian, hence Bog must be a Martian female, so again Bog must have lied. This proves that regardless of whether Ork told the truth or not, Bog definitely lied.
Since Bog lied, then Ork is neither from Mars nor female, hence Ork must be a Venusian male. Therefore Ork also lied, which means that Bog must be a Martian female. And so the solution is that Ork is a Venusian male and Bog is a Martian female (and all four statements were lies).
8. Since A claimed to be from Mars, then A must be male (as we saw in the solution of Problem 1), and hence B must be female. If A is truthful, then A really is from Mars, B lied, and being a lying female is also from Mars. If A lied, A is really from Venus, B told the truth, and being female is also from Venus. Therefore this is not a mixed couple; they are both from the same planet.
9. If A’s statement is true, then both are from Venus, hence A is from Venus and A must be female. Suppose A’s statement is false. Then at least one of them is from Mars. If A is from Mars, A must be female (since A’s statement is false). If B is from Mars, B must be male (since B’s statement is true), hence again, A must be female. And so A is the wife and B is the husband.
10. Suppose that Jal told the truth. Then the two really are both from Mars, hence Tork is from Mars and Tork’s statement that Jal is from Mars was true. We thus have the impossibility of a couple from the same planet both telling the truth. This cannot be, hence Jal must have lied. Therefore at least one of them is from Venus.
If Jal is from Mars, then it must be that Tork is the one from Venus. But then Tork told the truth in claiming that Jal is from Mars so Tork must be female, hence Jal must be male, and we have the impossibility of a male Martian making a false statement. Therefore Jal cannot be from Mars; Jal must be from Venus. Since Jal lied and is from Venus, Jal must be male. Also, since Jal is not from Mars, Tork lied. Hence Tork is a lying female, and thus from Mars.
In summary, Jal is a Venusian male and Tork is a Martian female.
• Part III •
KNIGHTS, KNAVES, AND PROPOSITIONAL LOGIC
• 6 •
A Bit of Propositional Logic
THE LIAR–truth teller puzzles of the last three chapters take on an added significance when looked at in terms of the subject known as propositional logic (as we will see in the next chapter). In this chapter we will go over a few of the basics—the logical connectives, truth tables, and tautologies. Readers already familiar with these concepts might pass right on to the next chapter (or perhaps just skim this one as a refresher).
THE LOGICAL CONNECTIVES
Propositional logic, like algebra, has its own symbolism, which is relatively easy to learn. In algebra, the letters x, y, z stand for unspecified numbers; in propositional logic, we use the letters p, q, r, s (sometimes with subscripts) to stand for unspecified propositions.
Propositions can be combined by using the so-called logical connectives. The principal ones are:
(1) ~ (not)
(2) & (and)
(3) v (or)
(4) ⊃ (if-then)
(5) ≡ (if-and-only-if)
An explanation of these follows.
(1) Negation. For any proposition p, by ~p we mean the opposite or contrary of p. We read ~p as “it is not the case that p”; or, more briefly, “not p.” The proposition ~p is called the negation of p; it is true if p is false and it is false if p is true. We can summarize these two facts in the following table, which is called the truth table for negation. In this table (as in all the tables that follow), we will use the letter “T” to stand for truth and “F” to stand for falsehood.
The first line of the truth table says that if p has the value T (i.e., if p is true), then ~p has the value F. The second line says that if p has the value F, then ~p has the value T. We can also write this as follows:
~T = F
~F = T
(2) Conjunction. For any propositions p and q, the proposition that p and q are both true is written “p&q” (sometimes “p∧q”). We call p&q the conjunction of p and q. It is true if p and q are both true, but false if either one of them is false. We thus have the following four laws of conjunction:
T & T = T
T & F = F
F & T = F
F & F = F
Thus the following is the truth table for conjunction:
(3) Disjunction. For any propositions p and q, we let pvq be the proposition that at least one of the propositions p or q is true. We read pvq as “either p or q—and possibly both.” (There is another sense of “or,” namely, exactly one, but this is not the sense in which we will use the word “or.” If p and q both happen to be true, the proposition pvq is taken to be true.) The proposition pvq is called the disjunction of p and q. Disjunction has the following truth table:
We see that pvq is false only in the fourth case—when p and q are both false.
(4) If-Then. For any propositions p and q, we write p⊃q to mean that either p is false or p and q are both true—in other words, if p is true, so
is q. We sometimes read p⊃q as “if p, then q,” or “p implies q,” or “it is not the case that p is true and q is false.” We call p⊃q the conditional of p and q. For the conditional, we have the following truth table.
We note that p⊃q is false only in the second line—the case when p is true and q is false. This perhaps needs some explanation: p⊃q is the proposition that it is not the case that p is true and q is false. The only way that it can be false is if it is the case that p is true and q is false.
(5) If-and-Only-If. Finally, we let p≡q be the proposition that p and q are either both true or both false, or, what is the same thing, that if either one of them is true, so is the other. We read p≡q as “p is true if and only if q is true,” or “p and q are equivalent.” (We recall that two propositions are called equivalent if they are either both true or both false.) The proposition p≡q is sometimes called the biconditional of p and q. Here is its truth table.
Parentheses. We need to use parentheses to avoid ambiguity. For example, suppose I write p&qvr. The reader cannot tell whether I mean that p is true and either q or r is true, or whether I mean that either p and q are both true or r is true. If I mean the former, I should write p&(qvr); if I mean the latter, I should write (p&q)vr.
Compound Truth Tables. By the truth value of a proposition is meant its truth or falsity—that is T, if p is true, and F, if p is false. Thus the propositions 2 + 2 = 4 and London is the capital of England, though different propositions, have the same truth value—namely, T.