CSE 463/563, Spring 2003 ========================================================================= HW 3 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 1: As usual, 0 points = no answer 1 point = incorrect answer 2 points = partial credit 3 points = correct answer ------------------------------------------------------------------------- SOLUTION POINTS A. 1. (Smoke -> Dumb) 0123 (parentheses omittable) 2. (~Smoke v Dumb) 0123 3. (~Dumb -> ~Smoke) 0123 4. Smoke (Smoke -> Fire) --------------- Therefore, Fire 0123 (2 pts for a single sentence; see comment below) total = 12 points COMMENT: A4 is *not* a conjunction. It consists of 3 separate, but related, sentences, i.e., as an argument or inference. This is different from a conjunction of the 3 sentences, which might be represented as follows: ((Smoke ^ (Smoke -> Fire)) -> Fire) The argument and this conditional sentence are related in the following way: In general, an argument of the form D|-a (that's ASCII for "delta |- alpha" :-) is valid (i.e., is such that "a" can by syntactically derived, preserving truth, from the wffs in D) iff the wff (&D -> a) is a theorem (where "&D" is the conjunction of the wffs in D). More perspicuously: "{d-1,...,d-n} |- a" is valid iff |-((d-1 ^...^ d-n) -> a) But the fact that you can "move" the wffs in D to the right-hand side of the turnstile (and, conversely, that you can move the antecedents of a conditional theorem to the left-hand side) is a meta-theorem of logic, and requires proof (which is beyond the scope of this course; for a proof, see almost any intro logic text). ------------------------------------------------------------------------- B.1. If there is smoke, then there is smoke. 0123 or: Smoke implies smoke. 2. If there is smoke, then there is fire. 0123 or: Where there's smoke, there's fire. 3. If, if there's smoke, then there's fire, then, if there's no smoke, then there's no fire 0123 or: if smoke implies fire, then no smoke implies no fire 4. (Either) there's smoke or there's fire or 0123 there's no fire. or: (Either) there's smoke or there's fire or it's not the case that there's fire. 5. If there's smoke and (there's) heat, then there's fire if and only if (either) if there's smoke, then there's fire or if there's heat, then there's fire. 0123 or: Smoke and heat imply fire iff either smoke implies fire or heat implies fire. 6. If, if there's smoke, then there's fire, then if there's smoke and (there's) heat, then there's fire. 0123 or: If smoke implies fire, then smoke and heat imply fire. 7. (Either) someone's big or someone's dumb or, if someone's big, then someone's dumb. 0123 NOTE: "Someone's big or dumb (etc.)" is INCORRECT. 8. (Either) someone's big and someone's dumb, or it's not the case that someone's dumb. 0123 total = 24 points ------------------------------------------------------------------------- C. To see the truth tables for these, try out the logic software from the Russell & Norvig text! It's all in /projects/rapaport/572/NEW. What follows is a script that gives the truth tables for this problem. (I have included a couple of typos I made, to show you that the symbol they use for disjunction is "|", and to show you how to get out of an error if you need to.) (Note also that R&N do truth tables in a slightly different order from the way I did in lecture.) The final answers follow the script. Script started on Tue 18 Feb 2003 09:39:36 AM EST adara/S03> cd /projects/rapaport/572/NEW adara/NEW> ls ./ agents/ doc/ logic/ uncertainty/ ../ aima.lisp* language/ planning/ utilities/ TAGS* code.tar* learning/ search/ 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 "smoke => smoke") -------------------------- $SMOKE $SMOKE => $SMOKE -------------------------- F T T T -------------------------- NIL USER(4): (truth-table "smoke => fire") -------------------------------- $SMOKE $FIRE $SMOKE => $FIRE -------------------------------- F F T T F F F T T T T T -------------------------------- NIL USER(5): (truth-table "((s => f) => (~s => ~f))") ---------------------------------------------------------------------------------- $S $F $S => $F ~ $S ~ $F (~ $S) => (~ $F) ($S => $F) => ((~ $S) => (~ $F)) ---------------------------------------------------------------------------------- F F T T T T T T F F F T T T F T T T F F F T T T F F T T ---------------------------------------------------------------------------------- NIL USER(6): (truth-table "s v f v ~f") Error: Bad syntax for infix expression: ($S $V $F $V (NOT $F)) Restart actions (select using :continue): 0: Return to Top Level (an "abort" restart) 1: Abort # [1] USER(7): :res USER(8): (truth-table "(s v f) v ~f") Error: Bad syntax for infix expression: ($S $V $F) Restart actions (select using :continue): 0: Return to Top Level (an "abort" restart) 1: Abort # [1] USER(9): :res USER(10): (truth-table "s | f | ~f") ------------------------------------------- $S $F $S | $F ~ $F ($S | $F) | (~ $F) ------------------------------------------- F F F T T T F T T T F T T F T T T T F T ------------------------------------------- NIL USER(11): (truth-table "((s ^ h) => f) <=> ((s => f) | (h => f))") ------------------------------------------------------------------------------------------------------------------------------------ $S $H $F $S ^ $H ($S ^ $H) => $F $S => $F $H => $F ($S => $F) | ($H => $F) (($S ^ $H) => $F) <=> (($S => $F) | ($H => $F)) ------------------------------------------------------------------------------------------------------------------------------------ F F F F T T T T T T F F F T F T T T F T F F T T F T T T T F T F F F F T F F T F T T T T T T F T F T T T T T F T T F T T T T T T T T T T T T T T ------------------------------------------------------------------------------------------------------------------------------------ NIL USER(12): (truth-table "(s => f) => ((s ^ h) => f)") --------------------------------------------------------------------------------- $S $F $H $S => $F $S ^ $H ($S ^ $H) => $F ($S => $F) => (($S ^ $H) => $F) --------------------------------------------------------------------------------- F F F T F T T T F F F F T T F T F T F T T T T F T F T T F F T T F T T T F T F T F T F T T T F T T T T T T T T T --------------------------------------------------------------------------------- NIL USER(13): (truth-table "(b | d | (b => d))") --------------------------------------------------- $B $D $B | $D $B => $D ($B | $D) | ($B => $D) --------------------------------------------------- F F F T T T F T F T F T T T T T T T T T --------------------------------------------------- NIL USER(14): (truth-table "(b ^ d) | ~d") ------------------------------------------- $B $D $B ^ $D ~ $D ($B ^ $D) | (~ $D) ------------------------------------------- F F F T T T F F T T F T F F F T T T F T ------------------------------------------- NIL USER(19): :ex ; Exiting Lisp adara/NEW> exit exit script done on Tue 18 Feb 2003 09:46:06 AM EST Now for the answers: 1. tautology 2. contingent 3. contingent 4. tautology 5. tautology 6. tautology 7. tautology 8. contingent Grading: a) for truth tables: 0123 each (total = 24 points) b) for taut vs. contra vs. cont.: 0 = missing 1 = incorrect 2 = incorrect, but correct for an incorrect truth table 3 = correct (total = 24 points) grand total = 48 points ========================================================================= GRAND TOTAL POINTS = 12 + 24 + 48 = 84 points Letter 463 both 563 ------ --- ---- --- A 80-84 A- 76-79 B+ 71-75 B 66-70 B- 62-65 C+ 57-61 C 48-56 29-56 C- 38-47 D+ 29-37 D 15-28 F 0-14