-第四章推理技術(shù)-謂詞邏輯課件

1、第四章 推理技術(shù) 4.1 一階謂詞邏輯推理4.2 歸結(jié)演繹推理推理技術(shù)概述推理是人類求解問(wèn)題的主要思維方法，即按照某種策略從已有事實(shí)和知識(shí)推出結(jié)論的過(guò)程。按思維方式可分演繹推理、歸納推理、類比推理等。邏輯推理：按邏輯規(guī)則進(jìn)行的推理。分為： 經(jīng)典邏輯推理 :主要指命題邏輯和一階謂詞邏輯推理，也稱精確推理或確定性推理； 非經(jīng)典邏輯推理：主要指除經(jīng)典邏輯之外，按多值邏輯、模糊邏輯、概率邏輯等的推理，也稱為非精確推理或非確定性推理。邏輯推理舉例 經(jīng)典推理：蘇格拉底之死 如何判別謊言？ ABC三人都喜歡說(shuō)謊話，偶爾也說(shuō)真話。某天，A指責(zé)B說(shuō)謊話，B指責(zé)C說(shuō)謊話，C說(shuō)AB兩人都在說(shuō)謊話。問(wèn)誰(shuí)在說(shuō)謊？ 有幾

2、條瘋狗？ 村里有50戶人家，每家都養(yǎng)了一條狗?，F(xiàn)發(fā)現(xiàn)村子里面出現(xiàn)了n只瘋狗，村里規(guī)定，誰(shuí)要是發(fā)現(xiàn)了自己的狗是瘋狗，就要將自己的狗槍斃。但問(wèn)題是，村子里面的人只能看出別人家的狗是不是瘋狗，而不能看出自己的狗是不是瘋的，如果看出別人家的狗是瘋狗，也不能告訴別人。于是大家開(kāi)始觀察，第一天晚上，沒(méi)有槍聲，第二天晚上，沒(méi)有槍聲，第三天晚上，槍聲響起（具體幾槍不清楚），問(wèn)村子里有幾只瘋狗？只有晚上才能看出病狗，并且一天晚上只能看一次。 愛(ài)因斯坦的世界難題（1）愛(ài)因斯坦在20世紀(jì)初出一個(gè)謎語(yǔ)。他說(shuō)世界上有98的人答不出來(lái)。1、在一條街上，有5座房子，噴了5種顏色；2、每個(gè)房里住著不同國(guó)籍的人；3、每個(gè)人喝不

3、同的飲料，抽不同品牌的香煙，養(yǎng)不同的寵物。 問(wèn)題是：誰(shuí)養(yǎng)魚(yú)？ 愛(ài)因斯坦的世界難題（2）條件是：1、英國(guó)人住紅色房子； 2、瑞典人養(yǎng)狗；3、丹麥人喝茶；4、綠色房子在白色房子左面；5、綠色房子主人喝咖啡；6、抽PallMall香煙的人養(yǎng)鳥(niǎo)；7、黃色房子主人抽Dunhill香煙；8、住在中間房子的人喝牛奶；9、挪威人住第一間房；10、抽Blends香煙的人住在養(yǎng)貓的人隔壁11、養(yǎng)馬的人住抽Dunhill香煙的人隔壁；12、抽BlueMaster的人喝??；13、德國(guó)人抽Prince香煙；14、挪威人住藍(lán)色房子隔壁；15、抽Blends香煙的人有一個(gè)喝水的鄰居。邏輯學(xué)與計(jì)算機(jī)科學(xué)邏輯學(xué)：研究思維規(guī)律的

4、科學(xué)計(jì)算機(jī)科學(xué)：模擬人腦行為和功能（思維）的科學(xué)思維：大腦、邏輯、語(yǔ)言、計(jì)算機(jī)邏輯是知識(shí)表示和推理的重要形式和工具8邏輯的歷史Aristotle邏輯學(xué)Leibnitz數(shù)理邏輯： 邏輯+數(shù)學(xué)Gottlob Frege (1848-1925)一階謂詞演算系統(tǒng) 邏輯是探索、闡述和確立有效推理原則的學(xué)科，最早由古希臘學(xué)者亞里士多德創(chuàng)建的。用數(shù)學(xué)的方法研究關(guān)于推理、證明等問(wèn)題的學(xué)科就叫做數(shù)理邏輯。也叫做符號(hào)邏輯。 20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展，成為數(shù)學(xué)和計(jì)算機(jī)科學(xué)基礎(chǔ)。邏輯系統(tǒng)一個(gè)邏輯系統(tǒng)是定義語(yǔ)言和它的含義的方法。邏輯系統(tǒng)中的一個(gè)邏輯理論是該邏輯的語(yǔ)言的一個(gè)語(yǔ)句集合，它包括：邏輯符號(hào)集合：在所有

5、該邏輯的邏輯理論中均出現(xiàn)的符號(hào)；非邏輯符號(hào)集合：不同的邏輯理論中出現(xiàn)的不同的符號(hào)；語(yǔ)句規(guī)則：定義什么樣的符號(hào)串是有意義的；證明：什么樣的符號(hào)串是一個(gè)合理的證明；語(yǔ)義規(guī)則：定義符號(hào)串的語(yǔ)義。邏輯程序語(yǔ)言邏輯符號(hào)保留字或者符號(hào)非邏輯符號(hào)用戶自定義的符號(hào)(變量名，函數(shù)名等)語(yǔ)句規(guī)則構(gòu)造一個(gè)程序的語(yǔ)句規(guī)則語(yǔ)義規(guī)則定義程序做什么的語(yǔ)句規(guī)則推理規(guī)則、公理和證明沒(méi)有邏輯與程序語(yǔ)言的對(duì)比1.3 命題邏輯命題：可以確定其真假的陳述句。Bolle提出了布爾代數(shù)。語(yǔ)言:原子Q、否定、吸取V、合取、蘊(yùn)含 、等價(jià)公式：AVB， (AB,A)= ? 公司招聘工作人員，有M,N,Q三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1

6、）三人中至少錄取一人;（2）如果錄取M,則一定錄取N；（3）如果錄取N,則一定錄取Q。結(jié)果如何？1.4 謂詞邏輯(一階邏輯)謂詞邏輯是一種形式語(yǔ)言，具有嚴(yán)密的理論體系，也是一種常用的知識(shí)表示方法。語(yǔ)言: ，(，)；常元，變?cè)?，函詞，謂詞；公式City（北京）City（上海）Age（張三，23）(x)( y)( z) (F(x, y)F(y, z)GF(x, z)）謂詞邏輯中的形式演繹推理將自然語(yǔ)言中的陳述語(yǔ)句利用謂詞公式表示利用邏輯等價(jià)式將謂詞公式進(jìn)行變換利用邏輯蘊(yùn)含式推出結(jié)論符號(hào)化過(guò)程公式變形推理過(guò)程表4.1 常用邏輯等價(jià)式 表4.2 常用邏輯蘊(yùn)含式 設(shè)有前提： (1)凡是大學(xué)生都學(xué)過(guò)計(jì)算機(jī)

7、； (2)小王是大學(xué)生。 試問(wèn)：小王學(xué)過(guò)計(jì)算機(jī)嗎？ 解 令S(x)：x是大學(xué)生; M(x)：x學(xué)過(guò)計(jì)算機(jī); a：小王。則上面的兩個(gè)命題可用謂詞公式表示為 (1) x(S(x)M(x) (2) S(a) 例 下面我們進(jìn)行形式推理： (1) x(S(x)M(x) 前提 (2)S(a)M(a) (1),US (3)S(a) 前提 (4)M(a) (2),(3),I3 得結(jié)果：M(a)，即“小王學(xué)過(guò)計(jì)算機(jī)”。 這種推理過(guò)程完全是一種符號(hào)變換過(guò)程，很類似于人們用自然語(yǔ)言推理的思維過(guò)程，因而稱為自然演繹推理 在語(yǔ)法上，如果存在一個(gè)從假設(shè)到的證明，則記為 ，稱由可推導(dǎo)出的，或可證明的。如果在沒(méi)有任何假設(shè)下是

8、可推導(dǎo)出的，則記為 ，稱為可證明的。 稱一個(gè)假設(shè)是不協(xié)調(diào)的，如果存在一個(gè)語(yǔ)句使得和的否定均可由推導(dǎo)得出。 稱一個(gè)邏輯系統(tǒng)是一致的，或相容的(consistent)，如果不存在邏輯系統(tǒng)的公式A，使得A與A同時(shí)成立。證 明(語(yǔ)法) 語(yǔ)言的解釋是在某個(gè)論域(domain)中定義非邏輯符號(hào)。語(yǔ)句的語(yǔ)義是在解釋下定義出語(yǔ)言L的真假值。如果I是L的一個(gè)解釋，且在I中為真，則記為I ，稱作I滿足 ，或者I 是的一個(gè)模型。 類似地，給定一個(gè)語(yǔ)句和一個(gè)語(yǔ)句 ，如果對(duì)每個(gè)解釋I ，有I 蘊(yùn)含I ，換言之，如果I 是的一個(gè)模型則I也是的一個(gè)模型，則記為 ，我們稱為的一個(gè)邏輯結(jié)果。解 釋(語(yǔ)義)可靠性(reliabl

9、e) 語(yǔ)法-語(yǔ)義一個(gè)邏輯是可靠的，如果它的證明保持真假值，即在任何解釋I下，如果I是 的模型，且可由推導(dǎo)出，則I也是的一個(gè)模型。即，一個(gè)邏輯是可靠的，如果對(duì)任何語(yǔ)句集合和語(yǔ)句 ， 蘊(yùn)涵 ?？煽啃院屯陚湫酝陚湫?complete) 語(yǔ)義-語(yǔ)法一個(gè)邏輯是完備的，如果任何永真語(yǔ)句是可證的。即，對(duì)任何語(yǔ)句集合和語(yǔ)句 ， 蘊(yùn)涵 。如果一個(gè)邏輯是完備的，則該邏輯的證明系統(tǒng)已強(qiáng)到可以推出任何永真式。Gdel完備性定理：一階邏輯是完備的可判定的一個(gè)邏輯稱為是可判定的(decidable)，如果存在一個(gè)算法對(duì)邏輯中的任一公式 A，可確定 A是否成立。否則，稱為是不可判定的(undecidable) 。如果上述算

10、法雖不一定存在，卻有一個(gè)過(guò)程，可對(duì)該系統(tǒng)的定理做出肯定的判斷，但對(duì)非定理的公式過(guò)程未必終止，因而未必能作出判斷。這時(shí)稱邏輯是半可判定的。可判定性一階邏輯是不可判定的，但它是半可判定的。 現(xiàn)代邏輯學(xué)與計(jì)算機(jī)科學(xué)、計(jì)算語(yǔ)言學(xué)和人工智能的關(guān)系表 邏 輯 自然語(yǔ) 程序 人工 邏輯 指令與直 數(shù)據(jù)庫(kù) 復(fù)雜性 智能體 未 來(lái) 展 望 言處理 控制 智能 編程 陳式語(yǔ)言 理論 理論 理論時(shí)序邏輯 廣泛應(yīng)用模態(tài)邏輯 非?；钴S算法證明 非單調(diào)推理 意義重大概率和模糊 目前主流直覺(jué)主義邏輯 主要替代者高階邏輯，-演算 更具中心作用經(jīng)典邏輯片斷 前景誘人資源和子結(jié)構(gòu)邏輯 纖維化和組合邏輯 可自我指稱謬誤理論 在適當(dāng)

11、語(yǔ)境邏輯動(dòng)力學(xué) 動(dòng)態(tài)邏輯觀論辯理論游戲 前景光明對(duì)象層次/元層次 總起中心作用機(jī)制:溯因 缺省 相干 邏輯的一部分與神經(jīng)網(wǎng)絡(luò)的聯(lián)系 極重要，剛開(kāi)始時(shí)間-行動(dòng)-修正模型 一類新模型加標(biāo)演繹系統(tǒng) 邏輯學(xué)的統(tǒng)一框架4.2 歸結(jié)演繹推理 歸結(jié)演繹推理是基于一種稱為歸結(jié)原理(亦稱消解原理 principle of resolution)的推理規(guī)則的推理方法。 歸結(jié)原理是由魯濱遜(J.A.Robinson)于1965年首先提出。它是謂詞邏輯的一個(gè)相當(dāng)有效的機(jī)械化推理方法。 歸結(jié)原理的出現(xiàn)，被認(rèn)為是自動(dòng)推理，特別是定理機(jī)器證明領(lǐng)域的重大突破。從理論上解決了定理證明問(wèn)題。 有關(guān)歸結(jié)演繹推理的定義文字子句空子句

12、子句集Skolem函數(shù)Skolem常量互補(bǔ)文字歸結(jié)，又稱消解(resolution) 定義1 原子謂詞公式及其否定稱為文字， 若干個(gè)文字的一個(gè)析取式稱為一個(gè)子句 不含任何文字的子句稱為空子句（真值為假），記為NIL。 例如下面的析取式都是子句 PQ乛R P(x,y)乛Q(x) 定義2 對(duì)一個(gè)謂詞公式G，通過(guò)以下步驟所得的子句集合S，稱為G的子句集。 (1)消去蘊(yùn)含詞和等值詞?？墒褂眠壿嫷葍r(jià)式: AB 乛AB A B (乛AB)(乛BA) (2)縮小否定詞的作用范圍，直到其僅作用于原子公式?？墒褂眠壿嫷葍r(jià)式: 乛(乛A) A 乛(AB) 乛A乛B將一個(gè)謂詞公式轉(zhuǎn)換為子句集乛(AB) 乛A乛B乛

13、xP(x) x乛P(x)乛 xP(x) x乛P(x) (3)適當(dāng)改名，使量詞間不含同名自由變?cè)图s束變?cè)?(4)消去存在量詞。 消去存在量詞時(shí)，同時(shí)還要進(jìn)行變?cè)鎿Q。變?cè)鎿Q分兩種情況： 若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變?cè)囊粋€(gè)函數(shù)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的函數(shù)稱為Skolem函數(shù)； 若該存在量詞不在任何全稱量詞的轄域內(nèi)，則用一個(gè)常量符號(hào)代替該存在量詞轄域中的相應(yīng)約束變?cè)?，這樣的常量符號(hào)稱為Skolem常量。 x y P(x,y) 根據(jù)步驟4轉(zhuǎn)換為 x P(x,g(x)這里y=g(x)為Skolem函數(shù)。 xP(x) 根據(jù)步驟4轉(zhuǎn)換為 P(a), 這

14、里a為Skolem常量 Skolem函數(shù)舉例 (5)消去所有全稱量詞。 (6)化公式為合取范式。 可使用邏輯等價(jià)式: A(BC) (AB)(AC) (AB)C (AC)(BC) (7)適當(dāng)改名，使子句間無(wú)同名變?cè)?(8)消去合取詞，以子句為元素組成一個(gè)集合S。 (A B) (C D)1. 消去 (A B) (C D)轉(zhuǎn)換子句集舉例(A B) (C D)1. 消去 (A B) (C D)2. 縮減 作用范圍 (A B) (C D)轉(zhuǎn)換子句集舉例(A B) (C D)1. 消去 (A B) (C D)2. 縮減 作用范圍 (A B) (C D)3.化公式為合取范式(A (C D) (B (C D

15、)(A C) (A D) (B C) (B D)轉(zhuǎn)換子句集舉例(A B) (C D)1. 消去 (A B) (C D)2. 縮減 作用范圍 (A B) (C D)3.化公式為合取范式(A (C D) (B (C D)(A C) (A D) (B C) (B D)子句集:A C , A D , B C , B D謂詞公式轉(zhuǎn)換子句集舉例定義3：若P是原子謂詞公式，則P與乛P為互補(bǔ)文字定義4：設(shè)C1與C2是子句集中的任意兩個(gè)基子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么C1和C2中分別消去L1和L2，并將兩個(gè)子句余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱此過(guò)程為歸結(jié)，又稱消解（resolu

16、tion）。稱C12為基子句C1和C2的歸結(jié)式。稱C1和C2為C12的親本子句。例3.9 設(shè)C1=乛PQR, C2=乛QS,于是C1,C2的歸結(jié)式為 乛PRS歸結(jié)（消解）定義子句集的特點(diǎn) 由謂詞公式轉(zhuǎn)化為子句集的過(guò)程中可以看出，在子句集中子句之間是合取關(guān)系。 其中只要有一個(gè)子句不可滿足(真值為假），則子句集就不可滿足。 若一個(gè)子句集中包含空子句，則這個(gè)子句集一定是不可滿足的。由歸結(jié)原理可知：如果兩個(gè)互否的單元子句進(jìn)行歸結(jié)，則歸結(jié)式為空子句即: L L= 同時(shí)， L L= F(假）因此 F因此，可以通過(guò)推導(dǎo)空子句來(lái)做間接證明。一旦推出了空子句，就說(shuō)明子句集S是不可滿足的歸結(jié)反演證明步驟第一步：化

17、子句集（1）將定理證明的前提謂詞公式轉(zhuǎn)換為子句集F (2) 將要求證明的目標(biāo)表示成謂詞公式G(目標(biāo)公式）（3）將目標(biāo)公式的否定式乛G轉(zhuǎn)化成子句的形式，并加入到子句集F,得到子句集S。第二步：歸結(jié)反演 應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)的歸結(jié)式都并入到S中。如此反復(fù)進(jìn)行，若歸結(jié)得到一個(gè)空子句NIL，則停止歸結(jié)，此時(shí)證明了G為真。歸結(jié)原理證明定理思路 用歸結(jié)原理證明定理有些類似于“反證法”的思想。反證法：首先假定要證明的結(jié)論不成立 然后通過(guò)推導(dǎo)出與已知條件存在矛盾 反證出結(jié)論成立。 歸結(jié)法：首先對(duì)結(jié)論求反， 然后將已知條件和結(jié)論的否定合在一起 用子 句集表達(dá)。 如果該子句集存在矛

18、盾，則證明了結(jié)論的 正確性。2命題邏輯的歸結(jié) 命題邏輯，簡(jiǎn)單的說(shuō)，就是不含有變量的邏輯。 歸結(jié)式：對(duì)任意兩個(gè)子句C1和C2，若C1中有一個(gè)文字L1，而C2中有一個(gè)與L1成互補(bǔ)的文字L2，則分別從C1、C2中刪去L1和L2，并將其剩余部分組成新的析取式C12，則稱這個(gè)新子句為歸結(jié)式或預(yù)解式。 命題邏輯的歸結(jié)過(guò)程命題邏輯中，若給定公理集F和命題P，則歸結(jié)證明過(guò)程可歸納如下：把F轉(zhuǎn)化成子句集表示，得子句集S0；把命題P的否定式P也轉(zhuǎn)化成子句集表示，并將其加到S0中，得SS0Sp；對(duì)子句集S反復(fù)應(yīng)用歸結(jié)推理規(guī)則，直至導(dǎo)出含有空子句的擴(kuò)大子句集為止。即出現(xiàn)歸結(jié)式為空子句的情況時(shí)，表明已找到了矛盾，證明過(guò)

19、程結(jié)束。 例 證明子句集P乛Q,乛P,Q是不可滿足的。證(1)P乛Q(2)乛P(3)Q(4)乛Q 由(1),(2)(5) 由(3),(4)基于命題邏輯的歸結(jié)舉例P乛Q乛P乛QQ 例 用歸結(jié)原理證明 R 是 P, (PQ)R, (SU)Q, U 的邏輯結(jié)果。 證明步驟第一步將問(wèn)題轉(zhuǎn)換為子句集。 我們先把諸前提條件化為子句形式，再把結(jié)論R的非乛R也化為子句，由所有子句得到子句集S將 P, (PQ)R, (SU)Q, U化為子句集形式：(PQ)R乛(PQ) R(乛P 乛Q) R乛P 乛QR(SU)Q(1)乛(S U) Q(2) (乛S 乛U) Q(3) (乛SQ) (乛UQ)子句集：P,乛P 乛QR

20、, 乛SQ , 乛UQ, U,乛R第二步：然后對(duì)該子句集S進(jìn)行歸結(jié)。 如果從子句集S最后歸結(jié)出空子句，則子句集S不可滿足，從而間接證明R是真。P乛P乛QR乛SQ乛UQU乛R乛P 乛Q (2)和（6）乛Q (1)和（7）乛U (4)和(8) (5)和(9)子句集圖31 例3.12歸結(jié)演繹樹(shù) 在一階謂詞邏輯中應(yīng)用消解原理，不像命題邏輯中那樣簡(jiǎn)單，因?yàn)橹^詞邏輯中謂詞具有常量、變量和函數(shù)等變?cè)拇嬖冢@就使尋找含互否文字的子句對(duì)的操作變得復(fù)雜。例如： C1=P(x)Q(x) C2=乛P(a)R(y) 直接比較，似乎兩者中不含互否文字，但如果我們用a替換C1中的x，則得到 C1=P(a)Q(a) C2=

21、乛P(a)R(y)于是根據(jù)命題邏輯中的消解原理，得C1和C2的消解式： C3=Q(a)R(y) 謂詞邏輯的歸結(jié)合一（Unify） 在謂詞邏輯的歸結(jié)過(guò)程中，尋找項(xiàng)之間合適的變量置換使表達(dá)式一致是一個(gè)很重要的過(guò)程，這個(gè)過(guò)程稱為合一。 定義6 一個(gè)替換(Substitution)是形如 mgu= t1/x1,t2/x2,tn/xn的有限集合， 其中t1,t2,tn是項(xiàng)，稱為替換的分子； x1,x2,xn是互不相同的個(gè)體變?cè)?，稱為替換的分母；替換(Substitution)C1=P(x)Q(x)C2=乛P(a)R(y)做替換：mgu=a/x C1=P(a)Q(a) C2=乛P(a)R(y)于是根據(jù)命題

22、邏輯中的消解原理，得C1和C2的消解式： C3=Q(a)R(y)例3.21 求證G是A1和A2的邏輯結(jié)果。A1: x(P(x)(Q(x)R(x)A2: x(P(x)S(x)G: x(S(x)R(x) 證 我們用反證法，即證明A1A2乛G不可滿足。首先求得子句集S： (1)乛P(x)Q(x) (2)乛P(y)R(y) (3)P(a) (4)S(a) (5)乛S(z)乛R(z) (乛G) 然后應(yīng)用消解原理，得(6)R(a) (2),(3),mgu=a/y(7)乛R(a) (4),(5),mgu=a/z(8) (6),(7)所以S是不可滿足的，從而G是A1和A2的邏輯結(jié)果。 (A1) (A2) S例

23、 設(shè)已知：(1)能閱讀者是識(shí)字的；(2)海豚不識(shí)字；(3)有些海豚是很聰明的。試證明：有些聰明并不能閱讀。證 首先，定義如下謂詞：R(x)：x能閱讀。L(x)：x識(shí)字。I(x)：x是聰明的。D(x)：x是海豚。 然后把上述各語(yǔ)句翻譯為謂詞公式：(1) x(R(x)L(x)(2) x(D(x)乛L(x) 已知條件(3) x(D(x)I(x)(4) x(I(x)乛R(x) 需證結(jié)論 求題設(shè)與結(jié)論否定的子句集，得(1)乛R(x)L(x)(2)乛D(y)乛L(y)(3)D(a)(4)I(a)(5)乛I(z)R(z)歸結(jié)得(6) R(a) (5)，(4)，a/z(7) L (a) (6)，(1)，a/x

24、(8) 乛D(a) (7), (2), a/y(9) (8), (3)這個(gè)歸結(jié)過(guò)程的演繹樹(shù)如圖32所示。 圖3-2 例3.22 歸結(jié)演繹樹(shù) 練習(xí)1證明子句集P乛Q,乛P, Q是不可滿足的。練習(xí)2某公司招聘工作人員，有A,B,C三人應(yīng)聘，經(jīng)面試后，公司表示如下想法：（1）三人中至少錄取一人（2）如果錄取A而不錄取B,則一定錄取C（3）如果錄取B,則一定錄取C試用歸結(jié)原理求證：公司一定錄取C第一步：將問(wèn)題用謂詞公式表示前提：（1）三人中至少錄取一人 ： A B C （2）如果錄取A而不錄取B,則一定錄取C： (A乛B)C（3）如果錄取B,則一定錄取C ： BC結(jié)論：公司一定錄取C C第二步：將謂詞

25、公式轉(zhuǎn)化為子句集，并將結(jié)論的否定化為子句，也加入子句集（1）A B C（2）(A乛B)C乛(A乛B) C乛A BC (3) BC乛B C (4)乛C子句集：A B C，乛A BC，乛B C，乛C第三步 證明子句集是不可滿足的（1） A B C（2）乛A BC (3) 乛B C (4) 乛C (5) B C 由（1）（2） (6) C 由 (5) (3) (7) 由（4）（6）課堂練習(xí)問(wèn)題1：設(shè)已知公理集為P （1）（PQ）R（2）（ST）Q（3）T（4）求證R。 由（1）有子句集P；由（2）有： （PQ）R (PQ)R (PQR)得子句集：PQR由（3）有：(ST)Q (ST)Q (ST)Q

26、(SQ)(TQ)得子句集：SQ, TQ由（4）有子句集：(T)。由結(jié)論的否定得子句集：R將以上子句集并在一起有總的子句集：P，PQR，SQ，TQ，T，R命題邏輯的歸結(jié)演繹樹(shù) 一個(gè)經(jīng)典的歸結(jié)問(wèn)題例“快樂(lè)學(xué)生”問(wèn)題 假設(shè)：任何通過(guò)計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂(lè)的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎(jiǎng)。 求證：張是快樂(lè)的。 解：先定義謂詞： Pass(x, y) x可以通過(guò)y考試 Win(x, prize) x能獲得獎(jiǎng)勵(lì) Study(x) x肯學(xué)習(xí) Happy(x) x是快樂(lè)的 Lucky(x) x是幸運(yùn)的再將問(wèn)題用謂詞表示如下： “任何通過(guò)計(jì)算機(jī)考試并

27、獎(jiǎng)的人都是快樂(lè)的” (x)(Pass(x, computer)Win(x, prize)Happy(x) “任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過(guò)所有考試” (x) ( y) (Study(x)Lucky(x)Pass(x, y) “張不肯學(xué)習(xí)但他是幸運(yùn)的” Study(zhang)Lucky(zhang) “任何幸運(yùn)的人都能獲獎(jiǎng)” (x) (Lucky(x)Win(x, prize) 結(jié)論“張是快樂(lè)的”的否定 Happy(zhang)將上述謂詞公式轉(zhuǎn)化為子句集如下： (1) Pass(x, computer)Win(x, prize)Happy(x) (2) Study(y)Pass(y, z) (

28、3) Lucky(u)Pass(u, v) (4) Study(zhang) (5) Lucky(zhang) (6) Lucky(w)Win(w, prize) (7) Happy(zhang) (結(jié)論的否定) Exciting(Liming)Happy(z)Exciting(z)Happy(Liming)Happy(x)Smart(x)Happy(x)Poor(Liming)Smart(Liming)Read(y)Smart(y )Poor(Liming)Read(Liming)Poor(Liming)Read(Liming)Read(Liming) NILLiming/zLiming/x

29、Liming/y歸結(jié)演繹推理的歸結(jié)策略 廣度優(yōu)先是一種窮盡子句比較的復(fù)雜搜索方法。設(shè)初始子句集為S0，廣度優(yōu)先策略的歸結(jié)過(guò)程可描述如下： (1) 從S0出發(fā)，對(duì)S0中的全部子句作所有可能的歸結(jié)，得到第一層歸結(jié)式，把這些歸結(jié)式的集合記為S1; (2) 用S0中的子句與S1中的子句進(jìn)行所有可能的歸結(jié)，得到第二層歸結(jié)式，把這些歸結(jié)式的集合記為S2; (3) 用S0和S1中的子句與S2中的子句進(jìn)行所有可能的歸結(jié)，得到第三層歸結(jié)式，把這些歸結(jié)式的集合記為S3; 如此繼續(xù)，知道得出空子句或不能再繼續(xù)歸結(jié)為止。 例 設(shè)有如下子句集： S=I(x)R(x), I(a), R(y)L(y), L(a) 用寬度優(yōu)

30、先策略證明S為不可滿足。 寬度優(yōu)先策略的歸結(jié)樹(shù)如下： 歸結(jié)演繹推理的歸結(jié)策略1. 廣度優(yōu)先策略（2/3）I(x)R(x)I(a)R(y)L(y)L(a)R(a)I(x) L(x)R(a)L(a)L(a)I(a)I(a)NILSS1S2歸結(jié)演繹推理的歸結(jié)策略1. 廣度優(yōu)先策略（3/3） 從這個(gè)例子可以看出，寬度優(yōu)先策略歸結(jié)出了許多無(wú)用的子句，既浪費(fèi)事間，又浪費(fèi)空間。但是，這種策略由一個(gè)有趣的特性，就是當(dāng)問(wèn)題有解時(shí)保證能找到最短歸結(jié)路徑。 因此，它是一種完備的歸結(jié)策略。寬度優(yōu)先對(duì)大問(wèn)題的歸結(jié)容易產(chǎn)生組合爆炸，但對(duì)小問(wèn)題卻仍是一種比較好的歸結(jié)策略。歸結(jié)演繹推理的歸結(jié)策略2. 支持集策略（1/3） 支

31、持集策略是沃斯(Wos)等人在1965年提出的一種歸結(jié)策略。它要求每一次參加歸結(jié)的兩個(gè)親本子句中，至少應(yīng)該有一個(gè)是由目標(biāo)公式的否定所得到的子句或它們的后裔?？梢宰C明支持集策略是完備的，即當(dāng)子句集為不可滿足時(shí)，則由支持集策略一定能夠歸結(jié)出一個(gè)空子句。也可以把支持集策略看成是在寬度優(yōu)先策略中引入了某種限制條件，這種限制條件代表一種啟發(fā)信息，因而有較高的效率 例 設(shè)有如下子句集： S=I(x)R(x), I(a), R(y)L(y), L(a) 其中，I(x)R(x)為目標(biāo)公式的否定。用支持集策略證明S為不可滿足。歸結(jié)演繹推理的歸結(jié)策略2. 支持集策略（2/3）I(x)R(x)I(a) R(y)L(

32、y)L(a)R(a)I(x)L(x)L(a)L(a)I(a)NIL歸結(jié)演繹推理的歸結(jié)策略2. 支持集策略（3/3） 從上述歸結(jié)過(guò)程可以看出，各級(jí)歸結(jié)式數(shù)目要比寬度優(yōu)先策略生成的少，但在第二級(jí)還沒(méi)有空子句。就是說(shuō)這種策略限制了子句集元素的劇增，但會(huì)增加空子句所在的深度。此外，支持集策略具有逆向推理的含義，由于進(jìn)行歸結(jié)的親本子句中至少有一個(gè)與目標(biāo)子句有關(guān)，因此推理過(guò)程可以看作是沿目標(biāo)、子目標(biāo)的方向前進(jìn)的。 歸結(jié)演繹推理的歸結(jié)策略3. 刪除策略（2/2）重言式刪除法 如果一個(gè)子句中包含有互補(bǔ)的文字對(duì)，則稱該子句為重言式。例如 P(x)P(x), P(x)Q(x)P(x) 都是重言式，不管P(x)的真

33、值為真還是為假，P(x)P(x)和P(x)Q(x)P(x)都均為真。 重言式是真值為真的子句。對(duì)一個(gè)子句集來(lái)說(shuō)，不管是增加還是刪除一個(gè)真值為真的子句，都不會(huì)影響該子句集的不可滿足性。因此，可從子句集中刪去重言式。歸結(jié)演繹推理的歸結(jié)策略4. 單文字子句策略（1/2） 如果一個(gè)子句只包含一個(gè)文字，則稱此子句為單文字子句。單文字子句策略是對(duì)支持集策略的進(jìn)一步改進(jìn)，它要求每次參加歸結(jié)的兩個(gè)親本子句中至少有一個(gè)子句是單文字子句。例 設(shè)有如下子句集： S=I(x)R(x), I(a), R(y)L(y), L(a) 用單文字子句策略證明S為不可滿足。 采用單文字子句策略，歸結(jié)式包含的文字?jǐn)?shù)將少于其親本子句中的文字?jǐn)?shù)，這將有利于向空子句的方向發(fā)展，因此會(huì)有較高的歸結(jié)效率。但這種策略是不完備的，即當(dāng)子句集為不可滿足時(shí)，用這種策略不一定能歸結(jié)出空子句。歸結(jié)演繹推理的歸結(jié)策略4. 單文字子句策略（2/2）I(x)R(x)I(a)R(y)L(y)L(a)R(a)R(a)NIL歸結(jié)演繹推理的歸結(jié)策略5. 線形輸入策