人工智能原理教案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é)需要在熟練掌握一般邏輯知識(shí)的基礎(chǔ)上，學(xué)習(xí)Skolem標(biāo)準(zhǔn)形和Herbrand定理，從而對(duì)歸結(jié)原理有一個(gè)比較透徹的了解?！緦W(xué)習(xí)指南】

在學(xué)習(xí)新知識(shí)的同時(shí)回顧以前所學(xué)的一般邏輯知識(shí)。對(duì)所涉及的概念和方法不要死記硬背，對(duì)于比較抽象的概念，可以通過比較簡(jiǎn)單的例子來理解。【難重點(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【知識(shí)點(diǎn)】

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

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

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

H域、H解釋、語義樹

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

歸結(jié)法的控制策略的原則及基本方法?！局R(shí)點(diǎn)】3歸結(jié)推理知識(shí)結(jié)構(gòu)歸結(jié)推理知識(shí)結(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)化為一個(gè)定理證明問題。定理證明的實(shí)質(zhì)：就是要對(duì)給出的（已知的）前提和結(jié)論，證明此前提推導(dǎo)出該結(jié)論這一事實(shí)是永恒的真理。這是非常困難的，幾乎是不可實(shí)現(xiàn)的。困難所在：要證明在一個(gè)論域上一個(gè)事件是永真的，就要證明在該域中的每一個(gè)點(diǎn)上該事實(shí)都成立。很顯然，論域是不可數(shù)時(shí)，該問題不可能解決。即使可數(shù)，如果該輪域是無限的，問題也無法簡(jiǎn)單地解決。Herbrand采用了反證法的思想，將永真性的證明問題轉(zhuǎn)化成為不可滿足性的證明問題。Herbrand理論為自動(dòng)定理證明奠定了理論基礎(chǔ)，而Robinson的歸結(jié)原理使得自動(dòng)定理證明得以實(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是重言式等價(jià)于A1ΛA2ΛA3Λ～B是矛盾式，也就是說永假式。反證法：證明A1ΛA2ΛA3Λ～B是矛盾式

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

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

3、北京是中國(guó)的首都。

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

2、到哪去？

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

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

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

p(rt)q命題表示公式（2）1、“如果我進(jìn)城我就去看你，除非我很累?！?3數(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無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個(gè)成真賦值，則稱A為可滿足的；析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式數(shù)理邏輯的基本定義合取式：p與q，記做p∧q14數(shù)理邏輯的基本等值式（24個(gè)）交換律：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個(gè)）交換律：p∨qq∨p；15同一律:p∨0p；

p∧1p零律：p∨11

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

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

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

p∧1p16合取范式合取范式：?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è)"或"語句的"與"，不然后續(xù)推導(dǎo)沒有意義。轉(zhuǎn)換是基于數(shù)理邏輯的基本等值公式進(jìn)行的，"或"轉(zhuǎn)換到"與"中。思路與代數(shù)學(xué)的提取公因式方法相似。合取范式合取范式：?jiǎn)卧泳?、單元子句的或（∨）的與（∧）。

17子句集命題公式的子句集S是合取范式形式下的子命題（元素）的集合。子句集是合取范式中各個(gè)合取分量的集合，生成子句集的過程可以簡(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}子句集命題公式的子句集S是合取范式形式下的子命題（元素）的集182.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è)過程為歸結(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，反之不一定成立。2.2.2命題邏輯的歸結(jié)歸結(jié)法推理的核心是求兩個(gè)子句的歸結(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)榇嬖谝粋€(gè)使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ā)，對(duì)S的子句間使用歸結(jié)推理規(guī)則，并將所得歸結(jié)式仍放入到S中（注意：此過程使得子句集不斷擴(kuò)大，是造成計(jì)算爆炸的根本原因），進(jìn)而再對(duì)新子句集使用歸結(jié)推理規(guī)則。重復(fù)使用這些規(guī)則直到得到空子句。這便說明S是不可滿足的，從而與S所對(duì)應(yīng)的定理是成立的。歸結(jié)步驟：

1)對(duì)子句集中的子句使用歸結(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)對(duì)子句集中的子句進(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ù)，所以在生成子句集之前要對(duì)邏輯公式做處理，具體的說就是要將其轉(zhuǎn)化為Skolem標(biāo)準(zhǔn)形，然后在子句集的基礎(chǔ)上再進(jìn)行歸結(jié)，雖然基本的歸結(jié)的基本方法都相同，但是其過程較之命題公式的歸結(jié)過程要復(fù)雜得多。本節(jié)針對(duì)謂詞邏輯歸結(jié)法介紹Skolem標(biāo)準(zhǔn)形、子句集等一些必要的概念和定理。

2.3謂詞邏輯歸結(jié)法基礎(chǔ)由于謂詞邏輯與命題邏輯不同，有量詞24前束范式前束范式：A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。前束范式A的形式為：

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

即：

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

約束變量換名規(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定理：

謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。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í)該變量改寫成為全程量詞的函數(shù)。

2)略去全程量詞“”

。簡(jiǎn)單地省略掉該量詞。消去量詞量詞消去原則：

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

由此得到前述范式。例題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子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集：所有子句的集合。對(duì)于任一個(gè)公式G，都可以通過Skolem標(biāo)準(zhǔn)形，標(biāo)準(zhǔn)化建立起一個(gè)子句集與之相對(duì)應(yīng)。因?yàn)樽泳洳贿^是一些文字的析取，是一種比較簡(jiǎn)單的形式，所以對(duì)G的討論就用對(duì)子句集S的討論來代替，以便容易處理。

2.3.2子句集文字：不含任何連接詞的謂詞公式。31子句集S的求取子句集S可由下面的步驟求?。?/p>

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

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

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

。注意：SKOLEM標(biāo)準(zhǔn)形必須滿足合取范式的條件。即，在生成子句集之前邏輯表達(dá)式必須是各"謂詞表達(dá)式"或"謂詞或表達(dá)式"的與。子句集S的求取子句集S可由下面的步驟求?。?2定理：謂詞表達(dá)式G是不可滿足的，當(dāng)且僅當(dāng)其子句集S是不可滿足的。G與S并不等值，但它們?cè)诓豢蓾M足的意義下是一致的。因此如果要證明A1∧A2∧A3→B，只需證明G＝A1∧A2∧A3∧～B的子句集S是不可滿足的。注意：G真不一定S真，而S真必有G真，即：SG。因?yàn)椋涸谏蒘KOLEM標(biāo)準(zhǔn)形時(shí)將存在量詞用常量或其他變量的函數(shù)代替，使得變量討論的論域發(fā)生了變化，即論域變小了。所以G不能保證S真。定理：謂詞表達(dá)式G是不可滿足的，當(dāng)且僅當(dāng)其子句集S是不可滿33謂詞歸結(jié)子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的子句集的求取過程可以分解成幾個(gè)部分單獨(dú)處理。如果Gi的子句集為Si，則

有S‘=S1

∪S2

∪S3

∪…∪Sn，雖然G的子句集不為S’，但是可以證明：

SG

與S1

∪S2

∪S3

∪…∪Sn在不可滿足的意義上是一致的。即SG

不可滿足S1

∪S2

∪S3

∪…∪Sn不可滿足由上面的定理，我們對(duì)SG的討論，可以用較為簡(jiǎn)單的S1

∪S2

∪S3

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

∪S2

∪S3

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

SG＝S1

∪S2

∪S3

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

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

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

ANS(x)表示問題的解答

求取子句集的例子（1）例2－3：對(duì)所有的x,y,z來說，如果35求取子句集的例子（2）對(duì)于第一個(gè)條件，“如果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)對(duì)于第二個(gè)條件：“每個(gè)人都有父親”，一階邏輯表達(dá)式如下：

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

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

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

否定后得到子句：

S～B：～Q(x,y)∨ANS(x)則得到的相應(yīng)的子句集為：{SA1，SA2，S～B}求取子句集的例子（2）對(duì)于第一個(gè)條件，“如果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)系式。

個(gè)體詞：表示主語或賓語的詞

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

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

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

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

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

量詞符號(hào)：，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合一和置換置換可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變量。定義：

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

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

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

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

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

中刪去以下兩種元素：

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

ii.當(dāng)yi∈{x1,…xn}時(shí)，從中刪除ui/yi(i=1,2,…,m)最后剩下的元素所構(gòu)成的集合。合成即是對(duì)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，需要?jiǎng)h除；a/x，b/y滿足定義中的條件ii，也需要?jiǎng)h除。最后得

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

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

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

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

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

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

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

(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)的人都能獲獎(jiǎng)“

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

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

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

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

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

歸結(jié)過程在尋找可歸結(jié)子句時(shí)，子句集中的子句越多，需要付出的代價(jià)就會(huì)越大。如果在歸結(jié)時(shí)能把子句集中無用的子句刪除掉，就會(huì)縮小搜索范圍，減少比較次數(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采用支撐集策略時(shí)，從開始到得到的整個(gè)歸結(jié)過程中，只選取不同時(shí)屬于S-T的子句，在其間進(jìn)行歸結(jié)。就是說，至少有一個(gè)子句來自于支撐集T或由T導(dǎo)出的歸結(jié)式。例如：A1∧A2∧A3∧～B中的～B可以作為支撐集使用。要求每一次參加歸結(jié)的親本子句中，只要有一個(gè)是有目標(biāo)公式的否定（～B）所得到的子句或者它們的后裔。支撐集策略的歸結(jié)是完備的。同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問題是如何尋找合適的支撐集。一個(gè)最容易找到的支撐集是目標(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é)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中“最大”的文字。

例S={～P∨～Q∨R,P∨R,Q∨R,～R}1）規(guī)定S中出現(xiàn)的文字的次序?yàn)镻>Q>R。2）選取S的一個(gè)解釋I=(～P,～Q,～R)用它來將S分成兩個(gè)部分。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é)策略首先從子句集中選取一個(gè)稱作頂子句的子句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é)速度的目的。如果能搞找到一個(gè)較好的頂子句，可以使歸結(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è)子句是單元子句（只含一個(gè)文字的子句）或單元因子。顯而易見，詞中方法可以簡(jiǎn)單地削去另一個(gè)非單子句中的一個(gè)因子，使其長(zhǎng)度減少，構(gòu)成簡(jiǎn)單化，歸結(jié)效率較高。單元?dú)w結(jié)完備；反之不成立。初始子句集中沒有單元子句時(shí)，單元?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é)的兩個(gè)子句中必須有一個(gè)是S的原始子句。這樣可以避免歸結(jié)出的不必要的新子句加入歸結(jié)，造成惡性循環(huán)?？梢詼p少不必要的歸結(jié)次數(shù)。輸入歸結(jié)完備；反之不成立。如同單元?dú)w結(jié)策略，不是所有的可歸結(jié)謂詞公式的最后結(jié)論都是可以從原始子句集中的得到的。簡(jiǎn)單的例子，歸結(jié)結(jié)束時(shí)，即最后一個(gè)歸結(jié)式為空子句的條件是，參加歸結(jié)的雙方必須是兩個(gè)單元子句。原始子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結(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定理來證明的。同時(shí)歸結(jié)原理是Herbrand定理的具體實(shí)現(xiàn)，利用Herbrand定理對(duì)公式的證明是通過歸結(jié)法來進(jìn)行的。本節(jié)簡(jiǎn)單地描述了Herbrand定理的基本思想和相關(guān)預(yù)備知識(shí)，最后給出Herbrand定理的一般形式。定義：公式G永真：對(duì)于G的所有解釋，G都為真。定義：公式G永假（矛盾）：沒有一個(gè)解釋使G為真。2.6Herbrand定理Herbrand定理是歸結(jié)原理的672.6.1Herbrand定理概述問題：一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？1936年圖靈(Turing)和邱吉(Church)互相獨(dú)立地證明了：

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

而t1,…,tn是Hi-1的元素,i=1,2,…。規(guī)定H∞為G的H域(或說是相應(yīng)的子句集S的H域)。不難看出，H域是直接依賴于G的，而且最多只有可數(shù)個(gè)元素。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中的任一謂詞符號(hào)，而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上任何一組真值的指定稱為一個(gè)解釋。H解釋：子句集S在H域上的解釋稱為H解釋。I是H域下的一個(gè)指派。凡對(duì)A中各元素真假值的一個(gè)具體設(shè)定，都是S的一個(gè)H解釋。由子句集S建立H域、原子集A，希望定義于一般論域D上使S為真的任一解釋I，可由依于S的H域上的某個(gè)解釋I*來實(shí)現(xiàn)。這樣，便使任意論域D上S為真的問題，化成了僅有可數(shù)個(gè)元素的H域上S為真的問題了。從而子句集S在D上不可滿足問題化成了H上的不可滿足的問題。2.6.1.3H解釋解釋I：謂詞公式G在論域D上任何一組真74幾個(gè)術(shù)語的定義沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱為基原子、基文字、基子句和基子句集?；鹤泳浼疭中某子句C中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所得的基子句C‘稱為C的一個(gè)基例。若一個(gè)解釋I*使得某個(gè)基子句為假，則此解釋I*為假。幾個(gè)術(shù)語的定義沒有變量出現(xiàn)的原子、文字、子句和子句集，分別稱75關(guān)于基例例S={P(x),Q(f(y))∨R(y)}有

H={a,f(a),f(f(a)),…}對(duì)任一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))}，求其一個(gè)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)),凡對(duì)A中各元素真假值的一個(gè)具體設(shè)定都為S的一個(gè)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))}，求其一個(gè)H77Herbrand定理

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

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

定理2.3.2(2)

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

定理2.3.2(3)

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

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

A={P,Q,R}屬命題邏輯。這時(shí)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語義樹中的幾個(gè)定義完全語義樹：如果對(duì)一棵語義樹的所有葉結(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)不能判斷這個(gè)事實(shí),就說N是失敗結(jié)點(diǎn)。封閉樹：如果S的完全語義樹的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn),就說它是一棵封閉樹。語義樹中的幾個(gè)定義完全語義樹：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所示的完全語義樹便具有每個(gè)分枝上都有失敗結(jié)點(diǎn)這樣的性質(zhì)，從而是一棵封閉的語義樹。如果從圖2-2剪去所有失敗結(jié)點(diǎn)以下的分枝，便得相應(yīng)的封閉語義樹，見左圖2-3。

t2-3_s