第三講-知識(shí)推理

知識(shí)推理

主講人：韓璐課前索引

【學(xué)習(xí)目標(biāo)】

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

【課前思考】

Herbrand定理和歸結(jié)法之間的關(guān)系。

在命題邏輯中，歸結(jié)法的邏輯基礎(chǔ)是什么？

什么樣的命題可以由歸結(jié)法來(lái)證明？

謂詞邏輯和命題邏輯的區(qū)別和聯(lián)系是什么？

如何證明一個(gè)邏輯等式為真？

什么是合取范式和析取范式？

什么是子句集？

什么叫歸結(jié)

什么叫歸結(jié)策略第三章歸結(jié)推理方法課前索引

【主要內(nèi)容】

理解邏輯是人工智能的基本工具。認(rèn)識(shí)歸結(jié)方法是實(shí)現(xiàn)定理機(jī)器證明的一種方法，歸結(jié)過(guò)程簡(jiǎn)單明了，而且歸結(jié)法對(duì)于謂詞邏輯描述的定理集來(lái)說(shuō)是完備的。會(huì)用歸結(jié)法證明定理。理解Herbrad定理給出了一階邏輯的半可判定算法。【知識(shí)點(diǎn)】

命題邏輯的歸結(jié)

謂詞邏輯的前束范式，約束變量換名規(guī)則

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

H域、H解釋、語(yǔ)義樹(shù)、Herbrand定理

合一和置換，歸結(jié)過(guò)程第三章歸結(jié)推理方法3.1概述

什么是推理所謂推理是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過(guò)程。推理所用的事實(shí)可分為兩種情況：一種是與求解問(wèn)題有關(guān)的初始證據(jù)，另一種是推理過(guò)程中所得到的中間結(jié)論。智能系統(tǒng)的推理過(guò)程是通過(guò)推理機(jī)來(lái)完成的。推理機(jī)是智能系統(tǒng)中用來(lái)實(shí)現(xiàn)推理的那些程序。智能系統(tǒng)的推理包括兩個(gè)基本問(wèn)題：一個(gè)是推理的方法，另一個(gè)是推理的控制策略。第三章歸結(jié)推理方法3.1概述

推理方法及其分類(lèi)推理方法主要解決在推理過(guò)程中前提與結(jié)論之間的邏輯關(guān)系，以及在非精確性推理中不確定性的傳遞問(wèn)題。

1．按推理的邏輯基礎(chǔ)分類(lèi)常用的推理方法可分為演繹推理、歸納推理和默認(rèn)推理。

(1)演繹推理是從已知的一般性知識(shí)出發(fā)，去推出蘊(yùn)含在這些已知知識(shí)中的適合于某種個(gè)別情況的結(jié)論。它是一種由一般到個(gè)別的推理方法，其核心是三段論。常用的三段論是由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論三部分組成的。大前提是已知的一般性知識(shí)或推理過(guò)程得到的判斷；小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。第三章歸結(jié)推理方法3.1概述

例如，有如下三個(gè)判斷：①計(jì)算機(jī)系的學(xué)生都會(huì)編程序；②程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生；③程強(qiáng)會(huì)編程序。這是一個(gè)三段論推理。其中，①是大前提，②是小前提；③是經(jīng)演繹推出來(lái)的結(jié)論。演繹推理就是從已知的大前提中推導(dǎo)出適應(yīng)于小前提的結(jié)論，即從已知的一般性知識(shí)中抽取所包含的特殊性知識(shí)。由此可見(jiàn)，只要大前提和小前提是正確的，則由它們推出的結(jié)論也必然是正確的。第三章歸結(jié)推理方法3.1概述

(2)歸納推理從一類(lèi)事物的大量特殊事例出發(fā)，去推出該類(lèi)事物的一般性結(jié)論。它是一種由個(gè)別到一般的推理方法。歸納推理的基本思想是：先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn)，數(shù)學(xué)歸納法就是歸納推理的一種典型例子。按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理；按照推理所使用的方法可分為枚舉歸納推理、類(lèi)比歸納推理、統(tǒng)計(jì)歸納推理和差異歸納推理等。

(3)默認(rèn)推理是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理，因此也稱(chēng)為缺省推理。在推理過(guò)程中，如果發(fā)現(xiàn)原先的假設(shè)不正確，就撤消原來(lái)的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新按新情況進(jìn)行推理。第三章歸結(jié)推理方法3.1概述

(4)演繹推理與歸納推理的區(qū)別演繹推理是在已知領(lǐng)域內(nèi)的一般性知識(shí)的前提下，通過(guò)演繹求解一個(gè)具體問(wèn)題或者證明一個(gè)結(jié)論的正確性。它所得出的結(jié)論實(shí)際上早已蘊(yùn)含在一般性知識(shí)的前提中，演繹推理只不過(guò)是將已有事實(shí)揭示出來(lái)，因此它不能增殖新知識(shí)。歸納推理所推出的結(jié)論是沒(méi)有包含在前提內(nèi)容中的。這種由個(gè)別事物或現(xiàn)象推出一般性知識(shí)的過(guò)程，是增殖新知識(shí)的過(guò)程。例如，一位計(jì)算機(jī)維修員，當(dāng)他剛開(kāi)始從事這項(xiàng)工作時(shí)，只有書(shū)本知識(shí)，而無(wú)實(shí)際經(jīng)驗(yàn)。但當(dāng)他經(jīng)過(guò)一段時(shí)間的工作實(shí)踐后，就會(huì)通過(guò)大量實(shí)例積累起來(lái)一些經(jīng)驗(yàn)，這些經(jīng)驗(yàn)就是由一個(gè)個(gè)實(shí)例歸納出來(lái)的一般性知識(shí)，采用的是歸納推理方式。當(dāng)它有了這些一般性知識(shí)后，就可以運(yùn)用這些知識(shí)去完成計(jì)算機(jī)的維修工作。而這種為某一臺(tái)具體的計(jì)算機(jī)運(yùn)用一般性知識(shí)進(jìn)行維修的過(guò)程則是演繹推理。第三章歸結(jié)推理方法3.1概述

2．按所用知識(shí)的確定性分類(lèi)可分為確定性推理和不確定性推理。確定性推理是指推理所使用的知識(shí)和推出的結(jié)論都是可以精確表示的,其真值要么為真,要么為假,不會(huì)有第三種情況出現(xiàn)。不確定性推理是指推理時(shí)所用的知識(shí)不都是確定的，推出的結(jié)論也不完全是確定的，其真值會(huì)位于真與假之間。由于現(xiàn)實(shí)世界中的大多數(shù)事物都具有一定程度的不確定性，并且這些事物是很難用精確的數(shù)學(xué)模型來(lái)進(jìn)行表示與處理的，因此不確定性推理也就成了人工智能的一個(gè)重要研究課題。第三章歸結(jié)推理方法3.1概述

3．按推理過(guò)程的單調(diào)性分為單調(diào)推理與非單調(diào)推理單調(diào)推理指在推理過(guò)程中，每當(dāng)使用新的知識(shí)后，所得到的結(jié)論會(huì)越來(lái)越接近于目標(biāo)，而不會(huì)出現(xiàn)反復(fù)情況，即不會(huì)由于新知識(shí)的加入否定了前面推出的結(jié)論，從而使推理過(guò)程又退回到先前的某一步。非單調(diào)推理是指在推理過(guò)程中，當(dāng)某些新知識(shí)加入后，會(huì)否定原來(lái)推出的結(jié)論，使推理過(guò)程退回到先前的某一步。非單調(diào)推理往往是在知識(shí)不完全的情況下發(fā)生的。在這種情況下，為使推理能夠進(jìn)行下去，就需要先作某些假設(shè)，并在此假設(shè)的基礎(chǔ)上進(jìn)行推理。但是，當(dāng)后來(lái)由于新的知識(shí)加入，發(fā)現(xiàn)原來(lái)的假設(shè)不正確時(shí)，就需要撤銷(xiāo)原來(lái)的假設(shè)以及由此假設(shè)為基礎(chǔ)推出的一切結(jié)論，再運(yùn)用新知識(shí)重新進(jìn)行推理。第三章歸結(jié)推理方法3.1概述

4.推理的控制策略及其分類(lèi)智能系統(tǒng)的推理過(guò)程相當(dāng)于人類(lèi)的思維過(guò)程，它不僅依賴(lài)于所用的推理方法，同時(shí)也依賴(lài)于推理的控制策略。推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理過(guò)程盡快達(dá)到目標(biāo)的策略。由于智能系統(tǒng)的推理過(guò)程一般表現(xiàn)為一種搜索過(guò)程，因此，推理的控制策略又可分為推理策略和搜索策略。推理策略主要解決推理方向、沖突消解等問(wèn)題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等；搜索策略主要解決推理線(xiàn)路、推理效果、推理效率等問(wèn)題。推理方向用來(lái)確定推理的控制方式，即推理過(guò)程是從初始證據(jù)開(kāi)始到目標(biāo)，還是從目標(biāo)開(kāi)始到初始證據(jù)。按照對(duì)推理方向的控制，推理可分為正向推理、逆向推理、混合推理及雙向推理四種情況。無(wú)論哪一種推理方式，系統(tǒng)都需要有一個(gè)存放知識(shí)的知識(shí)庫(kù)，一個(gè)存放初始證據(jù)及中間結(jié)果的綜合數(shù)據(jù)庫(kù)和一個(gè)用于推理的推理機(jī)。第三章歸結(jié)推理方法3.1概述

歸結(jié)原理由J.A.Robinson于1965年提出，又稱(chēng)為消解原理。

其基本思路是：要證明在一個(gè)論域上一個(gè)事件是永真的，就要證明在該域中的每一個(gè)點(diǎn)上該事實(shí)都成立。很顯然，論域是不可數(shù)時(shí)，該問(wèn)題不可能解決。即使可數(shù)，如果該輪域是無(wú)限的，問(wèn)題也無(wú)法簡(jiǎn)單地解決。

Herbrand采用了反證法的思想，將永真性的證明問(wèn)題轉(zhuǎn)化成為不可滿(mǎn)足性的證明問(wèn)題。

歸結(jié)法的基本原理是采用反證法或者稱(chēng)為反演推理方法，將待證明的表達(dá)式(定理)轉(zhuǎn)換成為邏輯公式(謂詞公式)，然后再進(jìn)行歸結(jié)，歸結(jié)能夠順利完成，則證明原公式(定理)是正確性的。第三章歸結(jié)推理方法3.1概述

例如：

由命題邏輯描述的命題：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é)推理方法，不涉及高階謂詞邏輯問(wèn)題

本章首先介紹了命題邏輯的歸結(jié)，并以此為基礎(chǔ)介紹了謂詞邏輯的歸結(jié)過(guò)程及相關(guān)的思想、概念和定義，最后給出了謂詞邏輯歸結(jié)的基礎(chǔ)Herbrand定理的一般形式。

第三章歸結(jié)推理方法3.2命題邏輯的歸結(jié)

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

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

·命題：真假確定的簡(jiǎn)單陳述句

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

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

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

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

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

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

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

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

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

數(shù)理邏輯的基本等值式(略)第三章歸結(jié)推理方法3.2命題邏輯的歸結(jié)

合取范式

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

合取范式：?jiǎn)卧泳?、單元子句的?∨)的與(∧)。

如：P∧(P∨Q)∧(～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)第三章歸結(jié)推理方法3.2命題邏輯的歸結(jié)

子句集

命題公式的子句集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}第三章歸結(jié)推理方法3.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，則稱(chēng)這一個(gè)過(guò)程為歸結(jié)，稱(chēng)C12為C1和C2的歸結(jié)式，稱(chēng)C1和C2為C12的親本子句。

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

C2＝～P∨C2'

存在互補(bǔ)對(duì)P和～P，

則可得歸結(jié)式：C12=C1'∨C2'

注意：C1ΛC2→C12

，反之不一定成立。

第三章歸結(jié)推理方法3.2命題邏輯的歸結(jié)

下面證明歸結(jié)式是原兩子句的邏輯推論，或者說(shuō)任一使C1、C2為真的解釋I下必有歸結(jié)式C12也為真。(C1ΛC2→C12)

有子句：C1＝P∨C1‘，

C2＝～P∨C2’

存在互補(bǔ)對(duì)P和～P，

證明：設(shè)I是使C1，C2為真的任一解釋?zhuān)鬒下的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是親本子句C1和C2的邏輯結(jié)論。第三章知識(shí)推理3.2命題邏輯的歸結(jié)

命題邏輯的歸結(jié)方法推理過(guò)程可以分為如下幾個(gè)步驟：

1建立待歸結(jié)命題公式：首先根據(jù)反證法將所求證的問(wèn)題轉(zhuǎn)化成為命題公式，求證其是矛盾式(永假式)。

2求取合取范式

3建立子句集

4歸結(jié)

歸結(jié)步驟：

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

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

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

(證明完畢)

得到空子句俄e，表示S是不可滿(mǎn)足的(矛盾)，故原命題成立。第三章歸結(jié)推理方法3.2命題邏輯的歸結(jié)

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

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

前項(xiàng)化為合取范式：P→Q＝～P∨Q

后項(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.□，(2，4歸結(jié))

由上可得原公式成立。

謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過(guò)程一樣。第三章歸結(jié)推理方法3.3謂詞邏輯歸結(jié)法基礎(chǔ)

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

Skolem標(biāo)準(zhǔn)形前束范式中消去所有的存在量詞，則稱(chēng)這種形式的謂詞公式為Skolem標(biāo)準(zhǔn)形。

前束范式：A是一個(gè)前束范式，如果A中的一切量詞都位于該公式的最左邊(不含否定詞)，且這些量詞的轄域都延伸到公式的末端。其形式為：(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn),Qi為量詞符號(hào)。

Skolem標(biāo)準(zhǔn)形的轉(zhuǎn)化過(guò)程為：依據(jù)約束變量換名規(guī)則，首先把公式變型為前束范式，然后依照量詞消去原則消去或者略去所有量詞。第三章歸結(jié)推理方法3.3謂詞邏輯歸結(jié)法基礎(chǔ)

下面例子描述了Skolem標(biāo)準(zhǔn)形的轉(zhuǎn)化過(guò)程第三章歸結(jié)推理方法3.3謂詞邏輯歸結(jié)法基礎(chǔ)

量詞消去原則：

1)消去存在量詞“”，即，將該量詞約束的變量用任意常量(a,b等)、或全稱(chēng)變量的函數(shù)(f(x),g(y)等)代替。如果存在量詞左邊沒(méi)有任何全稱(chēng)量詞，則只將其改寫(xiě)成為常量；如果是左邊有全稱(chēng)量詞的存在量詞，消去時(shí)該變量改寫(xiě)成為全稱(chēng)量詞的函數(shù)。

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

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

歸結(jié)推理所需的子句集S可由下面的步驟求取：

1.謂詞公式G轉(zhuǎn)換成前束范式(離散數(shù)學(xué))；

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

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

注意：Skolem標(biāo)準(zhǔn)形必須滿(mǎn)足合取范式的條件。在生成子句集之前邏輯表達(dá)式必須是各“謂詞表達(dá)式”或“謂詞或表達(dá)式”的與。第三章歸結(jié)推理方法3.3謂詞邏輯歸結(jié)法基礎(chǔ)定理:謂詞表達(dá)式G是不可滿(mǎn)足當(dāng)且僅當(dāng)其子句集S是不可滿(mǎn)足。

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

則SG=∪Si

第三章歸結(jié)推理方法3.4Herbrand定理Herbrand定理思想：因?yàn)榱吭~是任意的，所討論的個(gè)體變量域D是任意的，所以解釋的個(gè)數(shù)是無(wú)限、不可數(shù)的，要找到所有的解釋是不可能的。Herbrand定理的基本思想是簡(jiǎn)化討論域，建立一個(gè)比較簡(jiǎn)單、特殊的域，使得只要在這個(gè)論域上(此域稱(chēng)為H域)，原謂詞公式仍是不可滿(mǎn)足的，即保證不可滿(mǎn)足的性質(zhì)不變。

H域和D域關(guān)系的如下圖表示：第三章歸結(jié)推理方法3.4Herbrand定理H域(Herbrand域)的定義：

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

Hi=Hi-1∪{所有形如f(t1,…,tn)的元素}

其中f(t1,…,tn)是出現(xiàn)于G中的任一函數(shù)符號(hào)，而t1,…,tn是Hi-1的元素，i=1,2,…。

規(guī)定H∞為G的H域(或說(shuō)是相應(yīng)的子句集S的H域)。

不難看出，H域是直接依賴(lài)于G的最多只有可數(shù)個(gè)元素。例:

S={P(a),～P(x)∨P(f(x))}

依定義有

H0={a}

H1={a}∪{f(a)}={a,f(a)}

H2={a,f(a)}∪{f(a),f(f(a))}={a,f(a),f(f(a))}

…

H∞={a,f(a),f(f(a)),…}第三章歸結(jié)推理方法3.4Herbrand定理例:

S={P(f(x),a,g(y),b)}

依定義有

H0={a,b}

H1={a,b,f(a),g(a),f(b),g(b)}

H2=(a,b,f(a),g(a),f(b),g(b),f(f(a)),f(g(a)),f(f(b)),f(g(b)),g(f(a)),g(g(a)),g(f(b)),g(g(b))}

…

H∞=H0∪H1∪H2…

如果在S中出現(xiàn)函數(shù)形如f(x,a)仍視為f(X1,X2)的形式，這時(shí)若H0={a,b},則H1中除有f(a,a),f(b,a)外，還出現(xiàn)f(a,b),f(b,b)

注意：一個(gè)函數(shù)中含有多個(gè)變量時(shí)，每個(gè)變量都要做到全部的組合。第三章歸結(jié)推理方法3.4Herbrand定理

原子集A：

為研究子句集S中的不可滿(mǎn)足性，需要討論H域上S中各謂詞的真值。這里原子集A為公式中出現(xiàn)的謂詞套上H域的元素組成的集合。例:

S={P(x)∨Q(x),R(f(y))}，有

H={a,f(a),f(f(a)),…}

A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),…}。

解釋I:

謂詞公式G在論域D上任何一組真值的指派稱(chēng)為一個(gè)解釋。

H解釋?zhuān)鹤泳浼疭在的H域上的解釋稱(chēng)為H解釋。

I是H域下的一個(gè)指派。簡(jiǎn)單地說(shuō)，原子集A中的各元素真假組合都是H的解釋(或真或假只取一個(gè))。或者說(shuō)凡對(duì)A中各元素真假值的一個(gè)具體設(shè)定，都是S的一個(gè)H解釋。第三章歸結(jié)推理方法3.4Herbrand定理例：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(mén)，出現(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)),…}。第三章歸結(jié)推理方法3.4Herbrand定理術(shù)語(yǔ)的定義：

沒(méi)有變量出現(xiàn)的原子、文字、子句和子句集，分別稱(chēng)為基原子、基文字、基子句和基子句集。

若一個(gè)解釋I*使得某個(gè)基子句為假，則此解釋I*為假。

關(guān)鍵：

對(duì)于公式G的所有的解釋?zhuān)绻饺≈等珵榧?，才可以判定G是不可滿(mǎn)足的。因?yàn)樗薪忉尨砹怂械那闆r，如果這些解釋可以被窮舉，我們就可以在有限的步數(shù)內(nèi)判斷公式G的不可滿(mǎn)足性，本小節(jié)開(kāi)始所提的問(wèn)題便可解決。

定理1：子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)S的一切H解釋都為假。

定理2(Herbrand定理)：子句集S是不可滿(mǎn)足的，當(dāng)且僅當(dāng)對(duì)每一個(gè)解釋I下，至少存在一個(gè)有限的不可滿(mǎn)足的基子句集S’。

第三章歸結(jié)推理方法3.5歸結(jié)原理

雖然Herbrand定理給出了推理算法，但這種方法需逐次生成基例集S0’,S1’,…再檢驗(yàn)Si’的不可滿(mǎn)足性，這常常是難以實(shí)現(xiàn)。

例:S＝{P(x,g(x),y,h(x,y),z,k(x,y,z)),～P(u,v,e(v),w,f(v,w),x)}

有H0＝{a}

S0’＝{P(a,g(a),a,h(a,a),a,k(a,a,a)),～P(a,a,e(a),a,f(a,a),a)}

H1={a,g(a),h(a,a),k(a,a,a),e(a),f(a,a)}共含6個(gè)元素。

S1’：對(duì)S中文字P的變量x,y,z均可取值于H1的6個(gè)元素，從而對(duì)文字P可構(gòu)成63種可能的形式。對(duì)文字～P的變量u,v,w,x也可取值于H1的6個(gè)元素。從而對(duì)文字～P可構(gòu)成64種可能的形式。故S有63+64=1512個(gè)元素。

H2：元素個(gè)數(shù)有63數(shù)量級(jí)

S2’：元素個(gè)數(shù)有(63)4數(shù)量級(jí)

由于S是可滿(mǎn)足的基例集，還要繼續(xù)這個(gè)過(guò)程，建立S3’,S4’,直到S5’才是不可滿(mǎn)足。然而S5‘元素個(gè)數(shù)已達(dá)(1064)4數(shù)量級(jí)上，這是當(dāng)今計(jì)算機(jī)無(wú)法處理的。

這樣簡(jiǎn)單例子說(shuō)明Herbrand定理所給的算法不能直接應(yīng)用。第三章歸結(jié)推理方法3.5歸結(jié)原理

1965年Robinson提出了歸結(jié)原理。謂詞邏輯的歸結(jié)法是以命題邏輯的歸結(jié)法為基礎(chǔ)，在Skolem標(biāo)準(zhǔn)形的子句集上，通過(guò)置換和合一進(jìn)行歸結(jié)的。

1．置換置換可定義為在一個(gè)謂詞公式中用置換項(xiàng)去替換變量，其一般形式可表示為有限集合：｛ti／xi，t2/x2，，tn／xn｝

xi是變量，ti是不同于xi的項(xiàng)，ti/xi表示用ti替換xi。例如｛a/x，b/y，f(c)/z｝是一個(gè)置換。

2．合一合一是通過(guò)對(duì)項(xiàng)進(jìn)行置換，使兩個(gè)謂詞公式達(dá)到一致的過(guò)程,通過(guò)合一，可把若干公式合為一個(gè)公式。合一的一般定義為：設(shè)有公式集w＝｛W1，W2，…，Wn｝，若存在一個(gè)置換，可使w1

＝W2

＝…＝Wn,則稱(chēng)是W的一個(gè)合一，稱(chēng)W是可以合一的。第三章歸結(jié)推理方法3.5歸結(jié)原理歸結(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ò)程

·得到空子句

·命題得證反演法舉例：A→B，其中A，B是謂詞公式，(求非蘊(yùn)含等值)

使用反演法后得:

G＝A∧～B

第三章歸結(jié)推理方法3.5歸結(jié)原理例："快樂(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)第三章歸結(jié)推理方法3.5歸結(jié)原理

將上述謂詞公式轉(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é)論的否定第三章歸結(jié)推理方法3.5歸結(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è)歸結(jié)樹(shù)的過(guò)程。

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

·傳統(tǒng)的歸結(jié)法不能處理相等的關(guān)系。第三章歸結(jié)推理方法3.5歸結(jié)原理上述例題的歸結(jié)樹(shù)的示例

第三章歸結(jié)推理方法3.5歸結(jié)原理例:猴子香蕉問(wèn)題

已知一串香蕉掛在天花板上，猴子直接去拿是夠不到的，但猴子可以走動(dòng)且可以搬著梯子走動(dòng)，也可以爬上梯子來(lái)達(dá)到吃香蕉的目的。對(duì)這個(gè)問(wèn)題的描述，不可忽視動(dòng)作的先后次序，需體現(xiàn)出時(shí)間概念。要引入狀態(tài)S來(lái)區(qū)分動(dòng)作的先后，以不同的狀態(tài)表現(xiàn)不同的時(shí)間，而狀態(tài)間的轉(zhuǎn)換由一些算子(函數(shù))來(lái)實(shí)現(xiàn)。

首先引入謂詞：

P(x,y,z,s)表示猴子位于x處，香蕉位于y處，梯子位于z處，相應(yīng)的狀態(tài)為s。此時(shí)，謂詞P(x,y,z,s)方為真。

R(s)表示