1CS 1571 Intro to AIM. HauskrechtCS 1571 Introduction to AILecture 17Milos [email protected] Sennott SquareFirst-order logic CS 1571 Intro to AIM. HauskrechtSimulated annealing competitionResults: – Baer,Joshua R– Miller,Michael P– Matchett,Richard J2CS 1571 Intro to AIM. HauskrechtLimitations of propositional logicWorld we want to represent and reason about consists of a number of objects with variety of properties and relations among themPropositional logic:• Represents statements about the world without reflecting this structure and without modeling these entities explicitlyConsequence:• some knowledge is hard or impossible to encode in the propositional logic.• Two cases that are hard to represent:– Statements about similar objects, relations– Statements referring to groups of objects.CS 1571 Intro to AIM. HauskrechtTo derive we need: Limitations of propositional logic• Statements about similar objects and relations needs to be enumerated• Example: Seniority of people domainWhat is the problem?John is older than MaryMary is older than PaulJohn is older than PaulAssume we have:∧⇒John is older than Mary Mary is older than PaulJohn is older than PaulAssume we add another fact: Jane is older than MaryTo derive we need: Jane is older than Paul∧⇒Jane is older than Mary Mary is older than PaulJane is older than Paul3CS 1571 Intro to AIM. HauskrechtTo derive we need: Limitations of propositional logic• Statements about similar objects and relations needs to be enumerated• Example: Seniority of people domainProblem: KB grows largeJohn is older than MaryMary is older than PaulJohn is older than PaulAssume we have:∧⇒John is older than Mary Mary is older than PaulJohn is older than PaulAssume we add another fact: Jane is older than MaryTo derive we need: Jane is older than Paul∧⇒Jane is older than Mary Mary is older than PaulJane is older than PaulCS 1571 Intro to AIM. Hauskrecht• Statements about similar objects and relations needs to be enumerated• Example: Seniority of people domain• Problem: if we have many people and facts about their seniority we need represent many rules like this to allow inferences• Possible solution: ??For inferences we need: Limitations of propositional logic∧⇒John is older than Mary Mary is older than PaulJohn is older than Paul∧⇒Jane is older than Mary Mary is older than PaulJane is older than Paul4CS 1571 Intro to AIM. Hauskrecht• Statements about similar objects and relations needs to be enumerated• Example: Seniority of people domain• Problem: if we have many people and facts about their seniority we need represent many rules like this to allow inferences• Possible solution: introduce variablesFor inferences we need: Limitations of propositional logic∧⇒John is older than Mary Mary is older than PaulJohn is older than Paul∧⇒Jane is older than Mary Mary is older than PaulJane is older than Paul∧PersA is older than PersB PersB is older than PersC⇒PersA is older than PersCCS 1571 Intro to AIM. HauskrechtLimitations of propositional logic• Statements referring to groups of objects require exhaustive enumeration of objects• Example:• Solution: Allow quantification in statementsEvery student likes vacationAssume we want to express Doing this in propositional logic would require to includestatements about every studentJohn likes vacationMary likes vacationAnn likes vacation∧∧∧L5CS 1571 Intro to AIM. HauskrechtFirst-order logic (FOL)• More expressive than propositional logic• Eliminates deficiencies of PL by:– Representing objects, their properties, relations and statements about them;– Introducing variables that refer to an arbitrary objects and can be substituted by a specific object– Introducing quantifiers allowing us to make statements over groups objects without the need to represent each of them separately CS 1571 Intro to AIM. HauskrechtLogicLogic 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→6CS 1571 Intro to AIM. HauskrechtFirst-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))CS 1571 Intro to AIM. HauskrechtFirst 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)7CS 1571 Intro to AIM. HauskrechtFirst 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∃∀∃,CS 1571 Intro to AIM. HauskrechtSemantics. Interpretation. An interpretation I is defined by a mapping 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) =8CS 1571 Intro to AIM. HauskrechtSemantics 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)CS 1571 Intro to AIM. HauskrechtSemantics 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