人工智能的课件CH8-FOL.ppt

1、智能计算研究中心X. First order logic (FOL) Autumn 2012Instructor: Wang XiaolongHarbin Institute of Technology, Shenzhen Graduate SchoolIntelligent Computation Research Center(HITSGS ICRC)2Outline Why FOL? Syntax and semantics of FOL Using FOL Wumpus world in FOL Knowledge engineering in FOL3Pros and cons of

2、 propositional logicJ Propositional logic is declarativeJ Propositional logic allows partial/disjunctive/negated information (unlike most data structures and databases)J Propositional logic is compositional: meaning of B1,1 P1,2 is derived from meaning of B1,1 and of P1,2J Meaning in propositional l

3、ogic is context-independent (unlike natural language, where meaning depends on context) Propositional logic has very limited expressive power (unlike natural language) E.g., cannot say pits cause breezes in adjacent squares“ except by writing one sentence for each square4First-order logic Whereas pr

4、opositional logic assumes the world contains facts First-order logic (like natural language) assumes a car contains Objects: people, houses, numbers, colors, baseball games, wars, Relations: red, round, prime, brother of, bigger than, part of, comes between, Functions: father of, best friend, one mo

5、re than, plus, 5Examples:“One plus two equals three”Objects:Relations:Properties:Functions:“Squares neighboring the Wumpus are smelly”Objects:Relations:Properties:Functions:6Examples:“One plus two equals three”Objects:one, two, three, one plus twoRelations:equalsProperties:-Functions:plus (“one plus

6、 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:-7Semanticsthere is a correspondence between functions, which retur

7、n values predicates, which are true or falseFunction: father_of(Mary) = BillPredicate: father_of(Mary, Bill)8Syntax of FOL: Basic elements ConstantsKingJohn, 2, HIT,. PredicatesBrother, ,. FunctionsSqrt, LeftLegOf,. Variablesx, y, a, b,. Connectives, , , , Equality= Quantifiers , 9Atomic sentencesAt

8、omic sentence =predicate (term1,.,termn) or term1 = term2Term =function (term1,.,termn) or constant or variable E.g., Brother(KingJohn,RichardTheLionheart) (Length(LeftLegOf(Richard), Length(LeftLegOf(KingJohn)10Complex sentences Complex sentences are made from atomic sentences using connectivesS, S

9、1 S2, S1 S2, S1 S2, S1 S2,E.g. Sibling(KingJohn,Richard) Sibling(Richard,KingJohn) (1,2) (1,2) (1,2) (1,2) 11Truth in first-order logicSentences are true with respect to a model and an interpretationModel contains objects (domain elements) and relations among themInterpretation specifies referents f

10、orconstant symbols objectspredicate symbols relationsfunction symbols functional relationsAn atomic sentence predicate(term1,.,termn) is trueiff the objects referred to by term1,.,termnare in the relation referred to by predicate12Models for FOL: Example13Universal quantification Everyone at HIT is

11、smart:x At(x,HIT) Smart(x) x P is true in a model m iff P is true with x being each possible object in the model Roughly speaking, equivalent to the conjunction of instantiations of PAt(KingJohn, HIT) Smart(KingJohn) At(Richard, HIT) Smart(Richard) At(HIT, HIT) Smart(HIT) .14A common mistake to avoi

12、d Typically, is the main connective with Common mistake: using as the main connective with :x At(x, HIT) Smart(x)means “Everyone is at HIT and everyone is smart”15Existential quantification Someone at HIT is smart:x At(x, HIT) Smart(x) x P is true in a model m iff P is true with x being some possibl

13、e object in the modelRoughly speaking, equivalent to the disjunction of instantiations of PAt(KingJohn, HIT) Smart(KingJohn) At(Richard, HIT) Smart(Richard) At(HIT, HIT) Smart(HIT) .16Another common mistake to avoid Typically, is the main connective with Common mistake: using as the main connective

14、with :x At(x, HIT) Smart(x)is true if there is anyone who is not at HIT!17Properties of quantifiersx y is the same as y xx y is the same as y x x y is not the same as y xx y Loves(x,y) “There is a person who loves everyone in the world”y x Loves(x,y) “Everyone in the world is loved by at least one p

15、erson”Quantifier duality: each can be expressed using the otherx Likes(x,IceCream) x Likes(x,IceCream)x Likes(x,Broccoli) x Likes(x,Broccoli)18Equalityterm1 = term2 is true under a given interpretation if and only if term1 and term2 refer to the same object E.g., definition of Sibling in terms of Pa

16、rent:x,y Sibling(x,y) (x = y) m,f (m = f) Parent(m,x) Parent(f,x) Parent(m,y) Parent(f,y)19Using FOLThe kinship domain: Brothers are siblingsx,y Brother(x,y) Sibling(x,y) Ones mother is ones female parentm,c Mother(c) = m (Female(m) Parent(m,c) “Sibling” is symmetricx,y Sibling(x,y) Sibling(y,x)20Us

17、ing FOLThe set domain: s Set(s) (s = ) (x,s2 Set(s2) s = x|s2)x,s x|s = x,s x s s = x|sx,s x s y,s2 (s = y|s2 (x = y x s2)s1,s2 s1 s2 (x x s1 x s2)s1,s2 (s1 = s2) (s1 s2 s2 s1)x,s1,s2 x (s1 s2) (x s1 x s2)x,s1,s2 x (s1 s2) (x s1 x s2)21Interacting with FOL KBsSuppose a wumpus-world agent is using an

18、 FOL KB and perceives a smell and a breeze (but no glitter) at t=5:Tell(KB,Percept(Smell,Breeze,None,5)Ask(KB,a BestAction(a,5)I.e., does the KB entail some best action at t=5?Answer: Yes, a/Shoot substitution (binding list)Given a sentence S and a substitution , S denotes the result of plugging int

19、o S; e.g.,S = Smarter(x,y) = x/Hillary,y/BillS = Smarter(Hillary,Bill)Ask(KB,S) returns some/all such that KB 22Knowledge base for the wumpus world Perception t,s,b Percept(s,b,Glitter,t) Glitter(t) Reflex t Glitter(t) BestAction(Grab,t)23Deducing hidden properties x,y,a,b Adjacent(x,y,a,b) a,b x+1,

20、y, x-1,y,x,y+1,x,y-1 Properties of squares: s,t At(Agent,s,t) Breeze(t) Breezy(s)Squares are breezy near a pit: Diagnostic rule-infer cause from effects Breezy(s) r Adjacent(r,s) Pit(r) Causal rule-infer effect from causer Pit(r) s Adjacent(r,s) Breezy(s) 24Knowledge engineering in FOL1.Identify the

21、 task2.Assemble the relevant knowledge3.Decide on a vocabulary of predicates, functions, and constants4.Encode general knowledge about the domain5.Encode a description of the specific problem instance6.Pose queries to the inference procedure and get answers7.Debug the knowledge base25The electronic

22、circuits domainOne-bit full adder26The electronic circuits domain1.Identify the taskDoes the circuit actually add properly? (circuit verification)2.Assemble the relevant knowledgeComposed of wires and gates; Types of gates (AND, OR, XOR, NOT)Irrelevant: size, shape, color, cost of gates3.Decide on a

23、 vocabularyAlternatives:Type(X1) = XORType(X1, XOR)XOR(X1)27The electronic circuits domain4.Encode general knowledge of the domaint1,t2 Connected(t1, t2) Signal(t1) = Signal(t2)t Signal(t) = 1 Signal(t) = 01 0t1,t2 Connected(t1, t2) Connected(t2, t1)g Type(g) = OR Signal(Out(1,g) = 1 n Signal(In(n,g

24、) = 1g Type(g) = AND Signal(Out(1,g) = 0 n Signal(In(n,g) = 0g Type(g) = XOR Signal(Out(1,g) = 1 Signal(In(1,g) Signal(In(2,g)g Type(g) = NOT Signal(Out(1,g) Signal(In(1,g)28The electronic circuits domain5.Encode the specific problem instanceType(X1) = XOR Type(X2) = XORType(A1) = AND Type(A2) = AND

25、Type(O1) = ORConnected(Out(1,X1),In(1,X2)Connected(In(1,C1),In(1,X1)Connected(Out(1,X1),In(2,A2)Connected(In(1,C1),In(1,A1)Connected(Out(1,A2),In(1,O1) Connected(In(2,C1),In(2,X1)Connected(Out(1,A1),In(2,O1) Connected(In(2,C1),In(2,A1)Connected(Out(1,X2),Out(1,C1) Connected(In(3,C1),In(2,X2)Connecte

26、d(Out(1,O1),Out(2,C1) Connected(In(3,C1),In(1,A2)29The electronic circuits domain6. Pose queries to the inference procedureWhat are the possible sets of values of all the terminals for the adder circuit? i1,i2,i3,o1,o2 Signal(In(1, C1) = i1 Signal(In(2,C1) = i2 Signal(In(3,C1) = i3 Signal(Out(1,C1)

27、= o1 Signal(Out(2,C1) = o27.Debug the knowledge baseMay have omitted assertions like 1 030Summary First-order logic: objects and relations are semantic primitives syntax: constants, functions, predicates, equality, quantifiers Increased expressive power: sufficient to define wumpus world 31Assignments Ex 8.3, 8.15