謂詞演算中的歸結(jié)

謂詞演算中的歸結(jié)第一頁，共三十一頁，編輯于2023年，星期一合一合式公式(ξ1，ξ2，…，ξn)(λ1∨λ2∨…∨λk)，可縮寫為λ1∨λ2∨…∨λk，其中λ1，λ2，…λk是可能包含變量ξ1，ξ2，…，ξn的文字。也就是說，僅僅去掉了全稱量詞，并假定λi中任何變量全稱量化。這種縮寫形式的合式公式叫做子句。有時(shí)，用集合符號(hào)(λ1，λ2，…，λk)表達(dá)一個(gè)子句，并假定集合中的元素是析取的。如果兩個(gè)子句的文字相匹配但是互補(bǔ)，我們能歸結(jié)它們——就像在命題演算中一樣。如果一個(gè)子句中有一個(gè)文字λ(ξ)(ξ是一個(gè)變量)，而另一個(gè)子句中有一個(gè)互補(bǔ)文字﹁λ(τ)，τ是不包含ξ的某個(gè)項(xiàng)，我們能把第一個(gè)子句中的所有ξ用τ代替；然后對互補(bǔ)文字進(jìn)行命題歸結(jié)以產(chǎn)生那兩個(gè)子句的歸結(jié)式。第二頁，共三十一頁，編輯于2023年，星期一合一舉例：考慮兩個(gè)子句:P(f(y)，A)∨Q(B，C)﹁P(x，A)∨R(x，C)∨S(A，B)。用f(y)代替第二個(gè)子句中的x產(chǎn)生:﹁P(f(y)，A)∨R(f(y)，C)∨S(A，B)?，F(xiàn)在，兩個(gè)子句中的第一個(gè)文字剛好互補(bǔ)，因此我們能對文字(f(y)，A)執(zhí)行一次歸結(jié)，產(chǎn)生歸結(jié)式:R(f(y)，C)∨S(A，B)∨Q(B，C)。

用一個(gè)被稱為合一的方法計(jì)算適當(dāng)?shù)闹脫Q。合一在AI中是一個(gè)極其重要的方法。第三頁，共三十一頁，編輯于2023年，星期一合一為了描述合一，必須先討論一下置換:一個(gè)表達(dá)式項(xiàng)可能是變量符號(hào)、對象常量或者函數(shù)表達(dá)式，后者包含函數(shù)常量和表達(dá)式項(xiàng)。一個(gè)表達(dá)式的置換實(shí)例通過置換那個(gè)表達(dá)式中的變量項(xiàng)而得到。因此，P[x，f(y)，B]的四個(gè)置換實(shí)例是：

P[z，f(w)，B]P[x，f(A)，B]P[g(z)，f(A)，B]P[C，f(A)，B]

上面第一個(gè)實(shí)例稱為原始文字的字母變種(alphabeticvariant)，因?yàn)槲覀儍H僅用另外的變量代替了P[x，f(y)，B]中出現(xiàn)的變量。第4個(gè)叫基例(groundinstance)，因?yàn)槲淖种袥]有一項(xiàng)包含變量(一個(gè)基項(xiàng)是一個(gè)不包含任何變量的項(xiàng))。

第四頁，共三十一頁，編輯于2023年，星期一合一我們能通過一組有序?qū)={τ1/ξ1，τ2/ξ2，…，τn/ξn}來表達(dá)任何置換。τi/ξi對意思是說τi項(xiàng)替換在整個(gè)置換范圍內(nèi)的ξi的每次出現(xiàn)。而且，變量不能被一個(gè)包含相同變量的項(xiàng)代替。使用前面P[x，f(y)，B]的四個(gè)實(shí)例的置換是：

s1＝{z/x，w/y}s2＝{A/y}s3＝{g(z)/x，A/y}s4＝{C/x，A/y}上面是用ωs來指稱一個(gè)使用置換s的表達(dá)式ω的一個(gè)置換實(shí)例。因此，P[z，f(w)，B]=P[x，f(y)，B]s1。

P[z，f(w)，B]P[x，f(A)，B]P[g(z)，f(A)，B]P[C，f(A)，B]第五頁，共三十一頁，編輯于2023年，星期一合一

兩個(gè)置換s1和s2的組合用s1s2指稱，它指的是這個(gè)置換通過先把s2應(yīng)用到s1各項(xiàng)，再加上不含出現(xiàn)在s1中變量的所有s2對而得到，因此；

{

g(x，y)/z}{A/x，B/y，C/w，D/z}＝{g(A，B)/z，A/x，B/y，C/w}

{f(y)/x,z/y}{a/x,b/y,y/z}={f(b)/x,y/z}可以看出，把s1和s2連續(xù)地應(yīng)用到ω表達(dá)式和把s1s2應(yīng)用到ω是相同的，即：(ωs1)s2＝ω(sls2)。也能看出，置換組合是符合結(jié)合律的。即：(s1s2)s3＝s1(s2s3)。

舉例:ω是P(x，y)，s1是{

f(y)／x}，s2是{

A／y}。那么(ωs1)s2＝[p(f(y)，y)]{A／y}＝P(f(A)，A)和ω(s1s2)＝[P(x，y)]{f(A)／x，A／y}＝P(f(A)，A)第六頁，共三十一頁，編輯于2023年，星期一合一一般地講，置換不符合交換律，即s1s2＝s2s1是不成立的。因此，改變應(yīng)用置換順序會(huì)產(chǎn)生差異。例如：ω是P(x，y)，s1是{f(y)／x}，s2是{A／y}。那么ω(s1s2)＝P(f(A)，A)ω(s2s1)＝[P(x，y)]{A／y，f(y)／x}＝P(f(y)，A)第七頁，共三十一頁，編輯于2023年，星期一合一當(dāng)一個(gè)置換s被應(yīng)用到一個(gè)表達(dá)式集合{ωi}的每一個(gè)成員時(shí)，用{ωi}s表示置換實(shí)例集合。如果存在一個(gè)置換s，它使ω1s=ω2s=ω3s＝…，我們說表達(dá)式集合{ωi}是可以合一的(unifiable)。在這種情況下，s被稱為{ωi}的一個(gè)合一式(unifier)，因?yàn)樗氖褂冒鸭蠅嚎s成為一個(gè)單元素集合。例如：s＝{A／x，B／y}把集合{p[x，f(y)，B]，P[x，f(B)，B]}合一產(chǎn)生{

p[A，f(B)，B]}。

最一般(或最簡單)的合一式(mgu){ωi}的g有下面的特性：如果s是產(chǎn)生{ωi}s的{ωi}的任意合一式，那么存在一個(gè)置換s′以使{ωi}s＝{ωi}gs′。而且，經(jīng)一個(gè)最一般的合一式產(chǎn)生的通用實(shí)例除了字母變化外是惟一的。

第八頁，共三十一頁，編輯于2023年，星期一合一

有很多算法可以用來找到一個(gè)可以合一的表達(dá)式的有限集合的mgu，并且當(dāng)那個(gè)集合不能被合一時(shí)能返回失敗。這里給出的算法UNIFY工作在一個(gè)列表結(jié)構(gòu)的表達(dá)式集合上，在這些表達(dá)式中，每個(gè)文字和項(xiàng)作為一個(gè)列表項(xiàng)。例如：﹁P(x，f(A，y)寫為(﹁Px(fAy))列表結(jié)構(gòu)形式，表達(dá)式﹁P是列表中的第一個(gè)頂級表達(dá)式，(fAy)是第三個(gè)頂級表達(dá)式。

UNIFY的基礎(chǔ)是分歧集(disagreementset)的思想。一個(gè)非空的表達(dá)式集合W的分歧集由下面的方法得到：首先定位第一個(gè)符號(hào)(從左邊計(jì)數(shù))，如果在這個(gè)位置不是W中的所有表達(dá)式有完全相同的符號(hào)，那么從W的每個(gè)表達(dá)式中提取從占據(jù)那個(gè)位置的符號(hào)開始的子表達(dá)式，各個(gè)子表達(dá)式集合構(gòu)成W的分歧集。例如，兩個(gè)列表((﹁Px(fAy))，(﹁Px(fzB)))集合的分歧集是{A，z}。分歧集能用置換A／z產(chǎn)生協(xié)調(diào)。第九頁，共三十一頁，編輯于2023年，星期一合一UNIFY(Γ)(Γ是一個(gè)列表表達(dá)式集合)1)k←0，Γk←Γ，σk←ε(初始化步驟；ε是空的置換)。2)如果Γk是一個(gè)單元素集合，用Γ的mguσk退出；否則繼續(xù)。3)Dk←Γk的分歧集。4)如果在Dk中存在元素vk和tk，vk是一個(gè)不會(huì)出現(xiàn)在tk中的變量，則繼續(xù)；否則，失敗退出，Γ是不可以合一的。5)σk+1←σk{tk/vk}，Γk+1←{tk／vk}(注意Γk+1=Γkσk+1)。6)k←k+17)轉(zhuǎn)到第2步。第十頁，共三十一頁，編輯于2023年，星期一合一例：設(shè)F={P(a，x，f(g(y)))，P(z，f(z)，f(u))}，求其合一。1）令σ0=,F0=F,因F0中含有兩個(gè)表達(dá)式，所以σ0不是最一般合一。2）分歧集D0={a，z}.3)σ1=σ0

{a/z}={a/z}F1={P(a，x，f(g(y)))，P(a，f(a)，f(u))}4)D1={x,f(a)}5)σ2=σ1{f(a)/x}={a/z,f(a)/x}F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))}6)D2={g(y),u}7)σ3=σ2{g(y)/u}={a/z,f(a)/x,g(y)/u}第十一頁，共三十一頁，編輯于2023年，星期一合一8)F3=F2{g(y)/u}={P(a,f(a),f(g(y)))}.

因?yàn)镕3只含一個(gè)表達(dá)式，所以σ0就是最一般合一，即{a/z,f(a)/x,g(y)/u}是最一般合一。第十二頁，共三十一頁，編輯于2023年，星期一謂詞演算歸結(jié)

假如γ1和γ2是兩個(gè)子句(表示為文字集合)。如果γ1中有一個(gè)原子ф，γ2中有一個(gè)文字﹁ψ，并使ф和ψ有一個(gè)最一般合一式(mgu)，那么這兩個(gè)子句有一個(gè)歸結(jié)式ρ，它通過把置換μ與γ1和γ2減去互補(bǔ)其文字的并集而得到。即：ρ=[（γ1-{ф}）∪（γ2-{﹁ψ}）]μ

第十三頁，共三十一頁，編輯于2023年，星期一謂詞演算歸結(jié)

在兩個(gè)子句被歸結(jié)前，為了避免變量混淆，我們對每個(gè)子句中的變量重命名以使一個(gè)子句中的變量不會(huì)出現(xiàn)在另一個(gè)中。例如：假如我們正在歸結(jié)P(x)∨Q(f(x))與R(g(x))∨﹁Q(f(A))，首先重寫第二個(gè)子句，比如說為R(g(y))∨﹁Q(f(A))，然后執(zhí)行歸結(jié)獲得P(A)∨R(g(y))。變量重命名被稱為對變量進(jìn)行標(biāo)準(zhǔn)化(standardizingthevariablesapart)。

下面是一些例子:

{P(x)，Q(x，y)}和{﹁P(A)，R(B，z)}歸結(jié)產(chǎn)生:

{Q(A，y)，R(B，z)}。

{P(x，x)，Q(x)，R(x)}和{﹁P(A，z)，﹁Q(B)}可用兩種不同的方式歸結(jié)，分別產(chǎn)生{Q(A)，R(A)，﹁Q(B)}和{P(B，B)，R(B)，﹁P(A，z)}。第十四頁，共三十一頁，編輯于2023年，星期一謂詞演算歸結(jié)

有時(shí)需要對謂詞演算歸結(jié)有一個(gè)稍強(qiáng)的定義。例如，考慮兩個(gè)子句{P(u)，P(v)}和{﹁P(x)，P(y)}。這兩個(gè)子句各自有基例P(A)和﹁P(A)(由置換A／u，A／v，A／x，A／y獲得)。從這些基例中，能推斷出空子句，因此我們應(yīng)該能從初始子句推斷它，但是剛剛給定的歸結(jié)規(guī)則不能做到這些。更強(qiáng)的規(guī)則如下:假定γ1和γ2是兩個(gè)子句(再次表示為文字集合)。如果有γ1的一個(gè)子集γ′1和γ2的一個(gè)子集γ′2，使得γ′1的文字能與γ′2的文字的否定式用最一般合一式μ合一，那么這兩個(gè)子句有一個(gè)歸結(jié)式ρ，它通過把置換μ與γ1和γ2減去其互補(bǔ)子集的并集而得到。即：ρ=[(γ1-γ′1)∪(γ2-γ′2)]μ用這個(gè)歸結(jié)定義，歸結(jié)子句{P(u),P(v)}和{﹁P（x），﹁P(y)}產(chǎn)生空子句。第十五頁，共三十一頁，編輯于2023年，星期一完備性和合理性

謂詞演算的歸結(jié)是合理的。也就是說，如果ρ是兩個(gè)子句ф和ψ歸結(jié)式，那么{ф，ψ}?

ρ。這個(gè)事實(shí)的證明不比命題歸結(jié)的合理性證明難。

第十六頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

就像在命題演算中一樣，任何合式公式能被轉(zhuǎn)化為子句形式。步驟如下：

1)消除蘊(yùn)含符號(hào)(如在命題演算中一樣)。

2)減少否定符號(hào)的范圍(如在命題演算中一樣)。

3)變量標(biāo)準(zhǔn)化，由于量詞范圍內(nèi)的變量像“啞元”，因此它們能被更名，以使每個(gè)量詞有它自己的變量符號(hào)。舉例：可以改寫為:第十七頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

4)取消存在量詞。

舉例：在中，存在量詞(y)在一個(gè)全稱量詞(x)范圍內(nèi)，因此，y的“存在”可能依賴x的值。例如，如果的意思是“每個(gè)人x有身高y”，那么很明顯身高與人有關(guān)。用某個(gè)未知的函數(shù)h(x)顯式定義這個(gè)依賴關(guān)系，h(x)把x的每個(gè)值映射為存在的y值。這樣的一個(gè)函數(shù)叫做Skolem函數(shù)。如果我們把Skolem函數(shù)用在y存在的位置，就能取消存在量詞，并寫為第十八頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

從一個(gè)合式公式中消除一個(gè)存在量詞的一般規(guī)則是用一個(gè)Skolem函數(shù)代替存在量詞作用范圍內(nèi)變量的每一次出現(xiàn)，Skolem函數(shù)的參數(shù)是那些被全稱量詞約束的變量，全稱量詞的范圍包括要被消除的存在量詞的范圍。用在Skolem函數(shù)中的函數(shù)符號(hào)必須是“新的”，不能是已經(jīng)出現(xiàn)在任何合式公式中被用在歸結(jié)反駁中的符號(hào)。因此，我們能從

經(jīng)消除(z)，產(chǎn)生第十九頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

我們能從

經(jīng)消除(w)，產(chǎn)生

其中g(shù)(X，y)和h(x)都是Skolem函數(shù)。如果要被消除的存在量詞不在任何全稱量詞的范圍內(nèi)，那么我們使用一個(gè)沒有參數(shù)的Skolem函數(shù)，它只是y一個(gè)常量。因此，(x)P(x)成為P(Sk)，常量符號(hào)Sk(用來指向我們知道存在的那個(gè)項(xiàng)。另外，Sk是一個(gè)新的符號(hào)常量且沒有用在其他函數(shù)中，這是必要的。第二十頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

為了從一個(gè)合式公式中消除所有的存在量化變量，依次對每個(gè)子公式使用前述的過程。從一組合式公式中消除存在量詞產(chǎn)生公式集合的Skolem范式。注意，一個(gè)合式公式的Skolem范式并不等價(jià)于原始的合式公式！公式(

x)P(x)被它的Skolem范式P(Sk)邏輯涵蘊(yùn)，但反過來就不行。作為另一個(gè)例子，注意[P(A)∨P(B)]?

(x)P(x)，但是[P(A)∨P(B)]?

P(Sk)。公式集合Δ是可以滿足的，當(dāng)且僅當(dāng)Δ的Skolem范式是可以滿足的?；蛘?，對歸結(jié)反駁更有用的是，Δ是不可滿足的，當(dāng)且僅當(dāng)Δ的Skolem范式是不可滿足。

第二十一頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

5)轉(zhuǎn)化為前束范式。在這個(gè)階段，沒有任何殘留的存在量詞，每個(gè)全稱量詞有它自己的變量符號(hào)?，F(xiàn)在，我們可以把所有的全稱量詞移到合式公式的前面，并且讓每個(gè)量詞的范圍包括跟隨它的合式公式的全部。這樣的合式公式被稱為是在前束范式中。前束范式的一個(gè)合式公式包括一個(gè)稱為前束范式的量詞，它后面跟隨一個(gè)稱為矩陣(matrix)的沒有量詞的公式。

合式公式：的前束范式是：

第二十二頁，共三十一頁，編輯于2023年，星期一

6)將矩陣寫成一個(gè)合取范式。像命題演算一樣，我們可以通過重復(fù)使用分配律，用代替，把任何矩陣改寫成合取范式。將前述合式公式例子的矩陣改寫成合取范式，它變?yōu)?/p>

7)消除全稱量詞。由于用在合式公式中的所有變量必須是在一個(gè)量詞范圍內(nèi)，保證在這一步保留的所有變量都被全稱量化。而且，全稱量化的順序并不重要，因此可以刪去明確出現(xiàn)的全稱量詞，并且根據(jù)約定可以保證矩陣中的所有變量都被全稱量化?，F(xiàn)在，只留下了一個(gè)合取范式的矩陣。

把任意的合式公式轉(zhuǎn)化為子句形式

第二十三頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

8)消除∧符號(hào)?？梢杂煤鲜焦郊蟵ω1，ω2}代替表達(dá)式(ω1∧ω2)，刪除顯式出現(xiàn)的∧符號(hào)。重復(fù)代替的結(jié)果是獲得一個(gè)有限的合式公式集合，合式公式中的每一項(xiàng)是一個(gè)文字析取項(xiàng)。只包含文字析取項(xiàng)的任何合式公式被稱為一個(gè)子句，我們的合式公式例子被轉(zhuǎn)化為下面的子句集合：﹁P(x)∨﹁P(y)∨P[f(x,y)]﹁P(x)∨Q[x,h(x)]﹁P(x)∨﹁P[h(x)]第二十四頁，共三十一頁，編輯于2023年，星期一把任意的合式公式轉(zhuǎn)化為子句形式

9)變量更名。變量符號(hào)可以被更名，以使沒有任何變量符號(hào)出現(xiàn)在多于一個(gè)的子句中。注意到(?

x)[P(x)∧Q(x)]等價(jià)于[(?

x)P(x)∧((?

y)Q(y))?，F(xiàn)在子句是：﹁P(x1)∨﹁P(y)∨P[f(xl，y)]﹁P(x2)∨Q[x2，h(x2)]﹁P(x3)∨P[h(x3)]

一個(gè)子句的文字可以包含變量，但這些變量總是被理解為是全稱量化的。第二十五頁，共三十一頁，編輯于2023年，星期一用歸結(jié)證明定理當(dāng)歸結(jié)用作一個(gè)定理證明系統(tǒng)的推論規(guī)則時(shí)，可以將要從中證明一個(gè)定理的合式公式集合首先轉(zhuǎn)化成子句?？梢宰C明如果合式公式ω從一個(gè)合式公式集合Δ中邏輯地產(chǎn)生，那么同樣也從Δ中的合式公式轉(zhuǎn)換成的子句集合中邏輯地產(chǎn)生。反之亦然。因此，子句是一個(gè)表達(dá)謂詞演算合式公式的完備的通用形式。

假如機(jī)器人知道27號(hào)房間中的所有箱子都比28號(hào)房間中的小。即：1)(?x，y){Package(x)∧Package(y)∧Inroom(x，27)∧Inroom(y，28)]?Smaller(x，y)}

第二十六頁，共三十一頁，編輯于2023年，星期一縮寫謂詞符號(hào)使公式緊湊。轉(zhuǎn)換為子句形式，產(chǎn)生：2)﹁P(x)∨﹁P(y)∨﹁I(x，27)∨﹁I(y，28)∨S(x，y)

假定機(jī)器人知道箱子A在27號(hào)或28號(hào)房間中(但不知道是哪一個(gè))。它知道箱子B在房間27中且B不比A小。3)P(A)

4)P(B)5)I(A，27)∨I(A，28)6)I(B，27)7)﹁S(B，A)用歸結(jié)反駁，機(jī)器人能證明箱