人工智能原理及應用第3章確定性推理方法

二零一二年元月AI&itsApplications第3章確定性推理方法確定性推理方法

知識是人工智能研究的一個核心問題，它包括兩個方面：知識表示和知識推理，即如何在人工智能中清晰地表示人類的常識，并運用這些常識去進行符合人類行為的推理。按照推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。自然演繹推理和歸結推理是經典的確定性推理，它們以數理邏輯的有關理論、方法和技術為理論基礎，是機械化的、可在計算機上加以實現的推理方法。第3章確定性推理方法第3章主要內容3.1 推理概述

3.2 確定性推理的邏輯基礎

3.3 演繹推理方法

3.4 歸結推理方法

3.5 歸結過程中的控制策略

第3章確定性推理方法3.1推理概述

3.1.1推理的概念

3.1.2推理的方法

3.1.3推理的控制策略

3.1.4推理中的沖突

第3章確定性推理方法3.1推理概述

3.1.1推理的概念

所謂推理是指按照某種策略從已知事實出發去推出結論的過程。知識推理是指在計算機或智能機器中，在知識表達的基礎上，利用形式化的知識模型，進行機器思維求解問題，實現狀態轉移的智能操作序列。推理所用的事實可分為兩種情況，一種是與求解問題有關的初始證據；另一種是推理過程中所得到的中間結論，這些中間結論可以作為進一步推理的已知事實或證據。例：①商品是用來交換的，所以，有些用來交換的是商品。②老虎是要吃人的，東北虎是老虎；所以，東北虎是要吃人的。智能系統的推理包括兩個方面的基本問題：一個方面是推理的方法，另一個方面是推理的控制策略。第3章確定性推理方法3.1推理概述

3.1.2推理的方法

推理有很多種方法，根據知識表示方式分類分為“圖搜索”方法及“邏輯論證”方法；根據邏輯基礎分類可分為演繹推理、歸納推理、默認（缺省）推理；根據知識的確定性分類分為確定性推理與非確定性推理；根據推理過程的單調性分類分為單調推理、非單調推理。1．演繹推理：演繹推理是一種由一般到個別的推理方法，其核心是三段論，由一個大前提、一個小前提和一個結論這三部分組成的。其邏輯式為：大前提是已知的一般性知識或推理過程得到的判斷；小前提是關于某種具體情況或某個具體實例的判斷；結論是由大前提推出的，并且適合于小前提的判斷。第3章確定性推理方法3.1推理概述

3.1.2推理的方法

1．演繹推理：例：有如下三個判斷：①計算機系的學生都會編程序；（一般性知識）②程強是計算機系的一位學生；（具體情況）③因此程強會編程序。（結論）這是一個三段論推理。其中：“①計算機系的學生都會編程序”是大前提，“②程強是計算機系的一位學生”是小前提，那么“③程強會編程序”是經演繹推出來的結論。其結論蘊含在大前提中，這就是典型的演繹推理三段論。第3章確定性推理方法3.1推理概述

3.1.2推理的方法2．歸納推理歸納推理的基本思想是：先從已知事實中猜測出一個結論，然后對這個結論的正確性加以驗證。例如常用的數學歸納法。歸納推理的類型按照所選取的事例的廣泛性可分為完全歸納推理、不完全歸納推理。歸納推理按照推理所使用的方法可分為枚舉歸納推理、類比歸納推理、默認推理等。（1）枚舉歸納推理：是由已觀察到的事物都有某屬性，而沒有觀察到相反的事例，從而推出某類事物都有某屬性。（2）類比歸納推理：指在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它們在其它屬性上也相同或相似的一種歸納推理。（3）默認推理：稱為缺省推理，它是在知識不完全的情況下假設某些條件已經具備所進行的推理。第3章確定性推理方法3.1推理概述

3.1.2推理的方法3．演繹推理與歸納推理的區別：演繹推理是在已知領域內的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結論的正確性。它所得出的結論實際上早已蘊含在一般性知識的前提中，演繹推理只不過是將已有事實揭露出來，因此它不能增殖新知識。歸納推理所推出的結論是沒有包含在前提內容中的。這種由個別事物或現象推出一般性知識的過程，是增殖新知識的過程。4．推理的其它分類：（1）確定性推理與不確定推理（2）單調推理與非單調推理（3）啟發式推理與非啟發式推理第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策略，主要是指推理方向的選擇、推理時所用的搜索策略及沖突解決策略等。推理的控制策略包括推理策略和搜索策略。推理策略主要解決推理方向、求解策略、沖突消解策略等問題。搜索策略主要解決推理線路、推理效果、推理效率等問題。按照對推理方向的控制，推理可分為正向推理、反向推理、混合推理及雙向推理四種情況。一般都要求系統具有三個要素：一個存放知識的知識庫

一個存放初始事實和中間結果的數據庫

一個用于推理的推理機第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.1正向推理正向推理是由已知事實出發，正向使用推理規則向結論方向的推理，算法步驟描述如下：（1）把用戶提供的初始證據放入綜合數據庫；（2）檢查綜合數據庫中是否包含了問題的解，若已包含，則求解結束，并成功推出；否則執行下一步；第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.1正向推理（3）檢查知識庫中是否有可用知識，若有，形成當前可用知識集，執行下一步；否則轉(5)。（4）按照某種沖突消解策略，從當前可用知識集中選出一條規則進行推理，并將推出的新事實加入綜合數據庫種，然后轉(2)。第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.1正向推理（5）詢問用戶是否可以進一步補充新的事實，若可補充，則將補充的新事實加入綜合數據庫中，然后轉(3)；否則表示無解，失敗退出。第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略例：請用正向推理完成以下問題的求解：假設知識庫中包含有以下2條規則：

r1：

IFBTHENC

r2：

IFATHENB已知初始證據A，求證目標C。解：本例的推理過程如下：推理開始前，綜合數據庫為空。推理開始后，先把A放入綜合數據庫，然后檢查綜合數據庫中是否含有該問題的解，回答為“N”。接著檢查知識庫中是否有可用知識，顯然r2可用，形成僅含r2的知識集。從該知識集中取出r2，推出新的實事B，將B加入綜合數據庫，檢查綜合數據庫中是否含有目標C，回答為“N”。再檢查知識庫中是否有可用知識，此時由于B的加入使得r1為可用，形成僅含r1的知識集。從該知識集中取出r1，推出新的實事C，將C加入綜合數據庫，檢查綜合數據庫中是否含有目標C，回答為“Y”。

它說明綜合數據庫中已經含有問題的解，推理成功結束，目標C得證。第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.2反向推理反向推理是以某個假設目標作為出發點的一種推理，又稱為目標驅動推理或逆向推理。反向推理過程如圖：第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.2反向推理算法描述如下：（1）將要求證的目標（稱為假設）構成一個假設集；（2）從假設集中選出一個假設，檢查該假設是否在綜合數據庫中，若在，則該假設成立，此時，若假設集為空，則成功退出，否則仍執行(2)；若該假設不在數據庫中，則執行下一步；（3）檢查該假設是否可由知識庫的某個知識導出，若不能由某個知識導出，則詢問用戶該假設是否為可由用戶證實的原始事實，若是，該假設成立，并將其放入綜合數據庫，再重新尋找新的假設，若不是，則轉(5)；若能由某個知識導出，則執行下一步；（4）將知識庫中可以導出該假設的所有知識構成一個可用知識集；（5）檢查可用知識集是否為空，若是，失敗退出；否則執行下一步；（6）按沖突消解策略從可用知識集中取出一個知識，繼續；（7）將該知識的前提中的每個子條件都作為新的假設放入假設集，然后轉(2)。第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略例：請用反向推理完成以下問題的求解：假設知識庫中包含有以下2條規則：

r1：

IFBTHENC

r2：

IFATHENB已知初始證據A，求證目標C。解：其推理過程如下：推理開始前，綜合數據庫和假設集均為空。先將初始證據A和目標C分別放入綜合數據庫和假設集，然后從假設集中取出一個假設C，查找C是否為綜合數據庫中的已知事實，回答為“N”。再檢查C是否能被知識庫中的知識所導出，發現C可由r1導出，于是r1被放入可用知識集。接著從可用知識集中取出r1，將其前提條件B作為新的假設放入假設集。檢查B是否為綜合數據庫中的實事，回答為“N”。再檢查B是否能被知識庫中的知識所導出，發現B可由r2導出，于是r2被放入可用知識集。從可用知識集中取出r2，將其前提條件A作為新的假設放入假設集。然后從假設集中取出A，檢查A是否為綜合數據庫中的實事，回答為“Y”。說明該假設成立，由于無新的假設，故推理過程成功結束，于是目標C得證。第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.3正反向混合推理正向推理和反向推理相結合的推理方法稱為正反向混合推理。混合推理的方法包括：1.先正向后逆向2.先逆向后正向3.雙向混合第3章確定性推理方法3.1推理概述

3.1.4推理中的沖突在推理過程中，系統要不斷地用數據庫中的事實與知識庫中的規則進行匹配，當有一個以上規則的條件部分和當前數據庫相匹配時，就需要有一種策略來決定首先使用哪一條規則，這就是沖突解決策略。沖突解決策略實際上就是確定規則的啟用順序。常用排序方法有如下幾種:（1）按專一性排序

（2）按規則排序（3）按數據排序

（4）按就近原則排序（5）上下文限制

（6）按匹配度排序（7）按條件個數排序第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.1命題公式的解釋3.2.2等價式3.2.3永真蘊含式3.2.4前束范式與Skolem范式3.2.5置換與合一本節中要考慮在人工智能中如何利用謂詞邏輯表示來完成由問題到結論的推理。第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.1命題公式的解釋

定義3.1設D是謂詞公式P的非空個體域，若對P中的個體常量、函數和謂詞按如下規定賦值：（1）為每個個體常量指派D中的一個元素；（2）為每個n元函數指派一個從

到D的一個映射，其中（3）為每個n元謂詞指派一個從

到{F，T}的映射。則稱這些指派為P在D上的一個解釋I。定義3.2對于謂詞公式P，如果至少存在D上的一個解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.2等價式

定義3.3設P與Q是D上的兩個謂詞公式，若對D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D上是等價的。如果D是任意非空個體域，則稱P與Q是等價的，記作

。常用謂詞公式的等價式包括：（1）雙重否定律：

（2）交換律：

（3）結合律：

（4）分配律：

（5）摩根定律：

第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.2等價式常用謂詞公式的等價式包括：（6）吸收律：

（7）補余律:（8）連詞化歸律:

（9）量詞轉換律:

（10）量詞分配律:第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.3永真蘊含式

定義3.4對謂詞公式P和Q，如果

永真，則稱P永真蘊含Q，且稱Q為P的邏輯結論，P為Q的前提，記作。常用永真蘊含式包括：（1）化簡式：

（2）附加式：

（3）析取三段論：

（4）假言推理：

（5）拒取式：

第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.3永真蘊含式

常用永真蘊含式包括：（6）假言三段論：

（7）二難推理：

（8）全稱固化：

其中，y是個體域中的任一個體，依此可消去謂詞公式中的全稱量詞。（9）存在固化：

其中，y是個體域中某一個可以使

P(y)為真的個體，依此可消去謂詞公式中的存在量詞。第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.4前束范式與Skolem范式

范式分為兩種：前束范式與Skolem范式。定義3.5設F為一謂詞公式，如果其中的所有量詞均非否定地出現在公式的最前面，且它們的轄域為整個公式，則稱F為前束范式。一般形式：其中，

為前綴，它是一個由全稱量詞或存在量詞組成的量詞串；為母式，它是一個不含任何量詞的謂詞公式。例:定義3.6如果前束范式中所有的存在量詞都在全稱量詞之前，則稱這種形式的謂詞公式為Skolem范式。例：第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.5置換與合一

1．置換：定義3.7置換是形如：的有限集合。其中，

是項，

是互不相同的變元；

表示用t1

替換x1，并且要求t1

與x1

不能相同，x1

不能循環地出現在另一個t1

中。定義3.8設

是一個置換，F是一個謂詞公式，把公式F中出現的所有

換成

得到一個新的公式G，記作G=Fθ，稱G為F在置換θ下的例示。第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.5置換與合一

1．置換：定義3.9設是兩個置換。則θ與λ的合成也是一個置換，記作

。它是從集合:中刪去以下兩種元素：

①當

時，刪去

②當

時，刪去

最后剩下的元素所構成的集合。第3章確定性推理方法3.2確定性推理的邏輯基礎3.2.5置換與合一2．合一：定義3.10設有公式集

若存在一個置換θ，可使:

則稱θ是F的一個合一。稱F1,F2,…,Fn是可合一的。定義3.11設

是公式集F的一個合一，如果對F的任一個合一

都存在一個置換

，使得

，則稱

是一個最一般合一。第3章確定性推理方法3.3演繹推理方法3.3.1什么是演繹推理3.3.2演繹推理的特點基于規則的演繹推理是一種直接的推理方法。它不再把有關的知識轉化為子句集，而是把有關問題的知識和信息劃分為規則與事實兩種類型。規則由包含蘊含形式的表達式表示，事實由無蘊含式的表達式表示，并畫出相應的與/或圖，然后通過規則進行演繹推理。第3章確定性推理方法3.3演繹推理方法3.3.1什么是演繹推理所謂自然演繹推理，在已知一組為真的事實條件下，直接運用命題和謂詞邏輯的一系列基本規則或定律來推出結論，該過程稱為自然演繹推理。基于規則的演繹推理可分為正向演繹推理、反向演繹推理和正反向混合演繹推理。第3章確定性推理方法3.3演繹推理方法3.3.1什么是演繹推理3.3.1.1正向演繹推理1．事實表達式及其與/或圖正向演繹推理步驟如下：利用等價式P→Q與～P∨Q消去蘊含符“→”。把否定符號“～”移到每個謂詞符號的前面。變量標準化，即重新命名變量，使不同量詞約束的變量有不同的名字。引入Skolem函數消去存在量詞。將公式化為前束形。略去全稱量詞(這時默認事實表達式中尚存的變量是全稱量詞量化的變量)。重新命名變量；使同一變量不出現在不同的主要合取式中。第3章確定性推理方法3.3演繹推理方法3.3.1.1正向演繹推理2．F規則在與/或形正向演繹系統中，通常要求F規則應具有如下形式：L為單文字，W為與/或形公式。其變換步驟如下：（1）暫時消去蘊含符號“→”。（2）把否定符號“～”移到緊靠謂詞的位置上，使其作用域僅限于單個謂詞。（3）引入Skolem函數，消去存在量詞。（4）化成前束式，消去全部全稱量詞。（5）恢復蘊含式表示。第3章確定性推理方法3.3演繹推理方法3.3.1.1正向演繹推理3．規則正向演繹與/或樹正向演繹系統要求目標公式用子句形表示。如果目標公式不是子句形，則需要化成子句形。規則正向演繹推理過程是先用與/或樹把已知事實表示出來，然后再用F規則的前件和與或樹的葉節點進行匹配，并通過一個匹配弧把匹配成功的F規則加入到與/或樹中，依此使用F規則，直到產生一個含有以目標節點為終止節點的解圖為止。第3章確定性推理方法3.3演繹推理方法3.3.1.1正向演繹推理3．規則正向演繹(1)命題邏輯規則演繹過程：例：設已知事實為：

F規則為：

目標公式為：命題邏輯的規則演繹過程第3章確定性推理方法3.3演繹推理方法3.3.1.1正向演繹推理3．規則正向演繹(2)謂詞邏輯規則演繹過程例：設已知事實的與/或形表示為：F規則為：目標公式為：命題邏輯的規則演繹過程第3章確定性推理方法3.3演繹推理方法3.3.1什么是演繹推理3.3.1.2逆向演繹推理從目標表達式出發，反方向使用規則（B規則）對目標表達式的與或圖進行變換，最后得到含有事實節點的一致解圖。1．目標表達式的與或形表示：在基于規則的逆向系統中，要用對偶形式對目標表達式進行Skolem化。即消去全稱量詞，對受全稱量詞約束的變量用Skolem函數或者常量代替，省略存在量詞，所有變量默認為受存在量詞約束，并進行變量換名，使得目標公式的主析取元之間具有不同的變量名。第3章確定性推理方法3.3演繹推理方法3.3.2逆向演繹推理1．目標表達式的與或形表示：例：目標公式：

Skolem化后：

變量標準化：這個目標的與或圖表示如圖，其子句集可以從結束在端節點的解圖集中讀得：第3章確定性推理方法3.3演繹推理方法3.3.2逆向演繹推理2．規則的應用逆向演繹推理以逆向方式使用規則（稱為B規則），要求規則化簡為以下形式：其中，L為單文字，W是與或形；規則的激活取決于L和與或圖葉節點的匹配。逆向系統演繹過程的結束條件是生成的與或圖含有事實表達式，而事實表達式限制為文字的合取形式。當事實表達式有一個文字同與或圖中某一個端節點所標記的文字（子目標）匹配上時，就可以通過匹配弧把事實文字加到圖上。這樣當最后得到的與或圖包含一個結束在事實節點上的一致解圖時，系統便結束演繹，一個一致解圖是解圖中匹配弧置換集具有合一復合置換的那個解圖。第3章確定性推理方法3.3演繹推理方法3.3.2逆向演繹推理2．規則的應用例：下面通過一個簡例說明逆向系統的演繹過程。設有如下事實：FIDO是一只狗FIDO不叫FIDO擺尾巴MYRTLE瞄瞄叫規則如下：擺尾巴的狗是友好的友好且不叫的是不令對方害怕的第3章確定性推理方法3.3演繹推理方法3.3.2逆向演繹推理2．規則的應用例：狗是動物貓是動物喵喵叫的是貓問題是：是否存在一只貓和一只狗，使這只貓不怕這只狗？即目標公式：第3章確定性推理方法3.3演繹推理方法3.3.2逆向演繹推理2．規則的應用解：解該問題的過程如圖：得到解答語句：（它表示有一只名叫MYRTLE的貓和一只名叫FIDO的狗，這只貓不怕那只狗。）第3章確定性推理方法3.3演繹推理方法3.3.2演繹推理的特點正向演繹推理逆向演繹推理問題求解的描述事實文字與或形事實文字合取式規則L=>W規則W=>L目標文字析取形目標文字與或形初始與或圖相應于事實表達式∨事實表達式的與或樹相應于目標公式∧事實表達式的與或樹演繹推理F規則事實--->目標B規則目標--->事實結束條件包含所有目標節點的一致解圖以事實節點作為所有終節點的一致解圖第3章確定性推理方法3.4歸結推理方法3.4.1子句集及其化簡3.4.2Herbrand（海伯倫）定理3.4.3Robinson（魯賓遜）歸結原理3.4.4利用歸結推理進行定理證明3.4.5應用歸結原理進行問題求解在謂詞演算中，利用前面列出的等價式和永真蘊含式，可以從已知的一些公式推導出新的公式，這個導出的公式叫做定理，在推導過程中使用的推理規則序列就成了該定理的一個證明，而這種推導，就是歸結推理方法。第3章確定性推理方法3.4歸結推理方法3.4.1子句集及其化簡定義3.12任何文字的析取式稱為子句。定義3.13包含任何文字的子句稱為空子句，表示為NIL。定義3.14由子句或空子句所構成的集合稱為子句集。在謂詞邏輯中，任何一個謂詞公式都可以化成一個子句集。將謂詞公式化為子句集的步驟如下：(1)消去連接詞“→”和“?”：(2)減少否定符號的轄域：(3)對變元標準化：在一個量詞的轄域內，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現過的任意變元代替，使不同量詞約束的變元有不同的名字。(4)化為前束范式：把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。第3章確定性推理方法3.4歸結推理方法3.4.1子句集及其化簡在謂詞邏輯中，任何一個謂詞公式都可以化成一個子句集。將謂詞公式化為子句集的步驟如下：（5）消去存在量詞;（6）化為Skolem標準形;（7）消去全稱量詞：由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關緊要，因此可以省掉全稱量詞。（8）消去合取詞：在母式中消去所有合取詞，把母式用子句集的形式表示出來。（9）更換變量名稱：對子句集中的某些變量重新命名，使任意兩個子句中不出現相同的變量名。第3章確定性推理方法3.4歸結推理方法3.4.1子句集及其化簡例：將下列謂詞公式化成子句集。解：轉換過程遵照上述9個步驟。(1)(2)(3)(4)(5)(6)(7)第3章確定性推理方法3.4歸結推理方法3.4.1子句集及其化簡例：將下列謂詞公式化成子句集。解：轉換過程遵照上述9個步驟。(8)子句集為：(9)子句變量標準化后，最終的子句集為：第3章確定性推理方法3.4歸結推理方法3.4.1子句集及其化簡當原謂詞公式為非永假時，它與其標準子句集并不等價。當原謂詞公式為永假（或不可滿足）時，其標準子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。這個結論很重要，是歸結原理的主要依據，可用定理的形式來描述。定理3.1設有謂詞公式F，其標準子句集為S，則F為不可滿足的充要條件是S為不可滿足的。第3章確定性推理方法3.4歸結推理方法3.4.2Herbrand（海伯倫）定理1．H域及其原子集：定義3.15H域：設G是謂詞公式，定義在論域D上，令H0是G中所出現的常量的集合。若G中沒有常量出現，就任取常量a∈D，而規定H0={a}；

其中f(t1,…,tn)是出現于G中的任一函數符號，而t1…tn是Hi-1的元素，i=1,2,…。規定H∞為G的H域。(或說是相應的子句集S的H域)。第3章確定性推理方法3.4歸結推理方法3.4.2Herbrand（海伯倫）定理2．對H域的解釋問題：定義3.16如果子句集S的原子集為A，則對A中各元素的真假值的一個具體設定都是S的一個H解釋。定理3.2設I是S的論域D上的解釋，存在對應于I的H解釋

，使得若有

必有

。定理3.3子句集S是不可滿足的，當且僅當所有的S的H解釋下為假。定理3.4子句集S是不可滿足的，當且僅當對每一個解釋I下，至少有S的某個子句的某個基例為假。

第3章確定性推理方法3.4歸結推理方法3.4.2Herbrand（海伯倫）定理3．Herbrand（海伯倫）定理

定理3.5設有謂詞公式F，其標準形的子句集為S，則F不可滿足的充要條件是S不可滿足。Herbrand（海伯倫）定理如下：定理3.6子句集S不可滿足的充要條件是：該子句集S在H域中的所有解釋都為假。定理3.7子句集S不可滿足的充要條件是存在一個不可滿足的基子句集S′。

對Herbrand（海伯倫）定理一般通俗性解釋是：如果一個一階謂詞公式是永真的，則該公式的機器定理證明求解計算可在有限步內實現證明；如果該公式不是永真的，則無法在有限步內實現證明。第3章確定性推理方法3.4歸結推理方法3.4.2Herbrand（海伯倫）定理3．Herbrand（海伯倫）定理

例：對子句集

畫出相應的語義樹。解：第3章確定性推理方法3.4歸結推理方法3.4.2Herbrand（海伯倫）定理3．Herbrand（海伯倫）定理

Herbrand定理用于語義樹解釋有：定理3.8子句集S是不可滿足的，當且僅當對應于S的完全語義樹都是一棵有限的封閉語義樹。定理3.9子句集S是不可滿足的，當且僅當存在不可滿足的有限基例集（即存在有限個失敗結點）。

Herbrand定理給出了一階邏輯的半可判定算法。其中的“半”字指的是有條件下的判定算法，即僅當被證定理是成立的，使用該算法方可得證。而當被證定理并不成立時，使用該算法得不出任何結果。第3章確定性推理方法3.4歸結推理方法3.4.3Robinson（魯賓遜）歸結原理歸結原理由J.A.Robinson于1965年提出，又稱為消解原理。該原理是Robinson在Herbrand理論基礎上提出的一種基于邏輯的、采用反證法的推理方法。由于其理論上的完備性，歸結原理成為機器定理證明的主要方法。1．命題邏輯中的歸結原理：定義3.17若P是原子謂詞公式或原子命題，則稱P與～P為互補文字。定義3.18設C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，則從C1和C2中可以分別消去L1和L2，并將二子句中余下的部分做析取構成一個新的子句C12，稱這一過程為歸結，所得到的子句C12稱為C1和C2的歸結式，而稱C1和C2為C12的親本子句。第3章確定性推理方法3.4歸結推理方法3.4.3Robinson（魯賓遜）歸結原理1．命題邏輯中的歸結原理：定理3.10歸結式C12是其親本子句C1和C2的邏輯結論。定理3.11推論：設C1和C2是子句集S上的子句，C12是C1和C2的歸結式。如果把C12加入子句集S后得到新子句集S1，則S1和S在不可滿足的意義下是等價的。即：

S是不可滿足的

<=>S1是不可滿足的根據上述定理，有歸結推理過程如下：(1)對子句集S中的各子句間使用歸結推理規則。(2)將歸結所得的歸結式放入子句集S中，得新子句集S′。(3)檢查子句集S′中是否有空子句(NIL),若有則停止推理；(4)置S=S′，轉步驟（1）。第3章確定性推理方法3.4歸結推理方法3.4.3Robinson（魯賓遜）歸結原理2．一階謂詞邏輯中的歸結原理定義3.19設C1和C2是兩個沒有相同變元的子句，

L1和L2分別是C1和C2的文字，如果

L1與

～L2有最一般合一

，則把：

稱作子句

C1和C2的一個二元歸結式，而

L1和L2是被歸結的文字。

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

R1:“任何通過計算機考試并獲獎的人都是快樂的”

R2:“任何肯學習或幸運的人都可以通過所有考試”

R3:“張不肯學習但他是幸運的”

R4:“任何幸運的人都能獲獎”結論“張是快樂的”的否定第3章確定性推理方法3.4歸結推理方法3.4.4利用歸結推理進行定理證明證明：首先將每一個表示邏輯條件的謂詞子句轉換為子句集可以接受的Skolem標準形。由R1可得：(1)由R2可得

(2)

(3)由R3可得

(4)

(5)第3章確定性推理方法3.4歸結推理方法3.4.4利用歸結推理進行定理證明證明：首先將每一個表示邏輯條件的謂詞子句轉換為子句集可以接受的Skolem標準形。由R4可得

(6)由結論可得(7)此為結論的否定第3章確定性推理方法3.4歸結推理方法3.4.4利用歸結推理進行定理證明證明：根據以上7條子句，歸結如下：(8)(1)(6)歸結(9)(8)(7)歸結

(10)(9)(5)歸結(11)(10)(3)歸結(12)NIL(11)(5)歸結原題得證。第3章確定性推理方法3.4歸結推理方法3.4.4利用歸結推理進行定理證明證明：其歸結反演樹如圖：第3章確定性推理方法3.4歸結推理方法3.4.5應用歸結原理進行問題求解應用歸結原理不僅可以進行結論的證明，同時也可以利用歸結原理進行問題的求解。步驟如下：（1）把已知前提條件用謂詞公式表示出來，并化成相應的子句集，設該子句集的名字為S1。（2）把待求解的問題也用謂詞公式表示出來，然后將其否定，并與一謂詞ANSWER構成析取式。謂詞ANSWER是一個專為求解問題而設置的謂詞，其變量必須與問題公式的變量完全一致。（3）把問題公式與謂詞ANSWER構成的析取式化為子句集，并把該子句集與S1合并構成子句集S。（4）對子句集S應用謂詞歸結原理進行歸結，在歸結的過程中，通過合一置換，改變ANSWER中的變元。（5）如果得到歸結式ANSWER，問題的答案即在ANSWER謂詞中。第3章確定性推理方法3.4歸結推理方法3.4.5應用歸結原理進行問題求解例：求解問題,已知:如果x和y是同班同學,則x的老師也是y的老師；

王先生是小李的老師；

小李和小張是同班同學；

問小張的老師是誰?解：定義謂詞

：x是y的老師；

：x與y是同班同學；則已知可表示成如下的謂詞公式：第3章確定性推理方法3.4歸結推理方法3.4.5應用歸結原理進行問題求解例：以上謂詞公式及結論的反化成子句集如下:①～C(x,y)∨～T(z,x)∨T(z,y)②

③

④

⑤

①②歸結⑥

④⑤歸結⑦NIL③⑥歸結說明zhang的老師存在.第3章確定性推理方法3.4歸結推理方法3.4.5應用歸結原理進行問題求解例：為了求解用一個重言式代替④：④

用重言式代替結論的否定,恒為真⑤

①②歸結⑥

④⑤歸結⑦

③⑥歸結可得到問題的結果:張的老師是王先生。也可用輔助謂詞ANS(u)④