第3章 確定性推理方法.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

14、 歸結(jié)過程中的控制策略,3.5.1 面向?qū)ο蟮母拍钆c特性,無控制的盲目全面歸結(jié)導(dǎo)致大量的不必要的歸結(jié)式的產(chǎn)生，如何給出控制策略，以使系統(tǒng)僅選擇合適的子句對其做歸結(jié)來避免多余不必要的歸結(jié)式的出現(xiàn)，或者說少做些歸結(jié)但仍然導(dǎo)出空子句來，這已經(jīng)成為一個重要的問題。 歸納起來，歸結(jié)過程策略控制的要點如下： 要解決的問題：歸結(jié)方法的知識爆炸。 控制策略的目的：歸結(jié)點盡量少 控制策略的原則：刪除不必要的子句，或?qū)⒓託w結(jié)的子句做限制。給出控制策略，以使僅選擇合適的子句對其做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)。,3.5 歸結(jié)過程中的控制策略,3.5.2 歸結(jié)控制策略,歸結(jié)策略大致可分為兩大類：刪除策略和限制

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

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