第3章_確定性推理方法1

1、Artificial Intelligence Principles and Applications第第 3 章章 確定性推理方法確定性推理方法教材：教材： 王萬(wàn)良王萬(wàn)良人工智能及其應(yīng)用人工智能及其應(yīng)用（第（第2版）版） 高等教育出版社，高等教育出版社，2008. 62知識(shí)智能?第第3章章 確定性推理方法確定性推理方法第3章 確定性推理方法經(jīng) 典 邏 輯 推 理（ 確 定 性 推 理 ）不 確 定 性 推 理自 然 演 繹推 理歸 結(jié) 演 繹推 理與 /或 形演 繹 推 理推理推理知識(shí)智能 !3歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演

2、繹推理自然演繹推理 3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法3.4 海伯倫定理海伯倫定理3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理3.6 歸結(jié)反演歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 4歸歸結(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é)反演求解問題 53.1 推理的基本概念o3.1.1 推理的定義推理的定義o3.1.2

3、推理方式及其分類推理方式及其分類o3.1.3 推理的方向推理的方向o3.1.4 沖突消解策略沖突消解策略6推理機(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é)論73.1 推理的基本概念o3.1.1 推理的定義推理的定義o3.1.2 推理方式及其分類推理方式及其分類o3.1.3 推理的方向推理的方向o3.1.4 沖突消解策略沖突消解策略8（1）演繹推理演繹推理 (deductive reasoning) :

4、 一般一般 個(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 推理方式及其分類o 演繹推理、歸納推理、默認(rèn)推理演繹推理、歸納推理、默認(rèn)推理（ 大前提大前提 ）（ 小前提小前提 ）（ 結(jié)結(jié) 論論 ）93.1.2 推理方式及其分類o 演繹推理、歸納推理、默認(rèn)推理演繹推理、歸納推理、默認(rèn)推理（2）歸納推理歸納推理 (inductive reasoning): 個(gè)別個(gè)別 一般一般 完全歸納推理（完全歸納推理（必然性推理）必然性推理）

5、不完全歸納推理不完全歸納推理（非必然性推理）（非必然性推理）檢查全部產(chǎn)品合格檢查全部產(chǎn)品合格該廠產(chǎn)品合格該廠產(chǎn)品合格完全歸納推理完全歸納推理檢查全部樣品合格檢查全部樣品合格該廠產(chǎn)品合格該廠產(chǎn)品合格不完全歸納推理不完全歸納推理103.1.2 推理方式及其分類o 演繹推理、歸納推理、默認(rèn)推理演繹推理、歸納推理、默認(rèn)推理（3）默認(rèn)推理默認(rèn)推理（default reasoning，缺省推理），缺省推理）n 知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。 結(jié)結(jié) 論論 A 成立成立 B 成立？成立？（默認(rèn)（默認(rèn)B成立）成立）鳥籠要鳥籠要有蓋子有蓋子

6、制造鳥籠制造鳥籠 鳥會(huì)飛？鳥會(huì)飛？（默認(rèn)成立）（默認(rèn)成立）113.1.2 推理方式及其分類 2. 確定性推理、不確定性推理確定性推理、不確定性推理似然推理近似推理或模糊推理不確定性推理（概率論）（模糊邏輯）（1）確定性推理確定性推理：推理時(shí)所用的知識(shí)與證據(jù)都是確定的，推出的結(jié)論也是確定的，其真值或者為真或者為假。 （2）不確定性不確定性推理推理：推理時(shí)所用的知識(shí)與證據(jù)不都是確定的，推出的結(jié)論也是不確定的。12X：鳥：鳥 X：會(huì)飛：會(huì)飛 X: 企鵝企鵝 3.1.2 推理方式及其分類 3. 單調(diào)推理、非單調(diào)推理單調(diào)推理、非單調(diào)推理 （1）單調(diào)推理單調(diào)推理：隨著推理向前推進(jìn)及新知識(shí)的加入，推出的結(jié)論

7、越來(lái)越接近最終目標(biāo)。 （2）非單調(diào)推理非單調(diào)推理：由于新知識(shí)的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使推理退回到前面的某一步，重新開始。 默認(rèn)推理是非單調(diào)推理默認(rèn)推理是非單調(diào)推理 基于經(jīng)典邏輯的演繹推理基于經(jīng)典邏輯的演繹推理 X：不會(huì)飛不會(huì)飛X：企鵝：企鵝133.1.2 推理方式及其分類4啟發(fā)式推理、非啟發(fā)式推理啟發(fā)式推理、非啟發(fā)式推理 啟發(fā)性知識(shí)啟發(fā)性知識(shí)：與問題有關(guān)且能加快推理過(guò)程、提高搜索效率的知識(shí)。 o 目標(biāo)：在腦膜炎、肺炎、流感中選擇一個(gè)目標(biāo)：在腦膜炎、肺炎、流感中選擇一個(gè) 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則 r1：腦膜炎：腦膜炎 r2：肺：肺 炎炎 r3：流：流 感感 啟發(fā)式知識(shí)：?jiǎn)l(fā)式

8、知識(shí)：“腦膜炎危險(xiǎn)腦膜炎危險(xiǎn)”、“目前正在盛行流目前正在盛行流感感”。143.1 推理的基本概念o3.1.1 推理的定義推理的定義o3.1.2 推理方式及其分類推理方式及其分類o3.1.3 推理的方向推理的方向o3.1.4 沖突消解策略沖突消解策略153.1.3 推理的方向正向推理逆向推理(反向推理)雙向推理混合推理推理方向推理機(jī)數(shù)據(jù)庫(kù)知識(shí)庫(kù)專家用戶163.1.3 推理的方向n 正向推理（事實(shí)驅(qū)動(dòng)推理）正向推理（事實(shí)驅(qū)動(dòng)推理）: 已知事實(shí) 結(jié)論 基本思想基本思想（1）從初始已知事實(shí)出發(fā)，在知識(shí)庫(kù)KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用知識(shí)集KS。（2）按某種沖突消解策略從KS中選出一條知識(shí)進(jìn)行推

9、理，并將推出的新事實(shí)加入到數(shù)據(jù)庫(kù)DB中作為下一步推理的已知事實(shí)，再在KB中選取可適用知識(shí)構(gòu)成KS 。（3）重復(fù)（2），直到求得問題的解或KB中再無(wú)可適用的知識(shí)。1. 正向推理正向推理17KBKS183.1.3 推理的方向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. 正向推理正向推理193.1.3 推理的方向n 逆向推理（目標(biāo)驅(qū)動(dòng)推理）：

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

11、，如何確定先選哪一條？ 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. 逆向推理逆向推理223.1.3 推理的方向n 正向推理正向推理: 盲目、效率低。 逆向推理逆向推理: 若提出的假設(shè)目標(biāo)不符合實(shí)際，會(huì)降低效率。 正反向混合推理：正反向混合推理：（1）先正向后逆向：先正向后逆向：先進(jìn)行

12、正向推理，幫助選擇某個(gè)目標(biāo)，即從已知事實(shí)演繹出部分結(jié)果，然后再用逆向推理證實(shí)該目標(biāo)或提高其可信度；（2）先逆向后正向：先逆向后正向：先假設(shè)一個(gè)目標(biāo)進(jìn)行逆向推理，然后再利用逆向推理中得到的信息進(jìn)行正向推理，以推出更多的結(jié)論。3. 混合推理混合推理232425n 雙向推理雙向推理：正向推理與逆向推理同時(shí)進(jìn)行，且在推理過(guò)程中的某一步驟上“碰頭碰頭”的一種推理。已知事實(shí)已知事實(shí) 假設(shè)目標(biāo)假設(shè)目標(biāo)3.1.3 推理的方向4. 雙向推理雙向推理中間結(jié)論中間結(jié)論證證 據(jù)據(jù)263.1 推理的基本概念o3.1.1 推理的定義推理的定義o3.1.2 推理方式及其分類推理方式及其分類o3.1.3 推理的方向推理的方向

13、o3.1.4 沖突消解策略沖突消解策略273.1.4 沖突消解策略 已知事實(shí)與知識(shí)的三種匹配情況已知事實(shí)與知識(shí)的三種匹配情況：（1）恰好匹配成功（一對(duì)一）；）恰好匹配成功（一對(duì)一）；（2）不能匹配成功；）不能匹配成功；（3）多種匹配成功多種匹配成功（一對(duì)多、多對(duì)一、多對(duì)多）（一對(duì)多、多對(duì)一、多對(duì)多）沖突消解沖突消解283.1.4 沖突消解策略多種沖突消解策略：多種沖突消解策略：（1）按針對(duì)性排序）按針對(duì)性排序（2）按已知事實(shí)的新鮮性排序）按已知事實(shí)的新鮮性排序（3）按匹配度排序）按匹配度排序（4）按條件個(gè)數(shù)排序）按條件個(gè)數(shù)排序（5）按上下文限制排序）按上下文限制排序（6）按冗余限制排序）按冗余

14、限制排序（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 H229第3章 確定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理 3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法3.4 海伯倫定理海伯倫定理3.5 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理3.6 歸結(jié)反演歸結(jié)反演o3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 30p自然演繹推理自然演繹推理：從一組已知為真的事實(shí)出發(fā)，運(yùn)用從一組已知為真的事實(shí)出發(fā)，運(yùn)用經(jīng)典經(jīng)典邏輯的推理規(guī)則邏輯的推

15、理規(guī)則推出結(jié)論的過(guò)程。推出結(jié)論的過(guò)程。p推理規(guī)則推理規(guī)則：P規(guī)則、規(guī)則、T規(guī)則、假言推理、拒取式推理規(guī)則、假言推理、拒取式推理 3.2 自然演繹推理n 假言推理假言推理： P, PQ Q n “如果如果x是金屬，則是金屬，則x能導(dǎo)電能導(dǎo)電” , “銅是金屬銅是金屬” 推出推出 “銅能導(dǎo)銅能導(dǎo)電電” n 拒取式推理拒取式推理： PQ, Q Pn “如果下雨，則地下就濕如果下雨，則地下就濕” , “地上不濕地上不濕” 推出推出 “沒有下雨沒有下雨”31（1） 如果下雨，則地上是濕的（如果下雨，則地上是濕的（ PQ ）；（2）沒有下雨（）沒有下雨（P ）；）； （3）所以，地上不濕（所以，地上不濕（

16、Q ）。 3.2 自然演繹推理p錯(cuò)誤錯(cuò)誤1否定前件否定前件： PQ, P Q（1）如果行星系統(tǒng)是以太陽(yáng)為中心的，則金星會(huì)顯如果行星系統(tǒng)是以太陽(yáng)為中心的，則金星會(huì)顯示出位相變化（示出位相變化（ PQ ）；（2）金星顯示出位相變化（金星顯示出位相變化（ Q ）；）；（3） 所以，行星系統(tǒng)是以太陽(yáng)為中心（所以，行星系統(tǒng)是以太陽(yáng)為中心（ P ）。 錯(cuò)誤錯(cuò)誤2肯定后件肯定后件： PQ, Q P323.2 自然演繹推理p 例例1 已知事實(shí)：已知事實(shí)： （1）凡是容易的課程小王凡是容易的課程小王( Wang )都喜歡；都喜歡； （2）C 班的課程都是容易的；班的課程都是容易的； （3）ds 是是 C 班的一

17、門課程。班的一門課程。p 求證：小王喜歡求證：小王喜歡 ds 這門課程。這門課程。333.2 自然演繹推理p證明：證明：p定義謂詞定義謂詞： EASY ( x )：x 是容易的 LIKE ( x, y )：x 喜歡 y C ( x )：x 是 C 班的一門課程p 已知事實(shí)和結(jié)論用謂詞公式表示已知事實(shí)和結(jié)論用謂詞公式表示： ( ) ( EASY ( x ) LIKE ( Wang, x ) ) ( ) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ) xx343.2 自然演繹推理p 應(yīng)用推理規(guī)則進(jìn)行推理：應(yīng)用推理規(guī)則進(jìn)行推理： ( )（EASY (

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

19、點(diǎn)缺點(diǎn)：易產(chǎn)生組合爆炸，得到的中間結(jié)論一般呈指數(shù)形式遞增。36歸歸結(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é)反演求解問題 37歸 結(jié) 演 繹 推 理o反證法：反證法： ，當(dāng)且僅當(dāng) ，o 即 Q為 P 的邏輯結(jié)論，當(dāng)且僅當(dāng) 是不可滿足的。QP FQPQPo 定理：定理：Q 為為 ， ， 的邏輯結(jié)論，當(dāng)且僅當(dāng)?shù)倪壿嫿Y(jié)論，當(dāng)且僅當(dāng)o 是不可滿足的。是不可

20、滿足的。1P2PnPQPPPn)(2138歸 結(jié) 演 繹 推 理o思路：定理思路：定理 不可滿足 o 子句集不可滿足 海伯倫定海伯倫定理理o 魯賓遜歸結(jié)原理魯賓遜歸結(jié)原理QP QP393.3 謂詞公式化為子句集的方法 原子（原子（atom）謂詞公式）謂詞公式： 一個(gè)不能再分解的命題。 文字（文字（literal）：原子謂詞公式及其否定。 ：正文字， ：負(fù)文字。 子句（子句（clause）：任何文字的析取式。任何文字本身也都是子句。 空子句（空子句（NIL）：不包含任何文字的子句。 子句集子句集：由子句構(gòu)成的集合。PP)(,()(,(),()(xgxQxfxPxQxP空子句是永假的，不可滿足的。

21、空子句是永假的，不可滿足的。403.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法 例例2 將下列將下列謂詞公式化為子句集。謂詞公式化為子句集。 解解：（：（1）消）消去謂詞公式中的去謂詞公式中的“ ”和和“ ”符號(hào)符號(hào)),(),()(),()(yxRyxQyyxPyx 雙重否定律雙重否定律 德德.摩根律摩根律 量詞轉(zhuǎn)換律量詞轉(zhuǎn)換律 PP )(,)(QPQPQPQP)(PxPx)()(,)()(PxPx （2）把否定符號(hào)）把否定符號(hào) 移到緊靠謂詞的位置上移到緊靠謂詞的位置上,QPQP)()(QPQPQP),(),()(),()()(yxRyxQyyxPyx),(),()(),()(yxR

22、yxQyyxPyx（3）變量標(biāo)準(zhǔn)化）變量標(biāo)準(zhǔn)化 )()()()(yPyxPx),()()()(yPyxPx),(),()(),()(zxRzxQzyxPyx3.3 謂詞公式化為子句集的方法41 （4）消去存在量詞）消去存在量詞 a. 存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)。 b. 存在量詞出現(xiàn)在一個(gè)或者多個(gè)全稱量詞的轄域內(nèi)。)(,()(,()(,()(xgxRxgxQxfxPx)(),(xgzxfy函數(shù)為的存在量詞對(duì)于一般情況Skolem).),()()(2121yyxxxPyxxxnn),(21nxxxfySkolem化：用Skolem函數(shù)代替每個(gè)存在量詞量化的變量的過(guò)程。 （5）化為前束形）化為

23、前束形 前束形=（前綴）母式（前綴）：全稱量詞串。 母式：不含量詞的謂詞公式。 3.3 謂詞公式化為子句集的方法),(),()(),()(zxRzxQzyxPyx423.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)(,()(,()(,()(,()(xgxRxfxPxgxQxfxPx（7）略去全稱量詞）略去全稱量詞 )(,()(,()(,()(,(xgxRxfxPxgxQxfxP（8）消去合取詞）消去合取詞 )(,()(

24、,(,)(,()(,(xgxRxfxPxgxQxfxP（9）子句變量標(biāo)準(zhǔn)化）子句變量標(biāo)準(zhǔn)化 )(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP433.3 謂詞公式化為子句集的方法o 例例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）消去存在量詞，設(shè)）消去存在量詞，設(shè)y的函數(shù)是的函數(shù)是f(x)，則，則 )()()()(),()()()()(xBxPxxQyxSyxQxPx)()()()(),()()()()(xBxPxxQyxSyxQxPx)

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

26、)()()()(wBwPxfxSxQxPxQwx)()()(,()()()(wBwPxfxSxPxQwx)()()(,()()(wBwPxfxSxPxQ),(xQ),(,()(xfxSxP)()(wBwP),(xQ),(,()(yfySyP)()(wBwP453.3 謂詞公式化為子句集的方法o 例例4 將下列謂詞公式化為不含存在量詞的前束形。（1）消去存在量詞）消去存在量詞 （2）消去蘊(yùn)含符號(hào)）消去蘊(yùn)含符號(hào) （3）設(shè)）設(shè)z的函數(shù)是的函數(shù)是g(y)，則，則 )(,(),()()()()(afyxRzxQzPzyx)(,(),()()()(afybRzbQzPzy)(,(),()()()(afyb

27、RzbQzPzy)(,(),()()()(afybRzbQzPzy)(,()(,()()(afybRygbQygPy46歸歸結(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é)反演求解問題 47定義定義3.1（ H 域）域） 設(shè) S 為子句集，則按下述方法構(gòu)造的域 稱為海伯倫域，簡(jiǎn)記為 H 域。（1）令 是 S 中所有個(gè)體常量的集合，若 S 中不包含個(gè)體常量

28、，則令 ，其中 為 任意指定的一個(gè)個(gè)體常量。（2）令 S 中所有 n 元函數(shù) 是 H 中的元素，其中 。 3.4 海伯倫（Herbrand）定理 H0H0HiiHH1),(1nxxf, 2 , 1 , 0i483.4 海伯倫（Herbrand）定理 p 例例5 求子句集 的 H 域。 )(),()(yfRxQxPS 解：指定一個(gè)常量 作為個(gè)體常量，則得：a0H)(,)()(01fffHH)(),(,)(),(12ffffffHH)(),(),(,3ffffffH ),(),(),(,ffffffH.493.4 海伯倫（Herbrand）定理 p 例例6 求子句集 的 H 域。 )(),()(y

29、fRbQaPS 解解：根據(jù)：根據(jù) H 域的定義得：域的定義得：,0baH)(),(,)(),(01bfafbabfafHH)(),(),(),(,)(),(),(),(12bffaffbfafbabffaffbfafHH.503.4 海伯倫（Herbrand）定理 p 例例7 求子句集 的 H 域。 )(),(),(ygRxfQaPS 解：根據(jù)解：根據(jù) H 域的定義得：域的定義得：0aH p 例例8 求子句集 的 H 域。 )()(),(yRyQxPS 解：根據(jù)解：根據(jù) H 域的定義得：域的定義得：10HHH)(),(,)(),(01agafaagafHH)(),(),(),(),(),(,)

30、(),(),(),(),(),(12aggafgagfaffagafaggafgagagfffafHH513.4 海伯倫（Herbrand）定理 基子句：基子句：用用H 域中的元素代換子句中的變?cè)笏玫淖泳?，域中的元素代換子句中的變?cè)笏玫淖泳?，其中的謂詞稱為其中的謂詞稱為基原子基原子。原子集原子集：子句集中所有基原子構(gòu)成的集合。：子句集中所有基原子構(gòu)成的集合。子句集在子句集在 H 域上的解釋域上的解釋：對(duì)子句集中出現(xiàn)的常量、函數(shù)及謂：對(duì)子句集中出現(xiàn)的常量、函數(shù)及謂詞取值，一次取值就是一個(gè)解釋。詞取值，一次取值就是一個(gè)解釋。 例例 9 子句集子句集 , , H 域：域： S 的原子集：的原

31、子集： 則則 S 的解釋為的解釋為：)(),(xfQaPS ),(),(,affafa),(),(),(affQafQaP ),(),(),(1affQafQaPI ),(),(),(2affQafQaPI523.4 海伯倫（Herbrand）定理 o 定理定理 3.2（海伯倫定理）（海伯倫定理）：o 子句集不可滿足的充要條件是存在一個(gè)有限的不可滿足的基子句集 。53歸歸結(jié)結(jié)演演繹繹推推理理第3章 確定性推理方法3.1 推理的基本概念推理的基本概念 3.2 自然演繹推理自然演繹推理3.3 謂詞公式化為子句集的方法謂詞公式化為子句集的方法3.4 海伯倫定理海伯倫定理3.5 魯賓遜歸結(jié)原理魯賓遜歸

32、結(jié)原理3.6 歸結(jié)反演歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題應(yīng)用歸結(jié)反演求解問題 543.5 魯賓遜歸結(jié)原理u 魯賓遜歸結(jié)原理（消解原理）魯賓遜歸結(jié)原理（消解原理）的基本思想：基本思想：p檢查子句集檢查子句集 S 中是否包含空子句，若包含，則中是否包含空子句，若包含，則 S 不可滿足。不可滿足。p若不包含，在若不包含，在 S 中選擇合適的子句進(jìn)行歸結(jié)，一旦歸結(jié)出空中選擇合適的子句進(jìn)行歸結(jié)，一旦歸結(jié)出空子句，就說(shuō)明子句，就說(shuō)明 S 是不可滿足的。是不可滿足的。u子句集中子句之間是合取關(guān)系，只要有一個(gè)子句不可滿足，子句集中子句之間是合取關(guān)系，只要有一個(gè)子句不可滿足， 則子句集就不可滿足。則子句集就不

33、可滿足。 553.5 魯賓遜歸結(jié)原理1. 命題邏輯中的歸結(jié)原理（基子句的歸結(jié)）命題邏輯中的歸結(jié)原理（基子句的歸結(jié)） 定義定義3.3（歸結(jié)歸結(jié)）：設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果 C1中的文字L1與 C2中的文字L2互補(bǔ)，那么從C1和 C2中分別消去L1和L2，并將二個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12 。PQPRQRP R圖3-5 歸結(jié)過(guò)程的樹形表示1C2C3C的歸結(jié)式和2112C :CC的親本子句、1221 :CCC（歸結(jié)）（歸結(jié)）12C（歸結(jié)）（歸結(jié)）123CPCRQCQPC321，例，設(shè)56u 推論推論1：設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若用C

34、12代替C1與C2后得到新子句集S1，則由S1不可滿足性可推出原子句集S的不可滿足性，即： u 推論推論2：設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的歸結(jié)式，若C12 加入原子句集S，得到新子句集S1，則S與S1在不可滿足的意義上是等價(jià)的，即： u 定理定理3.3：歸結(jié)式C12是其親本子句C1與C2的邏輯結(jié)論。即如果 C1與C2為真，則C12為真。3.5 魯賓遜歸結(jié)原理的不可滿足性的不可滿足性 S 的不可滿足性的不可滿足性1SS1的不可滿足性的不可滿足性 S的不可滿足性的不可滿足性573.5 魯賓遜歸結(jié)原理2. 謂詞邏輯中的歸結(jié)原理（含有變量的子句的歸結(jié)）謂詞邏輯中的歸結(jié)原理（含有變量

35、的子句的歸結(jié)） 例：例：)()(1xQxPC)()(2yRaPC/xa)()(1aQaPC)()(2yRaPC)()(12yRaQC？定義定義 3.4 ：設(shè)是 兩個(gè)沒有相同變?cè)淖泳洌?和 分別是 中的文字，若 是 的最一般合一，則稱 為 的二元?dú)w結(jié)式。 21LL和21CC 與1L2L21CC 和)()(221112LCLCC21CC 和最一般合一最一般合一583.5 魯賓遜歸結(jié)原理例例10 設(shè)：設(shè)： 求其二元?dú)w結(jié)式。求其二元?dú)w結(jié)式。得：得：),()(1aQxPC)()(2xRbPC)()(),()()(),(12bPyRbPbPaQbPC)(),(yRaQ)()(yRaQ 解：令解：令 選選

36、 則則)(),(21bPLxPL/xb)()(2yRbPC)()(aQxP)()(yRbP)()(yRaQ/xbC1C2C12593.5 魯賓遜歸結(jié)原理例例11 設(shè)：設(shè)： 求其二元?dú)w結(jié)式。求其二元?dú)w結(jié)式。則得：則得：),()()(1xQafPxPC)()(2bRyPC)()(12afQbRC 解：解： 選選)(),(21yPLafPL/ )(xaf),()(1afQafPC/ )(yaf603.5 魯賓遜歸結(jié)原理對(duì)于謂詞邏輯，歸結(jié)式是其親本子句的邏輯結(jié)論。 對(duì)于一階謂詞邏輯，即若子句集是不可滿足的，則必存在一個(gè)從該子句集到空子句的歸結(jié)演繹；若從子句集存在一個(gè)到空子句的演繹，則該子句集是不可滿足

37、的。如果沒有歸結(jié)出空子句，則既不能說(shuō) S 不可滿足，也不能說(shuō) S 是可滿足的。 61歸歸結(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é)反演求解問題 623.6 歸結(jié)反演應(yīng)用歸結(jié)原理證明定理的過(guò)程稱為歸結(jié)反演。用歸結(jié)反演證明的步驟是：（1）將已知前提表示為謂詞公式F。（2）將待證明的結(jié)論表示為謂詞公式Q，并否定得到 Q 。（3）把謂詞公式集F， Q 化為

38、子句集S。（4）應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把每次 歸結(jié)得到的歸結(jié)式都并入到S中。如此反復(fù)進(jìn)行，若出 現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。633.6 歸結(jié)反演 例12 某公司招聘工作人員，A，B ，C 三人應(yīng)試，經(jīng)面試后公司表示如下想法：（1） 三人中至少錄取一人。（2） 如果錄取 A 而不錄取 B ，則一定錄取 C。（3） 如果錄取 B ，則一定錄取 C 。 n 求證：公司一定錄取求證：公司一定錄取 C。 643.6 歸結(jié)反演證明：公司的想法用謂詞公式表示： 。 xxP：錄取)( 把要求證的結(jié)論用謂詞公式表示出來(lái)并否定，得：)()()(CPBPAP)()()(CPBPA

39、P)()(CPBP（1）（2）（3） （4）)(CP 把上述公式化成子句集： （1）（2）（3）（4）)()()(CPBPAP)()()(CPBPAP)()(CPBP)(CP三人中至少錄取一人。如果錄取 A 而不錄取 B ，則一定錄取 C。如果錄取 B ，則一定錄取 C 。 公司一定錄取公司一定錄取 C。653.6 歸結(jié)反演應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)： （5） （1）與（2）歸結(jié)（6） （3）與（5）歸結(jié)（7） （4）與（6）歸結(jié) )()(CPBP)(CPNIL663.6 歸結(jié)反演o 例例13 已知：已知： 規(guī)則規(guī)則1：任何人的兄弟不是女性；：任何人的兄弟不是女性； 規(guī)則規(guī)則2

40、：任何人的姐妹必是女性。：任何人的姐妹必是女性。 事事 實(shí)：實(shí)：Mary 是是 Bill 的姐妹。的姐妹。 求證：求證： Mary 不是不是 Tom 的兄弟。的兄弟。o 證明：定義謂詞證明：定義謂詞 brother ( x, y ) : x 是是 y 的兄弟的兄弟 sister ( x, y ) : x 是是 y 的姐妹的姐妹 woman ( x ) : x 是女性是女性673.6 歸結(jié)反演o證明：將規(guī)則與事實(shí)用謂詞公式表示：證明：將規(guī)則與事實(shí)用謂詞公式表示： 把要求證的結(jié)論用謂詞公式表示出來(lái)并否定，得：把要求證的結(jié)論用謂詞公式表示出來(lái)并否定，得： 把上述公式化成子句集：把上述公式化成子句集： （1）（2）（3）)(),()()(xwomanyxbrotheryx)(),()()(xwomanyxsisteryx),(BillMarysister（4）),(TomMarybrother)(),(1xwomanyxbrotherC)(),(2xwomanyxsisterC),(3BillMarysisterC ),(4TomMary