5.谓词演算(5.6-5.8).ppt

第五章 谓词演算5.15.1 谓词演算的基本概念5.25.2 归结5.35.3 归结反演系统5.45.4 基于归结法的问答系统5.55.5 归结法的应用5.65.6 基于规则的正向演绎系统5.75.7 基于规则的反向演绎系统5.85.8 基于规则演绎系统的搜索策略5.6 5.6 基于规则的正向演绎系统基于规则的正向演绎系统5.6.1 5.6.1 正向演绎系统的基本思想正向演绎系统的基本思想逻辑蕴涵式与子句的区别：上面二个表达式在逻辑上是等价的，但是所表达的概念有区别：强调推理性(即：前件为真时后件为真)：只是表示了A、B、C中有一个为真，则公式为真可见：将蕴涵式些成与其等价的子句形式会损失一些逻辑信息。直接利用蕴涵式 所做的证明系统就是基于规则的演绎系统。5.6.2 5.6.2 事实表达式的与或表示事实表达式的与或表示方法：将规则前件的事实表达式从规则中分离出来，单独变换成与或形式的表 达式，但是不必化简成子句。例如：一个事实表达式：消去存在量词，由斯托林常量代替变元x，得到一个与或表达式：利用等价变换，得到：对第一个合取项进行变量换名(w/y)，目的是保证每个合取项的变量名都不相同得到公式：上式不是子句，但是一个与或表达式，可以直接用于正向推理系统。用与或图表示一个与或表达式：与或图中的节点代表子表达式当表达式为析取式(E1E2 Ek)时，则每个子表达式表示为原表达式 的一个后继节点，且用一个K连接符连接每个Ei，表示为与关系。当表达式为合取式(E1E2 Ek)时，则每个子表达式单独作为原表达 式的一个子节点，用1连接符连接，表示为或关系。上例的事实表达式用与或图表示如下：可以看出，每个端节点都是一个文字，所以与或图相当于把一个表达式按照与或关系拆分成文字表示。讨论：利用与或图求解图：方法与可分解系统中的解图求法相同。不同的是与或图中的节点之间的合取、析取关系是相反的。因此，求解图是按照K连接方式求解，而不是按照真值求解。上图中的三个解图分别构成三个子句：Q(w,A),R(y)S(A,y),P(y)S(A,y)基于规则正向推理系统中的与或图是一种知识表达方式；可分解系统中的与或图是一种图搜索方式，二者是不同的。5.6.3 命题逻辑的正向推理命题逻辑的正向推理关于规则的限制：规则以单文字前提出现 L W，其中：L：单文字前提W：用与或形式表示的任何公式如果规则为(L1L2)W形式，即前提是析取形式，则将其分解成二条规则 L1 W，L2 W如果规则为(L1L2)W形式，即前提是析取形式，不予讨论。例题见下页。例：初始数据库的与或表达式为：(PQ)R S (TU)规则：S(XY)Z推理过程：用与或图表示初始条件表达式 寻找与规则前提匹配的文字 用匹配弧连接上述两个文字 将规则结论的与或图连接到前提上，扩充与或图 正向系统的推理树根节点在下部推理树见下页(本例没有给出目标公式，仅为了说明事实与规则的推理树表达）(PQ)R S (TU)XYXYZSSTUTUS(TU)(PQ)RPQRPQ规则：S(XY)Z例：事实表达式 AB （本例包括了事实、规则、目标）规则 R1：A(CD)R2：B(EG)目标 CG推理树：由此解图得到子句集：CE,CG,DE,DG其中：CG是目标ABCGCDEGABABR1R25.6.4 谓词逻辑正向推理系统谓词逻辑正向推理系统1 目标公式的标准化(1)消去目标公式中的全称量词，用斯托林函数或常量替换该量词所约束的变元(2)自然消去全部存在量词(3)目标公式仅为文字的析取（正向推理系统的要求）(4)每个析取项的变量要使用不同的符号（变量换名）例：目标公式：消去全称量词，用斯托林函数代替变元y：自然消去存在量词：变量标准化：2 谓词逻辑与或图(1)求出事实表达式的与或图(2)设该图的一个端节点L与某规则LW的前提L可以合一，利用Unify算法求 出置换集 mgu(3)用匹配弧连接L L，并用mgu 对L和L置换合一(4)展开规则结论的与或图，直至出现目标例：给定事实：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)P(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)S(A)X(B)u=A/x,B/yu=B/xQ(B,A)U(A)u=B/yR(B,B)V(B)对应二个子句：S(A)X(B)U(A)；S(A)X(B)V(B)根据与或关系，得到二个子图(隐含在与或图中，一般不必单独画出来)，对应的二个子句是：S(A)X(B)U(A)（不一致解图）S(A)X(B)V(B)（一致解图）其中(后者)：变量x,y 分别按照置换u=A/x,B/y做相应的置换 u=A/x,B/yu=B/xu=A/x,B/yu=B/y关于置换一致性的定义：设置换集的集合u1,u2,un ui=ti1/vi1,ti2/vi2,tim/vim 是任意置换集定义二个表达式：U1=v11,v12,vn1,vn2,vnm 所有变量构成 U2=t11,t12,tn1,tn2,tnm 所有项构成置换集合u1,u2,un是一致的，当且仅当U1和U2是可合一的。合一复合定义：使得U1和U2可合一的mgu称为合一复合。例：u1 u2 U1 U2 合一复合 1A/x B/x U1=x,x,U2=A,B 不具有一致性2x/y y/z U1=y,z,U2=x,y x/y,x/z3 f(z)/x f(A)/x U1=x,x,U2=f(z),f(A)f(z)/x,A/x讨论：1 求合一复合的过程满足可结合性合可交换性（即：匹配弧的使用次序无关）2 生成与或图时，如果多次调用同一条规则，则每次调用时都要对变量换名一个正向推理例题：事实表达式：D(FIDO)(B(FIDO)I(FIDO)规则：R1：D(x)T(x)R2：B(y)N(y)目标公式：T(z)N(z)其中：规则中的变元x，y是全称量词约束；目标公式中的变元z是存在量词约束上面公式是已经标准化后的公式 得到二个解图：T(z)N(z)T(z)I(FIDO)T(z)N(z)T(FIDO)N(FIDO)D(x)B(y)D(FIDO)B(FIDO)I(FIDO)B(FIDO)I(FIDO)D(FIDO)(B(FIDO)I(FIDO)FIDO/xFIDO/zFIDO/zFIDO/y与或图与或图R1：D(x)T(x)R2：B(y)N(y)其中：第一个子句是目标公式，下面判断它是否是一致解图。构造置换集的集合FIDO/z,FIDO/y,FIDO/x 求出 U1=z,y,x,U2=FIDO,FIDO,FIDO 求出合一复合 u=FIDO/z,FIDO/y,FIDO/x 用合一复合u对子句T(z)N(z)做置换，得到目标公式：T(FIDO)N(FIDO)结论：此目标是原事实表达式与给定规则的逻辑结论。正向演绎系统小结：事实表达式为与或形规则形式：LW,其中L为单文字目标公式为文字析取对事实和规则进行Skolem化，消去存在量词，变量受全称量词约束，对主合取元和规则中的变量换名用“对偶形”对目标进行Skolem化，消去全称量词，变量受存在量词约束，对析取元中的变量换名事实表达成与或树，其中，“”对应树中“与”，“”对应树中“或”从事实出发，正向应用规则，到得到目标节点为结束的一致解图为止存在合一复合时，则解图是一致的5.7 基于规则的逆向演绎系统基于规则的逆向演绎系统5.7.1 目标表达式的与或表示目标表达式的与或表示 逆向推理系统从目标开始，与正向系统相反，规则的使用是反向的。目标表达式的与或形式：(1)利用斯托林函数对目标公式进行标准化（消去全称量词）(2)各析取项之间变元要各不相同（变量换名）(3)子表达式之间为析取关系时，使用1连接符连接 子表达式之间为合取关系时，使用K连接符连接(4)与或图的根节点在上面例：目标公式：标准化，得到：变量换名，得到：5.7.2 逆向推理系统逆向推理系统关于规则的限制：B规则的形式：W L其中：W：任何与或公式 L：单文字结论 规则中的变元全部是全称量词约束 如果规则为W(L1L2)形式，则分解为两条规则：W L1 和 W L2推理过程：(1)用与或图表示目标表达式(2)寻找与规则结论匹配的文字(3)用匹配弧连接上述的二个匹配文字(4)将规则的结论与前提连接，扩充与或图，直至出现事实表达式的文字(5)反向推理树的根节点在上面反向推理例题：事实表达式：F1：D(FIDO)F2：B(FIDO)F3：W(FIDO)F4：M(MR)规则：R1：W(x1)D(x1)F(x1)R2：(F(x2)B(x2)A(x2)R3：M(x3)C(x3)目标公式：C(x)D(y)A(x,y)得到一个解图：M(MR)D(FIDO)W(FIDO)D(FIDO)B(FIDO)判断是否是一致解图：C(x)A(x,y)D(y)A(y2,x2)M(x)F(y)B(y)x/x3x/y2,y/x2FIDO/y逆向推理树逆向推理树C(x)D(y)A(x,y)C(x3)D(FIDO)M(MR)MR/xF(x1)B(FIDO)FIDO/yy/x1D(y)W(y)W(FIDO)D(FIDO)FIDO/yFIDO/y(1)由反向推理树得到所有置换：x/x3,MR/x,FIDO/y,x/y2,y/x2,FIDO/y,y/x1,FIDO/y,FIDO/y(2)求出：U1=(x3,x,y,y2,x2,y,x1,y,y)U2=(x,MR,FIDO,x,y,FIDO,y,FIDO,FIDO)(3)求出合一复合：U=(x/x3,MR/x,FIDO/y,MR/y2,FIDO/x2,FIDO/x1)(4)利用合一复合对目标公式作置换，得到置换例：C(MR)D(FIDO)A(MR,FIDO)该置换例就是推理结果 练习题练习题:事实表达式:(1)Bit(A,dog)(2)Bit(B,cat)产生式规则：R1:Bit(x1,dog)Deer(x1)R2:Bit(x2,cat)Tiger(x2)R3:Bit(B,x3)Bit(A,x3)目标表达式：Deer(y)Tiger(y)5.8 基于规则演绎系统的搜索策略（选讲）基于规则演绎系统的搜索策略（选讲）搜索目的：在所有解图中找出一个具有一致性的解图以下搜索策略是基于逆向推理系统方法1：局部修剪 在生成解图过程中（即：随着解图的不断扩展，并非等到解图全部生成完毕），随时任取一个局部解图，判断其一致性，如不具备一致性，则剪掉不必要的分支。例：目标公式：P(x)Q(x)规则：R1：R(y)P(y)R2：S(z)P(B)事实表达式：R(A)Q(A)解：与或图见下页R(x)Q(A)对应的置换集 x/y,A/xS(z)Q(A)对应的置换集 B/x,A/x显然，第二个置换集不满足一致性，即二个分支不能同时成立。但是因为Q(A)是Q(A)的唯一分支，所以必须保留该分支，修剪掉另外一个分支：R2。P(x)Q(x)x/yA/xP(x)Q(x)P(B)R(x)P(y)B/xR(A)A/xR1R2S(z)Q(A)到此已经生成二个局部解图目标节点目标节点唯一分支被修剪分支方法2：规则连接图1 首先将前后件具有连接关系的所有规则先连接起来，构成规则连接图，并且标明所有置换。2 将目标与或图挂在规则连接图上部（寻找匹配关系）3 将事实节点挂在规则连接图的下部（具备匹配关系）4 寻找一个解图，求出合一复合，如果满足一致性，则该解图成立，否则重复寻找其它解图。例：同5.7.2节例题，规则如下：R1：(W(x1)D(x1)F(x1)R2：(F(x2)B(x2)A(x2)R3：M(x3)C(x3)规则连接图见下页以上是二个规则连接图。在此基础上，考虑上面挂目标与或图，下面挂事实文字。一个值得注意的问题：一个值得注意的问题：在规则连接图上如果多次使用同一条规则，必须注意：每次使用此规则时，要对规则中的变元换名。A(y2,x2)F(x2)B(x2)F(x1)x1/x2D(x1)W(x1)R2R1C(x3)M(x3)R3例：事实：P(A)规则 R：P(x)P(f(x)目标：P(f(f(A)规则连接图：P(f(x)P(x)规则的重复使用次数如果是固定的有限次，可以分别展开连接。如果使用次数不固定，则只能如上图所示表示规则的多次连接使用P(f(x)P(x)P(f(f(A)P(A)上连目标公式下连事实公式中间的规则连接图不变上图的规则R仅仅使用一次是无法得到结果P(A)的。实际上需要重复使用二次规则R才能推出所要的结果P(A)见下页。原例：事实：P(A)规则 R：P(x)P(f(x)目标：P(f(f(A)P(f(x)P(f(A)P(f(f(A)P(A)f(A)/xP(f(y)A/yP(A)目标表达式规则 R，第一次使用规则 R第二次使用，换名事实表达式规则结论规则结论规则前提规则前提