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

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

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

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

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

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

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

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

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

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

前束范式的形式為：

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

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

注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達(dá)式中的所有同名變量。所以將量詞提到公式最前端時(shí)存在約束變量換名問(wèn)題。要嚴(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è)個(gè)體域?yàn)橛懈F集合（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)等)代替。如果存在量詞左邊沒(méi)有任何全稱量詞，則只將其改寫(xiě)成為常量；如果是左邊有全程量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為全程量詞的函數(shù)。

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

Skolem 定理：

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

注意：公式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))

解：

第一步，消去→號(hào)，得：

～(～(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)))

第四步，變?cè)酌?，存在量詞左移，直至所有的量詞移到前面，得：

(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)，因?yàn)樗筮呏挥?”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子句集

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

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

子句集：所有子句的集合

對(duì)于任一個(gè)公式G，都可以通過(guò)Skolem標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)化建立起一個(gè)子句集與之相對(duì)應(yīng)。因?yàn)樽泳洳贿^(guò)是一些文字的析取，是一種比較簡(jiǎn)單的形式，所以對(duì)G的討論就用對(duì)子句集S的討論來(lái)代替，以便容易處理。

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

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

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

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

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

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

定理

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

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

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

定理的推廣

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

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

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

即SG 不可滿足

由上面的定理，我們對(duì)SG的討論，可以用較為簡(jiǎn)單的S1 ∪ S2 ∪ S3 ∪ …∪ Sn來(lái)代替。為方便起見(jiàn)，也稱S1 ∪ S2 ∪ S3 ∪ …∪ Sn為G的子句形，即：

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

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

例2－3

對(duì)所有的x,y,z來(lái)說(shuō)，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個(gè)人都有父親，試問(wèn)對(duì)某個(gè)人來(lái)說(shuō)誰(shuí)是它的祖父？

用一階邏輯表示這個(gè)問(wèn)題，并建立子句集。

解：

這里我們首先引入謂詞：

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

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

ANS(x)表示問(wèn)題的解答

于是有：

對(duì)于第一個(gè)條件，“如果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)

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

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

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

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

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

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

否定后得到子句：

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

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

解畢。

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

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

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

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

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

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

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

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

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

前束范式的形式為：

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

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

注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達(dá)式中的所有同名變量。所以將量詞提到公式最前端時(shí)存在約束變量換名問(wèn)題。要嚴(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è)個(gè)體域?yàn)橛懈F集合（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)等)代替。如果存在量詞左邊沒(méi)有任何全稱量詞，則只將其改寫(xiě)成為常量；如果是左邊有全程量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為全程量詞的函數(shù)。

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

Skolem 定理：

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

注意：公式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))

解：

第一步，消去→號(hào)，得：

～(～(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)))

第四步，變?cè)酌嬖诹吭~左移，直至所有的量詞移到前面，得：

(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)，因?yàn)樗筮呏挥?”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子句集

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

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

子句集：所有子句的集合

對(duì)于任一個(gè)公式G，都可以通過(guò)Skolem標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)化建立起一個(gè)子句集與之相對(duì)應(yīng)。因?yàn)樽泳洳贿^(guò)是一些文字的析取，是一種比較簡(jiǎn)單的形式，所以對(duì)G的討論就用對(duì)子句集S的討論來(lái)代替，以便容易處理。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 歸結(jié)原理

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

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

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

個(gè)體詞：表示主語(yǔ)的詞

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

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

個(gè)體常量：a,b,c

個(gè)體變量：x,y,z

謂詞符號(hào)：P,Q,R

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

置換：置換可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變量。

定義：

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

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

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

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

定義：置換的合成

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

即對(duì)ti先做λ置換然后再做θ置換，置換xi

中刪去以下兩種元素：

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

ii.當(dāng)yi∈{x1,x2, …, xn}時(shí)，刪去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，需要?jiǎng)h除；a/x，a/y滿足定義中的條件ii，也需要?jiǎng)h除。最后得

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

合一：合一可以簡(jiǎn)單地理解為“尋找相對(duì)變量的置換，使兩個(gè)謂詞公式一致”。

定義：

設(shè)有公式集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若存在一個(gè)置換θ，可使F1θ＝F2θ＝…= Fnθ，則稱θ是F的一個(gè)合一。同時(shí)稱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}是它的一個(gè)合一。

注意：一般說(shuō)來(lái)，一個(gè)公式集的合一不是唯一的。

定義：最一般合一

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

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

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

2.4.2 歸結(jié)式

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

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

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

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

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

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

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

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

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

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

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

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

例：

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

解：

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

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

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

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

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

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

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

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

·求取子句集S

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

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

·得到空子句

·命題得證 例題2-4

“快樂(lè)學(xué)生”問(wèn)題：

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

解：

先將問(wèn)題用謂詞表示如下：

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

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

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

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

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

～Study(zhang)∧Lucky(zhang)

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

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

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

～Happy(zhang)

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

首先將每一個(gè)表示邏輯條件的謂詞子句轉(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é)法的實(shí)質(zhì)：

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

·歸結(jié)的過(guò)程是一個(gè)語(yǔ)義樹(shù)倒塌的過(guò)程。

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

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

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

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

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

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

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

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

命題：非真即假的簡(jiǎn)單陳述句

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

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

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

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

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

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

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

q

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

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

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

·析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式

·合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式

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

下面這些基本的等式在歸結(jié)原理實(shí)施之前的公式轉(zhuǎn)化過(guò)程中是非常重要的。只有將邏輯公式正確轉(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

·等價(jià)等值式：pq

·假言易位式: p → q

·等價(jià)否定等值式：pq

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

－合取范式

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

合取范式：?jiǎ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)換成為各個(gè)“或”語(yǔ)句的“與”，不然后續(xù)推導(dǎo)沒(méi)有意義。轉(zhuǎn)換是基于數(shù)理邏輯的基本等值公式進(jìn)行的，“或”轉(zhuǎn)換到“與”中。思路與代數(shù)學(xué)的提取公因式方法相似。

－子句集

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

子句集是合取范式中各個(gè)合取分量的集合，生成子句集的過(guò)程可以簡(jiǎn)單地理解為將命題公式的合取范式中的與符號(hào)“∧”，置換為逗號(hào)“，”。

上例轉(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é)法推理的核心是求兩個(gè)子句的歸結(jié)式，因此需要先討論歸結(jié)式的定義和性質(zhì)。

歸結(jié)式的定義

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

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

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

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

下面證明歸結(jié)式是原兩子句的邏輯推論，或者說(shuō)任一使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)成立。

反之不一定成立，因?yàn)榇嬖谝粋€(gè)使C1'∨C2'為真的解釋I，不妨設(shè)C1'為真，C2'為假。若P為真，則～P∨C2'就為假了。因此反之不一定成立。由此可得歸結(jié)式的性質(zhì)。

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

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

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

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

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

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

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

歸結(jié)步驟：

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

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

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

（證明完畢）

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

例題2-1

證明公式：

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

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

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

分別將公式前項(xiàng)化為合取范式：

P → Q ＝ ～P ∨ Q

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

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

兩項(xiàng)合并后化為合取范式：

（～P ∨ Q）∧～Q ∧ P

則子句集為：

{ ～P∨Q，～Q，P}

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

1.～P∨Q

2.～Q

3.P

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

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

由上可得原公式成立。

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

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

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

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

證據(jù)理論由Dempster首先提出，并由他的學(xué)生Shafer發(fā)展起來(lái)，也稱D-S理論。在專家系統(tǒng)的不精確推理中已得到廣泛的應(yīng)用, 也用在模式識(shí)別系統(tǒng)中。證據(jù)理論中引入了信任函數(shù)，它滿足概率論弱公理。在概率論中，當(dāng)先驗(yàn)概率很難獲得，但又要被迫給出時(shí)，用證據(jù)理論能區(qū)分不確定性和不知道的差別。所以它比概率論更合適于專家系統(tǒng)推理方法。當(dāng)概率值已知時(shí)，證據(jù)理論就成了概率論。因此，概率論是證據(jù)理論的一個(gè)特例，有時(shí)也稱證據(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ù)理論實(shí)現(xiàn)的程序Dempster Shafer Engine下載。有興趣的讀者可以安裝這一軟件，看看運(yùn)行效果。這是我們已經(jīng)下載下來(lái)的程序包：DempsterShaferEngine.zip。3.4.1 證據(jù)的不確定性

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

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

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

證據(jù)理論定義了多個(gè)函數(shù)值來(lái)描述證據(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，表示對(duì)A的精確信任度

若A等于U，表示這個(gè)數(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ù)值的和。表示對(duì)A的總信任度。

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

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

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

可見(jiàn)Bel是Pl的一部分。

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

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

f(1, 1)表示A為真

f(0, 0)表示A為假

f(0, 1)表示對(duì)A一無(wú)所知

f(1, 0)不可能成立

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

此外，還可以用函數(shù)f1(A)來(lái)衡量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矛盾。沒(méi)有聯(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）然后計(jì)算：

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