Artificialintelligencepart3

Knowledgeandreasoning

Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)ArtificialintelligencepartVII.LogicalAgentsAutumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)

VII.LogicalAgentsAutumn2012OutlineKnowledge-basedagentsWumpusworldLogicingeneral-modelsandentailmentPropositional(Boolean)logicEquivalence,validity,satisfiabilityInferencerulesandtheoremprovingforwardchainingbackwardchainingresolutionOutlineKnowledge-basedagentsKnowledge-BasedAgentAgentthatusespriororacquiredknowledgetoachieveitsgoalsCanmakemoreefficientdecisionsCanmakeinformeddecisionsKnowledgeBase(KB):containsasetofrepresentationsoffactsabouttheAgent’senvironmentEachrepresentationiscalledasentenceUsesomeknowledgerepresentationlanguage,toTELLitwhattoknowe.g.,(temperature72F)ThenitcanAskitselfwhattodo-answersshouldfollowfromtheKBAgentcanuseinferencetodeducenewfactsfromTELLedfactsKnowledgeBaseInferenceengineDomainindependentalgorithmsDomainspecificcontentTELLASKKnowledge-BasedAgentAgentthaGenericknowledge-basedagentTELLKBwhatwasperceived

UsesaKRLtoinsertnewsentences,representationsoffacts,intoKB

ASKKBwhattodo.

Useslogicalreasoningtoexamineactionsandselectbest.Genericknowledge-basedagentWumpusWorldPEASdescriptionPerformancemeasuregold+1000,death-1000-1perstep,-10forusingthearrowEnvironmentSquaresadjacenttowumpusaresmellySquaresadjacenttopitarebreezyGlitteriffgoldisinthesamesquareShootingkillswumpusifyouarefacingitShootingusesuptheonlyarrowGrabbingpicksupgoldifinsamesquareReleasingdropsthegoldinsamesquareSensors:Stench,Breeze,Glitter,Bump,ScreamActuators:Leftturn,Rightturn,Forward,Grab,Release,ShootWumpusWorldPEASdescriptionPWumpusworldcharacterizationFully

Observable?No–onlylocalperceptionDeterministic? Yes–outcomesexactlyspecifiedEpisodic? No–sequentialatthelevelofactionsStatic? Yes–WumpusandPitsdonotmoveDiscrete? YesSingle-agent?Yes–WumpusisessentiallyanaturalfeatureWumpusworldcharacterizationFExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeOthertightspotsOthertightspotsAnotherexamplesolutionNoperception1,2and2,1OKMoveto2,1Bin2,12,2or3,1P?1,1VnoPin1,1Moveto1,2(onlyoption)AnotherexamplesolutionNoperExamplesolutionSandNoSwhenin2,11,3or1,2hasW1,2OK1,3WNoBin1,22,2OK&3,1PExamplesolutionSandNoSwheLogicingeneralLogicsareformallanguagesforrepresentinginformationsuchthatconclusionscanbedrawnSyntaxdefinesthesentencesinthelanguageSemanticsdefinethe"meaning"ofsentences;i.e.,definetruthofasentenceinaworldE.g.,thelanguageofarithmeticx+2≥yisasentence;x2+y>{}isnotasentencex+2≥yistrueiffthenumberx+2isnolessthanthenumberyx+2≥yistrueinaworldwherex=7,y=1x+2≥yisfalseinaworldwherex=0,y=6LogicingeneralLogicsareforEntailmentEntailmentmeansthatonethingfollowsfromanother:KB╞

αKnowledgebaseKBentailssentenceαifandonlyifαistrueinallworldswhereKBistrueE.g.,theKBcontaining“theGiantswon”and“theRedswon”entails“EithertheGiantswonortheRedswon”E.g.,x+y=4entails4=x+yEntailmentisarelationshipbetweensentences(i.e.,syntax)thatisbasedonsemanticsEntailmentEntailmentmeansthaModelsLogicianstypicallythinkintermsofmodels,whichareformallystructuredworldswithrespecttowhichtruthcanbeevaluatedWesaym

isamodelofasentenceαifαistrueinmM(α)isthesetofallmodelsofαThenKB╞αiffM(KB)M(α)E.g.KB=GiantswonandReds

won,α=GiantswonModelsLogicianstypicallythinEntailmentinthewumpusworldSituationafterdetectingnothingin[1,1],movingright,breezein[2,1]ConsiderpossiblemodelsforKBassumingonlypits3Booleanchoices8possiblemodelsEntailmentinthewumpusworldWumpusmodelsWumpusmodelsWumpusmodelsKB=wumpus-worldrules+observationsWumpusmodelsKB=wumpus-worldWumpusmodelsKB=wumpus-worldrules+observationsα1="[1,2]issafe",KB╞α1,provedbymodelcheckingWumpusmodelsKB=wumpus-worldWumpusmodelsKB=wumpus-worldrules+observationsWumpusmodelsKB=wumpus-worldWumpusmodelsKB=wumpus-worldrules+observationsα2="[2,2]issafe",KB╞α2WumpusmodelsKB=wumpus-worldInferenceKB├iα=sentenceαcanbederivedfromKBbyprocedureiSoundness:iissoundifwheneverKB├iα,itisalsotruethatKB╞αCompleteness:iiscompleteifwheneverKB╞α,itisalsotruethatKB├iαInferenceKB├iα=sentenceαLogicasarepresentationoftheWorldSentencesSentencesEntailsFactsFactsFollowsSemanticsSemanticsRepresentationWorld

Sentencearephysicalconfigurationsoftheagent,andreasoningisaprocessofconstructingnewphysicalconfigurationsfromoldones.Logicalreasoningshouldensurethatthenewconfigurationsrepresentaspectsoftheworldthatactuallyfollowfromtheaspectsthattheoldconfigurationsrepresent.LogicasarepresentationoftPropositionallogic:SyntaxPropositionallogicisthesimplestlogic–illustratesbasicideasThepropositionsymbolsP1,P2etcaresentencesIfSisasentence,Sisasentence(negation)IfS1andS2aresentences,S1

S2isasentence(conjunction)IfS1andS2aresentences,S1

S2isasentence(disjunction)IfS1andS2aresentences,S1

S2isasentence(implication)IfS1andS2aresentences,S1

S2isasentence(biconditional)Propositionallogic:SyntaxProPropositionallogic:SemanticsEachmodelspecifiestrue/falseforeachpropositionsymbolE.g. P1,2 P2,2 P3,1 false true falseWiththesesymbols,8possiblemodels,canbeenumeratedautomatically.Rulesforevaluatingtruthwithrespecttoamodelm: S istrueiff Sisfalse S1

S2istrueiff S1istrueand S2istrue S1

S2istrueiff S1istrueor S2istrue S1

S2 istrueiff S1isfalseor S2istrue i.e., isfalseiff S1istrueand S2isfalse S1

S2 istrueiff S1S2istrueandS2S1istrueSimplerecursiveprocessevaluatesanarbitrarysentence,e.g.,P1,2(P2,2

P3,1)=true

(truefalse)=true

true=truePropositionallogic:SemanticsTruthtablesforconnectivesTruthtablesforconnectivesWumpusworldsentencesLetPi,jbetrueifthereisapitin[i,j].LetBi,jbetrueifthereisabreezein[i,j].P1,1B1,1B2,1"Pitscausebreezesinadjacentsquares"B1,1

(P1,2

P2,1)B2,1 (P1,1

P2,2P3,1)WumpusworldsentencesLetPi,jTruthtablesforinferenceTruthtablesforinferenceInferencebyenumerationDepth-firstenumerationofallmodelsissoundandcompleteFornsymbols,timecomplexityisO(2n),spacecomplexityisO(n)InferencebyenumerationDepth-LogicalequivalenceTwosentencesarelogicallyequivalentifftrueinsamemodels:α≡?iffα╞βandβ╞αLogicalequivalenceTwosentencValidityandsatisfiabilityAsentenceisvalidifitistrueinallmodels,e.g.,True, AA, AA, (A(AB))BValidityisconnectedtoinferenceviatheDeductionTheorem:KB╞αifandonlyif(KB

α)isvalidAsentenceissatisfiableifitistrueinsomemodele.g.,AB, CAsentenceisunsatisfiableifitistrueinnomodelse.g.,AASatisfiabilityisconnectedtoinferenceviathefollowing:KB╞αifandonlyif(KB

α)isunsatisfiable--refutationValidityandsatisfiabilityAsProofmethodsProofmethodsdivideinto(roughly)twokinds:ApplicationofinferencerulesLegitimate(sound)generationofnewsentencesfromoldProof=asequenceofinferenceruleapplications

CanuseinferencerulesasoperatorsinastandardsearchalgorithmTypicallyrequiretransformationofsentencesintoanormalformModelcheckingtruthtableenumeration(alwaysexponentialinn)improvedbacktracking,e.g.,Davis--Putnam-Logemann-Loveland(DPLL)heuristicsearchinmodelspace(soundbutincomplete) e.g.,min-conflicts-likehill-climbingalgorithmsProofmethodsProofmethodsdivInferenceRulesInferenceRulesInferenceRulesInferenceRulesResolutionConjunctiveNormalForm(CNF)

conjunctionofdisjunctionsofliterals clauses E.g.,(A

B)(B

C

D)Resolutioninferencerule(forCNF):li

…

lk, m1

…

mnli

…

li-1

li+1

…

lk

m1

…

mj-1

mj+1

...

mn

whereliandmjarecomplementaryliterals. E.g.,P1,3

P2,2, P2,2

P1,3Resolutionissoundandcomplete

forpropositionallogicResolutionConjunctiveNormalFResolutionSoundnessofresolutioninferencerule:(li

…

li-1

li+1

…

lk)li mj(m1

…

mj-1

mj+1

...

mn)(li

…

li-1

li+1

…

lk)(m1

…

mj-1

mj+1

...

mn)ResolutionSoundnessofresolutConversiontoCNFB1,1

(P1,2

P2,1)Eliminate,replacingαβwith(αβ)(βα).(B1,1

(P1,2

P2,1))((P1,2

P2,1)B1,1)2.Eliminate,replacingαβwithαβ.(B1,1

P1,2

P2,1)((P1,2

P2,1)B1,1)3.MoveinwardsusingdeMorgan'srulesanddouble-negation:(B1,1P1,2

P2,1)((P1,2

P2,1)B1,1)4.Applydistributivitylaw(over)andflatten:(B1,1

P1,2

P2,1)(P1,2B1,1)(P2,1

B1,1)ConversiontoCNFB1,1(P1,2ResolutionalgorithmProofbycontradiction,i.e.,showKBαunsatisfiableResolutionalgorithmProofbycResolutionexampleKB=(B1,1

(P1,2P2,1))B1,1α=P1,2ResolutionexampleKB=(B1,1ForwardandbackwardchainingHornForm(restricted) KB=conjunctionofHornclauses(clauseswith≤1positiveliteral)Hornclause=propositionsymbol;or(conjunctionofsymbols)symbolE.g.,C(BA)(CDB)ModusPonens(forHornForm):completeforHornKBsα1,…,αn, α1

…

αn

ββCanbeusedwithforwardchainingorbackwardchaining.ThesealgorithmsareverynaturalandruninlineartimeForwardandbackwardchainingHForwardchainingIdea:findanyrulewhosepremisesaresatisfiedintheKB,additsconclusiontotheKB,untilqueryisfoundForwardchainingIdea:findanyForwardchainingalgorithmForwardchainingissoundandcompleteforHornKBForwardchainingalgorithmForwForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleForwardchainingexampleProofofcompletenessFCderiveseveryatomicsentencethatisentailedbyKBFCreachesafixedpointwherenonewatomicsentencesarederivedConsiderthefinalstateasamodelm,assigningtrue/falsetosymbolsEveryclauseintheoriginalKBistrueinm

a1

…

akbHencemisamodelofKBIfKB╞q,qistrueineverymodelofKB,includingmProofofcompletenessFCderiveBackwardchainingIdea:workbackwardsfromthequeryq:toproveqbyBC,checkifqisknownalready,orprovebyBCallpremisesofsomeruleconcludingqAvoidloops:checkifnewsubgoalisalreadyonthegoalstackAvoidrepeatedwork:checkifnewsubgoalhasalreadybeenprovedtrue,orhasalreadyfailedBackwardchainingIdea:workbaBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleBackwardchainingexampleForwardvs.backwardchainingFCisdata-driven,automatic,unconsciousprocessing,e.g.,objectrecognition,routinedecisionsMaydolotsofworkthatisirrelevanttothegoalBCisgoal-driven,appropriateforproblem-solving,e.g.,Wherearemykeys?HowdoIgetintoaPhDprogram?ComplexityofBCcanbemuchlessthanlinearinsizeofKBForwardvs.backwardchainingFEfficientpropositionalinferenceTwofamiliesofefficientalgorithmsforpropositionalinference:BasedonbacktrackingsearchBasedonhillclimbingsearchCompletebacktrackingsearchalgorithmsDPLLalgorithm(Davis,Putnam,Logemann,Loveland)IncompletelocalsearchalgorithmsWalkSATalgorithmEfficientpropositionalinfereTheDPLLalgorithmDetermineifaninputpropositionallogicsentence(inCNF)issatisfiable.Arecursivedepth-firstenumerationofpossiblemodels.Improvementsovertruthtableenumeration:EarlyterminationAclauseistrueifanyliteralistrue.Asentenceisfalseifanyclauseisfalse.PuresymbolheuristicPuresymbol:alwaysappearswiththesame"sign"inallclauses.e.g.,Inthethreeclauses(A

B),(B

C),(CA),AandBarepure,Cisimpure.Makeapuresymbolliteraltrue.UnitclauseheuristicUnitclause:onlyoneliteralintheclauseTheonlyliteralinaunitclausemustbetrue.TheDPLLalgorithmDetermineifTheDPLLalgorithmTheDPLLalgorithmTheWalkSATalgorithmIncomplete,localsearchalgorithmEvaluationfunction:Themin-conflictheuristicofminimizingthenumberofunsatisfiedclausesBalancebetweengreedinessandrandomnessTheWalkSATalgorithmIncompletTheWalkSATalgorithmTheWalkSATalgorithmHardsatisfiabilityproblemsConsiderrandom3-CNFsentences.e.g., (D

BC)(B

A

C)(C

BE)(E

DB)(BE

C)m=numberofclausesn=numberofsymbolsHardproblemsseemtoclusternearm/n=4.3(criticalpoint)HardsatisfiabilityproblemsCoHardsatisfiabilityproblemsHardsatisfiabilityproblemsHardsatisfiabilityproblemsMedianruntimefor100satisfiablerandom3-CNFsentences,n=50HardsatisfiabilityproblemsMeInference-basedagentsinthewumpusworldAwumpus-worldagentusingpropositionallogic:P1,1

W1,1

Bx,y

(Px,y+1

Px,y-1

Px+1,y

Px-1,y)Sx,y

(Wx,y+1

Wx,y-1

Wx+1,y

Wx-1,y)W1,1

W1,2

…W4,4

W1,1

W1,2

W1,1

W1,3

…64distinctpropositionsymbols,155sentencesInference-basedagentsinthe人工智能的課件CH7LogicAgentsExpressivenesslimitationofpropositionallogicKBcontains"physics"sentencesforeverysinglesquareForeverytimetandeverylocation[x,y],Lx,y

FacingRightt

Forwardt

Lx+1,y

RapidproliferationofclausestExpressivenesslimitationofpSummaryLogicalagentsapplyinferencetoaknowledgebasetoderivenewinformationandmakedecisionsBasicconceptsoflogic:syntax:formalstructureofsentencessemantics:truthofsentenceswrtmodelsentailment:necessarytruthofonesentencegivenanotherinference:derivingsentencesfromothersentencessoundness:derivationsproduceonlyentailedsentencescompleteness:derivationscanproduceallentailedsentencesWumpusworldrequirestheabilitytorepresentpartialandnegatedinformation,reasonbycases,etc.Resolutioniscompleteforpropositionallogic

Forward,backwardchainingarelinear-time,completeforHornclausesPropositionallogiclacksexpressivepowerSummaryLogicalagentsapplyinAssignmentsEx7.4,7.12,7.17.AssignmentsEx7.4,7.12,7.17.

Artificialintelligencepart3

Knowledgeandreasoning

Autumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)ArtificialintelligencepartVII.LogicalAgentsAutumn2012Instructor:WangXiaolongHarbinInstituteofTechnology,ShenzhenGraduateSchoolIntelligentComputationResearchCenter(HITSGSICRC)

VII.LogicalAgentsAutumn2012OutlineKnowledge-basedagentsWumpusworldLogicingeneral-modelsandentailmentPropositional(Boolean)logicEquivalence,validity,satisfiabilityInferencerulesandtheoremprovingforwardchainingbackwardchainingresolutionOutlineKnowledge-basedagentsKnowledge-BasedAgentAgentthatusespriororacquiredknowledgetoachieveitsgoalsCanmakemoreefficientdecisionsCanmakeinformeddecisionsKnowledgeBase(KB):containsasetofrepresentationsoffactsabouttheAgent’senvironmentEachrepresentationiscalledasentenceUsesomeknowledgerepresentationlanguage,toTELLitwhattoknowe.g.,(temperature72F)ThenitcanAskitselfwhattodo-answersshouldfollowfromtheKBAgentcanuseinferencetodeducenewfactsfromTELLedfactsKnowledgeBaseInferenceengineDomainindependentalgorithmsDomainspecificcontentTELLASKKnowledge-BasedAgentAgentthaGenericknowledge-basedagentTELLKBwhatwasperceived

UsesaKRLtoinsertnewsentences,representationsoffacts,intoKB

ASKKBwhattodo.

Useslogicalreasoningtoexamineactionsandselectbest.Genericknowledge-basedagentWumpusWorldPEASdescriptionPerformancemeasuregold+1000,death-1000-1perstep,-10forusingthearrowEnvironmentSquaresadjacenttowumpusaresmellySquaresadjacenttopitarebreezyGlitteriffgoldisinthesamesquareShootingkillswumpusifyouarefacingitShootingusesuptheonlyarrowGrabbingpicksupgoldifinsamesquareReleasingdropsthegoldinsamesquareSensors:Stench,Breeze,Glitter,Bump,ScreamActuators:Leftturn,Rightturn,Forward,Grab,Release,ShootWumpusWorldPEASdescriptionPWumpusworldcharacterizationFully

Observable?No–onlylocalperceptionDeterministic? Yes–outcomesexactlyspecifiedEpisodic? No–sequentialatthelevelofactionsStatic? Yes–WumpusandPitsdonotmoveDiscrete? YesSingle-agent?Yes–WumpusisessentiallyanaturalfeatureWumpusworldcharacterizationFExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeExploringaWumpusworldA=AgentB=BreezeS=SmellP=PitW=WumpusOK=SafeV=VisitedG=GlitterExploringaWumpusworldA=AgeOthertightspotsOthertightspotsAnotherexamplesolutionNoperception1,2and2,1OKMoveto2,1Bin2,12,2or3,1P?1,1VnoPin1,1Moveto1,2(onlyoption)AnotherexamplesolutionNoperExamplesolutionSandNoSwhenin2,11,3or1,2hasW1,2OK1,3WNoBin1,22,2OK&3,1PExamplesolutionSandNoSwheLogicingeneralLogicsareformallanguagesforrepresentinginformationsuchthatconclusionscanbedrawnSyntaxdefinesthesentencesinthelanguageSemanticsdefinethe"meaning"ofsentences;i.e.,definetruthofasentenceinaworldE.g.,thelanguageofarithmeticx+2≥yisasentence;x2+y>{}isnotasentencex+2≥yistrueiffthenumberx+2isnolessthanthenumberyx+2≥yistrueinaworldwherex=7,y=1x+2≥yisfalseinaworldwherex=0,y=6LogicingeneralLogicsareforEntailmentEntailmentmeansthatonethingfollowsfromanother:KB╞

αKnowledgebaseKBentailssentenceαifandonlyifαistrueinallworldswhereKBistrueE.g.,theKBcontaining“theGiantswon”and“theRedswon”entails“EithertheGiantswonortheRedswon”E.g.,x+y=4entails4=x+yEntailmentisarelationshipbetweensentences(i.e.,syntax)thatisbasedonsemanticsEntailmentEntailmentmeansthaModelsLogicianstypicallythinkintermsofmodels,whichareformallystructuredworldswithrespecttowhichtruthcanbeevaluatedWesaym

isamodelofasentenceαifαistrueinmM(α)isthesetofallmodelsofαThenKB╞αiffM(KB)M(α)E.g.KB=GiantswonandReds

won,α=GiantswonModelsLogicianstypicallythinEntailmentinthewumpusworldSituationafterdetectingnothingin[1,1],movingright,breezein[2,1]ConsiderpossiblemodelsforKBassumingonlypits3Booleanchoices8possiblemodelsEntailmentinthewumpusworldWumpusmodelsWumpusmodelsWumpusmodelsKB=wumpus-worldrules+observationsWumpusmodelsKB=wumpus-worldWumpusmodelsKB=wumpus-worldrules+observationsα1="[1,2]issafe",KB╞α1,provedbymodelcheckingWumpusmodelsKB=wumpus-worldWumpusmodelsKB=wumpus-worldrules+observationsWumpusmodelsKB=wumpus-worldWumpusmodelsKB=wumpus-worldrules+observationsα2="[2,2]issafe",KB╞α2WumpusmodelsKB=wumpus-worldInferenceKB├iα=sentenceαcanbederivedfromKBbyprocedureiSoundness:iissoundifwheneverKB├iα,itisalsotruethatKB╞αCompleteness:iiscompleteifwheneverKB╞α,itisalsotruethatKB├iαInferenceKB├iα=sentenceαLogicasarepresentationoftheWorldSentencesSentencesEntailsFactsFactsFollowsSemanticsSemanticsRepresentationWorld

Sentencearephysicalconfigurationsoftheagent,andreasoningisaprocessofconstructingnewphysicalconfigurationsfromoldones.Logicalreasoningshouldensurethatthenewconfigurationsrepresentaspectsoftheworldthatactuallyfollowfromtheaspectsthattheoldconfigurationsrepresent.LogicasarepresentationoftPropositionallogic:SyntaxPropositionallogicisthesimplestlogic–illustratesbasicideasThepropositionsymbolsP1,P2etcaresentencesIfSisasentence,Sisasentence(negation)IfS1andS2aresentences,S1

S2isasentence(conjunction)IfS1andS2aresentences,S1

S2isasentence(disjunction)IfS1andS2aresentences,S1

S2isasentence(implication)IfS1andS2aresentences,S1

S2isasentence(biconditional)Propositionallogic:SyntaxProPropositionallogic:SemanticsEachmodelspecifiestrue/falseforeachpropositionsymbolE.g. P1,2 P2,2 P3,1 false true falseWiththesesymbols,8possiblemodels,canbeenumeratedautomatically.Rulesforevaluatingtruthwithrespecttoamodelm: S istrueiff Sisfalse S1

S2istrueiff S1istrueand S2istrue S1

S2istrueiff S1istrueor S2istrue S1

S2 istrueiff S1isfalseor S2istrue i.e., isfalseiff S1istrueand S2isfalse S1

S2 istrueiff S1S2istrueandS2S1istrueSimplerecursiveprocessevaluatesanarbitrarysentence,e.g.,P1,2(P2,2

P3,1)=true

(truefalse)=true

true=truePropositionallogic:SemanticsTruthtablesforconnectivesTruthtablesforconnectivesWumpusworldsentencesLetPi,jbetrueifthereisapitin[i,j].LetBi,jbetrueifthereisabreezein[i,j].P1,1B1,1B2,1"Pitscausebreezesinadjacentsquares"B1,1

(P1,2

P2,1)B2,1 (P1,1

P2,2P3,1)WumpusworldsentencesLetPi,jTruthtablesforinferenceTruthtablesforinferenceInferencebyenumerationDepth-firstenumerationofallmodelsissoundandcompleteFornsymbols,timecomplexityisO(2n),spacecomplexityisO(n)InferencebyenumerationDepth-LogicalequivalenceTwosentencesarelogicallyequivalentifftrueinsamemodels:α≡?iffα╞βandβ╞αLogicalequivalenceTwosentencValidityandsatisfiabilityAsentenceisvalidifitistrueinallmodels,e.g.,True, AA, AA, (A(AB))BValidityisconnectedtoinferenceviatheDeductionTheorem:KB╞αifandonlyif(KB

α)isvalid