离散数学 第三章 消解原理.doc

*第三章 消 解 原 理3.1 斯柯伦标准形 内容提要 我们约定，本章只讨论不含自由变元的谓词公式(也称语句,sentences)，所说前束范式均指前束合取范式。 全称量词的消去是简单的。因为约定只讨论语句，所以可将全称量词全部省去，把由此出现于公式中的“自由变元”均约定为全称量化的变元。例如A(x)实指xA(x)。 存在量词的消去要复杂得多。考虑$xA(x)。 （1）当A(x)中除x外没有其它自由变元，那么，我们可以像在自然推理系统中所做那样，可引入A(e/x)，其中e为一新的个体常元，称e为斯柯伦（Skolem）常元，用A(e/x)代替$xA(x),但这次我们不把A(e/x)看作假设,详见下文。 （2）当A中除x外还有其它自由变元y1,yn，那么 $xA(x, y1,yn) 来自于y1yn$xA(x, y1,yn)，其中“存在的x”本依赖于y1,yn的取值。因此简单地用A(e/x, y1,yn)代替 $xA(x, y1,yn) 是不适当的，应当反映出x对y1,yn的依赖关系。为此引入函数符号f，以A(f(y1,yn)/x, y1,yn) 代替 $xA(x, y1,yn)，它表示：对任意给定的y1,yn, 均可依对应关系f确定相应的x，使x, y1,yn满足A。这里f是一个未知的确定的函数，因而应当用一个推理中尚未使用过的新函数符号，称为斯柯伦函数。 定理3.1（斯柯伦定理）对任意只含自由变元x, y1,yn的公式A(x, y1,yn)，$xA(x, y1,yn)可满足，当且仅当A(f(y1,yn), y1,yn)可满足。这里f为一新函数符号；当n = 0时，f为新常元。 定义3.1 设公式A的前束范式为B。C是利用斯柯伦常元和斯柯伦函数消去B中量词（称斯柯伦化）后所得的合取范式，那么称C为A的斯柯伦标准形（Skolem normal form）。 以下我们约定：斯柯伦标准形中，各子句之间没有相同的变元。 定义3.2 子句集S称为是可满足的，如果存在一个个体域和一种解释，使S中的每一个子句均为真，或者使得S的每一个子句中至少有一个文字为真。否则, 称子句集S是不可满足的。 习题解答练习3.1 1、求下列各式的斯柯伦标准形和子句集。 （1）(xP(x)$yzQ(y, z) （2）x(E(x, 0)$y(E(y, g(x)z(E(z, g(x)E(y, z) （3）(xP(x)$y P(y)（4） （1）（2）（3）解（1）(xP(x)$yzQ(y, z)xP(x)$yzQ(y, z) $xP(x)$yzQ(y, z)斯柯伦标准形：P(e1)Q(e2, z)子句集：P(e1)，Q(e2, z)（2）x(E(x, 0)$y(E(y, g(x)z(E(z, g(x)E(y, z) x$yz (E(x, 0)(E(y, g(x)(E(z, g(x)E(y, z) x$yz (E(x, 0)E(y, g(x)(E(x, 0)E(z, g(x)E(y, z) 斯柯伦标准形：(E(x, 0)E(f(x), g(x)(E(x, 0)E(z, g(x)E(f(x), z)子句集： E(x, 0)E(f(x), g(x), E(x, 0)E(z, g(x)E(f(x), z)（3）(xP(x)$y P(y)xP(x)$y P(y)xP(x)yP(y)xy (P(x)P(y)斯柯伦标准形：P(x)P(y)子句集：P(x),P(y) （4）（1）（2）（3）斯柯伦标准形：P(e1)Q(e2, z)(E(x, 0)E(f(x), g(x)(E(u, 0)E(y, g(u)E(f(u), y)P(w)P(v)子句集：P(e1)，Q(e2, z), E(x, 0)E(f(x), g(x), E(u, 0)E(y, g(u)E(f(u), y), P(w),P(v)2、设公式A1，A2的子句集分别为S1，S2，如果S1与S2等值（表示对应的斯柯伦标准形有相等的真值），问是否一定有A1与A2等值，为什么？解 不一定有A1与A2等值。例如，个体域为自然数集合，A1为$y P(y)，A2为$y Q(y)，P(y)表示：y是偶数，Q(y)表示：y是负数。$y P(y)与$y Q(y)不等值，但P(e1)与Q(e2)在解释I把e1，e2确定为奇数时，却是等值的。3、假如要利用子句集不可满足性来证明(PQ)(QR)(PR)永真。试作出待证公式否定的子句集。解 待证公式否定的子句集为： PQ, QR,P, Q4、要利用子句集不可满足性来证明例2.25的推理是正确的。试作出这一推理的否定（前提1前提2结论）的子句集。解5. 试简述A(e/x) 或A(f(y1,yn)/x, y1,yn) 可以在应用消解原理的推理中代替 $xA(x) 或 y1yn$xA(x, y1,yn) 的原因,以及选择e,f应注意的事项。解 A(e/x) 或A(f(y1,yn)/x, y1,yn) 可以在应用消解原理的推理中代替 $xA(x) 或 y1yn$xA(x, y1,yn) 的原因是：（1） （1） 用消解原理证明定理A或证明 GA，是通过确认A和B1BnA(B1,Bn为G中公式)的不可满足性来实现的。（2） （2） A(e/x) ，A(f(y1,yn)/x, y1,yn)与$xA(x) ，y1yn$xA(x, y1,yn)的不可满足性是相同的。选择e,f应注意选择新常元和新函数符号，即在推理过程中尚未使用过的常元和函数符号。3.2 命题演算消解原理内容提要 关于命题演算的消解原理。设C1，C2为两个子句，L1，L2是分别属于C1，C2的互补文字对，用C-L表示从子句C中删除文字L后所得的子句，那么消解原理可表示为 其中C1,C2称为消解母式，L1，L2称为消解基，而(C1-L1)(C2-L2)称为消解结果。 特别地，当C1，C2都是单文字子句，且互补时，C1，C2的消解结果不含有任何文字，这时我们称其消解结果是“空子句”（nil），常用符号 表示之, 空子句是永远无法被满足的。 关于消解原理我们有： 定理3.2 设C是C1，C2的消解结果，那么C是C1和C2的逻辑结果。 本定理的证明可仿以上对式（3.1）的证明，请读者自行完成。据本定理知，消解原理作为推理规则是适当的。 作为特别情况，p与p的消解结果是，实质上是pp的另一种表示形式,它们都是不可满足的，因而也满足定理3.2的结论。定义3.3 设S为一子句集，称C是S的消解结果，如果存在一个子句序列C1，C2 ，,Cn（= C），使Ci(i = 1,2, ,n) 或者是S中子句，或者是Ck，Cj (k,j i) 的消解结果。该序列称为是由S导出的C的消解序列。当是S的消解结果时，称该序列为S的一个否证（refutations）。定理3.3 如果子句集S有一个否证，那么S是不可满足的。 习题解答练习3.21、 1、 完成定理3.2证明。证 设C1，C2为两个子句，L1，L2是分别属于C1，C2的互补文字对，用C-L表示从子句C中删除文字L后所得的子句，那么消解原理可表示为 设C1，C2分别为L1C1，L2C2 ; L1，L2为消解基， 即C1=C1- L1 ，C2= C2- L2。由于L2 = L1，那么（L1C1）（L2C2）（L1C1）（L1C2） （L1C2）（C1L1）（C1C2） C1C2于是我们有 (L1C1)(L2C2)（C1- L1）（C2- L2）即C1C2（C1- L1）（C2- L2）。这就是说，C1与C2的消解结果是C1和C2的逻辑结果。 2、证明下列子句集是不可满足的。（1）S = pq, qr, pq, r解（1）pq （2）qr（3）pq（4）r（5）q 由（2）（4）消解得（6）p 由（1）（5）消解得（7）p 由（3）（5）消解得（8）（2）S = pq, qr, rw, rp, wq, qr解（1）pq （2）qr（3）rw（4）rp（5）wq （6）qr （7）rq 由（1）（4）消解得（8）q 由（2）（7）消解得（9）w 由（5）（8）消解得（10）r 由（6）（8）消解得（11）r 由（3）（9）消解得（12） 由（10）（11）消解得 3、用消解原理证明下列逻辑蕴涵式。（1）(pq)r (pr)(qr)解 S = pr,qr, pq , pr, qr, r（1）pr （2）qr（3）pq（4）pr（5）qr （6）r （7）p 由（1）（6）消解得（8）q 由（2）（6）消解得（9）q 由（3）（7）消解得（10） 由（8）（9）消解得（2）(pr)(qr) (pq)r解 S = pr,qr, pq , r（1）pr （2）qr（3）pq（4）r （5）p 由（1）（4）消解得（6）q 由（2）（4）消解得（7）q 由（3）（5）消解得（8） 由（6）（7）消解得（3）(p(q(rs)ps q解 S = pqr, pqs, p,s, q （1）pqr （2）pqs（3）p（4）s （5）q （6）qs 由（2）（3）消解得（7）s 由（5）（6）消解得（8） 由（4）（7）消解得（4）(pq)(pr)(qs) rs解 S = pq,pr, qs, r,s （1）pq （2）pr（3）qs（4）r（5）s （6）q 由（3）（5）消解得（7）p 由（1）（6）消解得（8）r 由（2）（7）消解得（9） 由（4）（8）消解得 4、已知有如下化学反应方程式 MgO+H2Mg+H2O C+O2CO2 CO2+H2OH2CO3现假定有物质MgO，H2，O2和C，形式证明可生成H2CO3。（用代替方程式中+，用分子式作为命题符号，表示该物质存在，例如MgO表示：“有MgO”，而MgO则表示“没有MgO”，从而得到一系列命题演算公式，再用消解原理证明，由它们可推出H2CO3。）解 S = MgO, H2, O2, C, MgOH2Mg, MgOH2H2O, CO2CO2 , CO2H2OH2CO3,H2CO3 （1）MgO （2）H2（3）O2（4）C （5）MgOH2Mg （6）MgOH2H2O（7）CO2CO2（8）CO2H2OH2CO3（9） H2CO3（10）H2Mg 由（1）（5）消解得（11）H2H2O 由（1）（6）消解得（12）O2CO2 由（4）（7）消解得（13）Mg 由（2）（10）消解得（14）H2O 由（2）（11）消解得（15）CO2 由（3）（12）消解得（16）H2OH2CO3 由（8）（15）消解得（17）H2CO3 由（14）（16）消解得（18） 由（9）（17）消解得3.3 谓词演算消解原理内容提要 定义3.4 形如t1/v1, t2/v2, , tn/vn的有穷集合称为一个代换（substitution），其中v1, vn为任意变元，t1,tn为任意个体项，但tivi(i = 1,2, ,n)。当代换为一空集合时，称为空代换。代换用小写希腊字母表示，空代换记为e，“对任意公式或项X作代换q”记为Xq，其意为对X中变元v1,v2, vn分别作代入t1,tn，即 Xq = Xt1/v1, t2/v2, , tn/vn 对于空代换e有Xe= X。 定义3.5 设q=t1/x1,tn/xn, s =s1/y1,sm/ym是两个代换，q与s的合成，记为q s，指如下所得的代换： 从 t1s/x1,tns/xn, s1/y1,sm/ym 中删去 （1）si/yi， 当yi恰为x1,xn之一 （2）tis/xi，当tis = xi。很显然，由于作了（1），（2）删除，q s仍为一代换。直觉地，它是指与先作q代换、再作s代换效果一样的一个代换。qs = sq 一般不能成立。 定义3.6 代换 q 称为表达式集合X1 , , Xn的一致化（unifier），如果 q 使 X1q = = Xnq 。X1 , , Xn的一致化称为是最一般的（most general unifier，简记为mgu），如果对X1 , , Xn的每一个一致化s，均有一代换，使s = q 。 X1 , , Xn有一致化（或称可一致化），则它必定有最一般的一致化mgu 。 考虑谓词公式斯柯伦标准形的子句集中的子句。 设C1，C2为两子句（我们曾约定它们无公共变元），分别含有文字L1和L2，且L1和L2（或 L1和L2）可一致化，其mgu为q 。那么，下列推理规则称为一阶谓词演算的消解原理： 这一过程表示：先对C1，C2作代换，使L1与 L2（或 L1和L2）一致化，然后再消解掉L1q和L2q，其余文字的析取便是C1，C2的消解结果。 如果在一阶谓词演算中引进了等词，那么光靠消解原理来进行推理便不够了。例如，由t1 = t2及P(t1)可推出P(t2)，这一推理无法通过消解来实现，因而在带等词的一阶谓词演算中，还要引进一条规则，它与消解原理联合使用能使问题得到圆满解决，这就是所谓换位原理（paramoduration principle）。 考虑下列规则： 它可以推广为 （3-3） 对式（3-3）再作推广便是换位原理。 设子句C1含有文字L(t)，记为L(t)C1,子句C2含有原子公式t1 = t2，记为t1 = t2C2,且t与t1，（或t2）有mgu s，那么 这里C1，C2称为换位母式，L(t)及t1 = t2称为换位基，其结果称为换位结果。注意：L(t)表示文字L中含项t，Ls( t2s)指：对L作代换s后,将原有项ts改为t2s。 消解原理和换位原理的联合使用，对于带等词的一阶谓词演算的定理证明是完备的，也就是说，只要A是该系统的定理（永真式），那么必可用消解原理和换位原理导出A的一个否证。 习题解答练习3.31、 1、 设代换q = a/x, f(z)/y, y/z，= b/x, z/y, g(x)/z试计算q 和 q 。解 q = a/x, f(g(x)/y, g(x)/z q = b/x, g(a)/z , f(z)/y 2、下列子句对可否一致化？若可一致化，试作出它们的mgu。（1）Q(a) , Q(b) （2）P(a,x) , P(a,a) （3）R(a,x,f(x) , R(a,y,y) （4）S(x,y,z) , S(u,h(u,v),u)（5）T(x,g(x),y,h(x,y),z,i(x,y,z) , T(u,v,k(v),w,f(v,w),w)解（1）不可一致化。（2）可一致化，mgu=a/x（3）不可一致化。（4）可一致化，mgu=u/x, h(u,v)/y,u/z（5）可一致化，mgu=x/u, g(x)/v, k(g(x)/y, h(x, k(g(x)/w, f(g(x), h(x, k(g(x)/z, i(x, k(g(x), h(x, k(g(x)/ w 3、用消解原理判定，下列子句集是否可满足： （1）P(x) , P(a)P(f(x) （2）P(x)P(f(x) , P(a) （3）P(x) , P(f(x)（4）P(x)P(f(x) , P(f(x)解（1）P(x) , P(a)P(f(x)等价于P(x) , P(a)P(f(y),用代换a/x和f(y)/x作两次消解即可得到空字句，因此P(x) , P(a)P(f(x)不可满足。（2）P(x)P(f(x) , P(a)可满足。（3）P(x) , P(f(x)等价于P(x) , P(f(y), 用代换f(y)/x作消解即可得到空字句，因此P(x) , P(f(x)不可满足。（4）P(x)P(f(x) , P(f(x)等价于P(y)P(f(y) , P(f(x) 用代换y/x和f(x)/y作两次消解即可得到空字句，因此P(x)P(f(x) , P(f(x)不可满足。4、设子句集S由下列子句组成： （1）M(a,f(c),f(b) （2）P(a) （3）M(x,x,f(x) （4）M(x,y,z)M(y,x,z) （5）M(x,y,z)D(x,z) （6）P(x)M(y,z,u)D(z,u)D(x,y)D(x,z) （7）D(a,b)用消解原理证明S不可满足。解（8）D(x, f(x) 由（5）x/y,f(x)/z,（3）消解得（9）M(y,z,u)D(z,u)D(a,y)D(a,z) 由（6）a/x,（2）消解得（10）D(x, f(x)D(a,x) 由（9）x/y,x/z, f(x)/u,（3）消解得（11）D(a, x) 由（8）,（10）消解得（12） 由（11）b/x,（7）消解得5、用消解原理证明： x(H(x)A(x) x(y(H(y)N(x,y)$y(A(y)N(x,y) 证 作出子句集，它包括 （1）H(x)A(x) （2）H(e2) （3）N(e1,e2)（4）A(y)N(e1,y)进行消解 （5）A(e2) 由（1） e2/x,（2）消解得 （6）A(e2) 由（4） e2/y,（3）消解得 （7） 由（5）,（6）消解得6、用消解原理证明例2.25的推理是正确的。解 例2.25的推理可表示为作出子句集，它包括(1) (1) P(e1)(2) D(y)L(e1,y)(3) P(x)S(z)L(x,z)(4) D(e2)(5) S(e2)进行消解（6）S(z)L(e1,z) 由（3） e1/x,（1）消解得（7）L(e1, e2) 由（6） e2/z,（5）消解得(8) D(e2) 由（2） e2/y,（7）消解得（9） 由（5）,（8）消解得 7、用消解原理证明下列推理是正确的： 解 作出子句集，它包括 （1）E(x)V(x)W(x,f(x)(2) E(x)V(x)C(f(x)(3) W(e,y)P(y)(4) P(e)(5) E(e)(6) P(x)V(x)(7) P(x)C(x)进行消解(8) V(e) 由（6） e/x,（4）消解得(9) C(e) 由（7） e/x,（4）消解得（10）E(e)V(e)P(f(e) 由（1） e/x,f(e)/y,（3）消解得(11) V(e)P(f(e) 由（5）,（10）消解得(12) P(f(e) 由（8）,（11）消解得(13) V(e)C(f(e) 由（2）e/x,（5）消解得(14) C(f(e) 由（8）（13）消解得(15)C(f(e) 由（7）f(e)/x,（12）消解得（16） 由（14）,（15）消解得8、利用消解原理和换位原理证明下列子句集S是不可满足的： （1）S = Q(a)R(a)a=b , Q(a)a=b , R(a)f(a)f(b) , f(x)=f(x)（2）S = Q(c)c=d , Q(c)f(c