CSE 463/563, Spring 2003 ========================================================================= HW 4 ANSWERS & GRADING SCHEME ========================================================================= Note 1: Since I can't type a horseshoe or a triple bar in ASCII, I'll use "->" for the material conditional and "<->" for the biconditional. ------------------------------------------------------------------------- Note 2: As usual, 0 points = no answer 1 point = incorrect answer 2 points = partial credit 3 points = correct answer ------------------------------------------------------------------------- 1. To see the answer for this, try out the logic software from Russell & Norvig. It's all in /projects/rapaport/572/NEW. What follows is a script that gives the answers to this problem. Grading: 0123 Script started on Tue 25 Feb 2003 09:48:13 AM EST adara/563> cd /projects/rapaport/572/NEW adara/NEW> old-acl Allegro CL Enterprise Edition 5.0.1 [SPARC] (8/20/99 10:07) Copyright (C) 1985-1999, Franz Inc., Berkeley, CA, USA. All Rights Reserved. Warning: Unknown command-line option "!*" ;; Optimization settings: safety 1, space 1, speed 1, debug 2. ;; For a complete description of all compiler switches given the ;; current optimization settings evaluate (EXPLAIN-COMPILER-SETTINGS). USER(1): :ld aima.lisp ; Loading /projects/rapaport/572/NEW/aima.lisp ; Fast loading /projects/rapaport/572/NEW/utilities/utilities.fasl ; Fast loading /projects/rapaport/572/NEW/utilities/binary-tree.fasl ; Fast loading /projects/rapaport/572/NEW/utilities/queue.fasl ; Fast loading /projects/rapaport/572/NEW/utilities/cltl2.fasl ; Fast loading ; /projects/rapaport/572/NEW/utilities/test-utilities.fasl USER(2): (aima-load 'logic) ; Fast loading /projects/rapaport/572/NEW/agents/test-agents.fasl ; Fast loading ; /projects/rapaport/572/NEW/agents/environments/basic-env.fasl ; Fast loading ; /projects/rapaport/572/NEW/agents/environments/grid-env.fasl ; Fast loading ; /projects/rapaport/572/NEW/agents/environments/vacuum.fasl ; Fast loading ; /projects/rapaport/572/NEW/agents/environments/wumpus.fasl ; Fast loading /projects/rapaport/572/NEW/agents/agents/agent.fasl ; Fast loading /projects/rapaport/572/NEW/agents/agents/vacuum.fasl ; Fast loading /projects/rapaport/572/NEW/agents/agents/wumpus.fasl ; Fast loading /projects/rapaport/572/NEW/agents/algorithms/grid.fasl ; Fast loading /projects/rapaport/572/NEW/logic/test-logic.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/tell-ask.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/unify.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/normal.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/prop.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/horn.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/fol.fasl ; Fast loading /projects/rapaport/572/NEW/logic/algorithms/infix.fasl ; Fast loading ; /projects/rapaport/572/NEW/logic/environments/shopping.fasl T USER(3): (truth-table "(~(P ^ Q) <=> (~P | ~Q))") -------------------------------------------------------------------------------- P Q P ^ Q ~ (^ P Q) ~ P ~ Q (~ P) | (~ Q) (~ (^ P Q)) <=> ((~ P) | (~ Q)) -------------------------------------------------------------------------------- F F F T T T T T T F F T F T T T F T F T T F T T T T T F F F F T -------------------------------------------------------------------------------- NIL ------------------------------------------------------------------------- 2. Grading: Mythical? 0123 Magical? 0123 Horned? 0123 Total = 9 points Using the following syntax and semantics: MYTH means: the unicorn is mythical MORT means: the unicorn is mortal MAMM means: the unicorn is a mammal HORN means: the unicorn is horned MAGIC means: the unicorn is magical represent the argument as follows: 1. MYTH -> ~MORT 2. ~MYTH -> (MORT ^ MAMM) 3. (~MORT v MAMM) -> HORN 4. HORN -> MAGIC Then argue as follows (I will leave it to you to fill in the missing steps): 5. ~MYTH -> MAMM ; from 2 6. (MYTH v ~MYTH) -> (~MORT v MAMM) ; from 1, 5 7. HORN ; from 3, 6 8. MAGIC ; from 4, 7 So HORN and MAGIC can be inferred. But MYTH cannot: If MYTH is F and MORT, MAMM, HORN, and MAGIC are all T, then the premises are all T, but MYTH is F. So the truth-value of MYTH need not be T even if all the premises are T. There's software for you to try this out. Here's a sample run (which is a continuation of the run from problem 1, above): USER(4): (setf kb (make-prop-kb)) # USER(5): (tell kb "MYTH => ~MORT") T USER(6): (tell kb "~MYTH => (MORT ^ MAMM)") T USER(7): (tell kb "(~MORT | MAMM) => HORN") T USER(8): (tell kb "HORN => MAGIC") T USER(9): (ask kb "MYTH") NIL USER(10): (ask kb "~MYTH") NIL USER(11): (ask kb "MAGIC") T USER(12): (ask kb "HORN") T USER(13): (exit) ; Exiting Lisp adara/NEW> x exit script done on Tue 25 Feb 2003 09:52:58 AM EST ------------------------------------------------------------------------- 3. a) Grading: 0123 P Q R if P, then Q, else R - - - -------------------- T T T T T T F T T F T F T F F F F T T T F T F F F F T T F F F F b) Grading: 0123 Total = 6 points (if P then Q else R) is logically equivalent to ((P -> Q) ^ (~P -> R)) or (if P then Q else R) is logically equivalent to ((~P v Q) ^ (P v R)) Actually, if-then-else is ambiguous. A complete analysis of IF-THEN-ELSE is available at: http://www.cse.buffalo.edu/~rapaport/572/S02/ifthenelse.pdf ========================================================================= GRAND TOTAL POINTS = 3 + 9 + 6 = 18 points Letter 463 both 563 ------ --- ---- --- A 18 A- 17 B+ 16 B 15 B- 14 C+ 13 C 11-12 7-12 C- 9-10 D+ 7-8 D 4-6 F 0-3