第一篇：人工智能原理教案02章 歸結(jié)推理方法2.4 歸結(jié)原理

2.4 歸結(jié)原理

本節(jié)在上節(jié)的基礎(chǔ)上，進(jìn)一步具體介紹謂詞邏輯的歸結(jié)方法。謂詞邏輯的歸結(jié)法是以命題邏輯的歸結(jié)法為基礎(chǔ)，在Skolem標(biāo)準(zhǔn)性的子句集上，通過置換和合一進(jìn)行歸結(jié)的。

下面先介紹一些本節(jié)中用到的必要概念：

一階邏輯：謂詞中不再含有謂詞的邏輯關(guān)系式。

個體詞：表示主語的詞

謂詞：刻畫個體性質(zhì)或個體之間關(guān)系的詞

量詞：表示數(shù)量的詞

個體常量：a,b,c

個體變量：x,y,z

謂詞符號：P,Q,R

量詞符號：，歸結(jié)原理正確性的根本在于，如果在子句集中找到矛盾可以肯定命題是不可滿足的。2.4.1 合一和置換

置換：置換可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。

定義：

置換是形如{t1/x1, t2/x2, …, tn/xn}的有限集合。其中，x1, x2, …, xn是互不相同的變量，t1, t2, …, tn是不同于xi的項（常量、變量、函數(shù)）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個ti中。例如

{a/x，c/y，f(b)/z}是一個置換。

{g(y)/x，f(x)/y}不是一個置換，原因是它在x和y之間出現(xiàn)了循環(huán)置換現(xiàn)象。置換的目的是要將某些變量用另外的變量、常量或函數(shù)取代，使其不在公式中出現(xiàn)。但在{g(y)/x，f(x)/y}中，它用g(y)置換x，用f(g(y))置換y，既沒有消去x，也沒有消去y。若改為{g(a)/x，f(x)/y}就可以了。

通常，置換用希臘字母θ、σ、α、λ來表示的。

定義：置換的合成

設(shè)θ＝{t1/x1, t2/x2, …, tn/xn}，λ＝{u1/y1, u2/y2, …, un/yn}，是兩個置換。則θ與λ的合成也是一個置換，記作θ·λ。它是從集合 {t1·λ/x1, t2·l/x2, …, tn·λ/xn, u1/y1, u2/y2, …, un/yn}

即對ti先做λ置換然后再做θ置換，置換xi

中刪去以下兩種元素：

i.當(dāng)tiλ＝xi時，刪去tiλ/xi(i = 1, 2, …, n);

ii.當(dāng)yi∈{x1,x2, …, xn}時，刪去uj/yj(j = 1, 2, …, m)

最后剩下的元素所構(gòu)成的集合。

例：

設(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}

其中，f(b)/x中的f(b)是置換l作用于f(y)的結(jié)果；y/y中的y是置換λ作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，a/y滿足定義中的條件ii，也需要刪除。最后得

θ·λ＝{f(b)/x，y/z}

合一：合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式一致”。

定義：

設(shè)有公式集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若存在一個置換θ，可使F1θ＝F2θ＝…= Fnθ，則稱θ是F的一個合一。同時稱F1，F(xiàn)2，...，F(xiàn)n是可合一的。例：

設(shè)有公式集F＝{P(x, y, f(y)), P(a,g(x),z)}，則λ＝{a/x, g(a)/y, f(g(a))/z}是它的一個合一。

注意：一般說來，一個公式集的合一不是唯一的。

定義：最一般合一

設(shè)σ是公式集F的一個合一，如果對F的任意一個合一θ都存在一個置換λ，使得θ＝σ·λ，則稱σ是一個最一般合一（Most General Unifier，簡記為mgu）

一個公式集的最一般合一是唯一的。若用最一般合一去置換那些可合一的謂詞公式，可使它們變成完全一致的謂詞公式。

歸結(jié)原理方法與命題邏輯基本相同。但由于有變量與函數(shù)，所以要考慮合一和置換。

2.4.2 歸結(jié)式

在謂詞邏輯下求兩個子句的歸結(jié)式，和命題邏輯一樣是消互補(bǔ)對，但需考慮變量的合一與置換。

設(shè)C1、C2是兩個無公共變量的子句，L1、L2分別是C1、C2的文字，如果L1、～L2有mgu σ,則

(C1σ-{L1σ})∪(C2σ-{L2σ})

稱作子句C1、C2的一個二元?dú)w結(jié)式，而L1、L2為被歸結(jié)的文字。

歸結(jié)式的注意事項：

·謂詞的一致性，P()與Q()，不可以歸結(jié)

·常量的一致性，P(a, …)與P(b,….)，不可以歸結(jié)

·變量，P(a, ….)與P(x, …)，可以通過置換歸結(jié)

變量與函數(shù)，P(a, x, ….)與P(x, f(x), …)，不可以歸結(jié)；

但P(a, x, …)與P(x, f(y), …)，可以通過對兩式分別做{f(y)/x}置換和{a/x}，再歸結(jié)。

·不能同時消去兩個互補(bǔ)對，形如P∨Q與～P∨～Q得空，是不正確的

·對子句集中的元素先進(jìn)行內(nèi)部簡化（置換、合并）

例：

設(shè)C1＝P(y)∨P(f(x))∨Q(g(x))，C2＝～P(f(g(a)))∨Q(b)，求C1和C2的歸結(jié)式。

解：

對C1，取最一般合一σ＝{f(x)/y}，得C1的因子

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

對C1的因子和C2進(jìn)行歸結(jié)，可得到C1和C2的歸結(jié)式：Q(g(g(a)))∨Q(b)2.4.3 歸結(jié)過程

謂詞邏輯的歸結(jié)過程與命題邏輯的歸結(jié)過程相比，其基本步驟相同，但每步的處理對象不同。謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集，必要時在得到歸結(jié)式前要進(jìn)行置換和合一。

具體的謂詞邏輯歸結(jié)過程如下：

·寫出謂詞關(guān)系公式

·用反演法寫出謂詞表達(dá)式

·化為SKOLEM標(biāo)準(zhǔn)形

·求取子句集S

·對S中可歸結(jié)的子句做歸結(jié)

·歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程

·得到空子句

·命題得證 例題2-4

“快樂學(xué)生”問題：

假設(shè)任何通過計算機(jī)考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎。求證：張是快樂的。

解：

先將問題用謂詞表示如下：

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

(x)((Pass(x, computer)∧Win(x, prize))→Happy(x))

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

(x)(y)(Study(x)∨Lucky(x)→Pass(x, y))

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

～Study(zhang)∧Lucky(zhang)

R4:“任何幸運(yùn)的人都能獲獎”

(x)(Luck(x)→Win(x,prize))

結(jié)論“張是快樂的”的否定

～Happy(zhang)

將上述謂詞公式轉(zhuǎn)化為子句集并進(jìn)行歸結(jié)如下：

首先將每一個表示邏輯條件的謂詞子句轉(zhuǎn)換為子句集可以接受的Skolem標(biāo)準(zhǔn)形。

由R1及邏輯轉(zhuǎn)換公式:P∧W→H = ～（P∧W）∨ H，可得

(1)～Pass(x, computer)∨～Win(x, prize)∨Happy(x)

由R2可得

(2)～Study(y)∨Pass(y,z)

(3)～Lucky(u)∨Pass(u,v)

由R3可得

(4)～Study(zhang)

(5)Lucky(zhang)

由R4可得

(6)～Lucky(w)∨Win(w，prize)

由結(jié)論可得

(7)～Happy(zhang)結(jié)論的否定

根據(jù)以上7條子句，歸結(jié)如下：

(8)～Pass(w, computer)∨Happy(w)∨～Luck(w)(1)，(6)歸結(jié)，{w/x}

(9)～Pass(zhang, computer)∨～Lucky(zhang)(8)，(7)歸結(jié)，{zhang/w}

(10)～Pass(zhang, computer)(9)，(5)歸結(jié)

(11)～Lucky(zhang)(10),(3)歸結(jié),{zhang/u, computer/v}

(12)?(11),(5)歸結(jié)

結(jié)論

1．歸結(jié)法的實質(zhì)：

·歸結(jié)法是僅有一條推理規(guī)則的推理方法。

·歸結(jié)的過程是一個語義樹倒塌的過程。

2．歸結(jié)法的問題

·對于傳統(tǒng)歸結(jié)法，子句中有等號或不等號時，完備性不成立。即，傳統(tǒng)的歸結(jié)法不能處理相等的關(guān)系。

Herbrand定理式歸結(jié)原理的理論基礎(chǔ)；而正是由于Herbrand定理的不實用性引出了可實用的歸結(jié)法。

第二篇：人工智能原理教案02章 歸結(jié)推理方法2.2 命題邏輯的歸結(jié)

2.2 命題邏輯的歸結(jié) 2.2.1 命題邏輯基礎(chǔ)

邏輯可分為經(jīng)典邏輯和非經(jīng)典邏輯，其中經(jīng)典邏輯包括命題邏輯和謂詞邏輯。歸結(jié)原理是一種主要基于謂詞（邏輯）知識表示的推理方法，而命題邏輯是謂詞邏輯的基礎(chǔ)。因此，在討論謂詞邏輯之前，先討論命題邏輯的歸結(jié)，便于內(nèi)容上的理解。

本節(jié)中，將主要介紹命題邏輯的歸結(jié)方法，以及有關(guān)的一些基礎(chǔ)知識和重要概念，如數(shù)理邏輯基本公式變形、前束范式、子句集等。

描述事實、事物的狀態(tài)、關(guān)系等性質(zhì)的文字串，取值為真或假（表示是否成立）的句子稱作命題。

命題：非真即假的簡單陳述句

在命題邏輯里，單元命題是基本的單元或作為不可再分的原子。下面所列出的是一些基本的數(shù)理邏輯公理公式和一些有用的基本定義，如合取范式、子句集，這些公式和定義在歸結(jié)法的推理過程中是必不可少的，也是歸結(jié)法的基礎(chǔ)，應(yīng)該熟練掌握。

－數(shù)理邏輯的基本定義

下面所列的是一些數(shù)理邏輯中重要的定義，在后面的分析中要用到：

·合取式：p與q，記做p ∧ q

·析取式：p或q，記做p ∨ q

·蘊(yùn)含式：如果p則q，記做p → q

·等價式：p當(dāng)且僅當(dāng)q，記做p

q

·若A無成假賦值，則稱A為重言式或永真式；

·若A無成真賦值，則稱A為矛盾式或永假式；

·若A至少有一個成真賦值，則稱A為可滿足的；

·析取范式：僅由有限個簡單合取式組成的析取式

·合取范式：僅由有限個簡單析取式組成的合取式

－數(shù)理邏輯的基本等值式

下面這些基本的等式在歸結(jié)原理實施之前的公式轉(zhuǎn)化過程中是非常重要的。只有將邏輯公式正確轉(zhuǎn)換成為歸結(jié)原理要求的范式，才能夠保證歸結(jié)的正常進(jìn)行。

·交換律：p∨q

q ∨p ；

q ∧ p

p ∧ q

·結(jié)合律：(p∨q)∨ rp∨(q ∨r);

(p ∧ q)∧ rp ∧(q ∧ r)

·分配律： p∨(q ∧ r)

(p∨q)∧(p ∨r)；(p ∧ q)∨(p ∧ r)

p ∧(q ∨ r)

·雙重否定律：p

·等冪律：p

～～p

p∨p；p p∧p

·摩根律: ～(p∨q)～ p ∧ ～ q ； ～ p ∨ ～ q

～(p ∧q)

·吸收律: p∨(p∧q)

p ；

p

p ∧(p∨q)

·同一律: p∨0

p ； p

p∧1

·零律：p∨1

p∧0 0

·排中律：p∨～p

·矛盾律：p∧～p 0

～ p∨q(p → q)∧(q → p)～ p → ～ q

～p～q

～p

·蘊(yùn)含等值式：p → q

·等價等值式：pq

·假言易位式: p → q

·等價否定等值式：pq

·歸謬論：(p → q)∧(p → ～q)

－合取范式

范式：范式是公式的標(biāo)準(zhǔn)形式，公式往往需要變換為同它等價的范式，以便對它們作一般性的處理。

合取范式：單元子句、單元子句的或（∨）的與（∧）。

如：P∧（P∨Q）∧（～P∨Q）

例：求取P ∧(Q → R)→ S 的合取范式

解： P ∧(Q → R)→ S

= ～（P∧(～Q∨R)）∨S

= ～P∨～(～Q∨R)∨S

= ～P∨(～～Q∧～R)∨S

= ～P∨(Q∧～R)∨S

= ～P∨S∨(Q∧～R)

=(～P∨S∨Q)∧(～P∨S∨～R)

注意：首先一定要將原有的命題公式整理、轉(zhuǎn)換成為各個“或”語句的“與”，不然后續(xù)推導(dǎo)沒有意義。轉(zhuǎn)換是基于數(shù)理邏輯的基本等值公式進(jìn)行的，“或”轉(zhuǎn)換到“與”中。思路與代數(shù)學(xué)的提取公因式方法相似。

－子句集

命題公式的子句集S是合取范式形式下的子命題（元素）的集合。

子句集是合取范式中各個合取分量的集合，生成子句集的過程可以簡單地理解為將命題公式的合取范式中的與符號“∧”，置換為逗號“，”。

上例轉(zhuǎn)換的合取范式：(～P∨S∨Q)∧(～P∨S∨～R)

其子句集為

S = {～P∨S∨Q, ～P∨S∨～R}

又如，有命題公式：P∧（P∨Q）∧（～P∨Q）

其子句集 S：S = {P, P∨Q, ～P∨Q}

2.2.2 命題邏輯的歸結(jié)

歸結(jié)法推理的核心是求兩個子句的歸結(jié)式，因此需要先討論歸結(jié)式的定義和性質(zhì)。

歸結(jié)式的定義

設(shè)C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么可從C1和C2中分別消去L1和L2，并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個新子句C12，則稱這一個過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。

例如：有子句：C1＝P∨C1'，C2＝～P∨C2'

存在互補(bǔ)對 P和～P，則可得歸結(jié)式：C12 = C1'∨C2'

注意：C1ΛC2 → C12，反之不一定成立。

下面證明歸結(jié)式是原兩子句的邏輯推論，或者說任一使C1、C2為真的解釋I下必有歸結(jié)式C12也為真。

證明：

設(shè)I是使C1，C2為真的任一解釋，若I下的P為真，從而～P為假，必有I下C2'為真，故C12為真。若不然，在I下P為假，從而I下C1'為真，故I下C12為真。于是C1∧C2為真。于是C1∧C2→R(C1,C2)成立。

反之不一定成立，因為存在一個使C1'∨C2'為真的解釋I，不妨設(shè)C1'為真，C2'為假。若P為真，則～P∨C2'就為假了。因此反之不一定成立。由此可得歸結(jié)式的性質(zhì)。

歸結(jié)式的性質(zhì)：歸結(jié)式C12 是親本子句C12 和C12的邏輯結(jié)論。

命題邏輯的歸結(jié)法證明過程

命題邏輯的歸結(jié)過程也就是推理過程。推理是根據(jù)一定的準(zhǔn)則由稱為前提條件的一些判斷導(dǎo)出稱為結(jié)論的另一些判斷的思維過程。命題邏輯的歸結(jié)方法推理過程可以分為如下幾個步驟：

1.建立待歸結(jié)命題公式

首先根據(jù)反證法將所求證的問題轉(zhuǎn)化成為命題公式，求證其是矛盾式（永假式）。

求取合取范式建立子句集歸結(jié)

歸結(jié)法是在子句集S的基礎(chǔ)上通過歸結(jié)推理規(guī)則得到的，歸結(jié)過程的最基本單元是得到歸結(jié)式的過程。從子句集S出發(fā)，對S的子句間使用歸結(jié)推理規(guī)則，并將所得歸結(jié)式仍放入到S中（注意：此過程使得子句集不斷擴(kuò)大，是造成計算爆炸的根本原因），進(jìn)而再對新子句集使用歸結(jié)推理規(guī)則。重復(fù)使用這些規(guī)則直到得到空子句?。這便說明S是不可滿足的，從而與S所對應(yīng)的定理是成立的。

歸結(jié)步驟：

1)對子句集中的子句使用歸結(jié)規(guī)則

2)歸結(jié)式作為新子句加入子句集參加歸結(jié)

3)歸結(jié)式為空子句□ 為止。

（證明完畢）

得到空子句□，表示S是不可滿足的（矛盾），故原命題成立。

例題2-1

證明公式：

(P → Q)→(～Q → ～P)證明：根據(jù)歸結(jié)原理

將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：

(P → Q)∧～(～Q → ～P)

分別將公式前項化為合取范式：

P → Q ＝ ～P ∨ Q

結(jié)論求～后的后項化為合取范式：

～(～Q → ～P)＝ ～(Q∨～P)＝ ～Q ∧ P

兩項合并后化為合取范式：

（～P ∨ Q）∧～Q ∧ P

則子句集為：

{ ～P∨Q，～Q，P}

對子句集中的子句進(jìn)行歸結(jié)可得：

1.～P∨Q

2.～Q

3.P

4.Q，（1，3歸結(jié)）

5.e，（2，4歸結(jié)）

由上可得原公式成立。

謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。

教師提示：命題邏輯基礎(chǔ)是學(xué)習(xí)歸結(jié)法的必要基礎(chǔ)，應(yīng)該在前序的課程中學(xué)習(xí)過。這里列出的只是一些簡單的性質(zhì)。如果大家對這些知識有什么疑惑的話，請參考數(shù)理邏輯的有關(guān)書籍。命題邏輯的歸結(jié)法的邏輯基礎(chǔ)是假言易位式和摩根律。

第三篇：人工智能原理教案02章歸結(jié)推理方法2.3謂詞邏輯歸結(jié)法基礎(chǔ)

2.3 謂詞邏輯歸結(jié)法基礎(chǔ)

由于謂詞邏輯與命題邏輯不同，有量詞、變量和函數(shù)，所以在生成子句集之前要對邏輯公式做處理，具體的說就是要將其轉(zhuǎn)化為Skolem標(biāo)準(zhǔn)形，然后在子句集的基礎(chǔ)上再進(jìn)行歸結(jié)，雖然基本的歸結(jié)的基本方法都相同，但是其過程較之命題公式的歸結(jié)過程要復(fù)雜得多。

本節(jié)針對謂詞邏輯歸結(jié)法介紹了Skolem標(biāo)準(zhǔn)形、子句集等一些必要的概念和定理。

2．3．1 Skolem 標(biāo)準(zhǔn)形 Skolem標(biāo)準(zhǔn)形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為Skolem標(biāo)準(zhǔn)形，任何一個謂詞公式都可以化為與之對應(yīng)的Skolem標(biāo)準(zhǔn)形。但是，Skolem標(biāo)準(zhǔn)形不唯一。

前束范式：A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。

Skolem標(biāo)準(zhǔn)形的轉(zhuǎn)化過程為，依據(jù)約束變量換名規(guī)則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。具體步驟如下：

將謂詞公式G轉(zhuǎn)換成為前束范式

前束范式的形式為：

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

即： 把所有的量詞都提到前面去。

注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達(dá)式中的所有同名變量。所以將量詞提到公式最前端時存在約束變量換名問題。要嚴(yán)守規(guī)則。

約束變量換名規(guī)則：

(Qx)M（x）（Qy）M（y）

(Qx)M（x,z）（Qy）M（y,z）

量詞否定等值式：

～(x)M（x）（y）～ M（y）

～(x)M（x）（y）～ M（y）

量詞分配等值式：

(x)(P（x）∧Q（x）)(x)P（x）∧(x)Q（x）

(x)(P（x）∨ Q（x）)(x)P（x）∨(x)Q（x）

消去量詞等值式：設(shè)個體域為有窮集合（a1, a2, …an）

(x)P（x）P（a1）∧ P（a2）∧ …∧ P（an）

(x)P（x）P（a1）∨ P（a2）∨ … ∨ P（an）

量詞轄域收縮與擴(kuò)張等值式：

(x)(P（x）∨ Q)(x)P（x）∨ Q

(x)(P（x）∧ Q)(x)P（x）∧ Q

(x)(P（x）→ Q)(x)P（x）→ Q

(x)(Q → P（x）)Q →(x)P（x）

(x)(P（x）∨ Q)(x)P（x）∨ Q

(x)(P（x）∧ Q)(x)P（x）∧ Q

(x)(P（x）→ Q)(x)P（x）→ Q

(x)(Q → P（x）)Q →(x)P（x）消去量詞

量詞消去原則：

1)消去存在量詞“"，即，將該量詞約束的變量用任意常量（a, b等）、或全稱變量的函數(shù)(f(x), g(y)等)代替。如果存在量詞左邊沒有任何全稱量詞，則只將其改寫成為常量；如果是左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)。

2)略去全程量詞”“，簡單地省略掉該量詞。

Skolem 定理：

謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。

注意：公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。例題2-2

將下式化為Skolem標(biāo)準(zhǔn)形：

～(x)(y)P(a, x, y)→(x)(～(y)Q(y, b)→R(x))

解：

第一步，消去→號，得：

～(～(x)(y)P(a, x, y))∨(x)(～～(y)Q(y, b)∨R(x))

第二步，～深入到量詞內(nèi)部，得：

(x)(y)P(a, x, y)∧～(x)((y)Q(y, b)∨R(x))

＝(x)(y)P(a, x, y)∧(x)((y)～Q(y, b)∧～R(x))

第三步，全稱量詞左移，（利用分配律），得

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

第四步，變元易名，存在量詞左移，直至所有的量詞移到前面，得：

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

＝(x)((y)P(a, x, y)∧(z)(～Q(z, b)∧～R(x)))

=(x)(y)(z)(P(a, x, y)∧～Q(z, b)∧～R(x))

由此得到前述范式

第五步，消去”“（存在量詞），略去”“全稱量詞

消去(y)，因為它左邊只有(”x)，所以使用x的函數(shù)f(x)代替之，這樣得到：

(x)(z)(P(a, x, f(x))∧～Q(z, b)∧～R(x))

消去(z)，同理使用g(x)代替之，這樣得到：

(x)(P(a, x, f(x))∧～Q(g(x), b)∧～R(x))

則，略去全稱變量，原式的Skolem標(biāo)準(zhǔn)形為：

P(a, x, f(x))∧～Q(g(x), b)∧～R(x)2.3.2子句集

文字：不含任何連接詞的謂詞公式。

子句：一些文字的析取（謂詞的和）。

子句集：所有子句的集合

對于任一個公式G，都可以通過Skolem標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)化建立起一個子句集與之相對應(yīng)。因為子句不過是一些文字的析取，是一種比較簡單的形式，所以對G的討論就用對子句集S的討論來代替，以便容易處理。

子句集S可由下面的步驟求?。?/p>

1.謂詞公式G轉(zhuǎn)換成前束范式

2.消去前束范式中的存在變量，略去其中的任意變量，生成SKOLEM標(biāo)準(zhǔn)形

3.將SKOLEM標(biāo)準(zhǔn)形中的各個子句提出，表示為集合形式

教師提示：為了簡單起見，子句集生成可以理解為是用“，”取代SKOLEM標(biāo)準(zhǔn)形中的“Λ”，并表示為集合形式。

注意：SKOLEM標(biāo)準(zhǔn)形必須滿足合取范式的條件。即，在生成子句集之前邏輯表達(dá)式必須是各“謂詞表達(dá)式”或“謂詞或表達(dá)式”的與。定理

謂詞表達(dá)式G是不可滿足的當(dāng)且僅當(dāng) 其子句集S是不可滿足的

公式G與其子句集S并不等值，但它們在不可滿足的意義下是一致的。因此如果要證明A1∧A2∧A3→B，只需證明G＝ A1∧A2∧A3∧～B的子句集是不可滿足的，這也正是引入子句集的目的。

注意：公式G和子句集S雖然不等值，但是它們的之間一般邏輯關(guān)系可以簡單的說明為：G真不一定S真，而S真必有G真，即，S G。在生成SKOLEM標(biāo)準(zhǔn)形時將存在量詞用常量或其他變量的函數(shù)代替，使得變量討論的論域發(fā)生了變化，即論域變小了。所以G不能保證S真。定理的推廣

對于形如G = G1Λ G2Λ G3Λ …Λ Gn 的謂詞公式，G的子句集的求取過程可以分解成幾個部分單獨(dú)處理。如果Gi的子句集為Si，則

有 S' = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，雖然G的子句集不為S'，但是可以證明：

SG 與S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可滿足的意義上是一致的。

即SG 不可滿足 S1 ∪ S2 ∪S3 ∪ …∪ Sn不可滿足

第四篇：人工智能原理教案02章 歸結(jié)推理方法2.3 謂詞邏輯歸結(jié)法基礎(chǔ)

2.3 謂詞邏輯歸結(jié)法基礎(chǔ)

由于謂詞邏輯與命題邏輯不同，有量詞、變量和函數(shù)，所以在生成子句集之前要對邏輯公式做處理，具體的說就是要將其轉(zhuǎn)化為Skolem標(biāo)準(zhǔn)形，然后在子句集的基礎(chǔ)上再進(jìn)行歸結(jié)，雖然基本的歸結(jié)的基本方法都相同，但是其過程較之命題公式的歸結(jié)過程要復(fù)雜得多。

本節(jié)針對謂詞邏輯歸結(jié)法介紹了Skolem標(biāo)準(zhǔn)形、子句集等一些必要的概念和定理。

2．3．1 Skolem 標(biāo)準(zhǔn)形

Skolem標(biāo)準(zhǔn)形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為Skolem標(biāo)準(zhǔn)形，任何一個謂詞公式都可以化為與之對應(yīng)的Skolem標(biāo)準(zhǔn)形。但是，Skolem標(biāo)準(zhǔn)形不唯一。

前束范式：A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。

Skolem標(biāo)準(zhǔn)形的轉(zhuǎn)化過程為，依據(jù)約束變量換名規(guī)則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。具體步驟如下：

將謂詞公式G轉(zhuǎn)換成為前束范式

前束范式的形式為：

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

即： 把所有的量詞都提到前面去。

注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達(dá)式中的所有同名變量。所以將量詞提到公式最前端時存在約束變量換名問題。要嚴(yán)守規(guī)則。

約束變量換名規(guī)則：

(Qx)M（x）

(Qx)M（x,z）

（Qy）M（y）

（Qy）M（y,z）

量詞否定等值式：

～(x)M（x）

～(x)M（x）

量詞分配等值式：

(x)(P（x）∧Q（x）)

(x)(P（x）∨ Q（x）)

(x)P（x）∧(x)Q（x）(x)P（x）∨(x)Q（x）

（y）～ M（y）

（y）～ M（y）

消去量詞等值式：設(shè)個體域為有窮集合（a1, a2, …an）

(x)P（x）

(x)P（x）

P（a1）∧ P（a2）∧ …∧ P（an）P（a1）∨ P（a2）∨ … ∨ P（an）

量詞轄域收縮與擴(kuò)張等值式：

(x)(P（x）∨ Q)

(x)(P（x）∧ Q)

(x)(P（x）→ Q)

(x)(Q → P（x）)

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)P（x）

(x)(P（x）∨ Q)

(x)(P（x）∧ Q)

(x)(P（x）→ Q)

(x)(Q → P（x）)

消去量詞

量詞消去原則：

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)P（x）

1)消去存在量詞“"，即，將該量詞約束的變量用任意常量（a, b等）、或全稱變量的函數(shù)(f(x), g(y)等)代替。如果存在量詞左邊沒有任何全稱量詞，則只將其改寫成為常量；如果是左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)。

2)略去全程量詞”“，簡單地省略掉該量詞。

Skolem 定理：

謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。

注意：公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。例題2-2

將下式化為Skolem標(biāo)準(zhǔn)形：

～(x)(y)P(a, x, y)→(x)(～(y)Q(y, b)→R(x))

解：

第一步，消去→號，得：

～(～(x)(y)P(a, x, y))∨(x)(～～(y)Q(y, b)∨R(x))

第二步，～深入到量詞內(nèi)部，得：

(x)(y)P(a, x, y)∧～(x)((y)Q(y, b)∨R(x))

＝(x)(y)P(a, x, y)∧(x)((y)～Q(y, b)∧～R(x))

第三步，全稱量詞左移，（利用分配律），得

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

第四步，變元易名，存在量詞左移，直至所有的量詞移到前面，得：

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

＝(x)((y)P(a, x, y)∧(z)(～Q(z, b)∧～R(x)))

=(x)(y)(z)(P(a, x, y)∧～Q(z, b)∧～R(x))

由此得到前述范式

第五步，消去”“（存在量詞），略去”“全稱量詞

消去(y)，因為它左邊只有(”x)，所以使用x的函數(shù)f(x)代替之，這樣得到：

(x)(z)(P(a, x, f(x))∧～Q(z, b)∧～R(x))

消去(z)，同理使用g(x)代替之，這樣得到：

(x)(P(a, x, f(x))∧～Q(g(x), b)∧～R(x))

則，略去全稱變量，原式的Skolem標(biāo)準(zhǔn)形為：

P(a, x, f(x))∧～Q(g(x), b)∧～R(x)

2.3.2子句集

文字：不含任何連接詞的謂詞公式。

子句：一些文字的析?。ㄖ^詞的和）。

子句集：所有子句的集合

對于任一個公式G，都可以通過Skolem標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)化建立起一個子句集與之相對應(yīng)。因為子句不過是一些文字的析取，是一種比較簡單的形式，所以對G的討論就用對子句集S的討論來代替，以便容易處理。

子句集S可由下面的步驟求取：

1.謂詞公式G轉(zhuǎn)換成前束范式

2.消去前束范式中的存在變量，略去其中的任意變量，生成SKOLEM標(biāo)準(zhǔn)形

3.將SKOLEM標(biāo)準(zhǔn)形中的各個子句提出，表示為集合形式

教師提示：為了簡單起見，子句集生成可以理解為是用“，”取代SKOLEM標(biāo)準(zhǔn)形中的“Λ”，并表示為集合形式。

注意：SKOLEM標(biāo)準(zhǔn)形必須滿足合取范式的條件。即，在生成子句集之前邏輯表達(dá)式必須是各“謂詞表達(dá)式”或“謂詞或表達(dá)式”的與。

定理

謂詞表達(dá)式G是不可滿足的當(dāng)且僅當(dāng) 其子句集S是不可滿足的

公式G與其子句集S并不等值，但它們在不可滿足的意義下是一致的。因此如果要證明A1∧A2∧A3→B，只需證明G＝ A1∧A2∧A3∧～B的子句集是不可滿足的，這也正是引入子句集的目的。

注意：公式G和子句集S雖然不等值，但是它們的之間一般邏輯關(guān)系可以簡單的說明為：G真不一定S真，而S真必有G真，即，S G。在生成SKOLEM標(biāo)準(zhǔn)形時將存在量詞用常量或其他變量的函數(shù)代替，使得變量討論的論域發(fā)生了變化，即論域變小了。所以G不能保證S真。

定理的推廣

對于形如G = G1Λ G2Λ G3Λ …Λ Gn 的謂詞公式，G的子句集的求取過程可以分解成幾個部分單獨(dú)處理。如果Gi的子句集為Si，則

有 S' = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，雖然G的子句集不為S'，但是可以證明：

SG 與S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可滿足的意義上是一致的。

即SG 不可滿足

由上面的定理，我們對SG的討論，可以用較為簡單的S1 ∪ S2 ∪ S3 ∪ …∪ Sn來代替。為方便起見，也稱S1 ∪ S2 ∪ S3 ∪ …∪ Sn為G的子句形，即：

S1 ∪ S2 ∪S3 ∪ …∪ Sn不可滿足

SG＝S1 ∪ S2 ∪ S3 ∪ …∪ Sn。根據(jù)以上定理可對一個謂詞表達(dá)式分而治之，化整為零，大大減少了計算復(fù)雜度。

例2－3

對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？

用一階邏輯表示這個問題，并建立子句集。

解：

這里我們首先引入謂詞：

P(x, y)表示x是y的父親

Q(x, y)表示x是y的祖父

ANS(x)表示問題的解答

于是有：

對于第一個條件，“如果y是x的父親，z又是y的父親，則z是x的祖父”，一階邏輯表達(dá)式如下：

A1：(x)(y)(z)(P(x, y)∧P(y, z)→Q(x, z))

則把A1化為合取范式，進(jìn)而化為Skolem標(biāo)準(zhǔn)形，表示如下：

S A1：～P(x ,y)∨～P(y, z)∨Q(x, z)

對于第二個條件：“每個人都有父親”，一階邏輯表達(dá)式如下：

A2：(y)(x)P(x, y)

化為Skolem標(biāo)準(zhǔn)形，表示如下：

S A2：P(f(y), x)

結(jié)論：某個人是它的祖父

B：(x)(y)Q(x, y)

否定后得到子句：

S～B：～Q(x, y)∨ANS(x)

則得到的相應(yīng)的子句集為：{ S A1，S A2，S～B }

解畢。

第五篇：人工智能原理教案03章 不確定性推理方法3.4 證據(jù)理論(D-S Theory)

3.4 證據(jù)理論（D-S Theory）

證據(jù)理論由Dempster首先提出，并由他的學(xué)生Shafer發(fā)展起來，也稱D-S理論。在專家系統(tǒng)的不精確推理中已得到廣泛的應(yīng)用, 也用在模式識別系統(tǒng)中。證據(jù)理論中引入了信任函數(shù)，它滿足概率論弱公理。在概率論中，當(dāng)先驗概率很難獲得，但又要被迫給出時，用證據(jù)理論能區(qū)分不確定性和不知道的差別。所以它比概率論更合適于專家系統(tǒng)推理方法。當(dāng)概率值已知時，證據(jù)理論就成了概率論。因此，概率論是證據(jù)理論的一個特例，有時也稱證據(jù)淪為廣義概率論。

在http://yoda.cis.temple.edu:8080/UGAIWWW/lectures/dempster.html上有關(guān)于Dempster－Shafer理論的英文介紹。

在http://www.quiver.freeserve.co.uk/Dse.htm上有免費(fèi)的利用證據(jù)理論實現(xiàn)的程序Dempster Shafer Engine下載。有興趣的讀者可以安裝這一軟件，看看運(yùn)行效果。這是我們已經(jīng)下載下來的程序包：DempsterShaferEngine.zip。3.4.1 證據(jù)的不確定性

證據(jù)用集合來表示：如U中的每個元素代表一種疾病。討論一組疾病A發(fā)生的可能性時，A就變成了單元的集合。U內(nèi)元素Ai間是互斥的，但Ai中元素間是不互斥的。

圖3-4證據(jù)理論集合空間分布示意圖

t3-4_swf.htm 例如U可以表示疾病空間，而每個Ai可以是一類疾病，各類疾病之間是可以交叉的（同時得多種疾?。?，但是各類疾病本身是不同的。

證據(jù)理論定義了多個函數(shù)值來描述證據(jù)及規(guī)則的不確定性，其中包括：分配函數(shù)、信任函數(shù)和似然函數(shù)，分別定義如下。

· 基本概率分配函數(shù)m：2U→[0,1]。

m(Φ)= 0 空的為零

Σm(A)= 1 全空間的和為

1（A屬于U）

基本概率分配函數(shù)是在U的冪集2U 上定義的，取值范圍是[0,1]。

基本概率函數(shù)的物理意義是：

若A屬于U，且不等于U，表示對A的精確信任度

若A等于U，表示這個數(shù)不知如何分配

· 信任函數(shù)Bel：2U →[0,1]。

A的信任函數(shù)為：包含于A中的所有集合的概率分配函數(shù)值之和。

根據(jù)定義有：Bel(Φ)＝m(Φ)= 0

Bel(U)＝Σm(B)= 1（B屬于U）

信任函數(shù)Bel類似于概率密度函數(shù)，表示A中所有子集的基本概率分配數(shù)值的和。表示對A的總信任度。

· 似然函數(shù)Pl：2U →[0,1]

A的似然函數(shù)為Pl(A)：與A的“與”不為零的所有集合的概率分配函數(shù)值之和。

根據(jù)定義有：0 ≤ Bel(A)≤ Pl(A)≤1

可見Bel是Pl的一部分。

稱Bel(A)和Pl(A)是A的下限不確定性值和上限不確定性值。因此可用區(qū)間（Bel(A)，Pl(A)）來表示A的不確定性度量。

我們可以通過信任函數(shù)、似然函數(shù)的特殊值，以及這些特殊值的相關(guān)關(guān)系來討論它們所描述的證據(jù)可信度情況。設(shè)函數(shù)f(Bel(A), Pl(A))，下列特殊值的含義：

f(1, 1)表示A為真

f(0, 0)表示A為假

f(0, 1)表示對A一無所知

f(1, 0)不可能成立

一般情況都是包含在這些特殊值的某一個區(qū)間中的?？梢愿鶕?jù)與這些特殊值的相對關(guān)系來判斷其可信程度。

此外，還可以用函數(shù)f1(A)來衡量A的不確定性，其定義如下：

f1(A)= Bel(A)+ |A|/|U|(Pl(A)∑m1(X)m2(Y), 當(dāng)X∩Y =Φ

= ∑m1(X)m2(Y), 當(dāng)X∩Y ≠Φ

且K-1 ≠ 0，若K-1 = 0，認(rèn)為m1, m2矛盾。沒有聯(lián)合基本概率分配函數(shù)。例題

已知：f1(A1)= 0.40 ,f1(A2)=0.50,|U| = 20.A1→B={b1,b2,b3}，(c1,c2,c3)=(0.1,0.2,0.3)

A2→B={b1,b2,b3}，(c1,c2,c3)=(0.5,0.2,0.1)

求：f1(B)

解：

（1）先求：

m1({b1},{b2},{b3})=(0.4*0.1,0.4*0.2,0.4*0.3)

=(0.04,0.08,0.12);

m1(U)=1-[m1({b1})+m1({b2})+m1({b3})]=0.76;

m2({b1},{b2},{b3})=(0.5*0.5,0.5*0.2,0.5*0.1)

=(0.25,0.10,0.05);

m2(U)=1-[m2({b1})+m2({b2})+m2({b3})]=0.70;

及m = m1⊙ m2

1/K=m1({b1})*m2({b1})+

m1({b1})*m2({U})+ m1({b2})*m2({U})+ m1({b2})*m2({b2})+ m1({b3})*m2({b3})+m1({b3})*m2({U})+m1({U})*m2({b1})+ m1({U})*m2({b2})+ m1({U})*m2({b3})+ m1({U})*m2({U})

=0.01+0.028+0.008+0.056+0.06+0.084+0.19+0.076+0.038+0.532

=1.082

（2）然后計算：

m({b1})=K*(m1({b1})*m2({b1})+ m1({b1})*m2({U})+ m1({U})*m2({b1}))

=1.082*(0.01+0.028+0.19)

=0.247

m({b2})=K*(m1({b2})*m2({b2})+ m1({b2})*m2({U})+ m1({U})*m2({b2}))

=1.082*(0.008+0.056+0.076)

=0.151

m({b3})=K*(m1({b3})*m2({b3})+ m1({b3})*m2({U})+ m1({U})*m2({b3}))

=1.082*(0.06+0.084+0.038)

=0.138

m(U)=1-[ m({b1})+ m({b2})+ m({b3})]=0.464

最后：

Bel（B）＝m({b1})+ m({b2})+ m({b3})＝0.536

P1(B)＝1-Bel(~B)

由于基本概率分配函數(shù)只定義在B集合和全集U之上，所以其它集合的分配函數(shù)值為0，即Bel(~B)=0

所以，可得

P1(B)＝1-Bel(~B)=1

F1(B)=Bel(B)+(P1(B)-Bel(B))*|B|/|U|

=0.536+(1-0.536)*3/20

=0.606