《人工智能》-第二章-知識表示方法

人工智能主講:吳順祥

教授模式識別與智能系統(tǒng)研究所Powerpoint中南大學智能系統(tǒng)與智能軟件研究所第二章知識表示方法2.0引言2.1狀態(tài)空間法2.2問題歸約法2.3謂詞邏輯法2.4語義網(wǎng)絡(luò)法2.5其他方法2.6小結(jié)中南大學智能系統(tǒng)與智能軟件研究所2.0引言信息科學有機體系的分支學科：信息獲取(感知與表示)、信息傳輸(通信與存儲)、信息處理(計算與認知)、信息再生(綜合與決策)、信息執(zhí)行(控制與顯示)知識成為由信息到智能的中介。知識的表示方法主要分為結(jié)構(gòu)化方法，包括邏輯方法和產(chǎn)生式方法非結(jié)構(gòu)化方法，包括語義網(wǎng)絡(luò)和框架等。3中南大學智能系統(tǒng)與智能軟件研究所2.0引言：數(shù)據(jù)、信息與知識2.0.1知識和知識表示數(shù)據(jù)一般指單獨的事實，是信息的載體。信息由符號組成，如文字和數(shù)字，但是對符號賦予了一定的意義，因此有一定的用途或價值。信息表示的是數(shù)據(jù)的含義。4中南大學智能系統(tǒng)與智能軟件研究所2.0引言：數(shù)據(jù)、信息與知識知識是由經(jīng)驗總結(jié)升華出來的，因此知識是經(jīng)驗的結(jié)晶。知識在信息的基礎(chǔ)上增加了上下文信息，提供了更多的意義，因此也就更加有用和有價值。知識是隨著時間的變化而動態(tài)變化的，新的知識可以根據(jù)規(guī)則和已有的知識推導出來。因此知識反映了信息之間的內(nèi)在關(guān)系或必然聯(lián)系。5中南大學智能系統(tǒng)與智能軟件研究所2.0引言：數(shù)據(jù)、信息與知識Feigenbaum認為知識是經(jīng)過加工的信息，它包括事實、信念和啟發(fā)式規(guī)則。Bernstein說知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。Hayes-Roth認為知識是事實、信念和啟發(fā)式規(guī)則。從知識庫觀點看，知識是某論域中所涉及的各有關(guān)方面、狀態(tài)的一種符號表示。6中南大學智能系統(tǒng)與智能軟件研究所2.0引言：數(shù)據(jù)、信息與知識人工智能系統(tǒng)所關(guān)心的知識

事實：是關(guān)于對象和物體的知識。規(guī)則：是有關(guān)問題中與事物的行動、動作相聯(lián)系的因果關(guān)系的知識。元知識：是有關(guān)知識的知識，是知識庫中的高層知識。常識性知識：泛指普遍存在而且被普遍認識了的客觀事實一類知識。7中南大學智能系統(tǒng)與智能軟件研究所2.0引言：數(shù)據(jù)、信息與知識知識表示就是研究用機器表示上述這些知識的可行性、有效性的一般方法，可以看作是將知識符號化并輸入到計算機的過程和方法。知識表示=數(shù)據(jù)結(jié)構(gòu)+處理機制知識表示的觀點：陳述性過程性8中南大學智能系統(tǒng)與智能軟件研究所2.0引言：數(shù)據(jù)、信息與知識陳述性知識表示和過程性知識表示各有優(yōu)缺點。(1)由于高級的智能行為似乎強烈地依賴于陳述性知識，因此AI的研究應(yīng)注重陳述性的開發(fā)。(2)過程性知識的陳述化表示。(3)以適當方式將過程性知識和陳述性知識綜合，可以提高智能系統(tǒng)的性能。9中南大學智能系統(tǒng)與智能軟件研究所2.0引言：知識-策略-智能策略就是關(guān)于如何解決問題的政策方略，包括在什么時間、什么地點、由什么主體采取什么行動、達到什么目標、注意什么事項等等一整套完整而具體的行動計劃規(guī)劃、行動步驟、工作方式和工作方法。10中南大學智能系統(tǒng)與智能軟件研究所2.0引言：知識-策略-智能“智能”應(yīng)當理解為：在給定的問題-問題環(huán)境-主體目的的條件下，智能就是有針對性地獲取問題-環(huán)境的信息，恰當?shù)貙@些信息進行處理以提煉知識達到認知，在此基礎(chǔ)上，把已有的知識與主體的目的信息相結(jié)合，合理地產(chǎn)生解決問題的策略信息，并利用所得到的策略信息在給定的環(huán)境下成功地解決問題達到主體的目的。11中南大學智能系統(tǒng)與智能軟件研究所2.0引言：知識-策略-智能4個要素包括信息知識策略行為4個能力包括獲取有用信息的能力由信息生成知識(認知)的能力由知識和目的生成策略(決策)的能力實施策略取得效果(施效)的能力12中南大學智能系統(tǒng)與智能軟件研究所2.0引言：知識-策略-智能信息、知識、智能之間的關(guān)系：信息是基本資源；知識是對信息進行加工所得到的抽象化產(chǎn)物；策略是由客體信息和主體目標演繹出來的智慧化身，智能是把信息資源加工成知識、進而把知識激活成解決問題的策略并在策略信息引導下具體解決問題的全部能力。信息、知識、智能關(guān)系，正好符合人類自身認識世界和優(yōu)化世界活動過程中由信息生成知識、由知識激活智能的過程總結(jié)：信息經(jīng)加工提煉而成知識，知識被目的激活而成智能。13中南大學智能系統(tǒng)與智能軟件研究所2.0引言：智能中“信息-知識-策略”關(guān)系獲取信息的功能由感覺器官完成，傳遞信息的功能由神經(jīng)系統(tǒng)完成，處理信息和再生信息的功能由思維器官完成，施用信息的功能由效應(yīng)器官完成。14中南大學智能系統(tǒng)與智能軟件研究所2.0引言：AI對知識表示方法的要求(1)表示能力，要求能夠正確、有效地將問題求解所需要的各類知識都表示出來。(2)可理解性，所表示的知識應(yīng)易懂、易讀。(3)便于知識的獲取，使得智能系統(tǒng)能夠漸進地增加知識，逐步進化。(4)便于搜索，表示知識的符號結(jié)構(gòu)和推理機制應(yīng)支持對知識庫的高效搜索，使得智能系統(tǒng)能夠迅速地感知事物之間的關(guān)系和變化；同時很快地從知識庫中找到有關(guān)的知識。(5)便于推理，要能夠從己有的知識中推出需要的答案和結(jié)論。15中南大學智能系統(tǒng)與智能軟件研究所2.0引言：知識的分類形態(tài)性知識、內(nèi)容性知識、效用性知識三者的綜合，構(gòu)成了知識的完整概念16中南大學智能系統(tǒng)與智能軟件研究所2.1狀態(tài)空間法

（StateSpaceRepresentation）問題求解技術(shù)主要是兩個方面：問題的表示求解的方法狀態(tài)空間法狀態(tài)（state）算符（operator）狀態(tài)空間方法17中南大學智能系統(tǒng)與智能軟件研究所2.1.1

問題狀態(tài)描述定義狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合。其矢量形式如下：

Q=［q0,q1,…,qn］T式中每個元素qi(i=0,1，…，n)為集合的分量，稱為狀態(tài)變量。給定每個分量的一組值就得到一個具體的狀態(tài)，如

qk=［q０k,q1k,…,qnk］T

2.1狀態(tài)空間法18中南大學智能系統(tǒng)與智能軟件研究所2.1.1

問題狀態(tài)描述算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學算子、運算符號或邏輯符號等。問題的狀態(tài)空間(statespace)

：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標狀態(tài)集合G。因此，可把狀態(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。19中南大學智能系統(tǒng)與智能軟件研究所2.

狀態(tài)空間表示概念詳釋對一個問題的狀態(tài)描述，必須確定3件事：(1)該狀態(tài)描述方式，特別是初始狀態(tài)描述；(2)操作符集合及其對狀態(tài)描述的作用；(3)目標狀態(tài)描述的特性。例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1狀態(tài)空間法20中南大學智能系統(tǒng)與智能軟件研究所例:三數(shù)碼難題

（3puzzleproblem）123123123312312312初始棋局目標棋局2.1狀態(tài)空間法21中南大學智能系統(tǒng)與智能軟件研究所2.1.2狀態(tài)圖示法圖論中的幾個術(shù)語

·

節(jié)點(node)：圖形上的匯合點，用來表示狀態(tài)、事件和時間關(guān)系的匯合，也可用來指示通路的匯合；·弧線(arc)：節(jié)點間的連接線；·有向圖(directedgraph)：一對節(jié)點用弧線連接起來，從一個節(jié)點指向另一個節(jié)點。·

后繼節(jié)點(descendantnode)與父輩節(jié)點(parentnode)：如果某條弧線從節(jié)點ni指向節(jié)點nj，那么節(jié)點nj就叫做節(jié)點ni的后繼節(jié)點或后裔，而節(jié)點ni叫做節(jié)點nj的父輩節(jié)點或祖先。22中南大學智能系統(tǒng)與智能軟件研究所2.1.2狀態(tài)圖示法路徑：某個節(jié)點序列(ni1,ni2,…,nik)當j=2，3,…,k時，如果對于每一個ni，nj-1都有一個后繼節(jié)點nij存在，那么就把這個節(jié)點序列叫做從節(jié)點ni1至節(jié)點nik的長度為k的路徑。代價：用c(ni,nj)來表示從節(jié)點ni指向節(jié)點nj的那段弧線的代價。兩節(jié)點間路徑的代價等于連接該路徑上各節(jié)點的所有弧線代價之和。顯式表示：各節(jié)點及其具有代價的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點、它的后繼節(jié)點以及連接弧線的代價。隱式表示：節(jié)點的無限集合{si}作為起始節(jié)點是已知的。后繼節(jié)點算符Γ也是已知的，它能作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價。23中南大學智能系統(tǒng)與智能軟件研究所圖的顯示說明和隱示說明一個圖可由顯式說明也可由隱式說明。顯然，顯式說明對于大型的圖是不切實際的，而對于具有無限節(jié)點集合的圖則是不可能的。把后繼算符應(yīng)用于節(jié)點的過程，就是擴展一個節(jié)點的過程。因此，搜索某個狀態(tài)空間以求得算符序列的一個解答的過程，就對應(yīng)于使隱式圖足夠大一部分變?yōu)轱@式以便包含目標的過程。這樣的搜索圖是狀態(tài)空間問題求解的主要基礎(chǔ)。

問題的表示對求解工作量有很大的影響。人們顯然希望有較小的狀態(tài)空間表示。許多似乎很難的問題，當表示適當時就可能具有小而簡單的狀態(tài)空間。2.1.2狀態(tài)圖示法AB2.1狀態(tài)空間法24中南大學智能系統(tǒng)與智能軟件研究所2.1.3狀態(tài)空間表示舉例產(chǎn)生式系統(tǒng)（productionsystem）一個總數(shù)據(jù)庫：它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫可能簡單，或許復雜。一套規(guī)則：它對數(shù)據(jù)庫進行操作運算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時所完成的動作。一個控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當數(shù)據(jù)庫的終止條件滿足時，就停止計算。2.1狀態(tài)空間法25中南大學智能系統(tǒng)與智能軟件研究所

狀態(tài)空間表示舉例例：猴子和香蕉問題2.1狀態(tài)空間法26中南大學智能系統(tǒng)與智能軟件研究所解題過程

用一個四元表列（W，x，Y，z）來表示這個問題狀態(tài).其中：W-猴子的水平位置；x－當猴子在箱子頂上時取x=1；否則取x=0；Y－箱子的水平位置；z-當猴子摘到香蕉時取z=1；否則取z=0。這個問題的操作（算符）如下：

goto（U）表示猴子走到水平位置U或者用產(chǎn)生式規(guī)則表示為（W，0，Y，z）

goto（U）（U，0，Y，z）2.1狀態(tài)空間法27中南大學智能系統(tǒng)與智能軟件研究所pushbox（V）猴子把箱子推到水平位置V，即有

（W，0，W，z）

pushbox（V）（V，0，V，z）climbbox猴子爬上箱頂，即有

（W，0，W，z）

climbbox

（W，1，W，z）grasp猴子摘到香蕉，即有

（c，1，c，0）grasp（c，1，c，1）2.1狀態(tài)空間法28中南大學智能系統(tǒng)與智能軟件研究所求解過程令初始狀態(tài)為(a,0,b,0)。這時，goto(U)是唯一適用的操作，并導致下一狀態(tài)(U，0，b,0)?，F(xiàn)在有3個適用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有適用的操作繼續(xù)應(yīng)用于每個狀態(tài)，我們就能夠得到狀態(tài)空間圖，如圖所示。從圖不難看出，把該初始狀態(tài)變換為目標狀態(tài)的操作序列為：

{goto(b),pushbox(c),climbbox,grasp}29中南大學智能系統(tǒng)與智能軟件研究所猴子和香蕉問題的狀態(tài)空間圖30中南大學智能系統(tǒng)與智能軟件研究所猴子和香蕉問題自動演示：

Ha!Ha!31中南大學智能系統(tǒng)與智能軟件研究所九宮排序（寬度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

8321476528143765283145761237846512384765125673123847658432中南大學智能系統(tǒng)與智能軟件研究所九宮排序（深度優(yōu)先搜索）23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761238476523456789abcd133中南大學智能系統(tǒng)與智能軟件研究所2.2問題歸約法

（ProblemReductionRepresentation）子問題1子問題n原始問題子問題集本原問題34中南大學智能系統(tǒng)與智能軟件研究所問題歸約表示的組成部分：一個初始問題描述；一套把問題變換為子問題的操作符；一套本原問題描述。問題歸約的實質(zhì)：從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。2.2問題規(guī)約法35中南大學智能系統(tǒng)與智能軟件研究所2.2.1問題歸約描述

（ProblemReductionDescription）梵塔難題123CBA2.2問題規(guī)約法36中南大學智能系統(tǒng)與智能軟件研究所解題過程（3個圓盤問題）1231231231231231231231232.2問題規(guī)約法37中南大學智能系統(tǒng)與智能軟件研究所多圓盤梵塔難題演示2.2問題規(guī)約法38中南大學智能系統(tǒng)與智能軟件研究所2.2.2與或圖表示1.與圖、或圖、與或圖2.2問題規(guī)約法ABCD與圖ABC或圖39中南大學智能系統(tǒng)與智能軟件研究所2.2問題規(guī)約法BCDEFGAHMBCDEFGAN40中南大學智能系統(tǒng)與智能軟件研究所2.一些關(guān)于與或圖的術(shù)語2.2問題規(guī)約法HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點終葉節(jié)點41中南大學智能系統(tǒng)與智能軟件研究所3.定義2.2問題規(guī)約法與或圖例子ttttttttt（a）（b）有解節(jié)點無解節(jié)點終葉節(jié)點42中南大學智能系統(tǒng)與智能軟件研究所不可解節(jié)點的一般定義(1)沒有后裔的非終葉節(jié)點為不可解節(jié)點。(2)全部后裔為不可解的非終葉節(jié)點且含有或后繼節(jié)點，此非終葉節(jié)點才是不可解的。(3)后裔至少有一個為不可解的非終葉節(jié)點且含有與后繼節(jié)點，此非終葉節(jié)點才是不可解的。與或圖構(gòu)成規(guī)則(1)與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。圖中所含起始節(jié)點對應(yīng)于原始問題。2.2問題規(guī)約法43中南大學智能系統(tǒng)與智能軟件研究所(2)對應(yīng)于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔.(3)對于把算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個子問題集合；有向弧線自A指向后繼節(jié)點表示所求得的子問題集合。(4)一般對于代表兩個或兩個以上子問題集合的每個節(jié)點，有向弧線從此節(jié)點指向此子問題集合中的各個節(jié)點。由于只有當集合中所有的項都有解時，這個子問題的集合才能獲得解答，所以這些子問題節(jié)點叫做與節(jié)點。(5)在特殊情況下，當只有一個算符可應(yīng)用于問題A，而且這個算符產(chǎn)生具有一個以上子問題的某個集合時，由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡化。44中南大學智能系統(tǒng)與智能軟件研究所梵塔問題歸約圖（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

2.2問題規(guī)約法45中南大學智能系統(tǒng)與智能軟件研究所2.3命題邏輯法歸結(jié)推理命題邏輯謂詞邏輯Skolem標準形、子句集基本概念謂詞邏輯歸結(jié)原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結(jié)Herbrand定理46中南大學智能系統(tǒng)與智能軟件研究所命題邏輯的歸結(jié)法命題邏輯基礎(chǔ)：定義：合取式：p與q，記做pΛq析取式：

p或q，記做p∨q蘊含式：如果p則q，記做p→q等價式：p當且僅當q，記做p<=>q47中南大學智能系統(tǒng)與智能軟件研究所命題邏輯基礎(chǔ)定義：若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。48中南大學智能系統(tǒng)與智能軟件研究所命題邏輯基礎(chǔ)基本等值式24個(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)49中南大學智能系統(tǒng)與智能軟件研究所命題邏輯基礎(chǔ)基本等值式（1）摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq

)<=>p

；

pΛ(p∨q

)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

50中南大學智能系統(tǒng)與智能軟件研究所命題邏輯基礎(chǔ)命題：能判斷真假（不是既真又假）的陳述句。 簡單陳述句描述事實、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1．

1+1=22．

雪是黑色的。

3．

北京是中國的首都。判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現(xiàn)在是假，隨著人類科學的發(fā)展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。而例如：1.快點走吧！2.到那去？3.x+y>10等.

都不是命題。51中南大學智能系統(tǒng)與智能軟件研究所命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”?！玴

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

是q的必要條件， 因而，可得命題公式：q→～p52中南大學智能系統(tǒng)與智能軟件研究所命題表示公式（2）例如：1．

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

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

∧(r∨t)→

q。53中南大學智能系統(tǒng)與智能軟件研究所命題邏輯的歸結(jié)法基本單元：簡單命題（陳述句）例：命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B反證法：證明A1ΛA2ΛA3Λ～B

是矛盾式（永假式）54中南大學智能系統(tǒng)與智能軟件研究所命題邏輯的歸結(jié)法建立子句集合取范式：命題、命題和的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}55中南大學智能系統(tǒng)與智能軟件研究所命題邏輯的歸結(jié)法歸結(jié)式消除互補文字對P和～P∨Q，求新子句→得到歸結(jié)式。如子句：C1,C2，歸結(jié)式：R(C1,C2)=C1ΛC2

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

，反之不一定成立。56中南大學智能系統(tǒng)與智能軟件研究所命題邏輯的歸結(jié)法歸結(jié)過程將命題寫成合取范式求出子句集對子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句□

，S是不可滿足的（矛盾），原命題成立。?（證明完畢）。謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。57中南大學智能系統(tǒng)與智能軟件研究所命題邏輯的歸結(jié)法歸結(jié)式的定義及性質(zhì)對子句C1和C2，若C1中有一個文字L1，而C2中有一個與L1成互補的文字L2，則分別從C1,C2中刪去L1和L2，并將其剩余部分組成新的析取式，則稱該子句為歸結(jié)式。例1:設(shè)兩個子句C1=L∨C1'，C2=(～

L)∨C2'，則歸結(jié)式C=Cl’∨C2’。當C1'=C2’=□時，C=□。例2:PΛ（～P∨Q）＝Q定理:二個子句C1和C2的歸結(jié)式C是C1和C2的邏輯推論。

58中南大學智能系統(tǒng)與智能軟件研究所命題邏輯歸結(jié)例題（1）例題，證明公式：(P→Q)→(～Q→～P)證明：（1）根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：(P→Q)∧～(～Q→～P)（2）分別將公式前項化為合取范式：

P→Q＝～P∨Q

結(jié)論求～后的后項化為合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

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

（3）則子句集為：{～P∨Q，～Q，P}59中南大學智能系統(tǒng)與智能軟件研究所命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

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

， （2，4歸結(jié)） 由上可得原公式成立。60中南大學智能系統(tǒng)與智能軟件研究所證明：化成子句集

S={P,～

P∨┐Q∨R，

～

S∨Q，～

T∨Q，

T，～

R}

歸結(jié)可用圖的演繹樹表示，由于根部出現(xiàn)空子句，因此命題R得證。

例：設(shè)已知前提集為

P……(1)(P∧Q)→R………(2)(S∨T)→Q………(3)T………(4)

求證R。61中南大學智能系統(tǒng)與智能軟件研究所2.4一階謂詞邏輯法個體詞：表示主語的詞謂詞：刻畫個體性質(zhì)或個體之間關(guān)系的詞量詞：表示數(shù)量的詞2.4.1謂詞演算

語法和語義基本符號：謂詞符號、變量符號、函數(shù)符號、常量符號、括號和逗號原子公式(atomicformulas)：由若干謂詞符號和項組成的謂詞演算。原子公式是謂詞演算基本積木塊。62中南大學智能系統(tǒng)與智能軟件研究所2.4一階謂詞邏輯法小王是個工程師。8是個自然數(shù)。我去買花。小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質(zhì)，第三個謂詞“去買”表示的一個動作也表示了主、賓兩個個體詞的關(guān)系，最后一個謂詞“是朋友”表示兩個個體詞之間的關(guān)系。63中南大學智能系統(tǒng)與智能軟件研究所2.4一階謂詞邏輯法一階邏輯公式及其解釋個體常量：a,b,c個體變量：x,y,z謂詞符號：P,Q,R量詞符號：

,

64中南大學智能系統(tǒng)與智能軟件研究所例如，要表示“機器人(ROBOT)在１號房間(r1)內(nèi)”，如圖所示，可以應(yīng)用原子公式:當機器人ROBOT移到房間r2時，原子公式可以表示為:INROOM(ROBOT,r2)這兩個原子公式的通用形式就是

65中南大學智能系統(tǒng)與智能軟件研究所又如,“李的母親和他的父親結(jié)婚”這句話的原子公式表示如下：連詞和量詞(Connective&Quantifiers)連詞與及合取（conjunction):合取就是用連詞∧把幾個公式連接起來而構(gòu)成的公式。合取項是合取式的每個組成部分。一些合適公式所構(gòu)成的任一合取也是一個合適公式。例：LIKE(I，MUSIC)∧LIKE(I，PAINTING)(我喜愛音樂和繪畫。)66中南大學智能系統(tǒng)與智能軟件研究所或及析?。╠isjunction）:析取就是用連詞∨把幾個公式連接起來而構(gòu)成的公式。析取項是析取式的每個組成部分。由一些合適公式所構(gòu)成的任一析取也是一個合適公式。例：PLAYS(LILI，BASKETBALL)∨PLAYS(LILI，F(xiàn)OOTBALL)(李力打籃球或踢足球。)蘊涵（Implication）：“=>”表示“如果-那么”的語句。用連詞=>連接兩個公式所構(gòu)成的公式叫做蘊涵。如果前項和后項都是合適公式，那么蘊涵也是合適公式。

IF=>THEN前項(左式)=>后項(右式)例：RUNS(LIUHUA，F(xiàn)ASTEST)=>WINS(LIUHUA，CHAMPION)(如果劉華跑得最快，那么他取得冠軍)2.3謂詞邏輯法67中南大學智能系統(tǒng)與智能軟件研究所非（Not）：表示否定，～、┑均可表示。一個合適公式的否定也是合適公式。例：～INROOM(ROBOT，r2)(機器人不在2號房間內(nèi))量詞全稱量詞（UniversalQuantifiers)：若一個原子公式P(x)，對于所有可能變量x都具有T值，則用

(

x)P(x)表示。例：(

x)[ROBOT(x)=>COLOR(x,GRAY)](

x)[Student(x)=>Uniform(x,Color)]存在量詞(ExistentialQuantifiers)：若一個原子公式P(x)，至少有一個變元X，可使P(X)為T值，則用(

x)P(x)表示。例(

x)INROOM(x,r1)68中南大學智能系統(tǒng)與智能軟件研究所例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個體域D為人類集合時，可符號化為：（1）

xP(x)，其中P(x)表示x是要死的。（2）

xQ(x),其中Q(x)表示x活到一百歲以上。在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為：（1）

x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）

x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。69中南大學智能系統(tǒng)與智能軟件研究所量詞否定等值式：～(

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è)個體域為有窮集合(a1,a2,…an)(

x

）

P（x）<=>P（a1

）ΛP（a2

）Λ…ΛP（an

）(

x

）P（x）<=>P（a1

）∨P（a2

）∨…∨P（an

）70中南大學智能系統(tǒng)與智能軟件研究所量詞轄域收縮與擴張等值式：(

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）71中南大學智能系統(tǒng)與智能軟件研究所2.4.2謂詞公式原子公式的的定義：用P(x1，x2，…，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,…，xn為客體變量或變元。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。2.3謂詞邏輯法72中南大學智能系統(tǒng)與智能軟件研究所項可遞歸定義如下：(1)單獨一個個體是項(包括常量和變量)。(2)若f是n元函數(shù)符號，而是項，則f()是項。(3)任何項僅由規(guī)則(1)(2)所生成。定義若P為n元謂詞符號,t1,…,tn都是項，則稱P(t1,…,tn)為原子公式。73中南大學智能系統(tǒng)與智能軟件研究所定義一階謂詞邏輯的合式公式：(1)原子謂詞公式是合式公式(也稱為原子公式)。(2)若P、Q是合式公式，則

(～

P)、(P∧Q)、(P∨Q)、(P→Q)、(P←→Q)

也是合式公式。(3)若P是合式公式，x是任一個體變元，則

(

x)P、（

x)P也是合式公式。(4)有限次重復（1）和（3）構(gòu)成的公式也是合式公司。2.3謂詞邏輯法74中南大學智能系統(tǒng)與智能軟件研究所2.3.3置換與合一置換：在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定的合適公式和合適公式集，以產(chǎn)生新的合適公式。一個重要的推理規(guī)則是假元推理，這就是由合適公式W1和W1=>W2產(chǎn)生合適公式W2的運算。另一個推理規(guī)則叫做全稱化推理，它是由合適公式(

x)W(x)產(chǎn)生合適公式W(A)，其中A為任意常量符號。概念假元推理：全稱化推理綜合推理75中南大學智能系統(tǒng)與智能軟件研究所2.3.3置換與合一置換：就是在該表達式中用置換項置換變量用項(A)替換函數(shù)表達式中的變量(x)，記為Es，即表示一個表達式E(Expression)用一個置換s(Substitution)而得到的表達式的置換。

例1:表達式P[x,f(y),B]的4個置換為:

s1={z/x,w/y}

s2={A/y}

s3={q(z)/x,A/y}

s4={c/x,A/y}76中南大學智能系統(tǒng)與智能軟件研究所2.3.3置換與合一我們用Es來表示一個表達式E用置換s所得到的表達式的置換。于是，可得到P[x,f(y),B]的4個置換的例，如下：

置換置換的例sl={z/x,w/y}，P[x,f(y)，B]s1=P[z,f(w),B]s2={A/y}，P[x,f(y)，B]s2=P[x,f(A),B]s3={g(z)/x,A/y}，P[x,f(y)，B]s3=P[g(z),f(A),B]s4={C/x,A/y}，P[x,f(y)，B]s4=P[C,f(A),B]77中南大學智能系統(tǒng)與智能軟件研究所置換置換的例

sl={z/x,w/y}，P[x,f(y)，B]s1=P[z,f(w),B]

s2={A/y}，P[x,f(y)，B]s2=P[x,f(A),B]

s3={g(z)/x,A/y}，P[x,f(y)，B]s3=P[g(z),f(A),B]

s4={C/x,A/y}，P[x,f(y)，B]s4=P[C,f(A),B]第一個例叫做原始文字的初等變式，實際上置換后只是對變量作了換名。第四個例稱作基例，即置換后項中不再含有變量。用s={t1/v1,t2/v2,….,tn/vn}來表示任一置換，用s對表達式E作置換后的例簡記為Es。78中南大學智能系統(tǒng)與智能軟件研究所2.3.3置換與合一性質(zhì).可結(jié)合的:(Ls1)s2=L(s1s2)(s1s2)s3=s1(s2s3)

置換是可結(jié)合的。用s1s2表示兩個置換s1和s2的合成。L表示一表達式，則有

(Ls1)s2=L(s1s2)以及(s1s2)s3=s1(s2s3)即用s1和s2相繼作用于表達式L是同用s1s2作用于L一樣的。.不可交換的一般說來，置換是不可交換的，即s1s2≠s2s12.3謂詞邏輯法79中南大學智能系統(tǒng)與智能軟件研究所合一（Unification)合一：尋找項對變量的置換，以使兩表達式一致。可合一：如果一個置換s作用于表達式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達式集{Ei}是可合一的。例:表達式集P[x,f(y),B]，P[x,f(B),B]的合一者設(shè)為:

s={A/x,B/y}因為：P[x,f(y),B]s＝P[A,f(y),B]＝P[A,f(B),B]若s為{Ei}的任一合一者，又存在某個s’,使得

{Ei}s={Ei}gs’成立，則稱g為{Ei}的最通用（最一般）的合一者，記為mgu。上例最簡單的合一者為：mgu

g＝｛B/y}.

2.3謂詞邏輯法80中南大學智能系統(tǒng)與智能軟件研究所UNIFY算法

mgug的置換限制最少，所產(chǎn)生的例更一般化，有利于歸結(jié)過程的靈活使用。UNIFY算法(算法中可合一的表達式要用表結(jié)構(gòu)來表示)如把P(x，f(A,y))表示成(Px(fAy))找到的合一者是可合一表達式的mgu，若表達式不可合一時，則算法失敗退出。

81中南大學智能系統(tǒng)與智能軟件研究所遞歸過程UNIFY(E1，E2)(1)IFATOM(E1)ORATOM(E2)THEN交換E1和E2的位置使E1是一個原子(有必要時)，do:;

原子包括謂詞符號、函數(shù)符號、常數(shù)符號、變量符號和否定符號。E1不是原子，而E2是原子時，則交換位置，使E1是一個原子。(2)Begin(3)IFE1=E2THENRETURNNIL;82中南大學智能系統(tǒng)與智能軟件研究所(4)IFVAR(E1)IFCONTAIN(E2，E1)THENRETURN(FAIL)ELSERETURN({E2/E1});E1是變量且E2中不含有E1,返回置換{E2/E1}。(5)IFVAR(E2)THENRETURN({E1/E2})ELSERETURN(FAIL);

E2是變量返回置換{E1/E2}。(6)End(7)F1:=FIRST(E1)，T1:=TAIL(E1);Fl放E1第一個元素，其余元素放在T1中。

83中南大學智能系統(tǒng)與智能軟件研究所(8)F2:=FIRST(E2)，T2:=TAIL(E2);(9)s1:=UNIFY(F1，F(xiàn)2);遞歸調(diào)用。(10)IFs1=FAILTHENRETURN(FAIL);(11)G1:=T1s1，G2:=T2s1;對未匹配部分作置換。(12)s2:=UNIFY(G1，G2);(13)IFs2:=FAILTHENRETURN(FAIL);(14)

RETURN(s=s1s2);返回s1和s2的合成。UNIFY(E1，E2)算法84中南大學智能系統(tǒng)與智能軟件研究所利用該算法可找到可合一表達式集的最一般的合一者，例{Ei}mgug{Ei}g{P(x)，P(A)},{A/x}P(A){P(f(x),y,g(y))，P(f(x),z,g(x))}{x/y，x/z}P(f(x),x,g(x))85中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標準形)SKOLEM標準形前束范式

定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。86中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標準形)即：把所有的量詞都提到前面去，然后消掉所有量詞

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

）

M（x）<=>（Qy

）

M（y）(Qx

）

M（x,z）<=>（Qy

）

M（y,z）87中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標準形)量詞消去原則： 消去存在量詞“

”，略去全程量詞“

”。

注意：左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。88中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標準形)Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。SKOLEM標準形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標準形同G并不等值。89中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標準形)例:將下式化為Skolem標準形： ～(

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)∨(u)(

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

(

x)(

y)(u)(

v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式90中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標準形)第五步，消去“

”（存在量詞），略去“

”全稱量詞消去(

y)，因為它左邊只有(

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標準形為：

P(a,x,f(x))∧～Q(g(x),b)∧～R(x)

91中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求取：

G→SKOLEM標準形

→消去存在變量

→以“，”取代“Λ”，并表示為集合形式。92中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形G是不可滿足的<=>S是不可滿足的G與S不等價，但在不可滿足得意義下是一致的。定理： 若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的<=>S是不可滿足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G93中南大學智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成幾個單獨處理。有SG=S1US2US3U…USn

則SG

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

不可滿足<=>S1US2US3U…USn不可滿足94中南大學智能系統(tǒng)與智能軟件研究所求取子句集例(1)例：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞：

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

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

ANS(x)表示問題的解答95中南大學智能系統(tǒng)與智能軟件研究所求取子句集例(2)對于第一個條件，“如果x是y的父親，y又是z的父親，則x是z的祖父”，一階邏輯表達式如下：

A1：(

x)(

y)(

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

A2：(

y)(

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

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}96中南大學智能系統(tǒng)與智能軟件研究所2.3.4歸結(jié)推理

歸結(jié)方法，1965年Robinson提出歸結(jié)方法的基本思想命題邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理97中南大學智能系統(tǒng)與智能軟件研究所2.3.4什么是歸結(jié)原理在定理證明系統(tǒng)中，已知一公式集F1，F(xiàn)2，…，F(xiàn)n，要證明一個公式W(定理)是否成立，即要證明W是公式集的邏輯推論時，一種證明法就是要證明F1∧F2∧…∧Fn→W為永真式。反證法：證明F=F1∧F2∧…∧Fn∧┐W為永假，這等價于證明F對應(yīng)的子句集S=S0∪{┐W}為不可滿足的。98中南大學智能系統(tǒng)與智能軟件研究所思路：設(shè)法檢驗擴充的子句集Si是否含有空子句，若S集中存在空子句，則S不可滿足。若沒有空子句，則就進一步用歸結(jié)法從S導出S1。然后再檢驗S1是否有空子句。用歸結(jié)法導出的擴大子句集S1，其不可滿足性是不變的，所以若S1中有空子句，也就證得了S的不可滿足性。通過歸結(jié)過程演繹出S的不可滿足性來，從而使定理得到證明。99中南大學智能系統(tǒng)與智能軟件研究所2.3.4謂詞邏輯的歸結(jié)原理在謂詞邏輯中，要考慮變量的約束問題，在應(yīng)用歸結(jié)法時，要對公式作變量置換和合一等處理，才能得到互補的基本式，以使進行歸結(jié)。歸結(jié)過程：·若S中兩子句間有相同互補文字的謂詞，但它們的項不同，則必須找出對應(yīng)的不一致項；

·進行變量置換，使它們的對應(yīng)項一致;

·求歸結(jié)式看能否導出空子句。100中南大學智能系統(tǒng)與智能軟件研究所2.3.4謂詞邏輯的歸結(jié)原理歸結(jié)原理就是從子句集S出發(fā)，應(yīng)用歸結(jié)推理規(guī)則導出子句集S1。再從S1出發(fā)導出S2，依此類推，直到某一個子句集Sn出現(xiàn)空子句為止。根據(jù)不可滿足性等價原理，已知若Sn為不可滿足的，則可逆向依次推得S必為不可滿足的。用歸結(jié)法，過程比較單鈍，只涉及歸結(jié)推理規(guī)則的應(yīng)用問題，因而便于實現(xiàn)機器證明。101中南大學智能系統(tǒng)與智能軟件研究所歸結(jié)原理的歸結(jié)過程歸結(jié)的過程寫出謂詞關(guān)系公式→用反演法寫出謂詞表達式→SKOLEM標準形→子句集S→對S中可歸結(jié)的子句做歸結(jié)→歸結(jié)式仍放入S中，反復歸結(jié)過程→得到空子句

?得證102中南大學智能系統(tǒng)與智能軟件研究所謂詞邏輯的歸結(jié)過程設(shè)C1和C2為不具有完全相同變元的兩個子句，子句中的變量已標準化。采用文字集的形式來表示子句(即文字之間理解為析取關(guān)系)，則有

C1={C1i},(i=1，2，…，n)，

C2={C2j},(j=l，2，…，m)103中南大學智能系統(tǒng)與智能軟件研究所設(shè){L1k}和{L2k}分別為C1和C2的兩個子集。若{L1k}和{┐L2k}的并集存在一個mgus，則兩個子句的歸結(jié)式為

C={{C1i}-{L1k}}s∪{{C2j}-{L2k}}s由于有多種方式選取{L1k}和{L2k}，因此歸結(jié)式不是唯一的。104中南大學智能系統(tǒng)與智能軟件研究所例:Cl=P(x,f(A))∨P(x,f(y))∨Q(y)C2=┐P(z,f(A))∨┐Q(z)(1)取L11=P(x,f(A))，L21=┐P(z，f(A))

則s={z/x}使L11和┐L21合一，歸結(jié)式為

P(z，f(y))∨Q(y)∨┐Q(z)(2)取L11=P(x,f(y))，L21=┐P(z，f(A))

則s={z/x，A/y}，歸結(jié)式為Q(A)∨┐Q(z)(3)取L11=Q(y)，L21=┐Q(z),則s={y/z}，歸結(jié)式為P(x，f(A))∨P(x，f(y))∨P(y,f(A))105中南大學智能系統(tǒng)與智能軟件研究所選擇不同文字對做歸結(jié)時可得到不同的歸結(jié)式，但由于都是用最一般的合一者作置換，因此這些歸結(jié)式仍是最一般的歸結(jié)式。如果對某個文字不是用mgu來合一，那么得到的歸結(jié)式比最一般的歸結(jié)式則有較多的限制?？偸窍Ｍ米钜话愕臍w結(jié)式，以增加歸結(jié)過程的靈活性。106中南大學智能系統(tǒng)與智能軟件研究所例：已知：（1）會朗讀的人是識字的，（2）海豚都不識字，（3）有些海豚是很機靈的。證明：有些很機靈的東西不會朗讀。解：把問題用謂詞邏輯描述如下，已知：（1）(

x)(R(x)→L(x))(2)(

x)(D(x)→┐L(x))(3)(

x)(D(x)∧I(x))

求證:(

x(I(x)∧┐R(x))

107中南大學智能系統(tǒng)與智能軟件研究所前提化簡，待證結(jié)論取反并化成子句形，求得子句集:(1)┐R(x)∨L(x)(2)┐D(y)∨┐L(y)(3a)D(A)(3b)I(A)(4)┐I(z)∨R(z)一個可行的證明過程:(5)R(A)(3b)和(4)的歸結(jié)式

(6)L(A)(5)和(1)的歸結(jié)式

(7)┐D(A)(6)和(2)的歸結(jié)式

(8)NIL(7)和(3a)的歸結(jié)式108中南大學智能系統(tǒng)與智能軟件研究所例題“快樂學生”問題假設(shè)任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。解：先將問題用謂詞表示如下：R1:“任何通過計算機考試并獲獎的人都是快樂的”

(

x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯學習或幸運的人都可以通過所有考試”

(

x)(

y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“張不肯學習但他是幸運的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸運的人都能獲獎”

(

x)(Luck(x)→Win(x,prize))結(jié)論：“張是快樂的”的否定～Happy(zhang)109中南大學智能系統(tǒng)與智能軟件研究所例題“快樂學生”問題由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)

110中南大學智能系統(tǒng)與智能軟件研究所2.3.5歸結(jié)反演(Refutation)歸結(jié)反演系統(tǒng)是用反演(反駁)或矛盾的證明法，使用歸結(jié)推理規(guī)則建立的定理證明系統(tǒng)。這種證明系統(tǒng)是基于歸結(jié)的反證法，故稱歸結(jié)反演系統(tǒng)?？捎迷谛畔z索、常識性推理和自動程序設(shè)計等。111中南大學智能系統(tǒng)與智能軟件研究所l·歸結(jié)反演的基本算法

綜合數(shù)據(jù)庫:子句集規(guī)則集合:IFcx(∈Si)和cy(∈Si)有歸結(jié)式rxyTHENSi+1=Si∪{rxy}

目標條件:Sn中出現(xiàn)空子句112中南大學智能系統(tǒng)與智能軟件研究所過程RESOLUTION(1)CLAUSES:=S;S為初始的基本子句集。(2)untilNIL是CLAUSES的元素，do:(3)begin(4)在CLAUSES中選兩個不同的可歸結(jié)的子句ci、cj;ci、cj稱母子句。(5)求ci、cj的歸結(jié)式rxy;(6)CLAUSES:={rxy}∪CLAUSES;(7)end;？？113中南大學智能系統(tǒng)與智能軟件研究所2·搜索策略選哪兩個子句做歸結(jié)？對哪一個文字做歸結(jié)？114中南大學智能系統(tǒng)與智能軟件研究所S={┐I(z)∨R(z)，I(A)，┐R(x)∨L(x)，┐D(y)∨┐L(y)，D(A)}歸結(jié)過程用歸結(jié)反演樹表示比較簡單。搜索策略的目標就是要找到一棵歸結(jié)反演樹。一個反演系統(tǒng)當存在一個矛盾時，如果使用的一種策略，最終都將找到一棵反演樹，則這種策略是完備的。

歸結(jié)反演樹115中南大學智能系統(tǒng)與智能軟件研究所提高策略效率——只歸結(jié)含有互補對的文字；及時刪去出現(xiàn)的重言式和被其他子句所包含的子句;每次歸結(jié)都取與目標公式否定式有關(guān)的子句作為母子句之一進行歸結(jié)等等。

(1)寬度優(yōu)先策略（完備，效率低）寬度優(yōu)先策略首先歸結(jié)出基本集S中可能生成的所有歸結(jié)式，稱第一級歸結(jié)式，然后生成第二級歸結(jié)式等等，直到出現(xiàn)空子句。116中南大學智能系統(tǒng)與智能軟件研究所(2)支持集策略（完備）歸結(jié)時，其母子句中至少有一個是與目標公式否定式有關(guān)的子句。117中南大學智能系統(tǒng)與智能軟件研究所(3)單元子句優(yōu)先策略每次歸結(jié)時優(yōu)先選取單文字的子句(稱單元子句)為母子句進行歸結(jié)，顯然歸結(jié)式的文字數(shù)會比其他情況歸結(jié)的結(jié)果要少，這有利于向空子句的方向搜索，實際上會提高效率。118中南大學智能系統(tǒng)與智能軟件研究所(4)線性輸入形策略每次歸結(jié)時，至少有一個母子句是從基本集中挑選。該策略可限制生成歸結(jié)式的數(shù)目，具有簡單和效率高的優(yōu)點。119中南大學智能系統(tǒng)與智能軟件研究所它不是一個完備的策略，反例：S={Q(u)∨P(A)，┑Q(w)∨P(w)，

┑Q(x)∨┑P(x)，Q(y)∨┑P(y)}，從S出發(fā)很容易找到一棵反演樹，但不存在一個線性輸入形策略的反演樹。120中南大學智能系統(tǒng)與智能軟件研究所（5）祖先過濾策略

（完備）

祖先過濾策略的搜索過程121中南大學智能系統(tǒng)與智能軟件研究所2.3.6謂詞演算歸結(jié)反演的合理性和完備性歸結(jié)原理是反演完備的，即如果一個子句集合是不可滿足的，則歸結(jié)將會推導出矛盾。歸結(jié)不能用于產(chǎn)生某子句集合的所有結(jié)論，但是它可以用于說明某個給定的句子是該子句集合所蘊涵的。因此，使用前面介紹的否定目標的方法，它可以發(fā)現(xiàn)所有的答案。122中南大學智能系統(tǒng)與智能軟件研