Knights, knaves and truth tables
Tonight's idea
On the island every person is a knight, who only says true things, or a knave, who only says false things. You cannot tell them apart by looking, only by listening.
One fact does all the work. Whatever islander \(A\) says is true exactly when \(A\) is a knight. So "\(A\) is a knight" and "what \(A\) said" are both true or both false.
To use it, write \(A\) for the claim "\(A\) is a knight", and build the statement out of \(A\), \(B\) and three connectives. NOT flips true and false. AND is true only when both parts are. OR is true when at least one part is (so true even when both are). A truth table lists every combination, T for true and F for false:
| \(A\) | NOT \(A\) |
|---|---|
| T | F |
| F | T |
| \(A\) | \(B\) | \(A\) AND \(B\) | \(A\) OR \(B\) |
|---|---|---|---|
| T | T | T | T |
| T | F | F | T |
| F | T | F | T |
| F | F | F | F |
To solve a puzzle, write each speaker's statement as a column, then keep only the rows where the statement's value matches the speaker's own column. Those rows are the answers. If no row survives, the situation is impossible; if several survive, the puzzle has not told you enough.
Watch one: "At least one of us is a knave"
You meet \(A\) and \(B\). \(A\) says: "At least one of us is a knave."
By cases. If \(A\) were a knave, the statement would be false, so neither is a knave, so \(A\) is a knight. Contradiction. So \(A\) is a knight, the statement is true, and the knave must be \(B\).
By table. The statement is (NOT \(A\)) OR (NOT \(B\)). Fill the column and compare it with the \(A\) column:
| \(A\) | \(B\) | (NOT \(A\)) OR (NOT \(B\)) | matches \(A\)? |
|---|---|---|---|
| T | T | F | no |
| T | F | T | yes |
| F | T | T | no |
| F | F | T | no |
One row survives: \(A\) is a knight, \(B\) is a knave. Same answer, no cleverness required.
Your turn
- (a) Can anyone on the island say "I am a knave"? Explain. (b) \(A\) says "I am a knight." What have you learned about \(A\)?
- \(A\) says: "We are both knaves." Work out what \(A\) and \(B\) are, by cases.
- \(A\) says: "Exactly one of us is a knight." Write the statement as (\(A\) OR \(B\)) AND NOT (\(A\) AND \(B\)), fill in a four-row truth table, and find every row that matches. What can you be sure of?
- Three islanders. \(A\) says: "All three of us are knaves." \(B\) says: "Exactly one of us is a knight." Find what each of \(A\), \(B\), \(C\) is. (Start with \(A\). Then split on \(B\).)
Stretch: one question at the fork
At a fork, one road leads to the village. A stranger stands there, a knight or a knave, you do not know which. You may ask one yes-or-no question. Find a question whose answer tells you the road whatever the stranger is, and check it with a table of the four cases.
Answers
- (a) No. A knight would be lying, a knave would be telling the truth. Neither is allowed. (b) Nothing. A knight says it truthfully and a knave says it falsely; everyone on the island says it.
- If \(A\) were a knight the statement would be true, making \(A\) a knave. Contradiction. So \(A\) is a knave and the statement is false: they are not both knaves. Since \(A\) is one, \(B\) is a knight.
- Statement column, rows TT, TF, FT, FF: F, T, T, F. Matches \(A\) in rows TF and FF. So \(B\) is a knave for certain, but \(A\) could be either. The puzzle does not settle \(A\).
- \(A\) cannot be a knight (a knight cannot truthfully call itself a knave), so \(A\) is a knave and not all three are knaves. If \(B\) is a knight, there is exactly one knight, so \(C\) is a knave: consistent. If \(B\) is a knave, then \(C\) must be the knight (someone is), which makes exactly one knight, so \(B\)'s statement would be true: contradiction. Answer: \(A\) knave, \(B\) knight, \(C\) knave.
Stretch. Ask: "If I asked you whether the left road leads to the village, would you say yes?" A knight answers honestly about an honest answer. A knave lies about a lie, and two lies cancel. The four cases: knight/left: yes; knight/right: no; knave/left: yes; knave/right: no. "Yes" means left, whoever is speaking.