473 Lesson Plan - Wed Oct 5 80 min 1:30 1. A* wrapup (10m) 1:40 2. Propositional logic (20m) 2:00 3. Translating sentences exercise (10m) 2:10 break (5m) 2:15 4. N-queens problem (20m) - translating into logic (10m) - solution by depth-first search (5m) - solution by local search (5m) - N-queens demo 2:35 5. Local Search - Intro (10) 2:45 5. Sudoku (5m) ------------------------------------------------------------ ------------------------------------------------------------ 1:40 2. Propositional logic (20m) Syntax: variables, literals, connectives AND, OR, NOT, IMPLIES truth tables rain v ~rain rain => cloud when is ~(rain => clouds) true? CNF Conversion: 1. Move negations in to literals by the rules: ~(A & B) ---> (~A v ~B) ~(A v B) ---> (~A & ~B) 2. Move disjunctions in the rule: (A & B) v (C & D) --> (A v C) & (A v D) & (B v C) & (B v D) MODEL of a formula SATISFIABILITY VALIDITY Theorem: (A => B) is VALID, written |= (A => B) iff every model of A is a model of B that is: A ENTAILS B, written A |= B Proof system: set of mechanical rules for deriving formulas, written A |- B A proof system is sound and complete: A |= B iff A |- B ------------------------------------------------------------ ------------------------------------------------------------ Translations What are the propositions? What are the sentences? If Michael is unqualified, he will have to flip burgers or run FEMA. MU => (FB v RF) or perhaps exclusive or: MU => ((FB & ~RF) v (~FB & RF)) If George nominates Harriet, then she will be a Supreme Court judge, unless the Democrats have some backbone. (GN => (~DB => HS)) reduces to: ~GN v DB v HS Correctly captures situation where ~DB and GN. But: also allows situation where DB, GN, and HS! So may want to strengthen to: (GN => (~DB <=> HS)) which reduces to: (~GN v DB v HS) & (~GN v ~DB v ~HS) ------------------------------------------------------------ ------------------------------------------------------------ N-Queens Translate into logic Qij == true if there is a queen on square i,j Lots of clauses to rule out attacks: (~Q11 v ~Q12) (~Q11 v ~Q13) Syntactic sugar: (all i . 1<=i<=8) (all j . 1<=j<=8) (all k . j