资源预览内容
第1页 / 共39页
第2页 / 共39页
第3页 / 共39页
第4页 / 共39页
第5页 / 共39页
第6页 / 共39页
第7页 / 共39页
第8页 / 共39页
第9页 / 共39页
第10页 / 共39页
亲,该文档总共39页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
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 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 quantifiers7Concepts ( 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 exists 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 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 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: (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, and 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(代换 ) Subst(, ), 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) correct? 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(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(brother(王五 ) 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)Sleep(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 instantiate 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 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合一、
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号