Knowledge Representation: LogicManuela VelosoCMU 15-381, Fall 2001The need for “knowledge” representationSymbolic knowledgePropositional logic and inferencePredicate logicThe resolution inference procedureActing in the WorldState and ActionsComplete intelligent agentPerception - at whichstateam I?Cognition - whichactionshould I take?Action - how do Iexecutethe action?State recognition implies staterepresentationMany examplesSymbolic knowledge about the worldKnowledge RepresentationOne of the goals (“the” goal?) of AI: buildintelligent agentsNeed “knowledge” – meaning of factsPhilosophyTheory ofmeaning– Natural language tomeaning“I think therefore I am” – logical clarificationof thoughtKnowledge base in AI – a set of representationsof facts about the worldWhatto represent?Which level ofdetail? – “frame problem”Knowledge RepresentationMany examples – any task is an exampleKnowledge level – epistemological level: whatthe agentknowsImplementation level – how knowledge isrepresentedThe representation of knowledge affectsdramatically the problem solving capability ofan agentHard to realize the effects of representationchoicesWhat is agoodrepresentation?Example: mutilated checkerboardMany possible representations.Knowledge RepresentationLogicSemantic networksFramesDefault logicsProbabilistic reasoningGraphical representationsSummaryThe wumpus world - Chapter 6, page 154Representing the worldSentencesPropositional logicSyntaxSemanticsProving the truth of a sentenceLogical inferenceDiscussionThe Wumpus WorldBreeze BreezeBreezeBreezeBreezeStenchStenchBreezePITPITPIT1 2 3 41234STARTGoldStenchReasoningPerceptions: stentch, breeze, glitter, bump (intowall), scream (wumpus killed)Actions: turn left, turn right, go forward, grab,shoot (only once), climb (at start)Goal: get the gold back to the start and climb outof the caveRules specify the actions to take at a particular state.Need to perceive and represent the world.RepresentationSentences - logicSyntax and semanticsFollowsSentencesFactsSentenceFactEntailsSemanticsSemanticsRepresentationWorldSentencesstench(2,1)“It’s raining.” “Lisboa´e a capital de Portugal.”SyntaxThe grammar: the rules oflegalsentences.Propositional logicSentence ::= TerminalSentenceNon-TerminalSentenceTerminalSentence ::= TrueFalseSymbolNon-TerminalSentence ::= Sentence ConnectiveSentenceSentenceConnective ::=Facts into logic - simple and hard1. Marcus was a man.2. All Pompeians were Romans.3. Caesar was a ruler.4. All Romans were either loyal to Caesar or hatedhim.5. Everyone is loyal to someone.Facts into logic - simple and hard6. People only try to assassinate rulers they are notloyal to.7. Marcus tried to assassinate Caesar.8. All Romans who know Marcus either hateCaesar or think that anyone who hates anyone iscrazy.9. Every country has a city that has been visited byevery person in the country.Facts into logic - simple and hard10. For every set, there is always another set with agreater cardinality.11. All blocks on top of blocks that have beenmoved or that are attached to blocks that havebeen moved have also been moved.SemanticsThe complete set of possible truth assignmentsto the symbols in the sentence: all the possibleworlds: all interpretations.Example: ; (true, true), (true, false), (false,true), (true, true)A sentence withpropositional symbols has interpretations.A sentence evaluates to True or False - subsetsof all interpretations.The truth of a sentence depends both on theinterpretation and on the state of the world.Example: stench-1-2Computing the Meaning of a SentenceBrute force: A truth table!Valid sentence: includes all interpretations.Examples: True, other examples?Satisfiable sentence: A sentence has at least oneinterpretation. Examples: ?Unsatisfiable sentence: No interpretations.Examples: False, other examples?If valid then satisfiable. If satisfiable, either validor not valid.Either satisfiable or unsatisfiable, not both.Knowledge BaseA collection of many sentences representing thecomplete knowledge about the world.BGPSWA = Agent = Breeze = Glitter, Gold = Pit = Stench = WumpusOK = Safe squareV = VisitedBP!AOK OKOK 1,1 2,1 3,1 4,1 1,2 2,2 3,2 4,2 1,3 2,3 3,3 4,3 1,4 2,4 3,4 4,4VSOKW!VContents of the knowledge base?EntailmentFollowsSentencesFactsSentenceFactEntailsSemanticsSemanticsRepresentationWorldThe meaning of the knowledge base: othersentences may be true, i.e., other sentences can bededucedfrom the sentences in the knowledge base.KB= SThe sentence S is “entailed” by the knowledge
View Full Document
Unlocking...