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

Contents

    The Lunch Problem

    Source

     Galen Harris Valle, Teaching English in Asia, p85 Roger Gower, Speaking, OUP

    The Problem


    (Statement):

      (01): Anne, Betty and Cindy order either a cup of coffee or a cup of tea each after lunch.


      (02): If Anne has coffee then Betty orders the drink that Cindy orders.


      (03): If Betty orders coffee then Anne orders the drink that Cindy does not order.


      (04): If Cindy orders tea then Anne orders the drink that Betty orders.



    (Question): Who orders the SAME drink after lunch? Which drink?, and How do you know?

    Solution using the Propositional Calculus

    Symbols
    1. A::=Anne orders coffee,
    2. B::=Betty orders coffee,
    3. C::=Cindy orders coffee.
    4. P<->Q::= (P/\Q)\/(~P/\~Q), P if and only if Q.
    5. (it_can_be_shown) |- (P<->Q) = (P->Q)/\(Q->P) = (P->Q)/\(~P->~Q).

    Givens
  1. (01) |- ~A = Anne orders tea, ~B=Betty orders tea, ~C=Cindy orders tea.


  2. (02) |- (P1): A -> ( B<-> C ).
  3. (03) |- (P2): B -> ~(A<->C).
  4. (04) |- (P3): ~C -> (A<->B).

    Goal

    Verify that Anne orders tea.
  5. (P1, P2, P3) |- (goal): ~A.

    Proof of goal

     Strategy is to use RAA, Reducto Ad Absurdum.
    Let
    1. (P4): ~~A.
    2. (P4, notnote) |- (P5): A.
    3. (P5, P1, ife) |- (P6): B<->C.
    4. (above) |- (P11): ~B.

      Proof P11
      Let
      1. (P7): B
      2. (P7, P6, <->) |- (P8): C.


      3. (P7, P2, ife) |- (P9): ~(A<->C).
      4. (P5, P9, <->) |- (P10): ~C.
      5. (P8, P10) |- RAA

      (Close Let P7)

    5. (P6, P11, <->) |- (P12): ~C.
    6. (P12, P3, ife) |- (P13): A<->B.
    7. (P13, P11, <->) |- (P14): ~A.
    8. (P5, P14) |- RAA

    (Close Let P4)

    . . . . . . . . . ( end of section Solution using the Propositional Calculus) <<Contents | Index>>

    Solution using Boolean Algebra

    Symbols
    1. a::=Anne
    2. b::=Betty
    3. c::=Cindy
    4. Cx::=x orders Coffee
    5. Tx::=x orders tea

    Givens


  6. (01, translation2LPC) |- (1): for all x, Cx <> Tx.
  7. (02, translation2LPC) |- (2): if Ca then Cb = Cc.
  8. (03, translation2LPC) |- (3): if Cb then Ca <> Cc.
  9. (04, translation2LPC) |- (4): if Tc then Ca = Cb.

    Boolean Form

    Transform
    1. Use Boolean with additive notation: + for "either _ or _ " etc.
    2. PQ means P and Q
    3. -P means not P
    4. 0 means false and 1 means true.
    5. if P then Q becomes -P + Q.
    6. P = Q becomes PQ + (-P) (-Q).

    7. For all x, -Cx = Tx.
    8. CxTx = 0 and Cx+Tx = 1.


  10. (2) |- (2a): Ta + CbCc + TbTc.
  11. (3) |- (3a): Tb + CaTc + TaCc.
  12. (4) |- (4a): Cc + CaCb + TaTb.

    Reduction


  13. (2a, 3a) |- (5): (Ta + CbCc + TbTc)(Tb + CaTc + TaCc)(Cc + CaCb + TaTb),
  14. iff
  15. (Ta(Tb + CaTc + TaCc) + (Tb + CaTc + TaCc)CbCc + (Tb + CaTc + TaCc)TbTc)(Cc + CaCb + TaTb),
  16. iff
  17. (TaTb + TaCaTc + TaTaCc + TbCbCc + CaTcCbCc + TaCcCbCc + TbTbTc + CaTcTbTc + TaCcTbTc)(Cc + CaCb + TaTb),
  18. iff
  19. (TaTb + TaCc + TaCbCc + TbTc + CaTbTc)(Cc + CaCb + TaTb),
  20. iff
  21. (TaTb + TaCc + TaCbCc + TbTc + CaTbTc)Cc + (TaTb + TaCc + TaCbCc + TbTc + CaTbTc)CaCb + (TaTb + TaCc + TaCbCc + TbTc + CaTbTc)TaTb
  22. iff
  23. TaTbCc + TaCc + TaCbCc + TaTb + TaTbCc + TaTbTc,
  24. iff
  25. Ta(TbCc + Cc + CbCc + Tb + TbCc + TbTc),
  26. iff
  27. Ta(TbCc + Cc + CbCc + Tb),
  28. iff
  29. Ta(Cc + Tb).

    Conclusion

    Anne always orders tea and either Cindy orders coffee or Betty orders tea.

    . . . . . . . . . ( end of section Solution using Boolean Algebra) <<Contents | Index>>

    Confirmation

    There is a Prolog program [ lunch.plg ] that tries all possible combinations of tea and coffee and lists those that are compatible with the given facts.

    Glossary

  30. translation2LPC::=standard intuitive translation to the lower predicate calculus with equality.

    . . . . . . . . . ( end of section The Lunch Problem) <<Contents | Index>>

Formulae and Definitions in Alphabetical Order