Midterm formatLast time: Logic and ReasoningLast Time: Syntax of propositional logicLast Time: Semantics of Propositional logicLast Time: Inference rules for propositional logicThis timeWhy first-order logic?First-order logic (FOL)Examples:Slide 10FOL: Syntax of basic elementsFOL: Atomic sentencesFOL: Complex sentencesSemantics of atomic sentencesExample modelQuantifiersUniversal quantification (for all): Existential quantification (there exists): Properties of quantifiersExample sentencesSlide 21EqualityHigher-order logic?Logical agents for the Wumpus worldUsing the FOL Knowledge BaseWumpus world, FOL Knowledge BaseDeducing hidden propertiesSituation calculusDescribing actionsDescribing actions (cont’d)PlanningGenerating action sequencesSummaryCS 561, Session 12-131Midterm format•Date: 10/10/2002 from 11:00am – 12:20 pm •Location: THH 101•Credits: 35% of overall grade•Approx. 4 problems, several questions in each.•Material: everything so far, up to slide 27 in this file.•Not a multiple choice exam•No books (or other material) are allowed.•Duration will be 1:20 hours.•Academic Integrity code: see class main page.CS 561, Session 12-132Last time: Logic and Reasoning•Knowledge Base (KB): contains a set of sentences expressed using a knowledge representation language•TELL: operator to add a sentence to the KB•ASK: to query the KB •Logics are KRLs where conclusions can be drawn•Syntax•Semantics•Entailment: KB |= a iff a is true in all worlds where KB is true•Inference: KB |–i a = sentence a can be derived from KB using procedure i•Sound: whenever KB |–i a then KB |= a is true•Complete: whenever KB |= a then KB |–i aCS 561, Session 12-133Last Time: Syntax of propositional logicCS 561, Session 12-134Last Time: Semantics of Propositional logicCS 561, Session 12-135Last Time: Inference rules for propositional logicCS 561, Session 12-136This time•First-order logic•Syntax•Semantics•Wumpus world exampleCS 561, Session 12-137Why first-order logic?•We saw that propositional logic is limited because it only makes the ontological commitment that the world consists of facts.•Difficult to represent even simple worlds like the Wumpus world;e.g., “don’t go forward if the Wumpus is in front of you” takes 64 rulesCS 561, Session 12-138First-order logic (FOL)•Ontological commitments:•Objects: wheel, door, body, engine, seat, car, passenger, driver•Relations: Inside(car, passenger), Beside(driver, passenger)•Functions: ColorOf(car)•Properties: Color(car), IsOpen(door), IsOn(engine)•Functions are relations with single value for each objectCS 561, Session 12-139Examples:•“One plus two equals three”Objects:Relations:Properties:Functions:•“Squares neighboring the Wumpus are smelly”Objects:Relations:Properties:Functions:CS 561, Session 12-1310Examples:•“One plus two equals three”Objects: one, two, three, one plus twoRelations: equalsProperties: --Functions: plus (“one plus two” is the name of the object obtained by applying function plus to one and two;three is another name for this object)•“Squares neighboring the Wumpus are smelly”Objects: Wumpus, squareRelations: neighboringProperties: smellyFunctions: --CS 561, Session 12-1311FOL: Syntax of basic elements•Constant symbols: 1, 5, A, B, USC, JPL, Alex, Manos, …•Predicate symbols: >, Friend, Student, Colleague, …•Function symbols: +, sqrt, SchoolOf, TeacherOf, ClassOf, …•Variables: x, y, z, next, first, last, …•Connectives: , , , •Quantifiers: , •Equality: =CS 561, Session 12-1312FOL: Atomic sentencesAtomicSentence Predicate(Term, …) | Term = TermTerm Function(Term, …) | Constant | Variable•Examples: SchoolOf(Manos)Colleague(TeacherOf(Alex), TeacherOf(Manos)) >((+ x y), x)CS 561, Session 12-1313FOL: Complex sentencesSentence AtomicSentence | Sentence Connective Sentence| Quantifier Variable, … Sentence| Sentence| (Sentence)•Examples: S1 S2, S1 S2, (S1 S2) S3, S1 S2, S1 S3Colleague(Paolo, Maja) Colleague(Maja, Paolo) Student(Alex, Paolo) Teacher(Paolo, Alex)CS 561, Session 12-1314Semantics of atomic sentences•Sentences in FOL are interpreted with respect to a model•Model contains objects and relations among them•Terms: refer to objects (e.g., Door, Alex, StudentOf(Paolo))•Constant symbols: refer to objects•Predicate symbols: refer to relations•Function symbols: refer to functional Relations•An atomic sentence predicate(term1, …, termn) is true iff the relation referred to by predicate holds between the objects referred to by term1, …, termnCS 561, Session 12-1315Example model•Objects: John, James, Marry, Alex, Dan, Joe, Anne, Rich•Relation: sets of tuples of objects{<John, James>, <Marry, Alex>, <Marry, James>, …}{<Dan, Joe>, <Anne, Marry>, <Marry, Joe>, …}•E.g.: Parent relation -- {<John, James>, <Marry, Alex>, <Marry, James>}then Parent(John, James) is trueParent(John, Marry) is falseCS 561, Session 12-1316Quantifiers•Expressing sentences of collection of objects without enumeration•E.g., All Trojans are cleverSomeone in the class is sleeping•Universal quantification (for all): •Existential quantification (three exists): CS 561, Session 12-1317Universal quantification (for all): <variables> <sentence>•“Every one in the 561a class is smart”: x In(561a, x) Smart(x) P corresponds to the conjunction of instantiations of PIn(561a, Manos) Smart(Manos) In(561a, Dan) Smart(Dan) …In(561a, Clinton) Smart(Clinton) is a natural connective to use with •Common mistake: to use in conjunction with e.g: x In(561a, x) Smart(x)means “every one is in 561a and everyone is smart”CS 561, Session 12-1318Existential quantification (there exists): <variables> <sentence>•“Someone in the 561a class is smart”: x In(561a, x) Smart(x) P corresponds to the disjunction of instantiations of PIn(561a, Manos) Smart(Manos) In(561a, Dan) Smart(Dan) …In(561a, Clinton) Smart(Clinton) is a natural connective to use with •Common mistake: to use in conjunction with e.g: x In(561a, x) Smart(x)is true if there is anyone that is not in 561a!(remember, false true is valid).CS 561, Session 12-1319Properties of quantifiersCS 561, Session 12-1320Example
View Full Document