离散数学-第三章-消解原理.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)f(d) , Q(c)a=b , Q(c)f(a)f(b) , f(x)=f(x)解 (1)S = Q(a)R(a)a=b , Q(a)a=b , R(a)f(a)f(b) , f(x)=f(x)1) 1) Q(a)R(a)a=b2) 2) Q(a)a=b3) 3) R(a)f(a)f(b)4) 4) f(x)=f(x)5) 5) R(a)a=b 由(1),(2)消解得6) 6) f(a)f(b)a=b 由(3),(5)消解得7) 7) 由(5)a/x,(2)换位消解得(2)S = Q(c)c=d , Q(c)f(c)f(d) , Q(c)a=b , Q(c)f(a)f(b) , f(x)=f(x)1)Q(c)c=d2)Q(c)f(c)f(d)3)Q(c)a=b4)Q(c)f(a)f(b)5)f(x)=f(x)6)Q(c)f(c)f(c) 由1),2)换位得7)Q(c) 由5)c/x,6)消解得8)Q(c)f(a)f(a) 由3),4)换位得9)Q(c) 由5)c/x,8)消解得10) 由(7),(9)消解得9、图3、2表示一个消解、换位过程,请依图写出原始子句集及消解、换位得详细步骤。 a=b P(a)R(a,b) P(c)ab a=b a=c a=aP(a)R(b,b) R(b,b) P(c) c=a P(a) P(a) 图3、2解 原始子句集S=a=b,P(a)R(a,b),P(c)ab,a=c,a=a,R(b,b)（1） (1) a=b（2） (2) a=c（3） (3) a=a（4） (4) R(b,b)（5） (5) P(a)R(a,b)（6） (6) P(c)ab（7） (7) P(a)R(b,b) 由(1),(5)换位得（8） (8) P(c) 由(1),(6)消解得（9） (9) c=a 由(2),(3)换位得（10） (10) P(a) 由(4),(7)消解得（11） (11) P(a) 由(8),(9)换位得（12） (12) 由(10),(11)消解得