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

Contents

    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