人工智能经典逻辑推理ppt课件.ppt
《人工智能经典逻辑推理ppt课件.ppt》由会员分享,可在线阅读,更多相关《人工智能经典逻辑推理ppt课件.ppt(104页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、人工智能Artificial Intelligence主讲:杨利英主讲:杨利英西安电子科技大学西安电子科技大学E_mail:第三章第三章 经典逻辑推理经典逻辑推理3.1 基本概念基本概念3.2 自然演绎推理自然演绎推理3.3 归结演绎推理归结演绎推理3.4 与或形演绎推理与或形演绎推理3.1 基本概念3.1.1 什么是推理什么是推理所谓推理就是按某种策略由已知判断所谓推理就是按某种策略由已知判断推出另一个判断的思维过程。推出另一个判断的思维过程。在人工智能中,推理是由程序实现的,称在人工智能中,推理是由程序实现的,称为推理机。为推理机。3.1.2 推理方式及其分类1. 演绎推理、归纳推理、默认
2、推理演绎推理、归纳推理、默认推理演绎推理:从一般到特殊。例如三段论。演绎推理:从一般到特殊。例如三段论。归纳推理:从个体到一般。归纳推理:从个体到一般。默认推理:缺省推理,在知识不完全情况下默认推理:缺省推理,在知识不完全情况下假设某些条件已经具备所进行的推理。假设某些条件已经具备所进行的推理。2. 确定性、不确定性推理确定性、不确定性推理3.1.2 推理方式及其分类3. 单调推理、非单调推理单调推理、非单调推理推出的结论是否单调增加推出的结论是否单调增加 5. 基于知识的推理(专家系统)基于知识的推理(专家系统) 、统计、统计推理、直觉推理(常识性推理)推理、直觉推理(常识性推理)4. 启发
3、式、非启发式推理启发式、非启发式推理 所谓启发性知识是指与问题有关且能加所谓启发性知识是指与问题有关且能加快推理进程、求得问题最优解的知识。快推理进程、求得问题最优解的知识。3.1.3 推理的控制策略推理的控制策略主要包括:推理方向、推理的控制策略主要包括:推理方向、搜索策略、冲突消解策略、求解策略及搜索策略、冲突消解策略、求解策略及限制策略。限制策略。1. 正向推理正向推理(数据驱动推理)基本思想:基本思想:从用户提供的初始已知事实出发,在知识从用户提供的初始已知事实出发,在知识库库KBKB中找出当前可适用的知识,构成可适用的知中找出当前可适用的知识,构成可适用的知识集识集KSKS,然后按某
4、种冲突消解策略从,然后按某种冲突消解策略从KSKS中选出一中选出一条知识进行推理,并将推出的新事实加入到数据条知识进行推理,并将推出的新事实加入到数据库库DBDB中,作为下一步推理的已知事实。在此之后,中,作为下一步推理的已知事实。在此之后,再在知识库中选取可适用的知识进行推理。如此再在知识库中选取可适用的知识进行推理。如此重复进行这一过程,直到求得所要求的解。重复进行这一过程,直到求得所要求的解。正正向向推推理理示示意意图图开始退出把初始已知事实送入DBDB中包含问题的解?KB中有可适用的知识?把KB中所有使用知识都选出来送入KSKS为空?按冲突消解策略从KS中选出一条知识进行推理推出的是新
5、事实?将该新事实加入DB中用户可补充新事实?把用户提供的新事实加入DB中YNNYNYNYNY成功失败2 逆向推理基本思想基本思想 首先选定一个假设目标,然后寻找支持该假设首先选定一个假设目标,然后寻找支持该假设的证据,若所需的证据都能找到,则说明原假的证据,若所需的证据都能找到,则说明原假设是成立的;若找不到所需要的证据,则说明设是成立的;若找不到所需要的证据,则说明原假设不成立,此时需要另作新的假设。原假设不成立,此时需要另作新的假设。逆向推理示意图逆向推理示意图开始退出提出假设该假设在DB中?该假设是证据?在KB中找出所有能导出该假设的知识送入KS有此事实?该假设成立该假设成立,并将此事实
6、存入数据库YNYNNNY从KS中选出一条知识,并将该知识的一个运用条件作为新的假设目标还有假设?询问用户Y 动物识别的例子动物识别的例子(正向推理正向推理)已知事实:一动物已知事实:一动物有毛,吃草,黑条纹有毛,吃草,黑条纹nR1:动物有毛:动物有毛 哺乳类哺乳类 nR2:动物产奶:动物产奶 哺乳类哺乳类 nR3:哺乳类:哺乳类 吃肉吃肉 食肉类食肉类 nR4:哺乳类:哺乳类 吃草吃草 有蹄类有蹄类 nR5:食肉类:食肉类 黄褐色黄褐色 有斑点有斑点 猎狗猎狗 nR6:食肉类:食肉类 黄褐色黄褐色 黑条纹黑条纹 虎虎 nR7:有蹄类:有蹄类 长脖长脖 长颈鹿长颈鹿 nR8:有蹄类:有蹄类 黑条
7、纹黑条纹 斑马斑马3.1.3 推理的控制策略3. 混合推理混合推理先正向推理后逆向推理先正向推理后逆向推理先逆向推理后正向推理先逆向推理后正向推理4. 双向推理双向推理正向推理与逆向推理同时进行,且在推理过程正向推理与逆向推理同时进行,且在推理过程中的某一步上中的某一步上“碰头碰头”。5. 求解策略求解策略只求一个解,还是求所有解以及最优解。只求一个解,还是求所有解以及最优解。6. 限制策略限制策略限制搜索的深度、宽度、时间、空间等等。限制搜索的深度、宽度、时间、空间等等。模式匹配模式匹配是指对两个知识模式是指对两个知识模式(例如两例如两个谓词公式、框架片断、语义网络片断个谓词公式、框架片断、
8、语义网络片断)进行比较,检查这两个知识模式是否完进行比较,检查这两个知识模式是否完全一致或者近似一致。全一致或者近似一致。3.1.4 模式匹配模式匹配可分为模式匹配可分为确定性匹配确定性匹配与与不确定性匹配不确定性匹配。3.1.4 模式匹配确定性匹配确定性匹配是指两个知识模式完全一致,或者是指两个知识模式完全一致,或者经过变量代换后变得完全一致。经过变量代换后变得完全一致。 知识:知识:IF father(x,y) and man(y) THEN son(y,x) 事实:事实:father(李四,李小四李四,李小四) and man(李小四李小四)不确定性匹配不确定性匹配是指两个知识模式不完全
9、一致,是指两个知识模式不完全一致,但是它们的相似程度又在规定的限度内。但是它们的相似程度又在规定的限度内。变量代换(置换)定义定义 代换是一个形如代换是一个形如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)
10、/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(李四,李小四李四,李小四) and man(李小四李小四) F=father(x,y) man(y) = 李四李四/X,李小四李小四/Y F= father(李四,李小四李四,李小四) man(李小四李小四) 结论结论:
11、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当当yix1,x2,xn后剩下的元素所构成的集合,记为后剩下的元素所构成的集合,记为 。注注 (1) ti表示对表示对ti运用运用进行代换。进行代换。 (2)就是对一个公式就是对一个公式F先运用先运用进行代换,然后再进行代换
12、,然后再运用运用进行代换:进行代换: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)则下式是它的一
13、个合一:则下式是它的一个合一:=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)求取最一般合一的算法:求取最
14、一般合一的算法:1.令令k=0,Fk=F, k=,是空代换。是空代换。2.若若Fk只含一个表达式,则算法停止,只含一个表达式,则算法停止,k就是最一般合一。就是最一般合一。3.找出找出Fk的差异集的差异集Dk。4.若若Dk中存在元素中存在元素xk和和tk,其中,其中xk是变元,是变元,tk是项,且是项,且xk不在不在tk中出现,则置:中出现,则置:Fk+1=Fktk/xkK+1=ktk/xkk=k+1然后转然后转(2)。若不存在这样的。若不存在这样的xk和和tk则算法停止。则算法停止。5.算法终止,算法终止,F的最一般合一不存在。的最一般合一不存在。求取最一般合一的例子求公式集求公式集 F=P
15、(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/z3.F1= F0 a/z=P(a,x,f(g(y),P(a,f(a),f(u) 。 1=0a/z=a/zwD1=x,f(a) 。代换:。代换: f(a)/xwF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u)
16、 。 2=1f(a)/x=a/z,f(a)/x D2=g(y),u 。代换:。代换: g(y)/uwF3=F2g(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 至此,求得最一般合一至此,求得最一般合一 a/z,f(a)/x,g(y)/u 3.1.5 冲突消解策略冲突冲突:多个知识都匹配成功。:多个知识都匹配成功。正向推理正向推理:n多条产生式前件都与已知事实匹配成功多条产生式前件都与已知事实匹配成功逆向推理逆向推理:n多条规则后件都和同一个假设匹配成功多条规则后件都和同一个假设匹配成功冲突消解的基本思想都是
17、冲突消解的基本思想都是对知识进行排序对知识进行排序。几种冲突消解策略1.按针对性排序按针对性排序优先选用针对性强的产生式规则。优先选用针对性强的产生式规则。2.按已知事实的新鲜性排序按已知事实的新鲜性排序优先选用与较多新事实匹配的规则。优先选用与较多新事实匹配的规则。3.按匹配度排序按匹配度排序在不确定性匹配中,计算两个知识模式的相似度在不确定性匹配中,计算两个知识模式的相似度(匹配度匹配度),并对其排序,相似度高的规则先推。并对其排序,相似度高的规则先推。4.按领域问题特点排序按领域问题特点排序5.按上下文限制排序按上下文限制排序把规则按照下上文分组,并只能选取组中的规则。把规则按照下上文分
18、组,并只能选取组中的规则。6.按冗余限制排序按冗余限制排序冗余知识越少的规则先推。冗余知识越少的规则先推。7.按条件个数排序按条件个数排序条件少的规则先推。条件少的规则先推。3.2 自然演绎推理从一组已知为真的事实出发,直接运用从一组已知为真的事实出发,直接运用经典逻辑的推理规则推出结论的过程,经典逻辑的推理规则推出结论的过程,称为自然演绎推理。其中,基本的推理称为自然演绎推理。其中,基本的推理规则是规则是P规则、规则、T规则、假言推理、拒取规则、假言推理、拒取式推理等。式推理等。假言推理的一般形式假言推理的一般形式拒取式推理的一般形式拒取式推理的一般形式,P PQQ,PQQP P P规则规则
19、:在推理的任何步骤都可以引入前提。:在推理的任何步骤都可以引入前提。T T规则规则:推理时,如果前面步骤中有一个或者多:推理时,如果前面步骤中有一个或者多个公式永真蕴含公式个公式永真蕴含公式S S,则可把,则可把S S引入推理过程引入推理过程中。中。3.2 自然演绎推理3.3 归结演绎推理归结演绎推理定理证明:要证明定理证明:要证明PQ(PQ)的永真性。的永真性。根据反证法,只要证明其否定根据反证法,只要证明其否定(PQ) 不不可满足性即可。可满足性即可。归结:归结:Resolution,也称为消解,消解原理,也称为消解,消解原理海伯伦海伯伦(Herbrand)定理为自动定理证明定理为自动定理
20、证明奠定了理论基础;鲁滨逊奠定了理论基础;鲁滨逊(Robinson)提提出的归结原理使机器定理证明成为现实。出的归结原理使机器定理证明成为现实。3.3.1 子句子句w在谓词逻辑中,把原子谓词公式及其否定在谓词逻辑中,把原子谓词公式及其否定统称为统称为文字文字。 如:如: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) 子
21、句集子句集: S= C1 ,C2 ,C3 ,Cn(3)任何谓词公式任何谓词公式F都可通过等价关系及推都可通过等价关系及推理规则化为相应的子句集理规则化为相应的子句集S把谓词公式化成子句集的步骤(1)1. 利用等价关系消去利用等价关系消去“”和和“”例如公式例如公式可等价变换成可等价变换成2. 利用等价关系把利用等价关系把“”移到紧靠谓词的位置上移到紧靠谓词的位置上上式经等价变换后上式经等价变换后3. 重新命名变元,使不同量词约束的变元有不同的名字重新命名变元,使不同量词约束的变元有不同的名字上式经变换后上式经变换后()() ( , )()( ( , )( , )xy P x yy Q x yR
22、 x y ()( () ( , )()( , )( , )xy P x yyQ x yR x y ()()( , ) ()( ( , )( , )xyP x yy Q x yR x y ()()( , ) ()( ( , )( , )xyP x yz Q x zR x z 把谓词公式化成子句集的步骤(2)4. 消去存在量词消去存在量词a.存在量词前面没有全称量词时,则只要用一个新的个体存在量词前面没有全称量词时,则只要用一个新的个体常量替换受该量词约束的变元。常量替换受该量词约束的变元。b.存在量词前面有一个或者多个全称量词时,要用函数存在量词前面有一个或者多个全称量词时,要用函数f(x1,x
23、2,xn)替换受该存在量词约束的变元。替换受该存在量词约束的变元。上式中存在量词上式中存在量词( y)及及( z)都位于都位于( x)的后面,所以需的后面,所以需要用要用函数函数替换,设替换替换,设替换y和和z的函数分别是的函数分别是f(x)和和g(x),则,则替换后得到替换后得到5. 把全称量词全部移到公式的左边把全称量词全部移到公式的左边()( , ( ) ( ( , ( )( , ( )xP x f xQ x g xR x g x()()( , ) ()( ( , )( , )xyP x yz Q x zR x z 把谓词公式化成子句集的步骤把谓词公式化成子句集的步骤(3)6. 利用等价
24、关系把公式化为利用等价关系把公式化为Skolem标准形标准形Skolem标准形的一般形式是标准形的一般形式是其中,其中,M是子句的合取式,称为是子句的合取式,称为Skolem标准形的母式。标准形的母式。上式化为上式化为Skolem标准形后得到标准形后得到7. 消去全称量词消去全称量词8. 对变元更名,使不同子句中的变元不同名对变元更名,使不同子句中的变元不同名上式化为上式化为9. 消去合取词,就得到子句集消去合取词,就得到子句集()() ()PQ RP QP R12()()()nxxx M()( , ( )( , ( ) ( , ( )( , ( )xP x f xQ x g xP x f x
25、R x g x ( , ( )( , ( ) ( , ( )( , ( )P x f xQ x g xP y f yR y g y ( , ( )( , ( )( , ( )( , ( )P x f xQ x g xP y f yR y g y()( , ( ) ( ( , ( )( , ( )xP x f xQ x g xR x g x 子句集的性质子句集的性质(1)子句集中子句之间是合取关系。)子句集中子句之间是合取关系。(2)子句集中的变元受全称量词的约束。)子句集中的变元受全称量词的约束。 子句集的意义子句集子句集S的不可满足性的不可满足性:对于任意论域中:对于任意论域中的任意一个解释
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能 经典 逻辑推理 ppt 课件
限制150内