第三讲经典逻辑推理.

第四章经典逻辑推理4.1基本概念4.2自然演绎推理4.3归结演绎推理4.4与或形演绎推理如何实现推理？逻辑方法是自动证明中常用的方法如何进行逻辑推理？推理的过程怎样？怎么实现推理？柯南的推理过程观察结果时钟与分钟重叠在一起时间是六点半推理依据正常的时钟如果是六点半，那么时钟与分钟应该是分开的推理结果有人故意移动过时钟人类的推理可以理解语义机器如何进行这样类似的推理？需要将推理的过程和理解分开，使其形式化事实规则结论推理的一般形式已知事实：事实1，事实2，...规则：如果事实1那么结论1如果事实2那么结论2….得到：结论1，结论2将事实与规则借助一些符号来表示，推理过程就可以被形式化P:某已知事实P→Q:如果P，那么Q结论：Q符号与形式语言自然语言不适合计算机处理她用红色水彩笔写了个蓝字。小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑符号与形式语言自然语言不适合计算机处理她用红色水彩笔写了个蓝字。小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑命题逻辑谓词逻辑符号与形式语言自然语言不适合计算机处理她用红色水彩笔写了个蓝字。小王不方便接电话，他方便去了。需要一种无歧义，方便存储和表达的形式化符号表征体系数理逻辑命题逻辑谓词逻辑如果不下雨，我就去你家玩﹁P→Q今天没有下雨﹁P我去了你家Q凡人都会死x(Man(x)Mortal(x))苏格拉底是人Man(Socrates)苏格拉底会死Mortal(Socrates)4.1基本概念4.1.1什么是推理所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。在人工智能中，推理是由程序实现的，称为推理机。4.1.2推理方式及其分类1.演绎推理、归纳推理、默认推理演绎推理：从一般到特殊。例如三段论。归纳推理：从个体到一般。默认推理：缺省推理，在知识不完全的情况下假设某些条件已经具备所进行的推理。2.确定性、不确定性推理3.单调推理、非单调推理推出的结论是否单调增加4.启发式、非启发式推理所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。5.基于知识的推理（专家系统）、统计推理、直觉推理（常识性推理）4.1.3推理的控制策略推理的控制策略主要包括：推理方向、搜索策略、冲突消解策略、求解策略及限制策略。1.正向推理（数据驱动推理）正向推理的基本思想是：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用的知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库DB中，作为下一步推理的已知事实。在此之后，再在知识库中选取可适用的知识进行推理。如此重复进行这一过程，直到求得所要求的解。正向推理示意图开始退出把初始已知事实送入DBDB中包含问题的解？KB中有可适用的知识？把KB中所有使用知识都选出来送入KSKS为空？按冲突消解策略从KS中选出一条知识进行推理推出的是新事实？将该新事实加入DB中用户可补充新事实？把用户提供的新事实加入DB中YNNYNYNYNY成功失败动物识别的例子已知事实：一动物{有毛，吃草，黑条纹}R1：动物有毛→哺乳类R2：动物产奶→哺乳类R3：哺乳类∧吃肉→食肉类R4：哺乳类∧吃草→有蹄类R5：食肉类∧黄褐色∧有斑点→猎狗R6：食肉类∧黄褐色∧黑条纹→虎R7：有蹄类∧长脖→长颈鹿R8：有蹄类∧黑条纹→斑马2逆向推理逆向推理的基本思想是：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若找不到所需要的证据，则说明原假设不成立，此时需要另作新的假设。逆向推理示意图开始退出提出假设该假设在DB中？该假设是证据？在KB中找出所有能导出该假设的知识送入KS有此事实？该假设成立该假设成立，并将此事实存入数据库YNYNNNY从KS中选出一条知识，并将该知识的一个运用条件作为新的假设目标还有假设？询问用户Y动物识别系统r1：if该动物有毛发then该动物是哺乳动物r2：if该动物有奶then该动物是哺乳动物r3：if该动物有羽毛then该动物是鸟r4：if该动物会飞and会下蛋then该动物是鸟r5：if该动物吃肉then该动物是食肉动物r6：if该动物有犬齿and有爪and眼盯前方then该动物是食肉动物r7：if该动物是哺乳动物and有蹄then该动物是有蹄类动物r8：if该动物是哺乳动物and是嚼反刍类动物then该动物是有蹄类动物r9：if该动物是哺乳动物and是食肉类动物and是黄褐色and身上有暗斑点then该动物是金钱豹r10：if该动物是哺乳动物and是食肉类动物and是黄褐色and身上有黑色条纹then该动物是虎r11：if该动物是有蹄类动物and有长脖子and有长腿and身上有暗斑点then该动物是长颈鹿r12：if该动物是有蹄类动物and身上有黑色条纹then该动物是斑马r13：if该动物是鸟and有长脖子and有长腿and不会飞then该动物是鸵鸟r14：if该动物是鸟and会游泳and不会飞and有黑白两色then该动物是企鹅r15：if该动物是鸟and善飞then该动物是信天翁3.混合推理先正向推理后逆向推理先逆向推理后正向推理4.双向推理正向推理与逆向推理同时进行，且在推理过程中的某一步上“碰头”。5.求解策略只求一个解，还是求所有解以及最优解。6.限制策略限制搜索的深度、宽度、时间、空间等等。所谓模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)进行比较，检查这两个知识模式是否完全一致或者近似一致。模式匹配可分为确定性匹配与不确定性匹配。确定性匹配是指两个知识模式完全一致，或者经过变量代换后变得完全一致。知识：IFfather(x,y)andman(y)THENson(y,x)事实：father(李四，李小四)andman(李小四)不确定性匹配是指两个知识模式不完全一致，但是它们的相似程度又在规定的限度内。4.1.4模式匹配变量代换定义4.1代换是一个形如{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(李小四,李四)代换的复合定义4.2设θ={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}后剩下的元素所构成的集合，记为θ°λ。注：tiλ表示对ti运用λ进行代换。θ°λ就是对一个公式F先运用θ进行代换，然后再运用λ进行代换：F（θ°λ）=（Fθ）λ代换的例子例如，设有代换θ={f(y)/x,z/w}λ={a/x,b/y,w/z}则θ°λ={f(y)λ/x,zλ/w,a/x,b/y,w/z}={f(b)/x,w/w,a/x,b/y,w/z}={f(b)/x,b/y,w/z}公式集的合一定义4.3设有公式集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}一个公式集的合一一般不唯一。最一般的合一定义4.4设σ是公式集F的一个合一，如果对任一个合一θ都存在一个代换λ，使得θ=σ°λ则称σ是一个最一般的合一。（1）代换过程是一个用项代替变元的过程，因此是一个从一般到特殊的过程。（2）最一般合一是唯一的。求取最一般合一差异集：两个公式中相同位置处不同符号的集合。例如：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))}求其最一般合一。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}1.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}4.1.5冲突消解策略冲突：多个知识都匹配成功。正向推理：多条产生式前件都与已知事实匹配成功逆向推理：多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是对知识进行排序。几种冲突消解策略1.按针对性排序优先选用针对性强的产生式规则。2.按已知事实的新鲜性排序优先选用与较多新事实匹配的规则。3.按匹配度排序在不确定性匹配中，计算两个知识模式的相似度(匹配度)，并对其排序，相似度高的规则先推。4.按领域问题特点排序5.按上下文限制排序把规则按照下上文分组，并只能选取组中的规则。6.按冗余限制排序冗余知识越少的规则先推。7.按条件个数排序条件少的规则先推。4.2自然演绎推理从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程，称为自然演绎推理。其中，基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式,PPQQ,PQQPP规则：在推理的任何步骤都可以引入前提。T规则：推理时，如果前面步骤中有一个或者多个公式永真蕴含公式S，则可把S引入推理过程中。4.3归结演绎推理定理证明即证明P→Q(¬P∨Q)的永真性。根据反证法，只要证明其否定(P∧¬Q)不可满足性即可。海伯伦(Herbrand)定理为自动定理证明奠定了理论基础；鲁滨逊(Robinson)提出的归结原理使机器定理证明成为现实。4.3.1子句在谓词逻辑中，把原子谓词公式及其否定统称为文字。如：P(x)，¬P(x,f(x))，Q(x,g(x))定义4.5：任何文字的析取式称为子句。例如：P(x)∨Q(x),¬P(x,f(x))∨Q(x,g(x))定义4.6：不包含任何文字的子句称为空子句。子句集(1)合取范式：C1∧C2∧C3…∧Cn(2)子句集: