CS 561, Session 12-131Midterm format• Date: 10/09/2003 from 11:00am – 12:20 pm • Location: disclosed in class• Credits: 35% of overall grade• Approx. 4 problems, several questions in each.• Material: everything so far.• 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 example• Ontology (ont = ‘to be’; logica = ‘word’): kinds of things one can talk about in the languageCS 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-139Semanticsthere is a correspondence between • functions, which return values• predicates, which are true or falseFunction: father_of(Mary) = BillPredicate: father_of(Mary, Bill)CS 561, Session 12-1310Examples:• “One plus two equals three”Objects:Relations:Properties:Functions:• “Squares neighboring the Wumpus are smelly”Objects:Relations:Properties:Functions:CS 561, Session 12-1311Examples:• “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-1312FOL: 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-1313Syntax of Predicate Logic•Symbol set• constants• Boolean connectives•variables• functions• predicates (relations)• quantifiersCS 561, Session 12-1314Syntax of Predicate Logic• Terms: a reference to an object• variables, •constants, • functional expressions (can be arguments to predicates)•Examples: • first([a,b,c]), sq_root(9), sq_root(n), tail([a,b,c])CS 561, Session 12-1315Syntax of Predicate Logic• Sentences: make claims about objects• (Well-formed formulas, (wffs))• Atomic Sentences (predicate expressions):• loves(John,Mary), brother_of(John,Ted)• Complex Sentences (Atomic Sentences connected by booleans):• loves(John,Mary)• brother_of(John,Ted)• teases(Ted, John)CS 561, Session 12-1316Examples of Terms: Constants, Variables and Functions• Constants: object constants refer to individuals• Alan, Sam, R225, R216•Variables• PersonX, PersonY, RoomS, RoomT• Functions• father_of(PersonX)• product_of(Number1,Number2)CS 561, Session 12-1317Examples of Predicates and Quantifiers•Predicates• in(Alan,R225)• partOf(R225,Pender)• fatherOf(PersonX,PersonY)• Quantifiers• All dogs are mammals.• Some birds can’t fly.• 3 birds can’t fly.CS 561, Session 12-1318Semantics• Referring to individuals• Jackie• son-of(Jackie), Sam• Referring to states of the world• person(Jackie), female(Jackie)• mother(Sam, Jackie)CS 561, Session 12-1319FOL: 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-1320FOL: Complex sentencesSentence → AtomicSentence| Sentence Connective Sentence| Quantifier Variable, … Sentence| ¬ Sentence| (Sentence)•Examples: •S1 ∧ S2, S1 ∨ S2, (S1 ∧ S2) ∨ S3, S1 ⇒ S2, S1⇔ S3• Colleague(Paolo, Maja) ⇒ Colleague(Maja, Paolo)Student(Alex, Paolo) ⇒ Teacher(Paolo, Alex)CS 561, Session 12-1321Semantics 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 iffthe relation referred to by predicate holds between the objects referred to by term1, …, termnCS 561, Session 12-1322Example 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-1323Quantifiers• Expressing sentences about collections of objects without enumeration (naming individuals)• E.g., All Trojans are cleverSomeone in the class is sleeping• Universal quantification (for all): ∀• Existential quantification (three exists): ∃CS 561, Session 12-1324Universal quantification (for all): ∀∀<variables> <sentence>•“Every one in the cs561 class is
View Full Document
Unlocking...