第3章 確定性推理方法（AI應(yīng)用3版）

1、第 3 章 確定性推理方法教材： 王萬良人工智能及其應(yīng)用（第3版） 高等教育出版社，2016. 22前面討論了把知識用某種模式表示出來存儲到計算機中去。但是，為使計算機具有智能，還必須使它具有思維能力。推理是求解問題的一種重要方法。因此，推理方法成為人工智能的一個重要研究課題。下面首先討論關(guān)于推理的基本概念，然后著重介紹魯賓遜歸結(jié)原理及其在機器定理證明和問題求解中的應(yīng)用。魯賓遜歸結(jié)原理使定理證明能夠在計算機上實現(xiàn)。第3章 確定性推理方法3第3章 確定性推理方法第3章 確定性推理方法4歸結(jié)演繹推理第3章 確定性推理方法3.1 推理的基本概念 3.2 自然演繹推理 3.3 謂詞公式化為子句集的方法

2、3.4 海伯倫定理3.5 魯賓遜歸結(jié)原理3.6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 5歸結(jié)演繹推理第3章 確定性推理方法3.1 推理的基本概念 3.2 自然演繹推理 3.3 謂詞公式化為子句集的方法3.4 海伯倫定理3.5 魯賓遜歸結(jié)原理3.6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 63.1 推理的基本概念3.1.1 推理的定義3.1.2 推理方式及其分類3.1.3 推理的方向3.1.4 沖突消解策略7醫(yī)療專家系統(tǒng)3.1.1 推理的定義推理：知識專家的經(jīng)驗、醫(yī)學(xué)常識初始證據(jù)病人的癥狀、化驗結(jié)果證據(jù)中間結(jié)論83.1 推理的基本概念3.1.1 推理的定義3.1.2 推理方式及其分類3.1.3 推

3、理的方向3.1.4 沖突消解策略9（1）演繹推理 (deductive reasoning) : 一般 個別 三段論式（三段論法） 足球運動員的身體都是強壯的 ； 高波是一名足球運動員； 所以，高波的身體是強壯的。3.1.2 推理方式及其分類 演繹推理、歸納推理、默認推理（ 大前提 ）（ 小前提 ）（ 結(jié) 論 ）103.1.2 推理方式及其分類 演繹推理、歸納推理、默認推理（2）歸納推理 (inductive reasoning): 個別 一般 完全歸納推理（必然性推理） 不完全歸納推理（非必然性推理）檢查全部產(chǎn)品合格該廠產(chǎn)品合格完全歸納推理檢查全部樣品合格該廠產(chǎn)品合格不完全歸納推理113.1

4、.2 推理方式及其分類 演繹推理、歸納推理、默認推理（3）默認推理（default reasoning，缺省推理） 知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進行的推理。 結(jié) 論 A 成立 B 成立？（默認B成立）鳥籠要有蓋子 制造鳥籠 鳥會飛？（默認成立）123.1.2 推理方式及其分類 2. 確定性推理、不確定性推理似然推理近似推理或模糊推理不確定性推理（概率論）（模糊邏輯）（1）確定性推理：推理時所用的知識與證據(jù)都是確定的，推出的結(jié)論也是確定的，其真值或者為真或者為假。 （2）不確定性推理：推理時所用的知識與證據(jù)不都是確定的，推出的結(jié)論也是不確定的。13X：鳥 X：會飛 X: 企鵝 3.1

5、.2 推理方式及其分類 3. 單調(diào)推理、非單調(diào)推理 （1）單調(diào)推理：隨著推理向前推進及新知識的加入，推出的結(jié)論越來越接近最終目標。 （2）非單調(diào)推理：由于新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使推理退回到前面的某一步，重新開始。 默認推理是非單調(diào)推理 基于經(jīng)典邏輯的演繹推理 X：不會飛X：企鵝143.1.2 推理方式及其分類4啟發(fā)式推理、非啟發(fā)式推理 啟發(fā)性知識：與問題有關(guān)且能加快推理過程、提高搜索效率的知識。 目標：在腦膜炎、肺炎、流感中選擇一個 產(chǎn)生式規(guī)則 r1：腦膜炎 r2：肺 炎 r3：流 感 啟發(fā)式知識：“腦膜炎危險”、“目前正在盛行流感”。153.1 推理的基本概念

6、3.1.1 推理的定義3.1.2 推理方式及其分類3.1.3 推理的方向3.1.4 沖突消解策略163.1.3 推理的方向173.1.3 推理的方向 正向推理（事實驅(qū)動推理）: 已知事實 結(jié)論 基本思想（1）從初始已知事實出發(fā)，在知識庫KB中找出當前可適用的知識，構(gòu)成可適用知識集KS。（2）按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫DB中作為下一步推理的已知事實，再在KB中選取可適用知識構(gòu)成KS 。（3）重復(fù)（2），直到求得問題的解或KB中再無可適用的知識。1. 正向推理18193.1.3 推理的方向 實現(xiàn)正向推理需要解決的問題： 確定匹配（知識與已知事實）的

7、方法。 按什么策略搜索知識庫。 沖突消解策略。 正向推理簡單，易實現(xiàn)，但目的性不強，效率低。1. 正向推理203.1.3 推理的方向 逆向推理（目標驅(qū)動推理）：以某個假設(shè)目標作為出發(fā)點。 基本思想： 選定一個假設(shè)目標。 尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則原假設(shè)成立；若無論如何都找不到所需要的證據(jù)，說明原假設(shè)不成立的；為此需要另作新的假設(shè)。 主要優(yōu)點：不必使用與目標無關(guān)的知識，目的性強，同時它還有利于向用戶提供解釋。 主要缺點：起始目標的選擇有盲目性。2. 逆向推理21223.1.3 推理的方向 逆向推理需要解決的問題： 如何判斷一個假設(shè)是否是證據(jù)？ 當導(dǎo)出假設(shè)的知識有多條時，如何確

8、定先選哪一條？ 一條知識的運用條件一般都有多個，當其中的一個經(jīng)驗證成立后，如何自動地換為對另一個的驗證？ . 逆向推理：目的性強，利于向用戶提供解釋，但選擇初始目標時具有盲目性，比正向推理復(fù)雜。2. 逆向推理233.1.3 推理的方向 正向推理: 盲目、效率低。 逆向推理: 若提出的假設(shè)目標不符合實際，會降低效率。 正反向混合推理：（1）先正向后逆向：先進行正向推理，幫助選擇某個目標，即從已知事實演繹出部分結(jié)果，然后再用逆向推理證實該目標或提高其可信度；（2）先逆向后正向：先假設(shè)一個目標進行逆向推理，然后再利用逆向推理中得到的信息進行正向推理，以推出更多的結(jié)論。3. 混合推理242526 雙向

9、推理：正向推理與逆向推理同時進行，且在推理過程中的某一步驟上“碰頭”的一種推理。已知事實 假設(shè)目標反向推理正向推理3.1.3 推理的方向4. 雙向推理中間結(jié)論證 據(jù)273.1 推理的基本概念3.1.1 推理的定義3.1.2 推理方式及其分類3.1.3 推理的方向3.1.4 沖突消解策略283.1.4 沖突消解策略 已知事實與知識的三種匹配情況：（1）恰好匹配成功（一對一）；（2）不能匹配成功；（3）多種匹配成功（一對多、多對一、多對多）沖突消解293.1.4 沖突消解策略多種沖突消解策略：（1）按針對性排序（2）按已知事實的新鮮性排序（3）按匹配度排序（4）按條件個數(shù)排序（5）按上下文限制排序

10、（6）按冗余限制排序（7）根據(jù)領(lǐng)域問題的特點排序r1: IF A1 AND A2 THEN H1r2: IF A1 AND A2 AND A3 AND A4 THEN H230第3章 確定性推理方法3.1 推理的基本概念 3.2 自然演繹推理 3.3 謂詞公式化為子句集的方法3.4 海伯倫定理3.5 魯賓遜歸結(jié)原理3.6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 31自然演繹推理：從一組已知為真的事實出發(fā)，運用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過程。推理規(guī)則：P規(guī)則、T規(guī)則、假言推理、拒取式推理 3.2 自然演繹推理 假言推理： P, PQ Q “如果x是金屬，則x能導(dǎo)電” , “銅是金屬” 推出 “銅

11、能導(dǎo)電” 拒取式推理： PQ, Q P “如果下雨，則地下就濕” , “地上不濕” 推出 “沒有下雨”32（1） 如果下雨，則地上是濕的（ PQ ）；（2）沒有下雨（P ）； （3）所以，地上不濕（Q ）。 3.2 自然演繹推理錯誤1否定前件： PQ, P Q（1）如果行星系統(tǒng)是以太陽為中心的，則金星會顯示出位相變化（ PQ ）；（2）金星顯示出位相變化（ Q ）；（3） 所以，行星系統(tǒng)是以太陽為中心（ P ）。 錯誤2肯定后件： PQ, Q P333.2 自然演繹推理 例1 已知事實： （1）凡是容易的課程小王( Wang )都喜歡； （2）C 班的課程都是容易的； （3）ds 是 C 班的

12、一門課程。 求證：小王喜歡 ds 這門課程。343.2 自然演繹推理證明：定義謂詞： EASY ( x )：x 是容易的 LIKE ( x, y )：x 喜歡 y C ( x )：x 是 C 班的一門課程 已知事實和結(jié)論用謂詞公式表示： ( ) ( EASY ( x ) LIKE ( Wang, x ) ) ( ) ( C ( x ) EASY ( x ) C ( ds ) LIKE ( Wang, ds ) 353.2 自然演繹推理 應(yīng)用推理規(guī)則進行推理： ( )（EASY ( x ) LIKE ( Wang, x ) EASY (z) LIKE ( Wang, z ) 全稱固化 ( ) (

13、C ( x ) EASY ( x ) C ( y ) EASY ( y ) 全稱固化 所以 C (ds), C (y) EASY (y) EASY (ds) P規(guī)則及假言推理 所以 EASY (ds), EASY (z) LIKE (Wang，z) LIKE ( Wang, ds ) T規(guī)則及假言推理36優(yōu)點：表達定理證明過程自然，易理解。擁有豐富的推理規(guī)則，推理過程靈活。便于嵌入領(lǐng)域啟發(fā)式知識。3.2 自然演繹推理 缺點：易產(chǎn)生組合爆炸，得到的中間結(jié)論一般呈指數(shù)形式遞增。37歸結(jié)演繹推理第3章 確定性推理方法3.1 推理的基本概念 3.2 自然演繹推理3.3 謂詞公式化為子句集的方法3.4

14、海伯倫定理3.5 魯賓遜歸結(jié)原理3.6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 38歸 結(jié) 演 繹 推 理反證法： ，當且僅當 ， 即 Q為 P 的邏輯結(jié)論，當且僅當 是不可滿足的。 定理：Q 為 ， ， 的邏輯結(jié)論，當且僅當 是不可滿足的。39歸 結(jié) 演 繹 推 理思路：定理 不可滿足 子句集不可滿足 海伯倫定理 魯賓遜歸結(jié)原理403.3 謂詞公式化為子句集的方法 原子（atom）謂詞公式： 一個不能再分解的命題。 文字（literal）：原子謂詞公式及其否定。 ：正文字， ：負文字。 子句（clause）：任何文字的析取式。任何文字本身也都是子句。 空子句（NIL）：不包含任何文字的子句。

15、子句集：由子句構(gòu)成的集合。空子句是永假的，不可滿足的。413.3 謂詞公式化為子句集的方法 例2 將下列謂詞公式化為子句集。 解：（1）消去謂詞公式中的“ ”和“ ”符號 雙重否定律 德.摩根律 量詞轉(zhuǎn)換律 （2）把否定符號 移到緊靠謂詞的位置上（3）變量標準化 3.3 謂詞公式化為子句集的方法42 （4）消去存在量詞 a. 存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)。 b. 存在量詞出現(xiàn)在一個或者多個全稱量詞的轄域內(nèi)。Skolem化：用Skolem函數(shù)代替每個存在量詞量化的變量的過程。 （5）化為前束形 前束形=（前綴）母式（前綴）：全稱量詞串。 母式：不含量詞的謂詞公式。 3.3 謂詞公式化為子句集

16、的方法433.3 謂詞公式化為子句集的方法（6）化為 Skolem 標準形 Skolem 標準形：M：子句的合取式，稱為Skolem標準形的母式。 （7）略去全稱量詞 （8）消去合取詞 （9）子句變量標準化 443.3 謂詞公式化為子句集的方法 例3 將下列謂詞公式化為子句集。（1）消去蘊含符號（2）把否定符號移到每個謂詞前面 （3）變量標準化 （4）消去存在量詞，設(shè)y的函數(shù)是f(x)，則 453.3 謂詞公式化為子句集的方法 例3 將下列謂詞公式化為子句集。（續(xù)）（5）化為前束形 （6）化為標準形 （7）略去全稱量詞 （8）消去合取詞，把母式用子句集表示 （9）子句變量標準化 463.3 謂

17、詞公式化為子句集的方法 例4 將下列謂詞公式化為不含存在量詞的前束形。（1）消去存在量詞 （2）消去蘊含符號 （3）設(shè)z的函數(shù)是g(y)，則 473.3 謂詞公式化為子句集的方法定理 3.1: 謂詞公式不可滿足的充要條件是其子句集不可滿足。謂詞公式不可滿足性子句集不可滿足性？48歸結(jié)演繹推理第3章 確定性推理方法3.1 推理的基本概念 3.2 自然演繹推理3.3 謂詞公式化為子句集的方法3.4 海伯倫定理3.5 魯賓遜歸結(jié)原理3.6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 49定義3.1（ H 域） 設(shè) S 為子句集，則按下述方法構(gòu)造的域 稱為海伯倫域，簡記為 H 域。（1）令 是 S 中所有個

18、體常量的集合，若 S 中不包含個體常量，則令 ，其中 為 任意指定的一個個體常量。（2）令 S 中所有 n 元函數(shù) 是 H 中的元素，其中 。 3.4 海伯倫（Herbrand）定理 503.4 海伯倫（Herbrand）定理 例5 求子句集 的 H 域。 解：指定一個常量 作為個體常量，則得：.513.4 海伯倫（Herbrand）定理 例6 求子句集 的 H 域。 解：根據(jù) H 域的定義得：.523.4 海伯倫（Herbrand）定理 例7 求子句集 的 H 域。 解：根據(jù) H 域的定義得： 例8 求子句集 的 H 域。 解：根據(jù) H 域的定義得：)(),(),(),(),(),(,)()

19、,(),(),(),(),(12aggafgagfaffagafaggafgagagfffafHHaa=533.4 海伯倫（Herbrand）定理 基子句：用H 域中的元素代換子句中的變元后所得的子句，其中的謂詞稱為基原子。原子集：子句集中所有基原子構(gòu)成的集合。子句集在 H 域上的解釋：對子句集中出現(xiàn)的常量、函數(shù)及謂詞取值，一次取值就是一個解釋。 定理 3.2（海伯倫定理）： 子句集不可滿足的充要條件是存在一個有限的不可滿足的基子句集 。54歸結(jié)演繹推理第3章 確定性推理方法3.1 推理的基本概念 3.2 自然演繹推理3.3 謂詞公式化為子句集的方法3.4 海伯倫定理3.5 魯賓遜歸結(jié)原理3.

20、6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 553.5 魯賓遜歸結(jié)原理 魯賓遜歸結(jié)原理（消解原理）的基本思想：檢查子句集 S 中是否包含空子句，若包含，則 S 不可滿足。若不包含，在 S 中選擇合適的子句進行歸結(jié)，一旦歸結(jié)出空子句，就說明 S 是不可滿足的。子句集中子句之間是合取關(guān)系，只要有一個子句不可滿足， 則子句集就不可滿足。 563.5 魯賓遜歸結(jié)原理1. 命題邏輯中的歸結(jié)原理（基子句的歸結(jié)） 定義3.3（歸結(jié)）：設(shè)C1與C2是子句集中的任意兩個子句，如果 C1中的文字L1與 C2中的文字L2互補，那么從C1和 C2中分別消去L1和L2，并將二個子句中余下的部分析取，構(gòu)成一個新子句C12

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

22、例：？定義 3.4 ：設(shè)是 兩個沒有相同變元的子句， 和 分別是 中的文字，若 是 的最一般合一，則稱 為 的二元歸結(jié)式。 最一般合一593.5 魯賓遜歸結(jié)原理例10 設(shè)： 求其二元歸結(jié)式。得： 解：令 選 則603.5 魯賓遜歸結(jié)原理例11 設(shè)： 求其二元歸結(jié)式。則得： 解： 選613.5 魯賓遜歸結(jié)原理對于謂詞邏輯，歸結(jié)式是其親本子句的邏輯結(jié)論。 對于一階謂詞邏輯，即若子句集是不可滿足的，則必存在一個從該子句集到空子句的歸結(jié)演繹；若從子句集存在一個到空子句的演繹，則該子句集是不可滿足的。如果沒有歸結(jié)出空子句，則既不能說 S 不可滿足，也不能說 S 是可滿足的。 62歸結(jié)演繹推理第3章 確定

23、性推理方法3.1 推理的基本概念 3.2 自然演繹推理3.3 謂詞公式化為子句集的方法3.4 海伯倫定理3.5 魯賓遜歸結(jié)原理3.6 歸結(jié)反演3.7 應(yīng)用歸結(jié)反演求解問題 633.6 歸結(jié)反演應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。用歸結(jié)反演證明的步驟是：（1）將已知前提表示為謂詞公式F。（2）將待證明的結(jié)論表示為謂詞公式Q，并否定得到 Q 。（3）把謂詞公式集F， Q 化為子句集S。（4）應(yīng)用歸結(jié)原理對子句集S中的子句進行歸結(jié)，并把每次 歸結(jié)得到的歸結(jié)式都并入到S中。如此反復(fù)進行，若出 現(xiàn)了空子句，則停止歸結(jié)，此時就證明了Q為真。643.6 歸結(jié)反演 例12 某公司招聘工作人員，A，B ，C

24、 三人應(yīng)試，經(jīng)面試后公司表示如下想法：（1）三人中至少錄取一人。（2）如果錄取 A 而不錄取 B ，則一定錄取 C。（3） 如果錄取 B ，則一定錄取 C 。 求證：公司一定錄取 C。 653.6 歸結(jié)反演證明：公司的想法用謂詞公式表示： 。 把要求證的結(jié)論用謂詞公式表示出來并否定，得：（1）（2）（3） （4） 把上述公式化成子句集： （1）（2）（3）（4）663.6 歸結(jié)反演應(yīng)用歸結(jié)原理進行歸結(jié)： （5） （1）與（2）歸結(jié)（6） （3）與（5）歸結(jié)（7） （4）與（6）歸結(jié) 673.6 歸結(jié)反演 例13 已知： 規(guī)則1：任何人的兄弟不是女性； 規(guī)則2：任何人的姐妹必是女性。 事 實：Mary 是 Bill 的姐妹。 求證： Mary 不是 Tom 的兄弟。 證明：定義謂詞 brother ( x, y ) : x 是 y 的兄弟 sister ( x, y ) : x 是 y 的姐妹 woman ( x ) : x 是女性683.6 歸結(jié)反演證明：將規(guī)則與事實用謂詞公式表示： 把要求證的結(jié)論用謂詞公式