第3章 推理技術(shù)1

1、2022-2-2人工智能12022-2-2人工智能23.1 3.1 消解原理消解原理3.2 3.2 規(guī)則演繹系統(tǒng)規(guī)則演繹系統(tǒng)3.3 3.3 產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)3.4 3.4 基于概率的推理基于概率的推理3.5 3.5 可信度方法可信度方法3.6 3.6 證據(jù)理論證據(jù)理論3.7 3.7 模糊推理模糊推理3.8 3.8 非單調(diào)推理非單調(diào)推理本章主要內(nèi)容：2022-2-2人工智能3 上一章中我們討論了一些簡(jiǎn)單搜索的基本原理。但上一章中我們討論了一些簡(jiǎn)單搜索的基本原理。但對(duì)于許多比較復(fù)雜的系統(tǒng)和問(wèn)題，如果采用上一章討論對(duì)于許多比較復(fù)雜的系統(tǒng)和問(wèn)題，如果采用上一章討論過(guò)的搜索方法，那么很難甚至無(wú)法使問(wèn)

2、題獲得解決的。過(guò)的搜索方法，那么很難甚至無(wú)法使問(wèn)題獲得解決的。需要應(yīng)用一些更先進(jìn)的推理技術(shù)和系統(tǒng)求解這種比較復(fù)需要應(yīng)用一些更先進(jìn)的推理技術(shù)和系統(tǒng)求解這種比較復(fù)雜的問(wèn)題。雜的問(wèn)題。 所謂推理就是按某種策略由已知判斷推出另一判斷的所謂推理就是按某種策略由已知判斷推出另一判斷的思維過(guò)程。一般來(lái)說(shuō)，推理都包括兩種判斷：一種是已思維過(guò)程。一般來(lái)說(shuō)，推理都包括兩種判斷：一種是已知的判斷，包括已知的知識(shí)和已知事實(shí)；另一種是由已知的判斷，包括已知的知識(shí)和已知事實(shí)；另一種是由已知判斷推出的新判斷，即推理的結(jié)論。知判斷推出的新判斷，即推理的結(jié)論。 下面我們首先討論一下與推理相關(guān)的一些概念。下面我們首先討論一下與推

3、理相關(guān)的一些概念。2022-2-2人工智能4推理方式及其分類(lèi)推理方式及其分類(lèi)1. 演繹推理、歸納推理、默認(rèn)推理演繹推理：從一般到特殊。例如三段論。歸納推理：從個(gè)體到一般。默認(rèn)推理：缺省推理，在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。2. 確定性、不確定性推理3. 單調(diào)性、非單調(diào)推理推出的結(jié)論是否單調(diào)增加。4. 啟發(fā)式、非啟發(fā)式推理所謂啟發(fā)性知識(shí)是指與問(wèn)題有關(guān)且能加快推理進(jìn)程、求得問(wèn)題最優(yōu)解的知識(shí)。5. 基于知識(shí)的推理、統(tǒng)計(jì)推理、直覺(jué)推理從方法論的角度劃分。2022-2-2人工智能5推理的控制策略推理的控制策略n推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制

4、策略。1.、正向推理 正向推理的基本思想是：從用戶提供的初始已知事實(shí)出發(fā)，在知識(shí)庫(kù)KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用知識(shí)集KS，然后按某種沖突消解策略從KS中選出一條知識(shí)進(jìn)行推理，并將推出的新事實(shí)加入到數(shù)據(jù)庫(kù)中作為下一步推理的已知事實(shí)。如此重復(fù)進(jìn)行這一過(guò)程，直到求得了所要求的解或者知識(shí)庫(kù)中再無(wú)可使用的知識(shí)為止。2、 逆向推理 逆向推理的基本思想是：首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明原假設(shè)是成立的；若無(wú)論如何都找不到所需要的證據(jù)，則說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的假設(shè)。2022-2-2人工智能6推理的控制策略（推理的控制策略（2 2）3. 混合推理

5、 先正向后逆向推理 先逆向后正向推理4. 雙向推理 正向推理與逆向推理同時(shí)進(jìn)行，且在推理過(guò)程中的某一步上“碰頭”。5. 求解策略 只求一個(gè)解，還是求所有解以及最優(yōu)解。6. 限制策略 限制推理的深度、寬度、時(shí)間、空間等等。2022-2-2人工智能7沖突消解策略沖突消解策略n沖突：多個(gè)知識(shí)都匹配成功。n在產(chǎn)生式系統(tǒng)中對(duì)于正向推理：q多條產(chǎn)生式前件都與已知事實(shí)匹配成功q多組不同事實(shí)都與同一規(guī)則前件匹配成功n對(duì)于逆向推理：q多條規(guī)則后件都和同一個(gè)假設(shè)匹配成功q多條規(guī)則后件可與多個(gè)假設(shè)匹配成功n沖突消解的基本思想都是對(duì)知識(shí)進(jìn)行排序。2022-2-2人工智能8幾種沖突消解策略幾種沖突消解策略w按針對(duì)性排序

6、前件中條件詳細(xì)(多)的規(guī)則先推。w按已知事實(shí)的新鮮性排序新鮮事實(shí)(剛得到的局部結(jié)論)越多(越新鮮)的規(guī)則先推。w按匹配度排序在不確定性匹配中，計(jì)算兩個(gè)知識(shí)模式的相似度(匹配度)，并對(duì)其排序，相似度高的規(guī)則先推。w按領(lǐng)域問(wèn)題特點(diǎn)排序w按上下文限制排序把規(guī)則按照下上文分組，并只能選取組中的規(guī)則。w按冗余限制排序冗余知識(shí)越少的規(guī)則先推。w按條件個(gè)數(shù)排序條件少的規(guī)則先推。2022-2-2人工智能9n所謂模式匹配是指對(duì)兩個(gè)知識(shí)模式(例如兩個(gè)謂詞公式、框架片斷、語(yǔ)義網(wǎng)絡(luò)片斷)的比較與耦合，及檢查這兩個(gè)知識(shí)模式是否完全一致或者近似一致。n按匹配時(shí)兩個(gè)知識(shí)模式的相似程度，模式匹配可分為確定性匹配與不確定性匹配

7、。n確定性匹配是指兩個(gè)知識(shí)模式完全一致，或者經(jīng)過(guò)變量代換后變得完全一致。例如：P1:father(李四，李小四) and man(李小四)P2:father(x,y) and man(y)n不確定性匹配是指兩個(gè)知識(shí)模式不完全一致，但是它們的相似程度又在規(guī)定的限度內(nèi)。 模式匹配模式匹配2022-2-2人工智能101、變量代換定義 代換是一個(gè)形如t1/x1,t2/x2,tn/xn的有限集合。 其中是t1,t2,tn項(xiàng)； x1,x2,xn是互不相同的變?cè)?；ti/xi表示用ti代換xi，不允許ti與xi相同，也不允許變?cè)獂i循環(huán)地出現(xiàn)在另一個(gè)tj中。例如：a/x,f(b)/y,w/z是一個(gè)代換g(y)

8、/x,f(x)/y不是代換g(a)/x,f(x)/y是代換2022-2-2人工智能112、代換的復(fù)合定義： 設(shè)= t1/x1,t2/x2,tn/xn= u1/y1,u2/y2,um/ym是兩個(gè)代換，則此兩個(gè)代換的復(fù)合也是一個(gè)代換，它是從t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym 中刪去如下兩種元素： ti/xi當(dāng)ti=xi ui/yi當(dāng)yix1,x2,xn 后剩下的元素所構(gòu)成的集合，記為 。n注： ti表示對(duì)ti運(yùn)用代換。實(shí)際上就是對(duì)一個(gè)公式先運(yùn)用代換，然后再運(yùn)用代換。2022-2-2人工智能123、代換的例子例如，設(shè)有代換= f(y)/x,z/y= a/x,b/y

9、,y/z則=f(y)/x,z/y,a/x,b/y,y/z=f(b)/x,y/y,a/x,b/y,y/z=f(b)/x,y/z2022-2-2人工智能134、公式集的合一定義： 設(shè)有公式集F=F1,F2,Fn，若存在一個(gè)代換使得 F1=F2=Fn則稱(chēng)為公式集F的一個(gè)合一，且稱(chēng)F1,F2,Fn是可合一的。n例如，設(shè)有公式集F=P(x,y,f(y),P(a,g(x),z) 則下式是它的一個(gè)合一：=a/x,g(a)/y,f(g(a)/zn一個(gè)公式集的合一一般不唯一。定義： 設(shè)是公式集F的一個(gè)合一，如果對(duì)任一個(gè)合一都存在一個(gè)代換，使得=，則稱(chēng)是一個(gè)最一般的合一。n最一般合一是唯一的。2022-2-2人工

10、智能14求取最一般合一n差異集：兩個(gè)公式中相同位置處不同符號(hào)的集合。例如：F1:P(x,y,z), F2:P(x,f(a),h(b) 則D1=y,f(a), D2=z,h(b)求取最一般合一的算法：w令k=0,Fk=F, k=。 是空代換。w若Fk只含一個(gè)表達(dá)式，則算法停止，k就是最一般合一。w找出Fk的差異集Dk。w若Dk中存在元素xk和tk，其中xk是變?cè)?，tk是項(xiàng)，且xk不在tk中出現(xiàn)，則置：K+1=ktk/xk Fk+1=Fktk/xk k=k+1然后轉(zhuǎn)(2)。若不存在這樣的xk和tk則算法停止。1.算法終止，F(xiàn)的最一般合一不存在。2022-2-2人工智能15求取最一般合一的例子例如，

11、設(shè)F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。w令F0=F, 0=。 F0中有兩個(gè)表達(dá)式，所以0不是最一般合一。w差異集D0=a,z 。w1=0a/z=a/zwF1=P(a,x,f(g(y),P(a,f(a),f(u) 。wD1=x,f(a) 。w2=1f(a)/x=a/z,f(a)/xwF2=F1f(a)/x=P(a,f(a),f(g(y),P(a,f(a),f(u) 。wD2=g(y),u 。w3=2g(y)/u=a/z,f(a)/x,g(y)/uwF3=F2g(y)/u=P(a,f(a),f(g(y),P(a,f(a),f(g(y) 。因?yàn)镕3中只有一個(gè)表達(dá)式

12、，所以就是最一般合一，即1.a/z,f(a)/x,g(y)/u2022-2-2人工智能16 消解原理消解原理是針對(duì)謂詞邏輯表示的問(wèn)題進(jìn)行求解方法，也叫是針對(duì)謂詞邏輯表示的問(wèn)題進(jìn)行求解方法，也叫做做歸結(jié)原理歸結(jié)原理。主要內(nèi)容包括子句集的求取、消解推理的規(guī)則。主要內(nèi)容包括子句集的求取、消解推理的規(guī)則和消解反演問(wèn)題求解方法。和消解反演問(wèn)題求解方法。消解原理的基礎(chǔ)知識(shí)：消解原理的基礎(chǔ)知識(shí)：u謂詞公式、某些推理規(guī)則以及置換合一等概念。謂詞公式、某些推理規(guī)則以及置換合一等概念。u在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱(chēng)為在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱(chēng)為文字文字。u任何文字的析取式稱(chēng)為任何文字的析

13、取式稱(chēng)為子句子句。 例如：例如： P(x)Q(x), P(x,f(x)Q(x,g(x)u不包含任何文字的子句稱(chēng)為不包含任何文字的子句稱(chēng)為空子句空子句。u空子句不含有文字，不能被任何解釋滿足，所以空子句是永空子句不含有文字，不能被任何解釋滿足，所以空子句是永假的，假的，不可滿足不可滿足的。的。2022-2-2人工智能173.1.1 3.1.1 化為子句集化為子句集 (1)(1)消去蘊(yùn)涵符號(hào)：只應(yīng)用消去蘊(yùn)涵符號(hào)：只應(yīng)用和符號(hào)，以和符號(hào)，以ABAB替換替換A=BA=B。 例如：例如：(2)(2)減少否定符號(hào)的轄域：每個(gè)否定符號(hào)最多只用到一減少否定符號(hào)的轄域：每個(gè)否定符號(hào)最多只用到一個(gè)謂詞符號(hào)上，并反

14、復(fù)應(yīng)用狄個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用狄摩根定律。例如：上摩根定律。例如：上式經(jīng)等價(jià)變換后式經(jīng)等價(jià)變換后()() ( , )()( ( , )( , )xy P x yy Q x yR x y ()( () ( , )()( , )( , )xy P x yyQ x yR x y ()()( , ) ()( ( , )( , )xyP x yy Q x yR x y 在說(shuō)明消解過(guò)程之前在說(shuō)明消解過(guò)程之前, ,我們首先說(shuō)明任一謂詞演算公式可我們首先說(shuō)明任一謂詞演算公式可以化成一個(gè)子句集。其變換過(guò)程由下列九個(gè)步驟組成：以化成一個(gè)子句集。其變換過(guò)程由下列九個(gè)步驟組成：2022-2-2人工智能18(3)(3

15、)對(duì)變量標(biāo)準(zhǔn)化對(duì)變量標(biāo)準(zhǔn)化 ：使不同量詞約束的變?cè)胁煌拿?，：使不同量詞約束的變?cè)胁煌拿?，通過(guò)變量更名來(lái)完成。例如，上式經(jīng)變換后通過(guò)變量更名來(lái)完成。例如，上式經(jīng)變換后()()( , ) ()( ( , )( , )xyP x yz Q x zR x z (4)(4)消去存在量詞：分兩種情況消去存在量詞：分兩種情況 a a）存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi)，則只要用一個(gè)新）存在量詞不出現(xiàn)在全稱(chēng)量詞的轄域內(nèi)，則只要用一個(gè)新的個(gè)體常量替換受該量詞約束的變?cè)５膫€(gè)體常量替換受該量詞約束的變?cè)?b b）存在量詞位于一個(gè)或者多個(gè)全稱(chēng)量詞的轄域內(nèi)，此時(shí)要用）存在量詞位于一個(gè)或者多個(gè)全稱(chēng)量詞的轄域

16、內(nèi)，此時(shí)要用SkolemSkolem函數(shù)函數(shù)f(x1,x2,xn)f(x1,x2,xn)替換受該存在量詞約束的變?cè)?。替換受該存在量詞約束的變?cè)Ｉ鲜街写嬖诹吭~上式中存在量詞( ( y)y)及及( ( z)z)都位于都位于( ( x)x)的轄域內(nèi)，所以需要的轄域內(nèi)，所以需要用用SkolemSkolem函數(shù)替換，設(shè)替換函數(shù)替換，設(shè)替換y y和和z z的的SkolemSkolem函數(shù)分別是函數(shù)分別是f(x)f(x)和和g(x)g(x)，則替換后得到，則替換后得到()( , ( ) ( ( , ( )( , ( )xP x f xQ x g xR x g x3.1.1 3.1.1 化為子句集（化為子句

17、集（2 2） 2022-2-2人工智能19(5)(5)化為前束形化為前束形 ：把所有全稱(chēng)量詞移到公式的左邊，并使：把所有全稱(chēng)量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。所得公式稱(chēng)為前束形。所得公式稱(chēng)為前束形。 3.1.1 3.1.1 化為子句集（化為子句集（3 3） (6)(6)化為合取范式化為合取范式 ：任何公式都可寫(xiě)成由一些謂詞和：任何公式都可寫(xiě)成由一些謂詞和( (或或) )謂詞的否定的析取的有限集組成的合取式。這種公式謂詞的否定的析取的有限集組成的合取式。這種公式叫做合取范式。我們可以反復(fù)應(yīng)用分配律。把任一公叫做合取

18、范式。我們可以反復(fù)應(yīng)用分配律。把任一公式化成合取范式。前面的公式經(jīng)變換得式化成合取范式。前面的公式經(jīng)變換得 ()( , ( )( , ( ) ( , ( )( , ( )xP x f xQ x g xP x f xR x g x (7)(7) 消去全稱(chēng)量詞消去全稱(chēng)量詞 ：到了這一步，所有余下的量詞均被：到了這一步，所有余下的量詞均被全稱(chēng)量詞量化了。同時(shí)全稱(chēng)量詞的次序也不重要了。全稱(chēng)量詞量化了。同時(shí)全稱(chēng)量詞的次序也不重要了。因此，我們可以消消去全稱(chēng)量詞。因此，我們可以消消去全稱(chēng)量詞。 2022-2-2人工智能20(8)(8)消去合取詞：用消去合取詞：用“，”代替符號(hào)代替符號(hào)，最后得到一個(gè)有，最后

19、得到一個(gè)有限集，其中每個(gè)公式是文字的析取。任一個(gè)只由文字限集，其中每個(gè)公式是文字的析取。任一個(gè)只由文字的析取構(gòu)成的合式公式叫做一個(gè)子句。例如，上式經(jīng)的析取構(gòu)成的合式公式叫做一個(gè)子句。例如，上式經(jīng)變換后得變換后得3.1.1 3.1.1 化為子句集（化為子句集（4 4） (9)(9)更換變量名稱(chēng)：使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的更換變量名稱(chēng)：使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中子句中。上式在更改變量名后，可以得到子句集：上式在更改變量名后，可以得到子句集：)(,()(,(,)(,()(,(xgxRxfxPxgxQxfxP)(,()(,(,)(,()(,(ygyRyfyPxgxQxfxP2022-

20、2-2人工智能21定義：定義：設(shè)設(shè)L1L1為任一原子公式，為任一原子公式，L2L2為另一原子公式，且具為另一原子公式，且具有相同的謂詞符號(hào)，但一般具有不同的變量。已知兩有相同的謂詞符號(hào)，但一般具有不同的變量。已知兩子句子句L1L1和和L2L2，如果，如果L1L1和和L2L2具有最一般合一具有最一般合一者者，那么通過(guò)消解可以從這兩個(gè)父輩子句推導(dǎo)出一，那么通過(guò)消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句個(gè)新子句()()。這個(gè)新子句叫做。這個(gè)新子句叫做消解式消解式。它是。它是由取這兩個(gè)子句的析取，然后消去互補(bǔ)對(duì)而得到的。由取這兩個(gè)子句的析取，然后消去互補(bǔ)對(duì)而得到的。如：如： 3.1.2 3.1.2 消解

21、推理規(guī)則消解推理規(guī)則 a)假言推理假言推理b)合并合并2022-2-2人工智能22c)重言式重言式d)重言式重言式e)三段論三段論f)空子句（矛盾）空子句（矛盾） 從以上各例可見(jiàn)，消解可以合并幾個(gè)運(yùn)算為一簡(jiǎn)從以上各例可見(jiàn)，消解可以合并幾個(gè)運(yùn)算為一簡(jiǎn)單的推理規(guī)則。單的推理規(guī)則。 2022-2-2人工智能23定理定理 若C12是子句C1與C2的消解式，則C12是C1與C2邏輯結(jié)論。證明：設(shè) C1=LC1, C2=LC2, 則C12=C1C2111222()()1212()()12121212121212CCLCLCLCLCCCCLLCCLLCCCCCCCCCCC 由 假 言 三 段 論消解推理規(guī)則

22、的正確性消解推理規(guī)則的正確性 2022-2-2人工智能24推論推論1 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的消解式。若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即 S1的不可滿足性S的不可滿足性推論推論2 設(shè)C1與C2是子句集S中的兩個(gè)子句，C12是它們的消解式。若把C12加入S中得到新子句集S2，則S與S2在不可滿足的意義上是等價(jià)的，即S2的不可滿足性S的不可滿足性?xún)蓚€(gè)推論兩個(gè)推論 2022-2-2人工智能25 為了對(duì)含有變量的子句使用消解規(guī)則，必須找到一為了對(duì)含有變量的子句使用消解規(guī)則，必須找到一個(gè)置換，作用于父輩子句使其含有互

23、補(bǔ)文字。個(gè)置換，作用于父輩子句使其含有互補(bǔ)文字。 消解兩個(gè)子句時(shí)，可能有一個(gè)以上的消解式。不過(guò)，在消解兩個(gè)子句時(shí)，可能有一個(gè)以上的消解式。不過(guò)，在任何情況下，它們最多具有有限個(gè)消解式。作為例子，我們?nèi)魏吻闆r下，它們最多具有有限個(gè)消解式。作為例子，我們考慮兩個(gè)子句考慮兩個(gè)子句: : Py,f(y) 進(jìn)一步消解得消解式為: Px,f(A)Px,f(y)Py,f(A) 那么得到消解式: Q(y)，Q(z) 如果取 Pz,f(y)Q(z)Q(y) 那么得到消解式: Px,f(A)，Pz,f(A) 如果取 Px,f(A)Px,f(y)Q(y) 和 Pz,f(A)Q(z)2022-2-2人工智能261 基

24、本思想基本思想 把要解決的問(wèn)題作為一個(gè)要證明的命題，其目標(biāo)公式被否定并化把要解決的問(wèn)題作為一個(gè)要證明的命題，其目標(biāo)公式被否定并化成子句形，然后添加到命題公式集中去成子句形，然后添加到命題公式集中去, ,把消解反演系統(tǒng)應(yīng)用于聯(lián)合把消解反演系統(tǒng)應(yīng)用于聯(lián)合集，并推導(dǎo)出一個(gè)空子句集，并推導(dǎo)出一個(gè)空子句(NIL)(NIL)，產(chǎn)生一個(gè)矛盾，這說(shuō)明目標(biāo)公式的，產(chǎn)生一個(gè)矛盾，這說(shuō)明目標(biāo)公式的否定式不成立，即有目標(biāo)公式成立，定理得證，問(wèn)題得到解決。這與否定式不成立，即有目標(biāo)公式成立，定理得證，問(wèn)題得到解決。這與數(shù)學(xué)中反證法的思想十分相似。數(shù)學(xué)中反證法的思想十分相似。 2 2 消解反演消解反演給出一個(gè)公式集給出一

25、個(gè)公式集S S和自標(biāo)公式和自標(biāo)公式L L，通過(guò)反證或反演來(lái)求證目標(biāo)公式，通過(guò)反證或反演來(lái)求證目標(biāo)公式L L，其證明步驟如下：，其證明步驟如下： (1) (1)否定否定L L，得，得L L； (2)(2)把把L L添加到添加到S S中去；中去； (3)(3)把新產(chǎn)生的集合把新產(chǎn)生的集合L L，S S化成子句集；化成子句集； (4)(4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句N(xiāo)ILNIL。 3.1.3 3.1.3 消解反演求解過(guò)程消解反演求解過(guò)程 2022-2-2人工智能27(3) 消解反演舉例消解反演舉例 下面舉個(gè)例子來(lái)說(shuō)明消解反演過(guò)程： 前提：

26、每個(gè)儲(chǔ)蓄錢(qián)的人都獲得利息。 結(jié)論：如果沒(méi)有利息，那么就沒(méi)有人去儲(chǔ)蓄錢(qián)。證明：令S(x,y)表示x儲(chǔ)蓄y , M(x)表示“x是錢(qián)”， I(x)表示“x是利息”， E(x,y)表示x獲得y 于是上述命題寫(xiě)成下列形式：結(jié)論：2022-2-2人工智能28用化為子句集方法，可把前提化為下列的子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，f(x)為Skolem函數(shù)。 而結(jié)論的否定可化為： L =I(z),S(a,b),M(b)把 L添加到S中去，得 S=L，S，即： S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x),I(z),S(a,b),

27、M(b)該消解反演可以表示為一棵反演樹(shù)，如下圖所示。 2022-2-2人工智能29(4) 反演求解過(guò)程反演求解過(guò)程用反演樹(shù)求取對(duì)某個(gè)問(wèn)題的答案，其過(guò)程如下：把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。按照反演樹(shù)，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。用根部的子句作為一個(gè)回答語(yǔ)句。 答案求取涉及到把一棵根部有NIL的反演樹(shù)變換為在根部帶有可用作答案的某個(gè)語(yǔ)句的一顆證明樹(shù)。由于變換關(guān)系涉及到把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句變換為一個(gè)重言式，所以被變換的證明樹(shù)就是一棵消解的證明樹(shù)，其在根部的語(yǔ)句在邏輯上遵循公理加上重言式，因而也單獨(dú)地遵循公理。因此被變換的證明樹(shù)本身

28、就證明了求取辦法是正確的。2022-2-2人工智能30下面通過(guò)一個(gè)簡(jiǎn)單的例子說(shuō)明消解反演求解過(guò)程“如果無(wú)論約翰(John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢?” 這個(gè)問(wèn)題說(shuō)明了兩個(gè)事實(shí)，然后提出一個(gè)問(wèn)題，而問(wèn)題的答案大概可從這兩個(gè)事實(shí)推導(dǎo)出。這兩個(gè)事實(shí)可以解釋為下列公式集S：),(),()(xFidoATxJohnATx),(SchoolJohnAT 求解的目標(biāo)為：),()(xFidoATx 如果我們首先證明目標(biāo)公式在邏輯上遵循S，然后尋求一個(gè)存在x的例，那么就能解決“菲多在哪里”的問(wèn)題。關(guān)鍵想法是把問(wèn)題化為一個(gè)包含某個(gè)存在量詞的目標(biāo)公式，使得此存在量詞量

29、化變量表示對(duì)該問(wèn)題的一個(gè)解答。2022-2-2人工智能31對(duì)本例應(yīng)用消解反演求解過(guò)程，我們有：(1)目標(biāo)公式否定的子句形式為 :AT(Fido,x)，把它添加至目標(biāo)公式的否定之否定的子句中去，得到重言式 ：AT(Fido,x)AT(Fido,x)(2) 用反演樹(shù)進(jìn)行消解，并在根部得到子句: AT (Fido，School) (3) 從根部求得答案AT(Ffido，School) 2022-2-2人工智能32 (5) 消解策略消解策略消解的一般過(guò)程：消解的一般過(guò)程：設(shè)子句集S=C1,C2,Cn，則消解的一般過(guò)程是：S內(nèi)任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第一級(jí)歸結(jié)式，記為S1。把S與S

30、1內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第二級(jí)歸結(jié)式，記為S2。S和S1內(nèi)的子句與S2內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱(chēng)為第三級(jí)歸結(jié)式，記為S3。1.如此繼續(xù)，直到出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)為止。2022-2-2人工智能33 可以通過(guò)一些策略來(lái)提高消解推理的效率，這些策略稱(chēng)為消解策略。策略可分為兩大類(lèi)：1、刪除策略：刪除某些無(wú)用的子句來(lái)縮小歸結(jié)的范圍。2、限制策略：通過(guò)對(duì)參加歸結(jié)的子句進(jìn)行種種限制，盡可能減小歸結(jié)的盲目性，使其盡快地歸結(jié)出空子句。2022-2-2人工智能34n純文字刪除法 如果某文字L在子句集中不存在可與之互補(bǔ)的文字L，則稱(chēng)該文字為純文字。包含純文

31、字的子句可以刪除。n重言式刪除法 如果一個(gè)子句中同時(shí)包含互補(bǔ)文字對(duì)，則該字句稱(chēng)為重言式。重言式是永遠(yuǎn)為真的子句，可以刪除。n包孕刪除法 設(shè)有子句C1和C2，如果存在一個(gè)代換，使得： C1C2 ，則稱(chēng)C1包孕于C2。此時(shí)把包孕的子句C2刪除，不會(huì)影響子句集的不可滿足性。刪除策略刪除策略2022-2-2人工智能35n支持集策略 限制：每一次歸結(jié)時(shí)，親本子句中至少有一個(gè)是由目標(biāo)公式的否定所得到的子句，或者是它們的后裔?？梢宰C明，支持集策略是完備的。n線性輸入策略 限制：參加歸結(jié)的兩個(gè)子句中必須至少有一個(gè)是初始子句集中的子句。線性輸入策略是不完備的。n單文字子句策略 限制：參加歸結(jié)的兩個(gè)子句中必須至少

32、有一個(gè)是單文字子句。單文字子句策略是不完備的。n祖先過(guò)濾策略 限制：參加歸結(jié)的子句滿足：(1)C1和C2中至少有一個(gè)是初始子句集中的子句?；?2)C1和C2中一個(gè)是另外一個(gè)的祖先子句。祖先過(guò)濾策略是完備的。限制策略限制策略2022-2-2人工智能36 對(duì)于許多公式來(lái)說(shuō)，子句形是一種低效率的表達(dá)式，因?qū)τ谠S多公式來(lái)說(shuō)，子句形是一種低效率的表達(dá)式，因?yàn)橐恍┲匾畔⒖赡茉谇笕∽泳湫芜^(guò)程中丟失。本節(jié)將研究為一些重要信息可能在求取子句形過(guò)程中丟失。本節(jié)將研究采用易于敘述的采用易于敘述的if-then(if-then(如果如果- -那么那么) )規(guī)則來(lái)求解問(wèn)題。規(guī)則來(lái)求解問(wèn)題。 在所有基于規(guī)則系統(tǒng)中，每個(gè)

33、if可能與某斷言集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱(chēng)為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rule based deduction system)。在這種系統(tǒng)中，通常稱(chēng)每個(gè)if部分為前項(xiàng)，稱(chēng)每個(gè)then部分為后項(xiàng)。 基于規(guī)則的演繹系統(tǒng)和產(chǎn)生式系統(tǒng)，均有正向推理和逆向推理兩種推理方式。2022-2-2人工智能371.事實(shí)表達(dá)式的與或形變換事實(shí)表達(dá)式的與或形變換在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實(shí)表示為非蘊(yùn)涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫(kù)。我們不想把這些事實(shí)化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換

34、為叫做與或形的非蘊(yùn)涵形式。要把一個(gè)公式化為與或形，可采用下列步驟： 3.2.1 3.2.1 規(guī)則正向演繹系統(tǒng)規(guī)則正向演繹系統(tǒng) n利用(W1W2)和(W1W2)的等價(jià)關(guān)系，消去符號(hào)(如果存在該符號(hào)的話)。實(shí)際上，在事實(shí)中間很少有符號(hào)出現(xiàn)，因?yàn)榭砂烟N(yùn)涵式表示為規(guī)則。n用狄摩根定律把否定符號(hào)移進(jìn)括號(hào)內(nèi)，直到每個(gè)否定符號(hào)的轄域最多只含有一個(gè)謂詞為止。n對(duì)所得到的表達(dá)式進(jìn)行Skolem化和前束化。n對(duì)全稱(chēng)量詞轄域內(nèi)的變量進(jìn)行改名和變量標(biāo)準(zhǔn)化，而存在量詞量化變量用Skolem函數(shù)代替。n刪去全稱(chēng)量詞，而任何余下的變量都被認(rèn)為具有全稱(chēng)量化作用。2022-2-2人工智能38例如，有事實(shí)表達(dá)式 對(duì)變量更名標(biāo)準(zhǔn)化

35、，使得同一變量不出現(xiàn)在事實(shí)表達(dá)式的不同主要合取式中。更名后得表達(dá)式： Q(w,A)R(v)P(v)S(A,v) 必須注意到Q(v,A)中的變量v可用新變量w代替，而合取式R(v)P(v)中的變量v卻不可更名，因?yàn)楹笳咭渤霈F(xiàn)在析取式S(A,v)中。把它可化為：Q(v,A)R(v)P(v)S(A,v) ),()()(),()(vuSvPvRuvQvu 與或形表達(dá)式是由符號(hào)和連接的一些文字的子表達(dá)式組成的。呈與或形的表達(dá)式并不是子句形，而是接近于原始表達(dá)式形式，特別是它的子表達(dá)式不是復(fù)合產(chǎn)生的。2022-2-2人工智能392. 事實(shí)表達(dá)式的與或圖表示事實(shí)表達(dá)式的與或圖表示 將上例與或形的事實(shí)表達(dá)式用

36、與或圖來(lái)表示。 表示某個(gè)事實(shí)表達(dá)式的與或圖的葉節(jié)點(diǎn)均由表達(dá)式中的文字來(lái)標(biāo)記。圖中標(biāo)記有整個(gè)事實(shí)表達(dá)式的節(jié)點(diǎn)，稱(chēng)為根節(jié)點(diǎn)，它在圖中沒(méi)有祖先。 注意與或標(biāo)記與普通與或圖的區(qū)別2022-2-2人工智能403. 與或圖的與或圖的F規(guī)則變換規(guī)則變換 把允許用作規(guī)則的公式類(lèi)型限制為下列形式： LW 式中：L是單文字；W為與或形的唯一公式。 把形式為L(zhǎng) W的規(guī)則應(yīng)用到任一個(gè)具有葉節(jié)點(diǎn)n并由文字L標(biāo)記的與或圖上，可以得到一個(gè)新的與或圖。在新的圖上，節(jié)點(diǎn)n由一個(gè)單線連接符接到后繼節(jié)點(diǎn)(也由L標(biāo)記)，它是表示為W的一個(gè)與或圖結(jié)構(gòu)的根節(jié)點(diǎn)。例如，把規(guī)則S =(XY)Z應(yīng)用于圖1中標(biāo)有S的葉節(jié)點(diǎn)上。所得到的新與或圖結(jié)

37、構(gòu)表示于圖2。圖圖1圖圖22022-2-2人工智能41 4. 目標(biāo)公式與終止條件目標(biāo)公式與終止條件 在正向演繹系統(tǒng)中，要求目標(biāo)公式用子句來(lái)表示，即文字的析取形式。可用用文字集表示此目標(biāo)公式 。 當(dāng)正向演繹系統(tǒng)產(chǎn)生一個(gè)含有以目標(biāo)節(jié)點(diǎn)作為終止的解圖時(shí)，此系統(tǒng)就成功地終止。 例如：已知事實(shí)：AB 規(guī)則：A=CD，B=EG 目標(biāo): CG 推理過(guò)程如圖所示。2022-2-2人工智能42 基于規(guī)則的逆向演繹系統(tǒng)，其操作過(guò)程與正向演繹系統(tǒng)相反，即為從目標(biāo)到事實(shí)的操作過(guò)程，從then到if的推理過(guò)程。 1. 目標(biāo)表達(dá)式的與或形式目標(biāo)表達(dá)式的與或形式 逆向演繹系統(tǒng)能夠處理任意形式的目標(biāo)表達(dá)式。首先，采用與變換事

38、實(shí)表達(dá)式同樣的過(guò)程，把目標(biāo)公式化成與或形。即消去蘊(yùn)涵符號(hào)，把否定符號(hào)移進(jìn)括號(hào)內(nèi)，對(duì)全稱(chēng)量詞Skolem化并刪去存在量詞。留在目標(biāo)表達(dá)式與或形中的變量假定都已存在量詞量化。 3.2.2 3.2.2 規(guī)則逆向演繹系統(tǒng)規(guī)則逆向演繹系統(tǒng) 設(shè)目標(biāo)表達(dá)式被化成與或形：P(f(y)Q(f(y),y)P(f(y)S(y) 式中，f(y)為一Skolem函數(shù)。對(duì)目標(biāo)的主要析取式中的變量分離標(biāo)準(zhǔn)化可得 P(f(z)Q(f(y),y)P(f(y)S(y) )()(),()()(ysxPyxQxPxy2022-2-2人工智能43 與或形的目標(biāo)公式也可以表示為與或圖。不過(guò)，與事實(shí)表達(dá)式的與或圖不同的是，對(duì)于目標(biāo)表達(dá)式，

39、與或圖中的k線連接符用來(lái)分開(kāi)合取關(guān)系的子表達(dá)式。 上面所用的目標(biāo)公式的與或圖如圖所示 2022-2-2人工智能44 B規(guī)則是建立在確定的蘊(yùn)涵式基礎(chǔ)上的，正如正向系統(tǒng)的F規(guī)則一樣。不過(guò)，在正向演繹系統(tǒng)中把這些B規(guī)則限制為： W=L 其中，W為任一與或形公式，L為文字，而且蘊(yùn)涵式中任何變量的量詞轄域?yàn)檎麄€(gè)蘊(yùn)涵式。 其次，把B規(guī)則限制為這種形式的蘊(yùn)涵式還可以簡(jiǎn)化匹配，使之不會(huì)引起重大的實(shí)際困難。 此外，可以把像W =(L1L2)這樣的蘊(yùn)涵式化為兩個(gè)規(guī)則W=L1和W= L2。 2. 與或圖的與或圖的B規(guī)則變換規(guī)則變換2022-2-2人工智能45 逆向系統(tǒng)中的事實(shí)表達(dá)式均限制為文字合取形，它可以表示為一

40、個(gè)文字集。 逆向系統(tǒng)成功的終止條件是與或圖包含有某個(gè)終止在事實(shí)節(jié)點(diǎn)上的一致解圖。 3.事實(shí)表示與終止條件事實(shí)表示與終止條件 已知事實(shí)：F1: DOG(FIDO)；狗的名字叫 Fido F2: BARKS(FIDO)；Fido是不叫的 F3: WAGS TAIL(FIDO)；Fido搖尾巴 F4: MEOWS(MYRTLE)；貓咪的名字叫Myrtle 規(guī)則： R1: WAGS TAIL(x1)DOG(x1)= FRIENDLY(x1)； R2: FRIENDLY(x2)BARKS(x2)=AFRAID(y2,x2)； R3: DOG(x3)= ANIMAL(x3)；狗為動(dòng)物 R4: CAT(x4

41、) =ANIMAL(x4)；貓為動(dòng)物 R5: MEOWS(x5) =CAT(x5)；貓咪是貓 問(wèn)題：是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗? 2022-2-2人工智能46用目標(biāo)表達(dá)式表示此問(wèn)題為: CAT(x)DOG(y)AFRAID(x,y) 我們就得到該問(wèn)題的回答語(yǔ)句為： CAT(MYRTLE)DOG(FIDO) AFRAID(MYRTLE,FIDO)2022-2-2人工智能47 正向演繹系統(tǒng)能夠處理任意形式的if表達(dá)式，但被限制在then表達(dá)式為由文字析取組成的一些表達(dá)式。逆向演繹系統(tǒng)能夠處理任意形式的then表達(dá)式，但被限制在if表達(dá)式為文字合取組成的一些表達(dá)式。我們希望能

42、夠構(gòu)成一個(gè)組合的系統(tǒng)，使它具有正向和逆向兩系統(tǒng)的優(yōu)點(diǎn)，以求克服各自的缺點(diǎn)(局限性)。 正向和逆向組合系統(tǒng)是建立在兩個(gè)系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫(kù)由表示目標(biāo)和表示事實(shí)的兩個(gè)與或圖結(jié)構(gòu)組成。這些與或圖最初用來(lái)表示給出的事實(shí)和目標(biāo)的某些表達(dá)式集合，現(xiàn)在這些表達(dá)式的形式不受約束。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來(lái)修正。 組合演繹系統(tǒng)的主要復(fù)雜之處在于其終止條件，終止涉及兩個(gè)圖結(jié)構(gòu)之間的適當(dāng)交接處。 3.2.3 3.2.3 雙向演繹系統(tǒng)雙向演繹系統(tǒng) 2022-2-2人工智能48 產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)(production system)首先是由波斯特首先是由波斯特(P

43、ost)于于1943年提出的產(chǎn)生式規(guī)則年提出的產(chǎn)生式規(guī)則(production rule)而得名的。他們用這種規(guī)則而得名的。他們用這種規(guī)則對(duì)符號(hào)串進(jìn)行置換運(yùn)算。后來(lái)，美國(guó)的紐厄爾和西蒙利用這個(gè)原對(duì)符號(hào)串進(jìn)行置換運(yùn)算。后來(lái)，美國(guó)的紐厄爾和西蒙利用這個(gè)原理建立一個(gè)人類(lèi)的認(rèn)知模型理建立一個(gè)人類(lèi)的認(rèn)知模型(1965年年)。同時(shí)，斯坦福大學(xué)利用產(chǎn)。同時(shí)，斯坦福大學(xué)利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)出第一個(gè)專(zhuān)家系統(tǒng)生式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)出第一個(gè)專(zhuān)家系統(tǒng)DENDRAL。產(chǎn)生式系統(tǒng)用來(lái)描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的產(chǎn)生式系統(tǒng)用來(lái)描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的系統(tǒng)。這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對(duì)的

44、概系統(tǒng)。這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對(duì)的概念。在產(chǎn)生式系統(tǒng)中，論域的知識(shí)分為兩部分：用事實(shí)表示靜態(tài)念。在產(chǎn)生式系統(tǒng)中，論域的知識(shí)分為兩部分：用事實(shí)表示靜態(tài)知識(shí)，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理知識(shí)，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理過(guò)程和行為。由于這類(lèi)系統(tǒng)的知識(shí)庫(kù)主要用于存儲(chǔ)規(guī)則，因此又過(guò)程和行為。由于這類(lèi)系統(tǒng)的知識(shí)庫(kù)主要用于存儲(chǔ)規(guī)則，因此又把此類(lèi)系統(tǒng)稱(chēng)為基于規(guī)則的系統(tǒng)把此類(lèi)系統(tǒng)稱(chēng)為基于規(guī)則的系統(tǒng)(rule based system)。 2022-2-2人工智能49 產(chǎn)生式系統(tǒng)由產(chǎn)生式系統(tǒng)由3 3個(gè)部分組成，即總數(shù)據(jù)庫(kù)個(gè)部分組成，即總數(shù)據(jù)庫(kù)( (或全局?jǐn)?shù)據(jù)庫(kù)或全局?jǐn)?shù)據(jù)庫(kù)) )、產(chǎn)、產(chǎn)生式規(guī)則和控制策略。各部分間的關(guān)系如圖所示。生式規(guī)則和控制策略。各部分間的關(guān)系如圖所示。 3.3.1 3.3.1