3-人工智能经典逻辑推理

人工智能ArtificialIntelligence主讲：杨利英西安电子科技大学E_mail：[e-mail]第三章经典逻辑推理3.1基本概念3.2自然演绎推理3.3归结演绎推理3.4与或形演绎推理3.1基本概念3.1.1什么是推理所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。在人工智能中，推理是由程序实现的，称为推理机。3.1.2推理方式及其分类1.演绎推理、归纳推理、默认推理演绎推理：从一般到特殊。例如三段论。归纳推理：从个体到一般。默认推理：缺省推理，在知识不完全情况下假设某些条件已经具备所进行的推理。2.确定性、不确定性推理3.1.2推理方式及其分类3.单调推理、非单调推理推出的结论是否单调增加5.基于知识的推理（专家系统）、统计推理、直觉推理（常识性推理）4.启发式、非启发式推理所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。3.1.3推理的控制策略推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制策略。1.正向推理（数据驱动推理）基本思想：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用的知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中，作为下一步推理的已知事实。在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的解。正向推理示意图开始退出把初始已知事实送入DBDB中包含问题的解？KB中有可适用的知识？把KB中所有使用知识都选出来送入KSKS为空？按冲突消解策略从KS中选出一条知识进行推理推出的是新事实？将该新事实加入DB中用户可补充新事实？把用户提供的新事实加入DB中YNNYNYNYNY成功失败2逆向推理基本思想首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。逆向推理示意图开始退出提出假设该假设在DB中？该假设是证据？在KB中找出所有能导出该假设的知识送入KS有此事实？该假设成立该假设成立，并将此事实存入数据库YNYNNNY从KS中选出一条知识，并将该知识的一个运用条件作为新的假设目标还有假设？询问用户Y动物识别的例子(正向推理)已知事实：一动物{有毛，吃草，黑条纹}R1：动物有毛→哺乳类R2：动物产奶→哺乳类R3：哺乳类∧吃肉→食肉类R4：哺乳类∧吃草→有蹄类R5：食肉类∧黄褐色∧有斑点→猎狗R6：食肉类∧黄褐色∧黑条纹→虎R7：有蹄类∧长脖→长颈鹿R8：有蹄类∧黑条纹→斑马3.1.3推理的控制策略3.混合推理先正向推理后逆向推理先逆向推理后正向推理4.双向推理正向推理与逆向推理同时进行，且在推理过程中的某一步上“碰头”。5.求解策略只求一个解，还是求所有解以及最优解。6.限制策略限制搜索的深度、宽度、时间、空间等等。模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)进行比较，检查这两个知识模式是否完全一致或者近似一致。3.1.4模式匹配模式匹配可分为确定性匹配与不确定性匹配。3.1.4模式匹配确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。知识：IFfather(x,y)andman(y)THENson(y,x)事实：father(李四，李小四)andman(李小四)不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。变量代换（置换）定义代换是一个形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中t1,t2,…,tn是项（常量、变量、函数）；x1,x2,…,xn是（某一公式中）互不相同的变元；ti/xi表示用ti代换xi不允许ti与xi相同，也不允许变元xi循环地出现在另一个tj中。例如：{a/x,f(b)/y,w/z}是一个代换{g(y)/x,f(x)/y}不是代换{g(a)/x,f(x)/y}是代换令θ={t1/x1,t2/x2,…,tn/xn}为一个代换，F为表达式，则Fθ表示对F用ti代换xi后得到的表达式。Fθ称为F的特例。规则:IFfather(x,y)andman(y)THENson(y,x)事实:father(李四，李小四)andman(李小四)F=father(x,y)∧man(y)θ={李四/X,李小四/Y}Fθ=father(李四，李小四)∧man(李小四)结论:son(李小四,李四)代换的复合定义设θ={t1/x1,t2/x2,…,tn/xn}λ={u1/y1,u2/y2,…,um/ym}是两个代换，则这两个代换的复合也是一个代换，它是从{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym}中删去如下两种元素：tiλ/xi当tiλ=xiui/yi当yi∈{x1,x2,…,xn}后剩下的元素所构成的集合，记为θ°λ。注(1)tiλ表示对ti运用λ进行代换。(2)θ°λ就是对一个公式F先运用θ进行代换，然后再运用λ进行代换：F（θ°λ）=（Fθ）λ代换复合的例子例如，设有代换θ={f(y)/x,z/y}λ={a/x,b/y,y/z}则θ°λ=?θ°λ={f(y)λ/x,zλ/y,a/x,b/y,y/z}={f(b)/x,y/y,a/x,b/y,y/z}={f(b)/x,y/z}公式集的合一定义设有公式集F={F1,F2,…,Fn}，若存在一个代换λ使得F1λ=F2λ=…=Fnλ则称λ为公式集F的一个合一，且称F1,F2,…,Fn是可合一的。例如，设有公式集F={P(x,y,f(y)),P(a,g(x),z)}则下式是它的一个合一：λ={a/x,g(a)/y,f(g(a))/z}一个公式集的合一一般不唯一。最一般合一定义设σ是公式集F的一个合一，如果对任一个合一θ都存在一个代换λ，使得θ=σ°λ则称σ是一个最一般的合一。最一般合一是唯一的。求取最一般合一差异集：两个公式中相同位置处不同符号的集合。例如：F={F1:P(x,y,z),F2:P(x,f(a),h(b))}则D1={y,f(a)},D2={z,h(b)}求取最一般合一的算法：1.令k=0,Fk=F,σk=ε，ε是空代换。2.若Fk只含一个表达式，则算法停止，σk就是最一般合一。3.找出Fk的差异集Dk。4.若Dk中存在元素xk和tk，其中xk是变元，tk是项，且xk不在tk中出现，则置：Fk+1=Fk{tk/xk}σK+1=σk°{tk/xk}k=k+1然后转(2)。若不存在这样的xk和tk则算法停止。5.算法终止，F的最一般合一不存在。求取最一般合一的例子求公式集F={P(a,x,f(g(y))),P(z,f(z),f(u))}的最一般合一。求取最一般合一的例子F={P(a,x,f(g(y))),P(z,f(z),f(u))}求其最一般合一的过程：1.令F0=F,σ0=ε。F0中有两个表达式，所以σ0不是最一般合一。2.差异集：D0={a,z}。代换：{a/z}3.F1=F0{a/z}={P(a,x,f(g(y))),P(a,f(a),f(u))}。σ1=σ0°{a/z}={a/z}D1={x,f(a)}。代换：{f(a)/x}F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))}。σ2=σ1°{f(a)/x}={a/z,f(a)/x}D2={g(y),u}。代换：{g(y)/u}F3=F2{g(y)/u}={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))}。σ3=σ2°{g(y)/u}={a/z,f(a)/x,g(y)/u}至此，求得最一般合一{a/z,f(a)/x,g(y)/u}3.1.5冲突消解策略冲突：多个知识都匹配成功。正向推理：多条产生式前件都与已知事实匹配成功逆向推理：多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是对知识进行排序。几种冲突消解策略1.按针对性排序优先选用针对性强的产生式规则。2.按已知事实的新鲜性排序优先选用与较多新事实匹配的规则。3.按匹配度排序在不确定性匹配中，计算两个知识模式的相似度(匹配度)，并对其排序，相似度高的规则先推。4.按领域问题特点排序5.按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。6.按冗余限制排序冗余知识越少的规则先推。7.按条件个数排序条件少的规则先推。3.2自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程，称为自然演绎推理。其中，基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式,PPQQ,PQQPP规则：在推理的任何步骤都可以引入前提。T规则：推理时，如果前面步骤中有一个或者多个公式永真蕴含公式S，则可把S引入推理过程中。3.2自然演绎推理3.3归结演绎推理定理证明：要证明P→Q(¬P∨Q)的永真性。根据反证法，只要证明其否定(P∧¬Q)不可满足性即可。归结：Resolution，也称为消解，消解原理海伯伦(Herbrand)定理为自动定理证明奠定了理论基础；鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。3.3.1子句在谓词逻辑中，把原子谓词公式及其否定统称为文字。如：P(x)，¬P(x,f(x))，Q(x,g(x))定义：不包含任何文字的子句称为空子句。定义：任何文字的析取式称为子句。例如：P(x)∨Q(x),¬P(x,f(x))∨Q(x,g(x))子句集(1)合取范式：C1∧C2∧C3…∧Cn(2)子句集:S={C1,C2,C3…,Cn}(3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S把谓词公式化成子句集的步骤(1)1.利用等价关系消去“→”和“↔”例如公式可等价变换成2.利用等价关系把“¬”移到紧靠谓词的位置上上式经等价变换后3.重新命名变元，使不同量词约束的变元有不同的名字上式经变换后()(()(,)()((,)(,)))xyPxyyQxyRxy()(()(,)()((,)(,)))xyPxyyQxyRxy()(()(,)()((,)(,)))xyPxyyQxyRxy()(()(,)()((,)(,)))xyPxyzQxzRxz把谓词公式化成子句集的步骤(2)4.消去存在量词a.存在量词前面没有全称量词时，则只要用一个新的个体常量替换受该量词约束的变元。b.存在量词前面有一个或者多个全称量词时，要用函数f(x1,x2,…,xn)替换受该存在量词约束的变元。上式中存在量词(y)及(z)都位于(x)的后面，所以需要用函数替换，设替换y和z的函数分别是f(x)和g(x)，则替换后得到5.把全称量词全部移到公式的左边()((,())((,())(,())))xPxfxQxgxRxgx()(()(,)()((,)(,)))xyPxyzQxzRxz把谓词公式化成子句集的步骤(3)6.利用等价关系把公式化为Skolem标准形Skolem标准形的一般形式是其中，M是子句的合取式，称为Skolem标准形的母式。上式化为Skolem标准形后得到7.消去全称量词8.对变元更名，使不同子句中的变元不同名上式化为9.消去合取词，就得到子句集()()()PQRPQPR12()()()nxxxM()(((,())(,()))((,())(,())))xPxfxQxgxPxfxRxgx((,())(,()))((,())(,()))PxfxQxgxPyfyRygy(,())(,())(,())(,())PxfxQxgxPyfyRygy()((,())((,())(,())))xPxfxQxgxRxgx子句集的性质（1）子句集中子句之间是合取关系。（2）子句集中的变元受全称量词的约束。子句集的