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

2.4 歸結原理

本節在上節的基礎上，進一步具體介紹謂詞邏輯的歸結方法。謂詞邏輯的歸結法是以命題邏輯的歸結法為基礎，在Skolem標準性的子句集上，通過置換和合一進行歸結的。

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

一階邏輯：謂詞中不再含有謂詞的邏輯關系式。

個體詞：表示主語的詞

謂詞：刻畫個體性質或個體之間關系的詞

量詞：表示數量的詞

個體常量：a,b,c

個體變量：x,y,z

謂詞符號：P,Q,R

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

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

定義：

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

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

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

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

定義：置換的合成

設θ＝{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.當tiλ＝xi時，刪去tiλ/xi(i = 1, 2, …, n);

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

最后剩下的元素所構成的集合。

例：

設θ＝{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)的結果；y/y中的y是置換λ作用于z的結果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，a/y滿足定義中的條件ii，也需要刪除。最后得

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

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

定義：

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

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

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

定義：最一般合一

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

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

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

2.4.2 歸結式

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

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

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

稱作子句C1、C2的一個二元歸結式，而L1、L2為被歸結的文字。

歸結式的注意事項：

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

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

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

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

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

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

·對子句集中的元素先進行內部簡化（置換、合并）

例：

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

解：

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

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

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

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

具體的謂詞邏輯歸結過程如下：

·寫出謂詞關系公式

·用反演法寫出謂詞表達式

·化為SKOLEM標準形

·求取子句集S

·對S中可歸結的子句做歸結

·歸結式仍放入S中，反復歸結過程

·得到空子句

·命題得證 例題2-4

“快樂學生”問題：

假設任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。

解：

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

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

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

R2:“任何肯學習或幸運的人都可以通過所有考試”

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

R3:“張不肯學習但他是幸運的”

～Study(zhang)∧Lucky(zhang)

R4:“任何幸運的人都能獲獎”

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

結論“張是快樂的”的否定

～Happy(zhang)

將上述謂詞公式轉化為子句集并進行歸結如下：

首先將每一個表示邏輯條件的謂詞子句轉換為子句集可以接受的Skolem標準形。

由R1及邏輯轉換公式: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)

由結論可得

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

根據以上7條子句，歸結如下：

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

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

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

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

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

結論

1．歸結法的實質：

·歸結法是僅有一條推理規則的推理方法。

·歸結的過程是一個語義樹倒塌的過程。

2．歸結法的問題

·對于傳統歸結法，子句中有等號或不等號時，完備性不成立。即，傳統的歸結法不能處理相等的關系。

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

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

2.2 命題邏輯的歸結 2.2.1 命題邏輯基礎

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

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

描述事實、事物的狀態、關系等性質的文字串，取值為真或假（表示是否成立）的句子稱作命題。

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

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

－數理邏輯的基本定義

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

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

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

·蘊含式：如果p則q，記做p → q

·等價式：p當且僅當q，記做p

q

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

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

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

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

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

－數理邏輯的基本等值式

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

·交換律：p∨q

q ∨p ；

q ∧ p

p ∧ q

·結合律：(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

·蘊含等值式：p → q

·等價等值式：pq

·假言易位式: p → q

·等價否定等值式：pq

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

－合取范式

范式：范式是公式的標準形式，公式往往需要變換為同它等價的范式，以便對它們作一般性的處理。

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

如：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)

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

－子句集

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

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

上例轉換的合取范式：(～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 命題邏輯的歸結

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

歸結式的定義

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

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

存在互補對 P和～P，則可得歸結式：C12 = C1'∨C2'

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

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

證明：

設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，不妨設C1'為真，C2'為假。若P為真，則～P∨C2'就為假了。因此反之不一定成立。由此可得歸結式的性質。

歸結式的性質：歸結式C12 是親本子句C12 和C12的邏輯結論。

命題邏輯的歸結法證明過程

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

1.建立待歸結命題公式

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

求取合取范式建立子句集歸結

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

歸結步驟：

1)對子句集中的子句使用歸結規則

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

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

（證明完畢）

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

例題2-1

證明公式：

(P → Q)→(～Q → ～P)證明：根據歸結原理

將待證明公式轉化成待歸結命題公式：

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

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

P → Q ＝ ～P ∨ Q

結論求～后的后項化為合取范式：

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

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

（～P ∨ Q）∧～Q ∧ P

則子句集為：

{ ～P∨Q，～Q，P}

對子句集中的子句進行歸結可得：

1.～P∨Q

2.～Q

3.P

4.Q，（1，3歸結）

5.e，（2，4歸結）

由上可得原公式成立。

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

教師提示：命題邏輯基礎是學習歸結法的必要基礎，應該在前序的課程中學習過。這里列出的只是一些簡單的性質。如果大家對這些知識有什么疑惑的話，請參考數理邏輯的有關書籍。命題邏輯的歸結法的邏輯基礎是假言易位式和摩根律。

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

2.3 謂詞邏輯歸結法基礎

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

本節針對謂詞邏輯歸結法介紹了Skolem標準形、子句集等一些必要的概念和定理。

2．3．1 Skolem 標準形 Skolem標準形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為Skolem標準形，任何一個謂詞公式都可以化為與之對應的Skolem標準形。但是，Skolem標準形不唯一。

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

Skolem標準形的轉化過程為，依據約束變量換名規則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。具體步驟如下：

將謂詞公式G轉換成為前束范式

前束范式的形式為：

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

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

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

約束變量換名規則：

(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）

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

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

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

量詞轄域收縮與擴張等值式：

(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等）、或全稱變量的函數(f(x), g(y)等)代替。如果存在量詞左邊沒有任何全稱量詞，則只將其改寫成為常量；如果是左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數。

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

Skolem 定理：

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

注意：公式G的SKOLEM標準形同G并不等值。例題2-2

將下式化為Skolem標準形：

～(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)∧～(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的函數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標準形為：

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

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

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

子句集：所有子句的集合

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

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

1.謂詞公式G轉換成前束范式

2.消去前束范式中的存在變量，略去其中的任意變量，生成SKOLEM標準形

3.將SKOLEM標準形中的各個子句提出，表示為集合形式

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

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

謂詞表達式G是不可滿足的當且僅當 其子句集S是不可滿足的

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

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

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

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

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

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

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

2.3 謂詞邏輯歸結法基礎

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

本節針對謂詞邏輯歸結法介紹了Skolem標準形、子句集等一些必要的概念和定理。

2．3．1 Skolem 標準形

Skolem標準形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為Skolem標準形，任何一個謂詞公式都可以化為與之對應的Skolem標準形。但是，Skolem標準形不唯一。

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

Skolem標準形的轉化過程為，依據約束變量換名規則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。具體步驟如下：

將謂詞公式G轉換成為前束范式

前束范式的形式為：

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

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

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

約束變量換名規則：

(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）

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

(x)P（x）

(x)P（x）

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

量詞轄域收縮與擴張等值式：

(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等）、或全稱變量的函數(f(x), g(y)等)代替。如果存在量詞左邊沒有任何全稱量詞，則只將其改寫成為常量；如果是左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數。

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

Skolem 定理：

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

注意：公式G的SKOLEM標準形同G并不等值。例題2-2

將下式化為Skolem標準形：

～(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)∧～(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的函數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標準形為：

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

2.3.2子句集

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

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

子句集：所有子句的集合

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

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

1.謂詞公式G轉換成前束范式

2.消去前束范式中的存在變量，略去其中的任意變量，生成SKOLEM標準形

3.將SKOLEM標準形中的各個子句提出，表示為集合形式

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

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

定理

謂詞表達式G是不可滿足的當且僅當 其子句集S是不可滿足的

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

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

定理的推廣

對于形如G = G1Λ G2Λ G3Λ …Λ Gn 的謂詞公式，G的子句集的求取過程可以分解成幾個部分單獨處理。如果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。根據以上定理可對一個謂詞表達式分而治之，化整為零，大大減少了計算復雜度。

例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的祖父”，一階邏輯表達式如下：

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

則把A1化為合取范式，進而化為Skolem標準形，表示如下：

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

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

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

化為Skolem標準形，表示如下：

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

結論：某個人是它的祖父

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

否定后得到子句：

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

則得到的相應的子句集為：{ S A1，S A2，S～B }

解畢。

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

3.4 證據理論（D-S Theory）

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

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

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

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

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

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

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

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

m(Φ)= 0 空的為零

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

1（A屬于U）

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

基本概率函數的物理意義是：

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

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

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

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

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

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

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

· 似然函數Pl：2U →[0,1]

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

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

可見Bel是Pl的一部分。

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

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

f(1, 1)表示A為真

f(0, 0)表示A為假

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

f(1, 0)不可能成立

一般情況都是包含在這些特殊值的某一個區間中的?？梢愿鶕c這些特殊值的相對關系來判斷其可信程度。

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

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

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

且K-1 ≠ 0，若K-1 = 0，認為m1, m2矛盾。沒有聯合基本概率分配函數。例題

已知：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)

由于基本概率分配函數只定義在B集合和全集U之上，所以其它集合的分配函數值為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