资源描述
人工智能（Artificial Intelligence）基本原理(3)22-May-241整体概述THEFIRSTPARTOFTHEOVERALLOVERVIEW,P L E A S E S U M M A R I Z E T H E C O N T E N T第一部分2第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足3基本概念推理方式及分类推理：已知/初始证据未知判断/结论 （推理机）推理方式及分类：演绎：一般个别，三段论，目前AI中用的最多归纳：个别一般默认：先认定条件成立，而后再修改完 全：枚举，遍历所有对象不完全：抽样，猜想基于方法论确定性推理不确定性推理使用的知识及结论的精确性结论是否单调单调：随着知识的加入，推理进行，结论单调增加非单调：新知识加入可使原有结论被推翻，默认推理使用的知识类型启发式：推理中使用问题相关的知识非启发式4基本概念推理方向（1）推理方向:正 向 推 理 示 意 图匹配方法搜索策略冲突消解全面性发散性5基本概念推理方向（2）逆 向 推 理 示 意 图匹配方法搜索策略冲突消解目标相关便于解释目标选择 盲目，可 能降低效 率6基本概念推理方向（3）先正后逆向混合推理示意图 先逆后正向混合推理示意图7基本概念推理方向（4）混合推理用途：已知事实不充分 无法匹配 近似匹配可能结论 寻找依据正向推理得出的结论可信度不高，逆推加强可信度逆推得到的信息作为正推前提，可得到更多结论双向推理：正向与逆向推理同时进行，在推理过程的某一步骤上“相合”，常用于定理的机器证明逆推8基本概念模式匹配（1）模式匹配 对两个知识模式（两个谓词公式，框架片断，语义网片断）进行比较，是推理的前期工作9基本概念模式匹配（2）定义1：代换是形如t1/x1，t2/x2，tn/xn的有限集合，其中 t1，t2，tn是项（变元，常量或函数），x1，x2，xn是互不相同的变元 注：xi不能循环地出现在另一 tj 中;以消去某一变元为目的 例1：a/x，f(b)/y，w/z g(y)/x，f(x)/y g(a)/x，f(x)/y g(a)/x，f(g(a)/y10基本概念模式匹配（3）=t1/x1，t2/x2，tn/xn，1/y1，2/y2，m/ym定义2：代换 则复合代换 从 t1/x1，t2/x2，tn/xn，1/y1，2/y2，m/ym 中删去ti/xi，当ti=xi i/yi，当yi x1，x2，xn注：ti表示ti中含有的变元用中代换该变元的项代替。代换 或本身内部需要复合的应先复合。11基本概念模式匹配（4）?例2：=f(y)/x，z/y，a/x，b/y，y/z，求 t1/x1 f(y)/xf(b)/x，t2/x2z/y=y/y（删去）1/y1a/x，y1 x1x（删去）2/y2b/y，y2x2y（删去）3/y3y/z，y3z =f(b)/x，y/z =f(z)/x，z/y，a/x，b/y，b/z t1/x1 f(z)/xf(b)/x，t2/x2z/y=b/y 1/y1a/x，y1 x1x（删去）2/y2b/y，y2x2y（删去）3/y3b/z，y3z =f(b)/x，b/y，b/z12定义3：设有公式集F=F1，F2，Fn，若存在一个代换 使得：F1 F2 Fn，则称为F的一个合一，F是可合一的。注：合一是不唯一的 合一表示公式集经一代换变为一样的13基本概念模式匹配（5）例3：F=P(x，y，f(y)，P(a，g(x)，z)=a/x，g(a)/y，f(g(a)/z，可合一为 P(a,g(a),f(g(a)定义4：设是公式集F的一个合一，若对任意的合一 都存在 代换使 ，则称是最一般的合一。注：任一合一都可由最一般合一与另一代换复合而得。不考虑 变量的重新命名最一般合一是唯一的。定义5：公式F1(x1，x2，xn)与 F2(y1，y2，yn)的差异集 是指 集合Dk=xi，yi，xiyi，k=1,2,m 例4：F1P(x，y，z)，F2P(x，f(a)，h(b)D1=y，f(a)，D2=z，h(b)14基本概念模式匹配（6）最一般合一的求解步骤：1）令k 0，Fk F，k（空代换）2）Fk只含一个表达式，stop得k3）找出差异集Dk 4)若 tk,xk Dk 且xk在 tk中不出现，则：k1 k tk/xk Fk1 Fktk/xk 转2）k k+15）stop，不存在15基本概念模式匹配（7）例5：F=P(a，x，f(g(y)，P(z，f(z)，f(u)F0=F，D0=a，z，k 1a/z，F1=P(a，x，f(g(y)，P(a，f(a)，f(u)D1=x，f(a)，2 1 f(a)/x=a/z，f(a)/x F2=P(a，f(a)，f(g(y)，P(a，f(a)，f(u)D2=g(y)，u，3 2 g(y)/u=a/z，f(a)/x，g(y)/u F3=P(a，f(a)，f(g(y)，P(a，f(a)，f(g(y)stop，a/z，f(a)/x，g(y)/u例6：P(x,f(y),B),P(z,f(B),B)1 A/x,B/y,A/z，2 z/x,B/y P(A,f(B),B)P(z,f(B),B)16基本概念冲突消解策略简述冲突的产生(以产生式规则为例）：已知事实与多个产生式规则的前件匹配（正向）假设内容与多个产生式规则的后件匹配（逆向）冲突消解：按针对性：包含条件较多认为与目标更接近，优先考虑按已知事实的新鲜度：后生成的事实更新鲜 新鲜知识数量比较 新鲜度 最新鲜知识的比较 最不新鲜知识的比较按匹配度：取决于匹配度的定义按事实的真实性：给每条知识赋予权函数表示获取时的真实程度按上下文的限制：分组按领域知识的特点：17第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足18自然演绎推理主要等价式（1）主要等价式交换律：PQ Q P，PQ Q P结合律：(PQ)R P(QR)(PQ)R P(QR)分配律：P(QR)(PQ)(PR)P(QR)(PQ)(PR)德.摩根律：(PQ)P Q (PQ)P Q 双重否定律：P P等价式永真蕴涵式推理规则已知为真的事实 推理规则 结论，规则19吸收律：P(PQ)P，P(PQ)P补余律：P P T，P P F联接词化归律：PQ P Q P Q （PQ）（QP）P Q (PQ)（P Q）量词转换律：(x)P (x)(P)(x)P (x)(P)量词分配律：(x)(PQ)(x)P(x)Q (x)(PQ)(x)P(x)Q自然演绎推理主要等价式（2）20自然演绎推理永真蕴涵式永真蕴涵式化简式：PQ P，PQ Q附加式：P P Q，Q P Q 析取三段论：P，P Q Q假言推理：P，PQ Q拒取式：Q，PQ P 假言三段论：PQ，Q R PR二难推论：P Q，PR，Q R R全称固化：(x)P(x)P(y)存在固化：(x)P(x)P(y)21自然演绎推理推理规则推理规则P规则：在推理的任何步骤都可引入前提T规则：若前面的公式永真蕴涵公式S，则S可引入推理过程CP规则：若能从R和前提集合中推出S，则可从前提集合推 出RS反证法：P Q 当且仅当 P Q F反证法定理：Q为P1，P2，Pn的逻辑结论，当且仅当 (P1 P2 Pn)Q 是不可满足的。PQ与 P Q 区别：PQ条件蕴含，其真值表可以为“F”；P Q永真蕴涵，其真值表无论P，Q取何值均为“T”PQ为真与Q是否为真不同22自然演绎推理例1：凡是容易的课程小王都喜欢 (x)(Easy(x)Like(Wang,x)C班的课程都是容易的 (x)(C(x)Easy(x)ds是C班的一门课程 C(ds)求证：小王喜欢ds课程 Like(Wang,ds)证：(x)(C(x)Easy(x)C(ds)Easy(ds)(永真蕴涵式之全称固化）C(ds)，C(ds)Easy(ds)Easy(ds)(永真蕴涵式之假言推理)(x)(Easy(x)Like(Wang,x)Easy(ds)Like(Wang,ds)Easy(ds),Easy(ds)Like(Wang,ds)Like(Wang,ds)23第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足24归结演绎推理子句及其化约（1）定理证明的形式：P Q 永真 P Q 不可满足定义1：原子谓词公式及其否定称为文字。P(x),P(f(x),Q 定义2：任何文字的析取式称为子句，子句合取构成的集合称 为子句集。P(x)Q(x),P(x,f(x)Q(x,g(x)定义3：不含任何文字的子句称为空子句，空子句是不可满足 的（不被解释）。命题：任一谓词公式都可化成子句集子句集：S称为子句集如果:S=(W1 W2 Wn)=W1,W2,Wn Wi=Li1 Li2 Lim,(i=1,2,n)Lij=Pij|Pij,(i=1,2,n；j=1,2,m,Pij 为文字)25归结演绎推理子句及其化约（2）子句集的化约步骤例1：(z)(x)(y)(P(x)Q(x)R(y)U(z)1）消蕴涵符（及）(z)(x)(y)(P(x)Q(x)R(y)U(z)2）移动至紧邻的谓词前(z)(x)(y)(P(x)Q(x)R(y)U(z)3）变量标准化即：不同的量词约束，对应于不同的变量(x)A(x)(x)B(x)=(x)A(x)(y)B(y)4）量词左移(x)A(x)(y)B(y)=(x)(y)A(x)B(y)26归结演绎推理子句及其化约（3）5）消存在量词 (skolem化）原则：对于一个受 约束的变量，如果他不受 约束，则该变量用一个常量代替，如果他受 约束，则该变量用一个函数代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)=(x)(P(x)Q(x)R(f(x)U(a)6）化为合取范式(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(x)U(a)Q(x)R(f(x)U(a)27归结演绎推理子句及其化约（4）7）隐去全程量词 P(x)R(f(x)U(a)Q(x)R(f(x)U(a)8）表示为子句集 P(x)R(f(x)U(a),Q(x)R(f(x)U(a)9）变量标准化（变量换名）P(x)R(f(x)U(a),Q(y)R(f(y)U(a)定理：若S是合式公式F的子句集，则F永假的充要条件是S 不可满足。S不可满足：若nil S，则S不可满足。28第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足29归结演绎推理海伯伦（HerbrandHerbrand）理论（1）子句集S的不可满足 S对任一个体域的所有解释都不满足例1：公式B(x)(P(x)Q(f(x),b)，个体域 D=1,2解释1：令 b=1,f(1)=2,f(2)=1,P(1)=F,P(2)=T,Q(1,1)=T,Q(2,1)=F得：x=1,2时，B=T,故在此解释下公式的真值为T解释2，3定义1：D为谓词公式P的个体域，若对P中个体常量、函数和 谓词按如下规定赋值 （1）为每个个体常量指派D中的一个元素 （2）为每个n元函数指派一个从Dn D的映射 Dn (x1，x2，xn)|xiD （3）为每个n元谓词指派一个从Dn F,T的映射 则称这些指派为公式P在D上的一个解释。30归结演绎推理海伯伦理论（2）问题：子句集的不可满足性是否可以在有限步内证实？海伯伦思路：构造一个特殊的域H，使得S的不可满足性只 要在该域上进行解释而不必对个体域上所有解 释进行。定义2：S为子句集，海伯伦域H定义为 （1）令H0定义为S中所有个体常量的集合，若S中无个体 常量，取H0=a,a为任意指定的一个个体常量 （2）令Hi+1 HiS中所有n元函数f(x1，x2，xn)|xj 是Hi中的元素，i=0,1,231归结演绎推理海伯伦理论（3）例2：S=P(x)Q(x),R(f(y)H0=a，H1=a,f(a)，H2=a,f(a),f(f(a),H a,f(a),f(f(a)，f(f(f(a),例3：S=P(a),Q(b),R(f(x)H0=a,b，H1=a,b,f(a),f(b)，H2=a,b,f(a),f(b),f(f(a),f(f(b),例4：S=P(a),Q(f(x),R(g(y)H0=a，H1=a,f(a),g(a)，H2=a,f(a),g(a),f(f(a),f(g(a),g(f(a),g(g(a),例5：S=P(x),Q(y)R(y)H0=H1=H2=H a32归结演绎推理海伯伦理论（4）定理1：子句集S不可满足 S对H域上的一切解释均为假定理2：子句集S不可满足 存在有限的不可满足的基子句集S定理的意义HerbrandHerbrand定理已将证明问题转化成了命题逻辑问题。由此定理保证，可以放心的用机器来实现自动推理了。（归结原理）注意HerbrandHerbrand定理给出了一阶逻辑的半可判定算法，即仅当被证明定理是成立时，使用该算法可以在有限步得证。而当被证定理并不成立时，使用该算法得不出任何结论。33第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足34归结演绎推理鲁滨逊（RobinsonRobinson）归结原理（1）归结原理是一种定理证明方法，1965年由Robinson提出，从理论上解决了定理证明问题。子句集S=C1，C2，Cn,S的不可满足 至少有一个Ci=F 若存在Ci Cj=Nil(如：P P=Nil)S为不可满足的命题的归结 通过归结使得Ci Cj简化，寻找是否有空子句存在定义1：P是原子谓词公式，则P 与 P 为互补文字定义2：C1，C2是S中任意两个子句，C1中的文字L1与 C2中的 文字L2互补，则C1 C2可以归结为 （C1 L1)（C2L2)=C12 C12为C1，C2的归结式，C1，C2为C12 的亲本子句记为35归结演绎推理鲁滨逊归结原理（2）例1：C1=P Q R,C2=Q S,C12=P R S C1=P,C2=P,C12=Nil C1=P Q,C2=Q R,C3=P,C12=P R,C123=R定理1：C12为C1，C2的逻辑结论，i.e.C1 C2 C12证：设 C1=L C1,C2=L C2,则 C12=C1 C2 C1=C1 L C1 L;C2=L C2 L C2 得：C1 C2=(C1 L)(L C2)C1 C2 C1 C2=C12 C1 C2 C12假言三段论36归结演绎推理鲁滨逊归结原理（3）推论1：在S中用C12代替C1和 C2后得到的新子句集S1，则 S1不可满足 S为不可满足的推论2：若把C12加入S中得到新子句集S2，则S2不可满足 S为不可满足的命题1:对不可满足的子句集S，归结原理是完备的 归结原理正确性的根本在于，找到矛盾可以肯定不真。37归结演绎推理鲁滨逊归结原理（4）谓词逻辑中的归结原理例2：C1=P(x)Q(x)，C2=P(a)R(y)，C12=？作代换：a/x,C1 =P(a)Q(a)，C2 =P(a)R(y)C12=Q(a)R(y)定义3：C1，C2是两个无相同变元 的子句，L1与 L2分别是 C1，C2的文字，若是L1与 L2的最一般合一，则 C12=（C1 L1)（C2 L2)称为C1，C2 的二元归结式，C1，C2为C12的亲本子句 38归结演绎推理鲁滨逊归结原理（5）例3：C1=P(a)Q(x)R(x)，C2=P(y)Q(b)P(a),P(y),a/y Q(x),Q(b),b/x C12=Q(x)R(x)Q(b)C12=P(a)R(b)P(y)归结方式不唯一例4：C1=P(x)Q(a)，C2=P(b)R(x)换变元 C2=P(b)R(y)变元相同要变换 P(x),P(b),b/x;C12=Q(a)R(y)例5：C1=P(x)P(f(a)Q(x)，C2=P(y)R(b)C1:P(x),P(f(a),f(a)/x,C1 P(f(a)Q(f(a)P(f(a),P(y),f(a)/y,C12=Q(f(a)R(b)？子句内部可合一的，先合一再与其它归结？39例6：C1=P(x)P(a)Q(x)，C2=P(y)/C2=P(f(b)C12=P(a)Q(x)C122=Q(x)C1=P(a)Q(a)（先合一）C12=Q(a)（少了普遍性）C12=P(a)Q(f(b)C1=P(a)Q(a)（先合一）无法归结40第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足41归结演绎推理归结反演（1）将归结原理用于自动定理证明问题问题：证明 F=P1，P2，Pn Q，只要证 P1 P2 ,Pn Q 是不可满足的步骤：1）写出Q 2）将F,Q 化成子句集S3）对S进行归结，归结式并入S4）出现Nil停止，得证42归结演绎推理归结反演（2）例1：F:(x)(y)(A(x,y)B(y)(y)(C(y)D(x,y)G:(x)C(x)(x)(y)(A(x,y)B(y)1)F化成子句集(x)(y)(A(x,y)B(y)(y)(C(y)D(x,y)(x)(y)(A(x,y)B(y)(C(f(x)D(x,f(x)A(x,y)B(y)C(f(x)A(x,y)B(y)D(x,f(x)2)G化成子句集(x)C(x)(x)(y)(A(x,y)B(y)(x)C(x)(x)(y)(A(x,y)B(y)(x)C(x)(x)(y)(A(x,y)B(y)43归结演绎推理归结反演（3）(x)C(x)(x)(y)(A(x,y)B(y)(x)C(x)A(a,b)B(b)C(x)A(a,b)B(b)A(x,y)B(y)C(f(x)A(x,y)B(y)D(x,f(x)C(z)A(a,b)G B(b)3)归结+:f(x)/z A(x,y)B(y)+:a/x,b/y B(b)+=NilF44归结演绎推理归结反演（4）例2:自然数都是大于零的整数 (x)(N(x)GZ(x)I(x)所有整数不是偶数就是奇数 (x)(I(x)E(x)O(x)偶数除以2是整数 (x)(E(x)I(s(x)证:所有自然数不是奇数就是 (x)(N(x)(O(x)I(s(x)其一半为整数的数 N(x)GZ(x)N(u)I(u)I(y)E(y)O(y)E(z)I(s(z)N(t)O(t)I(s(t)+:y/t I(y)E(y)+:z/t E(z)+:y/z I(y)+:u/y N(u)+:u/t Nil45归结演绎推理归结反演（5）例3：A，B，C三人中至少录取一人，若录A不录B，则一定录 C，录B则一定录C证：公司一定录CP(A)P(B)P(C)P(A)P(B)P(C)P(A)P(B)P(C)P(A)P(B)P(C)P(B)P(C)P(B)P(C)P(C)P(C)+:P(B)P(C)+:P(C)+:Nil46例4：设公理集：(x)(R(x)L(x)R(x)L(x)(1)(x)(D(x)L(x)D(x)L(x)(2)(x)(D(x)I(x)D(A)(3)I(A)(4)求证：(x)(I(x)R(x)目标求反：(x)(I(x)R(x)I(x)R(x)(5)归结演绎推理归结反演（6）47例4的归结树 换名后子句集为：R(x1)L(x1)D(x2)L(x2)D(A)I(A)I(x5)R(x5)I(A)I(x5)R(x5)R(A)A/x5 R(x1)L(x1)L(A)A/x1 D(x2)L(x2)D(A)A/x2 D(A)nil归结演绎推理归结反演（8）48归结演绎推理归结反演（9）例5：美国人(American)卖(Sells)武器(Weapon)给敌对(Hostile)国家是犯法的(Crime)。美国的敌国(Enemy)Nono有一些导弹(Missile)，所有这些导弹都是韦斯特(West)上校卖给他们的，而韦斯特上校是一个美国人。证明：韦斯特上校是一个罪犯。1)(x)(American(x)Weapon(y)Sells(x,y,z)Hostile(z)Criminal(x)2)(x)(Missile(x)Owns(Nono,x)3)Enemy(Nono,American)4)(x)(Missile(x)Weapon(x)5)(x)(Missile(x)Owns(Nono,x)Sells(West,x,Nono)6)American(West)7)(x)(Enemy(x,American)Hostile(x)8)Criminal(West)49归结演绎推理归结反演（10）1)American(x)Weapon(y)Sells(x,y,z)Hostile(z)Criminal(x)2)Missile(a)3)Owns(Nono,a)4)Enemy(Nono,American)5)Missile(x)Weapon(x)6)Missile(x)Owns(Nono,x)Sells(West,x,Nono)7)American(West)8)Enemy(x,American)Hostile(x)9)Criminal(West)502）5）10）a/x：Weapon(a)2）6）11）a/x：Owns(Nono,a)Sells(West,a,Nono)4）8）12）Nono/x：Hostile(Nono)3）11）13）a/x：Sells(West,a,Nono)7）1）14）West/x,：Weapon(y)Sells(West,y,z)Hostile(z)Criminal(West)10）14）15）y/x：Sells(West,y,z)Hostile(z)Criminal(West)13）15）16）y/x，Nono/z：Hostile(Nono)Criminal(West)12）16）17）：Criminal(West)9）17）Nil51第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足52归结演绎推理用归结原理求问题的答案（1）步骤：1）前提用谓词公式表示并化为子句集S2）构造：Q()Answer()，其中变元相同，Q为问题集3）对S Q()Answer()进行归结4）归结中取代Anwser()中变元的项就是问题的答案53归结演绎推理用归结原理求问题的答案（3）例2：王是李的老师 T(Wang,Li)李与张是同学C(Li,Zhang)若x与y是同学，则x的老师也是y的老师(x)(y)(C(x,y)T(z,x)T(z,y)张的老师是谁？(x)T(x,Zhang),Answer(x)1)T(Wang,Li)子句集2)C(Li,Zhang)3)C(x,y)T(z,x)T(z,y)4)T(u,Zhang)Answer(u)54归结演绎推理用归结原理求问题的答案（4）例2的归结树1)T(Wang,Li)3)C(x,y)T(z,x)T(z,y)5)C(Li,y)T(Wang,y)4)T(u,Zhang)Answer(u)6)C(Li,Zhang)Answer(Wang)2)C(Li,Zhang)Answer(Wang)Wang/z,Li/xWang/u,Zhang/y55归结演绎推理用归结原理求问题的答案（5）例3：A，B，C三人有人从不说假话，有人从不说真话，某人问:谁是说谎者？A答：B和C都是说谎者；B答：A和C都是说谎者；C答:B和C中至少有一个是说谎者；问：谁是诚实者，谁是说谎者？T(A)T(B)T(C)T(A)T(B)T(C)T(B)T(A)T(C)T(B)T(A)T(C)T(C)T(A)T(C)T(C)T(A)T(B)注：一般情况下，AB并不意味着 A B，此题由内容决定1）T(A)T(B)5）T(A)T(B)T(C)2）T(A)T(C)6）T(A)T(C)3）T(A)T(B)T(C)7）T(B)T(C)子句集4）T(B)T(C)56归结演绎推理用归结原理求问题的答案（6）T(x)Answer(x)T(A)T(B)T(B)T(C)T(A)T(C)T(A)T(C)T(C)Answer(C)查找诚实者：(x)T(x)查找说谎者：(x)T(x)T(A)T(B)T(B)T(C)T(A)T(C)T(A)T(C)T(A)T(x)Answer(x)Answer(A)T(A)T(B)T(A)T(C)T(B)T(C)T(B)T(C)T(B)T(x)Answer(x)Answer(B)C是诚实者A，B是说谎者查找说谎者：(x)T(x)57第三章 经典逻辑推理 基本概念 自然演绎推理 归结演绎推理推理方式及分类推理方向模式匹配冲突消解策略简述子句及其化约海伯伦理论鲁滨逊归结原理归结反演用归结原理求解问题归结策略归结推理的不足58归结演绎推理归结策略（1）归结的一般过程（广度优先）例1：S=C1,C2,C3,C41）C2 C3 C1 C3 C2 C3 C4 得S1 C4 C42)S与S1进行归结得S2 3)S,S1与S2进行归结得S3 注：可能产生无用子句，重复子句，效率不高例2：S=P,R,PQ,Q R1)S1=Q,Q,PR；2)S2=R,P；3)Nil59归结演绎推理归结策略（2）归结策略1）删除策略（完备）纯文字删除：文字L在S中不存在 L，删去含L的子句 S=PQ R,Q R,Q,R；删去PQ R重言删除：某一子句含L L，删去包蕴删除：若存在代换，使得C1 C2，则删去C1 P(x)=a/x P(a)Q(z),删去P(x)60归结演绎推理归结策略（3）2)支持集策略（完备）亲本子句中至少有一个是由目标的否定所得到的子句或 是其后裔例3：S=I(x)R(y),I(a),R(y)L(y),L(a)目标的否定I(x)R(y)I(a)R(y)L(y)L(a)R(a)I(x)L(x)I(a)L(a)I(a)NilS:S1:S2:613)线性输入策略（不完备）亲本子句中至少有一个S例4：S=P Q,PQ,P Q,P Q P Q PQP Q PQQPP QNil线性：S1=Q,P,P,Q=S2=死循环S:S1:S2:62提问与解答环节Questionsandanswers63添加标题添加标题添加标题添加标题此处结束语点击此处添加段落文本.您的内容打在这里，或通过复制您的文本后在此框中选择粘贴并选择只保留文字64谢谢聆听THANKYOUFORLISTENING演讲者：XX时间：202X.XX.XX65
展开阅读全文