第四章邏輯推理

第四章邏輯推理第一頁，共九十五頁，編輯于2023年，星期五4.1推理的基本概念按照某種策略從已知事實(shí)出發(fā)推出結(jié)論的過程。推理所用的事實(shí)分為兩種：

初始證據(jù)與中間結(jié)論智能系統(tǒng)的推理過程是通過推理機(jī)來完成的。所謂推理機(jī)就是智能系統(tǒng)中用來實(shí)現(xiàn)推理的程序。

一.什么是推理第二頁，共九十五頁，編輯于2023年，星期五二.推理方法及其分類可以從不同角度對(duì)推理方式進(jìn)行分類（邏輯基礎(chǔ)、所用知識(shí)的確定性、推理過程的單調(diào)性）1.按推理的邏輯基礎(chǔ)分類演繹推理歸納推理默認(rèn)推理

第三頁，共九十五頁，編輯于2023年，星期五演繹推理由一般到個(gè)別的推理方法。核心是三段論，通常由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論三部分組成的。例：阿凡提的故事---兩頭驢的故事①我肩上馱的是兩頭驢的東西（大前提）②國王和大臣的衣衫是我肩上馱的（小前提）③國王和大臣的衣衫是兩頭驢的東西（結(jié)論）第四頁，共九十五頁，編輯于2023年，星期五歸納推理從一類事物的大量特殊事例出發(fā)，去推出該類事物的一般性結(jié)論。（從個(gè)別到一般）基本思想是：先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn)。（歸納結(jié)論不具備邏輯必然性）數(shù)學(xué)歸納法就是歸納推理的一種典型例子。

如果按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理；如果按照推理所使用的方法可分為枚舉歸納推理、類比歸納推理、統(tǒng)計(jì)歸納推理和差異歸納推理等。

第五頁，共九十五頁，編輯于2023年，星期五演繹推理所得出的結(jié)論蘊(yùn)含在一般性知識(shí)的前提中，演繹推理只不過是將已有事實(shí)揭示出來，因此它不能增殖新知識(shí)。在歸納推理中，所推出的結(jié)論是沒有包含在前提內(nèi)容中的。這種由個(gè)別事物或現(xiàn)象推出一般性知識(shí)的過程，是增殖新知識(shí)的過程。演繹推理與歸納推理的區(qū)別第六頁，共九十五頁，編輯于2023年，星期五

確定性推理

推理所使用的知識(shí)和推出的結(jié)論都是可以精確表示的，其真值要么為真，要么為假，不會(huì)有第三種情況出現(xiàn)。經(jīng)典邏輯推理

不確定性推理

推理時(shí)所用的知識(shí)不都是確定的，推出的結(jié)論也不完全是確定的，其真值位于真與假之間。概率(probability)，模糊(fuzzy)2.按所用知識(shí)的確定性分類第七頁，共九十五頁，編輯于2023年，星期五3.按推理過程的單調(diào)性分類單調(diào)推理在推理過程中，每當(dāng)使用新的知識(shí)后，所得到的結(jié)論會(huì)越來越接近于目標(biāo)，而不會(huì)出現(xiàn)反復(fù)情況，即不會(huì)由于新知識(shí)的加入否定了前面推出的結(jié)論，從而使推理過程又退回到先前的某一步。非單調(diào)推理在推理過程中，當(dāng)某些新知識(shí)加入后，會(huì)否定原來推出的結(jié)論，使推理過程退回到先前的某一步。第八頁，共九十五頁，編輯于2023年，星期五三.推理控制策略如何使用領(lǐng)域知識(shí)使推理過程盡快達(dá)到目標(biāo)？推理控制策略可分為推理策略和搜索策略。推理策略主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等搜索策略主要解決推理線路、推理效果、推理效率等問題第九頁，共九十五頁，編輯于2023年，星期五1.推理策略推理方向正向推理、逆向推理、混合推理求解策略一個(gè)解，所有解或最優(yōu)解？限制策略對(duì)推理的深度,寬度,時(shí)間,空間等進(jìn)行限制沖突消解策略

如何從多條可用知識(shí)中選擇？第十頁，共九十五頁，編輯于2023年，星期五2.正向推理從已知事實(shí)出發(fā)、正向使用推理規(guī)則也稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈推理基本思想：

推理機(jī)根據(jù)已有事實(shí)，尋找當(dāng)前可用知識(shí)，然后按照沖突消解策略，從當(dāng)前可用知識(shí)集中選擇一條知識(shí)進(jìn)行推理，并將新推出的事實(shí)作為后面繼續(xù)推理時(shí)可用的已知事實(shí)。重復(fù)上述過程，直到求出所需要的解或者知識(shí)庫中再無可用知識(shí)。

第十一頁，共九十五頁，編輯于2023年，星期五3.逆向推理以假設(shè)目標(biāo)作為出發(fā)點(diǎn)進(jìn)行推理也稱為目標(biāo)驅(qū)動(dòng)推理或逆向鏈推理基本思想：首先將要求證的目標(biāo)（稱為假設(shè)）構(gòu)成假設(shè)集，從中逐個(gè)取出假設(shè)進(jìn)行驗(yàn)證。如該假設(shè)為已知事實(shí)或原始證據(jù)，則假設(shè)成立；如該假設(shè)可由知識(shí)庫中的一個(gè)或多個(gè)知識(shí)導(dǎo)出，則知識(shí)庫中所有可以導(dǎo)出該假設(shè)的知識(shí)構(gòu)成當(dāng)前可用知識(shí)集，從中選擇一個(gè)知識(shí)，將其前提中的所有子條件都作為新的假設(shè)放入假設(shè)集。重復(fù)上述過程，直到假設(shè)集為空時(shí)成功退出，或假設(shè)集非空但可用知識(shí)集為空時(shí)失敗退出。第十二頁，共九十五頁，編輯于2023年，星期五正向推理逆向推理優(yōu)點(diǎn)比較直觀，允許用戶主動(dòng)提供有用的事實(shí)信息。推理過程的目標(biāo)明確，同時(shí)也有利于向用戶提供解釋缺點(diǎn)推理無明確目標(biāo)，會(huì)執(zhí)行許多與解無關(guān)的操作，效率較低初始目標(biāo)選擇有盲目性，若選擇不好，可能需要多次提出假設(shè)，影響系統(tǒng)效率第十三頁，共九十五頁，編輯于2023年，星期五4.混合推理把正向推理和逆向推理結(jié)合起來所進(jìn)行的推理實(shí)現(xiàn)方法先正向后逆向先逆向后正向雙向混合推理同時(shí)作正向和逆向推理，二者在某處碰頭

第十四頁，共九十五頁，編輯于2023年，星期五5.推理的沖突消解策略在推理過程中，同時(shí)有多條知識(shí)可用，則發(fā)生“沖突”。如正向推理時(shí)有多條規(guī)則的前件與已有事實(shí)匹配成功，或逆向推理時(shí)有多條規(guī)則的后件與已有事實(shí)匹配成功。從多條可用知識(shí)中選擇用于推理的最佳知識(shí)，稱為“沖突消解”，其中所用策略稱為“沖突消解策略”。第十五頁，共九十五頁，編輯于2023年，星期五沖突消解策略基本思想對(duì)可用知識(shí)進(jìn)行排序常用排序方法

1.按特殊性排序

2.按新鮮性排序

3.差異性大的知識(shí)優(yōu)先

4.領(lǐng)域特點(diǎn)優(yōu)先

5.上下文關(guān)系優(yōu)先

6.前提條件少者優(yōu)先

第十六頁，共九十五頁，編輯于2023年，星期五4.2推理的邏輯基礎(chǔ)根據(jù)經(jīng)典邏輯的邏輯規(guī)則進(jìn)行的一種推理確定性推理主要推理方法包括

自然演繹推理歸結(jié)演繹推理與/或形演繹推理第十七頁，共九十五頁，編輯于2023年，星期五推理的邏輯基礎(chǔ)一階謂詞邏輯表示謂詞公式的解釋謂詞公式的永真性與可滿足性謂詞公式的等價(jià)性與永真蘊(yùn)含性謂詞公式的范式置換與合一

第十八頁，共九十五頁，編輯于2023年，星期五一、一階謂詞邏輯表示的邏輯基礎(chǔ)命題與真值論域和謂詞連接詞和量詞項(xiàng)與合式公式自由變?cè)图s束變?cè)谑彭?，共九十五頁，編輯?023年，星期五命題與真值一個(gè)陳述句稱為一個(gè)斷言。凡有真假意義的斷言稱為命題。命題的意義通常稱為真值，它只有真假兩種情況。真值為真記為T；反之記為F。一個(gè)命題不能同時(shí)既為真又為假例：“天安門城樓在長安街的北邊”是一個(gè)真值為T的命題，“天安門廣場(chǎng)在長安街的北邊”則是一個(gè)真值為F的命題。第二十頁，共九十五頁，編輯于2023年，星期五命題與真值一個(gè)命題可在一定條件下為真，在另外的條件下為假例：“北京今天有雨”沒有真假意義的感嘆句、疑問句等都不是命題。命題的優(yōu)點(diǎn)是簡單、明確；其主要缺點(diǎn)是無法描述客觀事物的結(jié)構(gòu)及其邏輯特征，也無法表示不同事物間的共性。

第二十一頁，共九十五頁，編輯于2023年，星期五論域和謂詞論域是由所討論對(duì)象之全體構(gòu)成的非空集合。在謂詞邏輯中，命題是用謂詞來表示的。一個(gè)謂詞可分為謂詞名和個(gè)體兩部分。謂詞定義：

設(shè)D是論域，P:Dn→{T，F(xiàn)}是一個(gè)映射，其中

Dn={(x1,x2,…,xn)|x1,x2,…,xn∈D}，則稱P是一個(gè)n元謂詞（n=1,2,…）,記為P(x1,x2,…,xn)。其中,x1,x2,…,xn為個(gè)體變?cè)?。第二十二頁，共九十五頁，編輯?023年，星期五謂詞在謂詞P(x1,x2,……,xn)中，如果xi(i=1,2,…,n)都是個(gè)體常量、變?cè)蚝瘮?shù)，稱它為一階謂詞。如果某個(gè)xi本身又是一個(gè)一階謂詞，則稱它為二階謂詞。例子

1.“王宏是學(xué)生”STUDENT(Wanghong)。

2.“x>6”Greater(x,6)3.“王宏的父親是教師”TEACHER(father(Wanghong))第二十三頁，共九十五頁，編輯于2023年，星期五連接詞┓：“非”或者“否定”┓P

對(duì)其后面命題的否定，使該命題的真值與原來相反?！牛骸拔鋈　盤∨Q

兩個(gè)命題之間具有“或”的關(guān)系。∧：“合取”P∧Q

兩個(gè)命題之間具有“與”的關(guān)系。→：“條件”或“蘊(yùn)含”P→Q

表示“若…則…”的語義?！骸半p條件”P←→Q

表示“當(dāng)且僅當(dāng)”的語義同命題邏輯，連接簡單命題成復(fù)合命題第二十四頁，共九十五頁，編輯于2023年，星期五對(duì)以上連接詞的定義，可用下表所給出的謂詞邏輯真值表來表示。

謂詞邏輯真值表

P

Q~PP∨QP∧QP→QP←→QTTFTTTTTFFTFFFFTTTFTFFFTFFTT第二十五頁，共九十五頁，編輯于2023年，星期五量詞量詞是由量詞符號(hào)和被其量化的變?cè)M成的表達(dá)式，對(duì)謂詞中的個(gè)體作出量的規(guī)定。全稱量詞：

命題(x)P(x)為真，當(dāng)且僅當(dāng)對(duì)論域中的所有x，都有P(x)為真。命題(x)P(x)為假，當(dāng)且僅當(dāng)至少存在一個(gè)x0∈D，使得P(x0)為假。存在量詞

命題(x)P(x)為真，當(dāng)且僅當(dāng)至少存在一個(gè)

x0∈D，使得P(x0)為真。命題(彐x)P(x)為假，當(dāng)且僅當(dāng)對(duì)論域中的所有x，都有P(x)為假。彐第二十六頁，共九十五頁，編輯于2023年，星期五項(xiàng)與合式謂詞公式——合法的表達(dá)式稱為合式公式項(xiàng):

（1）單獨(dú)一個(gè)個(gè)體詞是項(xiàng)；

（2）若t1，t2,…，tn是項(xiàng)，f是n元函數(shù)

，則f(t1,t2,…,tn)是項(xiàng)；

（3）由（1）,（2）生成的表達(dá)式是項(xiàng)原子謂詞公式：若t1，t2，…，tn是項(xiàng)，P是謂詞符號(hào)，則稱

P(t1,t2,…,tn)為原子謂詞公式。第二十七頁，共九十五頁，編輯于2023年，星期五項(xiàng)與合式合式公式：

（1）單個(gè)原子謂詞公式是合式公式；

（2）若A是合式公式，則┓A也是合式公式；

（3）若A、B都是合式公式，則A∨B，A∧B，A→B，A←→B也都是合式公式；

（4）若A是合式公式，x是項(xiàng)，則（

x)A和(彐x)A也都是合式公式。第二十八頁，共九十五頁，編輯于2023年，星期五自由變?cè)图s束變?cè)?dāng)一個(gè)謂詞公式含有量詞時(shí)，區(qū)分個(gè)體變?cè)欠袷芰吭~的約束是很重要的。通常，把位于量詞后面的單個(gè)謂詞或者用括號(hào)括起來的合式公式稱為該量詞的轄域，轄域內(nèi)與量詞中同名的變?cè)Q為約束變?cè)?，不受約束的變?cè)Q為自由變?cè)?/p>

（x)(P(x,y)→Q(x,y))∨R(x,y)

第二十九頁，共九十五頁，編輯于2023年，星期五謂詞邏輯表示法

謂詞邏輯可以用來表示知識(shí)

事物的狀態(tài)、屬性、概念等事實(shí)性知識(shí)，通常用否定、析取或合取符號(hào)連接起來的謂詞公式表示。事物的因果關(guān)系，即規(guī)則，通常用蘊(yùn)含式表示，例如，對(duì)“如果x，則y”,可表示為“x→y”。第三十頁，共九十五頁，編輯于2023年，星期五謂詞邏輯表示法例子“每個(gè)人都有一個(gè)父親”(x)(y)(PERSON(x)→HASFATHER(x,y))“所有教師都有自己的學(xué)生”

(x)(y)(TEACHER(x)→TEACHES(x,y)∧STUDENT(y))“所有的整數(shù)不是偶數(shù)就是奇數(shù)”

(x)(I(x)→E(x)∨O(x))彐彐第三十一頁，共九十五頁，編輯于2023年，星期五例：機(jī)器人移盒子問題

設(shè)在一房間里，c處有一個(gè)機(jī)器人，a和b處各有一張桌子，分別稱為a桌和b桌，a桌子上有一盒子，如下圖所示。要求機(jī)器人從c處出發(fā)把盒子從a桌上拿到b桌上，然后再回到c處。請(qǐng)用謂詞邏輯來描述機(jī)器人的行動(dòng)過程。

機(jī)器人移盒子ABC謂詞邏輯表示的應(yīng)用第三十二頁，共九十五頁，編輯于2023年，星期五

在這個(gè)例子中，不僅要用謂詞公式來描述事物的狀態(tài)、位置，而且還要用謂詞公式表示動(dòng)作。為此，需要定義如下謂詞公式：

TABLE(x):x是桌子

EMPTY(y):y手中是空的

AT(y,z):y在z的附近

HOLDS(y,w):y拿著w

ON（w，x）：w在x桌面上。其中：x的個(gè)體域是：y的個(gè)體域是：z的個(gè)體域是：w的個(gè)體域是：｛a，b｝{robot｝｛a，b，c｝{box}第三十三頁，共九十五頁，編輯于2023年，星期五

問題的初始狀態(tài)是：

AT（robot,c）

EMPTY（robot）

ON（box，a）

TABLE（a）

TABLE（b）

問題的目標(biāo)狀態(tài)是：

AT（robot，c）

EMPTY（robot）

ON（box，b）

TABLE（a）

TABLE（b）使用規(guī)則！第三十四頁，共九十五頁，編輯于2023年，星期五

機(jī)器人行動(dòng)的目標(biāo)是把問題的初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)，而要實(shí)現(xiàn)問題狀態(tài)的轉(zhuǎn)換需要完成一系列的操作。對(duì)于每個(gè)操作，一般都可分為條件和動(dòng)作兩個(gè)部分．

條件部分用來說明執(zhí)行該操作必須具備的先決條件，

動(dòng)作部分給出了該操作對(duì)問題狀態(tài)的改變情況。

條件部分可用謂詞公式來表示，動(dòng)作部分則是通過在執(zhí)行該操作前的問題狀態(tài)中刪去和增加相應(yīng)的謂詞來實(shí)現(xiàn)的。

在本問題中，機(jī)器人需要執(zhí)行以下三個(gè)操作：

Goto（x，y）：從x處走到y(tǒng)處。

Pickup（x）：在x處拿起盒子。

Setdown（x）：在x處放下盒子。

第三十五頁，共九十五頁，編輯于2023年，星期五

這三個(gè)操作對(duì)應(yīng)的條件與動(dòng)作如下：

Goto（x,y）

條件：AT（robot,x）

動(dòng)作：刪除表：AT（robot,x）

添加表：AT（robot,y）

Pickup（x）

條件：ON（box,x），TABLE（x），

AT（robot,x），EMPTY（robot）

動(dòng)作：刪除表：EMPTY（robot），

ON（box，x）

添加表：HOLDS（robot,box）

Setdown（x）

條件：AT（robot,x），TABLE（x），

HOLDS（robot,box）

動(dòng)作：刪除表：HOLDS（robot,box）

添加表：EMPTY（robot），

ON（box,x）第三十六頁，共九十五頁，編輯于2023年，星期五

機(jī)器人在執(zhí)行每一操作之前，都需要檢查當(dāng)前狀態(tài)是否可以滿足該操作的先決條件。如果滿足，就執(zhí)行相應(yīng)的操作，否則就檢查下一個(gè)操作所要求的先決條件。

作為謂詞邏輯知識(shí)表示方法的應(yīng)用，下面給出這個(gè)機(jī)器人行動(dòng)規(guī)劃問題的求解過程。其中，在檢查先決條件是否滿足時(shí)還需要進(jìn)行變量的置換。

謂詞邏輯表示的應(yīng)用第三十七頁，共九十五頁，編輯于2023年，星期五

狀態(tài)l（初始狀態(tài)）

AT(robot,c)

開始

EMPTY（robot）

========>ON（box，a）

TABLE（a）

TABLE（b）

Goto（x，y）

===============〉

用c代換x，a代換y

狀態(tài)2

AT（robot,a）

EMPTY（robot）

ON（box,a）

TABLE（a）

TABLE（b）

Pickup（x）

＝＝＝＝＝＝>

用a代換x

狀態(tài)3

AT（robot，a）

HOLDS（robot，box）

TABLE（a）

TABLE（b）

Goto（x，y）

＝＝＝＝＝＝＞

用a代換x，b代換y

狀態(tài)4

AT（robot，b）

HOLDS（robot，box）

TABLE（a）

TABLE（b）

Setdown（x）

============>

用b代換x狀態(tài)5

AT(robot,b)EMPTY（robot）ON(box,b)

TABLE（a）

TABLE（b）

Goto（x，y）

============>

用b代換x，c代換y

狀態(tài)6（目標(biāo)狀態(tài)）

AT（robot，c）EMPTY（robot）ON(box,b)

TABLE（a）TABLE（b）第三十八頁，共九十五頁，編輯于2023年，星期五二.謂詞公式的解釋設(shè)D是謂詞公式P的非空個(gè)體域，若對(duì)P中的個(gè)體常量、函數(shù)和謂詞按如下規(guī)定賦值：

（1）為每個(gè)個(gè)體常量指派D中的一個(gè)元素；（2）為每個(gè)n元函數(shù)指派一個(gè)從Dn到D的一個(gè)映射，其中

Dn∈{(x1,x2,……xn)|x1,x2,……,xn∈D}

（3）為每個(gè)n元謂詞指派一個(gè)從Dn到{T,F}的映射

則稱這些指派為P在D上的一個(gè)解釋。第三十九頁，共九十五頁，編輯于2023年，星期五例1：設(shè)個(gè)體域D={1,2}，求公式A=(x)(y)P(x,y)在D上的解釋，并指出在每一種解釋下公式A的真值。P(1,1)P(1,2)P(2,1)P(2,2)TFTFP(1,1)P(1,2)P(2,1)P(2,2)TTFF由上面的例子可以看出，謂詞公式的其值都是針對(duì)某一個(gè)解釋而言的，它可能在某一個(gè)解釋下真值為T，而在另一個(gè)解釋下為F。第四十頁，共九十五頁，編輯于2023年，星期五例2：設(shè)個(gè)體域D=｛1，2｝，求公式B=（x）P（F（x），a）在D上的解釋，并指出在該解釋下公式B的真值。aF(1)F(2)112對(duì)個(gè)體常量和函數(shù)的指派P(1,1)P(1,2)P(2,1)P(2,2)T×T×對(duì)謂詞的指派第四十一頁，共九十五頁，編輯于2023年，星期五三.謂詞公式的永真性與可滿足性如果謂詞公式P對(duì)非空個(gè)體域D上的任一解釋都取得真值T(F)，則稱P在D上是永真(假)的；如果P在任何非空個(gè)體域上均是永真(假)的，則稱P永真(假)

。永假性又稱不可滿足性或不相容性。對(duì)于謂詞公式P，如果至少存在D上的一個(gè)解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。謂詞公式的可滿足性又稱為相容性.第四十二頁，共九十五頁，編輯于2023年，星期五四.謂詞公式的等價(jià)性與永真蘊(yùn)含性

謂詞公式的等價(jià)性和永真蘊(yùn)含性可分別用相應(yīng)的等價(jià)式和永真蘊(yùn)含式來表示。這些等價(jià)式和永真蘊(yùn)含式都是演繹推理的主要依據(jù)，因此也稱它們?yōu)橥评硪?guī)則。

1．等價(jià)式

謂詞公式的等價(jià)式可定義如下：

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

第四十三頁，共九十五頁，編輯于2023年，星期五

（1）雙重否定率p<==>p

（2）交換率P∨Q<==>Q∨P，P∧Q<==>Q∧P

（3）結(jié)合率（P∨Q）∨R<==>P∨（Q∨R）,（P∧Q）∧R<==>P∧（Q∧R）

（4）分配率P∨（Q∧R）<==>（P∨Q）∧（P∨R）

P∧（Q∨R）<==>（P∧Q）∨（P∧R）

（5）狄·摩根定律（P∨Q）<==>P∧Q

（P∧Q）<==>P∨Q

（6）吸收率P∨（P∧Q）<==>P，P∧（P∨Q）<==>P

（7）補(bǔ)余率P∨P<==>T,P∧P<==>F

（8）連詞化歸率P→Q<==>P∨Q

第四十四頁，共九十五頁，編輯于2023年，星期五2.永真蘊(yùn)含式定義：對(duì)謂詞公式P和Q，如果P→Q永真，則稱P永真蘊(yùn)含

Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記作P=>Q。

（1）化簡式P∧Q=>P，P∧Q=>Q

（2）附加式P=>P∨Q，Q=>P∨Q

（3）析取三段論P(yáng)，PVQ=>Q

（4）假言推理P，P→Q=>Q

（5）拒取式Q，P→Q=>P

（6）假言三段論P(yáng)→Q，Q→R=>P→R

（7）二難推理P∨Q，P→R，Q→R=>R

（8）全稱固化（x）P（x）=>P（y）

其中，y是個(gè)體域中的任一個(gè)體，利用此永真蘊(yùn)含式可消去謂詞公式中的全程量詞。

（9）存在固化（彐x）P（x）=>P（y）

其中，y是個(gè)體域中某一個(gè)可以使P（y）為真的個(gè)體，利用此永真蘊(yùn)含式可消去謂詞公式中的存在量詞。

第四十五頁，共九十五頁，編輯于2023年，星期五

范式是公式的標(biāo)準(zhǔn)形式，公式往往需要變換為同它等價(jià)的范式，以便對(duì)它們作一般性的處理。在謂詞邏輯中，根據(jù)量詞在公式中出現(xiàn)的情況可將謂詞公式的范式分為兩種：前束范式Skolem范式五．謂詞公式的范式

第四十六頁，共九十五頁，編輯于2023年，星期五1.前束范式設(shè)F為一謂詞公式，如果其中的所有量詞均非否定地出現(xiàn)在公式的最前面，而它們的轄域?yàn)檎麄€(gè)公式，則稱F為前束范式。一般地，前束范式可寫成:

（Q1x1）…（Qnxn）M(x1,x2,……,xn)

其中，Qi（i=1，2，…，n）為前綴，它是一個(gè)由全稱量詞或存在量詞組成的量詞串；M(x1,x2,……,xn)為母式，它是一個(gè)不含任何量詞的謂詞公式。例：（x）(y）(z）(P(x)∧Q(y,z)∨R(x,z))任一謂詞公式均可化為與其對(duì)應(yīng)的前束范式第四十七頁，共九十五頁，編輯于2023年，星期五2.Skolem范式如果前束范式中所有的存在量詞都在全稱量詞之前，則稱這種形式的謂詞公式為Skolem范式。例：（x）（z）（y）（P(x)∨Q(y，z)∧R(x，z))任一謂詞公式均可化為與其對(duì)應(yīng)的Skolem范式第四十八頁，共九十五頁，編輯于2023年，星期五在不同謂詞公式中，往往會(huì)出現(xiàn)謂詞名相同但其個(gè)體不同的情況，此時(shí)推理過程是不能直接進(jìn)行匹配的，需要先進(jìn)行置換。例如，可根據(jù)全稱固化推理和假言推理由謂詞公式

W1(A)和（x）(W1(x)→W2(x))推出W2(A)?？梢钥闯?，要使用假言推理，首先需要找到項(xiàng)A對(duì)變?cè)獂的置換，使W1(A)與W1(x)一致。這種尋找項(xiàng)對(duì)變?cè)闹脫Q，使謂詞一致的過程叫做合一的過程。下面討論置換與合一的有關(guān)概念與方法。六．置換與合一第四十九頁，共九十五頁，編輯于2023年，星期五1.置換（Substitution）置換是形如{t1/x1,t2/x2,……,tn/xn}的有限集合。其中，t1,t2,…,tn是項(xiàng)；x1,x2,…,xn是互不相同的變?cè)?；ti/xi表示用ti置換xi。并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。置換的目的是將某些變?cè)昧硗獾淖冊(cè)?、常量或函?shù)取代，使其不在公式中出現(xiàn)。例：｛a／x，c／y，f(b)／z｝｛g(y)/x,f(x)/y｝第五十頁，共九十五頁，編輯于2023年，星期五置換的合成設(shè)θ={t1/x1,t2/x2,……,tn/xn},λ={u1/y1,u2/y2,……,um/ym}

是兩個(gè)置換。則θ與λ的合成也是一個(gè)置換，記作θ·λ它是從集合

{t1λ/x1,t2λ/x2,……,tnλ/xn,u1/y1,u2/y2,…,um/ym}

中刪去以下兩種元素

①當(dāng)tiλ=xi時(shí)，刪去tiλ/xi；

②當(dāng)yi∈｛x1,x2,…,xn｝時(shí)，刪去uj／yj。

最后剩下的元素所構(gòu)成的集合。第五十一頁，共九十五頁，編輯于2023年，星期五置換的合成實(shí)例例：設(shè)θ={f(y)/x,z/y},λ={a/x,b/y,y/z}，求θ與λ的合成。先求出集合{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}={f(b)/x,y/y,a/x,b/y,y/z}

根據(jù)條件①，刪除y/y

根據(jù)條件②，刪除a/x和b/y

最后得

θ·λ={f(b)/x,y/z}θ={f(y)/x,z/m},λ={a/x,b/y,m/z}{f(b/y)/x,(m/z)/m,a/x,b/y,m/z}={f(b)/x,m/m,a/x,b/y,m/z}

根據(jù)條件①，刪除m/m

根據(jù)條件②，刪除a/x

最后得

θ·λ={f(b)/x,b/y,m/z}第五十二頁，共九十五頁，編輯于2023年，星期五合一可以簡單地理解為是尋找項(xiàng)對(duì)變量的置換，使兩個(gè)謂詞公式一致。其形式定義如下:

定義：設(shè)有公式集F={F1,F2,…..,Fn},若存在一個(gè)置換θ，可使F1θ=F2θ=F3θ=……Fnθ

。則稱θ是F的一個(gè)合一。稱F1,F2,…..,Fn是可合一的。

一般來說．一個(gè)公式集的合一不是唯一的。定義：設(shè)σ是公式集F的一個(gè)合一,如果對(duì)F的任一個(gè)合一θ都存在一個(gè)置換λ，可使θ=σ·λ,則稱σ是一個(gè)最一般合一(MostGeneralUnifier.簡記MGU)。

一個(gè)公式集的最一般合一是唯一的。如果用最一般合一去置換可合一的謂詞公式,可使它們變成完全一致的謂詞公式。2.合一（Unifier）第五十三頁，共九十五頁，編輯于2023年，星期五合一算法設(shè)F={F1,F2,…..,Fn}是一個(gè)非空有限的公式集,從F中每個(gè)公式的第一個(gè)符號(hào)同時(shí)向右比較,直到發(fā)現(xiàn)第一個(gè)不相同的符號(hào)為止,從F的每個(gè)公式中取出以第一個(gè)不相同符號(hào)開始的最大子表達(dá)式,并組成一個(gè)集合D,則D稱為F的分歧集（DisagreementSet)。例：求F=｛P（x,y,z），P（x,f(a),h(b)）的分歧集解:

這里F1=P（x，y，z），F(xiàn)2=P（x,f(a),h（b）F1中的y與F2中的f（a）不同，它們構(gòu)成了一個(gè)分歧集：D1={y,f(a)}

F1中的z與F2中的h(b)不同，它們又構(gòu)成了一個(gè)分歧集：D2={z,h(b)}第五十四頁，共九十五頁，編輯于2023年，星期五合一算法

(1)令k=0,Fk=F,σk=ε(空置換)；

(2)若Fk只含有一個(gè)表達(dá)式，則算法停止,σk就是最一般合一;

(3)找出Fk的分歧集DK；

(4)若DK中存在元素xk和tk,xk是變?cè)?tk是項(xiàng),同時(shí)xk不在tk中出現(xiàn),則置

σk+1=σk·{tk/xk},Fk+1=Fk{tk/xk},k=k+1然后轉(zhuǎn)（2）；

（5）算法停止，F(xiàn)的最一般合一不存在。

第五十五頁，共九十五頁，編輯于2023年，星期五例：求公式集F={P(a,x,f(g(y)))

，P(z,h(a,u),f(u))}的最一般合一.解:根據(jù)合一算法,首先置

k=0;F0=F;σ0=ε

F0不是單一表達(dá)式,有D0={a,z}.其中z為變?cè)?并且z不在a中出現(xiàn),從而

σ1=σ0

·{a/z}

F1=F0(a/z)={P(a,x,f(g(y)))，P(a,h(a,u),f(u))}

k=1:F1不是單一表達(dá)式,D1={x,h(a,u)}.其中x為變?cè)?從而

σ2=σ1

·{h(a,u)/x}={a/z,h(a,u)/x}

F2=F1(h(a,u)/x)={P(a,h(a,u),f(g(y)))，P(a,h(a,u),f(u))}k=2:F2不是單一表達(dá)式,D2={g(y),u}.其中u為變?cè)?從而

σ3=σ2

·{g(y)/u}={a/z,h(a,g(y))/x,g(y)/u}

F3=F2(g(y)/u)={P(a,h(a,g(y)),f(g(y)))，P(a,h(a,g(y)),f(g(y)))}={P(a,h(a,g(y)),f(g(y)))}k=3:

F3已是單一表達(dá)式,從而

σ3={a/z,h(a,g(y))/x,g(y)/u}是F的最一般合一.第五十六頁，共九十五頁，編輯于2023年，星期五從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯中的推理規(guī)則推出結(jié)論。

注意避免兩類錯(cuò)誤：

肯定后件的錯(cuò)誤是指當(dāng)P→Q為真時(shí)，希望通過肯定后件Q為真來推出前件P為真

否定前件的錯(cuò)誤是指當(dāng)P→Q為真時(shí)，希望通過否定前件P來推出后件Q為假

天下雨地濕肯定后件:地濕下雨?否定前件:天不下雨地不濕?4.3自然演繹推理第五十七頁，共九十五頁，編輯于2023年，星期五

例：設(shè)已知如下事實(shí)：

（1）只要是需要編程序的課，王程都喜歡。

（2）所有的程序設(shè)計(jì)語言課都是需要編程序的課。

（3）C是一門程序設(shè)計(jì)語言課。

求證：王程喜歡C這門課。

證明：首先定義謂詞Prog(x)x是需要編程序的課。

Like(x,y)x喜歡y。

Lang(x)x是一門程序設(shè)計(jì)語言課。

把上述已知事實(shí)及待求解問題用謂詞公式表示如下：

Prog（x）→Like（Wang，x）

（x）（Lang（x）→Prog(x))

Lang（C）

應(yīng)用推理規(guī)則進(jìn)行推理:（x）（Lang（x）→Prog(x))=>Lang（y）→Prog（y）全稱固化

Lang（C），Lang（y）→Prog（y）=>Prog（C）假言推理

Prog（C），Prog（x）→Like（Wang，x）=>Like（Wang，C）假言推理.因此，王程喜歡C這門課。

例：設(shè)已知如下事實(shí)：

A，B，A→C，B∧C→D，D→Q

求證：Q為真。

證明：因?yàn)锳，A→C=>C假言推理

B，C=>B∧C引入合取詞

B∧C，B∧C→D=>D假言推理

D，D→Q=>Q假言推理

所以Q為真。第五十八頁，共九十五頁，編輯于2023年，星期五自然演繹推理優(yōu)缺點(diǎn)優(yōu)點(diǎn)過程自然，易于理解，推理規(guī)則豐富缺點(diǎn)容易產(chǎn)生知識(shí)爆炸，推理過程中得到的中間結(jié)論一般按指數(shù)規(guī)律遞增，對(duì)于復(fù)雜問題的推理不利，甚至難以實(shí)現(xiàn)第五十九頁，共九十五頁，編輯于2023年，星期五4.4歸結(jié)演繹推理

基于魯賓遜（Robinson）歸結(jié)原理的機(jī)器推理技術(shù)。魯賓遜歸結(jié)原理亦稱為消解原理，是魯賓遜于1965年在海伯倫（Herbrand）理論的基礎(chǔ)上提出的一種基于邏輯的“反證法”。在人工智能中，幾乎所有的問題都可以轉(zhuǎn)化為一個(gè)定理證明問題。而定理證明的實(shí)質(zhì)，就是要對(duì)前提P和結(jié)論Q，證明P→Q永真。第六十頁，共九十五頁，編輯于2023年，星期五欲證明P→Q永真，一種途徑是證明P→Q在任何一個(gè)非空個(gè)體域上都是永真的。非常困難，難以實(shí)現(xiàn)可將關(guān)于永真性的證明轉(zhuǎn)化為關(guān)于不可滿足性的證明。即要證明P→Q永真，只要能夠證明

P∧Q是不可滿足的就可以了。海伯倫理論和魯賓遜歸結(jié)原理。

理論基礎(chǔ)實(shí)現(xiàn)條件第六十一頁，共九十五頁，編輯于2023年，星期五文字：原子謂詞公式及其否定統(tǒng)稱為文字。

例如，P(x)、Q(y)、P(x)、Q(y)等都是文字。1．子句和子句集子句：任何文字的析取式稱為子句。

例如，P(x)∨Q(y)，P(x,f(x))∨Q(x,g(x))都是子句?？兆泳洌翰话魏挝淖值淖泳浞Q為空子句。

由于空子句不含有任何文字，也就不能被任何解釋所滿足，因此空子句是永假的，不可滿足的?？兆泳湟话惚挥洖椤趸騈IL。子句集：由子句或空子句所構(gòu)成的集合稱為子句集。一.子句集及其化簡第六十二頁，共九十五頁，編輯于2023年，星期五2.子句集的化簡

在謂詞邏輯中，任何一個(gè)謂詞公式都可以通過應(yīng)用等價(jià)關(guān)系及推理規(guī)則化成相應(yīng)的子句集。其化簡步驟如下：（l）消去連接詞“→”和“←→”

反復(fù)使用如下等價(jià)公式：

P→Q<=>PVQ

P←→Q<=>(P→Q)∧(Q→P)<=>(P∧Q)V(P∧Q）

即可消去謂詞公式中的連接詞“→”和“←→”。

例如公式

(x)((y)P(x,y)→(y)(Q(x,y)→R(x,y)))

經(jīng)等價(jià)變化后為

(x)((y)P(x,y)V(y)(Q(x,y)VR(x,y)))（2）減少否定符號(hào)的轄域（即把否定符號(hào)移到緊靠謂詞的位置上）

反復(fù)使用雙重否定律(P)<==>P

狄·摩根定律（P∨Q）<==>P∧Q

（P∧Q）<==>P∨Q

量詞轉(zhuǎn)換律(x）P<==>（彐x）P，（彐x）P<==>（x）P將每個(gè)否定符號(hào)“

”移到僅靠謂詞的位置，使得每個(gè)否定符號(hào)最多只作用于一個(gè)謂詞上。

例如，上步所得公式經(jīng)本步變換后為

(x)((彐y)P(x,y)∨(彐y)(Q(x,y)∧R(x,y)))

第六十三頁，共九十五頁，編輯于2023年，星期五（3）對(duì)變?cè)獦?biāo)準(zhǔn)化

在一個(gè)量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變?cè)坑昧硗庖粋€(gè)沒有出現(xiàn)過的任意變?cè)?，使不同量詞約束的變?cè)胁煌拿帧?/p>

例如，上步所得公式經(jīng)本步變換后為

(x)((彐y)P(x,y)∨(彐z)(Q(x,z)∧R(x,z)))

（4）化為前束范式

化為前束范式的方法是把所有量詞都移到公式的左邊，并且在移動(dòng)時(shí)不能改變其相對(duì)順序。由于第（3）步已對(duì)變?cè)M(jìn)行了標(biāo)準(zhǔn)化，每個(gè)量詞都有自己的變?cè)@就消除了任何由變?cè)饹_突的可能，因此這種移動(dòng)是可行的。

例如，上步所得公式化為前束范式后為:(x)(彐y)(彐z)(P(x,y)∨(Q(x,z)∧R(x,z)))（5）消去存在量詞

消去存在量詞時(shí)，需要區(qū)分以下兩種情況。

若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個(gè)新的個(gè)體常量替換受該存在量詞約束的變?cè)?，就可消去該存在量詞。

若存在量詞位于一個(gè)或多個(gè)全稱量詞的轄域內(nèi)，例如

(x1)(x2)……(xn)(彐y)P(x1,x2,……,xn,y)則需要用Skolem函數(shù)y=f（x1,x2,……,xn）替換受該存在量詞約束的變?cè)缓笤傧ピ摯嬖诹吭~。第六十四頁，共九十五頁，編輯于2023年，星期五

例如，在上步所得公式中存在量詞（彐y)和（彐z）都位于（x）的轄域內(nèi)，因此都需要用Skolem函數(shù)來替換。設(shè)替換y和z的Skolem函數(shù)分別是f（x）和g（x），則替換后的公式為:

(x)(彐y)(彐z)(P(x,y)∨(Q(x,z)∧R(x,z)))

f(x)g(x)g(x)（6）化為Skolem標(biāo)準(zhǔn)形

Skolem標(biāo)準(zhǔn)形的一般形式為

(x1)(x2)……(xn)M(x1,x2,……,xn)其中，M（x1,x2,……,xn）是Skolem標(biāo)準(zhǔn)形的母式，它由子句的合取所構(gòu)成。把謂詞公式化為Skolem標(biāo)準(zhǔn)形需要使用以下等價(jià)關(guān)系

PV（Q∧R）<=>（PVQ）∧（PVR）例如，上步所得的公式化為Skolem標(biāo)準(zhǔn)形后為（x）((P(x,f(x))∨Q(x,g(x)))∧(P(x,f(x))∨R(x,g(x))))（7）消去全稱量詞由于母式中的全部變?cè)苋Q量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變?cè)潜蝗Q量詞量化的。例如，上步所得公式消去全稱量詞后為

(

(P(x,f(x))∨Q(x,g(x)))∧(P(x,f(x))∨R(x,g(x))))第六十五頁，共九十五頁，編輯于2023年，星期五（8）消去合取詞

在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個(gè)元素都是一個(gè)子句。例如，上步所得公式的子句集中包含以下兩個(gè)子句

P(x,f(x))∨Q(x,g(x))P(x,f(x))∨R(x,g(x))（9）更換變?cè)Q

對(duì)子句集中的某些變?cè)匦旅?，使任意兩個(gè)子句中不出現(xiàn)相同的變?cè)?。由于每一個(gè)子句都對(duì)應(yīng)著母式中的一個(gè)合取元，并且所有變?cè)际怯扇Q量詞量化的，因此任意兩個(gè)相同子句的變?cè)g實(shí)際上不存在任何關(guān)系。這樣，更換變?cè)遣粫?huì)影響公式的真值的。

例如，對(duì)上步所得公式，可把第二個(gè)子句集中的變?cè)鹸更換為y，得到如下子句集

P(x,f(x))∨Q(x,g(x))

P(y,f(y))∨R(y,g(y))第六十六頁，共九十五頁，編輯于2023年，星期五

通過上述化簡步驟，可以將謂詞公式化簡為一個(gè)標(biāo)準(zhǔn)子句集。由于在消去存在量詞時(shí)所用的Skolem函數(shù)可以不同，因此化簡后的標(biāo)準(zhǔn)子句集是不惟一的。當(dāng)原謂詞公式為非永假時(shí)，它與其標(biāo)準(zhǔn)子句集并不等價(jià)。當(dāng)原謂詞公式為永假（即不可滿足）時(shí)，其標(biāo)準(zhǔn)子句集則一定是永假的，即Skolem化并不影響原謂詞公式的永假性。3．子句集的應(yīng)用定理1:

設(shè)有謂詞公式F，其標(biāo)準(zhǔn)子句集為S，則F為不可滿足的充要條件是S為不可滿足的。

第六十七頁，共九十五頁，編輯于2023年，星期五二.海伯倫理論判定一個(gè)于句集是不可滿足的=判定該子句集中的子句都是不可滿足的?！芭卸ㄗ泳鋵?duì)任何非空個(gè)體域上的任意解釋都是不可滿足的”非常困難對(duì)一個(gè)具體的謂詞公式找到一個(gè)特殊的論域，使得該謂詞公式只要在這個(gè)特殊的論域上不可滿足，就能保證它在任何論域上不可滿足海伯倫域第六十八頁，共九十五頁，編輯于2023年，星期五1.海伯倫域設(shè)S為論域D上的一個(gè)子句集，則按下述方法構(gòu)造的域H∞稱為海伯倫域，簡記為H域。（l）令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則可任取一常量a∈D，并令

H0={a}(2)令Hi+1=Hi∪｛S中所有n元函數(shù)

f(x1,x2,……,xn)|xj是Hi中的元素｝，其中，

i=0,1,2,……;j=1,2,……,n。

第六十九頁，共九十五頁，編輯于2023年，星期五例1：求S=｛P（a），Q（x）∨R（f（x））｝的H域。

解：在此例中只有一個(gè)個(gè)體常量a，依H域的定義有

H0=｛a｝

H1=｛a｝∪｛f(a)｝=｛a,f(a)｝

H2=｛a，f(a)｝∪｛f(f(a))｝=｛a，f(a)，f(f(a))｝

……………

H∞=｛a，f(a)，f(f(a)),………｝

例2：求子句集S={R（c），P（f（y）），Q（g（x））｝的H域。

解：在此例中有一個(gè)個(gè)體常量c和兩個(gè)函數(shù)f(y)、g(x)，依H域的定義有

H0=｛c｝

H1=｛c，f（c），g（c）｝

H2=｛c，f(c)，g(c)，f（f(c)），f（g(c)），g（f(c)），g（g(c)）｝

…………H∞=｛c，f(c)，g(c)，f（f(c)），f（g(c)），g（f(c)），g（g(c)），……｝第七十頁，共九十五頁，編輯于2023年，星期五為研究子句集的不可滿足性，除引入個(gè)體域H外，還需要引入以下幾個(gè)概念：

如果用H域中的元素代替子句中的變?cè)?，則所得到的子句稱為基子句。例如，在例1中用H域中的元素a或f（a）代替子句Q（x）∨R（f（x））中的變?cè)?所得到的子句Q（a）∨R（f（a））就是基子句。

基子句中的謂詞稱為基原子。如上例中的Q（a）、R（f（a））就是基原子。

子句集中所有基原子構(gòu)成的集合稱為原子集。即集合

A=｛所有形如P（t1，t2，…，tn）的元素｝

稱為子句集S的原子集。其中，P（x1，x2，…，xn）是S中的任一謂詞；第七十一頁，共九十五頁，編輯于2023年，星期五

子句集S在H域上的解釋就是對(duì)S中出現(xiàn)的常量、函數(shù)及謂詞的取值，一次取值就構(gòu)成一個(gè)解釋。如果從原子集的角度來看，子句集S在H域上的解釋就是對(duì)S的原子集A中元素的取值。

定義：子句集S在H域上的一個(gè)解釋IH滿足如下條件：

（1）在解釋IH下，常量映射到自身；

（2）S中的任一n元函數(shù)是Hn→H的映射。其中，Hn是一個(gè)由屬于H的n個(gè)元素構(gòu)成的集合。即函數(shù)的自變量h1,h2,…,hn∈H，并且有函數(shù)值f(h1,h2,…,hn）∈H；

（3）S中的任一n元謂詞是Hn→{T,F}的映射。即謂詞的真值可以指派為T或F。2.H解釋第七十二頁，共九十五頁，編輯于2023年，星期五定理2：設(shè)I是S在D域上的解釋，則S存在著對(duì)應(yīng)于I的H解釋IH，使得若有S在解釋I下為真，必有S在解釋IH下也為真。

并且，由此定理還可以得到以下兩個(gè)定理。定理3：子句集S不可滿足的充要條件是S的一切H解釋都為假。

定理4：（Herbrand定理）子句集S不可滿足的充要條件是存在一個(gè)有限的不可滿足的基子句集S’。第七十三頁，共九十五頁，編輯于2023年，星期五三.魯賓遜歸結(jié)原理對(duì)于句集中的子句做逐次歸結(jié)，證明子句集的不可滿足性基本思想首先把欲證明問題的結(jié)論否定，并加入子句集，得到一個(gè)擴(kuò)充的子句集S’。然后設(shè)法檢驗(yàn)子句集S’是否含有空子句，若含有空子句，則表明S’是不可滿足的；若不含有空子句，則繼續(xù)使用歸結(jié)法，在子句集中選擇合適的子句進(jìn)行歸結(jié)，直至導(dǎo)出空子句或不能繼續(xù)歸結(jié)為止。第七十四頁，共九十五頁，編輯于2023年，星期五1.有關(guān)概念與定理若P是原子謂詞公式，則稱P與P為互補(bǔ)文字。設(shè)C1和C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個(gè)新的子句C12。，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。例3.設(shè)C1=P∨Q，C2=Q，C3=P，求C1、C2、C3的歸結(jié)式C123。解：先對(duì)C1、C2歸結(jié)，可得C12=P

然后再對(duì)C12和C3歸結(jié)，得到C123=NIL第七十五頁，共九十五頁，編輯于2023年，星期五P∨QQPPNIL歸結(jié)過程的樹形表示第七十六頁，共九十五頁，編輯于2023年，星期五定理5:歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。推論1：設(shè)C1和C2是子句集S中的兩個(gè)子句，C12是C1和C2的歸結(jié)式，若用C12代替C1和C2后得到新的子句集S1，則由S1的不可滿足性可以推出原子句集S的不可滿足性。推論2：設(shè)C1和C2是子句集S中的兩個(gè)子句，C12是C1和C2的歸結(jié)式，若把C12加入S中得到新的子句集S2，則S與S2的不可滿足性是等價(jià)的。為證明子句集S的不可滿足性，只要對(duì)其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入到子句集S中，或者用歸結(jié)式代替他的親本子句，然后對(duì)新的子句集證明其不可滿足性就可以了。如果經(jīng)歸結(jié)能得到空子句，根據(jù)空子句的不可滿足性，即可得到原子句集S是不可滿足的結(jié)論。第七十七頁，共九十五頁，編輯于2023年，星期五應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。在命題邏輯中，對(duì)不可滿足的子句集S，其歸結(jié)原理是完備的。這種完備性可用如下定理描述:

定理6：子句集S是不可滿足的，當(dāng)且僅當(dāng)存在一個(gè)從S到空子句的歸結(jié)過程。

已知F，證明G為真的歸結(jié)反演過程如下：①否定目標(biāo)公式G，得￢G；②把￢G并入到公式集F中，得到｛F，￢G｝③把｛F，￢G｝化為子句集S；④應(yīng)用歸結(jié)原理對(duì)子句集S中的子句進(jìn)行歸結(jié)，并把次得到的歸結(jié)式并入S中。如此反復(fù)進(jìn)行，若出現(xiàn)空子句，則停止歸結(jié)，證明G為真2.命題邏輯的歸結(jié)反演第七十八頁，共九十五頁，編輯于2023年，星期五

例4：設(shè)已知的公式集為

｛P，（P∧Q）→R，（S∨T）→Q，T｝，求證結(jié)論R。

解：假設(shè)結(jié)論R為假，即￢R為真，將￢R加入公式集，并化為子句集

S=｛P，￢P∨￢Q∨R，￢S∨Q，￢

T∨Q，T，￢R

｝

其歸結(jié)過程如右圖的歸結(jié)演繹樹所示。在該樹中，由于根部出現(xiàn)空子句，因此命題R得到證明。

這個(gè)歸結(jié)證明過程的含義為：開始時(shí)假設(shè)子句集S中的所有子句均為真，即原公式集為真，￢R也為真；然后利用歸結(jié)原理，對(duì)子句集中含有互補(bǔ)文字的子句進(jìn)行歸結(jié)，并把所得的歸結(jié)式并入子句集中；重復(fù)這一過程，最后歸結(jié)出了空子句。根據(jù)歸結(jié)原理的完備性，可知子句集S是不可滿足的，即開始時(shí)假設(shè)的￢R為真是錯(cuò)誤的，這就證明了R為真。

￢P∨￢Q∨R￢R￢P∨￢QP￢Q￢T∨Q￢TTNIL一個(gè)命題邏輯的歸結(jié)演繹樹無用第七十九頁，共九十五頁，編輯于2023年，星期五3.謂詞邏輯的歸結(jié)反演C1和C2是兩個(gè)沒有公共變?cè)淖泳?，L1和L2分別是C1和C2中的文字。如果L1和￢L2存在最一般合一σ，則稱

C12=（C1σ－｛L1σ｝）∪（C2σ－｛L2σ｝）

為C1和C2的二元?dú)w結(jié)式，而L1和L2為歸結(jié)式上的文字。例5.設(shè)C1=P（a）∨R（x），C2=￢P（y）∨Q（b），求C12。

解：取L1=P（a），L2=￢P（y），則L1和￢L2的最一般合一是σ=（a／y），可得

C12=（C1σ－｛L1σ｝）∪（C2σ－｛L2σ｝）=（｛P(a)，R(x)｝-｛P(a)｝）∪（｛￢P(a)，Q(b)｝-｛￢P(a)=｛R(x)｝∪｛Q(b)｝=｛R(x)，Q(b)｝=R(x)∨Q(b)

第八十頁，共九十五頁，編輯于2023年，星期五

在這個(gè)例子中，把C1σ稱為C1的因子。一般來說，若子句C中有兩個(gè)或兩個(gè)以上的文字具有最一般合一σ，則稱Cσ為子句C的因子。如果Cσ是一個(gè)單文字，則稱它為C的單元因子。應(yīng)用因子概念，可對(duì)謂詞邏輯中的歸結(jié)原理給出如下定義。

定義：若C1和C2是無公共變?cè)淖泳?，則

①C1和C2的二元?dú)w結(jié)式；

②C1和C2的因子C2σ2的二元?dú)w結(jié)式；

③C1的因子C1σ1和C2的二元?dú)w結(jié)式；

④C1的因子C1σ1和C2的因子C2σ2

的二元?dú)w結(jié)式。

這四種二元?dú)w結(jié)式都是子句C1和C2的二元?dú)w結(jié)式，記為C12例6：設(shè)C1=P(y)∨P(f(x))∨Q(g(x))，C2=￢

P(f(g(a)))∨Q(b)，求C12。

解：對(duì)C1，取最一般合一σ=（f（x）／y｝，得C1的因子

C1σ=P(f(x))∨Q(g(x))

對(duì)C1的因子和C2歸結(jié)，可得到C1和C2的二元?dú)w結(jié)式

C12＝Q（g（g（a））∨Q（b）

對(duì)謂詞邏輯，前述定理仍然適用，即歸結(jié)式C12是其親本子句C1和C2的邏輯結(jié)論。用歸結(jié)式取代它在子句集S中的親本子句，所得到的子句集仍然保持著原子句集S的不可滿足性。

此外，對(duì)謂詞邏輯定理6也仍然適用，即從不可滿足的意義上說，一階謂詞邏輯的歸結(jié)原理也是完備的。第八十一頁，共九十五頁，編輯于2023年，星期五謂詞邏輯的歸結(jié)反演過程謂詞邏輯的歸結(jié)反演過程與命題邏輯的歸結(jié)反演過程相比，其步驟基本相同，但處理對(duì)象有所不同。在化簡子句集時(shí)，謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集；在按歸結(jié)原理進(jìn)行歸結(jié)時(shí)，謂詞邏輯的歸結(jié)原理需要考慮兩個(gè)親本子句的最一般合一。第八十二頁，共九十五頁，編輯于2023年，星期五例7已知

F：(x)((彐y)(A(x,y)∧B(y))→(彐y)(C(y)∧D(x,y)))G：￢(彐x)C(x)→(x)(y)(A(x,y)→￢

B(y))

求證：G是F的邏輯結(jié)論。

證明：先把G否定，并放入F中，得到的｛F，￢

G｝為:{(x)((彐y)(A(x,y)∧B(y))→(彐y)(C(y)∧D(x,y))),

￢(￢(彐x)C(x)→(x)(y)(A(x,y)→￢

B(y)))}再把｛F，￢

G｝化成于句集，得到

（1）￢

A（x，y）∨￢

B（y）∨C（f（x））

（2）￢A（u，v）∨￢B（v）∨D（u，f（u））

（3）￢C（z）

（4）A（m，n）

（5）B（k）

其中(1)、(2)是由F化出的2個(gè)子句，(3)、(4)、(5)是由￢G化出的3個(gè)子句。

最后應(yīng)用謂詞邏輯的歸結(jié)原理，對(duì)上述子句集進(jìn)行歸結(jié)，其過程為

（6）￢A（x，y）∨￢

B（y）由（1）和（3）歸結(jié)，取σ=｛f（x）／z｝

（7）￢B（n）由（4）和（6）歸結(jié)，取σ=｛m／x，n／y｝

（8）

NIL

由（5）和（7）歸結(jié)，取σ=｛k／n｝因此G是F的邏輯結(jié)論。上述歸結(jié)過程可用下圖所示的歸結(jié)樹來表示。第八十三頁，共九十五頁，編輯于2023年，星期五￢A(x,y)∨￢B(y)￢A(x,y)∨￢B(y)∨C(f(x))￢C(z){f(x)/z}A(m,n)￢B(n){m/x,n/y}B(k)NILk/n

例7