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

# 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>>