AI确定性推理3

3.4归结演绎推理一、子句集及其化简二、鲁滨逊归结原理三、用归结反演求取问题的答案四、归结反演推理的归结策略三、归结反演推理的归结策略 哪些子句对可进行归结，哪些子句对的归结 能尽快得到空子句？需要研究有效的归结策 略。常用的归结策略可分为两大类，一类是删除 策略，另一类是限制策略。三、归结反演推理的归结策略删除策略是通过删除某些无用的子句来缩小 归结范围；限制策略是通过对参加归结的子句进行某些 限制，来减少归结前盲目性，以尽快得到空 子句。为了说明选择归结策略的重要性,先介绍广度优先策略。三、归结反演推理的归结策略1、广度优先策略是一种穷尽子句比较的复杂搜索方法。例319设有如下子句集：S= 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),-1R(y)VL(y), -L(a) 其中，一d(x)VR(x)为目标公式的否定。用 支持集策略证明S为不可满足。归结树:各级归结式数目要比宽度优先策略生成的少，但会增加空子句所在的深度。是完备策略。三、归结反演推理的归结策略3、删除策略主要想法是：归结过程在寻找可归结子句时，子 句集中的子句越多，需要付出的代价就会越大。如 果在归结时能把子句集中无用的子句删除掉，这就 会缩小搜索范围，减少比较次数，从而提高归结效 率。 常用的删除方法有以下几种（纯文字、重言 式、包孕）1、归结反演推理的归结策略III(1)纯文字删除法如果某文字L在子句集中不存在可与其互补的文字 L,则称该文字另纯文字。在归结过程中，纯文字不可能被消除，用包含纯文 字的子句进行归结也不可能得到空子句，因此对包 含纯文字的子句进行归结是没有意义的，应该把它 从子句集中删除。对子句集而言，删除包含纯文字的子句，是不影响 其不可满足性的。例如，对子句集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)都均为真。对一个子句集来说，不管是增加还是删除一个真 值为真的子句，都不会影响该子句集的不可满足 性。因此，可从子句集中删去重言式。4、三碍反演推理的归烬十卄7L（y），（x）Z，31、归结反演推理的归结策略归结树：1、归结反演推理的归结策略1、归结反演推理的归结策略采用单文字子句策略，归结式包含的文字数将少于其亲本子句中的文字数，这将有利于向空子句的方向发展，因此会有较高的归结效率。但这种策略是不完备的，即当子句集为不可满足时，用这种策略不一定能归结出空子句。5、祖先过滤策略每次参加归结的两个亲本子句，只要满足以下两个条 件申的任意一个競可抠行归结：两个亲本子句中至少有一个是初始子句集中的子句。 如果叩个亲本子句都不是初始子句集中的子句，则一个 子奇应该是另一个孚旬的免辈字勾。所谓一个子勾(例如 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、规则逆向演绎推理规则正向演绎是一种正向推理。规则正向演绎从已知事实出发，正向使用规则，直 接进行演绎，直至到达目标为止。事实、规则、目标是如何表示的？、规则正向演绎推理1、事实表达式的与/或形变换在一个基于规则的正向演绎系统中，其前提 条件中的事实表达式是作为系统的初始综合 数据库来描述的。对事实的变换，只须转换成不含蕴含符号“亠， 的与/或形表示即可，而不必化成子句集。变 换步骤为：、规则正向演绎推理、规则正向演绎推理(1)利用“P QO-iPVQ”,消去蕴含符号。(注:事实表达式中很少有，而规则中才有)(2)利用狄摩根定律及量词转换率把“，移至U紧靠谓词的位置，直到每个否定符号的辖域 最多只含一个谓词为止。对所得到的表达式进行前束化。(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、事实表达式的与/或树表示可用一棵与/或树表示出来。例如，对上例所给出的 与/或式，可用如下与/或树来表示。、规则正向演绎推理事实表达式的子句集与解树集之间存在着一一对应关系，即解树集中的每个解树都对应着子句集中的一个子句。其对应方式为：解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。例如，上图所示的与/或树有3个解树，分别对应这 以下3个子句：Q(z, a)*R(y) V S(a, y)-P(y) V - S(a, y)、规则正向演绎推理、规则正向演绎推理3、规则的与/或形变换在与/或形正向演绎系统中，是以正向方式使用规则（F规则）对综合数据库中的与/或树结构进行变换的。为简化这种演绎过程,通常要求F规则应具有如下形式:LW其中，L为单文字，W为与/或形公式。为什么要限制其前件为单文字？因为在进行推理时，需要 用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) 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、目标公式的表示形式与/或树正向演绎系统要求目标公式用子句形表示。把一个目标公式转化为子句形的步骤与子句集的化简 步骤类似，但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), 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设已知事实的与/或形表示为:P(x, y)V(Q(x)AR(v, y)F 规则为：P(u, v)-*(S(u)VN(v) 目标公式为：S(a)VN(b)VQ(c)其推理过程如下图所示:、规则逆向演绎推理规则逆向演绎推理过程是从目标公式的与/或树出发，反向使用规则（B规则），对目标公式表达式的与/或树进行变换，直到得出含有事实节点一致解图为止。事实、规则、目标公式是如何表示的？1、目标公式的与/或形变换目标公式采用与/或形表示，其化简采用与正向系统 中对事实表达式处理的对偶形式。即要用存在量词约束变元的Skolem函数，来替换由 全称量词纟6束的相应交元，消圭全祐量询，再清去 存在量词，并进行变元换名，使主析取元之间具有 不同的变元名。例如，有如下目标公式：(3y)(V x)(P(x) - (Q(x ,y) A i(R(x) A S(y) Skole m化后为-P(f(y) V (Q(f(y), y) A (-R(f(y) V -S(y) 变元换占后为-P(f(z) V (Q(f(y), y) A (-R(f(y) V -S(y)1上规则逆向演绎推理2、目标公式的与/或树变换可见，子目标是文字的合取式3、B规则的表示形式 B规则的表示形式为：W-L其中，前项W为任一与/或形公式，后项L为一单文字。当B规则为WLjAL2时，则可化件为两条规则W-Li和W-L2进行处理。4、已知事实的表示形式反向演绎系统的事实表达式限制为文字合取形式，如FjAF2A .AFn其中，每个耳（，n）都为单文字，且都可单独起作 用，因此可表示为如下集合形式 F，F2? j Fn 5. 规则逆向演绎推理过程从目标公式的与/或树出发，不断用B规则的右部，和与/或 树的叶节点进行匹配，并将匹配成功的B规则用最一般合一匹配弧加入到与或树中，直到产生某个终止在事实节点上的一致解图为止。 一致解图是指在推理过程中所用到的置换应该是一致的。例332 设有如下事实：fj： DOG(Fido) f2: BARKS(Fido)f3: WAGS-TAIL(Fido)Fido是一只狗Fido是不叫的Fido摇尾巴猫咪的名字叫Myrtlef4: MEOWS(Myrtle)规则：巧：(WAGS-TAIL(xJ/DOG(Xi)fFRIENDLY(Xi)摇尾巴的狗是温顺的狗r2: (FRIENDLY(x2) ABARKS(x2)-AFRAID(y2, x2) 温顺又不叫的东西是不值得害怕的r3: DOG(x3)ANIMAL(x3) 狗为动物r4: CAT(x4)-ANIMAL(x4)猫为动物r5: MEOWS(x5)CAT(x5)猫咪是猫问题：是否存在这样的一只猫和一条狗，使得这只猫不害怕这只狗? 该问题的目标公式为：(3x)(3y) (CAT(x)ADOG(y)A-AFRAID(x,y)目标公式经变换后得到CAT(x) ADOG(y) A AFRAID(x9 y)用逆向推理求解该问题的演绎过程如下图所示：CAT( Myrtle A DOG(Fido) AAFRAID( Myrtle, Fido思考题一、设已知：(1) 如果X是y的父亲，y是Z的父亲，贝收是Z的祖父；(2) 每个人都有一个父亲。使用归结演绎推理证明：对于某人u, 定存在 一个人V, V是U的祖父。二、设有子句集：P(x)VQ(a, b), P(a)VQ(a, b),Q(a, f(a), -iP(x) V Q(x, b)用祖先过滤策略求出其归结式。思考题三、设已知事实为(PVQ)AR) V(SA(TVU) F规则为S-*(XAY)VZ_试用正向演绎推理推出所有可能的子目标。第3章确定性推理The End