人工智能5第五章确定性推理

《人工智能5第五章确定性推理》由会员分享，可在线阅读，更多相关《人工智能5第五章确定性推理（75页珍藏版）》请在装配图网上搜索。

1、第四章第四章 确定性推理确定性推理7/28/202214.1 确定性确定性推理推理概述概述第四章 确定性推理 4.1概述7/28/20222推推 理理l推理是指按照某种策略从巳知事实出发去推出结论的过程l 智能系统的推理过程实际上就是一种思维过程。l智能系统的推理过程是通过推理机来完成的。l推理机就是智能系统中用来实现推理的程序。l按照推理过程所用知识的确定性，推理可分为确定性推理和不确定性推理。第四章 确定性推理 4.1概述7/28/20223事事 实实l事实是推理过程中按知识表示方式表示的已知的知识l推理所用的事实可分为两种情况:与求解问题有关的初始证据推理过程中所得到的中间结论。第四章

2、确定性推理 4.1概述 7/28/20224推理的基本问题推理的基本问题l智能系统的推理包括两个基本问题：一个是推理的方法一个是推理的控制策略l 推理方法主要解决：在推理过程中前提与结论之间的逻辑关系在非精确性推理中不确定性的传递问题第四章 确定性推理 4.1概述 7/28/20225推理方法的分类推理方法的分类l推理可以有多种不同的分类方法l按照推理的逻辑基础分类：演绎推理归纳推理默认推理l按照所用知识的确定性分类：确定性推理不确定性推理l按照推理过程的单调性分类（推理过程所得到的结论是否越来越接近目标）：单调推理非单调推理第四章 确定性推理 4.1概述 7/28/20226演绎推理演绎推理

3、l 从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。l它是一种由一般到个别的推理方法。l核心是三段论第四章 确定性推理 4.1概述 7/28/20227归纳推理l 从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。l它是一种由个别到一般的推理方法。l基本思想：先从已知事实中猜测出一个结论，然后对这个结论的正确性加以证明确认l数学归纳法就是归纳推理的一种典型例子。l按照所选事例的广泛性，归纳推理可分为：完全归纳推理和不完全归纳推理；l按照推理所使用的方法可分为：枚举归纳推理、类比归纳推理、统计归纳推理和差异归纳推理等。第四章 确定性推理 4.1概述 7/28

4、/20228默认推理l 在知识不完全的倩况下，假设某些条件已经具备所进行的推理，因此也称为缺省推理。l在推理过程中如果发现原先的假设不正确，就撤销原来的假设以及由此假设所推出的所有结论。l重新按新情况进行推理。l解决了在一个不完备的知识集中进行推理的问题。第四章 确定性推理 4.1概述 7/28/20229推理过程的单调性l按照推理过程所得到的结论是否越来越接近日标，推理可分为单调推理与非单调推理。l单调推理：在推理过程中，每当使用新的知识后，所得到的结论会越来越接近于目标不会出现反复情况，即不会由于新知识的加入否定了前面推出的结论。l非单调推理：在推理过程中，当某些新知识加入后，会否定原来推

5、出的结论。l非单调推理往往是在知识不完全的情况下发生的。第四章 确定性推理 4.1概述 7/28/202210推理控制策略推理控制策略l推理的控制策略是在推理过程中采用的、解决如何使用领域知识使推理过程尽快达到目标的策略。第四章 确定性推理 4.1概述 7/28/202211推理控制策略推理控制策略分类分类l智能系统的推理过程一般表现为一种搜索过程，因此，推理的控制策略又可分为推理策略和搜索策略。l推理策略主要解决推理方向、冲突消解等问题。l搜索策略主要解决推理线路、推理效果、推理效率等问题。第四章 确定性推理 4.1概述 7/28/202212推理方向推理方向l推理方向确定推理过程是从初始证

6、据开始到目标，还是从目标开始到初始证据。按照对推理方向的控制，推理可分为正向推理、逆向推理、混合推理及双向推理四种情况。第四章 确定性推理 4.1概述 7/28/202213正向正向推理推理l正向推理是一种从已知事实出发、正向使用推理规则的推理方式，亦称为数据驱动推理。l基本思想是：用户需要事先提供一组初始证据，并将其放入综合数据库。推理机根据综合数据库中的已有事实，到知识库中寻找当前可用知识，形成一个当前可用知识集。按照冲突消解策略，从该知识集中选择一条知识进行推理，并将新推出的事实加入综合数据库，作为后面继续推理时可用的巳知事实，重复这一过程，直到求出所需要的解或者知识库中再无可用知识为止

7、第四章 确定性推理 4.1概述 7/28/202214逆向逆向推理推理l逆向推理是一种从以某个假设目标作为出发点的推理方法，亦称为目标驱动推理l基本思想是：将要求证的目标(称为假设)构成一个假设集。取一个假设对其进行验证，若在综合数据库里，则假设成立若能被用户认定为事实，则假设成立，并放入综合数据库若可由知识库中的一个或多个知识导出，则这些知识构成可用知识集。按照冲突消解策略，从该知识集中选择一条知识，将其前提中的所有子条件作为新的假设加入假设集。重复这一过程，直到假设集为空或假设集非空但可用知识集空为止第四章 确定性推理 4.1概述 7/28/202215混合推理混合推理l 正向推理和逆向推

8、理都有各自的优缺点。当问题较复杂时，单独使用其中哪一种，都会影响到推理效率。l为了取长补短可将它们结合起来使用。l这种把正向推理和逆向推理结合起来所进行的推理称为混合推理。第四章 确定性推理 4.1概述 7/28/202216混合推理的实现方法混合推理的实现方法l混合推理可有多种具体的实现方法混合推理可有多种具体的实现方法先正向推理，后逆向推理的方法先逆向推理，后正向推理的方法采用随机选择正向和逆向推理的方法（双向混合推理）第四章 确定性推理 4.1概述 7/28/202217混合推理的适用场合混合推理的适用场合l已知事实不够充分。l由正向推理推出的结论可信度不高l希望得出更多的结论l希望从正

9、反两个方向同时进行推理第四章 确定性推理 4.1概述 7/28/202218冲突消解策略冲突消解策略l冲突消解策略是指当推理过程有多条知识可用时，如何从这多条可用知识中选出一条最佳知识用于推理的策略。l冲突消解的基本思想是对可用知识进行排序。l常用的冲突消解策略有：特殊知识优先新鲜知识优先差异性大的知识优先领域特点知识优先上下文关系知识优先前提条件少的知识优先第四章 确定性推理 4.1概述 7/28/202219自然演绎推理自然演绎推理l 从一组己知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。l在自然演绎推理中，需要避免两类错误：肯定后件的错误和否定前件的错误。

10、l优点：定理证明过程自然，易于理解，有丰富的推理规则l主要缺点：容易产生知识爆炸，推理过程中得到的中间结论一般按指数规律递增，对于复杂问题的推理不利，甚至难以实现。l因此，提出了归结演绎推理因此，提出了归结演绎推理第四章 确定性推理 4.2自然演绎推理 7/28/202220归结演绎推理归结演绎推理l 归结演绎推理是一种基于归结原理的推理方法。l归结原理亦称消解原理，是鲁宾逊1965年提出的l归结演绎推理实际上是一种“反正法”，基本思想：推理就是要对前提P和结论Q，证明P Q永真。这就要证明P Q在任何一个非空的个体域上都是永真的。这将是非常困难的，甚至是不可实现的。而用反证法，只要能够证明(

11、P Q)是不可满足的。第四章 确定性推理 4.3归结演绎推理 7/28/202221子句和子句集子句和子句集l原子谓词公式及其否定都称为文字l文字的析取构成的公式称为子句l不包含任何文字的子句称为空了句l空子句不包含任何文字，因此，不能被任何指派所满足l所以空子句是不可满足的l子句集中的子句之间是合取关系l含空子句的子句集也就一定是不可满足的。第四章 确定性推理 4.3归结演绎推理 7/28/202222谓词公式转化为子句集谓词公式转化为子句集l消去蕴涵符号：PQ取代PQl减少否定符号的管辖域l对变量标准化l消去存在量词l化为前束形l化为合取范式：如：P(PQ）(PQ）l消去全称量词l获得子句

12、集l更换变量名 第四章 确定性推理 4.3归结演绎推理 7/28/202223化子句集例化子句集例例：(z)(x)(y)(P(x)Q(x)R(y)U(z)1,消蕴涵符理论根据：a b=a b(z)(x)(y)(P(x)Q(x)R(y)U(z)2,移动否定符理论根据：(a b)=a b (a b)=a b(x)P(x)=(x)P(x)(x)P(x)=(x)P(x)(z)(x)(y)(P(x)Q(x)R(y)U(z)第四章 确定性推理 4.3归结演绎推理 7/28/202224化子句集例化子句集例（续1）3,变量标准化即：对于不同的约束，对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)

13、(y)B(y)4,量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)5,消存在量词(skolem化）原则：对于一个受存在量词约束的变量，如果他不受全程量词约束，则该变量用一个常量代替，如果他受全程量词约束，则该变量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)第四章 确定性推理 4.3归结演绎推理 7/28/202225化子句集例（续化子句集例（续2）6,化为合取范式即(ab)(cd)(ef)的形式 (x)(P(x)Q(x)R(f(x)U(a)=(x)(P(x)Q(x)R(f(x)U(a)=(x)P(x)R(f

14、(x)U(a)Q(x)R(f(x)U(a)7,隐去全程量词 P(x)R(f(x)U(a)Q(x)R(f(x)U(a)第四章 确定性推理 4.3归结演绎推理 7/28/202226化子句集例化子句集例（续3）8,表示为子句集 P(x)R(f(x)U(a),Q(x)R(f(x)U(a)9,变量标准化（变量换名）P(x1)R(f(x1)U(a),Q(x2)R(f(x2)U(a)第四章 确定性推理 4.3归结演绎推理 7/28/202227归结归结(消解消解)原理原理基本思想基本思想l首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集S。l检验子句集S是否含有空子句l若不含空子句，则继续使

15、用归结法，在子句集中选择合适的子句进行归结l直至导出空子句或不能继续归结为止。第四章 确定性推理 4.3归结演绎推理 7/28/202228归结归结原理分类原理分类l 鲁宾逊归结原理可分为:命题逻辑归结原理谓词逻辑归结原理第四章 确定性推理 4.3归结演绎推理 7/28/202229归结式归结式l归结推理的核心是求两个子句的归结式l若P是原子谓词公式，则称P与P为互补文字l设C1和C2是子句集中的任意两个子句l如果C1中的文字L1与C2中的文字L2互补l那么可从C1和C2中分别消去L1和L2l并将C1和C2中余下的部分按析取关系构成一个新的子句C12，l则称这一过程为归结，l称C12为C1和C

16、2的归结式，C1和C2为C12的亲本子句。第四章 确定性推理 4.3归结演绎推理 7/28/202230消解过程举例消解过程举例l E2 E1 （前提）l E2 E3 （前提）l （消解式）E1 E3 （结论）第四章 确定性推理 4.2归结演绎推理 7/28/202231命题逻辑的消解推理举例命题逻辑的消解推理举例假言推理：P PQ (PQ）消解式：Q合并：PQ PQ 消解式：QQ=Q 重言式：P Q PQ 消解式：PP 或 QQ 空子句：P P 消解式：NIL 三段论：PQ (PQ）QR (QR）消解式：PR (PQ）第四章 确定性推理 4.2归结演绎推理 7/28/202232谓词逻辑的消

17、解推理举例谓词逻辑的消解推理举例B(x)B(x)C(x）消解式：C(x)P(x)Q(x）Qf(y)消解式：Pf(y)置换：f(y)/xPx,f(y)Q(x)Rf(a),y Pf(f(a),zR(z,w）消解式：Qf(f(a)Rf(a),yRf(y),w 置换：f(f(a)/x,f(y)/z第四章 确定性推理 4.2归结演绎推理 7/28/202233消解反演消解反演l消解反演是利用消解原理进行推理的过程。l消解反演的推理过程:给定公式集S和目标公式L证明公式L的步骤如下：l否定L，得L l把L 添加到S中去l把新产生的集合L,S化成子句集l应用消解原理力图推导出一个表示矛盾的空子句 第四章 确

18、定性推理 4.2归结演绎推理 7/28/202234命题逻辑消解反演的例子命题逻辑消解反演的例子设公理集：P,(PQ)R,(ST)Q,T求证：R子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）化子句集：(PQ)R=(PQ)R=PQR(ST)Q=(ST)Q=(ST)Q=(SQ)(TQ)=SQ,TQ第四章 确定性推理 4.2归结演绎推理 7/28/202235命题逻辑消解反演的例子（续）命题逻辑消解反演的例子（续）子句集：(1)P(2)PQR(3)SQ(4)TQ(5)T(6)R（目标求反）归结：(7)PQ (2,6)(8)Q (1,7)(9)T (4,8)(10)nil

19、 (5,9)第四章 确定性推理 4.2归结演绎推理 7/28/202236谓词逻辑消解反演的例子谓词逻辑消解反演的例子l例：已知：If Fido goes wherever John goes and if John is at school,where is Fido?(x)AT(John,x)AT(Fido,x)AT(John,School)求证：(x)AT(Fido,x)子句集：AT(John,y)AT(Fido,y)AT(John,School)AT(Fido,x)(x)AT(Fido,x)=(x)AT(Fido,x)第四章 确定性推理 4.2归结演绎推理 7/28/202237AT(

20、Fido,x)AT(John,y)AT(Fido,y)子句集：AT(John,y)AT(Fido,y)AT(John,School)AT(Fido,x)AT(John,x)x/yAT(John,School)nilSchool/xAT(Fido,School)谓词逻辑消解反演的例子（续）谓词逻辑消解反演的例子（续）第四章 确定性推理 4.2归结演绎推理 7/28/202238基于消解原理的问答系统基于消解原理的问答系统l消解原理主要用来解决证明的问题，但有时我们希望得到如x=?时，W(x)为真的回答l消解原理是将结论的否定作为前提进行归结，而为了回答问题，用由结论的否定构成的重言式作为前提进行

21、归结，得到的结论是问题的回答而不是空语句。这个过程称为修改证明过程（或修改归结过程）。l下面以猴子摘香蕉问题为例来说明第四章 确定性推理 4.2归结演绎推理 7/28/202239用消解原理解猴子摘香蕉问题用消解原理解猴子摘香蕉问题l为了把状态空间的算符描述与谓词演算结合起来，将状态添到谓词上；l将算符看成是把一种状态映射成另一种状态的函数；l问题简化成没有goto()规则；c第四章 确定性推理 4.2归结演绎推理 7/28/202240猴子摘香蕉问题的表示猴子摘香蕉问题的表示问题可以描述如下：1,ONBOX(s0)2,(x)(s)(ONBOX(s)AT(box,x,push(x,s)3,(s

22、)(ONBOX(climbbox(s)4,(s)(ONBOX(s)AT(box,c,s)HB(grasp(s)5,(x)(s)(AT(box,x,s)AT(box,x,climb(s)求解：(s)HB(s)第四章 确定性推理 4.2归结演绎推理 7/28/202241猴子摘香蕉问题的子句集猴子摘香蕉问题的子句集1,ON(s0)2,ON(s1)AT(box,x1,push(x1,s1)3,ON(climb(s2)4,ON(s3)AT(box,c,s3)HB(grasp(s3)5,AT(box,x4,s4)AT(box,x4,climb(s4)6,HB(s5)第四章 确定性推理 4.2归结演绎推理

23、 7/28/202242HB(s5)ON(s3)AT(box,c,s3)HB(grasp(s3)ON(s3)AT(box,c,s3)grasp(s3)/s5ON(climb(s2)climb(s2)/s3 AT(box,c,climb(s2)ON(s0)ON(s1)AT(box,x1,push(x1,s1)s0/s1AT(box,x1,push(x1,s0)AT(box,x4,s4)AT(box,x4,climb(s4)x4/x1,push(x4,s0)/s4AT(box,x4,climb(push(x4,s0)NILc/x4,push(c,s0)/s2HB(s5)HB(grasp(s3)HB

24、(grasp(climb(s2)HB(grasp(climb(push(c,s0)猴子摘香蕉问题的（修正）消解树猴子摘香蕉问题的（修正）消解树第四章 确定性推理 4.2归结演绎推理 7/28/202243归结反演的搜索策略归结反演的搜索策略l 归结反演过程是“运用归结规则直到产生空子句为止”l在对子句集进行归结时，一个关键问题是如何选择子句进行归结。l如果对任意一对可以归结的子句都做归结，这样不仅消耗很多的时间，还会产生许多无用的归结式，占用很多空间l因此，需要研究有效的归结控制（搜索）策略。l归结搜索策略一般包括：排序策略和限制策略第四章 确定性推理 4.2归结演绎推理 7/28/20224

25、4排序策略排序策略l归结顺序与状态空间的扩展顺序类似。l状态空间的搜索问题有多种搜索策略。l把原始子句看成0层归结式。l（i+1）层的归结式是一个i层归结式和一个j(ji)层归结式进行归结所得到的归结式。l宽度优先：先生成第1层的所有归结式然后是第2层所有的归结式，依次类推，直到产生空子句或不能再进行归结为止。l深度优先：产生一个第1层的归结式，然后用第1层的归结式和第0层的归结式进行归结，得到第2层的归结式，直到产生空子句结束，或者不能归结，则回溯到其他的上层子句继续归结l 单元优先：在归结过程中优先考虑仅由一个文字构成的子句，这样的子句称为单元子句。第四章 确定性推理 4.2归结演绎推理

26、7/28/202245限制策略限制策略l限制策略不涉及被归结子句的排序只允许某些归结发生。其中几种限制归结策略：l删除策略l支持集策略。l线性输入策略。l祖先过滤策略。第四章 确定性推理 4.2归结演绎推理 7/28/202246删除策略删除策略l如果在归结时能把子句集中的无用子句删除掉，这样就会缩小寻找范围，减少比较次数。从而提高归结的效率。l删除策略有几种删除方法：(1)纯文字删除法。(2)重言式删除法。(3)包孕删除法第四章 确定性推理 4.2归结演绎推理 7/28/202247纯文字删除法纯文字删除法l如果某文字L在子句集中不存在可与之互补的文字L，则称该文字为纯文字。l在归结时纯文字

27、不可能被消去，因而用包含它的子句进行归结时不可能得到空子句。l因此，这样的子句对归结是无意义的，把它从子句集中删去，不会影响子句集的不可满足性。l例如，子句集：SPV Q VR，Q VR，Q，Rl可以看出，P是纯文字，因此可将子句PV Q VR从S中删去。第四章 确定性推理 4.2归结演绎推理 7/28/202248重言式删除法重言式删除法l如果一个子句中同时包含互补文字对，则称该子句为重言式。l例如，P(x)VQ(x)V P(x)是重言式。l重言式是真值为真的子句。l对于一个子句集，增加或删去一个重言式子句都不会影响它的不可满足性，l因而可从子句集中删去重言式。第四章 确定性推理 4.2归结

28、演绎推理 7/28/202249包孕删除法包孕删除法l设C1，C2是两个子句，若存在置换，使得C1C2，则称子句C2包孕C1l例如，P(a)VQ(y)包孕P(x)(=a/x)l P(a)VQ(y)包孕Q(y)l对于一个子句集，删去一个被别的子句包孕的子句，不会影响它的不可满足性。l因而可从子句集中删去被包孕的子句。第四章 确定性推理 4.2归结演绎推理 7/28/202250支持集策略支持集策略l支持集策略：支持集策略：每次归结时参与归结的子句中至少应有一个是由目标公式的否定所得到的子句，或者是它们的后裔l后裔的定义：设1是子句1 与另外某子句的归结式是1 的后裔1 的后裔与其他子句的归结式是

29、1 的后裔。l支持集策略是完备的。即对一个不可满足的子句集运用支持集策略进行归结，最终总会导出空子句。第四章 确定性推理 4.2归结演绎推理 7/28/202251线性输入策略线性输入策略l 线性输入策略线性输入策略：参加归结的两个子句中至少有一个是初始子句集中的子句。l线性输入策略是不完备的。对于某些不可满足的子句集，无法用线性输入归结得到结果。第四章 确定性推理 4.2归结演绎推理 7/28/202252祖先过滤策略祖先过滤策略l祖先过滤策略祖先过滤策略：参与归结的两个子句中至少有一个是初始子句集中的子句，或者一个子句是另一个子句的祖先。l祖先过滤策略是线性输入策略的改进策略，它是完备的。

30、第四章 确定性推理 4.2归结演绎推理 7/28/202253消解方法小结消解方法小结l求子句集，进行归结，方法简单l通过修改证明树的方法，提取回答l方法通用l求解效率低，不宜引入启发信息l不宜理解推理过程第四章 确定性推理 4.2归结演绎推理 7/28/202254基于规则的演绎推理（一）基于规则的演绎推理（一）l归结反演系统解决问题的效率低下l归结演绎并非人类的自然思维方式，不利于人们从自然思维的角度组织问题的求解和提供问题求解所需的知识l基于规则的演绎推理，运用推理规则，直接推导目标公式l这符合人的自然思维方式，也能通过规则(作为启发式知识)更有效地引导演绎推理过程。l基于规则的演绎推理

31、成为比归结反演更有效的技术，广泛地应用于许多问题求解中第四章 确定性推理 4.3基于规则的演绎推理 7/28/202255基于规则的演绎推理基于规则的演绎推理(二二)l它把知识分为两类：规则和事实规则表示为if then 形式事实表示为与或形l规则作为启发式知识，引导演绎推理过程。l事实是有关问题状态和环境的知识，l规则演绎的任务就是从给定的事实证明某个目标公式成立。l采用直接法而不是反演系统证明目标公式，强调用规则进行演绎，故称基于规则的演绎推理.l分为两类:正向正向演绎演绎和逆向和逆向演绎演绎第四章 确定性推理 4.3基于规则的演绎推理 7/28/202256基于规则的正向演绎推理基于规则

32、的正向演绎推理l 将非蕴涵式部分的事实表示成与或形，可用与或图表示l将蕴涵式部分的事实表示成规则l规则表示成形式：L W 其中，L是单文字，W是与或形，变量受全称量词约束l将目标公式表示成子句集l正向演绎推理的过程正向演绎推理的过程,就是将规则运用于事实与或图,对与或图进行扩展变换的过程l当与或图的叶节点包含目标公式的子句集时，推理成功第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202257化化目标公式目标公式为子句集为子句集l大部分步骤与归结原理中化子句集步骤相同l消存在量词(skolem化）过程不同。对于一个受存在量词约束的变量，消去原则：如果他不受全程量词约束，则该变量

33、用一个常量代替如果他受全程量词约束，则该变量用一个函数代替，且全称量词变为存在量词。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)消存在量词 (P(x)Q(x)R(f(x)U(a)隐含目标公式的变量都受存在量词的约束第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202258事实表达式的与或图表示事实表达式的与或图表示l用K连线表示析取，无连线表示合取例：Q(w,A)(R(v)P(v)S(A,v)Q(w,A)(R(v)P(v)S(A,v)Q(w,A)(R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)第四章

34、 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202259将规则变换为限定形式将规则变换为限定形式l如果规则不是形式：L W其中，L是单文字，W是与或形，变量受全称量词约束则首先变换为这种形式l例：(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)P(x,y,z)(u)Q(x,u)=(x)(y)(z)(u)(P(x,y,z)Q(x,u)=P(x,y,f(x,y)Q(x,u)(Skolem化)=P(x,y,f(x,y)Q(x,u)(恢复蕴涵式)l例：(L1 L2)W=L1 W 和 L2 W 第四章 确定性推理

35、4.3基于规则的演绎推理正向演绎7/28/202260对与或图作变换例对与或图作变换例l例：事实：(P Q)R)(S (T U)规则：S (X Y)Z l事实的与或图与规则对其进行的变换过程如下图：第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202261(P Q)R)(S (T U)(P Q)R P Q R PQS (T U)ST UTUSX YZX YP Q SP Q T US RR T UP Q X ZP Q Y ZR X ZR Y Z规则的子句：S (X Y)Z=S(X Y)Z=S X Z S Y Z结论：加入规则后得到的解图，是事实与规则对应子句的归结式第四章 确定性

36、推理 4.3基于规则的演绎推理正向演绎7/28/202262目标公式作为终止条件目标公式作为终止条件l应用规则进行推理的目的是为了证明某个目标公式l在正向推理系统中，这种目标表达式只限于可证明的表达式，尤其是可证明的文字析取形的目标公式表达式l在与或图的产生过程中，目标文字或规则与图中文字节点匹配时，产生新后裔节点，标记为匹配的目标文字。当产生的图包含有终止在目标节点上的一个解图时，系统便成功地结束。第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202263例：事实：A B规则集：A C D B E G目标公式：C GA BAACDBBEGCG目标目标公式作为终止条件例一目标公

37、式作为终止条件例一匹配弧第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202264目标公式作为终止条件例二目标公式作为终止条件例二例：事实：P(x,y)(Q(x,A)R(B,y)规则集：P(A,B)(S(A)X(B)Q(B,A)U(A)R(B,B)V(B)目标：S(A)X(B)(U(A)V(B)事实的与或图与规则对其进行的变换过程如下图：第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202265P(x,y)(Q(x,A)R(B,y)P(x,y)Q(x,A)R(B,y)Q(x,A)R(B,y)P(A,B)A/x,B/yS(A)X(B)Q(B,A)B/xU(A)R(

38、B,B)B/yV(B)例二的与或图例二的与或图第四章 确定性推理 4.3基于规则的演绎推理正向演绎7/28/202266基于规则的基于规则的逆向演绎推理逆向演绎推理l将目标表达式表示成与或形l将规则限制为下列形式：W L 其中，L是单文字，W是与或形，变量受全称量词约束如规则形为：W L1 L2，则变换为：W L1 和 W L2l 事实表达式均限制为文字合取形，形如：l F1 F2 Fn Fi(i1,2n)为单文字且都可单独起作用l 推理过程：从目标公式的与或树出发，不断用规则的后件和与或树的叶节点进行匹配，并将匹配成功的规则用匹配弧加入与或树中，直到产生某个终止在事实节点上的解图为止。第四章

39、 确定性推理 4.3基于规则的演绎推理逆向演绎7/28/202267化目标表达式为与或形化目标表达式为与或形l消去蕴涵符号：PQ取代PQl减少否定符号的管辖域l对变量标准化l消去全称量词：引入Skolem函数l消去存在量词第四章 确定性推理 4.3基于规则的演绎推理逆向演绎7/28/202268目标表达式化为与或形举例目标表达式化为与或形举例例：(z)(x)(y)(P(x)Q(x)R(y)U(z)前三步：1,消蕴涵符 2,移动否定符 3,变量标准化 等3步与正向推理中化事实的表达式方法相同4,消全称量词(skolem化(对偶形)）原则：对于一个受全称量词约束的变量，如果他受存在量词约束，则该变

40、量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(z)(y)(P(f(z)Q(f(z)R(y)U(z)5,消存在量词 (P(f(z)Q(f(z)R(y)U(z)第四章 确定性推理 4.3基于规则的演绎推理逆向演绎7/28/202269目标表达式的与或图表示目标表达式的与或图表示l用K连线表示合取，无连线表示析取例：Q(w,A)(R(v)P(v)S(A,v)Q(w,A)(R(v)P(v)S(A,v)Q(w,A)(R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)读叶节点的与或关系，得子句：Q(w,A)R(v)S(A,v)P(v)S(A,v)第四章 确

41、定性推理 4.3基于规则的演绎推理逆向演绎7/28/202270逆向演绎逆向演绎例例：事实：D(F)B(F)W(F)M(N)规则：R1:(W(x1)D(x1)F(x1)R2:(F(x2)B(x2)A(y2,x2)R3:D(X3)A(x3)R4:C(x4)A(x4)R5:M(x5)C(x5)目标：C(x)D(y)A(x,y)C(x)D(y)A(x,y)C(x)D(y)A(x,y)C(x5)x/x5M(x)R5M(N)N/xD(F)F/yA(y2,x2)x/y2,y/x2F(y)B(y)R2B(F)F/yF(x1)y/x1W(y)D(y)R1W(F)F/yD(F)F/y第四章 确定性推理 4.3基

42、于规则的演绎推理逆向演绎7/28/202271正、逆向系统对比正、逆向系统对比l事实表达式任意形l规则形式：单文字 Wl目标公式为文字析取l对事实、规则消存在量词，Skolem化l消目标的全称量词，Skolem化(对偶形)l事实表达式与或树，“”对“与”，“”对应“或”l从事实出发，正向应用规则l以目标为结束的一致解图l事实表达式是合取形l规则形式：L 单文字l目标公式任意形l对事实、规则消存在量词，Skolem化l消目标的全称量词，Skolem化(对偶形)l目标公式的与或树，“”对“与”，“”对应“或”l从目标出发，逆向应用规则l以事实为结束的一致解图第四章 确定性推理 4.3基于规则的演绎推理 7/28/202272The End第四章 确定性推理 7/28/202273演讲完毕，谢谢观看！