[CSUSB] >> [CompSci] >> [Dick Botting] >> [CS656/556 Course Materials] >> kns1
[Index] || [Contents] || [Grades] Tue Aug 5 11:45:00 PDT 2003

# Knights, normals and spies

Merlin's Book of Logic Puzzles p65#1

Knights tell the truth, spies lie, and normals do both. Merlin interviews three people: A,B,C: one spy, one knight and one normal but doesn't know who is which.

1. A says C is not a spy.
2. B says A is not a knight
3. B says B is a knight.

Who is the spy, knight and normal in A, B, and C.

# Notation

1. K(x)::= x is a knight,
2. S(x)::= x is a spy,
3. N(x)::= x is normal.
4. says(x,P)::=x says P.

# Axioms

Knights tell the truth, spies lie, and normals do both:
5. says(x,P)= (K(x) and P) or (S(x) and not P ) or N(x).

The above is not true of the real world, but fits the world of the puzzle well.

Three people a,b,c, with one K , one S and one N .

Some observations

1. |-if x=y then (N(x) and N(y)) = N(y) else (N(x) and N(y)) = false.
2. |-if x=y then (S(x) and S(y)) = S(y) else (S(x) and S(y)) = false.
3. |-if x=y then (K(x) and K(y)) = K(y) else (K(x) and K(y)) = false.

4. |-if x<>z then (N(x) and not N(z)) = N(x).
5. |-if x<>z then (S(x) and not S(z)) = S(x).
6. |-if x<>z then (K(x) and not K(z)) = K(x).

# The Three Statements

Net
1. says(a, not S(c)).
2. says(b, not K(a)).
3. says(c, K(b)).

(End of Net)

# Abreviations and Mapping to Boolean Algebra

Leave out "(", ")"
Use nothing for "and". PQ P and Q.
Use prefix "-" for "not". -P not P.
Use infix "-" as "and not" P-Q P*(-Q).
Use "+" for "or". P+Q P or Q.
For example
1. Kx = K(x) = x is a knight.
2. says(x,P) = KxP + Sx-P + Nx.
3. says(a, not Sc) = Ka-Sc + Sa-Sc + Na.
4. Sa-Sc = Sa.

Consider

(A): Ka-Sc + SaSc + Na
1. = Ka-Sc + 0 + Na
2. = Ka-Sc + Na.

(B): Kb-Ka + SbKa + Nb

3. =Kb + SbKa +Nb.

(C): KcKb + Sc-Kb + Nc

4. = Sc-Kb + Nc.

5. (A, C) |- (AC):
6. (Ka-Sc + Na) (Sc-Kb + Nc)
7. = Ka-ScScKb + NaSc-Kb + Ka-ScNc + NaNc
8. = 0 + NaSc-Kb + 0 + NaNc
9. = Na-KbSc + KaNc.
10. (AC, B) |-
11. (Na-KbSc + KaNc) (Kb + SbKa + Nb)
12. = Na-KbSc(Kb + SbKa + Nb) + KaNc (Kb + SbKa + Nb)
13. = NaNbSc + KaSbNc
14. = 0 + KaSbNc
15. = KaSbNc.

(Close Consider )
So
6. A is a knight, B is a Spy, and C is Normal.

# Check via Prolog

[ kns1.plg ]

### Formulae and Definitions in Alphabetical Order

• A (Label)
• B (Label)
• C (Label)
• K (Function definition)
• N (Function definition)
• says (Function definition)
• S (Function definition)