第3章 確定性推理方法課件

人工智能原理及應(yīng)用第3章確定性推理方法

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

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

3.2 確定性推理的邏輯基礎(chǔ)

3.3 演繹推理方法

3.4 歸結(jié)推理方法

3.5 歸結(jié)過程中的控制策略

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

3.1.1推理的概念

3.1.2推理的方法

3.1.3推理的控制策略

3.1.4推理中的沖突

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

3.1.1推理的概念

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

3.1.2推理的方法

推理有很多種方法，根據(jù)知識(shí)表示方式分類分為“圖搜索”方法及“邏輯論證”方法；根據(jù)邏輯基礎(chǔ)分類可分為演繹推理、歸納推理、默認(rèn)（缺?。┩评恚桓鶕?jù)知識(shí)的確定性分類分為確定性推理與非確定性推理；根據(jù)推理過程的單調(diào)性分類分為單調(diào)推理、非單調(diào)推理。1．演繹推理：演繹推理是一種由一般到個(gè)別的推理方法，其核心是三段論，由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論這三部分組成的。其邏輯式為：大前提是已知的一般性知識(shí)或推理過程得到的判斷；小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。第3章確定性推理方法3.1推理概述

3.1.2推理的方法

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

3.1.2推理的方法2．歸納推理歸納推理的基本思想是：先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以驗(yàn)證。例如常用的數(shù)學(xué)歸納法。歸納推理的類型按照所選取的事例的廣泛性可分為完全歸納推理、不完全歸納推理。歸納推理按照推理所使用的方法可分為枚舉歸納推理、類比歸納推理、默認(rèn)推理等。（1）枚舉歸納推理：是由已觀察到的事物都有某屬性，而沒有觀察到相反的事例，從而推出某類事物都有某屬性。（2）類比歸納推理：指在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們?cè)谄渌鼘傩陨弦蚕嗤蛳嗨频囊环N歸納推理。（3）默認(rèn)推理：稱為缺省推理，它是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。第3章確定性推理方法3.1推理概述

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

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

一個(gè)存放初始事實(shí)和中間結(jié)果的數(shù)據(jù)庫

一個(gè)用于推理的推理機(jī)第3章確定性推理方法3.1推理概述

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

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

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

3.1.3推理的控制策略例：請(qǐng)用正向推理完成以下問題的求解：假設(shè)知識(shí)庫中包含有以下2條規(guī)則：

r1：

IFBTHENC

r2：

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

它說明綜合數(shù)據(jù)庫中已經(jīng)含有問題的解，推理成功結(jié)束，目標(biāo)C得證。第3章確定性推理方法3.1推理概述

3.1.3推理的控制策略3.1.3.2反向推理反向推理是以某個(gè)假設(shè)目標(biāo)作為出發(fā)點(diǎn)的一種推理，又稱為目標(biāo)驅(qū)動(dòng)推理或逆向推理。反向推理過程如圖：第3章確定性推理方法3.1推理概述

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

3.1.3推理的控制策略例：請(qǐng)用反向推理完成以下問題的求解：假設(shè)知識(shí)庫中包含有以下2條規(guī)則：

r1：

IFBTHENC

r2：

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

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

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

（2）按規(guī)則排序（3）按數(shù)據(jù)排序

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

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

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

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

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

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

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

（2）交換律：

（3）結(jié)合律：

（4）分配律：

（5）摩根定律：

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

（7）補(bǔ)余律:（8）連詞化歸律:

（9）量詞轉(zhuǎn)換律:

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

定義3.4對(duì)謂詞公式P和Q，如果

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

（2）附加式：

（3）析取三段論：

（4）假言推理：

（5）拒取式：

第3章確定性推理方法3.2確定性推理的邏輯基礎(chǔ)3.2.3永真蘊(yùn)含式

常用永真蘊(yùn)含式包括：（6）假言三段論：

（7）二難推理：

（8）全稱固化：

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

其中，y是個(gè)體域中某一個(gè)可以使

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

范式分為兩種：前束范式與Skolem范式。定義3.5設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，且它們的轄域?yàn)檎麄€(gè)公式，則稱F為前束范式。一般形式：其中，

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

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

是項(xiàng)，

是互不相同的變?cè)?/p>

表示用t1

替換x1，并且要求t1

與x1

不能相同，x1

不能循環(huán)地出現(xiàn)在另一個(gè)t1

中。定義3.8設(shè)

是一個(gè)置換，F(xiàn)是一個(gè)謂詞公式，把公式F中出現(xiàn)的所有

換成

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

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

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

①當(dāng)

時(shí)，刪去

②當(dāng)

時(shí)，刪去

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

若存在一個(gè)置換θ，可使:

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

是公式集F的一個(gè)合一，如果對(duì)F的任一個(gè)合一

都存在一個(gè)置換

，使得

，則稱

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

F規(guī)則為：

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

Skolem化后：

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

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

，使得若有

必有

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

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

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

對(duì)Herbrand（海伯倫）定理一般通俗性解釋是：如果一個(gè)一階謂詞公式是永真的，則該公式的機(jī)器定理證明求解計(jì)算可在有限步內(nèi)實(shí)現(xiàn)證明；如果該公式不是永真的，則無法在有限步內(nèi)實(shí)現(xiàn)證明。第3章確定性推理方法3.4歸結(jié)推理方法3.4.2Herbrand（海伯倫）定理3．Herbrand（海伯倫）定理

例：對(duì)子句集

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

Herbrand定理用于語義樹解釋有：定理3.8子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語義樹都是一棵有限的封閉語義樹。定理3.9子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的有限基例集（即存在有限個(gè)失敗結(jié)點(diǎn)）。

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

S是不可滿足的

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

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

L1與

～L2有最一般合一

，則把：

稱作子句

C1和C2的一個(gè)二元?dú)w結(jié)式，而

L1和L2是被歸結(jié)的文字。

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

R1:“任何通過計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂的”

R2:“任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有考試”

R3:“張不肯學(xué)習(xí)但他是幸運(yùn)的”

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

(2)

(3)由R3可得

(4)

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

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

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

王先生是小李的老師；

小李和小張是同班同學(xué)；

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

：x是y的老師；

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

③

④

⑤

①②歸結(jié)⑥

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

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

①②歸結(jié)⑥

④⑤歸結(jié)⑦

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