人工智能 課件 第二章 知識表示和邏輯推理

人工智能第2章知識表示和邏輯推理本章簡介智能行為的基礎(chǔ)是知識，尤其是所謂的常識性知識。人類的智能行為對于知識的依賴主要表現(xiàn)在對于知識的利用，即利用已經(jīng)具有的知識進(jìn)行分析、猜測、判斷、預(yù)測等等。知識表示和邏輯推理是人工智能的基礎(chǔ)。為使計(jì)算機(jī)具有智能行為,需要解決如何在計(jì)算機(jī)上表達(dá)人類的知識以及如何像人一樣利用知識（進(jìn)行邏輯推理）的問題。本章將討論知識表示和邏輯推理的基本概念、方法和技術(shù)。本章提綱2.1知識和推理的關(guān)系2.2一階謂詞邏輯表示法2.3產(chǎn)生式表示法2.5語義網(wǎng)絡(luò)表示法2.4框架表示法本章提綱2.6自然演繹推理2.7歸結(jié)演繹推理2.8與/或形演繹推理2.10證據(jù)理論2.9主觀貝葉斯推理2.11語義網(wǎng)絡(luò)表示法本章提綱2.1知識和推理的關(guān)系2.2一階謂詞邏輯表示法2.3產(chǎn)生式表示法2.5語義網(wǎng)絡(luò)表示法2.4框架表示法2.1.1知識的定義數(shù)據(jù)與信息數(shù)據(jù)：用一定的形式（如符號及其組合）表示出來的信息數(shù)據(jù)泛指對客觀事物的數(shù)量、屬性、位置及其相互關(guān)系的抽象表示。它既可以是一個(gè)數(shù)，例如整數(shù)、小數(shù)、正數(shù)、負(fù)數(shù)，也可以是由一組符號組合而成的字符串，例如一個(gè)人的姓名、性別、地址或者一條消息等等。數(shù)據(jù)與信息是兩個(gè)密切相關(guān)的概念。數(shù)據(jù)是信息的載體和表示，信息是數(shù)據(jù)在特定場合下的具體含義，或者說信息是數(shù)據(jù)的語義，只有把兩者密切地結(jié)合起來，才能實(shí)現(xiàn)對現(xiàn)實(shí)世界中某一具體事物的描述。2.1.1知識的定義什么是知識知識：人們在長期的生活及社會實(shí)踐中、科學(xué)研究及實(shí)驗(yàn)中積累起來的對客觀世界的認(rèn)識與經(jīng)驗(yàn)，人們把實(shí)踐中獲得的信息關(guān)聯(lián)在一起，就獲得了知識。知識是經(jīng)過削減、塑造、解釋、選擇和轉(zhuǎn)換的信息。信息之間有多種關(guān)聯(lián)形式，用得最多的一種是如果……，則……例：如果大雁向南飛，則冬天就要來臨了。知識反映了客觀世界中事物之間的關(guān)系，不同事物或者相同事物間的不同關(guān)系形成了不同的知識。2.1.2知識的特性相對正確性知識是人們對客觀世界認(rèn)識的結(jié)晶，并且又受到長期實(shí)踐的檢驗(yàn)。在一定的條件及環(huán)境下，知識一般是正確的，可信任的，但其正確性受限于特定環(huán)境。不確定性知識可能是模糊的、不精確的,存在真與假之間的中間狀態(tài)。造成知識具有不確定性的原因主要包括1）隨機(jī)性2）模糊性3）不完全性4）經(jīng)驗(yàn)性可表示性與可利用性知識可以用適當(dāng)形式表示出來，如用語言、文字、圖形、神經(jīng)元網(wǎng)絡(luò)等，并且可以被利用來解決問題。2.1.3知識的分類根據(jù)知識的作用范圍劃分常識性知識:通用性知識,適用于所有領(lǐng)域。領(lǐng)域性知識:面向特定領(lǐng)域的專業(yè)知識，如專家的經(jīng)驗(yàn)及有關(guān)理論。根據(jù)知識的作用及表示劃分事實(shí)性知識:描述領(lǐng)域內(nèi)的有關(guān)概念、事實(shí)，事物的屬性及狀態(tài)等,一般采用直接表達(dá)的形式。過程性知識:用于指出如何處理與問題相關(guān)的信息以求得問題的解,一般是通過對領(lǐng)域內(nèi)各種問題的比較與分析得出的規(guī)律性的知識，由領(lǐng)域內(nèi)的規(guī)則、定律、定理及經(jīng)驗(yàn)構(gòu)成?？刂菩灾R:又稱為深層知識或者元知識，它是關(guān)于如何運(yùn)用已有的知識進(jìn)行問題求解的知識，因此又稱為“關(guān)于知識的知識”。2.1.3知識的分類根據(jù)知識的確定性劃分確定性知識：可指出其真值為“真”或“假”的知識，是精確性的知識。不確定性知識：具有“不確定”特性的知識，它是對不精確、不完全及模糊性知識的總稱。根據(jù)知識的結(jié)構(gòu)及表現(xiàn)形式劃分邏輯性知識：反映人類邏輯思維過程的知識。形象性知識：通過事物的形象建立起來的知識。從抽象的、整體的觀點(diǎn)來劃分可劃分為零級知識、一級知識、二級知識等，每一級知識都對其低一層的知識有指導(dǎo)意義。在實(shí)際應(yīng)用中，通常把零級知識與一級知識統(tǒng)稱為領(lǐng)域知識，而把二級以上的知識統(tǒng)稱為元知識。2.1.4知識的表示符號表示法用各種包含具體含義的符號，以各種不同的方式和次序組合起來表示知識的一類方法，主要用來表示邏輯性知識。連接機(jī)制表示法用神經(jīng)網(wǎng)絡(luò)技術(shù)把各種物理對象以不同的方式及次序連接起來，并在其間傳遞及加工各種包含具體意義的信息，以此來表示相關(guān)的概念及知識，特別適用于表示各種形象性知識。說明性表示法著重于知識的靜態(tài)方面，如客體、事件、事實(shí)及其相互關(guān)系和狀態(tài)等，其控制性知識包含在控制系統(tǒng)中。過程性表示法強(qiáng)調(diào)對知識的利用，著重于知識的動(dòng)態(tài)方面。其控制性知識全部嵌入對知識的描述中，且將知識包含在若干過程中。2.1.4知識的表示對同一知識，一般都可以用多種方法進(jìn)行表示，但其效果卻不相同。因?yàn)椴煌I(lǐng)域中的知識一般都有不同的特點(diǎn)，而每一種表示方法也各有自己的長處與不足。在選擇知識表示方法時(shí)，應(yīng)從以下幾個(gè)方面進(jìn)行考慮：1）充分表示領(lǐng)域知識2）有利于對知識的利用3）便于對知識的組織、維護(hù)與管理4）便于理解和實(shí)現(xiàn)2.1.5推理及其分類推理的定義及構(gòu)成推理是按某種策略由已知判斷推出另一判斷的思維過程。推理的構(gòu)成主要包括兩種判斷：一種是已知的判斷，另一種是由已知判斷推出的新判斷，即推理的結(jié)論。推理的分類從新判斷推出的途徑來劃分，推理可分為演繹推理、歸納推理及默認(rèn)推理。按推理時(shí)所用知識的確定性來劃分，推理可分為確定性推理與不確定性推理。按推理過程中推出的結(jié)論是否單調(diào)地增加，推理又分為單調(diào)推理與非單調(diào)推理。從方法論的角度劃分，推理可分為基于知識的推理、統(tǒng)計(jì)推理及直覺推理。2.1.5推理及其分類演繹推理演繹推理是從全稱判斷推導(dǎo)出特稱判斷或單稱判斷的過程，即由一般性知識推出適合于具體情況的結(jié)論。演繹推理經(jīng)常采用三段論式，它包括：（1）大前提，這是已知的一般性知識或假設(shè)；（2）小前提，這是關(guān)于所研究的具體情況或個(gè)別事實(shí)的判斷；（3）結(jié)論，這是由大前提推出的適合于小前提所示情況的新判斷。例：（1）電氣工程師從事電氣專業(yè)工程設(shè)計(jì)；（2）高波是一名電氣工程師；（3）所以，高波從事電氣專業(yè)工程設(shè)計(jì)。2.1.5推理及其分類歸納推理歸納推理是從足夠多的事例中歸納出一般性結(jié)論的推理過程，是一種從個(gè)別到一般的推理。從歸納時(shí)所選事例的廣泛性來劃分，歸納推理又可分為完全歸納推理與不完全歸納推理兩種。例：（1）完全歸納推理某廠進(jìn)行產(chǎn)品質(zhì)量檢查，對每一件產(chǎn)品都進(jìn)行了嚴(yán)格檢查推導(dǎo)出結(jié)論：該廠生產(chǎn)的產(chǎn)品是合格的（2）不完全歸納推理檢查產(chǎn)品質(zhì)量時(shí)，只是隨機(jī)地抽查了部分產(chǎn)品，它們都合格推導(dǎo)出結(jié)論：該廠生產(chǎn)的產(chǎn)品是合格的2.1.5推理及其分類默認(rèn)推理默認(rèn)推理又稱為缺省推理，它是在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。例如，在條件A已成立的情況下，如果沒有足夠的證據(jù)能證明條件B不成立，則就默認(rèn)B是成立的，并在此默認(rèn)的前提下進(jìn)行推理，推導(dǎo)出某個(gè)結(jié)論。擺脫了需要知道全部有關(guān)事實(shí)才能進(jìn)行推理的要求，使得在知識不完全的情況下也能進(jìn)行推理。如果到某一時(shí)刻發(fā)現(xiàn)原先所作的默認(rèn)不正確，則要撤消所作的默認(rèn)以及由此默認(rèn)推出的所有結(jié)論，重新按新情況進(jìn)行推理。2.1.5推理及其分類確定性推理、不確定性推理確定性推理：推理時(shí)所用的知識都是精確的，推出的結(jié)論也是確定的，其真值或者為真，或者為假，沒有第三種情況出現(xiàn)。（經(jīng)典邏輯推理）不確定性推理：推理時(shí)所用的知識不都是精確的，推出的結(jié)論也不完全是肯定的。其真值位于真與假之間，命題的外延模糊不清。2.1.5推理及其分類單調(diào)推理、非單調(diào)推理單調(diào)推理：在推理過程中隨著推理的向前推進(jìn)及新知識的加入，推出的結(jié)論呈單調(diào)增加的趨勢，并且越來越接近最終目標(biāo)，不會由于新知識的加入否定了前面推出的結(jié)論。（基于經(jīng)典邏輯的演繹推理）非單調(diào)推理：在推理過程中由于新知識的加入，不僅沒有加強(qiáng)已推出的結(jié)論，反而要否定它，使得推理退回到前面的某一步，重新開始。非單調(diào)推理多是在知識不完全的情況下發(fā)生的。（默認(rèn)推理）2.1.5推理及其分類基于知識的推理、統(tǒng)計(jì)推理、直覺推理基于知識的推理：根據(jù)已掌握的事實(shí)，通過運(yùn)用知識進(jìn)行的推理。例：醫(yī)生根據(jù)病人的癥狀及檢驗(yàn)結(jié)果，運(yùn)用醫(yī)學(xué)知識進(jìn)行推理，最后給出診斷結(jié)論及治療方案。統(tǒng)計(jì)推理：根據(jù)對某事物的數(shù)據(jù)統(tǒng)計(jì)進(jìn)行的推理。例：農(nóng)民根據(jù)對農(nóng)作物的產(chǎn)量統(tǒng)計(jì)，得出是否增產(chǎn)的結(jié)論，從而可找出增產(chǎn)或者減產(chǎn)的原因。直覺推理：又稱為常識性推理，是根據(jù)常識進(jìn)行的推理。例：從某建筑物下面走過時(shí)，猛然發(fā)現(xiàn)有一物體從建筑物上掉落下來，這時(shí)你立即意識到有危險(xiǎn)并躲開。本章主要內(nèi)容圖2-1第二章主要內(nèi)容本章提綱2.1知識和推理的關(guān)系2.2一階謂詞邏輯表示法2.3產(chǎn)生式表示法2.5語義網(wǎng)絡(luò)表示法2.4框架表示法2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)命題與真值定義2.1一個(gè)陳述句稱為一個(gè)斷言。凡有真假意義的斷言稱為命題。命題的意義通常稱為真值，它只有真、假兩種情況。當(dāng)命題的意義為真時(shí)，則稱該命題的真值為真，記為T；反之，則稱該命題的真值為假，記為F。一個(gè)命題不能同時(shí)既為真又為假。一個(gè)命題可在一定條件下為真，在另一種條件下為假。沒有真假意義的感嘆句、疑問句等都不是命題。2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)論域與謂詞論域是由所討論對象之全體構(gòu)成的非空集合。論域中的元素稱為個(gè)體，論域也常稱為個(gè)體域。例:整數(shù)的個(gè)體域是由所有整數(shù)構(gòu)成的集合，每個(gè)整數(shù)都是該個(gè)體域中的一個(gè)個(gè)體。在謂詞邏輯中，命題是用謂詞來表示的。一個(gè)謂詞可分為謂詞名和個(gè)體兩部分。其中，個(gè)體是命題中的主語，謂詞名是命題的謂語。定義2.2設(shè)D是個(gè)體域。是一個(gè)映射，其中則稱P是一個(gè)n元謂詞（n=1，2，…），記為P(x1,x2,…,xn)。其中，x1，x2，…，xn為個(gè)體變元。2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)連接詞與量詞（1）連接詞連接詞是用來連接簡單命題，并由簡單命題構(gòu)成復(fù)合命題的邏輯運(yùn)算符號。它們分別是：?：稱為“非”或者“否定”。表示對其后面的命題的否定。?：稱為“析取”。表示所連接的兩個(gè)命題間具有“或”的關(guān)系。?：稱為“合取”。表示所連接的兩個(gè)命題間具有“與”的關(guān)系?！悍Q為“條件”或“蘊(yùn)涵”。它示“若……，則……”的語義。?：稱為“雙條件”。表示“當(dāng)且僅當(dāng)”的語義。2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)連接詞與量詞（1）連接詞PQ?PP?QP?QP→QP?QTTFTTTTTFFTFFFFTTTFTFFFTFFTT表

2?1謂詞邏輯真值表2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)連接詞與量詞（2）量詞全稱量詞“?”：“所有的”、“任一個(gè)”；存在量詞“?”：“至少有一個(gè)”、“存在有”。全稱量詞的定義：命題(?x)P(x)為真，當(dāng)且僅當(dāng)對論域中的所有x，都有P(x)為真。命題(?x)P(x)為假，當(dāng)且僅當(dāng)至少存在一個(gè)x0∈D，使得P(x0)為假。存在量詞的定義：命題(?x)P(x)為真，當(dāng)且僅當(dāng)至少存在一個(gè)x0∈D，使得P(x0)為真。命題(?x)P(x)為假，當(dāng)且僅當(dāng)對論域中的所有x，都有P(x)為假。2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)項(xiàng)與合式公式在一階謂詞演算中，合法的表達(dá)式稱為合式公式（即謂詞公式）。對合式公式的定義將涉及到“項(xiàng)”的概念，下面分別給出它們的定義。定義2.4項(xiàng)滿足如下規(guī)則：（1）單獨(dú)一個(gè)個(gè)體是項(xiàng)；（2）若t1，t2，…，tn是項(xiàng)，f是n元函數(shù)，則f(t1,t2,…,tn)是項(xiàng)；（3）由（1）、（2）生成的表達(dá)式是項(xiàng)。定義2.5原子謂詞公式的含義為：若t1，t2，…，tn是項(xiàng)，P是謂詞符號，則稱P(t1,t2,…,tn)為原子謂詞公式。2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)項(xiàng)與合式公式定義2.6滿足如下規(guī)則的謂詞演算可得到合式公式：（1）單個(gè)原子謂詞公式是合式公式；（2）若A是合式公式，則?A也是合式公式；（3）若A，B都是合式公式，則A?B，A?B，A→B，A?

B也都是合式公式；（4）若A是合式公式，x是項(xiàng)，則(?x)A和(?x)A也都是合式公式。在合式公式中，連接詞的優(yōu)先級別是：?，?，?，→，?2.2.1一階謂詞邏輯表示的邏輯基礎(chǔ)自由變元和約束變元轄域:位于量詞后面的單個(gè)謂詞或者用括弧括起來的合式公式。約束變元：轄域內(nèi)與量詞中同名的變元。自由變元：不受約束的變元。例：(?x)(P(x,y)→Q(x,y))?R(x,y)式中，(P(x,y)→Q(x,y))是(?x)的轄域，轄域內(nèi)的變元x是受(?x)約束的變元；R(x,y)中的x是自由變元；公式中所有的y都是自由變元。2.2.2一階謂詞邏輯表示方法（1）首先定義謂詞，指出每個(gè)謂詞的確切含義；（2）再用連接詞把有關(guān)的謂詞連接起來，形成一個(gè)謂詞公式表達(dá)一個(gè)完整的意義。例2.1用一階謂詞邏輯表示下列知識：小王是電氣工程系的一名學(xué)生。小王喜歡編程序。有的電氣工程系的學(xué)生不喜歡編程序。首先定義謂詞：ELECTRIC(x)：x是電氣工程系的學(xué)生。LIKE(,)：喜歡。此時(shí)可把上述知識分別表示為：COMPUTER(Xiaowang)LIKE(Xiaowang,programming)(?x)(ELECTRIC(x)→?LIKE(x,programming))例2.2用一階謂詞邏輯表示下列知識：所有的整數(shù)不是偶數(shù)就是奇數(shù)。首先定義謂詞：I(x)：x是整數(shù)。E(x)：x是偶數(shù)。O(x)：x是奇數(shù)。此時(shí)可把上述知識分別表示為：(?x)(I(x)→E(x)?O(x))(謂詞公式表示知識步驟2.2.3一階謂詞邏輯表示法的特點(diǎn)優(yōu)點(diǎn)（1）自然性（2）精確性（3）嚴(yán)密性（4）模塊化局限性（1）知識表示范圍的局限性只能表示精確性的知識，不能表示不精確、模糊性的知識。（2）容易產(chǎn)生組合爆炸隨著事實(shí)數(shù)目的增大及盲目地使用推理規(guī)則，可能形成組合爆炸。（3）效率低本章提綱2.1知識和推理的關(guān)系2.2一階謂詞邏輯表示法2.3產(chǎn)生式表示法2.5語義網(wǎng)絡(luò)表示法2.4框架表示法2.3.1產(chǎn)生式的基本形式產(chǎn)生式通常用于表示具有因果關(guān)系的知識，其基本形式是P→Q或者IFPTHENQ整個(gè)產(chǎn)生式的含義是：如果前提P被滿足，則可推出結(jié)論Q或執(zhí)行Q所規(guī)定的操作。蘊(yùn)含式與產(chǎn)生式的區(qū)別（1）蘊(yùn)含式只能表示精確知識，其值或者為真，或者為假，而產(chǎn)生式不僅可以表示精確知識，而且還可以表示不精確知識。（2）產(chǎn)生式中已知事實(shí)與前提所規(guī)定的條件，只要按某種算法求出的相似度落在某個(gè)預(yù)先指定的范圍內(nèi)就認(rèn)為是可匹配的，但對謂詞邏輯的蘊(yùn)含式來說，其匹配總要求是精確的。2.3.1產(chǎn)生式的基本形式用巴科斯范式BNF（BackusNormalForm）給出產(chǎn)生式的形式描述及語義如下：<產(chǎn)生式>::=<前提>→<結(jié)論><前提>::=<簡單條件>|<復(fù)合條件><結(jié)論>::=<事實(shí)>|<操作><復(fù)合條件>::=<簡單條件>AND<簡單條件>[(AND<簡單條件>)…]|<簡單條件>OR<簡單條件>[(OR<簡單條件>)…]<操作>::=<操作名>[(<變元>,…)]2.3.2產(chǎn)生式系統(tǒng)一般來說，一個(gè)產(chǎn)生式系統(tǒng)由以下三個(gè)基本部分組成：規(guī)則庫，綜合數(shù)據(jù)庫，控制系統(tǒng)。圖2-2產(chǎn)生式系統(tǒng)基本結(jié)構(gòu)規(guī)則庫用于描述相應(yīng)領(lǐng)域內(nèi)知識的產(chǎn)生式集合稱為規(guī)則庫。在建立規(guī)則庫時(shí)應(yīng)注意：（1）有效地表達(dá)領(lǐng)域內(nèi)的過程性知識。（2）對知識進(jìn)行合理的組織與管理。2.3.2產(chǎn)生式系統(tǒng)一般來說，一個(gè)產(chǎn)生式系統(tǒng)由以下三個(gè)基本部分組成：規(guī)則庫，綜合數(shù)據(jù)庫，控制系統(tǒng)。圖2-2產(chǎn)生式系統(tǒng)基本結(jié)構(gòu)綜合數(shù)據(jù)庫綜合數(shù)據(jù)庫又稱為事實(shí)庫、上下文、黑板等。它是一個(gè)用于存放問題求解過程中各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)，例如問題的初始狀態(tài)、原始證據(jù)、推理中得到的中間結(jié)論及最終結(jié)論。當(dāng)規(guī)則庫中某條產(chǎn)生式的前提可與綜合數(shù)據(jù)庫中的某些已知事實(shí)匹配時(shí)，該產(chǎn)生式就被激活，并把用它推出的結(jié)論放入綜合數(shù)據(jù)庫中，作為后面推理的已知事實(shí)。顯然，綜合數(shù)據(jù)庫的內(nèi)容是在不斷變化的，是動(dòng)態(tài)的。2.3.2產(chǎn)生式系統(tǒng)一般來說，一個(gè)產(chǎn)生式系統(tǒng)由以下三個(gè)基本部分組成：規(guī)則庫，綜合數(shù)據(jù)庫，控制系統(tǒng)。圖2-2產(chǎn)生式系統(tǒng)基本結(jié)構(gòu)控制系統(tǒng)控制系統(tǒng)又稱為推理機(jī)構(gòu)，由一組程序組成，負(fù)責(zé)整個(gè)產(chǎn)生式系統(tǒng)的運(yùn)行，實(shí)現(xiàn)對問題的求解。它要做以下幾項(xiàng)主要的工作：1）按一定的策略從規(guī)則庫選擇規(guī)則與綜合數(shù)據(jù)庫中的已知事實(shí)進(jìn)行匹配。2）匹配成功的規(guī)則可能不止一條，此時(shí)，推理機(jī)構(gòu)須調(diào)用相應(yīng)的解決沖突策略進(jìn)行消解，以便從中選出一條執(zhí)行。2.3.2產(chǎn)生式系統(tǒng)一般來說，一個(gè)產(chǎn)生式系統(tǒng)由以下三個(gè)基本部分組成：規(guī)則庫，綜合數(shù)據(jù)庫，控制系統(tǒng)。圖2-2產(chǎn)生式系統(tǒng)基本結(jié)構(gòu)控制系統(tǒng)3）在執(zhí)行某一條規(guī)則時(shí)，如果該規(guī)則的右部是一個(gè)或多個(gè)結(jié)論，則把這些結(jié)論加入到綜合數(shù)據(jù)庫中；如果規(guī)則的右部是一個(gè)或多個(gè)操作，則執(zhí)行這些操作。4）對于不確定性知識，在執(zhí)行每一條規(guī)則時(shí)還要按一定算法計(jì)算結(jié)論的不確定性。5）隨時(shí)掌握結(jié)束產(chǎn)生式系統(tǒng)運(yùn)行的時(shí)機(jī)，以便在適當(dāng)?shù)臅r(shí)候停止系統(tǒng)的運(yùn)行。2.3.3產(chǎn)生式系統(tǒng)的分類按規(guī)則庫及綜合數(shù)據(jù)庫的性質(zhì)及結(jié)構(gòu)特征進(jìn)行分類，產(chǎn)生式系統(tǒng)可分為：可交換的產(chǎn)生式系統(tǒng)，可分解的產(chǎn)生式系統(tǒng)，可恢復(fù)的產(chǎn)生式系統(tǒng)?？山粨Q的產(chǎn)生式系統(tǒng)如果一個(gè)產(chǎn)生式系統(tǒng)對規(guī)則的使用次序是可交換的，就稱這樣的產(chǎn)生式系統(tǒng)為可交換的產(chǎn)生式系統(tǒng)。在可交換產(chǎn)生式系統(tǒng)中，綜合數(shù)據(jù)庫DB的內(nèi)容是遞增的，即對規(guī)則的任何執(zhí)行序列

都有

2.3.3產(chǎn)生式系統(tǒng)的分類可分解的產(chǎn)生式系統(tǒng)

2.3.3產(chǎn)生式系統(tǒng)的分類可恢復(fù)的產(chǎn)生式系統(tǒng)

2.3.4產(chǎn)生式表示法的特點(diǎn)優(yōu)點(diǎn)（1）自然性（2）模塊性（3）有效性（4）清晰化局限性（1）效率不高由于規(guī)則庫一般都比較龐大，而匹配又是一件十分費(fèi)時(shí)的工作，因此其工作效率是不高的。在求解復(fù)雜問題時(shí)容易引起組合爆炸。（2）表達(dá)能力較低產(chǎn)生式適合于表達(dá)具有因果關(guān)系的過程性知識，但對具有結(jié)構(gòu)關(guān)系的知識卻無能為力。本章提綱2.1知識和推理的關(guān)系2.2一階謂詞邏輯表示法2.3產(chǎn)生式表示法2.5語義網(wǎng)絡(luò)表示法2.4框架表示法2.4.1框架框架是一種描述所論對象屬性的數(shù)據(jù)結(jié)構(gòu)。在框架理論中，將其視作知識表示的一個(gè)基本單位。一個(gè)框架中可以有任意有限數(shù)目的槽、側(cè)面和側(cè)面值，視其描述的屬性而定。2.4.1框架例：2.4.1框架（1）框架名的值允許帶有參數(shù)。此時(shí)，當(dāng)另一個(gè)框架調(diào)用它時(shí)需要提供相應(yīng)的實(shí)在參數(shù)。（2）當(dāng)槽值或側(cè)面值是一個(gè)過程時(shí)，它既可以是一個(gè)明確表示出來的<動(dòng)作>串，也可以是對主語言的某個(gè)過程的調(diào)用，從而可將過程性知識表示出來。（3）當(dāng)槽值或側(cè)面值是謂詞時(shí)，其真值由當(dāng)時(shí)謂詞中變元的取值確定。（4）槽值或側(cè)面值為<空>時(shí)，表示該值等待以后填入，當(dāng)時(shí)還不能確定。（5）<約束條件>是任選的，當(dāng)不指出約束條件時(shí)，表示沒有約束。2.4.2框架網(wǎng)絡(luò)框架的橫向聯(lián)系框架之間可以通過槽值建立橫向聯(lián)系。例如，在描述教師信息的框架中，“住址”槽的值可以是另一個(gè)框架的名字，如“adr_1”。橫向聯(lián)系使得我們可以從一個(gè)框架跳轉(zhuǎn)到另一個(gè)相關(guān)框架，獲取更多詳細(xì)信息，極大地增強(qiáng)了框架網(wǎng)絡(luò)的靈活性和信息檢索能力。2.4.2框架網(wǎng)絡(luò)框架的縱向聯(lián)系框架之間通過在下層框架中設(shè)置"繼承"槽，指明其上層框架，可以實(shí)現(xiàn)屬性的繼承。這種機(jī)制允許下層框架自動(dòng)獲得上層框架的屬性和值，避免了重復(fù)描述，提高了效率。2.4.3框架中槽的設(shè)置與組織在用框架作為知識的表示模式時(shí)，對槽的設(shè)置與組織應(yīng)注意以下幾個(gè)方面的問題：（1）充分表達(dá)事物各有關(guān)方面的屬性（2）充分表達(dá)相關(guān)事物間的各種關(guān)系（3）對槽及側(cè)面進(jìn)行合理的組織（4）有利于進(jìn)行框架推理2.4.3框架中槽的設(shè)置與組織幾種系統(tǒng)預(yù)定義槽名（1）ISA槽

用于指出事物間抽象概念上的類屬關(guān)系。其直觀含義是“是一個(gè)”，“是一種”，“是一只”，……。（2）AKO槽

用于具體地指出事物間的類屬關(guān)系。其直觀含義是“是一種”。用法類似于ISA槽。（3）Subclass槽

用于指出子類與類之間的類屬關(guān)系。用法類似于ISA槽。2.4.3框架中槽的設(shè)置與組織幾種系統(tǒng)預(yù)定義槽名（4）Instance槽

用來建立AKO槽的逆關(guān)系。當(dāng)用它作為某上層框架的槽時(shí)，可用來指出它的下一層框架是哪一些。（5）Part-of槽用于指出“部分”與“全體”的關(guān)系。（6）Infer槽用于指出兩個(gè)框架所描述事物間的邏輯推理關(guān)系，用它可以表示相應(yīng)的產(chǎn)生式規(guī)則。2.4.3框架中槽的設(shè)置與組織幾種系統(tǒng)預(yù)定義槽名（7）Possible-Reason槽與Infer槽的作用相反，它用來把某個(gè)結(jié)論與可能的原因聯(lián)系起來。例如，在上述的“結(jié)論”框架中可增加一個(gè)Possible-Reason槽，其槽值是某個(gè)框架的框架名，在該框架中描述了產(chǎn)生“感冒”的原因，如感染了流感病毒等。除了上述七種描述框架間層次結(jié)構(gòu)關(guān)系及推論關(guān)系的槽外，還有一些描述其它關(guān)系（如占有關(guān)系、時(shí)間關(guān)系、空間關(guān)系、相似關(guān)系等）的槽，在此不再一一列舉。2.4.4框架系統(tǒng)中求解問題的基本過程在用框架表示知識的系統(tǒng)中，問題的求解主要是通過匹配與填槽實(shí)現(xiàn)的。主要過程如下：（1）把問題用一個(gè)框架表示出來（2）通過與知識庫中已有框架進(jìn)行匹配，找出一個(gè)或幾個(gè)可匹配的預(yù)選框架作為初步假設(shè)，并收集進(jìn)一步的信息（3）用某種評價(jià)方法對預(yù)選框架進(jìn)行評價(jià)，以便決定是否接受它框架的匹配是通過對相應(yīng)的槽的槽名及槽值逐個(gè)進(jìn)行比較實(shí)現(xiàn)的。由于框架間存在繼承關(guān)系，以及應(yīng)用中問題的隨機(jī)性和復(fù)雜性，這使得框架的匹配問題成為一個(gè)比較復(fù)雜且比較困難，但又不能不解決的問題。2.4.5框架表示法的特點(diǎn)（1）結(jié)構(gòu)性框架表示法善于表達(dá)結(jié)構(gòu)性的知識，能夠把知識的內(nèi)部結(jié)構(gòu)關(guān)系及知識間的聯(lián)系表示出來。（2）繼承性框架表示法通過使槽值為另一個(gè)框架的名字實(shí)現(xiàn)框架間的聯(lián)系，建立起表示復(fù)雜知識的框架網(wǎng)絡(luò)。（3）自然性框架表示法體現(xiàn)了人們在觀察事物時(shí)的思維活動(dòng)，與人們的認(rèn)識活動(dòng)是一致的。（4）缺點(diǎn)框架表示法的主要不足之處是不善于表達(dá)過程性的知識。本章提綱2.1知識和推理的關(guān)系2.2一階謂詞邏輯表示法2.3產(chǎn)生式表示法2.5語義網(wǎng)絡(luò)表示法2.4框架表示法2.5.1語義網(wǎng)絡(luò)的概念語義網(wǎng)絡(luò)是通過概念及其語義關(guān)系來表達(dá)知識的一種網(wǎng)絡(luò)圖。從圖論的觀點(diǎn)看，它其實(shí)就是一個(gè)“帶標(biāo)識的有向圖”。其中，有向圖的節(jié)點(diǎn)表示各種事物、概念、情況、屬性、動(dòng)作、狀態(tài)等；弧表示各種語義聯(lián)系，指明它所連接的節(jié)點(diǎn)間的某種語義關(guān)系。一個(gè)最簡單的語義網(wǎng)絡(luò)是如下一個(gè)三元組：（節(jié)點(diǎn)1，弧，節(jié)點(diǎn)2）2.5.1語義網(wǎng)絡(luò)的概念當(dāng)把多個(gè)基本網(wǎng)元用相應(yīng)語義聯(lián)系關(guān)聯(lián)在一起時(shí)，就可得到一個(gè)語義網(wǎng)絡(luò)，下面給出語義網(wǎng)絡(luò)的BNF描述：<語義網(wǎng)絡(luò)>：：=<基本網(wǎng)元>|Merge(<基本網(wǎng)元>,…)<基本網(wǎng)元>：：=<基節(jié)點(diǎn)><語義聯(lián)系><節(jié)點(diǎn)><節(jié)點(diǎn)>：：=(<屬性—值對>,…)<屬性—值對>：：=<屬性名>：<屬性值><語義聯(lián)系>：：=<系統(tǒng)預(yù)定義的語義聯(lián)系>|<用戶自定義的語義聯(lián)系>2.5.2知識的語義網(wǎng)絡(luò)表達(dá)用語義網(wǎng)絡(luò)表示事實(shí)用短線與相應(yīng)節(jié)點(diǎn)相連的部分是該節(jié)點(diǎn)所描述對象的屬性下層概念可以繼承上層概念的屬性下層概念還可對其上層概念的屬性做進(jìn)一步的細(xì)化、補(bǔ)充、變異2.5.2知識的語義網(wǎng)絡(luò)表達(dá)用語義網(wǎng)絡(luò)表示事實(shí)圖2?11具有合取、析取關(guān)系的語義網(wǎng)絡(luò)圖2?13用動(dòng)作作為節(jié)點(diǎn)的語義網(wǎng)絡(luò)2.5.2知識的語義網(wǎng)絡(luò)表達(dá)用語義網(wǎng)絡(luò)表示事實(shí)間的關(guān)系（1）分類關(guān)系（2）聚集關(guān)系（4）多元關(guān)系（5）時(shí)間、位置等關(guān)系（3）推論關(guān)系2.5.2知識的語義網(wǎng)絡(luò)表達(dá)用語義網(wǎng)絡(luò)表示比較復(fù)雜的知識例1一個(gè)語義網(wǎng)絡(luò)表示兩個(gè)簡單事實(shí)黎明的電動(dòng)車是雅迪牌，黑色。劉華的電動(dòng)車是綠源牌，紅色。2.5.2知識的語義網(wǎng)絡(luò)表達(dá)用語義網(wǎng)絡(luò)表示比較復(fù)雜的知識例2含有全稱量詞的語義網(wǎng)絡(luò)1）每個(gè)學(xué)生都背誦了一首唐詩2）每個(gè)學(xué)生都背誦了《靜夜思》這首唐詩2.5.3常用的語義聯(lián)系（1）A-Member-of聯(lián)系表示個(gè)體與集體（類或集合）之間的關(guān)系，它們之間有屬性繼承性和屬性更改權(quán)。（2）Composed-of聯(lián)系表示“構(gòu)成”聯(lián)系，是一種一對多的聯(lián)系，被它聯(lián)系的節(jié)點(diǎn)間不具有屬性繼承性。（3）Have聯(lián)系表示屬性或事物的“占有”關(guān)系。2.5.3常用的語義聯(lián)系（4）Before，After，At聯(lián)系表示事件之間的時(shí)間先后關(guān)系的。（5）Located-on（-at，-under，-inside，-outside等)表示事物間的位置關(guān)系。（6）Similar-to，Near-to聯(lián)系表示事物間的相似和接近關(guān)系2.5.4語義網(wǎng)絡(luò)系統(tǒng)中求解問題的基本過程語義網(wǎng)絡(luò)系統(tǒng)主要由兩大部分組成：（1）由語義網(wǎng)絡(luò)構(gòu)成的知識庫；（2）用于求解問題的解釋程序，稱為語義網(wǎng)絡(luò)推理機(jī)。語義網(wǎng)絡(luò)系統(tǒng)求解問題的主要過程如下：（1）根據(jù)待求解問題的要求構(gòu)造一個(gè)網(wǎng)絡(luò)片斷，其中有些節(jié)點(diǎn)或弧的標(biāo)識是空的，反映待求解的問題。（2）依此網(wǎng)絡(luò)片斷到知識庫中去尋找可匹配的網(wǎng)絡(luò)，以找出所需要的信息。（3）當(dāng)問題的語義網(wǎng)絡(luò)片斷與知識庫中的某語義網(wǎng)絡(luò)片斷匹配時(shí)，則與詢問處匹配的事實(shí)就是問題的解。2.5.4語義網(wǎng)絡(luò)系統(tǒng)中求解問題的基本過程例：（1）趙云受教育情況的語義網(wǎng)絡(luò)（2）待求解問題的語義網(wǎng)絡(luò)片斷2.5.5語義網(wǎng)絡(luò)表示法的特點(diǎn)優(yōu)點(diǎn)（1）結(jié)構(gòu)性（2）聯(lián)想性語義網(wǎng)絡(luò)著重于表達(dá)語義關(guān)系知識，體現(xiàn)了聯(lián)想思維過程便于以聯(lián)想的方式實(shí)現(xiàn)對系統(tǒng)的檢索，有效避免組合爆炸（3）自然性缺點(diǎn)（1）不能保證嚴(yán)格性不能保證網(wǎng)絡(luò)操作所得推論的嚴(yán)格性和有效性語義網(wǎng)絡(luò)的含義完全依賴于處理程序如何對它進(jìn)行解釋（2）處理上的復(fù)雜性語義網(wǎng)絡(luò)表示知識的手段和節(jié)點(diǎn)間的聯(lián)系方式多種多樣本章提綱2.6自然演繹推理2.7歸結(jié)演繹推理2.8與/或形演繹推理2.10證據(jù)理論2.9主觀貝葉斯推理2.11語義網(wǎng)絡(luò)表示法2.6自然演繹推理前面討論了知識及其表示的有關(guān)問題，這樣就可把知識用某種模式表示出來存儲到計(jì)算機(jī)中去。但是，為使計(jì)算機(jī)具有智能，僅僅使它擁有知識還是不夠的，還必須使它具有思維能力，即能運(yùn)用知識進(jìn)行推理，求解問題。因此，關(guān)于推理及其方法的研究就成為人工智能的一個(gè)重要研究課題。目前，人們已經(jīng)對推理進(jìn)行了比較多的研究，提出了多種可在計(jì)算機(jī)上實(shí)現(xiàn)的推理方法。其中經(jīng)典邏輯推理是最先提出的一種。經(jīng)典邏輯推理是根據(jù)經(jīng)典邏輯（命題邏輯及一階謂詞邏輯）的邏輯規(guī)則進(jìn)行的一種推理，又稱為機(jī)械-自動(dòng)定理證明（mechanical-automatictheoremproving），主要推理方法有自然演繹推理、歸結(jié)演繹推理及與/或形演繹推理等。2.6.1推理所需邏輯基礎(chǔ)定義2.7如果謂詞公式P對非空個(gè)體域D上的任一解釋都取得真值T，則稱P在D上是永真的；如果P在任何非空個(gè)體域上均是永真的，則稱P永真。定義2.8對于謂詞公式P，如果至少存在D上的一個(gè)解釋，使公式P在此解釋下的真值為T，則稱公式P在D上是可滿足的。謂詞公式的可滿足性也稱為相容性。定義2.9如果謂詞公式P對非空個(gè)體域D上的任一解釋都取真值F，則稱P在D上是永假的；如果P在任何非空個(gè)體域上均是永假的，則稱P永假。謂詞公式的永假性又稱不可滿足性或不相容性。謂詞公式的永真性與可滿足性2.6.1推理所需邏輯基礎(chǔ)定義2.10設(shè)P與Q是D上的兩個(gè)謂詞公式，若對D上的任意解釋，P與Q都有相同的真值，則稱P與Q在D上是等價(jià)的。如果D是任意非空個(gè)體域，則稱P與Q是等價(jià)的，記做P?Q。謂詞公式的等價(jià)性與永真蘊(yùn)涵性

2.6.1推理所需邏輯基礎(chǔ)謂詞公式的等價(jià)性與永真蘊(yùn)涵性

2.6.1推理所需邏輯基礎(chǔ)定義2.11對謂詞公式P和Q，如果P→Q永真，則稱P永真蘊(yùn)涵Q，且稱Q為P的邏輯結(jié)論，P為Q的前提，記做P?Q。永真蘊(yùn)涵式常用的永真蘊(yùn)涵式如下：1）化簡式P?Q?P，P?Q?Q3）析取三段論?P，P?Q?Q5）拒取式?Q，P→Q??P2）附加式P?P?Q，Q?P?Q4）假言推理P，P→Q?Q6）假言三段論P(yáng)→Q，Q→R?P→R7）二難推理P?Q，P→R，Q→R?R8）全稱固化(?x)P(x)?P(y)式中，y是個(gè)體域中的任一個(gè)體，利用此永真蘊(yùn)涵式可消去謂詞公式中的全稱量詞。9）存在固化(?x)P(x)?P(y)式中，y是個(gè)體域中某一個(gè)可以使P(y)為真的個(gè)體，利用此永真蘊(yùn)涵式可消去謂詞公式中的存在量詞。2.6.1推理所需邏輯基礎(chǔ)永真蘊(yùn)涵式2.6.1推理所需邏輯基礎(chǔ)（1）置換定義2.12置換是形如{t1/x1，t2/x2，…，tn/xn}的有限集合。其中，t1，t2，…，tn是項(xiàng)；x1，x2，…，xn是互不相同的變元；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，xi不能循環(huán)地出現(xiàn)在另一個(gè)ti中。定義2.13設(shè)θ={t1/x1，t2/x2，…，tn/xn}是一個(gè)置換，F(xiàn)是一個(gè)謂詞公式，把公式F中出現(xiàn)的所有xi換成ti

（i=1，2，…，n），得到一個(gè)新的公式G，稱G為F在置換θ下的例示，記做G=Fθ。一個(gè)謂詞公式的任何例示都是該公式的邏輯結(jié)論。置換與合一2.6.1推理所需邏輯基礎(chǔ)（1）置換定義2.14設(shè)θ={t1/x1，t2/x2，…，tn/xn}，λ={u1/y1，u2/y2，…，um/ym}是兩個(gè)置換。則θ與λ的合成也是一個(gè)置換，記做θ·λ。它是從集合{t1λ/x1，t2λ/x2，…，tnλ/xn，u1/y1，u2/y2，…，um/ym}中刪去以下兩種元素：① 當(dāng)tiλ=xi時(shí)，刪去tiλ/xi（i=1，2，…，n）；② 當(dāng)yj∈{x1，x2，…，xn}時(shí)，刪去uj/yj（j=1，2，…，m）。最后剩下的元素所構(gòu)成的集合。置換與合一2.6.1推理所需邏輯基礎(chǔ)（2）合一定義2.15設(shè)有公式集F={F1，F(xiàn)2，…，F(xiàn)n}若存在一個(gè)置換θ，可使F1θ=F2θ=…=Fnθ，則稱θ是F的一個(gè)合一，稱F1，F(xiàn)2，…，F(xiàn)n是可合一的。一般來說，一個(gè)公式集的合一不是唯一的。定義2.16設(shè)σ是公式集F的一個(gè)合一，如果對F的任一個(gè)合一θ都存在一個(gè)置換λ，使得θ=σ·λ，則稱σ是一個(gè)最一般合一。一個(gè)公式集的最一般合一是唯一的。若用最一般合一去置換那些可合一的謂詞公式，可使它們變成完全一致的謂詞公式。置換與合一2.6.2自然演繹推理的形式自然演繹推理：從一組已知為真的事實(shí)出發(fā)，直接運(yùn)用經(jīng)典邏輯的推理規(guī)則推出結(jié)論的過程。其中，基本的推理規(guī)則是P規(guī)則、T規(guī)則、假言推理、拒取式推理等。2.6.3自然演繹推理的特點(diǎn)優(yōu)點(diǎn)（1）表達(dá)定理證明過程自然，容易理解（2）擁有豐富的推理規(guī)則，推理過程靈活缺點(diǎn)（1）容易產(chǎn)生組合爆炸本章提綱2.6自然演繹推理2.7歸結(jié)演繹推理2.8與/或形演繹推理2.10證據(jù)理論2.9主觀貝葉斯推理2.11語義網(wǎng)絡(luò)表示法2.7.1子句定理證明的實(shí)質(zhì)：對前提P和結(jié)論Q證明P→Q的永真性難點(diǎn)：證明一個(gè)謂詞公式的永真性解決思路：應(yīng)用反證法的思想，把關(guān)于永真性的證明轉(zhuǎn)化為不可滿足性的證明理論成果：海伯倫理論、魯賓遜歸結(jié)原理（以子句集為研究背景）定義2.17任何文字的析取式稱為子句。例：P(x)?Q(x)，?P(x,f(x))?Q(x,g(x))定義2.18不包含任何文字的子句稱為空子句。2.7.1子句（1）利用等價(jià)關(guān)系消去“→”和“?”。（2）重新命名變元名，使不同量詞約束的變元有不同的名字。（3）利用Skolem函數(shù)替換消去存在量詞，并化為標(biāo)準(zhǔn)形。（4）消去全稱量詞（5）對變元更名（6）消去合取詞謂詞公式轉(zhuǎn)化為子句集的步驟2.7.1子句例：謂詞公式轉(zhuǎn)化為子句集的步驟（1）（2）（3）（4）,（5）（6）2.7.2海伯倫理論定理2.1設(shè)有謂詞公式F，其標(biāo)準(zhǔn)形的子句集為S，則F不可滿足的充要條件是S不可滿足。定義2.19設(shè)S為子句集，則按下述方法構(gòu)造的域H∞稱為海伯倫域，簡記為H域：（1）令H0是S中所有個(gè)體常量的集合，若S中不包含個(gè)體常量，則令H0={a}，其中a為任意指定的一個(gè)個(gè)體常量。（2）令Hi+1=Hi∪{S中所有n元函數(shù)f(x1,?,xn)|xj（j=1,…,n）是Hi中的元素}，其中，i=0,1,2,…。2.7.2海伯倫理論2.7.2海伯倫理論2.7.2海伯倫理論定義2.20子句集S在H域上的一個(gè)解釋I滿足下列條件：（1）在解釋I下，常量映射到自身；（2）S中的任一個(gè)n元函數(shù)是Hn→H的映射。即，設(shè)h1,h2,…∈H，則f(h1,h2,?,hn)∈H；（3）S中的任一個(gè)n元謂詞是Hn→{T,F}的映射。謂詞的真值可以指派T，也可以指派為F。例:子句集S={P(a)，Q(f(x))}，它的H域?yàn)閧a,f(a),f(f(a)),…}。S的原子集為{P(a),Q(f(a)),Q(f(f((a))),…}，則S的解釋為：I1={P(a),Q(f(a)),Q(f(f((a))),…}I2={P(a),?Q(f(a)),Q(f(f((a))),…}…2.7.2海伯倫理論定理2.2子句集S不可滿足的充要條件是S對H域上的一切解釋都為假。定理2.3子句集不可滿足的充要條件是存在一個(gè)有限的不可滿足的基子句集S’。（海伯倫定理）海伯倫從理論上給出了證明子句集不可滿足性的可行性及方法，但在計(jì)算機(jī)上實(shí)現(xiàn)其證明過程卻是很困難的。1965年魯賓遜提出了歸結(jié)原理，使機(jī)器定理證明變?yōu)楝F(xiàn)實(shí)。2.7.3魯賓遜歸結(jié)原理認(rèn)識基礎(chǔ)：若一個(gè)子句集中包含空子項(xiàng)，則這個(gè)子句集一定是不可滿足的?；舅枷耄簷z查子句集S中是否包含空子句。若包含，則S不可滿足；若不包含，就在子句集中選擇合適的子句進(jìn)行歸結(jié)，一旦通過歸結(jié)能推出空子句，就說明子句集S是不可滿足的。2.7.3魯賓遜歸結(jié)原理定義2.22

設(shè)C1與C2是子句集中的任意兩個(gè)子句，如果C1中的文字L1與C2中的文字L2互補(bǔ)，那么從C1和C2中分別消去L1和L2，并將二個(gè)子句中余下的部分析取，構(gòu)成一個(gè)新子句C12，則稱這一過程為歸結(jié)，稱C12為C1和C2的歸結(jié)式，稱C1和C2為C12的親本子句。定理2.4

歸結(jié)式C12是其親本子句C1與C2的邏輯結(jié)論。推論1若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即S1的不可滿足性

?

S的不可滿足性推論2若把C12加入S中，得到新子句集S2，則S與S2在不可滿足的意義上是等價(jià)的，即S2的不可滿足性?S的不可滿足性命題邏輯中的歸結(jié)原理2.7.3魯賓遜歸結(jié)原理由上可知：為要證明子句集S的不可滿足性，只要對其中可進(jìn)行歸結(jié)的子句進(jìn)行歸結(jié)，并把歸結(jié)式加入子句集S，或者用歸結(jié)式替換它的親本子句，然后對新子句集（S1或S2）證明不可滿足性就可以了。命題邏輯中的歸結(jié)原理2.7.3魯賓遜歸結(jié)原理定義2.23設(shè)C1與C2是兩個(gè)沒有相同變元的子句，L1和L2分別是C1和C2中的文字，若σ是L1和?L2的最一般合一，則稱

為C1和C2的二元?dú)w結(jié)式，L1和L2稱為歸結(jié)式上的文字。若子句C中有兩個(gè)或兩個(gè)以上的文字具有最一般合一，則稱Cσ為子句C的因子。如果C是一個(gè)單文字，則稱它為C的單元因子。定義2.24子句C1和C2的歸結(jié)式是下列二元?dú)w結(jié)式之一：1）C1與C2的二元?dú)w結(jié)式；2）C1與C2的因子C2σ2的二元?dú)w結(jié)式；3）C1的因子C1σ1與C2的二元?dú)w結(jié)式；4）C1的因子C1σ1與C2的因子C2σ2的二元?dú)w結(jié)式。謂詞邏輯中的歸結(jié)原理2.7.3魯賓遜歸結(jié)原理應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。設(shè)F為已知前提的公式集，Q為目標(biāo)公式（結(jié)論）用歸結(jié)反演證明Q為真的步驟是：1）否定Q，得到?Q；2）把?Q并入到公式集F中得到{F,?Q}；3）把公式集{F,?Q}化為子句集S；4）應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)并把每次歸結(jié)得到的歸結(jié)式都并入S如此反復(fù)進(jìn)行，若出現(xiàn)了空子句，則停止歸結(jié)，此時(shí)就證明了Q為真。謂詞邏輯中的歸結(jié)原理2.7.4歸結(jié)策略歸結(jié)的關(guān)鍵：找出可進(jìn)行歸結(jié)的一對子句歸結(jié)策略：（1）刪除策略：刪除某些無用的子句來縮小歸結(jié)的范圍（2）限制策略：對參加歸結(jié)的子句進(jìn)行限制，盡可能減小歸結(jié)的盲目性，使其盡快地歸結(jié)出空子句歸結(jié)過程：設(shè)子句集S={C1,C2,C3,C4}1）每個(gè)子句兩兩進(jìn)行比較，若能進(jìn)行歸結(jié)，就求出歸結(jié)式。經(jīng)過本輪比較和歸結(jié)后，得到第一級歸結(jié)式。2）再用S中的子句分別與第一級歸結(jié)式中的子句逐個(gè)比較、歸結(jié)，這樣又會得到第二級歸結(jié)式。3）如此繼續(xù)，直到出現(xiàn)了空子句或不能再繼續(xù)歸結(jié)時(shí)為止。只要子句集是不可滿足的，上述歸結(jié)過程一定會歸結(jié)出空子句而終止。2.7.4歸結(jié)策略把子句集中的無用子句刪除掉，這樣就會縮小尋找范圍，減少比較次數(shù)，從而提高歸結(jié)的效率。（1）純文字刪除法若文字L在子句集中不存在可與之互補(bǔ)的文字?L，則稱其為純文字。在歸結(jié)時(shí)純文字不可能被消去，把它所在的子句刪去不會影響子句集的不可滿足性。（2）重言式刪除法若一個(gè)子句中同時(shí)包含互補(bǔ)文字對，則稱該子句為重言式，如P(x)??P(x)，P(x)?Q(x)??P(x)。重言式的真值恒為真，增加或者刪去重言式不會子句集的不可滿足性。刪除策略2.7.4歸結(jié)策略（3）包孕刪除法設(shè)有子句C1和C2，如果存在一個(gè)代換σ，使得，則稱C1包孕于C2。例如：P(x)包孕于P(a)，P(x)包孕于P(a)?Q(z) σ={a/x}把子句集中包孕的子句刪去后，不會影響子句集的不可滿足性。刪除策略支持集策略是沃斯（Wos）等人在1965年提出的一種歸結(jié)策略。它提出了如下限制：每一次歸結(jié)時(shí)，親本子句中至少應(yīng)有一個(gè)是由目標(biāo)公式的否定所得到的子句或者是它們的后裔?？梢宰C明，支持集策略是完備的，即若子句集是不可滿足的，則由支持集策略一定可以歸結(jié)出空子句。支持集策略2.7.4歸結(jié)策略該歸結(jié)策略提出了如下限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是初始子句集中的子句。線性輸入策略單文字子句策略要求參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是單文字子句，它有較高的歸結(jié)效率。但是，這種歸結(jié)策略是不完備的。當(dāng)初始子句集中不包含單文字子句時(shí)，歸結(jié)就無法進(jìn)行。單文字子句策略當(dāng)兩個(gè)子句滿足下述兩個(gè)條件中的任意一個(gè)就可進(jìn)行歸結(jié)：C1與C2中至少有一個(gè)是初始子句集中的子句。若都不是初始子句集中的子句，則一個(gè)應(yīng)是另一個(gè)的祖先。（C1是C2與別的子句歸結(jié)后得到的歸結(jié)式，則C2為C1的祖先）祖先過濾形策略2.7.5歸結(jié)演繹推理的特點(diǎn)（1）提供了一種簡單易行的方法實(shí)現(xiàn)問題的證明和求解；（2）形式單一，處理規(guī)則十分簡單；（3）可用來進(jìn)行機(jī)械化推理。優(yōu)點(diǎn)（1）用子句形式表示問題，不便于閱讀與理解；（2）子句是一種低效率的表達(dá)式，將公式標(biāo)準(zhǔn)化為高度統(tǒng)一的子句集，有可能丟失一些重要的控制信息。例：(?A??B)→C

(?A??C)→B

(?B??C)→A

?A→(B?C)?B→(A?C)?C→(A?B)將以上公式化為子句后，均為A?B?C。存在的問題本章提綱2.6自然演繹推理2.7歸結(jié)演繹推理2.8與/或形演繹推理2.10證據(jù)理論2.9主觀貝葉斯推理2.11語義網(wǎng)絡(luò)表示法2.8.1與/或形正向演繹推理與/或形正向演繹推理要求已知事實(shí)用不含蘊(yùn)含符號“→”的與/或形表示。把一個(gè)公式化為與/或形的步驟如下：1）利用P→Q??P?Q消去公式中的“→”；2）利用德·摩根律及量詞轉(zhuǎn)換律把“?”移到緊靠謂詞的位置上；3）重新命名變元名，使不同量詞約束的變元有不同的名字；4）引Skolem函數(shù)消去存在量詞；5）消去全稱量詞，且使各主要合取式中的變元不同名。事實(shí)表達(dá)式的與/或形變換及其樹形表示2.8.1與/或形正向演繹推理事實(shí)表達(dá)式的與/或形變換及其樹形表示例：(?x)(?y){Q(y,x)??[(R(y)?P(y))?S(x,y)]}進(jìn)行轉(zhuǎn)化后得到Q(z,a)?{[?R(y)??P(y)]??S(a,y)}樹形表示如下圖：2.8.1與/或形正向演繹推理F規(guī)則的表示形式在與/或形正向演繹推理中，通常要求F規(guī)則具有如下形式：L→W其中，L為單文字，W為與/或形。當(dāng)領(lǐng)域知識的表示形式不是所要求的形式時(shí)，變換步驟與公式化為與/或形類似：1）暫時(shí)消去蘊(yùn)含符號“→”；2）把“?”移到緊靠謂詞的位置上；3）引入Skolem函數(shù)消去存在量詞；4）消去全稱量詞；5）恢復(fù)為蘊(yùn)含式。2.8.1與/或形正向演繹推理目標(biāo)公式的表示形式在與/或形正向演繹推理中，要求目標(biāo)公式用子句表示，否則就需要化成子句形式，轉(zhuǎn)化方法如上節(jié)所述。推理過程1）首先用與/或樹把已知事實(shí)表示出來；2）用F規(guī)則的左部和與/或樹的葉節(jié)點(diǎn)進(jìn)行匹配并將匹配成功的F規(guī)則加入到與/或樹中；3）重復(fù)第2）步，直到產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)作為終止節(jié)點(diǎn)的解圖為止。2.8.2與/或形逆向演繹推理與/或形逆向演繹推理是從待證明的問題（目標(biāo)）出發(fā)，通過逆向地使用蘊(yùn)含式（B規(guī)則）進(jìn)行演繹推理，直到得到包含已知事實(shí)的終止條件為止。目標(biāo)公式的與/或形變換及其樹形表示變換過程：與正向演繹推理中對已知事實(shí)的變換相似不同點(diǎn)：用存在量詞約束的變元的Skolem函數(shù)替換由全稱量詞約束的相應(yīng)變元，并且消去全稱量詞，然后再消去存在量詞B規(guī)則的表示形式：W→L W為任一與/或形公式；L為文字。已知事實(shí)的表示形式：要求已知事實(shí)是文字的合取式，形如F1

?F2?…?Fn。在問題求解中，由于每個(gè)Fi（i=1，2，…，n）都可單獨(dú)起作用，可把上面公式表示為事實(shí)的集合：{F1,F2,…Fn}。2.8.2與/或形逆向演繹推理應(yīng)用B規(guī)則進(jìn)行逆向演繹推理的目的是求解問題，當(dāng)從目標(biāo)公式的與/或樹出發(fā)，通過運(yùn)用B規(guī)則最終得到了某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖時(shí)，推理就可成功結(jié)束，其推理過程為：1）首先用與/或樹把目標(biāo)公式表示出來；2）用B規(guī)則的右部和與/或樹的葉節(jié)點(diǎn)進(jìn)行匹配，并將匹配成功的B規(guī)則加入到與/或樹中；3）重復(fù)進(jìn)行第2）步，直到產(chǎn)生某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖為止。推理過程2.8.3與/或形雙向演繹推理與/或形正向演繹推理要求目標(biāo)公式是文字的析取式，與/或形逆向演繹推理要求事實(shí)公式為文字的合取式，都有一定的局限性。與/或形雙向演繹推理由表示目標(biāo)及表示已知事實(shí)的兩個(gè)與/或樹結(jié)構(gòu)組成，分別由正向演繹的F規(guī)則及逆向演繹的B規(guī)則進(jìn)行操作，并且仍然限制F規(guī)則為單文字的左部，B規(guī)則為單文字的右部。雙向演繹推理的難點(diǎn)在于終止條件，因?yàn)榉謩e從正、逆兩個(gè)方向進(jìn)行推理，其與/或樹分別向著對方擴(kuò)展，只有當(dāng)它們對應(yīng)的葉節(jié)點(diǎn)都可合一時(shí)，推理才能結(jié)束，其時(shí)機(jī)與判斷都難于掌握。2.8.4與/或形演繹推理的特點(diǎn)不必把公式化為子句集保留了連接詞“→”，可直觀地表達(dá)出因果關(guān)系，比較自然優(yōu)點(diǎn)正反向“接頭”的處理比較困難存在的問題本章提綱2.6自然演繹推理2.7歸結(jié)演繹推理2.8與/或形演繹推理2.10證據(jù)理論2.9主觀貝葉斯推理2.11語義網(wǎng)絡(luò)表示法2.9.1簡單不確定性推理設(shè)有如下產(chǎn)生式規(guī)則：IFETHENH其中，E為前提條件，H為結(jié)論。如果我們在實(shí)踐中經(jīng)大量統(tǒng)計(jì)能得出在E發(fā)生條件下H的條件概率P(H/E)，那么就可把它作為在證據(jù)E出現(xiàn)時(shí)結(jié)論H的確定性程度。對于復(fù)合條件E=E1ANDE2AND…ANDEn，當(dāng)已知條件概率P(H/E1,E2,…En)時(shí)，就可把它作為在證據(jù)E1，E2，…，En出現(xiàn)時(shí)結(jié)論H的確定性程度。經(jīng)典概率方法2.9.1簡單不確定性推理經(jīng)典概率方法要求給出P(H/E)，這在實(shí)際應(yīng)用中是相當(dāng)困難的。由貝葉斯定理，若A1，A2，…，An是彼此獨(dú)立的事件，則有：

逆概率方法用前提條件E代替B，用Hi代替公式中的Ai，就得到

i=1,2,…,n

i=1,2,…,n優(yōu)點(diǎn)：有較強(qiáng)的理論背景和良好的數(shù)學(xué)特性；用P(E/Hi)代替P(Hi/E)；缺點(diǎn)：要求給出P(Hi)及P(E/Hi)；應(yīng)用條件很嚴(yán)格，要求各事件互相獨(dú)立。2.9.2知識不確定性的表示在主觀貝葉斯方法中，知識是用產(chǎn)生式規(guī)則表示的：

IFETHEN(LS，LN)H(P(H))其中，E是該條知識的前提條件；H是結(jié)論，P(H)是H的先驗(yàn)概率；LS稱為充分性量度，用于指出E對H的支持程度，取值范圍為[0，+∞)，其值由領(lǐng)域?qū)＜医o出：LN稱為必要性量度，用于指出E對H的支持程度，即E對H為真的必要性程度，取值范圍為[0，+∞)，其值也由領(lǐng)域?qū)＜医o出：2.9.3證據(jù)不確定性的表示在主觀貝葉斯方法中，證據(jù)的不確定性也是用概率表示的。在PROSPECTOR中引進(jìn)了可信度的概念，可信度C(E/S)與概率P(E/S)的對應(yīng)關(guān)系如下：C(E/S)=-5，表示在觀察S下證據(jù)E肯定不存在，即P(E/S)=0。C(E/S)=0，表示S與E無關(guān)，即P(E/S)=P(E)。C(E/S)=5，表示在觀察S下證據(jù)E肯定存在，即P(E/S)=1。2.9.4組合證據(jù)不確定性的算法當(dāng)組合證據(jù)是多個(gè)單一證據(jù)的合取時(shí)，即E=E1ANDE2AND…ANDEn如果已知P(E1/S)，P(E2/S)，…，P(En/S)，則P(E/S)=min{P(E1/S),P(E2/S),…,P(En/S)}當(dāng)組合證據(jù)是多個(gè)單一證據(jù)的析取時(shí)，即E=E1ORE2OR…OREn如果已知P(E1/S)，P(E2/S)，…，P(En/S)，則P(E/S)=max{P(E1/S),P(E2/S),…,P(En/S)}對于“非”運(yùn)算，用下式計(jì)算：P(?E/S)=1-P(E/S)2.9.5不確定性的傳遞算法主觀貝葉斯方法推理的任務(wù)就是根據(jù)證據(jù)E的概率P(E)及LS，LN的值，把H的先驗(yàn)概率P(H)更新為后驗(yàn)概率P(H/E)或P(H/?E)。即證據(jù)肯定存在的情況在證據(jù)肯定存在時(shí)，P(E)=P(E/S)=1。充分性量度LS的意義：當(dāng)LS=1時(shí)，E與H無關(guān)。當(dāng)LS<1時(shí)，證據(jù)E的存在將導(dǎo)致H為真的可能性下降。當(dāng)LS=0時(shí)，證據(jù)E的存在，將使H為假。當(dāng)LS>1時(shí)，O(H/E)>O(H)，P(H/E)>P(H)；LS越大，P(H/E)就越大，E對H為真的支持越強(qiáng)。2.9.5不確定性的傳遞算法證據(jù)肯定不存在的情況在證據(jù)肯定不存在時(shí)，P(E)=P(E/S)=0，P(?E)=1。必要性量度LN的意義：當(dāng)LN>1時(shí)，由于證據(jù)E不存在，將增大結(jié)論H為真的概率。當(dāng)LN=1時(shí)，?E與H無關(guān)。當(dāng)LN<1時(shí)，由于證據(jù)E不存在，將使H為真的可能性下降。當(dāng)LN=0時(shí)，由于證據(jù)E不存在，將導(dǎo)致H為假。由于E和?E不可能同時(shí)支持H或同時(shí)反對H，所以在一條知識中的LS和LN一般不應(yīng)該出現(xiàn)如下情況中的任何一種：1）LS>1，LN>12）LS<1，LN<12.9.5不確定性的傳遞算法證據(jù)不確定的情況P(E/S)=1，即證據(jù)肯定存在的情況。P(E/S)=0，即證據(jù)肯定不存在的情況。P(E/S)=P(E)，表示E與S無關(guān)。2.9.5不確定性的傳遞算法證據(jù)不確定的情況P(E/S)為其它值時(shí)，通過分段線性插值可得：EH公式（UED公式）：CP公式：2.9.6主觀貝葉斯推理的特點(diǎn)優(yōu)點(diǎn)（1）公式大多在概率論的基礎(chǔ)上推導(dǎo)而來，具有堅(jiān)實(shí)的理論基礎(chǔ)。（2）LS及LN是由領(lǐng)域?qū)＜腋鶕?jù)實(shí)踐經(jīng)驗(yàn)給出的，避免了大量的數(shù)據(jù)統(tǒng)計(jì)工作。（3）既用LS指出了證據(jù)E對結(jié)論H的支持程度，又用LN指出了E對H的必要性程度，比較全面地反映了證據(jù)與結(jié)論間的因果關(guān)系。（4）給出了在證據(jù)肯定存在、肯定不存在以及證據(jù)不確定情況下更新先驗(yàn)概率為后驗(yàn)概率的方法。實(shí)現(xiàn)了不確定性的逐級傳遞。缺點(diǎn)（1）要求在給出知識時(shí)，同時(shí)給出H的先驗(yàn)概率P(H)，這是比較困難的。（2）貝葉斯定理中關(guān)于事件間獨(dú)立性的要求使主觀貝葉斯方法的應(yīng)用受到了限制。本章提綱2.6自然演繹推理2.7歸結(jié)演繹推理2.8與/或形演繹推理2.10證據(jù)理論2.9主觀貝葉斯推理2.11語義網(wǎng)絡(luò)表示法2.10.1證據(jù)理論證據(jù)理論是用集合表示命題。樣本空間：設(shè)D是變量x所有可能取值的集合，且D中的元素是互斥的，在任一時(shí)刻x都取且只能取D中的某一個(gè)元素為值，則稱D為x的樣本空間。概率分配函數(shù)設(shè)D為樣本空間，領(lǐng)域內(nèi)的命題都用D的子集表示，則概率分配函數(shù)定義如下：定義2.25

設(shè)函數(shù)M:2D→[0,1]，且滿足則稱M是2D上的概率分配函數(shù)，M(A)稱為A的基本概率數(shù)。2.10.1證據(jù)理論說明：概率分配函數(shù)的作用是把D的任意一個(gè)子集A都映射為[0,1]上的一個(gè)數(shù)M(A)。當(dāng)A?D時(shí)，M(A)表示對相應(yīng)命題的精確信任度。當(dāng)A由多個(gè)元素組成時(shí)，M(A)不包括對A的子集的精確信任度，而且也不知道該對它如何進(jìn)行分配。概率分配函數(shù)不是概率。例：設(shè)D={紅,黃,藍(lán)}，M({紅})=0.3，M({黃})=0，M({藍(lán)})=0.1，M({紅,黃})=0.2，M({紅,藍(lán)})=0.2，M({黃,藍(lán)})=0.1，M({紅,黃,藍(lán)})=0.1， M(?)=0。2.10.1證據(jù)理論信任函數(shù)定義2.26

命題的信任函數(shù)Bel:2D→[0,1]，且對所有的A?D其中2D表示D的所有子集。Bel函數(shù)被稱為下限函數(shù)，Bel(A)表示對命題A為真的信任程度。推論：2.10.1證據(jù)理論似然函數(shù)（不可駁斥函數(shù)、上限函數(shù)）定義2.27

似然函數(shù)Pl:2D→[0,1]，且對所有的A?D例：2.10.1證據(jù)理論概率分配函數(shù)的正交和定義2.28

設(shè)M1和M2是兩個(gè)概率分配函數(shù)，則其正交和M=M1⊕M2為其中：如果K≠0，則正交和M也是一個(gè)概率分配函數(shù)；如果K=0，則不存在正交和M，稱M1與M2