(Archive Question of the Week)
Logic puzzles can exercise our ability to reason carefully. Interestingly, the use of formal logic in doing so can actually get in our way, because such puzzles often have subtleties in their wording that are hard to capture in formal logic. Examining our thinking carefully can help us see wrong assumptions we are making.
The puzzle
In the following discussion from 2006, Eddie offered two conflicting solutions of an interesting puzzle, and Doctor Jacques helped him untangle his thinking. Here is the puzzle:
Can Rewriting P -> Q as ~Q -> ~P Lead to a False Conclusion? A teacher told the month of her birthday (let's call it M) to Peter, and the day of her birthday (let's call it D) to John. Then, the teacher showed a set of dates, and asked Peter and John which one was her birthday: 4 Mar, 5 Mar, 8 Mar 4 Jun, 7 Jun 1 Sep, 5 Sep 1 Dec, 2 Dec, 8 Dec Peter said, "If I don't know the answer, John doesn't know, too." John said, "At first I really didn't know, but now I know." Peter said, "I know, too." What is the teacher's birthday?
Two proposed solutions
Eddie first gave this solution:
The first time I thought the answer was 1 Sep. Peter said John couldn't know the teacher's birthday so Peter must have Mar or Sep, since all the days in those two months appear more than once in the list. Of course, John can also figure out that Peter has either Mar or Sep by Peter's argument. John knows the day and since he now knows the answer it can't be 5 since that day happens in both Mar and Sep. That means the day must be 1, 4 or 8. Lastly, Peter said he now also knows the answer. That would happen if and only if it was Sep since Mar would still have two possibilities, 4 and 8. So her birthday must be 1 Sep.
This is a typical way to work out this sort of puzzle. But then Eddie decided to restate one sentence in the problem as its contrapositive, which is supposed to be equivalent:
However, I know 'if P then Q' is equivalent to 'if Not Q then Not P'. But when I make that change, I get another date for the answer. "If I don't know the answer, John doesn't know, too" is changed into "If John knows the answer, I know the answer." Since only 7 and 2 directly let John know the answer, Peter could only have either Jun or Dec to make the argument true. But 7 or 2 can't be the day since John says he didn't know at first. Now that John knows it's either Jun or Dec, though, he knows the answer, so he must have 1, 4, or 8. But Peter also knows, so that can only happen if it's Jun since Dec still has two choices. So her birthday must be 4 Jun. I don't know why there will be two answers when I just change the first argument by a valid conversion: P -> Q = ~Q -> ~P. Or am I wrong somewhere in the process?
If I were doing this, I would now want to check each answer, to see whether it really works, and also to make sure I understand the problem. Let’s try that for this second answer. Suppose that the birthday is 4 Jun, so that Peter is told “Jun”, and John is told “4”. Can Peter say, “If I don’t know the answer, John doesn’t know, too [or either]”? Peter only knows the month is Jun; so as he sees it, John must have been told “4” or “7”. But Peter can’t be sure that John also doesn’t know, because if the number is 7, John does know. Therefore, he can’t say that, if (as is true) Peter doesn’t know, then John doesn’t know. So this answer is wrong.
Could Peter say, “If John knows the answer, I know the answer”? Not exactly. If John had said he knows, then Peter would know (because the number must be 7); but what John secretly knows can’t cause Peter to know now! The fact is, regardless, Peter doesn’t yet know.
Note in particular that Peter’s initial statement must be taken in the light of the current circumstances. He is not saying that, no matter what the truth is, if Peter doesn’t know, then John doesn’t know; his statement takes into account what he does know, not only the list of dates, but the month he was told. Otherwise, Peter could never have made this statement!
The error
Doctor Jacques first identifies the basic error: logic applies to precise statements, which must not have the ambiguity of ordinary English. There is a difference between a fact, a person knowing a fact, and hearing another person state the fact!
Disturbing, isn't it? At first sight, your two arguments are both correct.
The point is that we cannot blindly use propositional logic here. In propositional logic, a proposition is a statement that is either true or false, and we assume that, if the same proposition is used more than once, all occurrences have the same meaning (the same truth value).
However, in this case, a statement like "X knows the answer" does not satisfy that definition: such a statement can be false at some time and true some time later (this is the whole point of the riddle: at the beginning, nobody knows the answer, and, at the end, both Peter and John know it).
If we were to analyze the argument in a strictly formal way, we should consider several propositions like:
XKn : X (J, P) knows the answer at step n (1,2,3)
XSn : X says that he knows the answer at step n
and a few more, like "X knows at step m that Y
does not know at step n"...
We would also need to write down some implied statements explicitly, for example:
XK1 -> XK2 (once you know the answer, you don't forget it)
XSn -> XKn (our guys don't lie)
in addition to the statements that can be derived from the set of possible dates and the statements of Peter and John.
I didn't try to write that down in full (this could be interesting): the problem can be solved in a more informal way.
The implied statements are important in any puzzle of this type: the people don’t lie, they don’t forget, they use correct logic and don’t miss anything, and so on. Often such a puzzle will start out, “Two experienced logicians …”; but even then, they could make mistakes, couldn’t they? These puzzles are about perfect reasoning, not about real people.
But the central issue in Eddie’s question is that the statements also imply specific facts about sequencing: When a statement is made changes its meaning, because different information is available at different times. As I have noted before, elementary introductions to logic too often gloss over the difference between statements of formal logic and sentences in ordinary English, making it look as if you can ignore time issues (“then B is true” vs. “then B will be true”, for example) and apply logic recklessly.
The correct solution, in detail
Next, Doctor Jacques restated Eddie’s correct first argument, making its correctness clear:
I believe your first answer is the correct one. Let us be a little more explicit: At step 1, we know that Peter does not know the answer, since each possible month has more than one day, and nothing else has been said. By Peter's first statement (and the rule of modus ponens), this implies that John does not know the answer either, and the day cannot be 2 or 7. We also learn that Peter knows that John does not know the answer; this means that Peter knows that the day is neither 2 nor 7, and this rules out the months in which these days appear, i.e., Jun and Dec. At step 2, John first confirms that he did not know the answer (this does not tell us anything new). Now, John has just learned that the month is either Mar or Sep, and this is sufficient for him to deduce the answer. This means that the day (known to John) must appear exactly once in Mar or Sep, which leaves 1, 4, and 8. At step 3, Peter has learned that the day is 1, 4, or 8, and this is enough for him to know the answer. This means that exactly one of these days can appear in the month (known to Peter), and this rules out Mar, leaving only 1 Sep as the answer.
The error, in detail
Then he examined the error specifically:
Now, what is wrong with the second argument? It is quite correct that Peter could equivalently have said at step 1: "If John knows the answer, I know the answer" but this simply means that either John does not know the answer (meaning the day is neither 2 nor 7, which is true), or Peter knows the answer (which we know is false). However, the way you interpret it in your argument is as if Peter had said: "If I knew John knows the answer, I would know it too" (*) and this is completely different: the antecedent of that statement is not "John knows the answer", but "Peter knows that John knows the answer". By the way, it is interesting to note that, after step 2, Peter does indeed know that John knows the answer, and statement (*) would be true if Peter had said it at that time. The point is that statement (*) implies that the day must appear only once in the remaining possible months, and this has a different meaning at step 1 and step 2.
Eddie wrote back with further questions about the correct argument. The most useful is this:
First, you say: "We also learn that Peter knows that John does not know the answer; this means that Peter knows that the day is neither 2 nor 7, and this rules out the months in which these days appear, i.e., Jun and Dec." After I discussed this with some friends, we don't understand why Jun and Dec can be ruled out in Step 1. Isn't it possible that Peter got Jun and said the same 1st statement of "If I don't know the answer, John doesn't know, too."?
Doctor Jacques replied in depth:
First, we know--and everybody knows--that Peter does not know the answer at the beginning: the only thing Peter knows is the month, and, whichever month it is, there is always a choice of more than one day.
Assuming Peter does not lie, we have the argument:
"If P. does not know, J. does not know"
"P. does not know"
--------------------------------------
therefore,
"J. does not know"
Note that there is no problem of ambiguity here: "X does not know the answer" means the same thing throughout the argument.
Now, this argument tells us two things:
(1) the conclusion itself--John does not know.
This would be true if anybody else (for
example the teacher) has made that statement.
(2) the fact that the statement is made by Peter.
(1) tells us that the day (known to John) cannot be 2 or 7, since in either of these cases, there would only be one possible answer, and John would know it.
Note that, as far as John is concerned, we have a "necessary and sufficient condition": John knows the answer in step 1 if and only if the day is 2 or 7.
(2) tells us that, not only John does not know the answer, but Peter can be sure of it. Because of (1), this means that Peter knows that the day is neither 2 nor 7, and he can only be certain of that if neither of these days appears in the month he knows.
For example, if the month is Jun, the day can only be 4 or 7. It is true that, if the day were 4, John would not know the answer, and Peter's first statement would still be true. However, from Peter's point of view, it is also possible that the day is 7, in which case John would know the answer, and Peter's statement would be false. This means that, if the month is Jun, it is possible that John does not know, but Peter cannot be certain of it, and cannot therefore make his statement.
In fact, all this shows that there is an additional hidden assumption in this kind of problem.
We already assumed that the players do not lie, meaning their statements are true propositions (assuming we make them explicit enough to specify who knows what at what time).
In addition, we must assume that they are certain of what they are saying; formally, this would mean that their statements are not only true (which could happen by chance) but are also provable from the information available to the speaker at the time they are made; to put it otherwise, the players only assert things that they know to be true, not merely things that are true in fact. This is the assumption we use in the second part of the argument. In some similar problems (there are many of them...), this is made explicit by a statement like "the players are truthful and infinitely clever".