15-110 Spring 2011
Class Notes:  Knights and Knaves (Satisfiability)

• Basics
• Knights:  Always tell the truth.
• Knaves:  Always lie.
• Problem:
• Given:  One statement each by N characters, each a knight or a knave.
• Task: Determine who is a knight and who is a knave.  
• Sample Problems:
• Knights and Knaves Repository (by Zac Ernst)
  
  
• Knights-and-Knaves as Satisfiability
  
1. Start with a Knights-and-Knaves problem.
• For example, here is problem #1 from the Knights and Knaves Repository:
  "A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie.You meet two inhabitants: Zoey and Mel. Zoey tells you that Mel is a knave. Mel says, `Neither Zoey nor I are knaves.'  So who is a knight and who is a knave?"
  
  
2. Assign a (capital) letter to each character.
• Here, we will assign Z for Zoey and M for Mel.
  
  
3. Let A mean "A is a Knight".  And so "not A" means "A is not a Knight" (that is, "A is a Knave").
• Thus, Z means "Zoe is a Knight", and M means "Mel is a Knight."
  
  
4. Let SA be A's statement, represented as a boolean expression.  Do this for each character.
• Zoey says:  "Mel is a Knave", so SZ = (not M) 
• Mel says:  "Neither Zoey nor I are knaves", so SM = (Z and M)
  
  
5. Consider:
1. We know this tautology:  "A is a Knight" or "A is not a Knight"
2. We can rewrite that tautology in boolean logic as:  A or (not A)
3. Now, if "A is a Knight", then SA must be true, too (since A never lies).  Thus A is equivalent to (A and SA).
4. Similarly, if "A is a Knave", then SA must be false (since A always lies).  Thus (not A) is equivalent to ((not A) and (not SA)).
5. If we make the previous two changes to A or (not A) from step 2, we get:...
        (A and SA) or ((not A) and (not SA))
6. This is the total information we get from character A's statement.  Call this IA (for Information from A's statement).  So:
        IA =  (A and SA) or ((not A) and (not SA))
   You might notice this is the same as saying:
      IA =  (A = SA) 
7. Continuing with the specific example:...
• IZ = (Z = SZ)
• IM = (M = SM)
  
  
6. Finally, to solve the puzzle, we require that the information we glean from every character's statements are all true at the same time.  If we call the call the Puzzle Solution PS, then PS = IA and IB and ... and IQ (for as many characters are in the puzzle).
• So in the example, PS = IZ and IM
  
  
7. Now we just use truth tables to find a truth assignment to the variables that makes PS true.  (This is satisfiability!)
• So in the example:
  

  M	Z	SM = (Z and M)	SZ = (not M)	IM = (M = SM)	IZ = (Z = SZ)	PS = IZ and IM
  0	0	0	1	1	0	0
  0	1	0	1	1	1	1
  1	0	0	0	0	1	0
  1	1	1	0	1	0	0

  
  
• So the answer is:
      Mel is a Knave.
      Zoe is a Knight.
  
  
• Let's check our work:
• "Zoey tells you that Mel is a knave"
  This is the truth (Mel is a knave), which is what we expect, since Zoe is a Knight.  Check!
  
• "Mel says, `Neither Zoey nor I are knaves."
  Since Zoe is a Knight, this is a lie.  But Mel is a Knave, so he is expected to lie.  Check!
  
  
• Another Example
1. Start with a Knights-and-Knaves problem.
• For example, here is problem #51 from the Knights and Knaves Repository:
  "A very special island is inhabited only by knights and knaves. Knights always tell the truth, and knaves always lie. You meet three inhabitants: Alice, Rex and Bob. Alice tells you that Rex is a knave. Rex tells you that it's false that Bob is a knave. Bob claims, `I am a knight or Alice is a knight.' So who is a knight and who is a knave?"
  
  
2. Assign a (capital) letter to each character.
• Here, we will assign A for Alice, B for Bob, and R for Rex.
  
  
3. Let A mean "A is a Knight".  And so "not A" means "A is not a Knight" (that is, "A is a Knave").
• Thus, A means "Alice is a Knight", B means "Bob is a Knight", and R means "Rex is a Knight"
  
  
4. Let SA be A's statement, represented as a boolean expression.  Do this for each character.
• Alice says:  "Rex is a knave", so SA = (not R)
• Bob says:  "I am a knight or Alice is a knight", so SB = (B or A)
• Rex says:  "It's false that Bob is a knave", so SR = B.  [ or, if you prefer to be more precise, (not (not B)) ]
  
  
5. We assign IA, IB, and IR as follows:
• IA = (A = SA)
• IB = (B = SB)
• IR = (R = SR)
  
  
6. We assign PS as follows:
• So in the example, PS = IA and IB and IR
  
  
7. Now we just use truth tables to find a truth assignment to the variables that makes PS true.  (This is satisfiability!)
• So in the example:
  

  A	B	R	SA= (not R)	SB= (B or A)	SR= B	IA= A = SA	IB= B = SB	IR= R = SR	IA and IB and IR
  0	0	0	1	0	0	0	1	1	0
  0	0	1	0	0	0	1	1	0	0
  0	1	0	1	1	1	0	1	0	0
  0	1	1	0	1	1	1	1	1	1
  1	0	0	1	1	0	1	0	1	0
  1	0	1	0	1	0	0	0	0	0
  1	1	0	1	1	1	1	1	0	0
  1	1	1	0	1	1	0	1	1	0

  
  
• So the answer is:
      Alice is a Knave.
      Bob is a Knight.
      Rex is a Knight..
  
  
• Let's check our work:
• "Alice tells you that Rex is a knave."
  This is a lie (Mel is not a knave), which is what we expect, since Alice is a Knave.  Check!
  
• "Rex tells you that it's false that Bob is a knave."
  This is the truth (since Bob is a Knight, it is false that he is a Knave), which is what we expect since Rex is a Knight.  Check!
• "Bob claims, `I am a knight or Alice is a knight.'"
  This is the truth (since Bob is a Knight, so it's irrelevant that Alice is a Knave), which is what we expect since Bob is a Knight.  Check!