1、The Predicate CalculusChapter 152OutlinenMotivationnThe Language and Its SyntaxnSemanticsnQuantificationnSemantics of QuantifiersnPredicate Calculus as a Language for Representing Knowledge315.1 MotivationnPropositional calculusnExpressional limitationnAtoms have no internal structures.nFirst-order
2、predicate calculusnhas names for objects as well as propositions.nSymbolsnObject constantsnRelation constantsnFunction constantsnOther constructsnRefer to objects in the worldnRefer to propositions about the world4The Language and its SyntaxnComponentsnInfinite set of object constantsnAa, 125, 23B,
3、Q, John, EiffelTowernInfinite set of function constantsnfatherOf1, distanceBetween2, times2nInfinite set of relation constantsnB173, Parent2, Large1, Clear1, X114nPropositional connectivesnDelimitersn(, ), , ,(separator) , , ,5The Language and its SyntaxnTermsnObject constant is a termnFunctional ex
4、pressionnfatherOf(John, Bill), times(4, plus(3, 6), SamnwffsnAtomsnRelation constant of arity n followed by n terms is an atom (atomic formula)nAn atom is a wff.nGreaterthan(7,2), P(A, B, C, D), QnPropositional wffP Sam)hn,Brother(Jo 5,4)Lessthan(1 n(7,2)Greatertha615.3 SemanticsnWorldsnIndividualsn
5、ObjectsnConcrete examples: Block A, Mt. Whitney, Julius Caesar, nAbstract entities: 7, set of all integers, nFictional/invented entities: beauty, Santa Claus, a unicorn, honesty, nFunctions on individualsnMap n tuples of individuals into individualsnRelations over individualsnProperty: relation of a
6、rity 1 (heavy, big, blue, )nSpecification of n-ary relation: list all the n tuples of individuals715.3 SemanticsnInterpretationsnAssignment: maps the followingsnobject constants into objects in the worldnn-ary constants into n-ary functionsnn-ary relation constants into n-ary relationsncalled denota
7、tions of corresponding predicate-calculus expressionsnDomainnSet of objects to which object constant assignments are madenTrue/False valuesFigure 15.1 A Configuration of Blocks8Table 15.1 A Mapping between Predicate Calculus and the WorldDetermination of the value of some predicate-claculus wffs On(
8、A,B) is False because is not in the relation On. Clear(B) is True because is in the relation Clear. On(C,F1) is True because is in the relation On. On(C,F1) On(A,B) is True because both On(C,F1) and On(A,B) are TruePredicate CalculusABCF1OnClearWorldABCFloorOn=, , Clear=915.3 SemanticsnModels and Re
9、lated NotionsnAn interpretation satisfies a wffnwff has the value True under that interpretationnModel of wffnAn interpretation that satisfies a wffnValid wffnAny wff that has the value True under all interpretationsninconsistent/unsatisfiable wffnAny wff that does not have a modeln logically entail
10、s ( |=)nA wff has value True under all of those interpretations for which each of the wffs in a set has value TruenEquivalent wffsnTruth values are identical under all interpretations1015.3 SemanticsnKnowledgenPredicate-calculus formulasnrepresent knowledge of an agentnKnowledge base of agentnSet of
11、 formulasnThe agent knows = the agent believes Figure 15.2 Three Blocks-World Situations1115.4 QuantificationnFinite domainnClear(B1) Clear(B2) Clear(B3) Clear(B4)nClear(B1) Clear(B2) Clear(B3) Clear(B4)nInfinite domainnProblems of long conjunctions or disjunctions impracticalnNew syntactic entities
12、nVariable symbolsnconsist of strings beginning with lowercase lettersntermnQuantifier symbols give expressive power to predicate-calculusn: universal quantifiern: existential quantifier1215.4 Quantificationn : wffn: wff within the scope of the quantifiern: quantified variablenClosed wff (closed sent
13、ence)nAll variable symbols besides in are quantified over in nPropertynFirst-order predicate calculinrestrict quantification over relation and function symbols)( ,)()(),()()()( ),()()(xfSyxREyxPxxRxPAx)()(),()()(xyyxyxxyyx1315.5 Semantics of QuantifiersnUniversal Quantifiersn()() = Truen() is True f
14、or all assignments of to objects in the domainnExample: (x)On(x,C) Clear(C)? in Figure 15.2nx: A, B, C, Floorninvestigate each of assignments in turn for each of the interpretationsnExistential Quantifiersn()() = Truen() is True for at least one assignments of to objects in the domain1415.5 Semantic
15、s of QuantifiersnUseful Equivalencesn()() ()()n()() ()()n()() () ()nRules of InferencenPropositional-calculus rules of inference predicate calculusnmodus ponensnIntroduction and elimination of nIntroduction of n eliminationnResolutionnTwo important rulesnUniversal instantiation (UI)nExistential gene
16、ralization (EG)1515.5 Semantics of QuantifiersnUniversal instantiationn()() ()n(): wff with variable n: constant symboln(): () with substituted for throughout nExample: (x)P(x, f(x), B) P(A, f(A), B)nExistential generalizationn() ()()n(): wff containing a constant symbol n(): form with replacing eve
17、ry occurrence of throughout nExample: (x)Q(A, g(A), x) (y)(x)Q(y, g(y), x)1615.6 Predicate Calculus as a Language for Representing KnowledgenConceptualizationsnPredicate calculusnlanguage to express and reason the knowledge about real worldnrepresented knowledge: explored throughout logical deductio
18、nnSteps of representing knowledge about a worldnTo conceptualize a world in terms of its objects, functions, and relationsnTo invent predicate-calculus expressions with objects, functions, and relationsnTo write wffs satisfied by the world: wffs will be satisfied by other interpretations as well1715
19、.6 Predicate Calculus as a Language for Representing KnowledgenUsage of the predicate calculus to represent knowledge about the world in AInJohn McCarthy (1958): first usenGuha & Lenat 1990, Lenat 1995, Lenat & Guha 1990nCYC projectnrepresent millions of commonsense facts about the worldnNilsson 199
20、1: discussion of the role of logic in AInGenesereth & Nilsson 1987: a textbook treatment of AI based on logic1815.6 Predicate Calculus as a Language for Representing KnowledgenExamplesnExamples of the process of conceptualizing knowledge about a worldnAgent: deliver packages in an office buildingnPa
21、ckage(x): the property of something being a packagenInroom(x, y): certain object is in a certain roomnRelation constant Smaller(x,y): certain object is smaller than another certain objectn“All of the packages in room 27 are smaller than any of the packages in room 28”),Smaller()28,Inroom()27,Inroom(
22、)Package()Package(),(yxyxyxyx1915.6 Predicate Calculus as a Language for Representing Knowledgen“Every package in room 27 is smaller than one of the packages in room 29”nWay of stating the arrival time of an objectnArrived(x,z)nX: arriving objectnZ: time interval during which it arrivedn“Package A a
23、rrived before Package B”nTemporal logic: method of dealing with time in computer science and AI),Smaller()28,Inroom()27,Inroom()Package()Package()(),Smaller()28,Inroom()27,Inroom()Package()Package()(yxyxyxyxyxyxyxxyz2)Before(z1,z2)Arrived(B,z1)d(A,z2)Arrivez1,(2015.6 Predicate Calculus as a Language
24、 for Representing KnowledgenDifficult problems in conceptualizationn“The package in room 28 contains one quart of milk”nMass nounsnIs milk an object having the property of being whit?nWhat happens when we divide quart into two pints?nDoes it become two objects, or does it remain as one?nExtensions to the predicate calculusnallow one agent to make statements about the knowledge of another agentn“Robot A knows that Package B is in room 28”
