离散数学-归结反演系统

1、1/601/60离 散 数 学 Discrete Mathematics计算机科学与工程学院 金 忠http:/patternrecognition.asia/dm2/49回顾：谓词演算的假设推理过程定义: 如果能够作出一系列合式公式序列 A1，A2, A3, ，An，它们满足下列性质：(1)诸Ai或为公理/定理之一；(2) 或为公式1, 2, ,k之一，每个i称为假设；(3) 或由前面的若干个Ag、Ah利用分离规则、全n规则、存n规则等而得；(4) An=B。称这个公式序列A1，A2, ，An为由公式 1， 2， ，k证明B的证明过程.1， 2， ，k B3/49例 x(P(x)Q(x)(x

2、P(x)xQ(x)证明：(1) x(P(x) Q(x) 假设(2) x P(x) 假设(3) P(e) Q(e) 额外假设(4) P(e) 全称量词消去规则(5) Q(e) (3)(4)分离 (6) x Q(x) 存在量词引入4/49解：(1) x(P(x) Q(x) 假设(2) x P(x) 假设(3) P(e) 全称量词消去规则(4) P(e) Q(e) 额外假设(5) Q(e) (3)(4)分离(6) x Q(x) 存在量词引入规则例 x(P(x)Q(x)(xP(x)xQ(x)5/49例 用假设推理证明下述公式 x(P(x) Q(x) (xP(x) xQ(x)解：(1) x(P(x) Q

3、(x) 前提假设(2) xP(x) 前提假设(3) xQ(x) (1)(2)分离(PQ) PQ6/49例 能不能用假设推理证明下述公式? (xP(x) xQ(x) x(P(x) Q(x)解：(1) xP(x) xQ(x) 前提假设(2) xP(x) 前提假设(3) xQ(x) (1)(2)分离 可以举例说明此公式非重言式 (2)并非是结论的前件.?PQ (PQ) 例 举例说明如下公式非永真 (xP(x) xQ(x) x(P(x) Q(x)解 给定解释: 个体域取 I=1,2 P(x)表示x为偶数 Q(x)表示x为奇数显然, xP(x)=F xQ(x)=F xP(x)xQ(x) =FF=T x(

4、P(x)Q(x) =TF=F 所以，原式= TF=F。此例说明: 尽管 PQ，未必能够得到 (AB)8/49例 xy(A(x)B(y)(xA(x)yB(y)证明：xy(A(x)B(y) 前提xA(x) 前提A(a) 去存在量词A(a)B(y) 去全称量词B(y) 分离(3)(4)yB(y) 全称量词引入9/49例 (xA(x)yB(y)xy(A(x)B(y)证明(反证法)：xA(x)yB(y) 前提xy(A(x)B(y) 后件的否定xy(A(x) B(y) 替换(2)A(a) B(b) 额外假设A(a) 化简(4)B(b) 化简(4)xy( A(x) B(y) 替换(1)A(a) B(b) 去

5、全称量词B(b) 析取三段论显然(6)(9)矛盾，由反证法，结论得证。10/49例 (xA(x)yB(y) xy(A(x)B(y)证明思路：先证 (xA(x)yB(y) xy(A(x)B(y)再证xy(A(x)B(y)(xA(x)yB(y)最后利用公理7 (PQ)(QP)(PQ)即得到完整的证明。对比（求前束范式）：xA(x)yB(y) = xy(A(x)B(y)11/49例 已知知识： (1)桌子上的每一本书均是杰作； (2)写出杰作的人是天才； (3)某个不出名的人写了桌上某本书； 结论：某个不出名的人是天才。解：令 A(e)表示“e为桌上的书”； B(e)表示“e为杰作”； C(e)表示

6、“e为天才”； D(e)表示“e出名”； P(e)表示“e为人”； W(e1，e2)表示“e1 写了 e2”.12/49例 已知知识： (1)桌子上的每一本书均是杰作； (2)写出杰作的人是天才； (3)某个不出名的人写了桌上某本书； 结论：某个不出名的人是天才。(1) x(A(x)B(x)(2) x (P(x) y(B(y) W(x, y)C(x)(3) x (P(x) D(x) y(A(y) W(x，y)x(P(x) D(x) C(x)解：(1) x(A(x)B(x)(2) x (P(x) y(B(y) W(x, y)C(x)(3) x (P(x) D(x) y(A(y) W(x，y)(4

7、) P(a) D(a) y(A(y) W(a，y) 额外假设(5) P(a) D(a) A(b) W(a，b) 额外假设(6) A(b)B(b) 全称量词消去(1)(7) A(b) 化简(5)(8) B(b) 分离(6)(7)(9) x y (P(x) B(y) W(x, y)C(x) 等值替换(2)(17) x(P(x) D(x) C(x) 存在量词引入x (P(x) y(B(y) W(x, y)C(x) =x y(P(x)B(y) W(x，y)C(x)解：(5) P(a) D(a) A(b) W(a，b) 额外假设(6) A(b)B(b) 全称量词消去(1)(7) A(b) 化简(5)(8

8、) B(b) 分离(6)(7)(9) x y (P(x) B(y) W(x, y)C(x) 等值替换(2)(10) y (P(a) B(y) W(a, y)C(a) 全称量词消去(9)(11) (P(a) B(b) W(a,b)C(a) 全称量词消去(10)(12) P(a) W(a，b) 化简(5)(13) P(a) B(b) W(a，b) 合取(b)(12)(14) C(a) 分离(11)(13)(15) P(a) D(a) 化简(5)(16) P(a) D(a) C(a) 合取(14)(15)(17) x(P(x) D(x) C(x) 存在量词引入15/494.3 谓词演算的归结推理系统

9、将前提集S化成子句集，将目标公式的否定(即B)化成子句集，归结若能归结出矛盾，则认为证明完成。1， 2， ，k B前提公式集S目标公式B 1(2(kB)16/49引例(p71) 已知：(1)无论谁能读就有知识；(2)所有的海豚均没有知识；(3)有些海豚有智慧。试证明：(4)一些有智慧的个体不能读。x(R(x) L(x)x(H(x)L(x)x(H(x)I(x)x(I(x)R(x)其中： R(x): x能读； L(x): x有知识； H(x): x是海豚； I(x): x有智慧17/49引例 (p71，提取子句)(1) R(x1) L(x1)(2) H(x2) L(x2)(3) H(a) I(a)

10、(5) I(x3)R(x3)前提： x(R(x) L(x) x(H(x)L(x) x(H(x)I(x)结论的否定 x(I(x)R(x)=x(I(x)R(x)18/49引例 (p71，归结)(1) R(x1) L(x1)(2) H(x2) L(x2)(3) H(a)(4) I(a)(5) I(x3)R(x3)(6) R(a) a/ x3(4)(5)归结(7) L(a) a/ x1(6)(1)归结(8) H(a) a/ x2(7)(2)归结(9) (8)(3)归结注意：归结时使用了未讨论过的置换的概念。19/494.3.1 置换置换项对变量的替换。(1)置换必须处处进行。(2)要求没有变量被含有同

11、一变量的项来代替。 例 已知表达式 P(x) P(f(x)x不能用f(x)替换20/49例 已知表达式 P(x，g(y)，b)，考察置换: P(x，g(a)，b) a/y P(a，g(b)，b) a/x，b/y P(f(y)，g(a)，b) f(y)/x，a/y 一般地，置换可通过有序对的集合t1/v1，t2/v2，tn/vn来表达，其中ti/vi表示变量vi处处以项ti来代替。21/494.3.2 归结反演系统一、谓词演算公式子句的形成二、一般归结三、归结反演系统的应用22/49子句形成的一般步骤:(1)消去蕴含词和等价词(2)否定深入(3)约束变元改名(4)化为前束范式(5)消去存在量词(

12、按Skolem标准形)(6)消去全称量词(直接去掉)(7)化为合取范式(8)消去合取词得子句集，(9)改变变量的名称 (变量符号不重复使用)23/49例 求xP(x)x(A(x)y(B(y)W(x，y)的子句解:(1)消去蕴含词 xP(x)x(A(x)y(B(y)W(x，y)(2)约束变元改名： xP(x)z(A(z)y(B(y)W(z，y)(3)化为前束范式 xzy(P(x)(A(z)(B(y)W(z，y)(4)消去存在量词(按Skolem标准形) z(P(a)(A(z)(B(f(z)W(z，f(z)(5)消去全称量词(直接去掉) P(a)(A(z)(B(f(z)W(z，f(z)(6)利用分

13、配律化为合取范式 P(a)(A(z)B(f(z) (A(z)W(z，f(z)(7)消去合取词得子句集 P(a), A(z)B(f(z), A(z)W(z，f(z)(8)改变变量的名称： P(a), A(z1)B(f(z1), A(z2)W(z2，f(z2)关于改变变量名的说明:x(A(x) B(x)= xA(x) yB(y) 25/49一般归结寻找一个置换使得子句上含有互补的文字对(如P和P) 。例 设有两个子句 P(x，g(a)Q(y), P(z，g(a)Q(z) 可得若干归结式如下： Q(y) Q(z) z/x Q(y) Q(x) x/z P(x，g(a)P(z，g(a) z/y 26/4

14、9归结反演系统(Refutation)要证明定理 A1，A2，An B，只要：将 A1，A2，An, B分别化为子句集；归结出空子句,即证明其不可满足。第步等价于将A1A2AnB化为子句集27/49例 xy(A(x)B(y)(xA(x)yB(y)证明：分别从前件xy(A(x)B(y)、xA(x)以及后件的否定式yB(y)= yB(y)中提取子句如下： A(x)B(y), A(a), B(b)。 归结过程如下：A(x)B(y) 前提A(a) 前提B(b) 结论的否定B(y) a/x(1)(2)口 b/y(3)(4)28/49例 (xA(x)yB(y)xy(A(x)B(y)证明：分别从前件xA(x

15、)yB(y)= xy(A(x)B(y) 以及后件的否定式xy(A(x)B(y) =xy(A(x)B(y)中提取子句如下： A(x)B(y), A(a), B(b)。 归结过程如下：A(x)B(y) 前提A(a) 结论的否定B(b) 结论的否定B(y) a/x(1)(2)口 b/y(3)(4)例 习题4.6(3): xy(P(x)Q(y) (xP(x)yQ(y)归结推理证明思路一：利用 (AB)=(AB) (AB)可以得到5个子句（见下页）：P(x)Q(y)P(x1)Q(y1)P(a)P(a1)P(a)Q(b1)Q(b)P(a1)Q(b)Q(b1)使用假设推理法可以证之，见第10页。AB=xy(

16、P(x)Q(y)(uP(u)vQ(v)=xyuv(P(x)Q(y)(P(u)Q(v)=xyuv(P(x)Q(y)(P(u)Q(v)=xyuv(P(x)Q(y)P(u)Q(v)AB=xy(P(x)Q(y)(uP(u)vQ(v)= xy(P(x)Q(y) uv(P(u)Q(v) = xyuv(P(x)Q(y) (P(u)Q(v)= (P(a)Q(b) (P(a1)Q(b1)= (P(a)P(a1)(P(a)Q(b1)(P(a1)Q(b) (Q(b)Q(b1)P(x)Q(y)P(x1)Q(y1)P(a)P(a1)P(a)Q(b1)Q(b)P(a1)Q(b)Q(b1)P(a)Q(y)P(x1)Q(y1

17、) a1/x(1)(2)P(a)Q(y)Q(y1) a1/x1(6)(2)P(a)Q(y1) b1/y(7)(3)P(a) b1/y1(8)(3)Q(b) Q(y)P(x1)Q(y1) a1/x(1)(4)Q(b) Q(y)Q(y1) a1/x1(10)(5)Q(b) Q(y1) b1/y(11)(4)Q(b) b1/y1(12)(5)Q(y)P(x1)Q(y1) a/x(1)(9)Q(y)Q(y1) a/x1(14)(9)Q(y1) b/y(15)(13)口 b/y1(16)(13)例 习题4.6(3): xy(P(x)Q(y) (xP(x)yQ(y)归结推理证明思路二：利用 (AB)=(A

18、B)(AB)可以得到9个子句（见下页）：(4) Q(b)P(a1)(5) Q(b)Q(b1)(6) Q(b)P(x2)Q(y2) (7) P(x3)Q(y3)P(a1)(8) P(x4)Q(y4)Q(b1)(9) P(x5)Q(y5)P(x6)Q(y6)(1) P(a)P(a1)(2) P(a)Q(b1)(3) P(a)P(x1) Q(y1)AB=xy(P(x)Q(y)(uP(u)vQ(v) = xy(P(x)Q(y) uv(P(u)Q(v) =P(a)Q(b)(P(u)Q(v)AB=BA=(uP(u)vQ(v)xy(P(x)Q(y) =uv(P(u)Q(v)xy(P(x)Q(y) =P(a1

19、)Q(b1)(P(x)Q(y)(AB)=(AB)(AB)=(P(a)Q(b)(P(u)Q(v)(P(a1)Q(b1)(P(x)Q(y)=(P(a)P(a1) (P(a) Q(b1)(P(a)P(x) Q(y) (Q(b)P(a1) (Q(b)Q(b1)(Q(b)P(x)Q(y) (P(u)Q(v)P(a1) (P(u)Q(v)Q(b1) (P(u)Q(v)P(x)Q(y)(4) Q(b)P(a1)(5) Q(b)Q(b1)(6) Q(b)P(x2)Q(y2) (7) P(x3)Q(y3)P(a1)(8) P(x4)Q(y4)Q(b1)(9) P(x5)Q(y5)P(x6)Q(y6)(1) P(

20、a)P(a1)(2) P(a)Q(b1)(3) P(a)P(x1) Q(y1)(10) P(a)Q(y1) a1/x1(1)(3)(11) P(a) b1/y1(2)(10)(12) Q(b)Q(y1) a1/x2(4)(6)(13) Q(b) b1/y2(5)(12)(14) Q(y5)P(x6)Q(y6) a/x5(9)(11)(15) P(x6)Q(y6) b/y5(13)(14)(16) Q(y6) a/x6(9)(15)(17) 口 b/y6(13)(16)35/49例 已知知识： (1)每个作家均写过作品； (2)有些作家没写过小说；结论：有些作品不是小说。 x(A(x)y(B(y

21、)W(x，y) x(A(x)y(N(y)W(x，y) x(B(x)N(x)证明：令 A(e)表示“e为作家”； B(e)表示“e为作品”； N(e)表示“e为小说”； W(e1，e2)表示“e1 写了 e2”36/49求子句: 每个作家均写过作品 (1) x(A(x)y(B(y)W(x，y) ) = x(A(x) y(B(y)W(x，y) = x y (A(x) (B(y)W(x，y) = x (A(x) (B(f(x)W(x，f(x) = A(x) (B(f(x)W(x，f(x) = (A(x) B(f(x) (A(x) W(x，f(x) 得到子句： A(x1)B(f(x1)，A(x2)W(

22、x2，f(x2) 37/49求子句: 有些作家没写过小说(2) x(A(x)y(N(y)W(x，y) = x(A(x)y(N(y) W(x，y) = x y (A(x) (N(y) W(x，y) = y (A(a) (N(y) W(a，y) = A(a) (N(y) W(a，y)得到子句： A(a), N(y) W(a，y)38/49求子句:有些作品不是小说 x(B(x)N(x) 否定结论得到： x(B(x)N(x) = x(B(x)N(x) = B(x)N(x) 得到子句： B(x)N(x)(1) A(x1)B(f(x1)(2) A(x2)W(x2，f(x2)(3) A(a)(4) N(y)

23、W(a，y)(5) B(x)N(x)(6) A(x1) N(f(x1) f(x1)/x (5)(1)归结(7) N(f(a) a/x1 (6)(3)归结(8) W(a，f(a) f(a)/y (7)(4)归结 (9) A(a) a/x2 (8)(2)归结(10) 口 (9)(3)归结40/49例任何人如果喜欢步行，他就不喜欢乘汽车；每个人或者喜欢乘汽车，或者喜欢骑自行车；有的人不喜欢骑自行车，因而有的人不爱步行。试用归结原理证明之。证明：令 P(e)表示“e为人”； W(e)表示“e喜欢步行”； D(e)表示“e喜欢乘汽车”； R(e)表示“e喜欢骑自行车”41/49证明(续)则已知知识可以翻

24、译为：（1） x(P(x) (W(x) D(x)（2） x(P(x) (D(x) R(x)（3） x(P(x) R(x) 结论为： x(P(x) W(x) )结论的否定为： x( P(x) W(x)(1) P(x1)W(x1) D(x1)(2) P(x2)D(x2) R(x2)(3) P(a)(4) R(a)(5) P(x)W(x)(6) W(a) D(a) a/x1 (3)(1)归结(7) P(a)D(a) a/x2 (4)(2)归结(8) P(a) D(a) a/y (5)(6)归结 (9) P(a) (8)(7)归结(10) 口 (9)(3)归结43/49例 四对夫妇中，谁是男？谁是女？

25、王结婚时，周送了礼；周和钱是同一排球队的队员；李的爱人是陈的爱人的表哥；陈夫妇与邻居吵架时，徐、周、吴的爱人都去助战；李、徐、周结婚前住一间宿舍。试用归结法求王、周、钱、陈、李、徐、吴、孙八人谁是男？谁是女？谁和谁是夫妇？ 女(李)女(徐)=(女(李)女(徐) (女(徐)女(李)女(徐)女(周)=(女(徐)女(周) (女(周)女(周徐)女(李) 女(周)女(钱)=(女(周)女(钱) (女(钱)女(周)44/49例 四对夫妇中，谁和谁是夫妇？ 王结婚时，周送了礼；周和钱是同一排球队的队员；李的爱人是陈的爱人的表哥；陈夫妇与邻居吵架时，徐、周、吴的爱人都去助战；李、徐、周结婚前住一间宿舍。试用归结法求王、周、钱、陈、李、徐、吴、孙八人谁是男？谁是女？谁和谁是夫妇？ 婚(徐，陈)婚(周，陈)婚(徐，吴)婚(周，吴)婚(李，陈)婚(周，