3
$\begingroup$

On an island, every native is either a knight, who always tells the truth, or a knave, who always lies. You meet 4 natives, A, B, C, and D. This is what they say:

  • A: "C is a knight iff D is a knight"
  • B: "A and C are not both knights"
  • C: [This person has a speech disorder. You can tell from his gestures that he is saying something about B and D, and that he is trying to use 1 of 4 logical connectives: and, or, if...then, iff. You can't tell if he is identifying B or D as knights or knaves. In other words, C said one of the things in this set: $\{B,\neg B\} \times \{\wedge, \vee, \rightarrow, \leftrightarrow\} \times \{D,\neg D\}$ .]
  • D: [Says nothing]

Question: What is D?


My attempt at answering this question: Let $A$ be "A is a knight" and $\neg A$ be "A is knave". Same pattern for the other three.

  • $A \leftrightarrow (C \leftrightarrow D)$
  • $B \leftrightarrow (\neg (A \wedge C))$

Now I'm stuck. There are 16 possibilities for what C could have said. Do I need to try every single one of them until something works?

$\endgroup$
  • $\begingroup$ When you write about C that "You can't tell if he is identifying B or C as knights or knaves", just after having written that C "is saying something about B and D", I assume you meant to write about C that "You can't tell if he is identifying B or D as knights or knaves". Right? $\endgroup$ – J Marcos Sep 21 '14 at 3:05
  • $\begingroup$ Further, there is obviously a number of things that C could have meant to say, but some of them would not be enough for the kind of D to be determined. So, for deterministic solutions to be available to your problem, I understand you should postulate that the statement of the problem conveys enough information for one to uncover what kind of native D is (you might add to it the information that there was some logician present at the scene who overheard what C said and was then able to determine the kind of D). Do you accept that? If you do, the problem will turn out to be indeed solvable! $\endgroup$ – J Marcos Sep 21 '14 at 3:08
  • $\begingroup$ Yes! You are absolutely right. $\endgroup$ – FutureTrillionaire Sep 21 '14 at 13:55
1
$\begingroup$

Let us postulate that the events unfolded in such a way as to convey to some logician present at the scene enough information to uncover what kind of native D is. To that effect, one might for instance add to the above setup the information that in that meeting with the four natives I was able to determine the kind of D immediately after hearing what A, B and C said.

For ease of reference, let's call (*) the assumption that the statement $E(B,D)$ made by C has the form $\{B,\neg B\} \times \{\wedge, \vee, \rightarrow, \leftrightarrow\} \times \{D,\neg D\}$.

In view of the above postulate, as we will see, there are only three things that C could have said about B and D, namely:

(K1) "if B is a knave, then D is a knave"
(K2) "both B and D are knights"
(K3) "B is a knight iff D is a knight"

From all these statements one may conclude that D is a knave (and B is a knight), and from all other statements of the form (*) the status of D remains undecided. Moreover, if C said (K1), then one may also conclude that C is a knight (and that A is a knave); otherwise, if C said either (K2) or (K3), then C is a knave (and A is a knight).

In any case, the precise statement made by C does not matter much to the solution, as long as a solution is guaranteed to exist by the above postulate.


Indeed, note first that there are precisely four situations in which both $A\leftrightarrow(C\leftrightarrow D)$ and $B\leftrightarrow(\neg(A\land C))$ are true, namely, the two situations in which D is a knight, A and C are of one and the same kind and B is of the opposite kind, and the two situations in which $D$ is a knave, B is a knight, and A and C are of different kinds. To sum up, we have one of the following four situations:

(S1) $D\land(A\land C)\land \neg B$
or
(S2) $D\land(\neg A\land\neg C)\land B$
or
(S3) $\neg D\land(A\land\neg C)\land B$
or
(S4) $\neg D\land(\neg A\land C)\land B$

Note also that if C said $E(B,D)$, for some expression $E$ involving $B$ and $D$, then $C\leftrightarrow E(B,D)$ is true, that is, the sentence that says that C is a knight has the same value of the sentence $E(B,D)$.

Now, the kind of D could only be determined if something had been said by C to the effect that either situations (S1) and (S2) were simultaneously ruled out, or else situations (S3) and (S4) were simultaneously ruled out. To rule out both (S3) and (S4) one would have to make the sentence $C\leftrightarrow E(B,D)$ false in both situations. This is impossible, as (S3) and (S4) agree in what they say about B and about D, and yet disagree about the kind of C. So, it must be the case that (S1) and (S2) have been ruled out by what C said, that is:

(R1) $E(B,D)$ is true in situation (S1), where $C$ is false,
and
(R2) $E(B,D)$ is false in situation (S2), where $C$ is true.

As it has been remarked, (S3) and (S4) exclude one another concerning the kind of C. There are thus two cases to consider:

[Case 1] if $C$ is false, then the following holds good:

(Ra) $E(B,D)$ is false in (S3) but true in (S4)

In view of our adherence to format (*), conditions (R1)+(R2)+(Ra) together imply that $E(B,D)$ is equivalent to $\neg B\to \neg D$ (the other possibility sanctioned by these conditions would be equivalent to $B$, not having thus the right format).

[Case 2] if $C$ is true, then the following holds good:

(Rb) $E(B,D)$ is true in (S3) but false in (S4)

Conditions (R1)+(R2)+(Rb) together imply that $E(B,D)$ is equivalent either to $B\land D$ or to $B\leftrightarrow D$.

The above statements correspond respectively to (K1), (K2) and (K3), in the first paragraph above.


$\endgroup$
  • $\begingroup$ Yes, your postulate is correct! The original wording of my homework had this: "D: [just looks at you, expecting you to figure out what he is from what C said, which he apparently understood.]" I wasn't sure why my professor didn't just write "D: [Says nothing]" (like I did in my wording of the question), but now I understand. $\endgroup$ – FutureTrillionaire Sep 22 '14 at 4:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.