CS 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.• Nota multiple choice exam• No books(or other material) are allowed.• Duration will be 1:20 hours.• Academic Integritycode: 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 |–ia = sentence a can be derived from KB using procedure i• Sound: whenever KB |–ia then KB |= a is true• Complete: whenever KB |= a then KB |–iaCS 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”:∀∀∀∀xIn(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: ∀∀∀∀xIn(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”:∃∃∃∃xIn(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: ∃∃∃∃xIn(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 sentences• Brothers are siblings .• Sibling is transitive.• One’s mother is one’s sibling’s mother.• A first cousin is a child of a parent’s sibling.CS 561, Session 12-1321Example sentences• Brothers are siblings ∀∀∀∀ x, y Brother(x, y) Þ Sibling(x, y)• Sibling is transitive∀∀∀∀ x, y, z Sibling(x, y) ∧∧∧∧ Sibling(y, z)
View Full Document
Unlocking...