四章節(jié)謂詞演算推理理論ppt課件

1、第四章 謂詞演算的推理實(shí)際4.1 謂詞演算的永真推理系統(tǒng)謂詞演算的永真推理系統(tǒng)4.2謂詞演算的假設(shè)推理系統(tǒng)謂詞演算的假設(shè)推理系統(tǒng)4.3謂詞演算的歸結(jié)推理系統(tǒng)謂詞演算的歸結(jié)推理系統(tǒng)4.3 謂詞演算的歸結(jié)推理系統(tǒng)謂詞演算的歸結(jié)推理系統(tǒng)l 將前提集將前提集S化成子句集，化成子句集，l 將目的公式的否認(rèn)將目的公式的否認(rèn)(即即 B)化成子句集，化成子句集，l 歸結(jié)歸結(jié)l 假設(shè)能歸結(jié)出矛盾，那么以為證明完成。假設(shè)能歸結(jié)出矛盾，那么以為證明完成。 1， 2， ， k B前提公式集前提公式集S目的公式目的公式B引例(p45) 知：(1)(1)無(wú)論誰(shuí)能讀就有知識(shí)；無(wú)論誰(shuí)能讀就有知識(shí)；(2)(2)一切的海豚均沒(méi)有

2、知識(shí)；一切的海豚均沒(méi)有知識(shí)；(3)(3)有些海豚有智慧。有些海豚有智慧。試證明：試證明：(4)(4)一些有智慧的個(gè)體不能讀。一些有智慧的個(gè)體不能讀。 x(R(x)x(R(x) L(x) L(x) x(H(x)x(H(x)L(x)L(x) x(H(x)x(H(x) I(x)I(x) x(I(x)x(I(x)R(x)R(x)其中：其中： R(x): x R(x): x能讀；能讀； L(x): x L(x): x有知識(shí)；有知識(shí)； H(x): x H(x): x是海豚；是海豚； I(x): x I(x): x有智慧有智慧引例 (p45，提取子句)(1) R(x1) L(x1)(2) H(x2) L(x

3、2)(3) H(a) I(a)(5) I(x3)R(x3)前提：前提： x(R(x) L(x) x(H(x)L(x) x(H(x) I(x)結(jié)論的否認(rèn)結(jié)論的否認(rèn) x(I(x)R(x)= x( I(x) R(x)引例 (p45，歸結(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é)歸結(jié)(7) L(a) a/ x1(6)(1)歸結(jié)歸結(jié)(8) H(a) a/ x2(7)(2)歸結(jié)歸結(jié)(9) (8)(3)歸結(jié)歸結(jié)留意：歸結(jié)時(shí)運(yùn)用了未討論過(guò)的置換的概念。留意：歸結(jié)時(shí)運(yùn)用了未討論過(guò)的置換的概

4、念。4.3.1 置換置換置換置換項(xiàng)對(duì)變量的交換。項(xiàng)對(duì)變量的交換。(1)置換必需處處進(jìn)展。置換必需處處進(jìn)展。(2)要求沒(méi)有變量被含有同一變量的項(xiàng)來(lái)替代。要求沒(méi)有變量被含有同一變量的項(xiàng)來(lái)替代。 例例 知表達(dá)式知表達(dá)式 P(x) P(f(x)x不能用不能用f(x)交換交換例例 知表達(dá)式知表達(dá)式 P(x，g(y)，b)，調(diào)查置換，調(diào)查置換: 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 普通地，置換可經(jīng)過(guò)有序?qū)Φ募掀胀ǖ?，置換可經(jīng)過(guò)有序?qū)Φ募蟭1/v1，t2/v2，tn/vn來(lái)表達(dá)，其中來(lái)表達(dá)，其中ti/vi表示變量表示

5、變量vi處處以項(xiàng)處處以項(xiàng)ti來(lái)替代。來(lái)替代。4.3.2 歸結(jié)反演系統(tǒng)歸結(jié)反演系統(tǒng)一、謂詞演算公式子句的構(gòu)成一、謂詞演算公式子句的構(gòu)成二、普通歸結(jié)二、普通歸結(jié)三、歸結(jié)反演系統(tǒng)三、歸結(jié)反演系統(tǒng)子句構(gòu)成的普通步驟子句構(gòu)成的普通步驟:(1)消去蘊(yùn)含詞和等價(jià)詞消去蘊(yùn)含詞和等價(jià)詞(2)否認(rèn)深化否認(rèn)深化(3)約束變?cè)拿s束變?cè)拿?4)化為前束范式化為前束范式(5)消去存在量詞消去存在量詞(按按Skolem規(guī)范形規(guī)范形)(6)消去全稱量詞消去全稱量詞(直接去掉直接去掉)(7)化為合取范式化為合取范式(8)消去合取詞得子句集，消去合取詞得子句集，(9)改動(dòng)變量的稱號(hào)改動(dòng)變量的稱號(hào) (變量符號(hào)不反復(fù)運(yùn)用變量符

6、號(hào)不反復(fù)運(yùn)用)例例 求求 xP(x)x(A(x)y(B(y) W(x，y)的子句的子句解解:(1)消去蘊(yùn)含詞消去蘊(yùn)含詞 xP(x)x( A(x)y(B(y) W(x，y)(2)約束變?cè)拿杭s束變?cè)拿?xP(x)z( A(z)y(B(y) W(z，y)(3)化為前束范式化為前束范式 x z y(P(x) ( A(z) (B(y) W(z，y)(4)消去存在量詞消去存在量詞(按按Skolem規(guī)范形規(guī)范形) 原式原式z(P(a) ( A(z) (B(f(z) W(z，f(z)(5)消去全稱量詞消去全稱量詞(直接去掉直接去掉) 原式原式 P(a) ( A(z) (B(f(z) W(z，f(z)(

7、6)利用分配律化為合取范式利用分配律化為合取范式 原式原式 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)改動(dòng)變量的稱號(hào)：改動(dòng)變量的稱號(hào)： P(a), A(z1) B(f(z1), A(z2) W(z2，f(z2)關(guān)于改動(dòng)變量名的闡明關(guān)于改動(dòng)變量名的闡明: x(A(x) B(x)= xA(x) yB(y) 互補(bǔ)文字對(duì)的歸結(jié)互補(bǔ)文字對(duì)的歸結(jié)尋覓一個(gè)置換使得子句上含有互補(bǔ)的文字對(duì)尋覓一個(gè)置換使得子句上含有互補(bǔ)的文字對(duì)(如如P和和P) 。例例 設(shè)有兩個(gè)子句設(shè)有兩個(gè)子

8、句 P(x，g(a)Q(y), P(z，g(a)Q(z) 可得假設(shè)干歸結(jié)式如下：可得假設(shè)干歸結(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)要證明定理要證明定理 A1 A1，A2A2，An BAn B，只需：只需：將將 A1 A1，A2A2，An, An, B B分別化為子句集；分別化為子句集；歸結(jié)出空子句歸結(jié)出空子句, ,即證明其不可滿足。即證明其不可滿足。第步等價(jià)于將第步等價(jià)于將A1A2AnB化為子句集化為子句集例例 (p47)知知識(shí)：知知識(shí)： (1)每個(gè)作家均寫過(guò)作品；每個(gè)作家均寫過(guò)作品； (2)有些作家沒(méi)寫過(guò)小說(shuō)

9、；有些作家沒(méi)寫過(guò)小說(shuō)；結(jié)論：有些作品不是小說(shuō)。結(jié)論：有些作品不是小說(shuō)。 x(A(x)y(B(y) 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為小說(shuō)；為小說(shuō)； W(e1，e2)表示表示“e1 寫了寫了 e2求子句求子句: 每個(gè)作家均寫過(guò)作品每個(gè)作家均寫過(guò)作品 (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

10、(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(x2，f(x2) 求子句求子句: 有些作家沒(méi)寫過(guò)小說(shuō)有些作家沒(méi)寫過(guò)小說(shuō)(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)求子句求子句:有些作品不是小說(shuō)有些作品不是小說(shuō) x(B(x)N(x) 否認(rèn)結(jié)論得到

11、：否認(rèn)結(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)W(a，y)(5) B(x)N(x)(6) A(x1) N(f(x1) f(x1)/x (5)(1)歸結(jié)歸結(jié)(7) N(f(a) a/x1 (6)(3)歸結(jié)歸結(jié)(8) W(a，f(a) f(a)/y (7)(4)歸結(jié)歸結(jié) (9) A(a) a/x2 (8)(2)歸結(jié)歸結(jié)(10) 口口 (9)(3)歸結(jié)歸結(jié)補(bǔ)充習(xí)題任何人假設(shè)喜歡步行，他就不喜歡乘汽車；每個(gè)人或者喜歡乘汽車，

12、或者喜歡騎自行車；有的人不喜歡騎自行車，因此有的人不愛(ài)步行。試用歸結(jié)原理證明之。證明：令證明：令 P(e)表示表示“e為人；為人； W(e)表示表示“e喜歡步行；喜歡步行； D(e)表示表示“e喜歡乘汽車；喜歡乘汽車； R(e)表示表示“e喜歡騎自行車喜歡騎自行車證明(續(xù))那么知知識(shí)可以翻譯為：那么知知識(shí)可以翻譯為：1 x(P(x) (W(x) D(x)2 x(P(x) (D(x) R(x)3 x(P(x) R(x) 結(jié)論為：結(jié)論為： x(P(x) W(x) )結(jié)論的否以為：結(jié)論的否以為： x( P(x) W(x)(1) P(x1)W(x1) D(x1)(2) P(x2)D(x2) R(x2)

13、(3) P(a)(4) R(a)(5) P(x)W(x)(6) W(a) D(a) a/x1 (3)(1)歸歸結(jié)結(jié)(7) P(a)D(a) a/x2 (4)(2)歸結(jié)歸結(jié)(8) P(a) D(a) a/y (5)(6)歸結(jié)歸結(jié) (9) P(a) (8)(7)歸結(jié)歸結(jié)(10) 口口 (9)(3)歸結(jié)歸結(jié)4.3.3 霍恩子句邏輯程序霍恩子句邏輯程序許多人工智能系統(tǒng)中運(yùn)用的知識(shí)是由普通的蘊(yùn)許多人工智能系統(tǒng)中運(yùn)用的知識(shí)是由普通的蘊(yùn)含表達(dá)式來(lái)表示的。含表達(dá)式來(lái)表示的。假設(shè)把蘊(yùn)含式假設(shè)把蘊(yùn)含式(PQ)R化為等價(jià)的析取式化為等價(jià)的析取式P Q R ，往往會(huì)喪失能夠包含在蘊(yùn)含式中的重要的超邏往往會(huì)喪失能夠包含

14、在蘊(yùn)含式中的重要的超邏輯的控制信息。輯的控制信息。基于規(guī)那么的演繹系統(tǒng)知識(shí)：知識(shí)：l規(guī)那么規(guī)那么普通知識(shí)，由蘊(yùn)含式表示普通知識(shí)，由蘊(yùn)含式表示l現(xiàn)實(shí)現(xiàn)實(shí)專門知識(shí)，由不包含蘊(yùn)含式的陳說(shuō)組成專門知識(shí)，由不包含蘊(yùn)含式的陳說(shuō)組成基于規(guī)那么的演繹系統(tǒng)基于規(guī)那么的演繹系統(tǒng)根據(jù)現(xiàn)實(shí)和規(guī)那么來(lái)證明目的公式根據(jù)現(xiàn)實(shí)和規(guī)那么來(lái)證明目的公式一、子句的蘊(yùn)含表示方式一個(gè)子句一個(gè)子句( (析取式析取式) )： C = C = P1P1P2P2PnPnQ1Q1Q2Q2QmQm可以表示為：可以表示為： (P1 (P1P2P2Pn)Pn)(Q1(Q1Q2Q2Qm)Qm)簡(jiǎn)記為：簡(jiǎn)記為：P1P1，P2P2，PnPn Q1 Q1，Q

15、2Q2，QmQmQ1Q1，Q2Q2，Qm Qm P1 P1，P2P2，PnPn子句的類型Q1，Q2，Qm P1，P2，Pnm0,n0 P1，P2，Pnm0,n0Q1，Q2，Qm m0,n0口口m=0, n 0子句的歸結(jié)子句的歸結(jié)子句子句1子句子句2歸結(jié)式歸結(jié)式PRQPQRP, QRQPQRP, QRP,QPP,RP, QRP,QQQ,RP, QRQ,RPRPP口口一樣的文字出如今兩邊即可以消除一樣的文字出如今兩邊即可以消除每次歸結(jié)只能消除一對(duì)一樣的文字每次歸結(jié)只能消除一對(duì)一樣的文字霍恩子句 定義：子句定義：子句 L1L2Ln 中，假設(shè)至多只含有一個(gè)正文字，中，假設(shè)至多只含有一個(gè)正文字， 那么該

16、子句稱為霍恩子句。那么該子句稱為霍恩子句。 霍恩子句霍恩子句PQ1Q2Qn可表為：可表為：PQ1，Q2，Qn霍恩子句的類型霍恩子句的類型 P Q1，Q2，Qn n 0 P 上式上式n=0 Q1，Q2，Qn n 0口口 上式上式n=0過(guò)程過(guò)程現(xiàn)實(shí)現(xiàn)實(shí)目的目的停機(jī)語(yǔ)句停機(jī)語(yǔ)句過(guò)程名過(guò)程名過(guò)程調(diào)用，過(guò)程調(diào)用，過(guò)程調(diào)用，過(guò)程調(diào)用，過(guò)程調(diào)用，過(guò)程調(diào)用霍恩子句邏輯霍恩子句邏輯由霍恩子句構(gòu)成的一階謂詞演算系統(tǒng)由霍恩子句構(gòu)成的一階謂詞演算系統(tǒng)執(zhí)行算法：執(zhí)行算法：由目的中的一個(gè)過(guò)程調(diào)用與現(xiàn)實(shí)或過(guò)程名匹由目的中的一個(gè)過(guò)程調(diào)用與現(xiàn)實(shí)或過(guò)程名匹配啟動(dòng)，當(dāng)匹配勝利后，構(gòu)成新的目的。配啟動(dòng)，當(dāng)匹配勝利后，構(gòu)成新的目的。兩

17、個(gè)霍恩子句的歸結(jié)是一個(gè)霍恩子句。兩個(gè)霍恩子句的歸結(jié)是一個(gè)霍恩子句。霍恩子句邏輯霍恩子句邏輯要證明定理要證明定理 A1 A1，A2A2，An BAn B，只需：只需：將將A1A1，A2A2，An, An, B B分別化為霍恩子分別化為霍恩子句集；句集；歸結(jié)出空子句歸結(jié)出空子句, ,即證明其不可滿足。即證明其不可滿足。第步等價(jià)于將第步等價(jià)于將A1A2AnB化為霍恩子化為霍恩子句集句集例例 知前提知前提 (1) TOM在何處，在何處， MARY在何處在何處 (2) MARY在何處，她的在何處，她的COMPUTER在何處在何處 (3) TOM在圖書館在圖書館 試證試證“MARY的的COMPUTER是在

18、圖書館？是在圖書館？ 解：霍恩子句為解：霍恩子句為 (1) At(MARY,x) At(TOM,x) 過(guò)程過(guò)程 (2) At(COMPUTER,y) At(MARY,y) 過(guò)程過(guò)程 (3) At(TOM, Library) 現(xiàn)實(shí)現(xiàn)實(shí) (4) At(COMPUTER, Library) 目的目的解：霍恩子句邏輯程序?yàn)榻猓夯舳髯泳溥壿嫵绦驗(yàn)?(1) At(MARY,x) At(TOM,x) 過(guò)程過(guò)程 (2) At(COMPUTER,y) At(MARY,y) 過(guò)程過(guò)程 (3) At(TOM, Library) 現(xiàn)實(shí)現(xiàn)實(shí) (4) At(COMPUTER, Library) 目的目的 (5) At(M

19、ARY, Library) Library/y (2)(4)匹配匹配 (6) At(TOM, Library) ) Library/x (1)(5)匹配匹配 (7) 口口 (3)(6)匹配匹配 此程序證明了此程序證明了MARY的的COMPUTER在圖書館。在圖書館。例 一切羊都吃草,一切死羊都不吃草. 所以,一切死羊都不是羊.解解: 知識(shí)翻譯為知識(shí)翻譯為 x(羊羊(x) 吃草吃草(x) x(死羊死羊(x) 吃草吃草(x) x(死羊死羊(x) 羊羊(x), 其否以為其否以為 x(死羊死羊(x)羊羊(x) 霍恩子句邏輯程序及執(zhí)行過(guò)程如下：霍恩子句邏輯程序及執(zhí)行過(guò)程如下： (1) 吃草吃草(x)羊羊

20、(x) 過(guò)程過(guò)程 (2) 死羊死羊(x1), 吃草吃草(x1) 目的目的 (3) 死羊死羊(a) 現(xiàn)實(shí)現(xiàn)實(shí) (4) 羊羊(a) 現(xiàn)實(shí)現(xiàn)實(shí) (5) 死羊死羊(x), 羊羊(x) x/x1(2)(1)歸結(jié)歸結(jié) (6) 羊羊(a) a/x(5)(3)歸結(jié)歸結(jié) (7) 口口 (6)(4)歸結(jié)歸結(jié)例例 知知識(shí)：知知識(shí)：(1)有些病人喜歡一切的醫(yī)生；有些病人喜歡一切的醫(yī)生；(2)一切的病人均不喜歡庸醫(yī)；一切的病人均不喜歡庸醫(yī)；試證明結(jié)論：一切的醫(yī)生均不是庸醫(yī)。試證明結(jié)論：一切的醫(yī)生均不是庸醫(yī)。 x(P(x)y(D(y)L(x，y) x(P(x)y(Q(y) L(x，y)x(D(x) Q(x)證明：證明：

21、令令P(e)表示表示“e為病人；為病人； D(e)表示表示“e為醫(yī)生；為醫(yī)生； Q(e)表示表示“e為庸醫(yī)；為庸醫(yī)； L(e1，e2)表示表示“e1喜歡喜歡e2； x(D(x) Q(x)霍恩子句邏輯程序及執(zhí)行過(guò)程如下：霍恩子句邏輯程序及執(zhí)行過(guò)程如下：(1) P(a) 現(xiàn)實(shí)現(xiàn)實(shí)(2) L(a,y) D(y) 過(guò)程過(guò)程(3) P(x1), Q(y1), L(x1,y1 目目的的(4) D(b) 現(xiàn)實(shí)現(xiàn)實(shí)(5) Q(b) 現(xiàn)實(shí)現(xiàn)實(shí)(6) Q(y1), L(a，y1) a/x1(3)(1)歸歸結(jié)結(jié)(7) Q(y)， D(y) y/y1(6)(2)歸歸結(jié)結(jié)(8) Q(b) b/y(7)(4)歸結(jié)歸結(jié)(9

22、) 口口 (8)(5)歸結(jié)歸結(jié)例例 (p50-51) 知知識(shí)：知知識(shí)： (1)桌子上的每一本書均是杰作；桌子上的每一本書均是杰作； (2)寫出杰作的人是天才；寫出杰作的人是天才； (3)某個(gè)不知名的人寫了桌上某本書；某個(gè)不知名的人寫了桌上某本書； 結(jié)論：某個(gè)不知名的人是天才。結(jié)論：某個(gè)不知名的人是天才。解：令解：令 A(e)表示表示“e為桌上的書；為桌上的書； B(e)表示表示“e為杰作；為杰作； C(e)表示表示“e為天才；為天才； D(e)表示表示“e知名；知名； P(e)表示表示“e為人；為人； W(e1，e2)表示表示“e1 寫了寫了 e2.例例 (p50-51) 知知識(shí)：知知識(shí)： (

23、1)桌子上的每一本書均是杰作；桌子上的每一本書均是杰作； (2)寫出杰作的人是天才；寫出杰作的人是天才； (3)某個(gè)不知名的人寫了桌上某本書；某個(gè)不知名的人寫了桌上某本書； 結(jié)論：某個(gè)不知名的人是天才。結(jié)論：某個(gè)不知名的人是天才。(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) =x y(P(x)B(y) W(x，y)C(x) (P(x)B(y) W(x，y)C(x)(3) x

24、 (P(x) D(x) y(A(y) W(x，y) =xy(P(x) A(y) D(x) W(x，y) P(a) A(b) D(a) W(a，b)否認(rèn)結(jié)論得到否認(rèn)結(jié)論得到 x(P(x)x(P(x) D(x)D(x) C(x) C(x) = = x ( x ( P(x) P(x) D(x) D(x) C(x) C(x)解：解：(7)D(x3)(7)D(x3) P(x3) P(x3)，C(x3) C(x3) 過(guò)程過(guò)程 (8)(8) P(a) P(a)，C(a) a/x3(5)(7)C(a) a/x3(5)(7)歸結(jié)歸結(jié)(9)(9) C(a) (8)(3) C(a) (8)(3)歸結(jié)歸結(jié)(10)(1

25、0) P(a),B(y), W(a P(a),B(y), W(a，y) a/x2(9)(2)y) a/x2(9)(2)歸結(jié)歸結(jié)(11)(11) B(y) B(y)， W(a W(a，y) (10)(3)y) (10)(3)歸結(jié)歸結(jié)(12)(12) A(y) A(y)，W(aW(a，y) y/x1(11)(1)y) y/x1(11)(1)歸結(jié)歸結(jié)(13)(13) W(a W(a，b) b/y(12)(4)b) b/y(12)(4)歸結(jié)歸結(jié)(14)(14)口口 (13)(6) (13)(6)歸結(jié)歸結(jié)(1)B(x1)(1)B(x1)A(x1) A(x1) 過(guò)程過(guò)程(2)C(x2)(2)C(x2) P(x2) P(x2)，B(y)B(y)， W(x2 W(x2，y) y) 過(guò)程過(guò)程(3)P(a)(3)P(a) 現(xiàn)實(shí)現(xiàn)實(shí)(4)A(b)(4)A(b) 現(xiàn)實(shí)現(xiàn)實(shí)(5)(5) D(a) D(a) 目的目的(6)W(a(6)W(a，b)b) 現(xiàn)實(shí)現(xiàn)實(shí)例例 知知識(shí)如下：知知識(shí)如下： (1)每個(gè)程序員均寫過(guò)程序；每個(gè)程序員均寫過(guò)程序； (2)病