人工智能原理教案02章 歸結(jié)推理方法2歸結(jié)推理方法課件

第二章歸結(jié)推理方法

課前指導(dǎo)2.1歸結(jié)原理概述2.2命題邏輯的歸結(jié)2.3謂詞邏輯歸結(jié)法基礎(chǔ)2.4歸結(jié)原理2.5歸結(jié)過程控制策略2.6Herbrand定理章節(jié)小結(jié)第二章歸結(jié)推理方法課前指導(dǎo)1課前指導(dǎo)【學(xué)習(xí)目標(biāo)】

本章主要討論命題邏輯和一元謂詞邏輯的歸結(jié)推理方法。同學(xué)需要在熟練掌握一般邏輯知識的基礎(chǔ)上，學(xué)習(xí)Skolem標(biāo)準(zhǔn)形和Herbrand定理，從而對歸結(jié)原理有一個比較透徹的了解?！緦W(xué)習(xí)指南】

在學(xué)習(xí)新知識的同時回顧以前所學(xué)的一般邏輯知識。對所涉及的概念和方法不要死記硬背，對于比較抽象的概念，可以通過比較簡單的例子來理解?！倦y重點(diǎn)】

應(yīng)該熟練掌握把邏輯公式的合取范式、Skolem標(biāo)準(zhǔn)形的轉(zhuǎn)化方法、歸結(jié)法進(jìn)行歸結(jié)的過程，掌握線性歸結(jié)、支撐集歸結(jié)等歸結(jié)策略。課前指導(dǎo)【學(xué)習(xí)目標(biāo)】

本章主要討論命題邏輯和一元謂詞邏輯2【知識點(diǎn)】

歸結(jié)方法的特點(diǎn)、與其它推理方法的比較

命題邏輯基礎(chǔ)，前束范式，約束變量換名規(guī)則

Skolem標(biāo)準(zhǔn)形的定義，子句和子句集，定理的內(nèi)容及推廣

H域、H解釋、語義樹

合一和置換，歸結(jié)過程

歸結(jié)法的控制策略的原則及基本方法。【知識點(diǎn)】3歸結(jié)推理知識結(jié)構(gòu)歸結(jié)推理知識結(jié)構(gòu)42.1歸結(jié)原理概述歸結(jié)原理由J.A.Robinson于1965年提出，又稱為消解原理。該原理是Robinson在Herbrand理論基礎(chǔ)上提出的一種基于邏輯的、采用反證法的推理方法。由于其理論上的完備性，歸結(jié)原理成為機(jī)器定理證明的主要方法。注意：本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題本章首先介紹命題邏輯的歸結(jié)，并以此為基礎(chǔ)介紹謂詞邏輯的歸結(jié)過程及相關(guān)的思想、概念和定義，最后給出謂詞邏輯歸結(jié)的基礎(chǔ)Herbrand定理的一般形式。2.1歸結(jié)原理概述歸結(jié)原理由J.A.Robinson于195定理證明的實(shí)質(zhì)與困難從某種意義上講大部分人工智能問題都可以轉(zhuǎn)化為一個定理證明問題。定理證明的實(shí)質(zhì)：就是要對給出的（已知的）前提和結(jié)論，證明此前提推導(dǎo)出該結(jié)論這一事實(shí)是永恒的真理。這是非常困難的，幾乎是不可實(shí)現(xiàn)的。困難所在：要證明在一個論域上一個事件是永真的，就要證明在該域中的每一個點(diǎn)上該事實(shí)都成立。很顯然，論域是不可數(shù)時，該問題不可能解決。即使可數(shù)，如果該輪域是無限的，問題也無法簡單地解決。Herbrand采用了反證法的思想，將永真性的證明問題轉(zhuǎn)化成為不可滿足性的證明問題。Herbrand理論為自動定理證明奠定了理論基礎(chǔ)，而Robinson的歸結(jié)原理使得自動定理證明得以實(shí)現(xiàn)。因此，歸結(jié)推理方法在人工智能推理方法中有著很重要的歷史地位。定理證明的實(shí)質(zhì)與困難從某種意義上講大部分人工智能問題都可以轉(zhuǎn)6歸結(jié)法的特點(diǎn)與演繹法完全不同，歸結(jié)法是一種新的邏輯演算算法。它是一階邏輯中，至今為止的最有效的半可判定的算法。也是最適合計(jì)算機(jī)進(jìn)行推理的邏輯演算方法。半可判定，即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定（證明其為永真式）。歸結(jié)法的特點(diǎn)與演繹法完全不同，歸結(jié)法是一種新的邏輯演算算法。7歸結(jié)法基本原理歸結(jié)法的基本原理：是采用反證法或者稱為反演推理方法，將待證明的表達(dá)式（定理）轉(zhuǎn)換成為邏輯公式（謂詞公式），然后再進(jìn)行歸結(jié)，歸結(jié)能夠順利完成，則證明原公式（定理）是正確性的。例如：

由命題邏輯描述的命題：A1、A2、A3和B，要求證明：如果A1ΛA2ΛA3成立，則B成立，

即：A1ΛA2ΛA3→B是重言式（永真式）。歸結(jié)法的思路：A1ΛA2ΛA3→B是重言式等價于A1ΛA2ΛA3Λ～B是矛盾式，也就是說永假式。反證法：證明A1ΛA2ΛA3Λ～B是矛盾式

（永假式）歸結(jié)的目的：建立基本規(guī)則證明該條定理（事實(shí)）成立。歸結(jié)法基本原理歸結(jié)法的基本原理：是采用反證法或者稱為反演推理8歸結(jié)法和其它推理方法的比較

語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等知識表示方法的推理都是以邏輯推理方法為前提的。即，有了規(guī)則和已知條件，就能夠依據(jù)一定的規(guī)則和公理順藤摸瓜找到結(jié)果。而歸結(jié)方法是計(jì)算機(jī)自動推理、自動推導(dǎo)證明用的推理方法。（同樣的內(nèi)容可以在“數(shù)學(xué)定理機(jī)器證明”中找到。）歸結(jié)法和其它推理方法的比較語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等92.2命題邏輯的歸結(jié)2.2.1命題邏輯基礎(chǔ)邏輯可分為經(jīng)典邏輯和非經(jīng)典邏輯經(jīng)典邏輯包括命題邏輯和謂詞邏輯。歸結(jié)原理是一種主要基于謂詞（邏輯）知識表示的推理方法，而命題邏輯是謂詞邏輯的基礎(chǔ)。因此，在討論謂詞邏輯之前，先討論命題邏輯的歸結(jié)，便于內(nèi)容上的理解。本節(jié)中，將主要介紹命題邏輯的歸結(jié)方法，以及有關(guān)的一些基礎(chǔ)知識和重要概念，如數(shù)理邏輯基本公式變形、前束范式、子句集等。2.2命題邏輯的歸結(jié)2.2.1命題邏輯基礎(chǔ)10命題例子命題：非真即假的簡單陳述句。簡單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1、1+1=2.2、雪是黑色的。

3、北京是中國的首都。

4、到冥王星去度假。判斷一個句子是否是命題，首先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現(xiàn)在是假，隨著人類科學(xué)的發(fā)展，有可能變成真。但不管怎樣，真值是唯一的。因此以上例子都是命題。而例如：1、快點(diǎn)走吧！

2、到哪去？

3、X+Y>10等等句子，都不是命題。命題例子命題：非真即假的簡單陳述句。11命題表示公式（1）如何將陳述句轉(zhuǎn)化成命題公式？例如：設(shè)“下雨”為p，“騎車上班”為q，1、“只要不下雨，我騎自行車上班”。

p是q的充分條件，因而，可得命題公式：pq2、“只有不下雨，我才騎自行車上班”。p是q必要條件，因而，可得命題公式：qp命題表示公式（1）如何將陳述句轉(zhuǎn)化成命題公式？12命題表示公式（2）1、“如果我進(jìn)城我就去看你，除非我很累。”設(shè)：p，我進(jìn)城；q，去看你；r，我很累。則有命題公式：

r(pq)2、“應(yīng)屆高中生，得過數(shù)學(xué)或物理競賽的一等獎，保送上北京大學(xué)?！痹O(shè)：p，應(yīng)屆高中生；p，保送上北京大學(xué)；r，得過數(shù)學(xué)一等獎；t，得過物理一等獎。則有命題公式：

p(rt)q命題表示公式（2）1、“如果我進(jìn)城我就去看你，除非我很累?！?3數(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ù)理邏輯的基本定義合取式：p與q，記做p∧q14數(shù)理邏輯的基本等值式（24個）交換律：p∨qq∨p；

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

(p∧q)∧rp∧(q∧r)分配律：p∨(q∧r)(p∨q)∧(p∨r)；

p∧(q∨r)(p∧q)∨(p∧r)雙重否定律：p

～～p等冪律：pp∨p；pp∧p摩根律:～(p∨q)

～p∧～q；

～(p∧q)

～p∨～q吸收律:p∨(p∧q)p；

p∧(p∨q)p數(shù)理邏輯的基本等值式（24個）交換律：p∨qq∨p；15同一律:p∨0p；

p∧1p零律：p∨11

p∧00排中律：p∨～p1矛盾律：p∧～p0蘊(yùn)含等值式：p→q

～p∨q等價等值式：pq(p→q)∧(q→p)假言易位式:p→q

～p→～q等價否定等值式：pq～p～q歸謬論：(p→q)∧(p→～q)～p同一律:p∨0p；

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

如：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é)的提取公因式方法相似。合取范式合取范式：單元子句、單元子句的或（∨）的與（∧）。

17子句集命題公式的子句集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}子句集命題公式的子句集S是合取范式形式下的子命題（元素）的集182.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，反之不一定成立。2.2.2命題邏輯的歸結(jié)歸結(jié)法推理的核心是求兩個子句的歸結(jié)19歸結(jié)式是原兩子句的邏輯推論證明歸結(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)成立。反之不一定成立，因?yàn)榇嬖谝粋€使C1‘∨C2’為真的解釋I，不妨設(shè)C1‘為真，C2’為假。若P為真，則～P∨C2‘就為假了。因此反之不一定成立。由此可得歸結(jié)式的性質(zhì)。歸結(jié)式的性質(zhì)：歸結(jié)式C12是親本子句C12和C12的邏輯結(jié)論。歸結(jié)式是原兩子句的邏輯推論證明歸結(jié)式是原兩子句的邏輯推論，或20命題邏輯的歸結(jié)法推理過程命題邏輯的歸結(jié)過程也就是推理過程。推理是根據(jù)一定的準(zhǔn)則由稱為前提條件的一些判斷導(dǎo)出稱為結(jié)論的另一些判斷的思維過程。命題邏輯的歸結(jié)方法推理過程：建立待歸結(jié)命題公式

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

求取合取范式

建立子句集

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

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

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

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

（證明完畢）

得到空子句□，表示S是不可滿足的（矛盾），故原命題成立。歸結(jié)步驟歸結(jié)法是在子句集S的基礎(chǔ)上通過歸結(jié)推理規(guī)則得到的，歸22例題2-1:證明公式：(P→Q)→(～Q→～P)證明:(1)根據(jù)歸結(jié)原理,將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：

(P→Q)∧～(～Q→～P)(2)分別將公式前項(xiàng)化為合取范式：P→Q＝

～P∨Q

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

～(～Q→～P)＝

～(Q∨～P)＝

～Q∧P

兩項(xiàng)合并后化為合取范式：（～P∨Q）∧～Q∧P(3)則子句集為：{～P∨Q，～Q，P}(4)對子句集中的子句進(jìn)行歸結(jié)可得：

1.～P∨Q2.～Q

3.P

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

5.（2，4歸結(jié)）由上可得原公式成立。

例題2-1:證明公式：(P→Q)→(～Q→～P232.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謂詞邏輯歸結(jié)法基礎(chǔ)由于謂詞邏輯與命題邏輯不同，有量詞24前束范式前束范式：A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。前束范式A的形式為：

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

即：

把所有的量詞都提到前面去。注意：由于所有的量詞的轄域都延伸到公式的末端，即，最左邊量詞將約束表達(dá)式中的所有同名變量。所以將量詞提到公式最前端時存在約束變量換名問題。要嚴(yán)守規(guī)則。前束范式前束范式：A是一個前束范式，如果A中的一切量詞都位于25約束變量換名規(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è)個體域?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）

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

(Qx)M（x）（Qy）262.3.1Skolem標(biāo)準(zhǔn)形Skolem標(biāo)準(zhǔn)形的定義：

前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為Skolem標(biāo)準(zhǔn)形。注意：公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。

Skolem定理：

謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。Skolem標(biāo)準(zhǔn)形的轉(zhuǎn)化過程為，依據(jù)約束變量換名規(guī)則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。2.3.1Skolem標(biāo)準(zhǔn)形Skolem標(biāo)準(zhǔn)形的定義：

27消去量詞量詞消去原則：

1)消去存在量詞“”

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

2)略去全程量詞“”

。簡單地省略掉該量詞。消去量詞量詞消去原則：

1)消去存在量詞“”。即，將28例題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))

由此得到前述范式。例題2-2：將下式化為Skolem標(biāo)準(zhǔn)形：

～(x)29

第五步，消去“”，略去“”消去(

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)

第五步，消去“”，略去“”302.3.2子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集：所有子句的集合。對于任一個公式G，都可以通過Skolem標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)化建立起一個子句集與之相對應(yīng)。因?yàn)樽泳洳贿^是一些文字的析取，是一種比較簡單的形式，所以對G的討論就用對子句集S的討論來代替，以便容易處理。

2.3.2子句集文字：不含任何連接詞的謂詞公式。31子句集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á)式"的與。子句集S的求取子句集S可由下面的步驟求取：32定理：謂詞表達(dá)式G是不可滿足的，當(dāng)且僅當(dāng)其子句集S是不可滿足的。G與S并不等值，但它們在不可滿足的意義下是一致的。因此如果要證明A1∧A2∧A3→B，只需證明G＝A1∧A2∧A3∧～B的子句集S是不可滿足的。注意：G真不一定S真，而S真必有G真，即：SG。因?yàn)椋涸谏蒘KOLEM標(biāo)準(zhǔn)形時將存在量詞用常量或其他變量的函數(shù)代替，使得變量討論的論域發(fā)生了變化，即論域變小了。所以G不能保證S真。定理：謂詞表達(dá)式G是不可滿足的，當(dāng)且僅當(dāng)其子句集S是不可滿33謂詞歸結(jié)子句形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不可滿足由上面的定理，我們對SG的討論，可以用較為簡單的S1

∪S2

∪S3

∪…∪Sn來代替。為方便起見，也稱S1

∪S2

∪S3

∪…∪Sn為G的子句形，即：

SG＝S1

∪S2

∪S3

∪…∪Sn。謂詞歸結(jié)子句形G=G1ΛG2ΛG3Λ…ΛGn的34求取子句集的例子（1）例2－3：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞：

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

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

ANS(x)表示問題的解答

求取子句集的例子（1）例2－3：對所有的x,y,z來說，如果35求取子句集的例子（2）對于第一個條件，“如果y是x的父親，z又是y的父親，則z是x的祖父”，一階邏輯表達(dá)式如下：

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

SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對于第二個條件：“每個人都有父親”，一階邏輯表達(dá)式如下：

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

SA2：P(f(y),x)對于結(jié)論：某個人是它的祖父

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

否定后得到子句：

S～B：～Q(x,y)∨ANS(x)則得到的相應(yīng)的子句集為：{SA1，SA2，S～B}求取子句集的例子（2）對于第一個條件，“如果y是x的父親，z362.4歸結(jié)原理本節(jié)在上節(jié)的基礎(chǔ)上，進(jìn)一步具體介紹謂詞邏輯的歸結(jié)方法。謂詞邏輯的歸結(jié)法是以命題邏輯的歸結(jié)法為基礎(chǔ)，在Skolem標(biāo)準(zhǔn)形的子句集上，通過置換和合一進(jìn)行歸結(jié)的?；靖拍睿?/p>

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

個體詞：表示主語或賓語的詞

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

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

個體常量：a，b，c

個體變量：x，y，z

謂詞符號：P，Q，R

量詞符號：，2.4歸結(jié)原理本節(jié)在上節(jié)的基礎(chǔ)上，進(jìn)一步具體介紹謂詞邏輯的37人工智能原理教案02章歸結(jié)推理方法2歸結(jié)推理方法38人工智能原理教案02章歸結(jié)推理方法2歸結(jié)推理方法39人工智能原理教案02章歸結(jié)推理方法2歸結(jié)推理方法402.4.1合一和置換置換可以簡單的理解為是在一個謂詞公式中用置換項(xiàng)去置換變量。定義：

置換是形如{t1/vl,…,tn/vn}的一個有限集。其中vi是變量而ti是不同于vi的項(xiàng)(常量、變量、函數(shù)),且vi≠vj(i≠j),i,j=1,2,…,n例如

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

{g(y)/x，f(x)/y}不是一個置換。（原因是它在x和y之間出現(xiàn)了循環(huán)置換現(xiàn)象。）不含任何元素的置換為空置換,以ε表示。

置換可作用于某個謂詞公式上,也可作用于某個項(xiàng)上。置換θ作用于一謂詞公式E,結(jié)果以Eθ表示,并稱為E的一個例。θ作用于項(xiàng)t,結(jié)果以t·θ表示。2.4.1合一和置換置換可以簡單的理解為是在一個謂詞公式中41定義：置換的乘法（合成）設(shè)θ={t1/xl,…,tn/xn}，λ={u1/y1,…,um/ym}，是兩個置換。

則θ與λ的乘法（合成）也是一個置換，記作θ·λ。它是從集合{t1·λ/xl,…,tn·λ/xn，u1/y1,…,um/ym}

中刪去以下兩種元素：

i.當(dāng)ti·λ=xi時，從中刪除ti·λ/xi(i=1,2,…,n);

ii.當(dāng)yi∈{x1,…xn}時，從中刪除ui/yi(i=1,2,…,m)最后剩下的元素所構(gòu)成的集合。合成即是對ti先做λ置換然后再做θ置換，置換xi。

定義：置換的乘法（合成）設(shè)θ={t1/xl,…,tn/xn}42置換的合成例：設(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)是置換λ作用于f(y)的結(jié)果；y/y中的y是置換λ作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，b/y滿足定義中的條件ii，也需要刪除。最后得

θ·λ＝{f(b)/x，y/z}置換的合成例：43合一合一：合一可以簡單地理解為“尋找相應(yīng)變量的置換，使兩個謂詞公式一致”。定義：設(shè)有公式集E＝{E1,…,Ek}

，若存在一個置換θ，可使E1θ=E2θ=…=Ekθ，則稱θ是E的一個合一。同時稱E1,…,Ek是可合一的。例：

設(shè)有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，則λ＝{a/x,g(a)/y,f(g(a))/z}是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。合一合一：合一可以簡單地理解為“尋找相應(yīng)變量的置換，使兩44最一般合一定義：最一般合一設(shè)σ是公式集E1,…,Ek的一個合一置換，如果對E的任意一個合一θ都存在一個置換λ，使得θ＝σ·λ，則稱σ是E1,…,Ek的最一般合一（MostGeneralUnifier，簡記為mgu）換句話來說，其他任何合一置換θ都是σ與某個置換λ的合成。一個公式集的最一般合一是唯一的。若用最一般合一去置換那些可合一的謂詞公式，可使它們變成完全一致的謂詞公式。歸結(jié)原理方法與命題邏輯基本相同。但由于有變量與函數(shù)，所以要考慮合一和置換。最一般合一定義：最一般合一452.4.2歸結(jié)式在謂詞邏輯下求兩個子句的歸結(jié)式，和命題邏輯一樣是消互補(bǔ)對，但需考慮變量的合一與置換。設(shè)C1,C2是兩個無公共變量的子句，L1、L2分別是C1、C2的文字，如果Ll與～L2有mguσ，則(C1σ-{L1σ})∪(C2σ-{L2σ})稱作子句C1、C2的一個二元?dú)w結(jié)式，而L1、L2為被歸結(jié)的文字。子句因子：如果一個子句C的幾個文字有mguσ，那么C的例Cσ稱作子句的因子（進(jìn)行子句內(nèi)部的化簡）。2.4.2歸結(jié)式在謂詞邏輯下求兩個子句的歸結(jié)式，和命題邏輯46歸結(jié)式的注意事項(xiàng)1、謂詞的一致性，P(…)與Q(…)，不可以歸結(jié)。2、常量的一致性，P(a,…)與P(b,….)，不可以歸結(jié)。3、變量，P(a,….)與P(x,…)，可以通過置換歸結(jié)。4、變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不可以歸結(jié)；

但P(a,x,…)與P(x,f(y),…)，可以通過對兩式分別做{f(y)/x}置換和{a/x}，再歸結(jié)。5、不能同時消去兩個互補(bǔ)對，形如P∨Q與～P∨～Q得空，是不正確的。6、對子句集中的元素先進(jìn)行內(nèi)部簡化（置換、合并），然后進(jìn)行歸結(jié)。歸結(jié)式的注意事項(xiàng)1、謂詞的一致性，P(…)與Q(…)，不可47求謂詞邏輯歸結(jié)式的例子例：設(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)

求謂詞邏輯歸結(jié)式的例子例：482.4.3歸結(jié)過程謂詞邏輯的歸結(jié)過程與命題邏輯的歸結(jié)過程相比，其基本步驟相同，但每步的處理對象不同。謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集，必要時在得到歸結(jié)式前要進(jìn)行置換和合一。謂詞邏輯歸結(jié)過程：1、寫出謂詞關(guān)系公式2、用反演法寫出謂詞表達(dá)式3、化為SKOLEM標(biāo)準(zhǔn)形4、求取子句集S5、對S中可歸結(jié)的子句做歸結(jié)6、歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程7、得到空子句

命題得證2.4.3歸結(jié)過程謂詞邏輯的歸結(jié)過程與命題邏輯的歸結(jié)過程相49例題2-4："快樂學(xué)生"問題假設(shè)任何通過計(jì)算機(jī)考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運(yùn)的人都可以通過所有的考試，張不肯學(xué)習(xí)但他是幸運(yùn)的，任何幸運(yùn)的人都能獲獎。求證：張是快樂的。解：（一）先將問題用謂詞表示如下：

R1:"任何通過計(jì)算機(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)例題2-4："快樂學(xué)生"問題假設(shè)任何通過計(jì)算機(jī)考試并獲獎的50（二）將上述謂詞子句轉(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é)（二）將上述謂詞子句轉(zhuǎn)換為Skolem標(biāo)準(zhǔn)形：51歸結(jié)原理1．歸結(jié)法的實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法。歸結(jié)的過程是一個語義樹倒塌的過程。2．歸結(jié)法的問題對于傳統(tǒng)歸結(jié)法，子句中有等號或不等號時，完備性不成立。即，傳統(tǒng)的歸結(jié)法不能處理相等的關(guān)系。Herbrand定理是歸結(jié)原理的理論基礎(chǔ)；而正是由于Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。歸結(jié)原理1．歸結(jié)法的實(shí)質(zhì)：522.5歸結(jié)過程控制策略要解決的問題：歸結(jié)方法的知識爆炸。（背景：當(dāng)使用歸結(jié)法時，若從子句集S出發(fā)做所有可能的歸結(jié)，并將歸結(jié)式加入S中，再做第二層這樣的歸結(jié)，…直到產(chǎn)生空子句。）（后果：無控制的盲目全面歸結(jié)導(dǎo)致大量的不必要的歸結(jié)式的產(chǎn)生，更嚴(yán)重的是，它們又將產(chǎn)生下一層的更大量的不必要的歸結(jié)式的產(chǎn)生。這種盲目的全面歸結(jié)會產(chǎn)生組合爆炸問題。）控制策略的目的：歸結(jié)點(diǎn)盡量少（給出控制策略，以使系統(tǒng)僅選擇合適的子句對其做歸結(jié)來避免多余不必要的歸結(jié)式的出現(xiàn)，或者說少做些歸結(jié)但仍然導(dǎo)出空子句來。）控制策略的原則：刪除不必要的子句，或?qū)⒓託w結(jié)的子句做限制。2.5歸結(jié)過程控制策略要解決的問題：歸結(jié)方法的知識爆炸。53控制策略的分類（1）刪除策略（通過刪除某些無用的子句來縮小歸結(jié)的范圍）

刪除策略包括：純文字刪除法、重言式刪除法、包孕刪除法（2）限制策略（通過對參加歸結(jié)的子句進(jìn)行某些限制來減少歸結(jié)的盲目性）

限制策略包括：線性歸結(jié)、單元（單文字）歸結(jié)、語義歸結(jié)、輸入歸結(jié)和支持集策略等?？刂撇呗缘姆诸?42.5.1刪除策略名詞解釋：

歸類：設(shè)有兩個子句C和D，若有置換σ使得CσD成立，則稱子句C把子句D歸類（也稱C包孕于D）。

（可以理解為，由于小的可以代表大的，所以小的吃掉大的了。）若對S使用歸結(jié)推理過程中,當(dāng)歸結(jié)式Cj是重言式或Cj被S中子句或歸結(jié)式Ci(i<j)所歸類時,便將Cj刪除。這樣的推理過程便稱做使用了刪除策略的歸結(jié)過程。主要思想：

歸結(jié)過程在尋找可歸結(jié)子句時，子句集中的子句越多，需要付出的代價就會越大。如果在歸結(jié)時能把子句集中無用的子句刪除掉，就會縮小搜索范圍，減少比較次數(shù)，從而提高歸結(jié)效率。然而要在歸結(jié)式Cj產(chǎn)生后方能判別它是否可被刪除，這部分計(jì)算量是要花費(fèi)的，只是節(jié)省了被刪除的子句又生成的歸結(jié)式。2.5.1刪除策略名詞解釋：55例

C=P(x)D=P(a)∨Q(a)

取σ={a/x}，便有

Cσ=P(a){P(a)，Q(a)}

（子句的集合表示，要區(qū)別于子句集）而{P(a),Q(a)}的邏輯表示就是D=P(a)∨Q(a)。于是C把D歸類。刪除策略=>完備。（采用歸結(jié)策略進(jìn)行的歸結(jié)過程沒有破壞歸結(jié)法的完備性。）例C=P(x)D=P(a)∨Q(a)562.5.2采用支撐集策略

名詞解釋：支撐集：設(shè)有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支持集。t2-4_swf.htm采用支撐集策略時，從開始到得到的整個歸結(jié)過程中，只選取不同時屬于S-T的子句，在其間進(jìn)行歸結(jié)。就是說，至少有一個子句來自于支撐集T或由T導(dǎo)出的歸結(jié)式。例如：A1∧A2∧A3∧～B中的～B可以作為支撐集使用。要求每一次參加歸結(jié)的親本子句中，只要有一個是有目標(biāo)公式的否定（～B）所得到的子句或者它們的后裔。支撐集策略的歸結(jié)是完備的。同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問題是如何尋找合適的支撐集。一個最容易找到的支撐集是目標(biāo)子句的非，即S～B。2.5.2采用支撐集策略

名詞解釋：支撐集：設(shè)有不可滿足子57支持集策略的語義歸結(jié)過程例S={P∨Q,～P∨R,～Q∨R,～R}

取T={～R}支持集歸結(jié)過程：

(1)P∨Q(2)～P∨R(3)～Q∨R

(4)～R(5)～P(2)(4)(6)～Q(3)(4)(7)Q(1)(5)(8)口(6)(7)支持集策略的語義歸結(jié)過程例S={P∨Q,～P∨R582.5.3語義歸結(jié)策略語義歸結(jié)策略是將子句S分成兩部分，約定每部分內(nèi)的子句間不允許做歸結(jié)。還引入了文字次序，約定歸結(jié)時其中的一個子句的被歸結(jié)文字只能是該子句中“最大”的文字。

例S={～P∨～Q∨R,P∨R,Q∨R,～R}1）規(guī)定S中出現(xiàn)的文字的次序?yàn)镻>Q>R。2）選取S的一個解釋I=(～P,～Q,～R)用它來將S分成兩個部分。S1’={P∨R,Q∨R}為在I下為假的子句集合S2’={～P∨～Q∨R,～R}為在I下為真的子句集合規(guī)定Si’內(nèi)部的子句不允許歸結(jié),S1’與S2’子句間的歸結(jié)必須是S1’中的最大文字方可進(jìn)行。這樣所得的歸結(jié)式,仍按I來放入S1’或S2’。2.5.3語義歸結(jié)策略語義歸結(jié)策略是將子句S分成兩部分，約593）歸結(jié)過程：(1)～P∨～Q∨R∈S2’(2)P∨R∈S1’(3)Q∨R∈S1’(4)～R∈S2’(5)～Q∨R(2)(1)歸結(jié)∈S2’(6)～P∨R(3)(1)歸結(jié)∈S2’(7)R(2)(6)歸結(jié)∈S1’(8)R(3)(5)歸結(jié)∈S1’(9)口(7)(4)歸結(jié)3）歸結(jié)過程：(1)～P∨～Q∨R602.5.4線性歸結(jié)策略

線性歸結(jié)完備

圖2－5線性歸結(jié)策略示意圖

t2-5_swf.htm線性歸結(jié)策略首先從子句集中選取一個稱作頂子句的子句C0開始作歸結(jié)。歸結(jié)過程中所得到的歸結(jié)式Ci立即同另一子句Bi進(jìn)行歸結(jié)得歸結(jié)式Ci+1

。而Bi屬于S或是已出現(xiàn)的歸結(jié)式Cj(j<i)。即，如圖所示歸結(jié)得到的新子句立即參加歸結(jié)。線性歸結(jié)是完備的。同樣，所有可歸結(jié)的謂詞公式都可以采用線性歸結(jié)策略達(dá)到加快歸結(jié)速度的目的。如果能搞找到一個較好的頂子句，可以使歸結(jié)順利進(jìn)行。否則也可能事與愿違。2.5.4線性歸結(jié)策略

線性歸結(jié)完備

圖2－5線性61例S={P∨Q，～P∨Q，P∨～Q，

～P∨～Q}選取頂子句Co=P∨Q線性歸結(jié)過程:(l)P∨Q(2)～P∨Q(3)P∨～Q(4)～P∨～Q(5)Q(1)(2)(6)P(5)(3)(7)～Q(6)(4)(8)口(7)(5)例S={P∨Q，～P∨Q，P∨～Q，

622.5.5單元?dú)w結(jié)策略單元?dú)w結(jié)策略要求在歸結(jié)過程中，每次歸結(jié)都有一個子句是單元子句（只含一個文字的子句）或單元因子。顯而易見，詞中方法可以簡單地削去另一個非單子句中的一個因子，使其長度減少，構(gòu)成簡單化，歸結(jié)效率較高。單元?dú)w結(jié)完備；反之不成立。初始子句集中沒有單元子句時，單元?dú)w結(jié)策略無效。所以說"反之不成立"，即此問題不能采用單元?dú)w結(jié)策略。2.5.5單元?dú)w結(jié)策略單元?dú)w結(jié)策略要求在歸結(jié)過程中，每次歸63單元?dú)w結(jié)的例子例1S={P∨Q,～P∨R,～Q∨R,～R}單元?dú)w結(jié)過程(1)P∨Q(2)～P∨R(3)～Q∨R(4)～R(5)～P(4)(2)(6)～Q(4)(3)(7)Q(5)(1)(8)P(6)(1)(9)R(7)(3)(10)口(7)(6)單元?dú)w結(jié)的例子例1S={P∨Q,～P∨R,～Q∨642.5.6輸入歸結(jié)策略與單元?dú)w結(jié)策略相似，輸入歸結(jié)策略要求在歸結(jié)過程中，每一次歸結(jié)的兩個子句中必須有一個是S的原始子句。這樣可以避免歸結(jié)出的不必要的新子句加入歸結(jié)，造成惡性循環(huán)?？梢詼p少不必要的歸結(jié)次數(shù)。輸入歸結(jié)完備；反之不成立。如同單元?dú)w結(jié)策略，不是所有的可歸結(jié)謂詞公式的最后結(jié)論都是可以從原始子句集中的得到的。簡單的例子，歸結(jié)結(jié)束時，即最后一個歸結(jié)式為空子句的條件是，參加歸結(jié)的雙方必須是兩個單元子句。原始子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結(jié)策略。2.5.6輸入歸結(jié)策略與單元?dú)w結(jié)策略相似，輸入歸結(jié)策略要求65例2S={P∨Q,～P∨R,～Q∨R，～R}

輸入歸結(jié)過程

(1)P∨Q(2)～P∨R(3)～Q∨R(4)～R(5)Q∨R(1)(2)(6)R(3)(5)(7)口(4)(6)例2S={P∨Q,～P∨R,～Q∨R，～R}662.6Herbrand定理Herbrand定理是歸結(jié)原理的理論基礎(chǔ)，歸結(jié)原理的正確性是通過Herbrand定理來證明的。同時歸結(jié)原理是Herbrand定理的具體實(shí)現(xiàn)，利用Herbrand定理對公式的證明是通過歸結(jié)法來進(jìn)行的。本節(jié)簡單地描述了Herbrand定理的基本思想和相關(guān)預(yù)備知識，最后給出Herbrand定理的一般形式。定義：公式G永真：對于G的所有解釋，G都為真。定義：公式G永假（矛盾）：沒有一個解釋使G為真。2.6Herbrand定理Herbrand定理是歸結(jié)原理的672.6.1Herbrand定理概述問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？1936年圖靈(Turing)和邱吉(Church)互相獨(dú)立地證明了：

“沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過程將可能是不停止的?！?.6.1Herbrand定理概述問題：一階邏輯公式的永682.6.1.1Herbrand定理思想要證明一個公式是永假的，采用反證法的思想（歸結(jié)原理），就是要尋找一個已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。因?yàn)榱吭~是任意的，所討論的個體變量域D是任意的，所以解釋的個數(shù)是無限、不可數(shù)的，要找到所有的解釋是不可能的。Herbrand定理的基本思想是簡化討論域，建立一個比較簡單、特殊的域，使得只要在這個論域上（此域稱為H域），原謂詞公式仍是不可滿足的，即保證不可滿足的性質(zhì)不變。2.6.1.1Herbrand定理思想要證明一個公式是永692.6.1.2H域H域的定義：

設(shè)G是已給的公式,定義在論域D上,令H0是G中所出現(xiàn)的常量的集合。若G中沒有常量出現(xiàn),就任取常量a∈D,而規(guī)定H0={a}。

Hi=Hi-l∪{所有形如f(t1,...,tn)的元素}其中f(tl,…,tn)是出現(xiàn)于G中的任一函數(shù)符號,

而t1,…,tn是Hi-1的元素,i=1,2,…。規(guī)定H∞為G的H域(或說是相應(yīng)的子句集S的H域)。不難看出，H域是直接依賴于G的，而且最多只有可數(shù)個元素。2.6.1.2H域H域的定義：70H域和D域關(guān)系示意圖如下圖表示。

圖2－1H域與D域關(guān)系t2-1_swf.htmH域和D域關(guān)系示意圖如下圖表示。

圖2－1H域與D域關(guān)系t71H域例題例題2-4：設(shè)子句集S={P(x),Q(y,f(z,b)),R(a)}，求H域解：H0

＝{a,b}為子句集中出現(xiàn)的常量

H1

＝{a,b,f(a,b),f(a,a),f(b,a),f(b,b)}

H2

＝{a,b,f(a,b),f(a,a),f(b,a),f(b,b)

f(a,f(a,b)),f(a,f(a,a)),f(a,f(b,a)),f(a,f(b,b)),

f(b,f(a,b)),f(b,f(a,a)),f(b,f(b,a)),f(b,f(b,b)),

f(f(a,b),f(a,b)),f(f(a,b),f(a,a)),f(f(a,b),f(b,a)),f(f(a,b),f(b,b)),

f(f(a,a),f(a,b)),f(f(a,a),f(a,a)),f(f(a,a),f(b,a)),f(f(a,a),f(b,b)),

f(f(b,a),f(a,b)),f(f(b,a),f(a,a)),f(f(b,a),f(b,a)),f(f(b,a),f(b,b)),

f(f(b,b),f(a,b)),f(f(b,b),f(a,a)),f(f(b,b),f(b,a)),f(f(b,b),f(b,b))}

………

H∞=

H1∪H2∪………解畢。

H域例題例題2-4：設(shè)子句集S={P(x),Q(y,72原子集A原子集A為公式中出現(xiàn)的謂詞套上H域的元素組成的集合。

A={所有形如P(t1,...,tn)的元素}。這里，P(x1,…,xn)為出現(xiàn)于S中的任一謂詞符號，而t1,...,tn為S的H域中的任意元素。即把H域中的東西填到S的謂詞里去。上例題的原子集為：

A={P(a),Q(a,a),R(a),P(b),Q(b,a),Q(b,b),Q(b,a),R(b),P(f(a,b)),Q(f(a,b),f(a,b)),R(f(a,b),P(f(a,a)),P(f(b,a)),P(f(b,b)),……)一旦原子集內(nèi)真值確定好（規(guī)定好），則S在H上的真值可確定。不可數(shù)問題轉(zhuǎn)化成為了可數(shù)問題。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。原子集A原子集A為公式中出現(xiàn)的謂詞套上H域的元素組成的集合。732.6.1.3H解釋解釋I：謂詞公式G在論域D上任何一組真值的指定稱為一個解釋。H解釋：子句集S在H域上的解釋稱為H解釋。I是H域下的一個指派。凡對A中各元素真假值的一個具體設(shè)定，都是S的一個H解釋。由子句集S建立H域、原子集A，希望定義于一般論域D上使S為真的任一解釋I，可由依于S的H域上的某個解釋I*來實(shí)現(xiàn)。這樣，便使任意論域D上S為真的問題，化成了僅有可數(shù)個元素的H域上S為真的問題了。從而子句集S在D上不可滿足問題化成了H上的不可滿足的問題。2.6.1.3H解釋解釋I：謂詞公式G在論域D上任何一組真74幾個術(shù)語的定義沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱為基原子、基文字、基子句和基子句集?；鹤泳浼疭中某子句C中所有變元符號均以S的H域中的元素代入時，所得的基子句C‘稱為C的一個基例。若一個解釋I*使得某個基子句為假，則此解釋I*為假。幾個術(shù)語的定義沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱75關(guān)于基例例S={P(x),Q(f(y))∨R(y)}有

H={a,f(a),f(f(a)),…}對任一b∈D,子句P(b),Q(f(b))∨R(b)都叫基子句。而P(a),P(f(a))都稱作子句C=P(x)的基例。同樣，Q(f(a))∨R(a),Q(f(f(a)))∨R(f(a))都是子句Q(f(y))∨R(y)的基例。關(guān)于基例例S={P(x),Q(f(y))∨R(y)}76例：S＝{P(x)∨Q(x),R(f(y))}，求其一個H解釋I*解：S的H域?yàn)椋簕a,f(a),f(f(a)),…}

S的原子集為：{P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),凡對A中各元素真假值的一個具體設(shè)定都為S的一個H解釋。如：

I1*＝{P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),…}

I2*＝{～P(a),～Q(a),～R(a),～P(f(a)),Q(f(a)),R(f(a)),…}

I3*＝{P(a),～Q(a),～R(a),P(f(a)),Q(f(a)),～R(f(a)),…}

I1*，I2*，I3*中出現(xiàn)的P(a)表示P(a)的取值為T，出現(xiàn)的～P(a)表示P(a)的取值為F。顯然在H域上，這樣的定義I*下，S的真值就確定了。如：

S|I1*＝T，S|I2*＝F，S|I3*＝F這是因?yàn)樽泳浼疭＝{P(x)∨Q(x),R(f(y))}的邏輯含義為：

(x)(y)((P(x)∨Q(x))∧R(f(y)))，論域H為{a,f(a),f(f(a)),…}。例：S＝{P(x)∨Q(x),R(f(y))}，求其一個H77Herbrand定理

（H解釋）關(guān)鍵問題：對于公式G的所有的解釋，如果公式取值全為假，才可以判定G是不可滿足的。因?yàn)樗薪忉尨砹怂械那闆r，如果這些解釋可以被窮舉，問題便可解決。對論域D上的任一解釋I,若有S|I=T,如何求得一個相應(yīng)的H解釋I*,使得S|I*=T成立。由I到I*,實(shí)為H域到D域的映射,對H中每個常量、每個函數(shù)依I來規(guī)定D中的一個確定的元素。Herbrand定理（H解釋）關(guān)鍵問題：對于公式G的所有的78以下三個定理保證了歸結(jié)法的正確性。定理2.3.2(1)

設(shè)I是S的論域D上的解釋,存在對應(yīng)于I的H解釋I*,使得若有S|I=T,必有S|I*=T。說明：由I到I*,實(shí)為H域到D域的映射。即：對H中每個常量、每個函數(shù)依I來規(guī)定D中的一個確定的元素。

定理2.3.2(2)

子句集S是不可滿足的,當(dāng)且僅當(dāng)在所有的S的H解釋下為假。說明：這個定理將S在一般論域D上的不可滿足問題化成了可數(shù)集H上的不可滿足問題。

定理2.3.2(3)

子句集S是不可滿足的，當(dāng)且僅當(dāng)對每個解釋I下,至少有S的某個子句的某個基例為假。解釋：因?yàn)镾的邏輯含義是所包含的子句的合取,而且變量受全稱量詞作用。那么在某個解釋I(均指H解釋)下為假,只需某個子句的某個基例為假,而S是不可滿足則要求在任一解釋下均為假。

以下三個定理保證了歸結(jié)法的正確性。79人工智能原理教案02章歸結(jié)推理方法2歸結(jié)推理方法802.6.2語義樹與Herbrand定理從幾何上進(jìn)行討論，將子句集S的所有可能解釋展示在一棵樹上，進(jìn)而觀察每個分枝對應(yīng)的S的邏輯真值是真是假。語義樹的構(gòu)成方法：原子集A中所有元素逐層添加到一棵二叉樹，并將元素的'是'與'非'分別標(biāo)記在兩側(cè)的分枝上。語義樹特點(diǎn)：一般H是無限可數(shù)集，因此，S的語義樹是無限樹。2.6.2語義樹與Herbrand定理從幾何上進(jìn)行討論，將81語義樹的意義語義樹可以理解為H域的圖形解釋。通過子句集S→H域→原子集A→語義樹，可見，討論的對象從無限、不可數(shù)論域D轉(zhuǎn)換成了可數(shù)的、有序的語義樹。建立語義樹的目的：把S中的每個解釋都攤開。S的完全語義樹的每個直到葉結(jié)點(diǎn)N的分枝都對應(yīng)于S的一個解釋I(N)。討論S的不可滿足性，可通過對語義樹的每個分枝計(jì)算S的每一個解釋的真值而實(shí)現(xiàn)。如果每個基例都為假，則可認(rèn)為是不可滿足的。有時并非需要無限地延伸某個分枝方能確定在相應(yīng)的解釋下S取假值。如果某個分枝延伸到結(jié)點(diǎn)N時，I(N)已使S的某一子句的某一基例為假，就無需再對N作延伸了。語義樹的意義語義樹可以理解為H域的圖形解釋。82例1設(shè)子句集S的原子集

A={P,Q,R}屬命題邏輯。這時S的原子集就是S中出現(xiàn)的全體原子命題。為了方便,常用

I(N34)={P,～Q,～R}

表示從根結(jié)點(diǎn)到結(jié)點(diǎn)N分枝上所標(biāo)記的所有文字的并集。圖2.1所示S的語義樹是一棵有限樹。例1設(shè)子句集S的原子集

A={P,Q,83語義樹中的幾個定義完全語義樹：如果對一棵語義樹的所有葉結(jié)點(diǎn)N來說,I(N)包含了S的原子集A={A1,A2,…}中的所有元素Ai或～Ai（i=1…n)，就稱S是完全語義樹。失敗結(jié)點(diǎn)：如果結(jié)點(diǎn)N的I(N)使S的某一子句的某一基例為假,而N的父輩結(jié)點(diǎn)不能判斷這個事實(shí),就說N是失敗結(jié)點(diǎn)。封閉樹：如果S的完全語義樹的每個分枝上都有一個失敗結(jié)點(diǎn),就說它是一棵封閉樹。語義樹中的幾個定義完全語義樹：84例：S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}，畫出其語義樹。解：子句集S的H域?yàn)椋篐＝{a，f(a)，f(f(a))，…}原子集為：A＝{P(a),Q(a),P(f(a)),Q(f(a)),…}從A出發(fā)便可畫出S的語義樹，如圖2-2所示。例：S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y85前面圖2-2所示的完全語義樹便具有每個分枝上都有失敗結(jié)點(diǎn)這樣的性質(zhì)，從而是一棵封閉的語義樹。如果從圖2-2剪去所有失敗結(jié)點(diǎn)以下的分枝，便得相應(yīng)的封閉語義樹，見左圖2-3。

t2-3_s