《经典逻辑推理》PPT课件.ppt
《《经典逻辑推理》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《经典逻辑推理》PPT课件.ppt(62页珍藏版)》请在三一办公上搜索。
1、第四章经典逻辑推理,4.1 基本概念4.2 自然演绎推理4.3 归结演绎推理4.4 与或形演绎推理,4.1 基本概念,4.1.1 什么是推理所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。在人工智能中,推理是由程序实现的,称为推理机。,4.1.2 推理方式及其分类,1. 演绎推理、归纳推理、默认推理演绎推理:从一般到特殊。例如三段论。归纳推理:从个体到一般。默认推理:缺省推理,在知识不完全的情况下假设某些条件已经具备所进行的推理。2. 确定性、不确定性推理3. 单调推理、非单调推理推出的结论是否单调增加4. 启发式、非启发式推理所谓启发性知识是指与问题有关且能加快推理进程、求得问题最
2、优解的知识。5. 基于知识的推理(专家系统) 、统计推理、直觉推理(常识性推理),4.1.3 推理的控制策略,推理的控制策略主要包括:推理方向、搜索策略、冲突消解策略、求解策略及限制策略。1. 正向推理(数据驱动推理)正向推理的基本思想是:从用户提供的初始已知事实出发,在知识库KB中找出当前可适用的知识,构成可适用的知识集KS,然后按某种冲突消解策略从KS中选出一条知识进行推理,并将推出的新事实加入到数据库DB中,作为下一步推理的已知事实。在此之后,再在知识库中选取可适用的知识进行推理。如此重复进行这一过程,直到求得所要求的解。,正向推理示意图,2 逆向推理,逆向推理的基本思想是:首先选定一个
3、假设目标,然后寻找支持该假设的证据,若所需的证据都能找到,则说明原假设是成立的;若找不到所需要的证据,则说明原假设不成立,此时需要另作新的假设。,逆向推理示意图,动物识别的例子,已知事实:一动物有毛,吃草,黑条纹R1:动物有毛 哺乳类 R2:动物产奶 哺乳类 R3:哺乳类 吃肉 食肉类 R4:哺乳类 吃草 有蹄类 R5:食肉类 黄褐色 有斑点 猎狗 R6:食肉类 黄褐色 黑条纹 虎 R7:有蹄类 长脖 长颈鹿 R8:有蹄类 黑条纹 斑马,3. 混合推理先正向推理后逆向推理先逆向推理后正向推理4. 双向推理正向推理与逆向推理同时进行,且在推理过程中的某一步上“碰头”。5. 求解策略只求一个解,还
4、是求所有解以及最优解。6. 限制策略限制搜索的深度、宽度、时间、空间等等。,所谓模式匹配是指对两个知识模式(例如两个谓词公式、框架片断、语义网络片断)进行比较,检查这两个知识模式是否完全一致或者近似一致。模式匹配可分为确定性匹配与不确定性匹配。确定性匹配是指两个知识模式完全一致,或者经过变量代换后变得完全一致。 知识:IF father(x,y) and man(y) THEN son(y,x) 事实:father(李四,李小四) and man(李小四)不确定性匹配是指两个知识模式不完全一致,但是它们的相似程度又在规定的限度内。,4.1.4 模式匹配,变量代换,定义4.1 代换是一个形如t1
5、/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的特例。 规则: IF father(x,y) and man(y) THEN son(y,x)事实: father(李四,李小四) an
6、d man(李小四) 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当yix1,x2,xn后剩下的元素所构成的集合,记为 。注: ti表示对ti运用进行代换。就是对一个公式F先运用进行代换,然后再运用进行代换:F( )
7、=(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,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的一个合一,如果对任一个合一都存在
8、一个置换,使得=则称是一个最一般的合一。(1)置换过程是一个用项代替变元的过程,因此是一个从一般到特殊的过程。(2) 最一般合一是唯一的。,求取最一般合一,差异集:两个公式中相同位置处不同符号的集合。例:F1:P(x,y,z), F2:P(x,f(a),h(b),则D1=y,f(a), D2=z,h(b)是差异集。求取最一般合一的算法:令k=0,Fk=F, k=。 是空代换。若Fk只含一个表达式,则算法停止,k就是最一般合一。找出Fk的差异集Dk。若Dk中存在元素xk和tk,其中xk是变元,tk是项,且xk不在tk中出现,则置:Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后转(2)
9、。若不存在这样的xk和tk则算法停止。算法终止,F的最一般合一不存在。,求取最一般合一的例子,例如,设 F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。令F0=F, 0=。F0中有两个表达式,所以0不是最一般合一。差异集:D0=a,z。代换: a/zF1= F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u) 。 1=0a/z=a/zD1=x,f(a) 。代换: f(a)/xF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u) 。 2=1f(a)/x=a/z,f(a)/x D2=g(y),u 。代换: g(y)/uF3=F2g
10、(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y) 。 3=2g(y)/u=a/z,f(a)/x,g(y)/u,4.1.5 冲突消解策略,冲突:多个知识都匹配成功。正向推理:多条产生式前件都与已知事实匹配成功逆向推理:多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是对知识进行排序。,几种冲突消解策略,按针对性排序优先选用针对性强的产生式规则。按已知事实的新鲜性排序优先选用与较多新事实匹配的规则。按匹配度排序在不确定性匹配中,计算两个知识模式的相似度(匹配度),并对其排序,相似度高的规则先推。按领域问题特点排序按上下文限制排序把规则按照下上文分组,并只能选取组中的
11、规则。按冗余限制排序冗余知识越少的规则先推。按条件个数排序条件少的规则先推。,4.2 自然演绎推理,从一组已知为真的事实出发,直接运用经典逻辑的推理规则推出结论的过程,称为自然演绎推理。其中,基本的推理规则是P规则、T规则、假言推理、拒取式推理等。假言推理的一般形式拒取式推理的一般形式,P规则:在推理的任何步骤都可以引入前提。T规则:推理时,如果前面步骤中有一个或者多个公式永真蕴含公式S,则可把S引入推理过程中。,4.3 归结演绎推理,定理证明即证明PQ(PQ)的永真性。根据反证法,只要证明其否定(PQ) 不可满足性即可。海伯伦(Herbrand)定理为自动定理证明奠定了理论基础;鲁滨逊(Ro
12、binson)提出的归结原理使机器定理证明成为现实。,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) 子句集: S= C1 ,C2 ,C3 ,Cn(3)任何谓词公式F都可通过等价关系及推理规则化为相应的子句集S。,把谓词公式化成子句集的步骤(1),1. 利用等价关系消去“”和“”例如公式可等价变换成2. 利用等价关系把“”
13、移到紧靠谓词的位置上上式经等价变换后3. 重新命名变元,使不同量词约束的变元有不同的名字上式经变换后,把谓词公式化成子句集的步骤(2),4. 消去存在量词a.存在量词不出现在全称量词的辖域内,则只要用一个新的个体常量替换受该量词约束的变元。b.存在量词位于一个或者多个全称量词的辖域内,此时要用Skolem函数f(x1,x2,xn)替换受该存在量词约束的变元。上式中存在量词(y)及(z)都位于(x)的辖域内,所以需要用Skolem函数替换,设替换y和z的Skolem函数分别是f(x)和g(x),则替换后得到5. 把全称量词全部移到公式的左边,把谓词公式化成子句集的步骤(3),6. 利用等价关系把
14、公式化为Skolem标准形Skolem标准形的一般形式是其中,M是子句的合取式,称为Skolem标准形的母式。上式化为Skolem标准形后得到7. 消去全称量词8. 对变元更名,使不同子句中的变元不同名上式化为9. 消去合取词,就得到子句集,子句集的性质,(1)子句集中子句之间是合取关系。(2)子句集中的变元受全称量词的约束。,子句集的意义,子句集S的不可满足性:对于任意论域中的任意一个解释,S中的子句不能同时取得真值T。定理4.1 设有谓词公式F,其子句集为S,则F不可满足的充要条件是S不可满足。要证明PQ永真,只需证明公式F=(PQ)永假,即S不可满足。,4.3.2 Herbrand理论,
15、为了判断子句集的不可满足性,需要对所有可能论域上的所有解释进行判定。只有当子句集对任何非空个体域上的任何一个解释都是不可满足的,才可断定该子句集是不可满足的。海伯伦构造了一个特殊的论域(海伯伦域),并证明只要对这个特殊域上的一切解释进行判定,就可知子句集是否不可满足。,海伯伦域,定义4.7 设S为子句集,则按下述方法构造的域H称为海伯伦域,记为H域。(1)令H0是S中所有个体常量的集合,若S中不包含个体常量,则令H0a,其中a为任意指定的一个个体常量。(2)令Hi+1=HiS中所有n元函数f(x1,xn)|xj(j=1,n)是Hi中的元素,其中i=0,1,2,。例4.3 求子句集S=P(x)Q
16、(x),R(f(y)的H域。解:此例中没有个体常量,任意指定一个常量a作为个体常量,得到H0=aH1=a,f(a)H2=a,f(a),f(f(a)H3=a,f(a),f(f(a),f(f(f(a)H=a,f(a),f(f(a),f(f(f(a),子句集S在H域上的解释就是对S中出现的常量、函数及谓词进行指派。定义4.8 子句集S在H域上的一个解释I满足下列条件:(1)在解释I下,常量映射到自身;(2)S中的任一个n元函数是HnH的映射。即设 h1,h2,H,则f(h1,h2,hn)H;(3)S中的任一个n元谓词是HnT,F的映射。谓 词的真值可以指派为T,也可为F。,在H域上进行解释的意义,意
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 经典逻辑推理 经典 逻辑推理 PPT 课件
链接地址:https://www.31ppt.com/p-1380821.html