人工智能確定性推理82

1、第三章第三章 確定性推理確定性推理1需要掌握的問(wèn)題需要掌握的問(wèn)題l應(yīng)用歸結(jié)原理求解下列問(wèn)題：應(yīng)用歸結(jié)原理求解下列問(wèn)題： 任何兄弟都有同一個(gè)父親，任何兄弟都有同一個(gè)父親，John和和Peter是兄弟，且是兄弟，且John的父親是的父親是David，問(wèn)，問(wèn)Peter的父親是誰(shuí)？的父親是誰(shuí)？2 按照推理過(guò)程所用知識(shí)的確定性，推理可分為確定性推理和不確定性推理。 自然演繹推理和歸結(jié)推理是經(jīng)典的確定性推理，它們以數(shù)理邏輯的有關(guān)理論、方法和技術(shù)為理論基礎(chǔ)，是機(jī)械化的、可在計(jì)算機(jī)上加以實(shí)現(xiàn)的推理方法。 本章在討論有關(guān)推理的一般概念以及命題和謂詞邏輯的基礎(chǔ)上，介紹自然演繹推理方法和基于一階謂詞邏輯的歸結(jié)推理方

2、法。33.1 推理概述 3.1.1 推理的基本概念推理的基本概念 推理是指從已知事實(shí)出發(fā)，運(yùn)用已掌握的知識(shí)，推導(dǎo)出其中蘊(yùn)含的事實(shí)性結(jié)論或歸納出某些新的結(jié)論的過(guò)程。其中，推理所用的事實(shí)可分為兩種情況，一種是與求解問(wèn)題有關(guān)的初始證據(jù)；另一種是推理過(guò)程中所得到的中間結(jié)論，這些中間結(jié)論可以作為進(jìn)一步推理的已知事實(shí)或證據(jù)。 人工智能系統(tǒng)的構(gòu)成：推理機(jī)一些程序來(lái)完成的；綜合數(shù)據(jù)庫(kù)存放有用于推理的事實(shí)或證據(jù)；知識(shí)庫(kù)存放有用于推理所必須的知識(shí)。 43.1 推理概述 3.1.2 推理的方法及其分類(lèi) 1. 按照推理的邏輯基礎(chǔ)分類(lèi) 可分為演繹推理、歸納推理和默認(rèn)推理。 （1）演繹推理 演繹推理是從已知的一般性知識(shí)出

3、發(fā)，推理出適合于某種個(gè)別情況的結(jié)論的過(guò)程。它是一種由一般到個(gè)別的推理方法。53.1 推理概述 （2）歸納推理 歸納推理是從大量特殊事例出發(fā)，歸納出一般性結(jié)論的推理過(guò)程，是一種由個(gè)別到一般的推理方法。其基本思想是：首先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。 歸納推理又可分為： 從特殊事例考察范圍看：完全歸納推理、不完全歸納推理； 從使用的方法看：枚舉歸納推理、類(lèi)比歸納推理。63.1 推理概述 （3）默認(rèn)推理 默認(rèn)推理又稱(chēng)缺省推理，是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。也就是說(shuō)，在進(jìn)行推理時(shí)，如果對(duì)某些證據(jù)不能證明其

4、不成立的情況下，先假設(shè)它是成立的，并將它作為推理的依據(jù)進(jìn)行推理，但在推理過(guò)程中，當(dāng)由于新知識(shí)的加入或由于所推出的中間結(jié)論與已有知識(shí)發(fā)生矛盾時(shí)，就說(shuō)明前面的有關(guān)證據(jù)的假設(shè)是不正確，這時(shí)就要撤消原來(lái)的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新按新情況進(jìn)行推理73.1 推理概述 2. 按所用知識(shí)的確定性分類(lèi) 按推理時(shí)所用知識(shí)的確定性來(lái)劃分，推理可分為確定性推理、不確定性推理。3. 按推理過(guò)程的單調(diào)性 按照推理過(guò)程中所推出的結(jié)論是否單調(diào)地增加，或者說(shuō)按照推理過(guò)程所得到的結(jié)論是否越來(lái)越接近最終目標(biāo)來(lái)分類(lèi)，推理可分為單調(diào)推理與非單調(diào)推理。 83.1 推理概述 3.1.3 推理的控制策略 推理過(guò)程不僅依賴(lài)于所用

5、的推理方法，同時(shí)也依賴(lài)于推理的控制策略。控制策略包括推理方向、搜索策略、沖突消解策略等；而推理方法則是指在推理控制策略確定之后，在進(jìn)行具體推理時(shí)所要采取的匹配方法或不確定性傳遞算法等方法。 推理方向用來(lái)確定推理的驅(qū)動(dòng)方式，即是數(shù)據(jù)（證據(jù)）驅(qū)動(dòng)或是目標(biāo)驅(qū)動(dòng)。所謂數(shù)據(jù)驅(qū)動(dòng)即指推理過(guò)程從初始證據(jù)開(kāi)始直到目標(biāo)結(jié)束，而目標(biāo)驅(qū)動(dòng)則是指推理過(guò)程從目標(biāo)開(kāi)始進(jìn)行反向推理，直到出現(xiàn)與初始證據(jù)相吻合的結(jié)果。 按照對(duì)推理方向的控制，推理可分為正向推理、反向推理、混合推理及雙向推理四種情況。93.1 推理概述 l 正向推理是一種從已知事實(shí)出發(fā)、正向使用推理規(guī)則的推理方式，它是一種數(shù)據(jù)（或證據(jù)）驅(qū)動(dòng)的推理方式，又稱(chēng)前項(xiàng)鏈

6、推理或自底向上推理。l反向推理是一種以某個(gè)假設(shè)目標(biāo)為出發(fā)點(diǎn)，反向運(yùn)用推理規(guī)則的推理方式，它是一種目標(biāo)驅(qū)動(dòng)的推理方式，又稱(chēng)反向鏈推理或自頂向下推理。l混合推理是把正向推理和反向推理結(jié)合起來(lái)所進(jìn)行的推理。l所謂雙向混合推理是指正向推理和反向推理同時(shí)進(jìn)行，使推理過(guò)程在中間的某一步驟相匯合而結(jié)束的一種推理方法。 103.1 推理概述 3.1.4 推理的沖突消解策略 推理過(guò)程中的沖突消解策略，就是確定如何從多條匹配規(guī)則中選出一條規(guī)則作為啟用規(guī)則，將它用于當(dāng)前的推理。 目前已有的多種沖突消解策略的基本思想都是對(duì)匹配的知識(shí)或規(guī)則進(jìn)行排序，以決定匹配規(guī)則的優(yōu)先級(jí)別，優(yōu)先級(jí)高的規(guī)則將作為啟用規(guī)則。常用排序方法有

7、如下幾種:113.1 推理概述 (1)按就近原則排序 (2)按知識(shí)特殊性排序 (3)按上下文限制排序 (4)按知識(shí)的新鮮性排序 (5)按知識(shí)的差異性排序 (6)按領(lǐng)域問(wèn)題的特點(diǎn)排序 (7)按規(guī)則的次序排序(8)按前提條件的規(guī)模排序 123.2 3.2 命題邏輯命題邏輯 3.2.1 命題 定義 3.1 能夠分辨真假的語(yǔ)句稱(chēng)作命題。定義3.2 一個(gè)語(yǔ)句如果不能再進(jìn)一步分解成更簡(jiǎn)單的語(yǔ)句，并且又是一個(gè)命題，則稱(chēng)此命題為原子命題。 原子命題是命題中最基本的單位。我們一般用P、Q、R、大寫(xiě)拉丁字母表示命題，而命題的真與假分別用“T”與“F”表示。 用大寫(xiě)英文字母表示的命題既可以是一個(gè)特定的命題，也可以是

8、一個(gè)抽象的命題。前者稱(chēng)為命題常量，后者稱(chēng)為命題變量。對(duì)于命題變量而言，只有把確定的命題代入后，它才可能有明確的邏輯值（T或F）。 133.2 3.2 命題邏輯命題邏輯3.2.2 命題公式 1. 連接詞：稱(chēng)為“非”或“否定”。：稱(chēng)為“析取”。：稱(chēng)為“合取”。：稱(chēng)為“條件”或者“蘊(yùn)含”。：稱(chēng)為“雙條件”。P Q表示“P當(dāng)且僅當(dāng)Q”。表3.1 命題邏輯真值表P QPQPQPQP QPT TTTTTFT FTFFFFF TTFTFTF FFFTTT143.2 3.2 命題邏輯命題邏輯2.命題公式定義3.3 以下面的遞歸形式給出命題公式的定義： l （1）原子命題是命題公式。l （2）A是命題公式，則A

9、也是命題公式。l （3）若A和B都是命題公式，則AB、AB、 AB、ABl（4）只有按（1）（3）所得的公式才是命題公式。 153.2 3.2 命題邏輯命題邏輯命題公式的缺點(diǎn)： l 無(wú)法把所描述的客觀事物的結(jié)構(gòu)和邏輯特征反映出來(lái)l 不能把不同事物的共同特征反映出來(lái)P:“張三是李四的老師”；僅用字母P看不出張三和李四之間的師生關(guān)系。 為了克服命題邏輯的局限性，引入了下面的謂詞邏輯163.3 3.3 謂詞邏輯謂詞邏輯3.3.1 謂詞與個(gè)體 在謂詞邏輯中，將原子命題分解為謂詞與個(gè)體兩部分。個(gè)體是指可以獨(dú)立存在的物體，可以是抽象的或具體的。謂詞則是用于刻畫(huà)個(gè)體的性質(zhì)、狀態(tài)或個(gè)體間的關(guān)系的。 例如：“李

10、白是詩(shī)人” 可表示為：poet(LiBai) poet稱(chēng)為謂詞，用以刻畫(huà)“是詩(shī)人”；LiBai稱(chēng)為個(gè)體 173.3 3.3 謂詞邏輯謂詞邏輯 一個(gè)謂詞可以與一個(gè)個(gè)體相關(guān)聯(lián)，此種謂詞稱(chēng)作一元謂詞，它刻畫(huà)了個(gè)體的性質(zhì)。一個(gè)謂詞也可以與多個(gè)個(gè)體相關(guān)聯(lián)，此種謂詞稱(chēng)為多元謂詞，它刻畫(huà)了個(gè)體間的“關(guān)系”。 183.3 3.3 謂詞邏輯謂詞邏輯謂詞的一般形式：P(x1,x2,xn )其中P是謂詞，而x1,x2,xn是個(gè)體。謂詞通常用大寫(xiě)字母表示，個(gè)體通常用小寫(xiě)字母表示。 項(xiàng)：在謂詞中，個(gè)體可以是常量，也可以是變量，還可以是一個(gè)函數(shù)。例如，“小劉的哥哥是個(gè)工人”，可以表示為worker(brother(Liu

11、)，其中brother(Liu)是一個(gè)函數(shù)。個(gè)體常數(shù)、變量和函數(shù)統(tǒng)稱(chēng)為項(xiàng)。 謂詞的語(yǔ)義：由使用者根據(jù)需要人為地定義. 193.3 3.3 謂詞邏輯謂詞邏輯謂詞的元數(shù)：謂詞中包含的個(gè)體數(shù)目稱(chēng)為謂詞的元數(shù)，例如P(x)是一元謂詞，P(x,y)是二元謂詞，而P(x1,x2,xn )則是n元謂詞。謂詞的階數(shù)：在謂詞P(x1,x2,xn )中，若xi(i=1,2,n)都是個(gè)體常量、變?cè)蚝瘮?shù)，則稱(chēng)它為一階謂詞。如果某個(gè)xi本身又是一個(gè)一階謂詞，則稱(chēng)它為二階謂詞，依次類(lèi)推。謂詞和函數(shù)的區(qū)別：謂詞具有邏輯值“真”或“假”，而函數(shù)則是某個(gè)個(gè)體到另一個(gè)個(gè)體（按數(shù)學(xué)上的概念是自變量到因變量）之間的映射。 203.

12、3 3.3 謂詞邏輯謂詞邏輯3.3.2 謂詞公式 1. 連接詞 ， 2. 量詞 為刻畫(huà)謂詞與個(gè)體間的關(guān)系，引入了兩個(gè)量詞：全稱(chēng)量詞（x）,和存在量詞（x）。 3. 謂詞演算公式定義3.4 謂詞演算中，由單個(gè)謂詞構(gòu)成的不含任何連接詞的公式，叫做原子謂詞公式。 213.3 3.3 謂詞邏輯謂詞邏輯由原子公式的定義出發(fā)，可定義謂詞演算的合式公式如下。定義3.5 可按下述規(guī)則得到謂詞演算的合式公式： （1） 原子謂詞公式是合式公式。 （2） 若A是合式公式，則A也是合式公式。 （3）若A和B都是合式公式，則AB、AB、AB、AB也都是合式公式。 （4）若A是合式公式，x是任一個(gè)體變?cè)?，則(x)A和(x

13、)A也都是合式公式。 （5）只有按（1）（4）所得的公式才是合式公式。 223.3 3.3 謂詞邏輯謂詞邏輯4. 量詞轄域與約束變?cè)?在一個(gè)公式中，如果有量詞出現(xiàn)，位于量詞后面的單個(gè)謂詞或者用括弧括起來(lái)的合式公式稱(chēng)為量詞的轄域。在轄域內(nèi)與量詞中同名的變?cè)Q(chēng)為約束變?cè)?233.3 3.3 謂詞邏輯謂詞邏輯3.3.3 謂詞公式的永真性和可滿(mǎn)足性謂詞公式的永真性和可滿(mǎn)足性1謂詞公式的解釋定義3.6 設(shè)D為謂詞公式P的個(gè)體域，若對(duì)P中的個(gè)體常量、函數(shù)和謂詞按照如下規(guī)定賦值：（1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；（2）為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的映射，其中 Dn=(x1,x2,xn)|x1,x

14、2,xn D（3）為每個(gè)n元謂詞指派一個(gè)從Dn到F,T的映射；則稱(chēng)這些指派為公式P在D上的一個(gè)解釋。243.3 3.3 謂詞邏輯謂詞邏輯例3.1 設(shè)個(gè)體域D=1,2，求公式A=(x)(P(x)Q(f(x),b)在D上的某一個(gè)解釋?zhuān)⒅赋鲈诖私忉屜鹿紸的真值。 詳細(xì)的求解過(guò)程參見(jiàn)教材253.3 3.3 謂詞邏輯謂詞邏輯2謂詞公式的永真性定義3.7 如果謂詞公式P，對(duì)個(gè)體域D上的任何一個(gè)解釋都取得真值T，則稱(chēng)P在D上是永真的；如果P在每個(gè)非空個(gè)體域上均永真，則稱(chēng)P永真。定義3.8 如果謂詞公式P對(duì)于個(gè)體域D上的所有解釋都取得假值F，則稱(chēng)P在D上是永假的；如果P在每個(gè)非空個(gè)體域上均永假，則稱(chēng)P永假

15、。謂詞公式的永假性又稱(chēng)為不可滿(mǎn)足性或不相容性。263.3 3.3 謂詞邏輯謂詞邏輯3謂詞公式的可滿(mǎn)足性 定義3.9 對(duì)于謂詞公式P，如果至少存在一個(gè)解釋使得公式P在此解釋下的真值為T(mén)，則稱(chēng)公式P是可滿(mǎn)足的。按照定義3.9，對(duì)謂詞公式P，如果不存在任何解釋?zhuān)沟肞的取值為T(mén)，則稱(chēng)公式P是不可滿(mǎn)足的。所以，謂詞公式P永假與不可滿(mǎn)足是等價(jià)的。若P永假，則也可稱(chēng)P是不可滿(mǎn)足的。 273.3 3.3 謂詞邏輯謂詞邏輯3.3.4 謂詞公式的等價(jià)性與永真蘊(yùn)含 定義3.10 設(shè)P與Q是兩個(gè)謂詞公式，D是它們共同的個(gè)體域。若對(duì)D上的任何一個(gè)解釋?zhuān)琍與Q的取值都相同，則公式P和Q在域D上是等價(jià)的。如果D是任意個(gè)體

16、域，則稱(chēng)P和Q是等價(jià)的，記作P Q。常用的一些等價(jià)式參見(jiàn)教材 定義3.11 對(duì)于謂詞公式P和Q，如果PQ永真，則稱(chēng)P永真蘊(yùn)含Q，且稱(chēng)Q為P的邏輯結(jié)論，稱(chēng)P為Q的前提，記作P=Q。 以后要用到的一些永真蘊(yùn)含式參見(jiàn)教材283.3 3.3 謂詞邏輯謂詞邏輯謂詞邏輯中還有如下一些推理規(guī)則：（1）P規(guī)則：在推理的任何步驟上都可引入前提。（2）T規(guī)則：推理時(shí)，如果前面步驟中有一個(gè)或多個(gè)永真蘊(yùn)含公式S，則可把S引入推理過(guò)程中。（3）CP規(guī)則：如果能從R和前提集合中推出S來(lái)，則可從前提集合推出RS來(lái)。（4）反證法：P=Q，當(dāng)且僅當(dāng)PQF，即Q為P的邏輯結(jié)論，當(dāng)且僅當(dāng)PQ 是不可滿(mǎn)足的。推廣之，可得如下定理。

17、定理3.1 Q為P1，P2，Pn的邏輯結(jié)論，當(dāng)且僅當(dāng) (P1P2Pn)Q是不可滿(mǎn)足的。293.3 3.3 謂詞邏輯謂詞邏輯3.3.5 置換與合一 1. 置換 置換的定義定義3.12 置換是形如t1/x1,t2/x2,tn/xn的一個(gè)有限集。其中xi是變量，ti是不同于xi的項(xiàng)（常量，變量，函數(shù)），且xi xj（Ij），i，j=1,2,n 。 303.3 3.3 謂詞邏輯謂詞邏輯例如，a/x,b/y,f(x)/z，f(z)/x,y/z都是置換。不含任何元素的置換稱(chēng)為空置換，以 表示。 置換乘法 置換乘法作用是將兩個(gè)置換合成為一個(gè)置換。定義3.13假設(shè) =t1/x1,t2/x2,tn/xn =u1

18、/y1,u2/y2,um/ym是兩個(gè)置換，則它們的乘積是一個(gè)新置換，其作用于公式E時(shí)，相當(dāng)于先后對(duì)E的作用。它的定義如下：313.3 3.3 謂詞邏輯謂詞邏輯先作置換t1 /x1,t2 /x2,tn /xn,u1/y1,u2/y2,um/ym。若yi x1,xn時(shí)，先從上述集合中刪除ui/yi 。若 ti =xi時(shí)，再?gòu)纳鲜黾现袆h除ti /xi 。刪除以后剩下元素所構(gòu)成的集合稱(chēng)作與的乘積，記作 。 置換結(jié)合率一般地說(shuō)，下列的置換結(jié)合律成立 ( ) = = ( ) ) 但除了空置換外，置換的交換律不成立。即只有= = 。 323.3 3.3 謂詞邏輯謂詞邏輯2. 合一 合一的概念定義3.14

19、設(shè)有公式集E1,E2,En和置換 ，使 E1 = E2 =En 便稱(chēng)E1，E2，En是可合一的 ，且稱(chēng)為合一置換。定義3.15 若E1，E2，En 有合一置換，且對(duì)E1，E2，En 的任一置換都存在一個(gè)置換，使得= ，則稱(chēng)是E1，E2，En 的最一般合一置換，記為mgu。333.3 3.3 謂詞邏輯謂詞邏輯 最一般合一置換的求取算法設(shè)有兩個(gè)謂詞公式： E1：P(x,y,z); E2：P(x,f(a),g(b)分別從E1與E2的第一個(gè)符號(hào)開(kāi)始逐個(gè)向右比較，此時(shí)發(fā)現(xiàn)E1中的y與E2中的f(a)不同，則它們構(gòu)成了一個(gè)不一致集： D1=y,f(a)當(dāng)繼續(xù)向右比較時(shí)，又發(fā)現(xiàn)中E1中的z與E2中g(shù)(b)不

20、同，則又得到一個(gè)不一致集： D2=z,g(b) 下面給出求公式E1,E2的最一般合一置換的算法：343.3 3.3 謂詞邏輯謂詞邏輯（1） 令W= E1,E2 。（2） 令 k=0，Wk=W，k= ；是空置換，它表示不作置換。（3） 如果Wk只有一個(gè)表達(dá)式，則算法停止，k就是所要求的mgu。（4） 找出Wk的不一致集Dk 。 （5） 若Dk中存在元素xk和tk ，其中xk是變?cè)?，tk是項(xiàng)，且xk不在tk中 出現(xiàn)，則置： k+1=k tk/xk Wk+1=wktk/xk k=k+1 然后轉(zhuǎn)（3）。（6） 算法終止，W的mgu不存在?？梢宰C明，如果E1和E2可合一，則算法必停止于第（3）步。 35

21、3.3 3.3 謂詞邏輯謂詞邏輯例3.5 設(shè)E1=P(a,v,f(g(y)，E2=P(z,f(a),f(u)，求E1 和E2的mgu。解題請(qǐng)參見(jiàn)教材 答案為：3= a/z ,f(a)/v,g(y)/u 3就是E1 和E2的mgu。 363.4 3.4 自然演繹推理方法自然演繹推理方法 3.4.1 自然演繹推理的概念自然演繹推理的概念 自然演繹推理是指從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用命題邏輯或謂詞邏輯中的推理規(guī)則推出結(jié)論的過(guò)程。 假言三段論的基本形式為 PQ，QRPR 它表示如果謂詞公式PQ和QR均為真，則謂詞公式PR也為真。 假言推理可用下列形式表示 P，PQ Q它表示如果謂詞公式P和PQ都

22、為真，則可推得Q為真結(jié)論。 373.4 3.4 自然演繹推理方法自然演繹推理方法 拒取式的一般形式為 PQ，Q P它表示如果謂詞公式PQ為真且Q為假，則可推得P為假的結(jié)論。2.4.2 2.4.2 利用演繹推理解決問(wèn)題利用演繹推理解決問(wèn)題 在利用自然演繹推理方法求解問(wèn)題時(shí)，一定要注意避免兩種類(lèi)型的錯(cuò)誤：肯定后件的錯(cuò)誤和否定前件的錯(cuò)誤。 383.4 3.4 自然演繹推理方法自然演繹推理方法 肯定后件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過(guò)肯定后件Q為真來(lái)推出前件P為真。這顯然是錯(cuò)誤的推理邏輯，因?yàn)楫?dāng) PQ及 Q為真時(shí)，前件 P既可能為真，也可能為假。 否定前件的錯(cuò)誤是指當(dāng)PQ為真時(shí)，希望通過(guò)否定前件P來(lái)推

23、出后件Q為假。這也是不允許的，因?yàn)楫?dāng)PQ及P為假時(shí)，后件Q既可能為真，也可能為假。 相關(guān)的例題請(qǐng)參見(jiàn)教材393.4 3.4 自然演繹推理方法自然演繹推理方法 3.4.3 演繹推理的特點(diǎn)演繹推理的特點(diǎn) 參見(jiàn)教材403.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 研究用計(jì)算機(jī)實(shí)現(xiàn)定理證明的機(jī)械化，已是人工智能研究的一個(gè)重要領(lǐng)域。對(duì)于定理證明問(wèn)題，如果用一階謂詞邏輯表示的話(huà)，就是要求對(duì)前提P和結(jié)論Q證明PQ是永真的。然而，要證明這個(gè)謂詞公式的永真性，必須對(duì)所有個(gè)體域上的每一個(gè)解釋進(jìn)行驗(yàn)證，這是極其困難的。為了化簡(jiǎn)問(wèn)題，和數(shù)學(xué)上常采用的方法一樣，我們考慮反證法。即，我們先否定邏輯結(jié)論Q，再由否定后的邏輯結(jié)論

24、Q及前提條件P出發(fā)推出矛盾，即可證明原問(wèn)題。413.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.1謂詞公式與子句集謂詞公式與子句集 1范式 前束形范式 一個(gè)謂詞公式，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且它的轄域一直延伸到公式之末，同時(shí)公式中不出現(xiàn)連接詞及 ，這種形式的公式稱(chēng)作前束形范式。例如，公式( x)(y)( z)(P(x)F(y,z)Q(y,z)即是一個(gè)前束形的公式。423.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 斯克林范式 從前束形范式中消去全部存在量詞所得到的公式即為Skolem范式，或稱(chēng)Skolem標(biāo)準(zhǔn)型。例如，如果用f(x)代替上面前束形范式中的y即得到Skolem范

25、式：( x) ( z)(P(x)F(f(x), z)Q(f(x), z)Skolem標(biāo)準(zhǔn)型的一般形式是( x1)( x2)( xn)M(x1,x2,xn)其中，M(x1,x2,xn)是一個(gè)合取范式，稱(chēng)為Skolem標(biāo)準(zhǔn)型的母式。433.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 將謂詞公式G化為Skolem標(biāo)準(zhǔn)型的步驟如下：（1） 消去謂詞公式G中的蘊(yùn)涵（）和雙條件符號(hào)（ ），以AB代替AB，以(AB)(AB)替換AB。（2） 減少否定符號(hào)（）的轄域，使否定符號(hào)“”最多只作用到一個(gè)謂詞上。（3） 重新命名變?cè)顾械淖冊(cè)拿志煌?，并且自由變?cè)凹s束變?cè)嗖煌?43.5 3.5 歸結(jié)推理方法

26、歸結(jié)推理方法 （4） 消去存在量詞。這里分兩種情況，一種情況是存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi)，此時(shí)，只要用一個(gè)新的個(gè)體常量替換該存在量詞約束的變?cè)?，就可以消去存在量詞；另一種情況是，存在量詞位于一個(gè)或多個(gè)全稱(chēng)量詞的轄域內(nèi)，這時(shí)需要用一個(gè)Skolem函數(shù)替換存在量詞而將其消去。（5）把全稱(chēng)量詞全部移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。（6）母式化為合取范式：任何母式都可以寫(xiě)成由一些謂詞公式和謂詞公式否定的析取的有限集組成的合取。 需要指出的是，由于在化解過(guò)程中，消去存在量詞時(shí)作了一些替換，一般情況下，G的Skolem標(biāo)準(zhǔn)型與G并不等值。453.5 3.5 歸結(jié)推理方

27、法歸結(jié)推理方法 2子句與子句集定義3.16 不含有任何連接詞的謂詞公式叫原子公式，簡(jiǎn)稱(chēng)原子，而原子或原子的否定統(tǒng)稱(chēng)文字。定義3.17 子句就是由一些文字組成的析取式。定義3.18 不包含任何文字的子句稱(chēng)為空子句，記為NIL。定義3.199 由子句構(gòu)成的集合稱(chēng)為子句集。463.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3不可滿(mǎn)足意義下的一致性定理3.2 設(shè)有謂詞公式G，而其相應(yīng)的子句集為S，則G是不可滿(mǎn)足的充分必要條件是S是不可滿(mǎn)足的。 要再次強(qiáng)調(diào)：公式G與其子句集S并不等值，只是在不可滿(mǎn)足意義下等價(jià)。 相關(guān)的例子參見(jiàn)教材中的例3.9473.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 4PP1P2Pn的子

28、句集 當(dāng)PP1P2Pn時(shí)，若設(shè)P的子句集為SP，Pi的子句集為Si，則一般情況下，SP并不等于S1S2S3Sn，而是要比S1S2S3Sn復(fù)雜得多。但是，在不可滿(mǎn)足的意義下，子句集SP與S1S2S3Sn是一致的，即 SP不可滿(mǎn)足S1S2S3Sn不可滿(mǎn)足483.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.2 3.5.2 HerbrandHerbrand理論理論 1H域 定義3.20 設(shè)謂詞公式G的子句集為S，則按下述方法構(gòu)造的個(gè)體變?cè)騂。稱(chēng)為公式G或子句集S的Herbrand域，簡(jiǎn)稱(chēng)H域。（1） 令H0是S中所出現(xiàn)的常量的集合。若S中沒(méi)有常量出現(xiàn)，就任取一個(gè)常量aD，規(guī)定H0=a。（2） 令H

29、i+1=HiS中所有的形如f(t1,tn)的元素其中f(t1,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而t1，tn是Hi中的元素。i=0，1，2，。 493.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例3.10 求子句集ST(x)Q(z),R(f(y)的H域。解 此例中沒(méi)有個(gè)體常量，任意指定一個(gè)常量a作為個(gè)體常量；只有一個(gè)函數(shù)f(y)，有：H0=aH1=a,f(a)H2=a,f(a),f(f(a)H=a,f(a),f(f(a),f(f(f(a),503.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 2原子集定義3.21 下列集合稱(chēng)為子句集S的原子集： A所有形如P(t1, t2,tn)的元素其中，P(t1, t

30、2,tn)是出現(xiàn)在S中的任一謂詞符號(hào)，而t1，t2，tn則是S的H域上的任意元素。513.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定義3.22 將沒(méi)有變?cè)霈F(xiàn)的原子、文字、子句和子句集分別稱(chēng)作基原子、基文字、基子句和基子句集。定義3.23 當(dāng)子句集S中的某個(gè)子句C中的所有變?cè)?hào)均以其H域中的元素替換時(shí)，所得到的基子句稱(chēng)作C的一個(gè)基例。 例如，對(duì)于子句集 SP(a),P(x)P(f(x) 它的H域?yàn)閍,f(a),f(f(a),。 對(duì)于子句P(a)，因?yàn)槠渲胁缓凶冊(cè)运咽腔泳?，而且aH，所以它也是基例。 523.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3H域上的解釋定義3.24 如果子句集

31、S的原子集為A，則對(duì)A中各元素的真假值的一個(gè)具體設(shè)定都是S的一個(gè)H解釋?？梢宰C明，在給定域D上的任一個(gè)解釋I，總能在H域上構(gòu)造一個(gè)解釋I*與之對(duì)應(yīng)，使得如果D域上的解釋能滿(mǎn)足子句集S，則在H域的解釋I*也能滿(mǎn)足S（即若S|I=T，就有S|I*=T）。相關(guān)舉例參見(jiàn)教材533.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定理3.3 設(shè)I是子句集S在域D上的一個(gè)解釋?zhuān)瑒t存在對(duì)應(yīng)于I的H域解釋I*，使得若有 S|I=T，就必有S|I*=T。定理3.4 子句集S不可滿(mǎn)足的充要條件是S對(duì)H域上的一切解釋都為假。 證明 充分性：若S在一般域D上是不可滿(mǎn)足的，必然在H域上是不可滿(mǎn)足的，從而對(duì)H域上的一切解釋都為假。

32、必要性：若S在任一H解釋I*下均為假，必然會(huì)使S在D域上的每一個(gè)解釋為假。否則，如果存在一個(gè)解釋I0使S為真，那么依據(jù)定理3.3可知，一定可以在H域找到相對(duì)應(yīng)的一個(gè)解釋I*0使S為真。這與S在所有H解釋下均為假矛盾。543.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定理3.5 子句集S不可滿(mǎn)足的充分必要條件是存在一個(gè)有限的不可滿(mǎn)足的基例集S。 該定理稱(chēng)為Herbrand定理，下面給出它的簡(jiǎn)要證明。證明 充分性：設(shè)子句集S有一個(gè)不可滿(mǎn)足的基例集S，因?yàn)樗豢蓾M(mǎn)足，所以一定存在一個(gè)解釋I使S為假。根據(jù)H域上的解釋與D域上的解釋的對(duì)應(yīng)關(guān)系，可知在D域上一定存在一個(gè)解釋使S不可滿(mǎn)足，從而證明了子句集S是不

33、可滿(mǎn)足的。553.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 必要性：設(shè)子句集S不可滿(mǎn)足，由定理3.4可知，S對(duì)H域上的所有解釋均為假。這樣，就至少會(huì)存在一個(gè)S中的某子句Ci的基例Ci為假。既然至少有一個(gè)基例Ci為假，因而S的基例集S是不可滿(mǎn)足的。另外，由于S中的子句是有限的，而每個(gè)子句又由有限的文字組成，因而S的不可滿(mǎn)足的基例集也是有限的。563.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.3 歸結(jié)原理歸結(jié)原理定義3.25 若P是原子謂詞公式或原子命題，則稱(chēng)P與P為互補(bǔ)文字。1命題邏輯中的歸結(jié)原理歸結(jié)與歸結(jié)式 定義3.26 設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字

34、L2互補(bǔ)，則從C1和C2中可以分別消去L1和L2，并將二子句中余下的部分做析取構(gòu)成一個(gè)新的子句C12，稱(chēng)這一過(guò)程為歸結(jié)，所得到的子句C12稱(chēng)為C1和C2的歸結(jié)式，而稱(chēng)C1和C2為C12的親本子句。573.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 定理3.6 歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。推論 設(shè)C1和C2是子句集S上的子句，C12是C1和C2的歸結(jié)式。如果把C12加入子句集S后得到新子句集S1，則S1和S在不可滿(mǎn)足的意義下是等價(jià)的。即： S是不可滿(mǎn)足的 S1是不可滿(mǎn)足的 歸結(jié)推理過(guò)程歸結(jié)推理過(guò)程 子句集S不可滿(mǎn)足性的推理過(guò)程如下： (1) 對(duì)子句集S中的各子句間使用歸結(jié)推理規(guī)則。

35、(2) 將歸結(jié)所得的歸結(jié)式放入子句集S中，得新子句集S。 (3) 檢查子句集S中是否有空子句(NIL),若有則停止推理;否則轉(zhuǎn)（4）。 (4) 置S=S，轉(zhuǎn)步驟（1）。583.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 2一階謂詞邏輯中的歸結(jié)原理 下面是謂詞邏輯關(guān)于歸結(jié)的定義。定義定義3.27 設(shè)C1和C2是兩個(gè)沒(méi)有相同變?cè)淖泳?，L1 和L2分別是C1 和C2的文字，如果L1與 L2有mgu ，則把 C12 =( C1L1)(C2 L2)稱(chēng)作子句C1 和C2的一個(gè)二元?dú)w結(jié)式，而L1 和L2是被歸結(jié)的文字。 為了說(shuō)明的方便。將Ci和Li寫(xiě)成集合形式， 如P(x)Q(y)P(x),Q(y)。在集合的表

36、示下做減法或做并運(yùn)算，然后再寫(xiě)成子句形，如集合運(yùn)算結(jié)果為P(x),Q(y)，可改寫(xiě)為P(x)Q(y)。 593.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 在謂詞邏輯中，對(duì)子句進(jìn)行歸結(jié)推理時(shí)，要注意以下幾個(gè)問(wèn)題：（1）若被歸結(jié)的子句C1 和C2中具有相同的變?cè)獣r(shí)，需要將其中一個(gè)子句的變?cè)?，否則可能無(wú)法做合一置換。從而沒(méi)有辦法進(jìn)行歸結(jié)。 （2）在求歸結(jié)式時(shí)，不能同時(shí)消去兩個(gè)互補(bǔ)文字對(duì)，消去兩個(gè)互補(bǔ)文字對(duì)所得的結(jié)果不是兩個(gè)親本子句的邏輯推論。（3）如果在參加歸結(jié)的子句內(nèi)含有可合一的文字，則在進(jìn)行歸結(jié)之前，應(yīng)對(duì)這些文字進(jìn)行合一，以實(shí)現(xiàn)這些子句內(nèi)部的化簡(jiǎn)。 603.5 3.5 歸結(jié)推理方法歸結(jié)推理方法

37、應(yīng)用因子的概念，可對(duì)謂詞邏輯中的歸結(jié)原理定義如下。 定義3.28 設(shè)C1和 C2是沒(méi)有相同變?cè)淖泳?，則下列四種二元?dú)w結(jié)式都叫做C1和C2的歸結(jié)式，仍記作C12。（1） C1與C2的二元?dú)w結(jié)式。（2） C1的因子C11與C2的二元?dú)w結(jié)式。（3） C1與C2的因子C22的二元?dú)w結(jié)式。（4） C1的因子C11與C2的因子C22的二元?dú)w結(jié)式。613.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例例 設(shè)C1=P(a)Q(x)R(x)，C2 =P(y)Q(b)， 求其二元?dú)w結(jié)式。解解 若選L1=P(a)，L2=P(y)，則L1和L2的mgu是=a/y，于是由定義3.27得C1和C2 的二元?dú)w結(jié)式為C12 =(

38、 C1-L1)(C2 -L2)=(P(a),Q(x),R(x)-P(a)(P(a),Q(b)-P(a)=(Q(x),R(x)(Q(b)=Q(x)R(x)Q(b) 若選L1=Q(x)，L2=Q(b)，則二者的mgu=b/x， C12 =P(a)R(b)P(y)623.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3歸結(jié)原理的完備性歸結(jié)原理的完備性 對(duì)于一階謂詞邏輯，從不可滿(mǎn)足的意義上說(shuō)，歸結(jié)原理是完備的。即若子句集是不可滿(mǎn)足的，則必存在一個(gè)從該子句集到空子句的歸結(jié)推理過(guò)程；反之，若從子句集到空子句存在一個(gè)歸結(jié)推理過(guò)程，則該子句集必是不可滿(mǎn)足的。 633.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.4

39、利用歸結(jié)原理進(jìn)行定理證明利用歸結(jié)原理進(jìn)行定理證明 應(yīng)用歸結(jié)原理進(jìn)行定理證明的步驟如下：應(yīng)用歸結(jié)原理進(jìn)行定理證明的步驟如下： 設(shè)要被證明的定理可用謂詞公式表示為如下的形式： A1A2AnB(1) 首先否定結(jié)論B，并將否定后的公式B與前提公式集組成如下形式的謂詞公式： G= A1A2AnB(2) 求謂詞公式G的子句集S。(3) 應(yīng)用歸結(jié)原理，證明子句集S的不可滿(mǎn)足性，從而證明謂詞公式G的不可滿(mǎn)足性。這就說(shuō)明對(duì)結(jié)論B的否定是錯(cuò)誤的，推斷出定理的成立。643.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例例 已知：A: (x)( y)(P(x,y)Q(y)( y)(R(y)T(x,y)B: ( x)R(x)

40、( x)( y)(P(x,y)Q(y)求證：B是A的邏輯結(jié)論。證明證明 首先將A和B化為子句集(1)P(x,y)Q(y) R(f(x)(2)P(x,y)Q(y) T(x,f(x) /(1)(2)為A(3)R(z)(4)P(a，b)(5)Q(b) /(3)(4)(5)為B653.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 下面進(jìn)行歸結(jié)： （6） P(x,y)Q(y) （1）與（3）歸結(jié)，=f(x)/z （7） Q(b) （4）與（6）歸結(jié)，=a/x,b/y （8） NIL（空子句） （5）與（7）歸結(jié)所以B是A的邏輯結(jié)論。663.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 3.5.5 應(yīng)用歸結(jié)原理進(jìn)行問(wèn)題求

41、解應(yīng)用歸結(jié)原理進(jìn)行問(wèn)題求解下面是利用歸結(jié)原理求取問(wèn)題答案的步驟：（1）把已知前提條件用謂詞公式表示出來(lái)，并化成相應(yīng)的子句集，設(shè)該子句集的名字為S1。（2）把待求解的問(wèn)題也用謂詞公式表示出來(lái)，然后將其否定，并與一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個(gè)專(zhuān)為求解問(wèn)題而設(shè)置的謂詞，其變量必須與問(wèn)題公式的變量完全一致。（3）把問(wèn)題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1合并構(gòu)成子句集S。673.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 （4）對(duì)子句集S應(yīng)用謂詞歸結(jié)原理進(jìn)行歸結(jié)，在歸結(jié)的過(guò)程中，通過(guò)合一置換，改變ANSWER中的變?cè)?。?）如果得到歸結(jié)式ANSWER ，則問(wèn)

42、題的答案即在ANSWER謂詞中。683.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 例例 任何兄弟都有同一個(gè)父親，John和Peter是兄弟，且John的父親是David，問(wèn)Peter的父親是誰(shuí)？解解 第一步：將已知條件用謂詞公式表示出來(lái)，并化成子句集，那么要先定義謂詞。（1） 定義謂詞：設(shè)Father(x,y)表示x是y的父親。Brother(x,y)表示x和y是兄弟。693.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 （2） 將已知事實(shí)用謂詞公式表示出來(lái)。 F1 ：任何兄弟都有同一個(gè)父親。 (x)(y)(z)(Brother(x,y)Father(z,x)Father(z,y) F2：John和Pet

43、er是兄弟。 Brother(John,Peter) F3： John的父親是David。 Father(David, John)（3） 將它們化成子句集得： S1=Brother(x,y)Father(z,x)Father(z,y), Brother(John,Peter), Father(David,John)703.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 第二步：把問(wèn)題用謂詞公式表示出來(lái)，并將其否定與謂詞ANSWER作析取。 設(shè)Peter的父親是u，則有：Father(u,Peter)。 將其否定與ANSWER作析取，得： G：Father(u,Peter)ANSWER(u)713.5 3

44、.5 歸結(jié)推理方法歸結(jié)推理方法 第三步：將上述公式G化為子句集S2，并將S1和S2合并到S。 S2 =Father(u,Peter)ANSWER(u) S= S1S2將S中各子句列出如下：（1）Brother(x,y)Father(z,x)Father(z,y)。（2）Brother(John,Peter)。（3）Father(David,John)。（4）Father(u,Peter)ANSWER(u)。723.5 3.5 歸結(jié)推理方法歸結(jié)推理方法 第四步：應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)（5）Brother(John,y)Father(David,y) （1）與（3）歸結(jié) =David/z,John/x（6）Brother(John,Peter)ANSWER(David) （4）與（5）歸結(jié)=David/u,Peter/y（7）ANSWER(David) （2）與（6）歸結(jié)第五步：得到了歸結(jié)式ANSWER(David)，答案即在其中，所以u(píng)=David。即Peter的父親是David。733.6 歸結(jié)過(guò)程的控制策略3.6.1 引入控制策略引入控制策略1引入控制策略的原因 對(duì)子句集S進(jìn)行歸結(jié)時(shí)，首先要從子句集中找出