~45 minutes. Solve three Knights-and-Knaves puzzles using Boolean algebra. The point is the method, not the answer.
Goal: solve 3 logic puzzles systematically using Boolean expressions and truth-table evaluation, not guessing.
Estimated time: 45 minutes
Prerequisites: Week 3 lecture (Boolean algebra, truth tables)
Background
In a Knights-and-Knaves puzzle:
- Knights always tell the truth. If a Knight says "P", then P is true.
- Knaves always lie. If a Knave says "P", then P is false (i.e., NOT P is true).
Let K_X = 1 mean "person X is a Knight" and K_X = 0 mean "person X is a Knave."
When person X says "statement S":
- If X is a Knight (K_X = 1): S must be true
- If X is a Knave (K_X = 0): NOT S must be true
- In both cases: K_X = S (the speaker's type equals the truth value of the statement)
Puzzle 1
You meet two people, Alice and Bob.
Alice says: "We are both Knaves."
Let K_A = 1 if Alice is a Knight, K_B = 1 if Bob is a Knight.
Alice's statement is "K_A = 0 AND K_B = 0" (both are Knaves).
Since K_A = truth value of Alice's statement:
K_A = (NOT K_A) AND (NOT K_B)
Try all 4 combinations of K_A and K_B. Which combination satisfies the equation?
| K_A | K_B | NOT K_A | NOT K_B | (NOT K_A) AND (NOT K_B) | Does K_A = RHS? |
|---|---|---|---|---|---|
| 0 | 0 | ||||
| 0 | 1 | ||||
| 1 | 0 | ||||
| 1 | 1 |
Who is the Knight? Who is the Knave?
Puzzle 2
You meet three people: Alice, Bob, and Carol.
Alice says: "Bob is a Knave." Bob says: "Carol is a Knight." Carol says: "I am a Knave." (Note: think carefully about what this statement means for the speaker.)
Write a Boolean equation for each statement:
- Alice's statement: K_A = NOT K_B
- Bob's statement: K_B = K_C
- Carol's statement: K_C = NOT K_C
Solve each equation independently first. Note that one of them is a contradiction (no solution in isolation; what does that tell you about Carol?). Then use the results to find K_A and K_B.
Puzzle 3
You meet two people, X and Y.
X says: "At least one of us is a Knave."
Can you determine whether X is a Knight or a Knave? Can you determine Y's type?
Translate "at least one of us is a Knave" into a Boolean expression: (NOT K_X) OR (NOT K_Y).
Apply the "K_X = truth value of statement" rule:
K_X = (NOT K_X) OR (NOT K_Y)
Evaluate all 4 combinations. Find which one(s) satisfy the equation. Write your conclusion.
Expected output / artifact
lab-3-2-logic-puzzles.txt with:
- The full truth table for each puzzle
- Your identification of who is a Knight/Knave in each case
- For Puzzle 3: your interpretation of what "at least one solution" vs "unique solution" means for the puzzle's answer
git add lab-3-2-logic-puzzles.txt
git commit -m "lab-3-2: knights and knaves logic puzzles"
Common pitfalls
- Puzzle 2 Carol: "I am a Knave" is a self-referential statement. If Carol is a Knight, her statement is true, which means she is a Knave. Contradiction. So Carol cannot be a Knight. Work from that constraint.
- Puzzle 3 conclusion: a unique solution to the equations is not always achievable; in some puzzles the information given is consistent with multiple solutions. When that happens, the puzzle is under-constrained; state which types are possible.
Stretch (optional)
Construct your own 2-person puzzle where exactly one solution exists. Write the two statements and verify that your truth-table evaluation gives exactly one satisfying assignment.
Lab 3.2 v0.1.