1、人工智能原理及應用,第3章 確定性推理方法 二零一二年元月,AI （6）化為Skolem標準形; （7）消去全稱量詞：由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關緊要，因此可以省掉全稱量詞。 （8）消去合取詞：在母式中消去所有合取詞，把母式用子句集的形式表示出來。 （9）更換變量名稱：對子句集中的某些變量重新命名，使任意兩個子句中不出現相同的變量名。,3.4 歸結推理方法,3.4.1 子句集及其化簡,例：將下列謂詞公式化成子句集。 解：轉換過程遵照上述9個步驟。 (1) (2) (3) (4) (5) (6) (7),3.4 歸結推理方法,3.4.1 子句集及其化簡,例：將

2、下列謂詞公式化成子句集。 解：轉換過程遵照上述9個步驟。 (8)子句集為： (9)子句變量標準化后，最終的子句集為：,3.4 歸結推理方法,3.4.1 子句集及其化簡,當原謂詞公式為非永假時，它與其標準子句集并不等價。當原謂詞公式為永假（或不可滿足）時，其標準子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。這個結論很重要，是歸結原理的主要依據，可用定理的形式來描述。 定理3.1 設有謂詞公式F，其標準子句集為S，則F為不可滿足的充要條件是S為不可滿足的。,3.4 歸結推理方法,3.4.2 Herbrand（海伯倫）定理,1H域及其原子集： 定義3.15 H域：設G是謂詞公式，

3、定義在論域D上，令H0是G中所出現的常量的集合。若G中沒有常量出現，就任取常量aD，而規(guī)定H0=a； 其中f(t1,tn)是出現于G中的任一函數符號，而t1tn是Hi-1的元素，i=1,2,。規(guī)定H為G的H域。(或說是相應的子句集S的H域)。,3.4 歸結推理方法,3.4.2 Herbrand（海伯倫）定理,2對H域的解釋問題： 定義3.16 如果子句集S的原子集為A，則對A中各元素的真假值的一個具體設定都是S的一個H解釋。 定理3.2 設I是S的論域D上的解釋，存在對應于I的H解釋 ，使得若有 必有 。 定理3.3 子句集S是不可滿足的，當且僅當所有的S的H解釋下為假。 定理3.4 子句集S

4、是不可滿足的，當且僅當對每一個解釋I下，至少有S的某個子句的某個基例為假。,3.4 歸結推理方法,3.4.2 Herbrand（海伯倫）定理,3Herbrand（海伯倫）定理 定理3.5 設有謂詞公式F，其標準形的子句集為S，則F不可滿足的充要條件是S不可滿足。 Herbrand（海伯倫）定理如下： 定理3.6 子句集S不可滿足的充要條件是：該子句集S在H域中的所有解釋都為假。 定理3.7 子句集S不可滿足的充要條件是存在一個不可滿足的基子句集S。 對Herbrand（海伯倫）定理一般通俗性解釋是：如果一個一階謂詞公式是永真的 ，則該公式的機器定理證明求解計算可在有限步內實現證明；如果該公式不

5、是永真的，則無法在有限步內實現證明。,3.4 歸結推理方法,3.4.2 Herbrand（海伯倫）定理,3Herbrand（海伯倫）定理 例：對子句集 畫出相應的語義樹。 解：,3.4 歸結推理方法,3.4.2 Herbrand（海伯倫）定理,3Herbrand（海伯倫）定理 Herbrand定理用于語義樹解釋有： 定理3.8 子句集S是不可滿足的，當且僅當對應于S的完全語義樹都是一棵有限的封閉語義樹。 定理3.9 子句集S是不可滿足的，當且僅當存在不可滿足的有限基例集（即存在有限個失敗結點）。 Herbrand定理給出了一階邏輯的半可判定算法。其中的“半”字指的是有條件下的判定算法，即僅當被

6、證定理是成立的，使用該算法方可得證。而當被證定理并不成立時，使用該算法得不出任何結果。,3.4 歸結推理方法,3.4.3 Robinson（魯賓遜）歸結原理,歸結原理由J.A.Robinson于1965年提出，又稱為消解原理。該原理是Robinson在Herbrand理論基礎上提出的一種基于邏輯的、采用反證法的推理方法。由于其理論上的完備性，歸結原理成為機器定理證明的主要方法。 1命題邏輯中的歸結原理： 定義3.17 若P是原子謂詞公式或原子命題，則稱P與P為互補文字。 定義3.18 設C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，則從C1和C2中可以分別消去

7、L1和L2，并將二子句中余下的部分做析取構成一個新的子句C12，稱這一過程為歸結，所得到的子句C12稱為C1和C2的歸結式，而稱C1和C2為C12的親本子句。,3.4 歸結推理方法,3.4.3 Robinson（魯賓遜）歸結原理,1命題邏輯中的歸結原理： 定理3.10 歸結式C12是其親本子句C1和C2的邏輯結論。 定理3.11 推論：設C1和C2是子句集S上的子句，C12是C1和C2的歸結式。如果把C12加入子句集S后得到新子句集S1，則S1和S在不可滿足的意義下是等價的。即： S是不可滿足的 S1是不可滿足的 根據上述定理，有歸結推理過程如下： (1)對子句集S中的各子句間使用歸結推理規(guī)則

8、。 (2)將歸結所得的歸結式放入子句集S中，得新子句集S。 (3)檢查子句集S中是否有空子句(NIL),若有則停止推理； (4)置S=S，轉步驟（1）。,3.4 歸結推理方法,3.4.3 Robinson（魯賓遜）歸結原理,2一階謂詞邏輯中的歸結原理 定義3.19 設C1和C2是兩個沒有相同變元的子句， L1和L2分別是C1和C2 的文字，如果 L1與 L2有最一般合一 ，則把： 稱作子句 C1和C2的一個二元歸結式，而 L1和L2是被歸結的文字。,3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,對于給定的一個謂詞公式集F，要證明謂詞公式集F能推導出目標公式G，可應用歸結原理證明步

9、驟如下： （1）否定結論G，得到G； （2）將前提條件F和G轉化為子句集S （3）應用歸結原理，對子句集S反復進行歸結，若能歸結出空子句，則證明子句集S的不可滿足性，也即FG為真。,3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,例：快樂學生問題，假設： 任何通過計算機考試并獲獎的人都是快樂的 任何肯學習或幸運的人都可以通過所有的考試 張不肯學習但他是幸運的 任何幸運的人都能獲獎。 求證：張是快樂的。,3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,證明：先將問題用謂詞表示如下： R1:“任何通過計算機考試并獲獎的人都是快樂的” R2:“任何肯學習或幸運的人都可以通過所

10、有考試” R3:“張不肯學習但他是幸運的” R4:“任何幸運的人都能獲獎” 結論“張是快樂的”的否定,3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,證明： 首先將每一個表示邏輯條件的謂詞子句轉換為子句集可以接受的Skolem標準形。由R1可得： (1) 由R2可得 (2) (3) 由R3可得 (4) (5),3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,證明： 首先將每一個表示邏輯條件的謂詞子句轉換為子句集可以接受的Skolem標準形。 由R4可得 (6) 由結論可得 (7) 此為結論的否定,3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,證明： 根據以

11、上7條子句，歸結如下： (8) (1)(6)歸結 (9) (8)(7)歸結 (10) (9)(5)歸結 (11) (10)(3)歸結 (12) NIL (11) (5)歸結 原題得證。,3.4 歸結推理方法,3.4.4 利用歸結推理進行定理證明,證明：其歸結反演樹如圖：,3.4 歸結推理方法,3.4.5 應用歸結原理進行問題求解,應用歸結原理不僅可以進行結論的證明，同時也可以利用歸結原理進行問題的求解。步驟如下： （1）把已知前提條件用謂詞公式表示出來，并化成相應的子句集，設該子句集的名字為S1。 （2）把待求解的問題也用謂詞公式表示出來，然后將其否定，并與一謂詞ANSWER構成析取式。謂詞A

12、NSWER是一個專為求解問題而設置的謂詞，其變量必須與問題公式的變量完全一致。 （3）把問題公式與謂詞ANSWER構成的析取式化為子句集，并把該子句集與S1合并構成子句集S。 （4）對子句集S應用謂詞歸結原理進行歸結，在歸結的過程中，通過合一置換，改變ANSWER中的變元。 （5）如果得到歸結式ANSWER ，問題的答案即在ANSWER謂詞中。,3.4 歸結推理方法,3.4.5 應用歸結原理進行問題求解,例：求解問題,已知: 如果x和y是同班同學,則x的老師也是y的老師； 王先生是小李的老師； 小李和小張是同班同學； 問小張的老師是誰? 解：定義謂詞 ：x是y的老師； ：x與y是同班同學；則已

13、知可表示成如下的謂詞公式：,3.4 歸結推理方法,3.4.5 應用歸結原理進行問題求解,例：以上謂詞公式及結論的反化成子句集如下: C(x,y)T(z,x)T(z,y) 歸結 歸結 NIL 歸結 說明zhang的老師存在.,3.4 歸結推理方法,3.4.5 應用歸結原理進行問題求解,例：為了求解用一個重言式代替： 用重言式代替結論的否定, 恒為真 歸結 歸結 歸結 可得到問題的結果:張的老師是王先生。 也可用輔助謂詞ANS(u) 用輔助謂詞ANS(u) 歸結 歸結 歸結 也得結果:張的老師是王先生。,3.5 歸結過程中的控制策略,3.5.1 引入控制策略的原因 3.5.2 歸結控制策略,3.5

14、 歸結過程中的控制策略,3.5.1 面向對象的概念與特性,無控制的盲目全面歸結導致大量的不必要的歸結式的產生，如何給出控制策略，以使系統僅選擇合適的子句對其做歸結來避免多余不必要的歸結式的出現，或者說少做些歸結但仍然導出空子句來，這已經成為一個重要的問題。 歸納起來，歸結過程策略控制的要點如下： 要解決的問題：歸結方法的知識爆炸。 控制策略的目的：歸結點盡量少 控制策略的原則：刪除不必要的子句，或對參加歸結的子句做限制。給出控制策略，以使僅選擇合適的子句對其做歸結。避免多余的、不必要的歸結式出現。,3.5 歸結過程中的控制策略,3.5.2 歸結控制策略,歸結策略大致可分為兩大類：刪除策略和限制

15、策略。 3.5.2.1 刪除策略 定義3.20 歸類：設有兩個子句C和D，若有置換使得C D成立，則稱子句C把子句D歸類。 刪除策略的主要想法是：歸結過程在尋找可歸結子句時，子句集中的子句越多，需要付出的代價就會越大。如果在歸結時能把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數，從而提高歸結效率。 盡管使用刪除策略的歸結，少做了歸結但不影響產生空子句，就是說刪除策略的歸結推理是完備的。,3.5 歸結過程中的控制策略,3.5.2 歸結控制策略,3.5.2.2 語義歸結策略 語義歸結策略是將子句S按照一定的語義分成兩部分，約定每部分內的子句間不允許作歸結。同時還引入了文字次序，約定歸結

16、時其中的一個子句的被歸結文字只能是該子句中最大的文字。 語義歸結策略的歸結是完備的，同樣，所有可歸結的謂詞公式都可以用采用語義歸結策略達到加快歸結速度的目的。 3.5.2.3 線性歸結策略 在歸結過程中,除第一次歸結可用給定的子句集S中子句（該子句稱為頂子句）外,其后各次歸結則至少要有一個親本子句是上次歸結的結果。線性歸結可用一個歸結演繹樹加以表示。線性歸結策略也是完備的。,3.5 歸結過程中的控制策略,3.5.2 歸結控制策略,3.5.2.4 輸入歸結策略 每次參加歸結的兩個親本子句，必須至少有一個子句是初始子句集S中的子句。輸入歸結策略是不完備的。例如子句集 是不可滿足的，但用輸入歸結策略不能導出空子句。 3.5.2.5 單元歸結策略 每次