人工智能主講:吳順祥

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

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

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

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

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

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

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

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

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

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

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

·

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

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

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

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

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

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

goto（U）（U，0，Y，z）2.1狀態(tài)空間法27中南大學(xué)智能系統(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中南大學(xué)智能系統(tǒng)與智能軟件研究所求解過(guò)程令初始狀態(tài)為(a,0,b,0)。這時(shí)，goto(U)是唯一適用的操作，并導(dǎo)致下一狀態(tài)(U，0，b,0)。現(xiàn)在有3個(gè)適用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。把所有適用的操作繼續(xù)應(yīng)用于每個(gè)狀態(tài)，我們就能夠得到狀態(tài)空間圖，如圖所示。從圖不難看出，把該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為：

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

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

231847652831476523184765283147652831647528314765283164752831647528371465

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

231847652831476523184765283147652831647528314765283164752831647528371465

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

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

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

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

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

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

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

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

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

1+1=22．

雪是黑色的。

3．

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

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

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

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

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

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

∧(r∨t)→

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

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

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

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

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

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

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

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

58中南大學(xué)智能系統(tǒng)與智能軟件研究所命題邏輯歸結(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}59中南大學(xué)智能系統(tǒng)與智能軟件研究所命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對(duì)子句集中的子句進(jìn)行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

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

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

S={P,～

P∨┐Q∨R，

～

S∨Q，～

T∨Q，

T，～

R}

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

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

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

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

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

,

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

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

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

(

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

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

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

x)P(x)表示。例(

x)INROOM(x,r1)68中南大學(xué)智能系統(tǒng)與智能軟件研究所例如：（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活到一百歲以上。69中南大學(xué)智能系統(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è)個(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

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

(～

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

也是合式公式。(3)若P是合式公式，x是任一個(gè)體變?cè)瑒t

(

x)P、（

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

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

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

s1={z/x,w/y}

s2={A/y}

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

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

置換置換的例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中南大學(xué)智能系統(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]第一個(gè)例叫做原始文字的初等變式，實(shí)際上置換后只是對(duì)變量作了換名。第四個(gè)例稱作基例，即置換后項(xiàng)中不再含有變量。用s={t1/v1,t2/v2,….,tn/vn}來(lái)表示任一置換，用s對(duì)表達(dá)式E作置換后的例簡(jiǎn)記為Es。78中南大學(xué)智能系統(tǒng)與智能軟件研究所2.3.3置換與合一性質(zhì).可結(jié)合的:(Ls1)s2=L(s1s2)(s1s2)s3=s1(s2s3)

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

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

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

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

g＝｛B/y}.

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

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

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

原子包括謂詞符號(hào)、函數(shù)符號(hào)、常數(shù)符號(hào)、變量符號(hào)和否定符號(hào)。E1不是原子，而E2是原子時(shí)，則交換位置，使E1是一個(gè)原子。(2)Begin(3)IFE1=E2THENRETURNNIL;82中南大學(xué)智能系統(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第一個(gè)元素，其余元素放在T1中。

83中南大學(xué)智能系統(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;對(duì)未匹配部分作置換。(12)s2:=UNIFY(G1，G2);(13)IFs2:=FAILTHENRETURN(FAIL);(14)

RETURN(s=s1s2);返回s1和s2的合成。UNIFY(E1，E2)算法84中南大學(xué)智能系統(tǒng)與智能軟件研究所利用該算法可找到可合一表達(dá)式集的最一般的合一者，例{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中南大學(xué)智能系統(tǒng)與智能軟件研究所謂詞歸結(jié)子句形(Skolem

標(biāo)準(zhǔn)形)SKOLEM標(biāo)準(zhǔn)形前束范式

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

標(biāo)準(zhǔn)形)量詞消去原則： 消去存在量詞“

”，略去全程量詞“

”。

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

標(biāo)準(zhǔn)形)Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價(jià)的前束范式，但其前束范式不唯一。SKOLEM標(biāo)準(zhǔn)形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標(biāo)準(zhǔn)形同G并不等值。89中南大學(xué)智能系統(tǒng)與智能軟件研究所謂詞歸結(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))由此得到前述范式90中南大學(xué)智能系統(tǒng)與智能軟件研究所謂詞歸結(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)

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

G→SKOLEM標(biāo)準(zhǔn)形

→消去存在變量

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

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

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

則SG

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

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

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

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

ANS(x)表示問(wèn)題的解答95中南大學(xué)智能系統(tǒng)與智能軟件研究所求取子句集例(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}96中南大學(xué)智能系統(tǒng)與智能軟件研究所2.3.4歸結(jié)推理

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

·進(jìn)行變量置換，使它們的對(duì)應(yīng)項(xiàng)一致;

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

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

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

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

C={{C1i}-{L1k}}s∪{{C2j}-{L2k}}s由于有多種方式選取{L1k}和{L2k}，因此歸結(jié)式不是唯一的。104中南大學(xué)智能系統(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中南大學(xué)智能系統(tǒng)與智能軟件研究所選擇不同文字對(duì)做歸結(jié)時(shí)可得到不同的歸結(jié)式，但由于都是用最一般的合一者作置換，因此這些歸結(jié)式仍是最一般的歸結(jié)式。如果對(duì)某個(gè)文字不是用mgu來(lái)合一，那么得到的歸結(jié)式比最一般的歸結(jié)式則有較多的限制。總是希望用最一般的歸結(jié)式，以增加歸結(jié)過(guò)程的靈活性。106中南大學(xué)智能系統(tǒng)與智能軟件研究所例：已知：（1）會(huì)朗讀的人是識(shí)字的，（2）海豚都不識(shí)字，（3）有些海豚是很機(jī)靈的。證明：有些很機(jī)靈的東西不會(huì)朗讀。解：把問(wèn)題用謂詞邏輯描述如下，已知：（1）(

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

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

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

求證:(

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

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

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

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

(8)NIL(7)和(3a)的歸結(jié)式108中南大學(xué)智能系統(tǒng)與智能軟件研究所例題“快樂(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)109中南大學(xué)智能系統(tǒng)與智能軟件研究所例題“快樂(lè)學(xué)生”問(wè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é)論的否定）(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中南大學(xué)智能系統(tǒng)與智能軟件研究所2.3.5歸結(jié)反演(Refutation)歸結(jié)反演系統(tǒng)是用反演(反駁)或矛盾的證明法，使用歸結(jié)推理規(guī)則建立的定理證明系統(tǒng)。這種證明系統(tǒng)是基于歸結(jié)的反證法，故稱歸結(jié)反演系統(tǒng)。可用在信息檢索、常識(shí)性推理和自動(dòng)程序設(shè)計(jì)等。111中南大學(xué)智能系統(tǒng)與智能軟件研究所l·歸結(jié)反演的基本算法

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

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

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

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

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

（完備）

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