(cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page i — #2 (cid:2) (cid:2) Thinking as Computation A First Course (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page ii — #3 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page iii — #4 (cid:2) (cid:2) Thinking as Computation A First Course Hector J. Levesque TheMITPress Cambridge,Massachusetts London,England (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page iv — #5 (cid:2) (cid:2) (cid:2)c 2012MassachusettsInstituteofTechnology Allrightsreserved.Nopartofthisbookmaybereproducedinanyformbyanyelectronicor mechanical means (including photocopying, recording, or information storage and retrieval) withoutpermissioninwritingfromthepublisher. MITPressbooksmaybepurchasedatspecialquantitydiscountsforbusinessorsalespromo- tionaluse.Forinformation,[email protected] SalesDepartment,TheMITPress,55HaywardStreet,Cambridge,MA02142. ThisbookwassetinPalatinobytheauthorusingtheLATEXdocumentpreparationsystem. PrintedandboundintheUnitedStatesofAmerica. LibraryofCongressCataloging-in-PublicationData Levesque,HectorJ.,1951– Thinkingascomputation:afirstcourse/HectorJ.Levesque. p. cm. Includesbibliographicalreferencesandindex. ISBN978-0-262-01699-5(hardcover:alk.paper) 1.Computationalintelligence. I.Title. Q342.L48 2012 006.3—dc23 2011026394 10 9 8 7 6 5 4 3 2 1 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page v — #6 (cid:2) (cid:2) For the late RayReiter, whogotmetothinking (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page vi — #7 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page vii — #8 (cid:2) (cid:2) Contents Preface xiii Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Overviewofthebook. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi Guideforthecourseinstructor . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii Guideforthestudent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xix Acknowledgments xxi 1 ThinkingandComputation 1 1.1 Thinking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.1.1 Whatisthinking? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Computation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2.1 Symbolsandsymbolicstructures. . . . . . . . . . . . . . . . . . . 4 1.2.2 Whatiscomputation? . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2.3 Somearithmeticprocedures . . . . . . . . . . . . . . . . . . . . . 5 1.2.4 Thelesson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3 Thinkingascomputation . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.3.1 Leibnizandhisidea . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3.2 Propositionsvs.sentences . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.3 Usingwhatisknown:Thewebofbelief . . . . . . . . . . . . . . 16 Wanttoreadmore? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Exercise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 AProcedureforThinking 23 2.1 Atomicandconditionalsentences . . . . . . . . . . . . . . . . . . . . . . 23 2.2 Logicalentailment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.3 Back-chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.1 Usingvariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3.2 Tracingtheback-chaining . . . . . . . . . . . . . . . . . . . . . . . 28 2.4 Variablesinqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.4.1 Onecomplication:Renamingvariables . . . . . . . . . . . . . . . 31 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page viii — #9 (cid:2) (cid:2) viii Contents 2.4.2 Anothercomplication:Backtracking . . . . . . . . . . . . . . . . . 33 2.4.3 Amorecomplexquery . . . . . . . . . . . . . . . . . . . . . . . . 34 2.5 Whyisback-chaininggood?. . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.5.1 Gettingstuckinaloop. . . . . . . . . . . . . . . . . . . . . . . . . 37 Wanttoreadmore? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3 ThePrologLanguage 41 3.1 Prologprograms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 Prologqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2.1 Queriesandtheiroutcomes . . . . . . . . . . . . . . . . . . . . . . 46 3.2.2 Conjunctivequeries . . . . . . . . . . . . . . . . . . . . . . . . . . 48 3.2.3 Negationinqueries . . . . . . . . . . . . . . . . . . . . . . . . . . 49 3.2.4 Tracingtheback-chaining . . . . . . . . . . . . . . . . . . . . . . . 50 3.2.5 Instantiatedanduninstantiatedvariables . . . . . . . . . . . . . . 52 3.2.6 Equalityinqueries . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.3 Prologback-chaining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.3.1 Unification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.3.2 Renamingvariables . . . . . . . . . . . . . . . . . . . . . . . . . . 58 ∗ 3.3.3 Back-chainingrevisited . . . . . . . . . . . . . . . . . . . . . . . . 58 Wanttoreadmore? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4 WritingPrologPrograms 63 4.1 ThetruthinProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.1.1 Thetruth,andnothingbut . . . . . . . . . . . . . . . . . . . . . . 63 4.1.2 Thewholetruth. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.2 Ablocksworld . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.3 RecursioninProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 ∗ 4.4 Mathematicalinduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.5 Nonterminatingprograms . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.6 Amorecomplexpredicate . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 ∗ 4.6.1 Recursionandtermination,reconsidered . . . . . . . . . . . . . . 75 4.7 EfficiencyinProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Wanttoreadmore? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) (cid:2) “run” — 2011/9/8 — 18:05 — page ix — #10 (cid:2) (cid:2) Contents ix 5 CaseStudy:SatisfyingConstraints 85 5.1 Constraintsatisfactionproblems . . . . . . . . . . . . . . . . . . . . . . . 86 5.1.1 Generate-and-test . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 5.1.2 Variables,domains,constraints . . . . . . . . . . . . . . . . . . . . 89 5.1.3 OutputinProlog . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5.2 Afirstexample:Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.2.1 TheanonymousvariableinProlog . . . . . . . . . . . . . . . . . . 91 5.2.2 Sudokuasconstraintsatisfaction . . . . . . . . . . . . . . . . . . . 92 5.2.3 Searchspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 5.2.4 Guessedvaluesandforcedvalues . . . . . . . . . . . . . . . . . . 95 5.3 Asecondexample:Cryptarithmetic . . . . . . . . . . . . . . . . . . . . . 96 5.3.1 ArithmeticinProlog . . . . . . . . . . . . . . . . . . . . . . . . . . 96 5.3.2 Cryptarithmeticasconstraintsatisfaction . . . . . . . . . . . . . . 99 5.3.3 Minimizingtheguesswork:Tworules . . . . . . . . . . . . . . . . 101 ∗ 5.4 Athirdexample:Theeightqueens . . . . . . . . . . . . . . . . . . . . . . 103 5.5 Afourthexample:Logicproblems . . . . . . . . . . . . . . . . . . . . . . 107 5.5.1 Hiddenvariables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 ∗ 5.5.2 Amorecomplexlogicproblem . . . . . . . . . . . . . . . . . . . . 109 ∗ 5.6 Afifthexample:Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Wanttoreadmore? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 ∗ 6 CaseStudy:InterpretingVisualScenes 119 6.1 Thethinkingpartofvision . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.2 Aerialsketchmaps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 6.2.1 Constraintsonimageregions . . . . . . . . . . . . . . . . . . . . . 122 6.3 Polyhedralobjects. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 6.3.1 Constraintsonverticesandedges . . . . . . . . . . . . . . . . . . 126 6.3.2 Impossibleobjects . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 6.4 Objectrecognition. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 ∗ 6.4.1 Handlingocclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Wanttoreadmore? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 7 ListsinProlog 137 7.1 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137 7.1.1 ListsasPrologterms . . . . . . . . . . . . . . . . . . . . . . . . . . 139 7.1.2 Unificationwithlists . . . . . . . . . . . . . . . . . . . . . . . . . . 139 (cid:2) (cid:2) (cid:2) (cid:2)