第三章 確定性推理方法

1、第第 3 章章 確定性推理方法確定性推理方法知識(shí)知識(shí) 智能智能？ 知識(shí)知識(shí) 推理推理智能智能！5個(gè)房間的問題（給福爾摩斯出的問題）個(gè)房間的問題（給福爾摩斯出的問題）5個(gè)不同顏色的房間，每間有個(gè)不同國(guó)籍的人，每人有自己喜歡的飲個(gè)不同顏色的房間，每間有個(gè)不同國(guó)籍的人，每人有自己喜歡的飲料，香煙和寵物，已知信息料，香煙和寵物，已知信息：1.英國(guó)人住在紅房間里；英國(guó)人住在紅房間里；2.西班牙人有一條狗；西班牙人有一條狗；3.挪威人住在左邊第一個(gè)房間里；挪威人住在左邊第一個(gè)房間里；4.黃房間的人在抽庫(kù)爾斯牌香煙；黃房間的人在抽庫(kù)爾斯牌香煙；5.抽切斯菲爾德牌香煙的人是養(yǎng)了一只狐貍的人的鄰居；抽切斯菲爾德

2、牌香煙的人是養(yǎng)了一只狐貍的人的鄰居；6.挪威人住在藍(lán)房間隔壁；挪威人住在藍(lán)房間隔壁；7.抽溫斯頓牌香煙的人有一只蝸牛；抽溫斯頓牌香煙的人有一只蝸牛；8.抽幸運(yùn)牌香煙的人喝橘子汁；抽幸運(yùn)牌香煙的人喝橘子汁；9.烏克蘭人喝茶；烏克蘭人喝茶；10.日本人抽國(guó)會(huì)牌香煙；日本人抽國(guó)會(huì)牌香煙；11.抽庫(kù)爾斯牌香煙的人的房間在有匹馬的房間隔壁；抽庫(kù)爾斯牌香煙的人的房間在有匹馬的房間隔壁；12.綠房間的人喝咖啡；綠房間的人喝咖啡；13.中間房間的人喝牛奶中間房間的人喝牛奶14.綠房間的人在白房間的隔壁綠房間的人在白房間的隔壁F問題：?jiǎn)栴}： 哪個(gè)房間的人喝水？斑馬在哪個(gè)房間？哪個(gè)房間的人喝水？斑馬在哪個(gè)房間？房

3、間號(hào)房間號(hào)12345顏色顏色國(guó)籍國(guó)籍香煙香煙飲料飲料寵物寵物3.挪威人住在左邊第一個(gè)房間挪威人住在左邊第一個(gè)房間6.挪威人住在藍(lán)房間旁邊挪威人住在藍(lán)房間旁邊13.中間房間的人喝牛奶中間房間的人喝牛奶挪威人挪威人藍(lán)色藍(lán)色牛奶牛奶12.綠房間的人喝咖啡綠房間的人喝咖啡14.綠房間的人在白房間的隔壁綠房間的人在白房間的隔壁綠色綠色白色白色咖啡咖啡1.英國(guó)人住在紅色的房間英國(guó)人住在紅色的房間紅色紅色英國(guó)人英國(guó)人黃色黃色4.黃房間的人抽庫(kù)爾斯牌香煙黃房間的人抽庫(kù)爾斯牌香煙11.抽庫(kù)爾斯牌煙的房間在有匹馬的房間的隔壁抽庫(kù)爾斯牌煙的房間在有匹馬的房間的隔壁庫(kù)爾斯牌庫(kù)爾斯牌馬馬水水2.西班牙人有一條狗西班牙人

4、有一條狗8.抽幸運(yùn)牌香煙的人喝橘子汁抽幸運(yùn)牌香煙的人喝橘子汁9.烏克蘭人喝茶烏克蘭人喝茶10.日本人抽國(guó)會(huì)牌香煙日本人抽國(guó)會(huì)牌香煙橘子汁是誰(shuí)喝的？橘子汁橘子汁狗狗幸運(yùn)牌幸運(yùn)牌西班牙人西班牙人茶茶烏克蘭人烏克蘭人日本人日本人國(guó)會(huì)牌國(guó)會(huì)牌7.抽溫斯頓牌香煙的人有一只蝸牛抽溫斯頓牌香煙的人有一只蝸牛溫斯頓溫斯頓蝸牛蝸牛切斯菲爾德切斯菲爾德5.抽切斯菲爾德香煙的人的抽切斯菲爾德香煙的人的是養(yǎng)了一只狐貍的人的鄰居是養(yǎng)了一只狐貍的人的鄰居狐貍狐貍斑馬斑馬8.抽幸運(yùn)牌香煙的人喝橘子汁抽幸運(yùn)牌香煙的人喝橘子汁9.烏克蘭人喝茶烏克蘭人喝茶用用Prolog語(yǔ)言編的程序，一秒鐘都不到就知道了語(yǔ)言編的程序，一秒鐘都不

5、到就知道了答案答案, ,不過它的推理過程和人的完全不一樣；不過它的推理過程和人的完全不一樣；Prolog：Programm Logic ( (邏輯程序設(shè)計(jì)語(yǔ)言邏輯程序設(shè)計(jì)語(yǔ)言) )推理方法：確定性推理推理方法：確定性推理：（演繹推理）：（演繹推理） （1 1）謂詞公式化為子句集謂詞公式化為子句集 （2 2）魯賓遜歸結(jié)原理（消解原理）魯賓遜歸結(jié)原理（消解原理） （3 3）歸結(jié)反演）歸結(jié)反演機(jī)器證明機(jī)器證明歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理 3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法 3.4 海伯倫定理

6、海伯倫定理 3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理 3.6 歸結(jié)反演歸結(jié)反演 3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 3.1 推理的基本概念3.1.1 推理的定義推理的定義3.1.2 推理方式及其分類推理方式及其分類3.1.3 推理的方向推理的方向3.1.4 沖突消解策略沖突消解策略推 理 機(jī)數(shù) 據(jù) 庫(kù)知 識(shí) 庫(kù)專 家病 人醫(yī)療專家系統(tǒng)醫(yī)療專家系統(tǒng)3.1.1 推理的定義某 種 策 略已 知 事 實(shí)（ 證 據(jù) ）知 識(shí)結(jié) 論知識(shí)知識(shí)專家的經(jīng)驗(yàn)、醫(yī)學(xué)常識(shí)專家的經(jīng)驗(yàn)、醫(yī)學(xué)常識(shí)初始初始證據(jù)證據(jù)病人的癥狀、化驗(yàn)結(jié)果病人的癥狀、化驗(yàn)結(jié)果證據(jù)證據(jù)中間結(jié)論中間結(jié)論推理：推理：3.1 推理的基本概念3.

7、1.1 推理的定義推理的定義3.1.2 推理方式及其分類推理方式及其分類3.1.3 推理的方向推理的方向3.1.4 沖突消解策略沖突消解策略（1）演繹推理演繹推理 (deductive reasoning) : 一般一般 個(gè)別個(gè)別 三段論式三段論式（三段論法）（三段論法） 足球運(yùn)動(dòng)員的身體都是強(qiáng)壯的足球運(yùn)動(dòng)員的身體都是強(qiáng)壯的 ； 高波是一名足球運(yùn)動(dòng)員；高波是一名足球運(yùn)動(dòng)員； 所以，高波的身體是強(qiáng)壯的。所以，高波的身體是強(qiáng)壯的。3.1.2 推理方式及其分類1.演繹推理、歸納推理、默認(rèn)推理演繹推理、歸納推理、默認(rèn)推理（ 大前提大前提 ）（ 小前提小前提 ）（ 結(jié)結(jié) 論論 ）3.1.2 推理方式及其

8、分類1.演繹推理、歸納推理、默認(rèn)推理（按推出結(jié)論的途徑演繹推理、歸納推理、默認(rèn)推理（按推出結(jié)論的途徑）（2）歸納推理歸納推理 (inductive reasoning): 個(gè)別個(gè)別 一般一般 完全歸納推理（完全歸納推理（必然性推理）必然性推理） 不完全歸納推理不完全歸納推理（非必然性推理）（非必然性推理）檢查全部產(chǎn)品合格檢查全部產(chǎn)品合格該廠產(chǎn)品合格該廠產(chǎn)品合格完全歸納推理完全歸納推理檢查全部樣品合格檢查全部樣品合格該廠產(chǎn)品合格該廠產(chǎn)品合格不完全歸納推理不完全歸納推理 3.1.2 推理方式及其分類（3）默認(rèn)推理默認(rèn)推理（default reasoning，缺省推理），缺省推理）n 知識(shí)不完全知識(shí)

9、不完全的情況下假設(shè)的情況下假設(shè)某些條件已經(jīng)具備某些條件已經(jīng)具備所進(jìn)行的推理所進(jìn)行的推理。 結(jié)結(jié) 論論 A 成立成立 B 成立？成立？（在不能證明（在不能證明B不成立的情況下，默認(rèn)不成立的情況下，默認(rèn)B成立）成立）鳥籠要鳥籠要有蓋子有蓋子 制造鳥籠制造鳥籠 鳥會(huì)飛？鳥會(huì)飛？（正常情況下默認(rèn)鳥會(huì)飛成立）（正常情況下默認(rèn)鳥會(huì)飛成立）1.演繹推理、歸納推理、默認(rèn)推理演繹推理、歸納推理、默認(rèn)推理3.1.2 推理方式及其分類 2. 確定性推理、不確定性推理（按知識(shí)的確定性）確定性推理、不確定性推理（按知識(shí)的確定性）似然推理近似推理或模糊推理不確定性推理（概率論）（模糊邏輯）（1）確定性推理確定性推理：推理

10、時(shí)所用的知識(shí)與證據(jù)都是確定的，推推理時(shí)所用的知識(shí)與證據(jù)都是確定的，推出的結(jié)論也是確定的，其真值或者為真或者為假。出的結(jié)論也是確定的，其真值或者為真或者為假。 （2）不確定性不確定性推理推理：推理時(shí)所用的知識(shí)與證據(jù)不都是確定的，推理時(shí)所用的知識(shí)與證據(jù)不都是確定的，推出的結(jié)論也是不確定的。推出的結(jié)論也是不確定的。X：鳥：鳥 X：會(huì)飛：會(huì)飛3.1.2 推理方式及其分類 3. 單調(diào)推理、非單調(diào)推理（按靠近結(jié)論的方式）單調(diào)推理、非單調(diào)推理（按靠近結(jié)論的方式） （1）單調(diào)推理單調(diào)推理：隨著推理向前推進(jìn)及新知識(shí)的加入：隨著推理向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論越來越接近最終目標(biāo)。，推出的結(jié)論越來越接近最終目

11、標(biāo)。 （2）非單調(diào)推理非單調(diào)推理：由于新知識(shí)的加入，不僅沒有加：由于新知識(shí)的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使推理退回到前強(qiáng)已推出的結(jié)論，反而要否定它，使推理退回到前面的某一步，重新開始。面的某一步，重新開始。 默認(rèn)推理是非單調(diào)推理默認(rèn)推理是非單調(diào)推理 基于經(jīng)典邏輯的演繹推理基于經(jīng)典邏輯的演繹推理 X：企鵝：企鵝X：不會(huì)飛：不會(huì)飛X：不會(huì)飛：不會(huì)飛3.1.2 推理方式及其分類4啟發(fā)式推理、非啟發(fā)式推理（是否運(yùn)用啟發(fā)式知識(shí)）啟發(fā)式推理、非啟發(fā)式推理（是否運(yùn)用啟發(fā)式知識(shí)） 啟發(fā)性知識(shí)啟發(fā)性知識(shí)：與問題有關(guān)且能加快推理過程、提高搜索效率與問題有關(guān)且能加快推理過程、提高搜索效率的知識(shí)。的

12、知識(shí)。 目標(biāo)：在腦膜炎、肺炎、流感中選擇一個(gè)目標(biāo)：在腦膜炎、肺炎、流感中選擇一個(gè) 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則 r1：腦膜炎：腦膜炎 r2：肺：肺 炎炎 r3：流：流 感感 啟發(fā)式知識(shí)：?jiǎn)l(fā)式知識(shí)：“腦膜炎危險(xiǎn)腦膜炎危險(xiǎn)”、“目前正在盛行流目前正在盛行流感感”。3.1 推理的基本概念3.1.1 推理的定義推理的定義3.1.2 推理方式及其分類推理方式及其分類3.1.3 推理的方向推理的方向3.1.4 沖突消解策略沖突消解策略3.1.3 推理的方向正向推理逆向推理( 反向推理)雙向推理混合推理推理方向3.1.3 推理的方向n 正向推理（事實(shí)驅(qū)動(dòng)推理）正向推理（事實(shí)驅(qū)動(dòng)推理）: 已知事實(shí)已知事實(shí) 結(jié)論結(jié)論

13、 基本思想基本思想（1）從初始已知事實(shí)出發(fā)，在知識(shí)庫(kù)）從初始已知事實(shí)出發(fā)，在知識(shí)庫(kù)KB中找出當(dāng)前可適用的中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用知識(shí)集知識(shí)，構(gòu)成可適用知識(shí)集KS。（2）按某種沖突消解策略從）按某種沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理，并中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入到數(shù)據(jù)庫(kù)將推出的新事實(shí)加入到數(shù)據(jù)庫(kù)DB中作為下一步推理的已知事中作為下一步推理的已知事實(shí)，再在實(shí)，再在KB中選取可適用知識(shí)構(gòu)成中選取可適用知識(shí)構(gòu)成KS 。（3）重復(fù)（）重復(fù)（2），直到求得問題的解或），直到求得問題的解或KB中再無可適用的知中再無可適用的知識(shí)。識(shí)。1. 正向推理正向推理3.1.3 推理的方

14、向n 實(shí)現(xiàn)正向推理需要解決的問題：實(shí)現(xiàn)正向推理需要解決的問題：l 確定匹配（知識(shí)與已知事實(shí)）的方法。確定匹配（知識(shí)與已知事實(shí)）的方法。l 按什么策略搜索知識(shí)庫(kù)。按什么策略搜索知識(shí)庫(kù)。l 沖突消解策略。沖突消解策略。 正向推理簡(jiǎn)單，易實(shí)現(xiàn)，但目的性不強(qiáng)，效正向推理簡(jiǎn)單，易實(shí)現(xiàn)，但目的性不強(qiáng)，效率低。率低。1. 正向推理正向推理3.1.3 推理的方向n 逆向推理（目標(biāo)驅(qū)動(dòng)推理）：以逆向推理（目標(biāo)驅(qū)動(dòng)推理）：以某個(gè)假設(shè)目標(biāo)某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)。作為出發(fā)點(diǎn)。 基本思想：基本思想： 選定一個(gè)假設(shè)目標(biāo)。選定一個(gè)假設(shè)目標(biāo)。 尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則原假設(shè)尋找支持該假設(shè)的證據(jù)，若所需的

15、證據(jù)都能找到，則原假設(shè)成立；若無論如何都找不到所需要的證據(jù)，說明原假設(shè)不成立成立；若無論如何都找不到所需要的證據(jù)，說明原假設(shè)不成立的；為此需要另作新的假設(shè)。的；為此需要另作新的假設(shè)。 主要優(yōu)點(diǎn)：不必使用與目標(biāo)無關(guān)的知識(shí)，目的性強(qiáng)，同時(shí)它主要優(yōu)點(diǎn)：不必使用與目標(biāo)無關(guān)的知識(shí)，目的性強(qiáng)，同時(shí)它還有利于向用戶提供解釋。還有利于向用戶提供解釋。 主要缺點(diǎn)：起始目標(biāo)的選擇有盲目性。主要缺點(diǎn)：起始目標(biāo)的選擇有盲目性。2. 逆向推理逆向推理3.1.3 推理的方向n 逆向推理需要解決的問題：逆向推理需要解決的問題：u 如何判斷一個(gè)假設(shè)是否是證據(jù)？如何判斷一個(gè)假設(shè)是否是證據(jù)？u 當(dāng)導(dǎo)出假設(shè)的知識(shí)有多條時(shí)，如何確定

16、先選哪一條？當(dāng)導(dǎo)出假設(shè)的知識(shí)有多條時(shí)，如何確定先選哪一條？ u一條知識(shí)的運(yùn)用條件一般都有多個(gè)，當(dāng)其中的一個(gè)經(jīng)一條知識(shí)的運(yùn)用條件一般都有多個(gè)，當(dāng)其中的一個(gè)經(jīng)驗(yàn)證成立后，如何自動(dòng)地?fù)Q為對(duì)另一個(gè)的驗(yàn)證？驗(yàn)證成立后，如何自動(dòng)地?fù)Q為對(duì)另一個(gè)的驗(yàn)證？u . 逆向推理：目的性強(qiáng)，利于向用戶提供解釋，但選擇初始逆向推理：目的性強(qiáng)，利于向用戶提供解釋，但選擇初始目標(biāo)時(shí)具有盲目性，比正向推理復(fù)雜。目標(biāo)時(shí)具有盲目性，比正向推理復(fù)雜。2. 逆向推理逆向推理3.1.3 推理的方向n 正向推理正向推理: 盲目、效率低。盲目、效率低。 逆向推理逆向推理: 若提出的假設(shè)目標(biāo)不符合實(shí)際，會(huì)降低效率。若提出的假設(shè)目標(biāo)不符合實(shí)際，

17、會(huì)降低效率。 正反向混合推理：正反向混合推理：（1）先正向后逆向：先正向后逆向：先進(jìn)行正向推理，幫助選擇某個(gè)目標(biāo)，即先進(jìn)行正向推理，幫助選擇某個(gè)目標(biāo)，即從已知事實(shí)演繹出部分結(jié)果，然后再用逆向推理證實(shí)該目標(biāo)或從已知事實(shí)演繹出部分結(jié)果，然后再用逆向推理證實(shí)該目標(biāo)或提高其可信度；提高其可信度；（2）先逆向后正向：先逆向后正向：先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后再利先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后再利用逆向推理中得到的信息進(jìn)行正向推理，以推出更多的結(jié)論用逆向推理中得到的信息進(jìn)行正向推理，以推出更多的結(jié)論。3. 混合推理混合推理n 雙向推理雙向推理：正向推理與逆向推理同時(shí)進(jìn)行，且在推理過程中正向推理與逆向

18、推理同時(shí)進(jìn)行，且在推理過程中的某一步驟上的某一步驟上“碰頭碰頭”的一種推理。的一種推理。已知事實(shí)已知事實(shí) 假設(shè)目標(biāo)假設(shè)目標(biāo)3.1.3 推理的方向4. 雙向推理雙向推理中間結(jié)論中間結(jié)論證證 據(jù)據(jù)3.1 推理的基本概念3.1.1 推理的定義推理的定義3.1.2 推理方式及其分類推理方式及其分類3.1.3 推理的方向推理的方向3.1.4 沖突消解策略沖突消解策略3.1.4 沖突消解策略 已知事實(shí)與知識(shí)的三種匹配情況已知事實(shí)與知識(shí)的三種匹配情況：（1）恰好匹配成功（一對(duì)一）；）恰好匹配成功（一對(duì)一）；（2）不能匹配成功；）不能匹配成功；（3）多種匹配成功多種匹配成功（一對(duì)多、多對(duì)一、多對(duì)多）（一對(duì)多、

19、多對(duì)一、多對(duì)多）沖突消解沖突消解3.1.4 沖突消解策略 多種沖突消解策略：多種沖突消解策略：（1）按針對(duì)性排序）按針對(duì)性排序（2）按已知事實(shí)的新鮮性排序）按已知事實(shí)的新鮮性排序（3）按匹配度排序）按匹配度排序（4）按條件個(gè)數(shù)排序）按條件個(gè)數(shù)排序（5）按上下文限制排序）按上下文限制排序（6）按冗余限制排序）按冗余限制排序（7）根據(jù)領(lǐng)域問題的特點(diǎn)排序）根據(jù)領(lǐng)域問題的特點(diǎn)排序r1: IF A1 AND A2 THEN H1r2: IF A1 AND A2 AND A3 AND A4 THEN H2第3章 確定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理 3.3

20、 謂詞公式化為子句集的方法謂詞公式化為子句集的方法 3.4 海伯倫定理海伯倫定理 3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理 3.6 歸結(jié)反演歸結(jié)反演 3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 27 定義定義1 設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域，若對(duì)D上的任何一個(gè)解釋，P與Q都有相同的真值，則稱公式P和Q在D上是等價(jià)的。如果D是任意個(gè)體域，則稱P和Q是等價(jià)的，記為P Q 。常用的等價(jià)式見P32（4）德.摩根律(De. Morgen) （8）連接詞化規(guī)律（蘊(yùn)含、等價(jià)等值式）連接詞化規(guī)律（蘊(yùn)含、等價(jià)等值式） （10）量詞轉(zhuǎn)換律）量詞轉(zhuǎn)換律 3.2 自然演繹推理自然演繹推理自然演繹推理

21、：從一組已知為真的事實(shí)出發(fā)，運(yùn)用從一組已知為真的事實(shí)出發(fā)，運(yùn)用經(jīng)典經(jīng)典邏輯的推理規(guī)則邏輯的推理規(guī)則推出結(jié)論的過程。推出結(jié)論的過程。28 定義定義2 對(duì)于謂詞公式對(duì)于謂詞公式P與與Q，如果，如果PQ永真，則稱公式永真，則稱公式P永永真蘊(yùn)含真蘊(yùn)含Q，且稱，且稱Q為為P的邏輯結(jié)論，稱的邏輯結(jié)論，稱P為為Q的前提，記為的前提，記為P Q。常用的永真蘊(yùn)含式見常用的永真蘊(yùn)含式見P33（3）假言推理）假言推理 （4）拒取式推理）拒取式推理 （5）假言三段論）假言三段論 3.2 自然演繹推理29謂詞邏輯的其他推理規(guī)則謂詞邏輯的其他推理規(guī)則1. P規(guī)則：在推理的任何步驟上都可引入前提。規(guī)則：在推理的任何步驟上都

22、可引入前提。2. T規(guī)則：在推理過程中，如果前面步驟中有一個(gè)或多個(gè)規(guī)則：在推理過程中，如果前面步驟中有一個(gè)或多個(gè)公式永真蘊(yùn)含公式公式永真蘊(yùn)含公式S，則可把，則可把S引入推理過程中引入推理過程中。3. CP規(guī)則：如果能從任意引入的命題規(guī)則：如果能從任意引入的命題R和前提集合中推出和前提集合中推出S來，則可從前提集合推出來，則可從前提集合推出R S來。來。3.2 自然演繹推理30 所有的人都是會(huì)死的，所有的人都是會(huì)死的， 因?yàn)橹T葛亮是人，因?yàn)橹T葛亮是人， Human（Zhugeliang） 所以諸葛亮是會(huì)死的。所以諸葛亮是會(huì)死的。 Die（Zhugeliang） 1 P規(guī)則規(guī)則 2 Human（Z

23、hugeliang） P規(guī)則規(guī)則 1, 2 Die（Zhugeliang） T規(guī)則規(guī)則 QQPP , )3()()(xDiexHumanx)()(xDiexHumanx3.2 自然演繹推理31謂詞邏輯的其他推理規(guī)則謂詞邏輯的其他推理規(guī)則：4.4.反證法：反證法：PQ ，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) PQF，即即Q為為P的邏輯結(jié)的邏輯結(jié)論，當(dāng)且僅當(dāng)論，當(dāng)且僅當(dāng)PQ是不可滿足的是不可滿足的。 定理：定理：Q為為P1,P2,Pn 的邏輯結(jié)論的邏輯結(jié)論，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) P1 P2, Pn Q 是不可滿足的是不可滿足的。3.2 自然演繹推理推理規(guī)則推理規(guī)則：P規(guī)則、規(guī)則、T規(guī)則、假言推理、拒取式推理規(guī)則、假言推理

24、、拒取式推理 3.2 自然演繹推理n 假言推理假言推理： P, PQ Q n “如果如果x是金屬，則是金屬，則x能導(dǎo)電能導(dǎo)電” , “銅是金屬銅是金屬” 推出推出 “銅能導(dǎo)銅能導(dǎo)電電” n 拒取式推理拒取式推理： PQ, Q Pn “如果下雨，則地下就濕如果下雨，則地下就濕” , “地上不濕地上不濕” 推出推出 “沒有下雨沒有下雨”（1） 如果下雨，則地上是濕的（如果下雨，則地上是濕的（ PQ ）；（2）沒有下雨（）沒有下雨（P ）；）； （3）所以，地上不濕（所以，地上不濕（Q ）。 3.2 自然演繹推理 錯(cuò)誤錯(cuò)誤1否定前件否定前件： PQ, P Q（1）如果行星系統(tǒng)是以太陽(yáng)為中心的，則金星

25、會(huì)顯示出位相變?nèi)绻行窍到y(tǒng)是以太陽(yáng)為中心的，則金星會(huì)顯示出位相變化（化（ PQ ）；（2）金星顯示出位相變化（金星顯示出位相變化（ Q ）；）；（3） 所以，行星系統(tǒng)是以太陽(yáng)為中心（所以，行星系統(tǒng)是以太陽(yáng)為中心（ P ）。 錯(cuò)誤錯(cuò)誤2肯定后件肯定后件： PQ, Q P3.2 自然演繹推理 例例1 已知事實(shí)：已知事實(shí)： （1）凡是容易的課程小王凡是容易的課程小王( Wang )都喜歡；都喜歡； （2）C 班的課程都是容易的；班的課程都是容易的； （3）ds 是是 C 班的一門課程。班的一門課程。 求證：小王喜歡求證：小王喜歡 ds 這門課程。這門課程。3.2 自然演繹推理 證明：證明：定義謂詞定

26、義謂詞： EASY ( x )：x 是容易的是容易的 LIKE ( x, y )：x 喜歡喜歡 y C ( x )：x 是是 C 班的一門課程班的一門課程 已知事實(shí)和結(jié)論用謂詞公式表示已知事實(shí)和結(jié)論用謂詞公式表示： ( x) ( EASY ( x ) LIKE ( Wang, x ) ) ( x) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ) 3.2 自然演繹推理 應(yīng)用推理規(guī)則進(jìn)行推理應(yīng)用推理規(guī)則進(jìn)行推理： ( x)（EASY ( x ) LIKE ( Wang, x ) EASY (z) LIKE ( Wang, z ) 全稱固化全稱固化 (

27、 x ) (C ( x ) EASY ( x ) C ( y ) EASY ( y ) 全稱固化全稱固化 所以 C (ds), C (y) EASY (y) EASY (ds) P規(guī)則及假言推理規(guī)則及假言推理 所以 EASY (ds), EASY (z) LIKE (Wang，z) LIKE ( Wang, ds ) T規(guī)則及假言推理規(guī)則及假言推理 優(yōu)點(diǎn)：優(yōu)點(diǎn)：n表達(dá)定理證明過程自然，易理解。表達(dá)定理證明過程自然，易理解。n擁有豐富的推理規(guī)則，推理過程靈活。擁有豐富的推理規(guī)則，推理過程靈活。n便于嵌入領(lǐng)域啟發(fā)式知識(shí)便于嵌入領(lǐng)域啟發(fā)式知識(shí)。3.2 自然演繹推理 缺點(diǎn)缺點(diǎn)：易產(chǎn)生組合爆炸，得到的中

28、間結(jié)論一般呈指易產(chǎn)生組合爆炸，得到的中間結(jié)論一般呈指數(shù)形式遞增。數(shù)形式遞增。歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理 3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法 3.4 海伯倫定理海伯倫定理 3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理 3.6 歸結(jié)反演歸結(jié)反演 3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 3.3 謂詞公式化為子句集的方法 原子（原子（atom）謂詞公式：）謂詞公式： 一個(gè)不能再分解的命題。一個(gè)不能再分解的命題。 文字（文字（literal）：原子謂詞公式及其否定。）：原子謂詞公式及其否定

29、。 ：正文字，：正文字， ：負(fù)文字。：負(fù)文字。（封閉世界假設(shè)）（封閉世界假設(shè)） 子句（子句（clause）：任何文字的）：任何文字的析取式析取式。任何文字本身也都是子句。任何文字本身也都是子句。 空子句（空子句（NIL）：不包含任何文字的子句。）：不包含任何文字的子句。 子句集：由子句子句集：由子句構(gòu)成的集合。構(gòu)成的集合。PP)(,()(,(),()(xgxQxfxPxQxP空子句是永假的，不可滿足的?？兆泳涫怯兰俚?，不可滿足的。3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法)()()()(),()()()()(xBxPxxQyxSyxQxPx 例例2 將下列將下列謂詞公式化為子句集

30、。謂詞公式化為子句集。解：（1）消去謂詞公式中的“ ”和“ ”符號(hào),QPQP)()(QPQPQP)()()()(),()()()()(xBxPxxQyxSyxQxPx （2）把否定符號(hào)）把否定符號(hào)” ” 移到緊靠謂詞的位置上移到緊靠謂詞的位置上雙重否定律雙重否定律 德德.摩根律摩根律 量詞轉(zhuǎn)換律量詞轉(zhuǎn)換律 PP )(,)(QPQPQPQP)(PxPx)()(,)()(PxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx （3）變量標(biāo)準(zhǔn)化）變量標(biāo)準(zhǔn)化 )()()()(yPyxPx),()()()(yPyxPx)()()()(),()()()()(wBwPwxQyxSyx

31、QxPx （4）消去存在量詞）消去存在量詞 a. 存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)。存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)。 b. 存在量詞出現(xiàn)存在量詞出現(xiàn)在一個(gè)或者多個(gè)全稱量詞的轄域內(nèi)。在一個(gè)或者多個(gè)全稱量詞的轄域內(nèi)。Skolem1212()()()() (, ).)nnxxxy P x xxyy 對(duì)對(duì)于于一一般般情情況況存存在在量量詞詞 的的函函數(shù)數(shù)為為),(21nxxxfySkolem化：用化：用Skolem函數(shù)代替每個(gè)存在量詞量化的變量的過程。函數(shù)代替每個(gè)存在量詞量化的變量的過程。 （5）化為前束形）化為前束形 前束形前束形=（前綴）（前綴）母式母式（前綴）：全稱量詞串。（前綴）：全稱量詞串

32、。 母式母式：不含量詞的謂詞公式。：不含量詞的謂詞公式。 3.3 謂詞公式化為子句集的方法)()()()()(,()()()(wBwPwxQxfxSxQxPx)( xfy )()()()(,()()()(wBwPxQxfxSxQxPwx)()()()(),()()()()(wBwPwxQyxSyxQxPx 3.3 謂詞公式化為子句集的方法（6）化為）化為 Skolem 標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形 Skolem 標(biāo)準(zhǔn)形：M：子句的合取式，稱為Skolem標(biāo)準(zhǔn)形的母式。 Mxxxn)()(21)()()(RPQPRQP)()()(RPQPRQP（7）略去全稱量詞）略去全稱量詞 （8）消去合取詞）消去合取詞 （9

33、）子句變量標(biāo)準(zhǔn)化）子句變量標(biāo)準(zhǔn)化 )()()(,()()()()(wBwPxfxSxQxPxQwx)()()(,()()()(wBwPxfxSxPxQwx)()()(,()()(wBwPxfxSxPxQ)()(wBwP),(xQ),(,()(xfxSxP),(xQ),(,()(yfySyP)()(wBwP3.3 謂詞公式化為子句集的方法 例例3 將下列謂詞公式化為子句集。將下列謂詞公式化為子句集。解：（解：（1）消去蘊(yùn)含符號(hào)）消去蘊(yùn)含符號(hào)（2）把否定符號(hào)移到每個(gè)謂詞前面）把否定符號(hào)移到每個(gè)謂詞前面 （3）變量標(biāo)準(zhǔn)化）變量標(biāo)準(zhǔn)化 （4）消去存在量詞，）消去存在量詞，),(),()(),()(yx

34、RyxQyyxPyx),(),()(),()()(yxRyxQyyxPyx),(),()(),()(yxRyxQyyxPyx),(),()(),()(zxRzxQzyxPyx)(),(xgzxfy )(,()(,()(,()(xgxRxgxQxfxPx 例例3 將下列將下列謂詞公式化為子句集。（續(xù)）謂詞公式化為子句集。（續(xù)）（5）化為前束形）化為前束形( (沒變化沒變化) ) （6）化為標(biāo)準(zhǔn)形）化為標(biāo)準(zhǔn)形 （7）略去全稱量詞）略去全稱量詞 （8）消去合取詞，把母式用子句集表示）消去合取詞，把母式用子句集表示 （9）子句變量標(biāo)準(zhǔn)化）子句變量標(biāo)準(zhǔn)化 3.3 謂詞公式化為子句集的方法)(,()(,(

35、)(,()(xgxRxgxQxfxPx)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx)(,()(,()(,()(,(xgxRxfxPxgxQxfxP)(,()(,(,)(,()(,(xgxRxfxPxgxQxfxP)(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP3.3 謂詞公式化為子句集的方法 練習(xí)練習(xí): 將下列謂詞公式化為子句集。將下列謂詞公式化為子句集。解：（解：（1）消去蘊(yùn)含符號(hào)）消去蘊(yùn)含符號(hào)（2）把否定符號(hào)移到每個(gè)謂詞前面）把否定符號(hào)移到每個(gè)謂詞前面 （3）變量標(biāo)準(zhǔn)化）變量標(biāo)準(zhǔn)化 （4）消去存在量詞，）消去存在量詞，),(),(),()()(y

36、xRyxQyxPyx),(),(),()()(yxRyxQyxPyx),(),(),()()(yxRyxQyxPyx)(xfy )(,()(,()(,()(xfxRxfxQxfxPx),(),(),()()(yxRyxQyxPyx 例例3 將下列將下列謂詞公式化為子句集。（續(xù)）謂詞公式化為子句集。（續(xù)）（5）化為前束形）化為前束形 （6）化為標(biāo)準(zhǔn)形）化為標(biāo)準(zhǔn)形 （7）略去全稱量詞）略去全稱量詞 （8）消去合取詞，把母式用子句集表示）消去合取詞，把母式用子句集表示 （9）子句變量標(biāo)準(zhǔn)化）子句變量標(biāo)準(zhǔn)化 3.3 謂詞公式化為子句集的方法)(,()(,()(,()(,()(xfxRxfxQxfxRx

37、fxPx)(,()(,()(,()(,()(xfxRxfxQxfxRxfxPx)(,()(,()(,()(,(xfxRxfxQxfxRxfxP)(,()(,(),(,()(,(yfyRyfyQxfxRxfxP歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理 3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法 3.4 海伯倫定理海伯倫定理 3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理 3.6 歸結(jié)反演歸結(jié)反演 3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 定理：定理： PQ當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P Q F 即即 Q為為 P 的邏輯

38、的邏輯結(jié)論，當(dāng)且僅當(dāng)結(jié)論，當(dāng)且僅當(dāng)P Q 是不可滿足的。是不可滿足的。 定理：定理：Q 為為 ， ， 的邏輯結(jié)論，當(dāng)且僅的邏輯結(jié)論，當(dāng)且僅當(dāng)當(dāng) 是不可滿足的。是不可滿足的。1P2PnPQPPPn)(213.5 魯賓遜歸結(jié)原理定理定理 : 謂詞公式不可滿足的謂詞公式不可滿足的充要條件充要條件是其子句集不可滿足。是其子句集不可滿足。謂詞公式謂詞公式不可滿足性不可滿足性子句集子句集不可滿足性不可滿足性？3.5 魯賓遜歸結(jié)原理思路：定理思路：定理 不可滿足不可滿足 子句集不可滿足子句集不可滿足 海伯倫定理海伯倫定理 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理QP QP3.5 魯賓遜歸結(jié)原理3.5 魯賓遜歸結(jié)原理u

39、魯賓遜歸結(jié)原理（消解原理）魯賓遜歸結(jié)原理（消解原理）的基本思想：基本思想：p檢查子句集檢查子句集 S 中是否包含空子句，若包含，則中是否包含空子句，若包含，則 S 不可滿足。不可滿足。p若不包含，在若不包含，在 S 中選擇合適的子句進(jìn)行歸結(jié)，一旦歸結(jié)出空中選擇合適的子句進(jìn)行歸結(jié)，一旦歸結(jié)出空子句，就說明子句，就說明 S 是不可滿足的。是不可滿足的。u 子句集中子句之間是合取關(guān)系，只要有一個(gè)子句不可滿足，子句集中子句之間是合取關(guān)系，只要有一個(gè)子句不可滿足， 則子句集就不可滿足。則子句集就不可滿足。 3.5 魯賓遜歸結(jié)原理1. 命題邏輯中的歸結(jié)原理（基子句的歸結(jié)）命題邏輯中的歸結(jié)原理（基子句的歸結(jié)

40、） 歸結(jié)歸結(jié)：設(shè)：設(shè)C1與與C2是子句集中的任意兩個(gè)子句，如果是子句集中的任意兩個(gè)子句，如果 C1中的文中的文字字L1與與 C2中的文字中的文字L2互補(bǔ)，那么從互補(bǔ)，那么從C1和和 C2中分別消去中分別消去L1和和L2，并將二個(gè)子句中余下的部分，并將二個(gè)子句中余下的部分析取析取，構(gòu)成一個(gè)新子句，構(gòu)成一個(gè)新子句C12 。C12 稱為稱為C1 和和C2 的的歸結(jié)式歸結(jié)式;C1 和和C2 為為C12的親本子句。的親本子句。3C1C2C（歸結(jié)）（歸結(jié)）12C（歸結(jié)）（歸結(jié)）123C123CPQCQRCP 設(shè)設(shè)，例例： P QPR Q R P Ru 推論推論1：設(shè)：設(shè)C1與與C2是子句集是子句集S中的兩

41、個(gè)子句，中的兩個(gè)子句，C12是它們的歸結(jié)是它們的歸結(jié)式，若用式，若用C12代替代替C1與與C2后得到新子句集后得到新子句集S1，則由，則由S1不可滿足性不可滿足性可推出原子句集可推出原子句集S的不可滿足性，即：的不可滿足性，即： u 推論推論2：設(shè)設(shè)C1與與C2是子句集是子句集S中的兩個(gè)子句，中的兩個(gè)子句，C12是它們的歸結(jié)式，是它們的歸結(jié)式，若若C12 加入原子句集加入原子句集S，得到新子句集，得到新子句集S1，則，則S與與S1在不可滿足的意在不可滿足的意義上是等價(jià)的，即：義上是等價(jià)的，即： u 定理定理1：歸結(jié)式：歸結(jié)式C12是其親本子句是其親本子句C1與與C2的邏輯結(jié)論。即如果的邏輯結(jié)論

42、。即如果 C1與與C2為真，則為真，則C12為真。為真。3.5 魯賓遜歸結(jié)原理S1的不可滿足性的不可滿足性 S 的不可滿足性的不可滿足性S1的不可滿足性的不可滿足性 S的不可滿足性的不可滿足性3.5 魯賓遜歸結(jié)原理2. 謂詞邏輯中的歸結(jié)原理（含有變量的子句的歸結(jié)）謂詞邏輯中的歸結(jié)原理（含有變量的子句的歸結(jié)） )()(1xQxPC)()(2yRaPC/xa)()(1aQaPC)()(2yRaPC)()(12yRaQC？最一般合一最一般合一最一般合一最一般合一例：例：3.5 魯賓遜歸結(jié)原理 例例4設(shè)設(shè)： 求其二元?dú)w結(jié)式。求其二元?dú)w結(jié)式。),()(1aQxPC)()(2yRbPC 解：解：令令)()

43、(2yRbPC)()(aQxP)()(yRbP)()(yRaQ/xbC1C2C123.5 魯賓遜歸結(jié)原理則得：則得： 解：解：f(a)是個(gè)體常項(xiàng)，令是個(gè)體常項(xiàng)，令/ )(xaf),()(1afQafPC/ )(yaf求其二元?dú)w結(jié)式。求其二元?dú)w結(jié)式。),()()(1xQafPxPC)()(2bRyPC 例例5：設(shè)設(shè)再令：再令：),()(2bRafPC得：得：),()(1afQafPC),()(2bRafPC)()(12afQbRC3.5 魯賓遜歸結(jié)原理注：注：對(duì)于謂詞邏輯，歸結(jié)式是其親本子句的邏輯結(jié)論。對(duì)于謂詞邏輯，歸結(jié)式是其親本子句的邏輯結(jié)論。 對(duì)于一階謂詞邏輯，即若子句集是不可滿足的，則必存

44、在對(duì)于一階謂詞邏輯，即若子句集是不可滿足的，則必存在一個(gè)從該子句集到空子句的歸結(jié)演繹；若從子句集存在一一個(gè)從該子句集到空子句的歸結(jié)演繹；若從子句集存在一個(gè)到空子句的演繹，則該子句集是不可滿足的。個(gè)到空子句的演繹，則該子句集是不可滿足的。如果沒有歸結(jié)出空子句，如果沒有歸結(jié)出空子句，則既不能說則既不能說 S 不可滿足，也不能不可滿足，也不能說說 S 是可滿足的。是可滿足的。 歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法 3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理 3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法 3.4 海伯倫定理海伯倫定理 3.5 魯賓遜歸結(jié)

45、原理魯賓遜歸結(jié)原理 3.6 歸結(jié)反演歸結(jié)反演 3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 3.6 歸結(jié)反演v應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。v用歸結(jié)反演證明的步驟是：用歸結(jié)反演證明的步驟是：（1）將已知前提表示為謂詞公式）將已知前提表示為謂詞公式F。（2）將待證明的結(jié)論表示為謂詞公式）將待證明的結(jié)論表示為謂詞公式Q，并否定得到，并否定得到 Q 。（3）把謂詞公式集）把謂詞公式集F， Q 化為子句集化為子句集S。（4）應(yīng)用歸結(jié)原理對(duì)子句集）應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次中的子句進(jìn)行歸結(jié)，并把每次 歸結(jié)得到的歸結(jié)式都并入到歸結(jié)

46、得到的歸結(jié)式都并入到S中。如此反復(fù)進(jìn)行，若出中。如此反復(fù)進(jìn)行，若出 現(xiàn)了現(xiàn)了空子句空子句，則停止歸結(jié)，此時(shí)就證明了，則停止歸結(jié)，此時(shí)就證明了Q為真。為真。3.6 歸結(jié)反演 例例6 某公司招聘工作人員，某公司招聘工作人員，A，B ，C 三人應(yīng)試，三人應(yīng)試，經(jīng)面試后公司表示如下想法：經(jīng)面試后公司表示如下想法：（1） 三人中至少錄取一人。三人中至少錄取一人。（2） 如果錄取如果錄取 A 而不錄取而不錄取 B ，則一定錄取，則一定錄取 C。（3） 如果錄取如果錄取 B ，則一定錄取，則一定錄取 C 。 n 求證：公司一定錄取求證：公司一定錄取 C。 3.6 歸結(jié)反演v證明：公司的想法用謂詞公式表示：證

47、明：公司的想法用謂詞公式表示： 。 xxP：錄取)( 把要求證的結(jié)論用謂詞公式表示出來并否定，得：把要求證的結(jié)論用謂詞公式表示出來并否定，得：)()()(CPBPAP)()()(CPBPAP)()(CPBP（1）（2）（3） （4）)(CP 把上述公式化成子句集：把上述公式化成子句集： （1）)()()(CPBPAP)()()(CPBPAP（2）)()(CPBP（3）)(CP（4）3.6 歸結(jié)反演P(A) P(B) P(C) P(A) P(B) P(C)P(B) P(C) P(B) P(C)P(C) P(C)NIL應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)： （1）（2）（3）（4）3.6 歸

48、結(jié)反演歸結(jié)反演 例例7 已知：已知： 規(guī)則規(guī)則1：任何人的兄弟不是女性；：任何人的兄弟不是女性； 規(guī)則規(guī)則2：任何人的姐妹必是女性。：任何人的姐妹必是女性。 事事 實(shí)：實(shí)：Mary 是是 Bill 的姐妹。的姐妹。 求證：求證： Mary 不是不是 Tom 的兄弟。的兄弟。 證明：定義謂詞證明：定義謂詞 brother ( x, y ) : x 是是 y 的兄弟的兄弟 sister ( x, y ) : x 是是 y 的姐妹的姐妹 woman ( x ) : x 是女性是女性 證明：將規(guī)則與事實(shí)用謂詞公式表示：證明：將規(guī)則與事實(shí)用謂詞公式表示： 把要求證的結(jié)論用謂詞公式表示出來把要求證的結(jié)論用

49、謂詞公式表示出來并否定并否定，得：，得： 把上述公式化成子句集：把上述公式化成子句集： （1）（2）（3）)(),()()(xwomanyxbrotheryx)(),()()(xwomanyxsisteryx),(BillMarysister（4）),(TomMarybrother)(),(1xwomanyxbrotherC)(),(2xwomanyxsisterC),(3BillMarysisterC ),(4TomMarybrotherC 3.6 歸結(jié)反演歸結(jié)反演（1）（2）（3）)(),()()(xwomanyxbrotheryx),(BillMarysister)(),()()(xwo

50、manyxbrotheryx),(BillMarysister（1）（2）（3）3.6 歸結(jié)反演 sisiter(x,y) woman(x)sister(Mary,Bill)woman(Mary) brother(x,y) woman(x) brother(Mary,y)brother(Mary,Tom)NIL =Mary/x =Mary/x 將子句集進(jìn)行歸結(jié)：將子句集進(jìn)行歸結(jié)： （C2）（C3）（C1）（C4）歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法3.4 海伯倫定理海伯倫定理3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理3.6 歸結(jié)反演歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 3.7 應(yīng)用歸結(jié)原理求解問題 應(yīng)用歸結(jié)原理求解問題的步驟：應(yīng)用歸結(jié)原理求解問題的步驟：（1）已知前提）已知前提 F 用謂詞公式表示，并化為子句集用謂詞公式表示，并化為子句集 S ；（3）把（）把（ Q ANSWER） 化為子句集，并入到子句集化為子句集，并入到子句集 S中，中，得到子句集得到子句集 ；S（4）對(duì)）對(duì) 應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)；應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)