華工人工智能老師上課課件第三章

《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法歸結(jié)推理命題邏輯謂詞邏輯Skolem標(biāo)準(zhǔn)形、子句集基本概念謂詞邏輯歸結(jié)原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結(jié)Herbrand定理歸結(jié)命題謂詞邏Skolem標(biāo)準(zhǔn)形、基本謂詞邏輯合一和置換、數(shù)《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法概述歸結(jié)原理由J.A.Robinson由1965年提出。與演繹法(deductiveinference)完全不同，新的邏輯演算(inductiveinference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。而歸結(jié)方法是自動(dòng)推理、自動(dòng)推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”）本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題。

概述歸結(jié)原理由J.A.Robinson由1965年提出。《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法命題例命題：能判斷真假（不是既真又假）的陳述句。

簡(jiǎn)單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1．

1+1=22．

雪是黑色的。3．

北京是中國的首都。4．

到冥王星去渡假。

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

快點(diǎn)走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命題。命題例命題：能判斷真假（不是既真又假）的陳述句?！度斯ぶ悄茉怼返谌職w結(jié)推理方法命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”?！玴

是q的充分條件， 因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”?！玴

是q的必要條件， 因而，可得命題公式：q→～p命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式?！度斯ぶ悄茉怼返谌職w結(jié)推理方法命題表示公式（2）例如：1．

“如果我進(jìn)城我就去看你，除非我很累?！? 設(shè)：p，我進(jìn)城，q，去看你，r，我很累。 則有命題公式：～r→(p→q)。2．“應(yīng)屆高中生，得過數(shù)學(xué)或物理競(jìng)賽的一等獎(jiǎng)， 保送上北京大學(xué)?！?設(shè)：p，應(yīng)屆高中生，q，保送上北京大學(xué)上學(xué)，

r，是得過數(shù)學(xué)一等獎(jiǎng)。t，是得過物理一等獎(jiǎng)。 則有命題公式公式：p

∧(r∨t)→

q。

命題表示公式（2）例如：《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：定義：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

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

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

q

。。。。。。命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：《人工智能原理》第三章歸結(jié)推理方法命題邏輯基礎(chǔ)定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個(gè)成真賦值，則稱A為可滿足的；析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式。合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式。命題邏輯基礎(chǔ)定義：《人工智能原理》第三章歸結(jié)推理方法命題邏輯基礎(chǔ)基本等值式24個(gè)(1)交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結(jié)合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

命題邏輯基礎(chǔ)基本等值式24個(gè)(1)《人工智能原理》第三章歸結(jié)推理方法命題邏輯基礎(chǔ)基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊(yùn)含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

命題邏輯基礎(chǔ)基本等值式（1）《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）例：

命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法建立子句集合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

命題邏輯的歸結(jié)法建立子句集《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法歸結(jié)式消除互補(bǔ)對(duì)，求新子句→得到歸結(jié)式。如子句：C1,C2， 歸結(jié)式：R(C1,C2)=C1ΛC2

注意：C1ΛC2→R(C1,C2)

，反之不一定成立。命題邏輯的歸結(jié)法歸結(jié)式《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法歸結(jié)過程

將命題寫成合取范式求出子句集對(duì)子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。命題邏輯的歸結(jié)法歸結(jié)過程《人工智能原理》第三章歸結(jié)推理方法命題邏輯歸結(jié)例題（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}命題邏輯歸結(jié)例題（1）例題，證明公式：(P→Q)→(《人工智能原理》第三章歸結(jié)推理方法命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

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

， （2，4歸結(jié)）

由上可得原公式成立。命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)一階邏輯基本概念個(gè)體詞：表示主語的詞謂詞：刻畫個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞量詞：表示數(shù)量的詞謂詞歸結(jié)原理基礎(chǔ)一階邏輯《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)

小王是個(gè)工程師。

8是個(gè)自然數(shù)。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個(gè)體詞，而“是個(gè)工程師”、“是個(gè)自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個(gè)謂詞表示的是事物的性質(zhì)，第三個(gè)謂詞“去買”表示的一個(gè)動(dòng)作也表示了主、賓兩個(gè)個(gè)體詞的關(guān)系，最后一個(gè)謂詞“是朋友”表示兩個(gè)個(gè)體詞之間的關(guān)系。謂詞歸結(jié)原理基礎(chǔ) 小王是個(gè)工程師?！度斯ぶ悄茉怼返谌職w結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)一階邏輯公式及其解釋個(gè)體常量：a,b,c個(gè)體變量：x,y,z謂詞符號(hào)：P,Q,R量詞符號(hào)：

,謂詞歸結(jié)原理基礎(chǔ)一階邏輯《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個(gè)體域D為人類集合時(shí)，可符號(hào)化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百歲以上。在個(gè)體域D是全總個(gè)體域時(shí)，引入特殊謂詞R(x)表示x是人，可符號(hào)化為：（1）x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

謂詞歸結(jié)原理基礎(chǔ)例如：（1）所有的人都是要死的?！度斯ぶ悄茉怼返谌職w結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)量詞否定等值式：～(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

）謂詞歸結(jié)原理基礎(chǔ)量詞否定等值式：《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)量詞轄域收縮與擴(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）謂詞歸結(jié)原理基礎(chǔ)量詞轄域收縮與擴(kuò)張等值式：《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)SKOLEM標(biāo)準(zhǔn)形前束范式

定義：說公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)SKOLEM標(biāo)準(zhǔn)形《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)即：把所有的量詞都提到前面去，然后消掉所有量詞

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)約束變項(xiàng)換名規(guī)則：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)即：把所有的量詞都《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)

量詞消去原則： 消去存在量詞“”，略去全程量詞“”。 注意：左邊有全程量詞的存在量詞，消去時(shí)該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。

謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形) 《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)例:將下式化為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))第三步，變?cè)酌?/p>

(x)((y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量詞左移，直至所有的量詞移到前面，得：

(x)(y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)

第五步，消去“”（存在量詞），略去“”全稱量詞 消去(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)

謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形) 第五步，消去“”《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求取：

G→SKOLEM標(biāo)準(zhǔn)形 →消去存在變量 →以“，”取代“Λ”，并表示為集合形式。謂詞歸結(jié)子句形子句與子句集《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形

G是不可滿足的<=>S是不可滿足的G與S不等價(jià)，但在不可滿足得意義下是一致的。

定理： 若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的<=>S是不可滿足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G謂詞歸結(jié)子句形G是不可滿足的<=>S是不可滿足的《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成幾個(gè)單獨(dú)處理。

有SG=S1US2US3U…USn

則SG

與S1US2US3U…USn在不可滿足得意義上是一致的。 即SG

不可滿足<=>S1US2US3U…USn不可滿足謂詞歸結(jié)子句形G=G1ΛG2ΛG3Λ…ΛGn的《人工智能原理》第三章歸結(jié)推理方法求取子句集例(1)例：對(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)例：對(duì)所有的x,y,z來說，如果y是x的父《人工智能原理》第三章歸結(jié)推理方法求取子句集例(2)對(duì)于第一個(gè)條件，“如果x是y的父親，y又是z的父親，則x是z的祖父”，一階邏輯表達(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),y)對(duì)于結(jié)論：某個(gè)人是它的祖父

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

否定后得到子句：～（(x)(y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)則得到的相應(yīng)的子句集為：{SA1，SA2，S～B}求取子句集例(2)對(duì)于第一個(gè)條件，“如果x是y的父親，y《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。

歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。《人工智能原理》第三章歸結(jié)推理方法置換置換：可以簡(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è)置換，

置換置換：可以簡(jiǎn)單的理解為是在一個(gè)謂詞公式中用置換項(xiàng)去置換變《人工智能原理》第三章歸結(jié)推理方法置換的合成設(shè)＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是兩個(gè)置換。 則與的合成也是一個(gè)置換，記作·。它是從集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn}

中刪去以下兩種元素：當(dāng)ti=xi時(shí)，刪去ti/xi(i=1,2,…,n);

當(dāng)yi{x1,x2,…,xn}時(shí)，刪去uj/yj(j=1,2,…,m)

最后剩下的元素所構(gòu)成的集合。合成即是對(duì)ti先做置換然后再做置換，置換xi置換的合成設(shè)＝{t1/x1,t2/x2,…,tn/x《人工智能原理》第三章歸結(jié)推理方法置換的合成例：設(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}置換的合成例：《人工智能原理》第三章歸結(jié)推理方法合一合一可以簡(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è)合一。注意：一般說來，一個(gè)公式集的合一不是唯一的。

合一合一可以簡(jiǎn)單地理解為“尋找相對(duì)變量的置換，使兩個(gè)謂詞公式《人工智能原理》第三章歸結(jié)推理方法歸結(jié)原理歸結(jié)的注意事項(xiàng)：謂詞的一致性，P()與Q()，不可以常量的一致性，P(a,…)與P(b,….)，不可以 變量，P(a,….)與P(x,…)，可以變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不可以；是不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)，P∨Q與～P∨～Q的空，不可以先進(jìn)行內(nèi)部簡(jiǎn)化（置換、合并）

歸結(jié)原理歸結(jié)的注意事項(xiàng)：《人工智能原理》第三章歸結(jié)推理方法歸結(jié)原理歸結(jié)的過程寫出謂詞關(guān)系公式→用反演法寫出謂詞表達(dá)式→SKOLEM標(biāo)準(zhǔn)形→子句集S→對(duì)S中可歸結(jié)的子句做歸結(jié)→歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程→得到空子句

?得證歸結(jié)原理歸結(jié)的過程《人工智能原理》第三章歸結(jié)推理方法例題“快樂學(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)例題“快樂學(xué)生”問題假設(shè)任何通過計(jì)算機(jī)考試并獲獎(jiǎng)的人都是快樂《人工智能原理》第三章歸結(jié)推理方法例題“快樂學(xué)生”問題由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é)論的否定）(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)

例題“快樂學(xué)生”問題由R1及邏輯轉(zhuǎn)換公式:P∧W→H=～《人工智能原理》第三章歸結(jié)推理方法歸結(jié)原理歸結(jié)法的實(shí)質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法。歸結(jié)的過程是一個(gè)語義樹倒塌的過程。歸結(jié)法的問題子句中有等號(hào)或不等號(hào)時(shí)，完備性不成立。※Herbrand定理的不實(shí)用性引出了可實(shí)用的歸結(jié)法。歸結(jié)原理歸結(jié)法的實(shí)質(zhì)：《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法歸結(jié)過程的控制策略要解決的問題：歸結(jié)方法的知識(shí)爆炸?？刂撇呗缘哪康臍w結(jié)點(diǎn)盡量少控制策略的原則給出控制策略，以使僅對(duì)選擇合適的子句間方可做歸結(jié)。避免多余的、不必要的歸結(jié)式出現(xiàn)。或者說，少做些歸結(jié)仍能導(dǎo)出空子句。歸結(jié)過程的控制策略要解決的問題：《人工智能原理》第三章歸結(jié)推理方法控制策略的方法(1)

刪除策略 => 完備名詞解釋：歸類：設(shè)有兩個(gè)子句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é)效率。刪除策略對(duì)阻止不必要的歸結(jié)式的產(chǎn)生來縮短歸結(jié)過程是有效的。然而要在歸結(jié)式Cj產(chǎn)生后方能判別它是否可被刪除，這部分計(jì)算量是要花費(fèi)的，只是節(jié)省了被刪除的子句又生成的歸結(jié)式。盡管使用刪除策略的歸結(jié)，少做了歸結(jié)但不影響產(chǎn)生空子句，就是說刪除策略的歸結(jié)推理是完備的。控制策略的方法(1) 刪除策略 => 完備《人工智能原理》第三章歸結(jié)推理方法控制策略的方法(2)采用支撐集 <=>完備

支撐集：設(shè)有不可滿足子句集S的子集T，如果S-T是可滿足的，則T是支持集。

采用支撐集策略時(shí)，從開始到得到的整個(gè)歸結(jié)過程中，只選取不同時(shí)屬于S-T的子句，在其間進(jìn)行歸結(jié)。就是說，至少有一個(gè)子句來自于支撐集T或由T導(dǎo)出的歸結(jié)式。

例如：A1ΛA2ΛA3Λ～B中的～B可以作為支撐集使用。要求每一次參加歸結(jié)的親本子句中，只要應(yīng)該有一個(gè)是有目標(biāo)公式的否定（～B）所得到的子句或者它們的后裔。支撐集策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達(dá)到加快歸結(jié)速度的目的。問題是如何尋找合適的支撐集。一個(gè)最容易找到的支撐集是目標(biāo)子句的非，即S～B。

控制策略的方法(2)采用支撐集 <=>完備《人工智能原理》第三章歸結(jié)推理方法ST可滿足支撐集示意圖ST可滿足支撐集示意圖《人工智能原理》第三章歸結(jié)推理方法控制策略的方法(3)

語義歸結(jié) <=> 完備

語義歸結(jié)策略是將子句S按照一定的語義分成兩部分，約定每部分內(nèi)的子句間不允許作歸結(jié)。同時(shí)還引入了文字次序，約定歸結(jié)時(shí)其中的一個(gè)子句的被歸結(jié)文字只能是該子句中“最大”的文字。 語義歸結(jié)策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用語義歸結(jié)策略達(dá)到加快歸結(jié)速度的目的。問題是如何尋找合適的語義分類方法，并根據(jù)其含義將子句集兩個(gè)部分中的子句進(jìn)行排序。

控制策略的方法(3) 語義歸結(jié) <=> 完備《人工智能原理》第三章歸結(jié)推理方法控制策略的方法(4)

線性歸結(jié) <=>完備線性歸結(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)行。否則也可能事與愿違。

控制策略的方法(4) 線性歸結(jié) <=>完備《人工智能原理》第三章歸結(jié)推理方法C0C1C2C3C4C5空線性歸結(jié)策略示意圖C0C1C2C3C4C5空線性歸結(jié)策略示意圖《人工智能原理》第三章歸結(jié)推理方法控制策略的方法(5)

單元?dú)w結(jié) => 完備

單元?dú)w結(jié)策略要求在歸結(jié)過程中，每次歸結(jié)都有一個(gè)子句是單元子句（只含一個(gè)文字的子句）或單元因子。顯而易見，詞中方法可以簡(jiǎn)單地削去另一個(gè)非單子句中的一個(gè)因子，使其長(zhǎng)度減少，構(gòu)成簡(jiǎn)單化，歸結(jié)效率較高。初始子句集中沒有單元子句時(shí)，單元?dú)w結(jié)策略無效。所以說“反之不成立”，即此問題不能采用單元?dú)w結(jié)策略。

控制策略的方法(5) 單元?dú)w結(jié) => 完備《人工智能原理》第三章歸結(jié)推理方法控制策略的方法(6)

輸入歸結(jié) => 完備

與單元?dú)w結(jié)策略相似，輸入歸結(jié)策略要求在歸結(jié)過程中，每一次歸結(jié)的兩個(gè)子句中必須有一個(gè)是S的原始子句。這樣可以避免歸結(jié)出的不必要的新子句加入歸結(jié)，造成惡性循環(huán)?？梢詼p少不必要的歸結(jié)次數(shù)。如同單元?dú)w結(jié)策略，不是所有的可歸結(jié)謂詞公式的最后結(jié)論都是可以從原始子句集中的得到的。簡(jiǎn)單的例子，歸結(jié)結(jié)束時(shí)，即最后一個(gè)歸結(jié)式為空子句的條件是，參加歸結(jié)的雙方必須是兩個(gè)單元子句。原始子句集中沒有單元子句的謂詞公式一定不能采用輸入歸結(jié)策略。

控制策略的方法(6) 輸入歸結(jié) => 完備《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法Herbrand定理問題： 一階邏輯公式的永真性（永假性）的判定是否能在有限步內(nèi)完成？Herbrand定理問題：《人工智能原理》第三章歸結(jié)推理方法Herbrand定理1936年圖靈(Turing)和邱吉(Church)互相獨(dú)立地證明了：

“沒有一般的方法使得在有限步內(nèi)判定一階邏輯的公式是否是永真（或永假）。但是如果公式本身是永真（或永假）的，那么就能在有限步內(nèi)判定它是永真（或永假）。對(duì)于非永真（或永假）的公式就不一定能在有限步內(nèi)得到結(jié)論。判定的過程將可能是不停止的?！?/p>

Herbrand定理1936年圖靈(Turing)和邱吉(C《人工智能原理》第三章歸結(jié)推理方法Herbrand定理Herbrand的思想定義： 公式G永真：對(duì)于G的所有解釋，G都為真。思想：

尋找一個(gè)已給的公式是真的解釋。然而，如果所給定的公式的確是永假的，就沒有這樣的解釋存在，并且算法在有限步內(nèi)停止。Herbrand定理Herbrand的思想《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（H域）基本方法：因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是任意的，所以解釋的個(gè)數(shù)是無限、不可數(shù)的。簡(jiǎn)化討論域。建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上，該公式是不可滿足的。此域稱為H域。

Herbrand定理（H域）基本方法：《人工智能原理》第三章歸結(jié)推理方法D域H域H域與D域關(guān)系示意圖D域H域H域與D域關(guān)系示意圖《人工智能原理》第三章歸結(jié)推理方法H域例題設(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∪H3………H域例題設(shè)子句集S={P(x),Q(y,f(z,b)《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（H域）幾個(gè)基本概念f（tn）：f為子句集S中的所有函數(shù)變量。t1,t2,…tn為S的H域的元素。通過它們來討論永真性。原子集A：謂詞套上H域的元素組成的集合。如

A={所有形如P(t1,t2,…tn)的元素}

即把H中的東西填到S的謂詞里去。S中的謂詞是有限的，H是可數(shù)的，因此，A也是可數(shù)的。Herbrand定理（H域）幾個(gè)基本概念《人工智能原理》第三章歸結(jié)推理方法原子集例題上例題的原子集為：A={

P(a),Q(a,a),R(a),P(b),Q(b,a), Q(b,b),Q(a,b),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ù)問題。原子集例題上例題的原子集為：《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（H解釋）解釋I：謂詞公式G在論域D上任何一組真值的指定稱為一個(gè)解釋。H解釋：子句集S在的H域上的解釋稱為H解釋。

問題：對(duì)于所有的解釋，全是假才可判定。因?yàn)樗薪忉尨砹怂械那闆r，如可窮舉，問題便可解決。Herbrand定理（H解釋）解釋I：謂詞公式G在論域D上任《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（H解釋）如下三個(gè)定理保證了歸結(jié)法的正確性：定理1：

設(shè)I是S的論域D上的解釋，存在對(duì)應(yīng)于I的H解釋I*，使得若有S|I=T，必有S|I*=T。定理2： 子句集S是不可滿足的，當(dāng)且僅當(dāng)所有的S的H解釋下為假。定理3： 子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少有S的某個(gè)子句的某個(gè)基例為假。Herbrand定理（H解釋）如下三個(gè)定理保證了歸結(jié)法的正確《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（H解釋）基例S中某子句中所有變?cè)?hào)均以S的H域中的元素代入時(shí)，所得的基子句C’稱為C的一個(gè)基例。若一個(gè)子句為假，則此解釋為假。一般來說，D是無窮不可列的，因此，子句集S也是無窮不可列的。但S確定后H是無窮可列的。不過在H上證明S的不可滿足性仍然是不可能的。解決問題的方法：語義樹Herbrand定理（H解釋）基例《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（語義樹）構(gòu)成方法原子集中所有元素逐層添加的一棵二叉樹。將元素的是與非分別標(biāo)記在兩側(cè)的分枝上（可不完全畫完）。特點(diǎn)一般情況H是可數(shù)集，S的語義樹是無限樹。Herbrand定理（語義樹）構(gòu)成方法《人工智能原理》第三章歸結(jié)推理方法N0P(a)N12Q(a)P(f(a))N24N31N38無限語義樹N11~P(a)~Q(a)Q(a)~Q(a)~P(f(a))N21S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}

N0P(a)N12Q(a)P(f(a))N24N31N38無《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（語義樹）意義SHA語義樹可以理解語義樹為H域的圖形解釋。目的：把每個(gè)解釋都攤開。語義樹中包含原子集的全部元素。因此，語義樹是完全的。每一個(gè)直到葉子節(jié)點(diǎn)的分支對(duì)應(yīng)S的一個(gè)解釋?？梢酝ㄟ^對(duì)語義樹每一個(gè)分支來計(jì)算S的真值。如果每個(gè)基例都為假，則可認(rèn)為是不可滿足的。Herbrand定理（語義樹）意義《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（語義樹）幾個(gè)概念失敗結(jié)點(diǎn)： 當(dāng)（由上）延伸到點(diǎn)N時(shí)，I(N)已表明了S的某子句的某基例假。但N以前尚不能判斷這事實(shí)。就稱N為失敗結(jié)點(diǎn)。

封閉語義樹： 如果S的完全語義樹的每個(gè)分枝上都有一個(gè)失敗結(jié)點(diǎn)，就稱它是一棵封閉語義樹。Herbrand定理（語義樹）幾個(gè)概念《人工智能原理》第三章歸結(jié)推理方法N0P(a)N1,2Q(a)P(f(a))N2,4N3,1N3,8N1,1N4,2N4,1N2,1N3,2N2,2N3,6N4,9N4,10N4,13N4,14封閉語義樹Q(f(a))S＝{～P(x)∨Q(x)，P(f(y))，～Q(f(y))}

N0P(a)N1,2Q(a)P(f(a))N2,4N3,1N《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理H域H解釋語義樹結(jié)論：Herbrand定理Herbrand定理H域《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（結(jié)論）Herbrand定理：子句集S是不可滿足的，當(dāng)且僅當(dāng)對(duì)應(yīng)于S的完全語義數(shù)是棵有限封閉樹。

子句集S是不可滿足的，當(dāng)且僅當(dāng)存在不可滿足的S的有限基例集。

Herbrand定理（結(jié)論）Herbrand定理：《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（結(jié)論）定理的意義Herbrand定理已將證明問題轉(zhuǎn)化成了命題邏輯問題。由此定理保證，可以放心的用機(jī)器來實(shí)現(xiàn)自動(dòng)推理了。（歸結(jié)原理）注意Herbrand定理給出了一階邏輯的半可判定算法，即僅當(dāng)被證明定理是成立時(shí)，使用該算法可以在有限步得證。而當(dāng)被證定理并不成立時(shí)，使用該算法得不出任何結(jié)論。但是

Herbrand定理（結(jié)論）定理的意義《人工智能原理》第三章歸結(jié)推理方法Herbrand定理（結(jié)論）仍存在的問題：基例集序列元素的數(shù)目隨子句基的元素?cái)?shù)目成指數(shù)地增加。因此，Herbrand定理是30年代提出的，始終沒有顯著的成績(jī)。直至1965年Robinson提出了歸結(jié)原理。Herbrand定理（結(jié)論）仍存在的問題：《人工智能原理》第三章歸結(jié)推理方法歸結(jié)原理與Herbrand定理歸結(jié)原理是語義樹的一個(gè)倒塌過程最后歸結(jié)出空，就是剩一個(gè)根節(jié)點(diǎn)，就說明語義樹是有限封閉的，證明結(jié)束。歸結(jié)原理與Herbrand定理歸結(jié)原理是語義樹的一個(gè)倒塌過程《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法

TheEnd.第三章歸結(jié)推理方法《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法歸結(jié)推理命題邏輯謂詞邏輯Skolem標(biāo)準(zhǔn)形、子句集基本概念謂詞邏輯歸結(jié)原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結(jié)Herbrand定理歸結(jié)命題謂詞邏Skolem標(biāo)準(zhǔn)形、基本謂詞邏輯合一和置換、數(shù)《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法概述歸結(jié)原理由J.A.Robinson由1965年提出。與演繹法(deductiveinference)完全不同，新的邏輯演算(inductiveinference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。而歸結(jié)方法是自動(dòng)推理、自動(dòng)推導(dǎo)證明用的。（“數(shù)學(xué)定理機(jī)器證明”）本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題。

概述歸結(jié)原理由J.A.Robinson由1965年提出?！度斯ぶ悄茉怼返谌職w結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法命題例命題：能判斷真假（不是既真又假）的陳述句。

簡(jiǎn)單陳述句描述事實(shí)、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1．

1+1=22．

雪是黑色的。3．

北京是中國的首都。4．

到冥王星去渡假。

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

快點(diǎn)走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命題。命題例命題：能判斷真假（不是既真又假）的陳述句?！度斯ぶ悄茉怼返谌職w結(jié)推理方法命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”?！玴

是q的充分條件， 因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”。～p

是q的必要條件， 因而，可得命題公式：q→～p命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式?！度斯ぶ悄茉怼返谌職w結(jié)推理方法命題表示公式（2）例如：1．

“如果我進(jìn)城我就去看你，除非我很累?！? 設(shè)：p，我進(jìn)城，q，去看你，r，我很累。 則有命題公式：～r→(p→q)。2．“應(yīng)屆高中生，得過數(shù)學(xué)或物理競(jìng)賽的一等獎(jiǎng)， 保送上北京大學(xué)?！?設(shè)：p，應(yīng)屆高中生，q，保送上北京大學(xué)上學(xué)，

r，是得過數(shù)學(xué)一等獎(jiǎng)。t，是得過物理一等獎(jiǎng)。 則有命題公式公式：p

∧(r∨t)→

q。

命題表示公式（2）例如：《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：定義：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

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

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

q

。。。。。。命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：《人工智能原理》第三章歸結(jié)推理方法命題邏輯基礎(chǔ)定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個(gè)成真賦值，則稱A為可滿足的；析取范式：僅由有限個(gè)簡(jiǎn)單合取式組成的析取式。合取范式：僅由有限個(gè)簡(jiǎn)單析取式組成的合取式。命題邏輯基礎(chǔ)定義：《人工智能原理》第三章歸結(jié)推理方法命題邏輯基礎(chǔ)基本等值式24個(gè)(1)交換率：p∨q<=>q

∨p

；

pΛq<=>qΛp

結(jié)合率：(p∨q)∨

r<=>p∨(q∨r); (pΛq)Λ

r<=>pΛ(qΛr)分配率：p∨(qΛ

r)<=>(p∨q)Λ(p∨r)

；

pΛ(q∨

r)<=>(pΛq)∨(pΛr)

命題邏輯基礎(chǔ)基本等值式24個(gè)(1)《人工智能原理》第三章歸結(jié)推理方法命題邏輯基礎(chǔ)基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊(yùn)含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

命題邏輯基礎(chǔ)基本等值式（1）《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）例：

命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

命題邏輯的歸結(jié)法基本單元：簡(jiǎn)單命題（陳述句）《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法建立子句集合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

命題邏輯的歸結(jié)法建立子句集《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法歸結(jié)式消除互補(bǔ)對(duì)，求新子句→得到歸結(jié)式。如子句：C1,C2， 歸結(jié)式：R(C1,C2)=C1ΛC2

注意：C1ΛC2→R(C1,C2)

，反之不一定成立。命題邏輯的歸結(jié)法歸結(jié)式《人工智能原理》第三章歸結(jié)推理方法命題邏輯的歸結(jié)法歸結(jié)過程

將命題寫成合取范式求出子句集對(duì)子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。命題邏輯的歸結(jié)法歸結(jié)過程《人工智能原理》第三章歸結(jié)推理方法命題邏輯歸結(jié)例題（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}命題邏輯歸結(jié)例題（1）例題，證明公式：(P→Q)→(《人工智能原理》第三章歸結(jié)推理方法命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

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

， （2，4歸結(jié)）

由上可得原公式成立。命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法第三章歸結(jié)推理方法概述命題邏輯的歸結(jié)法謂詞歸結(jié)子句形歸結(jié)原理歸結(jié)過程的策略控制Herbrand定理第三章歸結(jié)推理方法概述《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)一階邏輯基本概念個(gè)體詞：表示主語的詞謂詞：刻畫個(gè)體性質(zhì)或個(gè)體之間關(guān)系的詞量詞：表示數(shù)量的詞謂詞歸結(jié)原理基礎(chǔ)一階邏輯《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)

小王是個(gè)工程師。

8是個(gè)自然數(shù)。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個(gè)體詞，而“是個(gè)工程師”、“是個(gè)自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個(gè)謂詞表示的是事物的性質(zhì)，第三個(gè)謂詞“去買”表示的一個(gè)動(dòng)作也表示了主、賓兩個(gè)個(gè)體詞的關(guān)系，最后一個(gè)謂詞“是朋友”表示兩個(gè)個(gè)體詞之間的關(guān)系。謂詞歸結(jié)原理基礎(chǔ) 小王是個(gè)工程師。《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)一階邏輯公式及其解釋個(gè)體常量：a,b,c個(gè)體變量：x,y,z謂詞符號(hào)：P,Q,R量詞符號(hào)：

,謂詞歸結(jié)原理基礎(chǔ)一階邏輯《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個(gè)體域D為人類集合時(shí)，可符號(hào)化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百歲以上。在個(gè)體域D是全總個(gè)體域時(shí)，引入特殊謂詞R(x)表示x是人，可符號(hào)化為：（1）x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

謂詞歸結(jié)原理基礎(chǔ)例如：（1）所有的人都是要死的?！度斯ぶ悄茉怼返谌職w結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)量詞否定等值式：～(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

）謂詞歸結(jié)原理基礎(chǔ)量詞否定等值式：《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)原理基礎(chǔ)量詞轄域收縮與擴(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）謂詞歸結(jié)原理基礎(chǔ)量詞轄域收縮與擴(kuò)張等值式：《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)SKOLEM標(biāo)準(zhǔn)形前束范式

定義：說公式A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)SKOLEM標(biāo)準(zhǔn)形《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)即：把所有的量詞都提到前面去，然后消掉所有量詞

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)約束變項(xiàng)換名規(guī)則：(Qx

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)即：把所有的量詞都《人工智能原理》第三章歸結(jié)推理方法謂詞歸結(jié)子句形(Skolem標(biāo)準(zhǔn)形)