离散数学-第三章-消解原理.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) 来自于"y1…"yn$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)→$y"zQ(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)→$y"zQ(y, z))┝┥┐"xP(x)∧$y"zQ(y, z)
┝┥$x┐P(x)∧$y"zQ(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$y"z (E(x, 0)∨(E(y, g(x))∧(┐E(z, g(x))∨E(y, z))))
┝┥"x$y"z ((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)∧"y┐P(y)
┝┥"x"y (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、假如要利用子句集不可满足性来证明(P→Q)∧(Q→R)→(P→R)永真。试作出待证公式否定得子句集。
解 待证公式否定得子句集为:{ ┐P∨Q, ┐Q∨R,P, ┐Q}

4、要利用子句集不可满足性来证明例2、25得推理就是正确得。试作出这一推理得否定(┐(前提1∧前提2→结论))得子句集。
解

5、 试简述A(e/x) 或A(f(y1,…,yn)/x, y1,…,yn) 可以在应用消解原理得推理中代替 $xA(x) 或 "y1…"yn$xA(x, y1,…,yn) 得原因,以及选择e,f应注意得事项。
解 A(e/x) 或A(f(y1,…,yn)/x, y1,…,yn) 可以在应用消解原理得推理中代替 $xA(x) 或 "y1…"yn$xA(x, y1,…,yn) 得原因就是:
（1） (1)               用消解原理证明定理A或证明 G┝A,就是通过确认┐A与B1∧¼∧Bn∧┐A(B1,¼,Bn为G中公式)得不可满足性来实现得。
（2） (2)               A(e/x) ,A(f(y1,…,yn)/x, y1,…,yn)与$xA(x) ,"y1…"yn$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得消解结果就是□,□实质上就是p∧┐p得另一种表示形式,它们都就是不可满足得,因而也满足定理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、2
1、 1、  完成定理3、2证明。
证 设C1,C2为两个子句,L1,L2就是分别属于C1,C2得互补文字对,用C-L表示从子句C中删除文字L后所得得子句,那么消解原理可表示为

设C1,C2分别为L1∨C1’,L2∨C2’ ; L1,L2为消解基, 即C1’=C1- L1 ,C2’= C2- L2。
由于L2 = ┐L1,那么
(L1∨C1’)∧(L2∨C2’)┝(L1∨C1’)∧(┐L1∨C2’)
┝ (L1∧C2’)∨(C1’∧┐L1)∨(C1’∧C2’)
┝ C1’∨C2’
于就是我们有
(L1∨C1’)∧(L2∨C2’)┝(C1- L1)∨(C2- L2)
即C1∧C2┝(C1- L1)∨(C2- L2)。这就就是说,C1与C2得消解结果就是C1与C2得
逻辑结果。

2、证明下列子句集就是不可满足得。
(1)S = {p∨q, ┐q∨r, ┐p∨q, ┐r}
解(1)p∨q
(2)┐q∨r
(3)┐p∨q
(4)┐r
(5)┐q 由(2)(4)消解得
(6)p 由(1)(5)消解得
(7)┐p 由(3)(5)消解得
(8)□

(2)S = {p∨q, q∨r, r∨w, ┐r∨┐p, ┐w∨┐q, ┐q∨┐r}
解(1)p∨q
(2)q∨r
(3)r∨w
(4)┐r∨┐p
(5)┐w∨┐q
(6)┐q∨┐r
(7)┐r∨q 由(1)(4)消解得
(8)q 由(2)(7)消解得
(9)┐w 由(5)(8)消解得
(10)┐r 由(6)(8)消解得
(11)r 由(3)(9)消解得
(12)□ 由(10)(11)消解得

3、用消解原理证明下列逻辑蕴涵式。
(1)(p∨q)→r┝ (p→r)∧(q→r)
解 S = {┐p∨r,┐q∨r, p∨q , p∨┐r, q∨┐r, ┐r}
(1)┐p∨r
(2)┐q∨r
(3)p∨q
(4)p∨┐r
(5)q∨┐r
(6)┐r
(7)┐p 由(1)(6)消解得
(8)┐q 由(2)(6)消解得
(9)q 由(3)(7)消解得
(10)□ 由(8)(9)消解得

(2)(p→r)∧(q→r) ┝ (p∨q)→r
解 S = {┐p∨r,┐q∨r, p∨q , ┐r}
(1)┐p∨r
(2)┐q∨r
(3)p∨q
(4)┐r
(5)┐p 由(1)(4)消解得
(6)┐q 由(2)(4)消解得
(7)q 由(3)(5)消解得
(8)□ 由(6)(7)消解得

(3)(p→(┐q∨(r∧s)))∧p∧┐s┝ ┐q
解 S = {┐p∨┐q∨r, ┐p∨┐q∨s, p,┐s, q }
(1)┐p∨┐q∨r
(2)┐p∨┐q∨s
(3)p
(4)┐s
(5)q
(6)┐q∨s 由(2)(3)消解得
(7)s 由(5)(6)消解得
(8)□ 由(4)(7)消解得

(4)(p∨q)∧(p→r)∧(q→s) ┝ r∨s
解 S = { p∨q,┐p∨r, ┐q∨s, ┐r,┐s }
(1)p∨q
(2)┐p∨r
(3)┐q∨s
(4)┐r
(5)┐s
(6)┐q 由(3)(5)消解得
(7)p 由(1)(6)消解得
(8)r 由(2)(7)消解得
(9)□ 由(4)(8)消解得

4、已知有如下化学反应方程式
MgO+H2→Mg+H2O
C+O2→CO2
CO2+H2O→H2CO3
现假定有物质MgO,H2,O2与C,形式证明可生成H2CO3。(用∧代替方程式中+,用分子式作为命题符号,表示该物质存在,例如MgO表示:“有MgO”,而┐MgO则表示“没有MgO”,从而得到一系列命题演算公式,再用消解原理证明,由它们可推出H2CO3。)
解 S = {MgO, H2, O2, C, ┐MgO∨┐H2∨Mg, ┐MgO∨┐H2∨H2O, ┐C∨┐O2∨CO2 , ┐CO2∨┐H2O∨H2CO3,┐H2CO3 }
(1)MgO
(2)H2
(3)O2
(4)C
(5)┐MgO∨┐H2∨Mg
(6)┐MgO∨┐H2∨H2O
(7)┐C∨┐O2∨CO2
(8)┐CO2∨┐H2O∨H2CO3
(9) ┐H2CO3
(10)┐H2∨Mg 由(1)(5)消解得
(11)┐H2∨H2O 由(1)(6)消解得
(12)┐O2∨CO2 由(4)(7)消解得
(13)Mg 由(2)(10)消解得
(14)H2O 由(2)(11)消解得
(15)CO2 由(3)(12)消解得
(16)┐H2O∨H2CO3 由(8)(15)消解得
(17)H2CO3 由(14)(16)消解得
(18)□ 由(9)(17)消解得

3、3 谓词演算消解原理
内容提要
定义3、4 形如{t1/v1, t2/v2, …, tn/vn}得有穷集合称为一个代换(substitution),其中v1,…, vn为任意变元,t1,…,tn为任意个体项,但ti≠vi(i = 1,2, …,n)。当代换为一空集合时,称为空代换。代换用小写希腊字母表示,空代换记为e,“对任意公式或项X作代换q”记为Xq,其意为对X中变元v1,v2,…, vn分别作代入t1,…,tn,即
Xq = X{t1/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代换效果一样得一个代换。
q◦s = s◦q 一般不能成立。
定义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 = t2∨C2’,且t与t1,(或t2)有mgu s,那么

这里C1,C2称为换位母式,L(t)及t1 = t2称为换位基,其结果称为换位结果。注意:L(t)表示文字L中含项t,Ls( t2s)指:对L作代换s后,将原有项ts改为t2s。
消解原理与换位原理得联合使用,对于带等词得一阶谓词演算得定理证明就是完备得,也就就是说,只要A就是该系统得定理(永真式),那么必可用消解原理与换位原理导出┐A得一个否证。
习题解答
练习3、3
1、 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=b
2) 2)      Q(a)∨a=b
3) 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=d
2)┐Q(c)∨f(c)≠f(d)
3)Q(c)∨a=b
4)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)∨a≠b a=b a=c a=a

P(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)∨a≠b,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)∨a≠b
（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)消解得