《人工智能：一种现代方法ch09 inferenceFOL - 2016》由会员分享，可在线阅读，更多相关《人工智能：一种现代方法ch09 inferenceFOL - 2016（39页珍藏版）》请在金锄头文库上搜索。
1、1一阶逻辑推理1 代换、全称量词实例化、存在量词实例化2 合一、 CNF、归结推理5New Quantifiers in FOL (review) Universal quantifier(全称量词 ) x means “For all x” Always true Usually used with x means “Not all x” Existential quantifier (存在量词 ) x means “There exists an x” True for at least one interpretation Usually used with x means “There
2、 exists no x”6Sentences in FOL (review) Term (项 ) Constant symbol, variable symbol, or function symbol atomic sentence(原子语句 ) Predicate symbol with value true or false Represents a relation between terms complex sentence(复合语句 ) Atom(s) joined together using logical connectives and/or quantifiers7Con
3、cepts （ review） Literal(文字 ) 原子、原子的否定 Clause and Clause set disjunctions of literals(文字的析取 ) e.g. P(x) Q(x,y), P(x,c)R(x,y,f(x) CNF(Conjunctive normal form, 合取范式 ) conjunction of disjunctions of literals CNFs do not contain quantifiers!81 代换、量词实例化9 已知命题逻辑的推理策略，一阶逻辑下如何推理？10Logics in General What exis
4、ts in the world TRUTH Propositional Logic: facts hold or do not hold. First Order Logic: objects with relations between them that hold or do not hold First order inference can be done by converting the knowledge base to PL and using propositional inference. How to convert universal quantifiers? How
5、to convert existential quantifiers?11Barber Paradox The barber shave all those men, and only those men, who do not shave themselves. There is no barber in town. B(x): x is a barber. H(x,y): x shave y.FOL sentences: _ _ _ how to prove it using resolution like in PL?12Barber Paradox The barber shave a
6、ll those men, and only those men, who do not shave themselves. There is no barber in town. B(x): x is a barber. H(x,y): x shave y.FOL sentences: (x)(B(x) (y)(H(y,y) H(x,y) (x)(B(x) (y)(H(y,y) H(x,y) (x)B(x) how to prove it using resolution like in PL? convert to CNF, which contains no quantifiers, a
7、nd then use resolution rules.13Substitution 9.1.1 PR, QR can infer PQ using resolution in PL. PR(a), QR(a) can infer PQ can PR(x), QR(y) infer PQ ? First, we need substitution14Substitution 9.1.1 FOL is Similar to PL Important differences Quantifiers Variables Important concept: substitution(代换 ) Su
8、bst(, ), is like x/Michael, y/Bob replace variables with terms)()()( xM o r ta lxM a nx )()()(,/S u b s t ( xM o r t a lxM a nxM i c h a e lx )()( M i c h a e lM o r t a lM i c h a e lM a n substitutionsentence15Substitution 9.1.1 Subst(Michael/x, Man(Michael) Mortal(Michael) = Max(x) Mortal(x) corr
9、ect? Subst(Michael/Bob, Man(Michael) Mortal(Michael) = Max(Bob) Mortal(Bob) correct? Subst(x/Bob, Man(x) Mortal(x) = Max(Bob) Mortal(Bob) correct?16Substitution 9.1.1 Subst(Michael/x, Man(Michael) Mortal(Michael) = Max(x) Mortal(x) no Subst(Michael/Bob, Man(Michael) Mortal(Michael) = Max(Bob) Mortal
10、(Bob) no Subst(x/Bob, Man(x) Mortal(x) = Max(Bob) Mortal(Bob) yes17inference rules for quantifiers9.1.1 Universal Instantiation (实例化 ) Everyone at AI class is smart. (x) (AtAI(x) Smart(x) after substitution (代换） x/张三 , x/李四 , x/brother(王五 ) becomes AtAI(张三 ) Smart(张三 ) AtAI(李四 ) Smart(李四 ) AtAI(brot
11、her(王五 ) Smart(brother(王五 ) Weve replaced the variable with all possibleground terms (基项 ,terms without variables),/(S U B S T gvv18inference rules for quantifiers9.1.1 Existential Instantiation (实例化 ) Example: Someone at AI is sleeping in class. (x)(AtAI(x)Sleep(x) Lets call it a becomes: (AtAI(a)S
12、leep(a) You can replace the variable with a constant symbol that does not appear elsewhere in the knowledge base The constant symbol is a Skolem constant),/(S U B S T kvv19inference rules for quantifiers9.1.1 Existential instantiation consider: Everyone has a mother. y x Mother(x,y) how to instantia
13、te x? y Mother(M12,y) correct?M12 a constant symbol that does not appear elsewhere in the knowledge base20inference rules for quantifiers9.1.1 Existential instantiation consider: Everyone has a mother. y x Mother(x,y) how to instantiate x? y Mother(m(y),y) m(y) is a Skolem function21inference rules
14、for quantifiers9.1.1 Instantiate (x1)(xk-1)(xk)(Qxk+1)(Qxn)M(x1, , xk, , xn)replace xk with a Skolem function f(x1, , xk-1)(x1)(xk-1)(Qxk+1)(Qxn)M(x1,f(x1,xk-1),xn)22 substitute more than once for ? substitute more than once for ?23inference rules for quantifiers9.1.1 Only perform substitution once for existential quantifier x Kill (x, Victim) There exists a x who killed Victim. Someone killed the victim Maybe more than one person killed the victim Existential quantifier says at least one person was killer Replacement is Kill (Murderer, Victim)24合一、
