第三章謂詞邏輯與確定性推理謂詞邏輯指基于數(shù)理邏輯的表示、推理方法，一階謂詞邏輯是經(jīng)典的命題邏輯。由于其表示的多為確定性知識，也多用于確定性推理。一階謂詞邏輯推理基礎(chǔ)歸結(jié)原理自然演義推理歸結(jié)演義推理定義1：一個陳述句稱為一個斷言。有真假意義的斷言稱為命題。命題的意義（真假）結(jié)果稱為真值，為真時記為T，

為假時記為F。

例如：王立是大學(xué)生；上海是全國最大的城市。再如：當(dāng)x=6，y=5時，命題：x大于y結(jié)果為T，

命題：x小于y結(jié)果為F。

反例：今天好冷！幾度呀？都不是命題。

§3-1謂詞邏輯基本概念1.命題的真值§3-1謂詞邏輯基本概念2.論域和謂詞定義2：論域是問題涉及對象的全體構(gòu)成的非空集合。集合中的元素稱為個體，因此，論域也稱為個體域。

謂詞邏輯：命題是用謂詞來表示的，由兩個部分構(gòu)成即：一個謂詞=謂詞名（個體）。其中，個體是命題的主語，表示獨立的事務(wù)或抽象的概念。謂詞名是謂語，表達個體的狀態(tài)、性質(zhì)或個體間的關(guān)系。定義3：設(shè)D是個體域，P：Dn

{T，F(xiàn)}是一個映射，其中

Dn={（x1,x2,…,xn）|x1,x2,…,xn∈D}

則稱P是一個n元謂詞（n=1，2，…),

記為P（x1，x2，…，xn）。

其中，x1,x2,…,xn為個體變元。

個體可以是常量、變量或函數(shù)。例如：GREATER（x，6）

表示x>6

TEACHER（father（A））

表示的父親是教師。其中，

father（A）

是函數(shù)，小寫。一般形式為

f(x1，x2…xn)

，其值在個體域中。§3-1謂詞邏輯基本概念§3-1謂詞邏輯基本概念3.連接詞和量詞（1）連接詞：是連接簡單命題，構(gòu)成復(fù)合命題的邏輯運算符號。～：否定、對命題“非”。

∨：析取，對命題取“或”

∧：和取，對命題取“與”

→：條件，蘊涵，表示“如果…則…”

?：雙條件，表示“當(dāng)且僅當(dāng)”。表2-1謂詞邏輯表PQ～PP∨QP∧QP→QP?QTTFTTTTTFFTFFFFTTTFTFFFTFFTT（2）量詞：用于對謂詞中的個體約束或規(guī)定。分為全稱量詞?和存在量詞?

。

?x：表示論域中所有的x。

?x：表示論域中存在x。

命題（?x

）P（x）為真：當(dāng)且僅當(dāng)對于論域中的所有x

，都有P（x）為真；只要有一個x0∈D，使得P（x）為假，那么（?x

）P（x）就為假。命題（?x

）P（x）為真：只要有一個x0∈D，使得P（x）為真；當(dāng)且僅當(dāng)對于論域中的所有x

，都有P（x）為假，那么（?x

）P（x）就為假?！?-1謂詞邏輯基本概念定義3.項的規(guī)則

1）單獨一個個體詞是項：t1，t2，t3，…tn

。

2）若t1，t2，t3，…tn

是項，則函數(shù)f(t1，t2，t3，…tn

)也是項。

3）由1）和2）生成的表達式也是項。定義4.原子謂詞公式

若t1，t2，t3，…tn

是項，P是謂詞符號，則P(t1，t2，t3，…tn

)稱為原子謂詞公式。

§3-1謂詞邏輯基本概念4.項與合式公式定義5.合式公式（謂詞公式）

1）原子謂詞公式稱為合式公式；

2）由～∧∨→?連接的合式公式還是合式公式；

3）由??約束的合式公式也稱為合式公式。定義6.自由變元與約束變元

?、?是有轄區(qū)的，受??約束的變元稱為約束變元。不受它們的約束的變元稱為自由變元。

(1)（?x）P（x），x為約束變元

(2)（?x）（H（x）→G（x，y）），y為自由變元

(3)（?x）A(x)∧B(x)，

只約束A(x)，而B（x）中的x仍為自由變元。§3-1謂詞邏輯基本概念謂詞邏輯可以表示事物的狀態(tài)、性質(zhì)、概念，也可以表示事物之間的因果關(guān)系，即規(guī)則。對于事實的知識用～∧∨連接的謂詞公式表示。對于事物的因果關(guān)系通常用蘊含→式表示。

x→y表示“如果x,則y”

使用謂詞邏輯進行知識表示時，一般先根據(jù)題意定義謂詞，然后在根據(jù)表達的需要使用適當(dāng)?shù)倪B詞和量詞把謂詞連接起來構(gòu)成謂詞公式。§3-2謂詞邏輯的問題表示1.謂詞邏輯表示例3.1所有的學(xué)生都有某教材。

STUDENT(x):表示x是學(xué)生

HASMATERIAL(x,y)：表示x有教材y

題目所表達的知識可以表示為：

(?x)(?y)(STUDENT(x)→HASMATERIAL(x,y))例3.2所有整數(shù)不是偶數(shù)就是奇數(shù)。

I(x):表示x是整數(shù)

E(x)：表示x是偶數(shù)

O(x)：表示x是奇數(shù)題目所表達的知識可以表示為：

(?x)(I(x)→E(x)∨O(x))§3-2謂詞邏輯的問題表示如果對邏輯的某些外延擴展后，則可把大部分的知識表達成一階謂詞邏輯的形式。例如：王是計算機系的學(xué)生，李明是王的同班同學(xué)，他們系系的學(xué)生都喜歡編程。定義謂詞：

COMPUTRE（x）：x是計算機系的學(xué)生

CLASSMATE（x，y）：x是y的同班同學(xué)

LIKE（x，y）：x喜歡y。題目的

知識表示：

COMPUTRE（wang）

CLASSMATE（liming，wang）

(?x)(COMPUTRE（x）→LIKE(x，programming))2.謂詞邏輯應(yīng)用§3-2謂詞邏輯的問題表示例3.3機器人要把a處桌子上的箱子搬到b處的桌子上，再回到c處。謂詞：TABLE（x）：x是桌子

EMPTY（y）：y手中是空的

AT（y，z）：y在z位置附近

HOLD（y，w）：y拿著wON（w，x）：w在桌子x上其中x∈{a,b}，y∈{robot}，

z∈{a,b,c},w∈{box}abc§3-2謂詞邏輯的問題表示圖3-1盒子移動場景

增加動作謂詞：

1）

Goto（x，y）：從x走到y(tǒng)2）Pickup（x）：在x處拿起盒子

3）Setdown

（x）：在x處放下盒子分別對應(yīng)的條件：

1）AT（Robot，x）

2)ON（box，x），TABLE(x），AT(Robot，x），EMPTY(Robot)3)AT（Robot，x）），TABLE（x），HOLD（Robot，x）abc§3-2謂詞邏輯的問題表示AT（Robot，c）EMPTY（Robot）ON（box，a）TABLE（a）TABLE（b）AT（Robot，c）EMPTY（Robot）ON（box，b）TABLE（a）TABLE（b）AT（Robot，a）EMPTY（Robot）ON（box，a）TABLE（a）TABLE（b）AT（Robot，a）HOLD（Robot，box)TABLE（a）TABLE（b）AT（Robot，b）HOLD（Robot，box)TABLE（a）TABLE（b）AT（Robot，b）EMPTY（Robot）ON（box，b）TABLE（a）TABLE（b）Goto(x，y)Pickup(x)Goto(x，y)Setdown(x)Goto(x，y)§3-2謂詞邏輯的問題表示表達知識形式化能夠自然、明確、精確。一階謂詞邏輯具有完備的邏輯推理算法。不能表達不精確的、模糊的知識。形成知識庫較困難，當(dāng)知識系統(tǒng)較大時，存在組合爆炸的問題、推理的效率底。

3.謂詞邏輯表示的特點§3-2謂詞邏輯的問題表示（1）推理：由事實出發(fā)推出結(jié)論的過程（2）推理從邏輯基礎(chǔ)出發(fā)分：演義推理和歸納推理演義推理：有一般到特殊，核心是三段論。歸納推理：由特殊到一般：枚舉、統(tǒng)計、類比。（3）按所用的事實：確定性推理和非確定性推理。（4）按結(jié)論的出現(xiàn)情況：單調(diào)性推理和非單調(diào)推理。（5）按控制策略：正向推理、逆向推理與混合推理。（6）按使用知識策略：啟發(fā)式推理和非啟發(fā)式推理?！?-3推理基礎(chǔ)定義7.設(shè)P為謂詞公式，D為其個體域，若對P中的謂詞、個體常量、函數(shù)按如下定義賦值：

（1）為每個個體指派D中的一個元素（2）為每個n元函數(shù)指派一個從Dn個到D中的映射其中：Dn={（x1,x2,…xn）|x1,x2,x3,…∈D}

（3）為每個n謂詞指派一個從Dn

到{T,F}的映射則稱這些指派為P在D上的一個解釋?！?-3推理基礎(chǔ)1.謂詞公式的解釋對謂詞公式中的個體變項、函數(shù)變項、謂詞變項用指定的常項去替代，所得到的結(jié)果稱為對謂詞公式的一個解釋或賦值。

在有限個體域下，可按下列規(guī)則消去量詞。如§3-3推理基礎(chǔ)§3-3推理基礎(chǔ)

af(1)f(2)112例3.4設(shè)個體域D={1，2}，求謂詞公式B=(?x)P(f(x)，a)在D上的解釋，并給出該解釋下B的真值。解：設(shè)個體常量a和函數(shù)f（x）的真值指派為:對謂詞的真值指派為:P(1,1)P(1,2)P(2,1)P(2,2)TxTx

B=(?x)P（f(x)，a）=P(f(1),a)∧P(f(2),a)=P(1,1)∧P(2,1)=T

定義8.設(shè)P為謂詞公式，對于非空個體域D上的任何解釋都取得真值T，則稱P在D上永真。如果P在任何非空個體域上均為T，則稱P永真。定義9.設(shè)P為謂詞公式，如果至少存在D上的一個解釋，使得P在該解釋下取真值T，則稱公式P在D上是可滿足的。定義10.設(shè)P為謂詞公式，對于非空個體域D上的任何解釋都取得真值F，則稱P在D上永假。如果P在任何非空個體域上均為F，則稱P永假。也稱為不可滿足性或不相容性?！?-3推理基礎(chǔ)2.謂詞公式的永真與可滿足性1）等價關(guān)系設(shè)P和

Q為D上的兩個謂詞公式，對于D上的任何解釋P和Q都有相同的真值

，則稱P和Q在D上等價。如果對于D是任意的個體域，則稱P和Q等價。

常用的等價式（公理）否定之否定：～(～P)<=>P

交換率：P∨Q<=>Q∨P；P∧Q<=>Q∧P

結(jié)合率：（P∨Q）∨R<=>P∨（Q∨R）；（P∧Q）∧R<=>P∧（Q∧R）3.謂詞公式的等價與永真蘊含(命題邏輯回顧)§3-3推理基礎(chǔ)分配率：P∨（Q∧R）<=>（P∨Q）∧（P∨R）；

P∧（Q∨R）<=>（P∧Q）∨（P∧R）摩根定理：～（

P∨Q）<=>～P∧～

Q；

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

Q

補余率：～P∨P<=>T(永真)；～P∧P<=>F(永假)連詞歸化：（

P→Q）<=>～P∨Q

（P?Q）<=>（P→Q）∧（Q→P）；（P?Q）<=>（P∧Q）∨（～P∧～

Q）量詞轉(zhuǎn)換：～（?x）P（x）<=>（?x）～

P（x）；

～（?x）P（x）<=>（?x）～

P（x）量詞分配：（?x）（P∧Q）<=>（?x）P∧（?x）Q；（?x）（P∨Q）<=>（?x）P∨（?x）Q§3-3推理基礎(chǔ)

2）永真蘊含式定義11.設(shè)對于謂詞公式P和

Q，如果P→Q為永真，則稱P永真蘊含

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

。常用的永真蘊含式：化簡式：P∧Q=>P；P∧Q=>Q

附加式：P=>P∨Q；Q=>P∨Q

析取三段論：～P，P∨Q=>Q

假言推理：P，P→Q=>Q

拒取式：～Q，P→Q=>～P

假言三段論：P→Q，Q→R=>P→R

二難推理：P∨Q，P→R，Q→R=>R

全稱固化：（?x）P（x）=>P（y）

存在固化：（?x）P（x）=>P（c）PQ～PP∨QP∧QP→QP?QTTFTTTTTFFTFFFFTTTFTFFFTFFTTP∧QPQP∨Q=>QP→QP→Q=>QTTT

TTFTF

FTFFTTFFFT析取三段論：～P，P∨Q=>Q假言推理：P，P→Q=>Q3)變元替換一般替換：新變元、轄區(qū)不便；1.全稱固化：（?x）P（x）=>P（y）：y是個體域中的任一個體，用此永真可以消去謂詞中的全稱量詞(US規(guī)則)。（?x）P（x）=>P（c）2.存在固化：（?x）P（x）=>P（c）：c是個體域中使p(x)為真的個體。用于消去存在量詞(ES規(guī)則)

。3.全稱推廣規(guī)則：P（x）=>（?y）P（y）：由此引起的其他位置上的x也是不自由的(UG規(guī)則)

。4.存在量詞附加規(guī)則(EG規(guī)則)P（c）=>?(x）P（x）一般：abcde表示個體常量，tuvwxyz表示變量例8，證明證明：

⑴P

⑵T⑴ES

⑶P⑷T⑶US

⑸T⑵⑷假言推理

⑹T⑸化簡

⑺T⑵⑹合取

⑻T⑺EG由已知事實出發(fā)，根據(jù)經(jīng)典的邏輯推理規(guī)則推出結(jié)論的過程稱為演繹推理。最基本的推理規(guī)則是三段論：假言推理、拒取式推理、假言三段論。在假言推理P，P→Q=>Q中，說明當(dāng)P→Q為真，前件為真，則Q為真。例3.7已知:A，B，A→C，B∧C→D，D→Q

求證:Q=T（為真）

證明：A，A→C=>CB，C=>B∧C引入合取詞

B∧C，B∧C→D=>DD，D→Q=>Q得證#4自然演繹推理拒：～Q，P→Q=>～P三：P→Q，Q→R=>P→R

例3.9已知事實:凡是編程課，王程都喜歡；所有程序設(shè)計語言課都是需要編程的課；C語言課是一門程序設(shè)計語言課求證:王程喜歡C語言課

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

Like(x,y)x喜歡yLang(x)x是一門程序設(shè)計語言課事實描述：Prog(x)→Like(Wangch,x)(?x)（Lang(x)→Prog(x))Lang(C)推理：Lang(y)→Prog(y)全稱固化

Lang(C)，Lang(y)→Prog(y)=>Prog(C)C需要編程

Prog(C)，Prog(C)→Like(Wangch,C)=>Like(Wangch,C)4自然演繹推理歸結(jié)演繹推理是基于一種稱為歸結(jié)原理(亦稱消解原理principleofresolution)的推理規(guī)則進行推理的方法。是由魯濱遜(J.A.Robinson)于1965年在海伯倫（Herbrand）理論上建立首先提出。它是謂詞邏輯中一個相當(dāng)有效的機械化推理方法。被認為是自動推理，特別是定理機器證明領(lǐng)域的重大突破?；舅枷耄焊鶕?jù)前提P和結(jié)論Q，要證明P→Q永真，對謂詞邏輯來講就要證明其在任何一個非空的個體域上永真。要證明P→Q永真，只要證明P

∧～

Q不可滿。連詞歸化：（P→Q）<=>～P∨Q

摩根定理：～（～P∨Q）<=>P

∧～

Q§3-4歸結(jié)演繹推理

范式是是公式的標(biāo)準(zhǔn)形式，公式要轉(zhuǎn)換為等價的范式，方便一般性的處理。根據(jù)量詞的情況分為兩種：前束范式和Skolem范式。

1）前束范式定義12.設(shè)M是謂詞公式，如果其中所有的量詞均非否定地約束整個公式，則稱P為前束范式。一般地寫成：（Q1）（…）（Qn

）M（x1

，x2

，…，xn

）

其中：Qi

（i=1，2…n）為前綴，

M（x1

，x2

，…，xn

）為母式。1.謂詞公式的范式§3-4歸結(jié)演繹推理例如：

(?x)(?y)(?z)[P（x）∧Q（y，z）∨R（x，z）]2）Skolem

范式在前束范式中，如果所有的存在量詞都在全稱量詞之前，則稱該謂詞公式為Skolem

范式。例如：

(?

x)(?

y)(?z)[P（x）∨Q（y，z）∧R（x，z）]

可以證明：任何謂詞公式均可化為Skolem

范式§3-4歸結(jié)演繹推理推理過程中，在不同謂詞公式可能出現(xiàn)謂詞名相同，個體不同的情況，需要對個體變元使用置換（Substitution）進行替換，如果置換的結(jié)果使謂詞形式一致，這個過程叫做合一（Unify）。

例如：使用假言推理和全稱固化，由

W1(y)和

(?x)[W1(x)→

W2(x)]

推出W2(y)

這里需要找到項y對變元x的置換,即用y替換x。2.置換與合一§3-4歸結(jié)演繹推理

1）置換在謂詞公式中變元替換的形式{t1/x1，t2/x2，…，tn/xn}。

其中，{t1，t2，…，tn}為項，

{x1，x2，…，xn}是不相同的變元。

ti/xi表示用ti替換xi

。

ti，xi不能相同，xi不能循環(huán)出現(xiàn)在ti中。例如：{a/x，c/y，f(b)/x}是一個置換。而在{g(y)/x，f(x)/y}中，

x與y循環(huán)出現(xiàn)，則不能正確置換。§3-4歸結(jié)演繹推理例3.5一個謂詞公式及其個體如下：P(x，f(y)，B)，分別使用置換θ1={z/x，w/y}，θ2={q(z)/x，A/y}進行變元替換。

θ1的置換結(jié)果：P(z，f(w)，B）；

θ2的置換結(jié)果：P(q(z)，f(A)，B）.

定義13.設(shè)θ={t1/x1，t2/x2，…，tn/xn}是一個置換，F(xiàn)是一個謂詞公式，用ti替換xi

后的新公式為G，則稱G是公式F在θ置換下的例示，也是公式F的一個邏輯結(jié)論。記作：G=Fθ

§3-4歸結(jié)演繹推理定義14.設(shè)θ={t1/x1，t2/x2，…，tn/xn}和

λ={u1/y1，u2/y2，…，um/ym}是兩個不同的置換，則θ與λ合成也是一個置換，記為θ·λ，可以是先用θ置換再用λ置換。也可以按照下面的方法進行置換。從集合{t1λ

/x1，t2λ

/x2，…，tn

λ

/xn

，u1/y1，u2/y2，…，um/ym}中刪除兩種元素：（1）當(dāng)ti

λ=xi時刪去ti

λ/xi（i=1,2，…,n）（2）當(dāng)yi

∈{x1，x2，…，xn

}時，刪去uj/yj

（j=1,2，…,m）§3-4歸結(jié)演繹推理例3.6θ={f(y)/x，z/y}，λ={a/x，b/y，y/z}

α=θ·λ={t1λ

/x1，t2λ

/x2，…，tn

λ

/xn

，u1/y1，u2/y2，…，um/ym}={f(b/y)/x，(y/z)/y,a/x，b/y，y/z}={f(b)/x，y/y,a/x，b/y，y/z}={f(b)/x，y/z}（1）這種情況無意義，要刪去（2）這種情況前面已經(jīng)替換，也要刪去。在θ中y也已被替換過?！?-4歸結(jié)演繹推理

2）合一

定義15.設(shè)有公式集F={P1，P2

，…，Pn}，若存在一個置換θ使得P1θ

=P2θ=…=Pn

θ

，則稱θ是F的一個合一，稱P1，

P2，

…Pn

是可合一的。例如，對于公式集

F={P1，P2}={P（x，y，f（y)），P（a，g(x)，z）}

θ={a/x，g(a)/y，f(g(a))/z}

就是F的一個合一?！?-4歸結(jié)演繹推理定義16.設(shè)α是公式集F的一個合一，對于F的任何一個合一θ，都存在一個置換λ

使得θ

=α·λ

，則稱α

是F的最一般合一（MostGeneralUnifier）。一般，一個公式集的合一不一定是唯一的，但一個公式集的最一般合一是唯一的。

使用最一般的合一去置換可合一的謂詞公式集，可使它們的項變成完全一致?！?-4歸結(jié)演繹推理3）合一算法例如：F={P(x，y，z)），P（x，f(a)，h(b)}.

這里P1=P(x，y，z)

，P2=P（x，f(a)，h(b)）求最一般合一，先求分歧集（DisagreementSet）開始，從左至右分別比較P1，P2的符合，直到發(fā)現(xiàn)第一個不同之處，構(gòu)成一個分歧集D1={y，f(a)},于是產(chǎn)生一個置換σ1={y/f(a)}

變量替換后F1=F0·σ1

下一個分歧集是D2={z，h(b)}。于是又產(chǎn)生一個置換

σ2=σ1·{z/h(b)}

再變量替換后F2=F1·σ2……

最后所求得的σ

即為最一般合一。§3-4歸結(jié)演繹推理定理3.1：設(shè)有謂詞公式F，其標(biāo)準(zhǔn)子句集為S，F(xiàn)為不可滿足（永假）的充要條件是，S為不可滿足的。要證明一個子句集是不可滿足的，就要證明其中的每一個子句在任何個體論域上，都為不可滿足。

Herbrand理論：Herbrand構(gòu)造了一個特殊的論域，并證明了只要對子句在這個特殊域上的解釋進行判定，就可知子句集是否為不可滿足的。這個特殊的論域稱為Herbrand域（H）。

定理3.2:子句集S為不可滿足的充要條件是S的一切H解釋都為假。定理3.3：子句集S為不可滿足的充要條件是存在一個有限的不可滿足的基子句集S’。3.Herbrand理論§3-4歸結(jié)演繹推理定義15.原子謂詞公式及其否定稱為文字，任何文字的一個析取式稱為一個子句，不含任何文字的子句稱為空子句，記為或NIL。由子句或空子句構(gòu)成的集合稱為子句集。例：P(x)，～P(x)，Q(x,y)，～Q(x,y)都是文字；其中P(x)，～P(x)為互補文字。

P(x)∨Q(x,y)，P(x，f(x))∨Q(x,g(y))都是子句。一個謂詞公式可以通過等價關(guān)系與推理規(guī)則化簡為子句的集合?；喓笞泳浼戏Q為原來謂詞公式的子句集。當(dāng)謂詞公式為永假時，其子句集一定是永假的，而當(dāng)謂詞公式為非永假時，沒有這種關(guān)系。這是歸結(jié)原理的主要依據(jù)。4.子句和子句集

§3-4歸結(jié)演繹推理消去蘊含連接詞：→

或?縮小否定詞的轄區(qū)標(biāo)準(zhǔn)化變元化為前束范式消去存在量詞化為Skolem

標(biāo)準(zhǔn)式消去所有全稱量詞消去合取詞∧適當(dāng)更換變元名5.子句集化簡步驟§3-4歸結(jié)演繹推理消去蘊含連接詞：→

或?

反復(fù)使用：

P→Q<=>～P∨QP?Q<=>（

P∧Q）∨（～P∧～

Q）

例：(?x)（(?y)P（x，y）→～(?y)（Q(x，y）→R(x，y))

）

``````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````````<=>(?x)（～(?y)P（x，y）∨～(?y)（～Q(x，y）∨R(x，y))）縮小否定詞的轄區(qū)，使～靠近單個謂詞名§3-4歸結(jié)演繹推理縮小否定詞的轄區(qū)，使～靠近單個謂詞名使用雙重否定：～（～P）<=>P

摩根定理：～（P∨Q）<=>～P∧～Q；～（P∧Q）<=>～P∨～Q

量詞轉(zhuǎn)換：～（?x）P（x）<=>（?x）～P（x）；～（?x）P（x）<=>（?x）～P（x）由(?x)(～(?y)P（x，y）∨～(?y)（～Q(x，y)∨R(x，y))

）<=>(?x)((?y)～

P（x，y）∨(?y)（Q(x，y)∧～R(x，y))

）§3-4歸結(jié)演繹推理

(?x)((?y)～

P（x，y）∨(?y)（Q(x，y)∧～R(x，y)))標(biāo)準(zhǔn)化變元：變量換名使不同量詞與被約束的變元一致。

(?x)((?y)～

P（x，y）∨(?z)（Q(x，z)∧～R(x，z)))化為前束范式:前移所有量詞

(?x)(?y)(?z)（～

P（x，y）∨（Q(x，z)∧～R(x，z)))消去存在量詞:分兩種情況：

a.若該存在量詞在所有全稱量詞之前，則用一個常量符號代替該存在量詞轄域中的相應(yīng)約束變元，這樣的常量符號稱為Skolem常量§3-4歸結(jié)演繹推理

b.若該存在量詞在某些全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個函數(shù)代替該存在量詞轄域中的相應(yīng)約束變元，這樣的函數(shù)稱為Skolem函數(shù)。(?x)(?y)(?z)（～

P（x，y）∨（Q(x，z)∧～R(x，z)))

由于(?y)(?z)都處于(?x）約束之內(nèi)，都需要用Skolem函數(shù)來替換，分別為：f(x)和g(x)。(?x）（～

P（x，f(x)）∨（Q(x，g(x))∧～R(x，g(x))§3-4歸結(jié)演繹推理(?x）（～

P（x，f(x)）∨（Q(x，g(x))∧～R(x，g(x))化為Skolem

標(biāo)準(zhǔn)式：全稱約束的子句合取范式?？梢允褂茫篜∨（Q∧R）<=>（P∨Q）∧（P∨Q）(?x)((～

P(x，f(x))∨Q(x，g(x)))∧(～

P（x，f(x)）∨～

R(x，g(x))))消取全稱量詞，剩余的母式默認為被全稱量詞量化。(～

P(x，f(x))∨Q(x，g(x)))∧(～

P（x，f(x)）∨～

R(x，g(x)))§3-4歸結(jié)演繹推理消去合取詞∧，得到子句集，其中的每一個元素都是子句?？梢缘玫絻蓚€子句：～

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

～

P（x，f(x)）∨～

R(x，g(x))更換變元，使子句之間沒有重復(fù)變量，因為所有變元都被全稱量化，子句之間不存在相互依賴關(guān)系?！?/p>

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

～

P（y，f(y)）∨～

R(y，g(y))§3-4歸結(jié)演繹推理由謂詞公式轉(zhuǎn)化子句集可知子句之間存在合取關(guān)系。只要證明其中的一個子句不可滿足，則整個子句集就是不可滿足。更為明確的是如果子句集中包含空子句，則此子句集一定是不可滿足的。歸結(jié)過程的思路：先把求證的問題否定，證明其是不可滿足的。證明過程是逐步擴充子句，并設(shè)法檢驗子句集中是否含有空子句。若不含空子句，則繼續(xù)歸約，直至找到空子句或不能繼續(xù)歸約。6.Robinson歸結(jié)原理§3-4歸結(jié)演繹推理1）命題邏輯的歸結(jié)定義3.16設(shè)C1、C2是命題邏輯中的兩個子句，C1中有文字L1，C2中有文字L2，且L1與L2互補，可以從C1、C2中分別刪除L1，L2，再將剩余部分析取起來，構(gòu)成的新子句為C12，稱C12為C1、C2的歸結(jié)式(或消解式)，C1、C2稱為其歸結(jié)式的親本子句，L1、L2稱為消解基。這一過程為歸結(jié)。

例3.9C1=～P∨Q，C2=～Q，

C3=P，求歸結(jié)式C123。

解：先歸結(jié)C1、C2：

C12=～P

再歸結(jié)C12、C3：

C123=NIL～P∨Q～Q～PPNIL圖3-2樹形歸結(jié)過程§3-4歸結(jié)演繹推理定理3.4：歸結(jié)式C12是親本子句C1和C2的邏輯結(jié)論。分析：設(shè)C1=L∨C1’,C2=～L∨C2’按照定理，新子句

C12=C1’∨C2’需要證明的是:

C1∧C2=>

C12（永真）證明：C1=L∨C1’<=>C1’∨L<=>～C1’→

LC2=～L∨C2’<=>L→

C2’假言三段論：C1∧C2=（～C1’→

L）∧（L→

C2’）

=>

（～C1’→

C2’）

又（～C1’→

C2’）<=>C1’∨C2’=C12

于是：C1∧C2

=>

C12§3-4歸結(jié)演繹推理假言三段論：P→Q，Q→R=>P→R

定理3.5：（歸結(jié)原理的完備性定理）如果子句集S是不可滿足的，那么必存在(當(dāng)且僅當(dāng))存在一個從S到空子句NIL的規(guī)約過程。(該定理的證明要用到Herbrand定理，從略。)

命題邏輯的歸結(jié)反演過程：由已知前提F，要證明結(jié)論為G，且F、G都是公式集的形式，只要證明F

∧～G不可滿足。又根據(jù)定理3.1，公式F

∧～G與其子句集等價。又轉(zhuǎn)化為一個含有空子句的歸結(jié)過程。這樣用歸結(jié)原理進行的定理的自動證明也稱為歸結(jié)反演?！?-4歸結(jié)演繹推理歸結(jié)過程描述：否定目標(biāo)公式G，得到

～

G;把～G并入到公式集F中，得到{F，～G};把公式集{F，～

G}化為子句集S;利用歸結(jié)原理對S進行歸結(jié)，若歸結(jié)過程出現(xiàn)空子句，則結(jié)論成立，即G為真例3.10已知{P，（P∧Q）→R，（S∨E）→Q，E}，求證R

證：化為子句集：

S={P，～P∨～Q∨R，～S∨Q，～E∨Q，E，～R}§3-4歸結(jié)演繹推理

S={P，～P∨～Q∨R，～S∨Q，～E∨Q，E，～R}的歸結(jié)演繹樹如下：～P∨

～Q～E∨Q～EENIL～P∨～Q∨R～RP～Q圖3-3一個命題邏輯的歸結(jié)演繹樹§3-4歸結(jié)演繹推理2）謂詞邏輯的歸結(jié)基本原則：先用最一般合一對變元進行代換，然后再進行歸結(jié)。定義3.17設(shè)C1、C2是兩個無相同變元的子句（子句集化簡的最后一步），L1、L2分別是C1、C2中的文字，如果L1和～L2有最一般合一σ，則子句