《AI确定性推理3》由会员分享，可在线阅读，更多相关《AI确定性推理3（46页珍藏版）》请在金锄头文库上搜索。
1、3.4归结演绎推理一、子句集及其化简二、鲁滨逊归结原理三、用归结反演求取问题的答案四、归结反演推理的归结策略三、归结反演推理的归结策略 哪些子句对可进行归结，哪些子句对的归结 能尽快得到空子句？需要研究有效的归结策 略。常用的归结策略可分为两大类，一类是删除 策略，另一类是限制策略。三、归结反演推理的归结策略删除策略是通过删除某些无用的子句来缩小 归结范围；限制策略是通过对参加归结的子句进行某些 限制，来减少归结前盲目性，以尽快得到空 子句。为了说明选择归结策略的重要性,先介绍广度优先策略。三、归结反演推理的归结策略1、广度优先策略是一种穷尽子句比较的复杂搜索方法。例319设有如下子句集：S=
2、 I(x)VR(x), 1(a), -R(y)VL(y), -nL(a) 用广度优先策略证明S为不可满足。1、归结反演推理的归结策略宽度优先策略的归结树:S5152l(x)VR(x) 1(a)R(y)VL(y)L(a)L(a)L(a)1(a)l(a)NIL1、归结反演推理的归结策略1、归结反演推理的归结策略特点:归结出了许多无用的子句，对大问题的归结容易产生 组合爆炸，但对小问题却不失为一种比较好的归结策略， 并且是一种完备的归结策略。支持集策略要求每一次参加归结的两个亲本子句中，至少应该有一个是由目标公式的否定所得到的子句 或它们的后裔。例3.20设有如下子句集：S=-KVRCx), I(a
3、),-1R(y)VL(y), -L(a) 其中，一d(x)VR(x)为目标公式的否定。用 支持集策略证明S为不可满足。归结树:各级归结式数目要比宽度优先策略生成的少，但会增加空子句所在的深度。是完备策略。三、归结反演推理的归结策略3、删除策略主要想法是：归结过程在寻找可归结子句时，子 句集中的子句越多，需要付出的代价就会越大。如 果在归结时能把子句集中无用的子句删除掉，这就 会缩小搜索范围，减少比较次数，从而提高归结效 率。 常用的删除方法有以下几种（纯文字、重言 式、包孕）1、归结反演推理的归结策略III(1)纯文字删除法如果某文字L在子句集中不存在可与其互补的文字 L,则称该文字另纯文字。
4、在归结过程中，纯文字不可能被消除，用包含纯文 字的子句进行归结也不可能得到空子句，因此对包 含纯文字的子句进行归结是没有意义的，应该把它 从子句集中删除。对子句集而言，删除包含纯文字的子句，是不影响 其不可满足性的。例如，对子句集S=PVQVR, -iQVR, Q, R其中P是纯文字，因此可以将子句PVQVR从子 句集S中删除。(2)重言式删除法重言式是真值为真的子句。 如果一个子句中包含有互补的文字对，则称该子 句为重言式。例如P(x) VP(x), P(x) VQ(x) VP(x) 都是重言式，不管P (x)的真值为真还是为假， P(x) VP(x)和P(x) VQ(x) VP(x)都均为
5、真。对一个子句集来说，不管是增加还是删除一个真 值为真的子句，都不会影响该子句集的不可满足 性。因此，可从子句集中删去重言式。4、三碍反演推理的归烬十卄7L（y），（x）Z，31、归结反演推理的归结策略归结树：1、归结反演推理的归结策略1、归结反演推理的归结策略采用单文字子句策略，归结式包含的文字数将少于其亲本子句中的文字数，这将有利于向空子句的方向发展，因此会有较高的归结效率。但这种策略是不完备的，即当子句集为不可满足时，用这种策略不一定能归结出空子句。5、祖先过滤策略每次参加归结的两个亲本子句，只要满足以下两个条 件申的任意一个競可抠行归结：两个亲本子句中至少有一个是初始子句集中的子句。
6、如果叩个亲本子句都不是初始子句集中的子句，则一个 子奇应该是另一个孚旬的免辈字勾。所谓一个子勾(例如 S是另一个子句(例如阪)的先辈子句是指C2是由C与别的 扌句归结后得到的归结点。 例3. 23设有如下子句集：S= Q (x) V iP (x)， Q(y) V P (y), Q (w) VP(w),Q(a)VP(a) 用祖先过滤策略证明S为不可满足证明：从S出发，按祖先过滤策略归结过程如下图所示祖先过滤策略也是完备的归结反演系统(34)基于规则的演绎系统(35)演绎过程接近人们习惯的问题描述方式，容 易理解，但不一定比反演系统更有效。本节内容:、规则正向演绎推理1、规则逆向演绎推理规则正向演
7、绎是一种正向推理。规则正向演绎从已知事实出发，正向使用规则，直 接进行演绎，直至到达目标为止。事实、规则、目标是如何表示的？、规则正向演绎推理1、事实表达式的与/或形变换在一个基于规则的正向演绎系统中，其前提 条件中的事实表达式是作为系统的初始综合 数据库来描述的。对事实的变换，只须转换成不含蕴含符号“亠， 的与/或形表示即可，而不必化成子句集。变 换步骤为：、规则正向演绎推理、规则正向演绎推理(1)利用“P QO-iPVQ”,消去蕴含符号。(注:事实表达式中很少有，而规则中才有)(2)利用狄摩根定律及量词转换率把“，移至U紧靠谓词的位置，直到每个否定符号的辖域 最多只含一个谓词为止。对所得到
8、的表达式进行前束化。(4)对全称量词辖域内的变量进行改名和标准 化，对存在量词量化的变量用skolem函数代 替，使不同量词约束的变元有不同的名字。、规则正向演绎推理(5)消去全称量词，而余下的变量都被认为是全称量 词量化的变量。(6)对变量进行换名，使主合取元具有不同的变量名。例如，有如下表达式(3 x) (Vy)(Q(y, x)A -.(R(y)VP(y)AS(x, y)可把它转化为:Q(z，a)A(-R(y)A -P(y)V -S(a, y) 这就是与/或形表示。、规则正向演绎推理2、事实表达式的与/或树表示可用一棵与/或树表示出来。例如，对上例所给出的 与/或式，可用如下与/或树来表示
9、。、规则正向演绎推理事实表达式的子句集与解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。其对应方式为：解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。例如，上图所示的与/或树有3个解树，分别对应这 以下3个子句：Q(z, a)*R(y) V S(a, y)-P(y) V - S(a, y)、规则正向演绎推理、规则正向演绎推理3、规则的与/或形变换在与/或形正向演绎系统中，是以正向方式使用规则（F规则）对综合数据库中的与/或树结构进行变换的。为简化这种演绎过程,通常要求F规则应具有如下形式:LW其中，L为单文字，W为与/或形公式。为什么要限制其前件为单
10、文字？因为在进行推理时，需要 用F规则的前件与表示事实的与/或树的叶节点（都是单文 字）进行匹配。如果领域知识的规则表示形式与上述要求不同， 则应将它转换成要求的形式。其变换步骤如下： 暂时消去蕴含符号“4，。设有如下公式：(V x)( 3y) (V z)P(x, y,z) - (Vu)Q(x, u) 运用等价关系“P QO-PVQ”，可将上式变 为：(V x)( -(3 y)(V z)P(x, y,z) V (V u)Q(x, u)(2)把否定符号“”移到紧靠谓词的位置上，使其作用域仅限 于单个谓词。通过使用狄.摩根定律及量词转换率可把上式转(V x)(Vy)(3z) -iP(x, y,z)
11、 V (Vu)Q(x, u)(3) 引入Skolem函数，消去存在量词。消去存在量词(V x)(Vy) (-P(x, y,f(x,y) V (Vu)Q(x, u)(4) 化成前束式，消去全部全称量词。消去全称量词启，上戎交另:-P(x, y,f(x,y) V Q(x, u)此公式中的变元都被视为受全称量词约束的变元。(5) 恢复蕴含式表示。利用等价关系“PVQ0P Q” 将上式变为：p(x vf(xv)fO(x u)对非单文字i青况，若茏式为L1VL2-W,则可将其 转换成与之等价的两个规则L1-W与L2-W进行 处理。4、目标公式的表示形式与/或树正向演绎系统要求目标公式用子句形表示。把一个
12、目标公式转化为子句形的步骤与子句集的化简 步骤类似，但Skolem化的过程不同。目标公式的Skolem化过程，是化简子句形的Skolem 过程的对偶形式，即把目标公式中属于存在量词辖域 内的全称变量用存在量词量化变量的Skolem函数来 代替。使经Skolem化目标公式只剩下存在量词，然后再对析取元作变量替换，最后把存在量词消掉。例如：设目标公式为(3y)(Vx) (P(x, y)VQ(x，y) 用Skolem函数消去全称量词后有(3 y)(P(f(y)，y) V Q(f(y), y)进行变量换名，使每个析取元具有不同的变量符号，于是有(3 y)P(f(y), y)V(3 z)Q(f(z),
13、z) 最后，消去存在量词得P(f(y)，y) v Q(f，z)这样，目标公式中的变量都假定受存在量词的约束、规则正向演绎推理5、规则正向演绎推理过程从已知事实出发，不断运用F规则，推出欲证明目标，具体操作为:先用与/或树把已知事实表示出来，然后再用F规贝U 的前件和与或树的叶节点进行匹配，通过一个匹配弧，把匹配成功的F规则加入到与/或树中，依此使用F规则，直到产生一个含有以目标节点为终止节点的解图为止。、规则正向演绎推理(1)命题逻辑的规则演绎过程由于命题逻辑中的公式不含变元，因此其规则演 绎过程比较简单。例325设已知事实为：AVBF规则为：rx: A-CADr2: B-EAG目标公式为：CVG推理过程：先将已知事实用与/或树表示出来，然后 再用匹配弧把巧和*分别连接到事实与/或树中与匚和 1*2前件匹配的两个不同端节点，由于出现了以目标节 点为终节点的解树，故推理过程结束，如图示。、规则正向演绎推理用归结演绎推理验证上述推理的正确性：由已知事实.规 则及目标的否定可得到如下子句集：A V B，一A V C，A V D，B V E，一B V G，一C，G其归结过程如下图所示：、规则正向演绎推理(2)谓词逻辑的规则演绎过程在谓词逻辑情况下，由于事实、F规则及目标中均含有变元，因此，其规则演绎过程还需要用最一般合一对变进 行置换。例326设已知事实的与/或
