離散數(shù)學(xué)-歸結(jié)反演系統(tǒng)

1、1/601/60離 散 數(shù) 學(xué) Discrete Mathematics計算機科學(xué)與工程學(xué)院 金 忠http:/patternrecognition.asia/dm2/49回顧：謂詞演算的假設(shè)推理過程定義: 如果能夠作出一系列合式公式序列 A1，A2, A3, ，An，它們滿足下列性質(zhì)：(1)諸Ai或為公理/定理之一；(2) 或為公式1, 2, ,k之一，每個i稱為假設(shè)；(3) 或由前面的若干個Ag、Ah利用分離規(guī)則、全n規(guī)則、存n規(guī)則等而得；(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) 假設(shè)(2) x P(x) 假設(shè)(3) P(e) Q(e) 額外假設(shè)(4) P(e) 全稱量詞消去規(guī)則(5) Q(e) (3)(4)分離 (6) x Q(x) 存在量詞引入4/49解：(1) x(P(x) Q(x) 假設(shè)(2) x P(x) 假設(shè)(3) P(e) 全稱量詞消去規(guī)則(4) P(e) Q(e) 額外假設(shè)(5) Q(e) (3)(4)分離(6) x Q(x) 存在量詞引入規(guī)則例 x(P(x)Q(x)(xP(x)xQ(x)5/49例 用假設(shè)推理證明下述公式 x(P(x) Q(x) (xP(x) xQ(x)解：(1) x(P(x) Q

3、(x) 前提假設(shè)(2) xP(x) 前提假設(shè)(3) xQ(x) (1)(2)分離(PQ) PQ6/49例 能不能用假設(shè)推理證明下述公式? (xP(x) xQ(x) x(P(x) Q(x)解：(1) xP(x) xQ(x) 前提假設(shè)(2) xP(x) 前提假設(shè)(3) xQ(x) (1)(2)分離 可以舉例說明此公式非重言式 (2)并非是結(jié)論的前件.?PQ (PQ) 例 舉例說明如下公式非永真 (xP(x) xQ(x) x(P(x) Q(x)解 給定解釋: 個體域取 I=1,2 P(x)表示x為偶數(shù) Q(x)表示x為奇數(shù)顯然, 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) 額外假設(shè)A(a) 化簡(4)B(b) 化簡(4)xy( A(x) B(y) 替換(1)A(a) B(b) 去

5、全稱量詞B(b) 析取三段論顯然(6)(9)矛盾，由反證法，結(jié)論得證。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)某個不出名的人寫了桌上某本書； 結(jié)論：某個不出名的人是天才。解：令 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)某個不出名的人寫了桌上某本書； 結(jié)論：某個不出名的人是天才。(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) 額外假設(shè)(5) P(a) D(a) A(b) W(a，b) 額外假設(shè)(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) 額外假設(shè)(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 謂詞演算的歸結(jié)推理系統(tǒng)

9、將前提集S化成子句集，將目標(biāo)公式的否定(即B)化成子句集，歸結(jié)若能歸結(jié)出矛盾，則認(rèn)為證明完成。1， 2， ，k B前提公式集S目標(biāo)公式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)結(jié)論的否定 x(I(x)R(x)=x(I(x)R(x)18/49引例 (p71，歸結(jié))(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)歸結(jié)(7) L(a) a/ x1(6)(1)歸結(jié)(8) H(a) a/ x2(7)(2)歸結(jié)(9) (8)(3)歸結(jié)注意：歸結(jié)時使用了未討論過的置換的概念。19/494.3.1 置換置換項對變量的替換。(1)置換必須處處進行。(2)要求沒有變量被含有同

11、一變量的項來代替。 例 已知表達(dá)式 P(x) P(f(x)x不能用f(x)替換20/49例 已知表達(dá)式 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 一般地，置換可通過有序?qū)Φ募蟭1/v1，t2/v2，tn/vn來表達(dá)，其中ti/vi表示變量vi處處以項ti來代替。21/494.3.2 歸結(jié)反演系統(tǒng)一、謂詞演算公式子句的形成二、一般歸結(jié)三、歸結(jié)反演系統(tǒng)的應(yīng)用22/49子句形成的一般步驟:(1)消去蘊含詞和等價詞(2)否定深入(3)約束變元改名(4)化為前束范式(5)消去存在量詞(

12、按Skolem標(biāo)準(zhǔn)形)(6)消去全稱量詞(直接去掉)(7)化為合取范式(8)消去合取詞得子句集，(9)改變變量的名稱 (變量符號不重復(fù)使用)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標(biāo)準(zhǔn)形) 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)關(guān)于改變變量名的說明:x(A(x) B(x)= xA(x) yB(y) 25/49一般歸結(jié)尋找一個置換使得子句上含有互補的文字對(如P和P) 。例 設(shè)有兩個子句 P(x，g(a)Q(y), P(z，g(a)Q(z) 可得若干歸結(jié)式如下： 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歸結(jié)反演系統(tǒng)(Refutation)要證明定理 A1，A2，An B，只要：將 A1，A2，An, B分別化為子句集；歸結(jié)出空子句,即證明其不可滿足。第步等價于將A1A2AnB化為子句集27/49例 xy(A(x)B(y)(xA(x)yB(y)證明：分別從前件xy(A(x)B(y)、xA(x)以及后件的否定式y(tǒng)B(y)= yB(y)中提取子句如下： A(x)B(y), A(a), B(b)。 歸結(jié)過程如下：A(x)B(y) 前提A(a) 前提B(b) 結(jié)論的否定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)。 歸結(jié)過程如下：A(x)B(y) 前提A(a) 結(jié)論的否定B(b) 結(jié)論的否定B(y) a/x(1)(2)口 b/y(3)(4)例 習(xí)題4.6(3): xy(P(x)Q(y) (xP(x)yQ(y)歸結(jié)推理證明思路一：利用 (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)使用假設(shè)推理法可以證之，見第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)例 習(xí)題4.6(3): xy(P(x)Q(y) (xP(x)yQ(y)歸結(jié)推理證明思路二：利用 (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)有些作家沒寫過小說；結(jié)論：有些作品不是小說。 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) 否定結(jié)論得到： 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)歸結(jié)(7) N(f(a) a/x1 (6)(3)歸結(jié)(8) W(a，f(a) f(a)/y (7)(4)歸結(jié) (9) A(a) a/x2 (8)(2)歸結(jié)(10) 口 (9)(3)歸結(jié)40/49例任何人如果喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車，或者喜歡騎自行車；有的人不喜歡騎自行車，因而有的人不愛步行。試用歸結(jié)原理證明之。證明：令 P(e)表示“e為人”； W(e)表示“e喜歡步行”； D(e)表示“e喜歡乘汽車”； R(e)表示“e喜歡騎自行車”41/49證明(續(xù))則已知知識可以翻

24、譯為：（1） x(P(x) (W(x) D(x)（2） x(P(x) (D(x) R(x)（3） x(P(x) R(x) 結(jié)論為： x(P(x) W(x) )結(jié)論的否定為： 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)歸結(jié)(7) P(a)D(a) a/x2 (4)(2)歸結(jié)(8) P(a) D(a) a/y (5)(6)歸結(jié) (9) P(a) (8)(7)歸結(jié)(10) 口 (9)(3)歸結(jié)43/49例 四對夫婦中，誰是男？誰是女？

25、王結(jié)婚時，周送了禮；周和錢是同一排球隊的隊員；李的愛人是陳的愛人的表哥；陳夫婦與鄰居吵架時，徐、周、吳的愛人都去助戰(zhàn)；李、徐、周結(jié)婚前住一間宿舍。試用歸結(jié)法求王、周、錢、陳、李、徐、吳、孫八人誰是男？誰是女？誰和誰是夫婦？ 女(李)女(徐)=(女(李)女(徐) (女(徐)女(李)女(徐)女(周)=(女(徐)女(周) (女(周)女(周徐)女(李) 女(周)女(錢)=(女(周)女(錢) (女(錢)女(周)44/49例 四對夫婦中，誰和誰是夫婦？ 王結(jié)婚時，周送了禮；周和錢是同一排球隊的隊員；李的愛人是陳的愛人的表哥；陳夫婦與鄰居吵架時，徐、周、吳的愛人都去助戰(zhàn)；李、徐、周結(jié)婚前住一間宿舍。試用歸結(jié)法求王、周、錢、陳、李、徐、吳、孫八人誰是男？誰是女？誰和誰是夫婦？ 婚(徐，陳)婚(周，陳)婚(徐，吳)婚(周，吳)婚(李，陳)婚(周，