第三講-知識推理

知識推理

主講人：韓璐課前索引

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

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

【課前思考】

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

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

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

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

如何證明一個邏輯等式為真？

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

什么是子句集？

什么叫歸結(jié)

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

【主要內(nèi)容】

理解邏輯是人工智能的基本工具。認識歸結(jié)方法是實現(xiàn)定理機器證明的一種方法，歸結(jié)過程簡單明了，而且歸結(jié)法對于謂詞邏輯描述的定理集來說是完備的。會用歸結(jié)法證明定理。理解Herbrad定理給出了一階邏輯的半可判定算法?！局R點】

命題邏輯的歸結(jié)

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

Skolem標準形的定義，子句和子句集，Skolem定理及推廣

H域、H解釋、語義樹、Herbrand定理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例如：

由命題邏輯描述的命題：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ī)則證明該條定理(事實)成立。注意：本課程只討論一階謂詞邏輯描述下的歸結(jié)推理方法，不涉及高階謂詞邏輯問題

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

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

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

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

·命題：真假確定的簡單陳述句

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

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

·蘊含式：如果p則q，記做p→q

·等價式：p當且僅當q，記做pq

·若A無成假賦值，則稱A為重言式或永真式；

·若A無成真賦值，則稱A為矛盾式或永假式；

·若A至少有一個成真賦值，則稱A為可滿足的；

·析取范式：僅由有限個簡單合取式組成的析取式

·合取范式：僅由有限個簡單析取式組成的合取式

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

合取范式

范式：范式是公式的標準形式，公式往往需要變換為同它等價的范式，以便對它們作一般性的處理。

合取范式：單元子句、單元子句的或(∨)的與(∧)。

如：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是合取范式形式下的子命題(元素)的集合。

子句集是合取范式中各個合取分量的集合，生成子句集的過程可以簡單地理解為將命題公式的合取范式中的與符號"∧"，置換為逗號"，"。

上例轉(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é)推理的核心是求兩個子句的歸結(jié)式，因此需要先討論歸結(jié)式的定義和性質(zhì)。

歸結(jié)式的定義：

設(shè)C1和C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么可從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'

存在互補對P和～P，

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

注意：C1ΛC2→C12

，反之不一定成立。

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

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

有子句：C1＝P∨C1‘，

C2＝～P∨C2’

存在互補對P和～P，

證明：設(shè)I是使C1，C2為真的任一解釋，若I下的P為真，從而～P為假，必有I下C2‘為真，故C12為真。若不然，在I下P為假，從而I下C1’為真，故I下C12為真。于是C1∧C2為真。于是C1∧C2→R(C1,C2)成立。

反之不一定成立，因為存在一個使C1‘∨C2’為真的解釋I，不妨設(shè)C1‘為真，C2’為假。若P為真，則～P∨C2‘就為假了。因此反之不一定成立。由此可得歸結(jié)式的性質(zhì)。

歸結(jié)式的性質(zhì)：歸結(jié)式C12是親本子句C1和C2的邏輯結(jié)論。第三章知識推理3.2命題邏輯的歸結(jié)

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

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

2求取合取范式

3建立子句集

4歸結(jié)

歸結(jié)步驟：

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

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

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

(證明完畢)

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

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

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

前項化為合取范式：P→Q＝～P∨Q

后項化為合取范式：～(～Q→～P)＝～(Q∨～P)＝～Q∧P

兩項合并后化為合取范式：(～P∨Q)∧～Q∧P

則子句集為：

{～P∨Q，～Q，P}

對子句集中的子句進行歸結(jié)可得：

1.～P∨Q

2.～Q

3.P

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

5.□，(2，4歸結(jié))

由上可得原公式成立。

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

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

Skolem標準形前束范式中消去所有的存在量詞，則稱這種形式的謂詞公式為Skolem標準形。

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

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

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

量詞消去原則：

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

2)略去全稱量詞“”，簡單地省略掉該量詞。

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

歸結(jié)推理所需的子句集S可由下面的步驟求?。?/p>

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

2.消去前束范式中的存在變量，略去其中的任意變量，生成Skolem標準形

3.將Skolem標準形中的各個子句提出，表示為集合形式

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

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

則SG=∪Si

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

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

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

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

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

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

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

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)的形式，這時若H0={a,b},則H1中除有f(a,a),f(b,a)外，還出現(xiàn)f(a,b),f(b,b)

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

原子集A：

為研究子句集S中的不可滿足性，需要討論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上任何一組真值的指派稱為一個解釋。

H解釋：子句集S在的H域上的解釋稱為H解釋。

I是H域下的一個指派。簡單地說，原子集A中的各元素真假組合都是H的解釋(或真或假只取一個)?；蛘哒f凡對A中各元素真假值的一個具體設(shè)定，都是S的一個H解釋。第三章歸結(jié)推理方法3.4Herbrand定理例：S＝{P(x)∨Q(x),R(f(y))}，求其一個H解釋I*

解：S的H域為：{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

這是因為子句集S＝{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ù)語的定義：

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

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

關(guān)鍵：

對于公式G的所有的解釋，如果公式取值全為假，才可以判定G是不可滿足的。因為所有解釋代表了所有的情況，如果這些解釋可以被窮舉，我們就可以在有限的步數(shù)內(nèi)判斷公式G的不可滿足性，本小節(jié)開始所提的問題便可解決。

定理1：子句集S是不可滿足的，當且僅當S的一切H解釋都為假。

定理2(Herbrand定理)：子句集S是不可滿足的，當且僅當對每一個解釋I下，至少存在一個有限的不可滿足的基子句集S’。

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

雖然Herbrand定理給出了推理算法，但這種方法需逐次生成基例集S0’,S1’,…再檢驗Si’的不可滿足性，這常常是難以實現(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個元素。

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

H2：元素個數(shù)有63數(shù)量級

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

由于S是可滿足的基例集，還要繼續(xù)這個過程，建立S3’,S4’,直到S5’才是不可滿足。然而S5‘元素個數(shù)已達(1064)4數(shù)量級上，這是當今計算機無法處理的。

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

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

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

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

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

＝W2

＝…＝Wn,則稱是W的一個合一，稱W是可以合一的。第三章歸結(jié)推理方法3.5歸結(jié)原理歸結(jié)過程

謂詞邏輯的歸結(jié)過程與命題邏輯的歸結(jié)過程相比，其基本步驟相同，但每步的處理對象不同。謂詞邏輯需要把由謂詞構(gòu)成的公式集化為子句集，必要時在得到歸結(jié)式前要進行置換和合一。

·具體的謂詞邏輯歸結(jié)過程如下：

·寫出謂詞關(guān)系公式

·用反演法寫出謂詞表達式

·化為Skolem標準形

·求取子句集S

·對S中可歸結(jié)的子句做歸結(jié)

·歸結(jié)式仍放入S中，反復(fù)歸結(jié)過程

·得到空子句

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

使用反演法后得:

G＝A∧～B

第三章歸結(jié)推理方法3.5歸結(jié)原理例："快樂學(xué)生"問題：

假設(shè)任何通過計算機考試并獲獎的人都是快樂的，任何肯學(xué)習(xí)或幸運的人都可以通過所有的考試，張不肯學(xué)習(xí)但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。

解：先將問題用謂詞表示如下：

R1:"任何通過計算機考試并獲獎的人都是快樂的"

(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))

R2:"任何肯學(xué)習(xí)或幸運的人都可以通過所有考試"

(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))

R3:"張不肯學(xué)習(xí)但他是幸運的"

～Study(zhang)∧Lucky(zhang)

R4:"任何幸運的人都能獲獎"

(x)(Luck(x)→Win(x,prize))

結(jié)論"張是快樂的"的否定

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

將上述謂詞公式轉(zhuǎn)化為子句集并進行歸結(jié)如下：

首先將每一個表示邏輯條件的謂詞子句轉(zhuǎn)換為子句集可以接受的Skolem標準形。

由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é)法的實質(zhì)：

·歸結(jié)法是僅有一條推理規(guī)則的推理方法。

·歸結(jié)的過程是一個歸結(jié)樹的過程。

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

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

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

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

首先引入謂詞：

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

R(s)表示