收藏 分销(赏)

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

上传人:人****来 文档编号:4356017 上传时间:2024-09-12 格式:DOC 页数:9 大小:71KB
下载 相关 举报
离散数学-第三章-消解原理.doc_第1页
第1页 / 共9页
离散数学-第三章-消解原理.doc_第2页
第2页 / 共9页
点击查看更多>>
资源描述
*第三章 消 解 原 理 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)消解得
展开阅读全文

开通  VIP会员、SVIP会员  优惠大
下载10份以上建议开通VIP会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传
相似文档                                   自信AI助手自信AI助手

当前位置:首页 > 教育专区 > 其他

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        抽奖活动

©2010-2025 宁波自信网络信息技术有限公司  版权所有

客服电话:4009-655-100  投诉/维权电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服