1CS 2710 Foundations of AICS 2710 Foundations of AILecture 11Milos [email protected] Sennott SquareFirst-order logic. CS 2710 Foundations of AIAdministration• PS-4:– Due on Thursday, October 7, 2004• Midterm: – October 19, 2004 during the class– Closed book– Covers:Search and Knowledge Representation2CS 2710 Foundations of AILogicLogic is defined by:• A set of sentences– A sentence is constructed from a set of primitives according to syntax rules.• A set of interpretations– An interpretation gives a semantic to primitives. It associates primitives with objects, values in the real world.• The valuation (meaning) function V– Assigns a truth value to a given sentence under some interpretationinterpretasentence: ×V },{tion FalseTrue→CS 2710 Foundations of AIFirst-order logic. Syntax.Term - syntactic entity for representing objectsTerms in FOL:• Constant symbols: represent specific objects– E.g. John, France, car89• Variables: represent objects of a certain type (type = domain of discourse)–E.g. x,y,z• Functions applied to one or more terms– E.g. father-of (John)father-of(father-of(John))3CS 2710 Foundations of AIFirst order logic. Syntax.Sentences in FOL:• Atomic sentences:– A predicate symbol applied to 0 or more termsExamples:Red(car12), Sister(Amy, Jane);Manager(father-of(John));– t1 = t2 equivalence of termsExample:John = father-of(Peter)CS 2710 Foundations of AIFirst order logic. Syntax.Sentences in FOL:• Complex sentences:• Assume are sentences in FOL. Then:–and–are sentences Symbols- stand for the existential and the universal quantifier)(ψφ∧ )(ψφ∨ψ¬)(ψφ⇔)(ψφ⇒ψφ,φx∀φy∃∀∃,4CS 2710 Foundations of AISemantics. Interpretation. An interpretation I is defined by a mapping of symbols to the domain of discourse D or relations on D• domain of discourse: a set of objects in the world we represent and refer to; An interpretation I maps:• Constant symbols to objects in DI(John) = • Predicate symbols to relations, properties on D• Function symbols to functional relations on D ;; ….;; ….I(brother) =I(father-of) =CS 2710 Foundations of AISemantics of sentences. Meaning (evaluation) function:A predicate predicate(term-1, term-2, term-3, term-n) is true for the interpretation I , iff the objects referred to by term-1, term-2, term-3, term-n are in the relation referred to by predicateinterpretasentence: ×V },{tion FalseTrue→V(brother(John, Paul), I) = True;; ….I(brother) =I(John) = I(Paul) =brother(John, Paul) =in I(brother)5CS 2710 Foundations of AISemantics of sentences.• Equality• Boolean expressions: standard• QuantificationsV(term-1= term-2, I) = TrueIff I(term-1) =I(term-2)V(sentence-1 ∨sentence-2, I) = TrueIff V(sentence-1,I)= True or V(sentence-2,I)= TrueE.g.V( , I) = TrueIff for all V( ,I[x/d])= Trueφx∀Dd∈φV( , I) = TrueIff there is a , s.t. V( ,I[x/d])= Trueφx∃Dd∈φsubstitution of x with dCS 2710 Foundations of AIOrder of quantifiers• Order of quantifiers of the same type does not matter• Order of different quantifiers changes the meaningFor all x and y, if x is a parent of y then y is a child of x)x,(),(, ychildyxparentyx ⇒∀)x,(),(, ychildyxparentxy ⇒∀),( yxlovesyx∃∀6CS 2710 Foundations of AIOrder of quantifiers• Order of quantifiers of the same type does not matter• Order of different quantifiers changes the meaningEverybody loves somebodyFor all x and y, if x is a parent of y then y is a child of x)x,(),(, ychildyxparentyx ⇒∀)x,(),(, ychildyxparentxy ⇒∀),( yxlovesyx∃∀),( yxlovesxy∀∃CS 2710 Foundations of AIOrder of quantifiers• Order of quantifiers of the same type does not matter• Order of different quantifiers changes the meaningEverybody loves somebodyThere is someone who is loved by everyoneFor all x and y, if x is a parent of y then y is a child of x)x,(),(, ychildyxparentyx ⇒∀)x,(),(, ychildyxparentxy ⇒∀),( yxlovesyx∃∀),( yxlovesxy∀∃7CS 2710 Foundations of AIConnections between quantifiersEveryone likes ice creamIs it possible to convey the same meaning using an existential quantifier ?A universal quantifier in the sentence can be expressed using anexistential quantifier !!!),( IceCreamxlikesx∀),( IceCreamxlikesx ¬¬∃There is no one who does not like ice creamCS 2710 Foundations of AIConnections between quantifiersIs it possible to convey the same meaning using a universal quantifier ?An existential quantifier in the sentence can be expressed using a universal quantifier !!!Someone likes ice cream),( IceCreamxlikesx∃Not everybody does not like ice cream),( IceCreamxlikesx¬¬∀8CS 2710 Foundations of AIRepresenting knowledge in FOLExample: Kinship domain• Objects: people• Properties: gender• Relations: parenthood, brotherhood, marriage• Functions: mother-of (one for each person x))(),( xFemalexMale),(),,(),,( yxSpouseyxBrotheryxParent)( xMotherOfK,,, JaneMaryJohnCS 2710 Foundations of AIKinship domain in FOLRelations between predicates and functions: write down what we know about them; how relate to each other.• Male and female are disjoint categories• Parent and child relations are inverse• A grandparent is a parent of parent• A sibling is another child of one’s parents• And so on ….),(),(),(, cpParentpgParentpcgtGrandparencg∧∃⇔∀),(),()(),(, ypParentxpParentpyxyxSiblingyx∧∃∧≠⇔∀),(),(, xyChildyxParentyx⇔∀)()( xFemalexMalex¬⇔∀9CS 2710 Foundations of AIInference in First order logicCS 2710 Foundations of AILogical inference in FOLLogical inference problem:• Given a knowledge base KB (a set of sentences) and a sentence , does the KB semantically entail ?In other words: In all interpretations in which sentences in the KB are true, is also true?Logical inference problem in the first-order logic is undecidable !!!. No procedure that can decide the entailment for all possible input sentencesin a finite number of steps.α=|KB?ααα10CS 2710 Foundations of AILogical inference problem in the Propositional logicComputational procedures that answer: Three approaches:• Truth-table approach• Inference rules• Conversion to the inverse SAT problem– Resolution-refutation α=|KB?CS 2710 Foundations of AIInference in FOL: Truth table approach• Is the Truth-table approach a viable approach for the FOL?• NO! • Why? • It would require us to