《離散數(shù)學(xué)第四章謂詞演算的推理理論-歸結(jié)推理系統(tǒng).ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第四章謂詞演算的推理理論-歸結(jié)推理系統(tǒng).ppt（50頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、第四章 謂詞演算的推理理論,4.1 謂詞演算的永真推理系統(tǒng) 4.2謂詞演算的假設(shè)推理系統(tǒng) 4.3謂詞演算的歸結(jié)推理系統(tǒng) 4.3.1 置換 4.2.2 歸結(jié)反演系統(tǒng) 4.3.3 霍恩子句邏輯程序,,4.3 謂詞演算的歸結(jié)推理系統(tǒng),問題：從公式集S出發(fā)，證明目標(biāo)公式T。 在歸結(jié)系統(tǒng)中: 首先否定目標(biāo)公式， 然后將這個(gè)公式加到公式集S中， 再將該公式化成子句集， 若能歸結(jié)成空子句(用表示)， 則認(rèn)為證明了該公式T。,引例(p45),設(shè)有語句串及它的符號表示如下： (1)無論誰能讀就有知識；x(R(x) L(x)) (2)所有的海豚均沒有知識；x(H(x) L(x)) (3)有些海豚有智慧。x(
2、H(x)I(x)) 從這些語句出發(fā)，證明語句： (4)一些有智慧的個(gè)體不能讀。x(I(x)R(x)),引例 (p45，提取子句),對應(yīng)語句(1)至(3)的子句集為： (1) R(x1) L(x1) (2) H(x2) L(x2) (3) H(a) (4) I(a) 其中子句(3)(4)為對(3)式SKOLEM化而得，a為SKOLEM常量。 要證明的定理的否定式為： x(I(x)R(x)), 即 x(I(x)R(x)) 化為子句形式為(5)： (5) I(x3)R(x3),引例 (p45，歸結(jié)),(1) R(x1) L(x1) (2) H(x2) L(x2) (3) H(a) (4) I(a
3、) (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é)時(shí)使用了未討論過的置換的概念。,4.3.1 置換,項(xiàng)對變量的替換。 置換準(zhǔn)則為： (1)置換必須處處進(jìn)行。 (2)要求沒有變量被含有同一變量的項(xiàng)來代替。 如表達(dá)式P(x,g(x),b)中的x不能用含有x的項(xiàng)f(x)來置換，即P(f(x),g(f(x)),b)是錯(cuò)誤的置換。,例 已知表達(dá)式 P(x，g(
4、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ū)Φ募?t1/v1，t2/v2，，tn/vn 來表達(dá)，其中ti/vi表示變量vi處處以項(xiàng)ti來代替。,4.3.2 歸結(jié)反演系統(tǒng),一、謂詞演算公式子句的形成 二、一般歸結(jié) 三、歸結(jié)反演算系統(tǒng)的應(yīng)用,一、謂詞演算公式子句的形成,一般步驟: (1)消去蘊(yùn)含詞和等價(jià)詞 (2)否定深入 (3)約束變元改名 (4)化為前束范式 (5)消去存在量詞(按Skolem標(biāo)準(zhǔn)形) (6)消去全稱量詞(直接去掉) (
5、7)化為合取范式 (8)消去合取詞得子句集， (9)改變變量的名稱 (變量符號不重復(fù)使用),例(p46-47) xP(x)x(A(x)y(B(y)W(x，y))),解: (1)消去蘊(yùn)含詞 xP(x)x(A(x)y(B(y)W(x，y))) (2)約束變元改名： 利用改名方法對上式施行改名，以保證每一個(gè)量詞約束的變元不同名。 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))))),例 (p47),(
6、5)消去全稱量詞(直接去掉) 原式 P(a)(A(z)(B(f(z))W(z，f(z)))) (6)利用分配律化為合取范式 原式 P(a)(A(z)B(f(z))) (A(z)W(z，f(z))) (7)消去合取詞得子句集 此時(shí)公式中只含有一些文字的析取 P(a), A(z)B(f(z)), A(z)W(z，f(z)) (8)改變變量的名稱： 改名使得每個(gè)變量符號不出現(xiàn)在一個(gè)以上的子句中 P(a), A(z1)B(f(z1)), A(z2)W(z2，f(z2)),二、一般歸結(jié),只需尋找一個(gè)置換，把它們作用到母體子句上使它們含有互補(bǔ)的文字對(如P和P) 。,例 設(shè)有 P(x，g
7、(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,,歸結(jié)反演系統(tǒng)產(chǎn)生式系統(tǒng),子句集看作為一個(gè)綜合數(shù)據(jù)庫， 而規(guī)則表就是歸結(jié)，表中的規(guī)則用到數(shù)據(jù)庫中的子句對，產(chǎn)生一個(gè)新的子句，把新子句加入數(shù)據(jù)庫中產(chǎn)生新的數(shù)據(jù)庫，形成新的歸結(jié)，重復(fù)此過程，觀察數(shù)據(jù)庫中是否含有空子句。,例 (p47)已知知識：,(1)每個(gè)作家均寫過作品； (2)有些作家沒寫過小說； 結(jié)論：有些作品不是小說。,證明：令 A(e)表示“e為作家
8、”； B(e)表示“e為作品”； N(e)表示“e為小說”； W(e1，e2)表示“e1 寫了 e2” 知識可以符號化如下： (1) x(A(x)y(B(y)W(x，y))) (2) x(A(x)y(N(y)W(x，y))),例 (p47, 求子句),(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
9、(f(x))) (A(x) W(x，f(x))) 得到子句： A(x1)B(f(x1))，A(x2)W(x2，f(x2)),例 (p47,續(xù)),(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),例 (p47,續(xù)),要證明的結(jié)論為：有些作品不是小說。 x(B(x)N(x)) 否定結(jié)論得到： x(B(x)N(x))
10、 = x(B(x)N(x)) B(x)N(x) 得到子句： B(x)N(x),例 (p47, 歸結(jié)),(1) A(x1)B(f(x1)) (2) A(x2)W(x2，f(x2)) (3) A(a) (4) N(y)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) 口
11、 (9)(3)歸結(jié),補(bǔ)充習(xí)題,任何人如果喜歡步行，他就不喜歡乘汽車；每個(gè)人或者喜歡乘汽車，或者喜歡騎自行車；有的人不喜歡騎自行車，因而有的人不愛步行。試用歸結(jié)原理證明之。,證明：令 P(e)表示“e為人”； W(e)表示“e喜歡步行”； D(e)表示“e喜歡乘汽車”； R(e)表示“e喜歡騎自行車”,證明(續(xù)),則已知知識可以翻譯為： （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)
12、),證明(續(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é),例 用歸結(jié)方法證明下列公式,x(P(f(x))(P(f(a))P(x))),證: 目標(biāo)的否定為
13、 x(P(f(x))(P(f(a)) P(x))) = x (P(f(x))(P(f(a)) P(x))) = x (P(f(x)) ( P(f(a)) P(x))) 子句集為 (1) P(f(x1)) (2) P(f(a)) P(x2) (3) P(x2) a/x1 (1)(2)歸結(jié) (4)口 f(x1)/x2(1)(3)歸結(jié),直觀解釋: 顯然，如果存在x, 使得P(f(x))為假，則公式為真。反之，如果對于任意t, P(f(t))皆為真，則取x=f(t)即可。,,三、歸結(jié)反演算系統(tǒng)的應(yīng)用,在人工智能領(lǐng)域中的規(guī)劃生成問題。,例
14、(p48)給機(jī)器人r 編制一程序，使它能夠登上一只椅子c以取下掛在房頂?shù)南憬禸。,4.3.3 霍恩子句邏輯程序,一、子句的蘊(yùn)含表示形式 二、霍恩子句邏輯程序,,超邏輯的控制信息,許多人工智能系統(tǒng)中使用的知識是由一般的蘊(yùn)含表達(dá)式來表示的。如果把蘊(yùn)含式 (PQ)R 化為等價(jià)的析取式 P Q R ， 往往會丟失可能包含在蘊(yùn)含式中的重要的超邏輯的控制信息。,基于規(guī)則的演繹系統(tǒng),將知識分為兩類：,一類是規(guī)則，其由蘊(yùn)含式表示，它表達(dá)了有關(guān)領(lǐng)域的一般知識，且可作為產(chǎn)生式規(guī)則來使用； 另一類是事實(shí)，其由不包含蘊(yùn)含式的陳述組成，它們用來表達(dá)某一領(lǐng)域?qū)ｉT的知識。,基于規(guī)則的演繹系統(tǒng)(產(chǎn)生式系統(tǒng))根據(jù)這些事實(shí)和規(guī)則
15、來證明目標(biāo)公式，這種推理強(qiáng)調(diào)使用規(guī)則進(jìn)行演繹，直觀易于理解。,正向演繹系統(tǒng)、逆向演繹系統(tǒng),事實(shí)表達(dá)式,目標(biāo)表達(dá)式,推理,事實(shí)表達(dá)式,目標(biāo)表達(dá)式,推理,,,關(guān)于規(guī)則的約定,約定作為規(guī)則的一些公式限制為如下形式的公式： WL 這些產(chǎn)生式規(guī)則和事實(shí)應(yīng)滿足下列條件： (1)L是單文字（原子公式或原子公式的否定）， 事實(shí)上即使L不是單文字，也可把該蘊(yùn)含式化為多重規(guī)則。 如：W(L1L2)等價(jià)于規(guī)則對WL1和WL2； (2)W是任一公式(假設(shè)是與或形公式,本書限為合取式)。,一、子句的蘊(yùn)含表示形式,一個(gè)子句是若干文字的析取，一般地， C = P1P2PnQ1Q2Qm 其中，Pi和Qi為謂詞，變
16、元被省略。 可以表示為： (P1P2Pn)(Q1Q2Qm) 如果約定蘊(yùn)含前件的文字之間恒為合取，而蘊(yùn)含后件的文字之間恒為析取，那么上式可改寫為如下形式： P1，P2，，PnQ1，Q2，，Qm,子句的性質(zhì),(1) Q1，Q2，，Qm，等價(jià)于Q1Q2Qm； 而 P1，P2，，Pn等價(jià)于P1P2Pn。 當(dāng)m=n=0時(shí)，表示空子句。 (2)當(dāng)子句C： Q1，Q2，，Qm P1，P2，，Pn 和子句C ： Q1 ，Q2 ，，Qs P1 ，P2 ，，Pt 中有Qi和Pj ，(或Pi和Qj )相同，則C和C 可進(jìn)行歸結(jié)。 (3)要證明定理 A1A2AnB， 只要將 A1A2AnB 化
17、為子句集，并證明其不可滿足，即用以上方式歸結(jié)出空子句。,二、霍恩子句邏輯程序,定義1：子句 L1L2Ln 中，如果至多只含有一個(gè)正文字，那么該子句稱為霍恩子句。,霍恩子句PQ1Q2Qn通常表示為： PQ1，Q2，，Qn 霍恩子句必為下列四種形式之一： (1)PQ1，Q2，，Qn n0 (2)P n=0 (3)Q1，Q2，，Qn n0 (4)口(空子句) 上式n=0,P Q1，Q2，，Qn n0 (2) P n=0(3
18、) Q1，Q2，，Qn n0(4) 口 上式n=0,形如PQ1，Q2，，Qn的霍恩子句稱為一個(gè)過程，P稱為過程名，Q1，Q2，，Qn稱為過程體，諸Qi解釋為過程調(diào)用； 形如P的霍恩子句稱為一個(gè)事實(shí)； 形如Q1，Q2，，Qn的霍恩子句稱為目標(biāo)，目標(biāo)全部由過程調(diào)用所組成，常用來表示一個(gè)詢問。 形如口(空子句)稱為停機(jī)語句，表示執(zhí)行成功。,霍恩子句邏輯,定義2：霍恩子句邏輯就是由霍恩子句構(gòu)成的一階謂詞演算系統(tǒng)的子系統(tǒng)。,定義3：霍恩子句邏輯程序就是指由被稱為過程、事實(shí)和目標(biāo)的霍恩子句所組成的集合。,霍恩邏輯程序的執(zhí)行算法,(1) 給定一個(gè)霍恩子
19、句邏輯程序，它由目標(biāo)中的一個(gè)過程調(diào)用與事實(shí)或與一個(gè)過程的過程名匹配啟動，當(dāng)匹配成功后，形成新的目標(biāo)，完成一次匹配。 (2) 再由目標(biāo)中的另一個(gè)過程調(diào)用重新啟動程序，直至目標(biāo)中全部過程調(diào)用匹配成功(即歸結(jié)為空子句)，或者某一過程調(diào)用不能與事實(shí)或過程名相匹配。,兩個(gè)霍恩子句的歸結(jié)是一個(gè)霍恩子句。在自動定理證明中，這能導(dǎo)致子句的在計(jì)算機(jī)上表示得更加高效。實(shí)際上，Prolog 就是完全在霍恩子句上構(gòu)造的編程語言。,例 已知前提 (1) TOM在何處， MARY在何處 (2) MARY在何處，她的COMPUTER在何處 (3) TOM在圖書館 詢問“MARY的COMPUTER是否在圖書館？”。 試給出
20、它的證明程序。,解：霍恩子句為 (1) At(MARY,x) At(TOM,x) 過程 (2) At(COMPUTER,y) At(MARY,y) 過程 (3) At(TOM, Library) 事實(shí) (4) At(COMPUTER, Library) 目標(biāo),,例 MARY的COMPUTER是否在圖書館？,解：霍恩子句邏輯程序?yàn)? (1) At(MARY,x) At(TOM,x) 過程 (2) At(COMPUTER,y) At(MARY,y) 過程 (3) At(TOM, Library) 事實(shí) (4) At(
21、COMPUTER, Library) 目標(biāo) (5) At(MARY, Library) Library/y (2)(4)匹配 (6) At(TOM, Library) ) Library/x (1)(5)匹配 (7) 口 (3)(6)匹配 此程序證明了MARY的COMPUTER在圖書館。,,例 所有羊都吃草,所有死羊都不吃草. 所以,所有死羊都不是羊.,解: 知識翻譯為 x(羊(x) 吃草(x)) x(死羊(x) 吃草(x)) x(死羊(x) 羊(x)), 其否定為 x(死羊(x)羊(x)) 霍恩子句邏輯程序及執(zhí)行過程如下： (1) 吃草(x)羊(x
22、) 過程 (2) 死羊(x1), 吃草(x1) 目標(biāo) (3) 死羊(a) 事實(shí) (4) 羊(a) 事實(shí) (5) 死羊(x), 羊(x) x/x1(2)(1)歸結(jié) (6) 羊(a) a/x(5)(3)歸結(jié) (7) 口 (6)(4)歸結(jié),例 (原題p44) 已知知識： (1)有些病人喜歡所有的醫(yī)生； (2)所有的病人均不喜歡庸醫(yī)；試證明結(jié)論：所有的醫(yī)生均不是庸醫(yī)。,證明：已知知識翻譯為： (1)
23、 x(P(x)y(D(y)L(x，y))) (2) x(P(x)y(Q(y) L(x，y))) 結(jié)論翻譯為： x(D(x) Q(x)),結(jié)論的否定為: x(D(x) Q(x)),霍恩子句邏輯程序及執(zhí)行過程如下： (1) P(a) 事實(shí) (2) L(a,y) D(y) 過程 (3) P(x1), Q(y1), L(x1,y1） 目標(biāo) (4) D(b) 事實(shí) (5) Q(b) 事實(shí) (6) Q(y1), L(a，y1) a/x1(3)(1)歸結(jié) (
24、7) Q(y)， D(y) y/y1(6)(2)歸結(jié) (8) Q(b) b/y(7)(4)歸結(jié) (9) 口 (8)(5)歸結(jié),例 (p50-51) 已知知識： (1)桌子上的每一本書均是杰作； (2)寫出杰作的人是天才； (3)某個(gè)不出名的人寫了桌上某本書； 結(jié)論：某個(gè)不出名的人是天才。,解：令 A(e)表示“e為桌上的書”； B(e)表示“e為杰作”； C(e)表示“e為天才”； D(e)表示“e出名”； P(e)表示“e為人”； W(e1，e2)表示“e1 寫了 e2”.,例 (續(xù)，p51),
25、(1)x(A(x)B(x)) (2)x y((P(x)B(y) W(x，y))C(x)) (P(x)B(y) W(x，y))C(x) (3)xy(P(x) A(y) D(x) W(x，y)) P(a) A(b) D(a) W(a，b) 結(jié)論：x(P(x) D(x) C(x)),否定結(jié)論得到 x(P(x) D(x) C(x)) = x ( P(x) D(x) C(x)),解：,(7)D(x3) P(x3)，C(x3) 過程 (8) P(a)，C(a) a/x3(5)(7)歸結(jié) (9) C(a) (8)(3)歸結(jié) (10) P(a),B(y), W(a，
26、y) a/x2(9)(2)歸結(jié) (11) B(y)， W(a，y) (10)(3)歸結(jié) (12) A(y)，W(a，y) y/x1(11)(1)歸結(jié) (13) W(a，b) b/y(12)(4)歸結(jié) (14)口 (13)(6)歸結(jié),(1)B(x1)A(x1) 過程 (2)C(x2) P(x2)，B(y)， W(x2，y) 過程 (3)P(a) 事實(shí) (4)A(b) 事實(shí) (5) D(a) 目標(biāo) (6)W(a，b) 事實(shí),例 已知知識如下： (1)每個(gè)程序員均寫過
27、程序； (2)病毒是一種程序 (3)有些程序員沒寫過病毒； 結(jié)論：有些程序不是病毒。 試用霍恩子句邏輯程序證明之。,證明： 令 P(e)表示 e為程序員； A(e)表示 e為程序； B(e)表示 e為病毒； W(e1,e2)表示 e1寫了 e2.,例 證明（續(xù)）,則已知知識可以翻譯為： （1） x(P(x) y(A(y) W(x,y))) x y (P(x) (A(y) W(x,y))) （2） x(B(x) A(x)) （3） x(P(x) y(B(y) W(x,y))) 結(jié)論為： x(A(x) B(x)) 結(jié)論的否定為： x( A(x) B(x)) = x(A(x) B
28、(x)),例 證明（續(xù)）,(1) A(f(x1)) P(x1) 過程 (2) W(x2, f(x2)) P(x2) 過程 (3) A(x3) B(x3) 過程 (4) P(a) 事實(shí) (5) B(y), W(a, y) 目標(biāo) (6) B(x4) A(x4) 過程 (7) A(y), W(a, y) y/x4(5)(6)歸結(jié) (8) P(x1), W(a, f(x1)) f(x1)/y(7)(1)歸結(jié) (9) W(a, f(a)) a/x1 (8)(4)歸結(jié) (10)
29、P(a) a/x2 (9)(2)歸結(jié) (11) 口 (4)(10)歸結(jié),補(bǔ)充習(xí)題,乒乓球隊(duì)隊(duì)員都是優(yōu)秀的天才,有些乒乓球隊(duì)隊(duì)員參加奧運(yùn)會, 所以有些乒乓球隊(duì)隊(duì)員是天才, 且參加奧運(yùn)會。試用霍恩子句邏輯程序證明之。,證明： 令 P(e)表示 e為乒乓球隊(duì)隊(duì)員； E(e)表示 e是優(yōu)秀的； G(e)表示 e為天才； O(e)表示 e參加奧運(yùn)會.,證明(續(xù)),則已知知識可以翻譯為： （1） x(P(x) (E(x) G(x))) （2） x(P(x) O(x)) 結(jié)論為： x(P(x) G(x) O(x)) 結(jié)論的否定為： x( P(x) G(x
30、) O(x)),證明(續(xù)),(1) E(x1) P(x1) 過程 (2) G(x2) P(x2) 過程 (3) P(a) 事實(shí) (4) O(a) 事實(shí) (5) P(x), G(x), O(x) 目標(biāo) (6) G(a), O(a) a/x(5)(3)歸結(jié) (7) O(a), P(a) a/x2(6)(2)歸結(jié) (8) P(a) (7)(4)歸結(jié) (9) 口 (4)(10)歸結(jié),作業(yè),4.3 指出下列推理過程的錯(cuò)誤所在 4.4 用假設(shè)推理證明下列公式 (1) x(P(x)Q(x)) ((xQ(x)xR(x))(x P(x) xR(x) )) 4.6 用歸結(jié)方法證明下列公式 (1) 4.7,第四章 謂詞演算的推理理論,4.1 謂詞演算的永真推理系統(tǒng) 4.2謂詞演算的假設(shè)推理系統(tǒng) 4.3謂詞演算的歸結(jié)推理系統(tǒng) 4.3.1 置換 4.2.2 歸結(jié)反演系統(tǒng) 4.3.3 霍恩子句邏輯程序 第五章 遞歸函數(shù)論,,
離散數(shù)學(xué)第四章謂詞演算的推理理論-歸結(jié)推理系統(tǒng).ppt
