第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 上一章中我們討論了一些簡單搜索的基本原理。但上一章中我們討論了一些簡單搜索的基本原理。但對于許多比較復雜的系統(tǒng)和問題，如果采用上一章討論對于許多比較復雜的系統(tǒng)和問題，如果采用上一章討論過的搜索方法，那么很難甚至無法使問

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

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

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

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

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

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

8、/x,f(x)/y不是代換g(a)/x,f(x)/y是代換2022-2-2人工智能112、代換的復合定義： 設= t1/x1,t2/x2,tn/xn= u1/y1,u2/y2,um/ym是兩個代換，則此兩個代換的復合也是一個代換，它是從t1/x1,t2/x2,tn/xn,u1/y1,u2/y2,um/ym 中刪去如下兩種元素： ti/xi當ti=xi ui/yi當yix1,x2,xn 后剩下的元素所構(gòu)成的集合，記為 。n注： ti表示對ti運用代換。實際上就是對一個公式先運用代換，然后再運用代換。2022-2-2人工智能123、代換的例子例如，設有代換= 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、公式集的合一定義： 設有公式集F=F1,F2,Fn，若存在一個代換使得 F1=F2=Fn則稱為公式集F的一個合一，且稱F1,F2,Fn是可合一的。n例如，設有公式集F=P(x,y,f(y),P(a,g(x),z) 則下式是它的一個合一：=a/x,g(a)/y,f(g(a)/zn一個公式集的合一一般不唯一。定義： 設是公式集F的一個合一，如果對任一個合一都存在一個代換，使得=，則稱是一個最一般的合一。n最一般合一是唯一的。2022-2-2人工

10、智能14求取最一般合一n差異集：兩個公式中相同位置處不同符號的集合。例如：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只含一個表達式，則算法停止，k就是最一般合一。w找出Fk的差異集Dk。w若Dk中存在元素xk和tk，其中xk是變元，tk是項，且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、設F=P(a,x,f(g(y),P(z,f(z),f(u)求其最一般合一。w令F0=F, 0=。 F0中有兩個表達式，所以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) 。因為F3中只有一個表達式

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

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

14、復應用狄個謂詞符號上，并反復應用狄摩根定律。例如：上摩根定律。例如：上式經(jīng)等價變換后式經(jīng)等價變換后()() ( , )()( ( , )( , )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 在說明消解過程之前在說明消解過程之前, ,我們首先說明任一謂詞演算公式可我們首先說明任一謂詞演算公式可以化成一個子句集。其變換過程由下列九個步驟組成：以化成一個子句集。其變換過程由下列九個步驟組成：2022-2-2人工智能18(3)(3

15、)對變量標準化對變量標準化 ：使不同量詞約束的變元有不同的名字，：使不同量詞約束的變元有不同的名字，通過變量更名來完成。例如，上式經(jīng)變換后通過變量更名來完成。例如，上式經(jīng)變換后()()( , ) ()( ( , )( , )xyP x yz Q x zR x z (4)(4)消去存在量詞：分兩種情況消去存在量詞：分兩種情況 a a）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，則只要用一個新）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，則只要用一個新的個體常量替換受該量詞約束的變元。的個體常量替換受該量詞約束的變元。 b b）存在量詞位于一個或者多個全稱量詞的轄域內(nèi)，此時要用）存在量詞位于一個或者多個全稱量詞的轄域

16、內(nèi)，此時要用SkolemSkolem函數(shù)函數(shù)f(x1,x2,xn)f(x1,x2,xn)替換受該存在量詞約束的變元。替換受該存在量詞約束的變元。上式中存在量詞上式中存在量詞( ( y)y)及及( ( z)z)都位于都位于( ( x)x)的轄域內(nèi)，所以需要的轄域內(nèi)，所以需要用用SkolemSkolem函數(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)化為前束形化為前束形 ：把所有全稱量詞移到公式的左邊，并使：把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為前束形。所得公式稱為前束形。 3.1.1 3.1.1 化為子句集（化為子句集（3 3） (6)(6)化為合取范式化為合取范式 ：任何公式都可寫成由一些謂詞和：任何公式都可寫成由一些謂詞和( (或或) )謂詞的否定的析取的有限集組成的合取式。這種公式謂詞的否定的析取的有限集組成的合取式。這種公式叫做合取范式。我們可以反復應用分配律。把任一公叫做合取

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

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

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

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

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

23、補文字。個置換，作用于父輩子句使其含有互補文字。 消解兩個子句時，可能有一個以上的消解式。不過，在消解兩個子句時，可能有一個以上的消解式。不過，在任何情況下，它們最多具有有限個消解式。作為例子，我們?nèi)魏吻闆r下，它們最多具有有限個消解式。作為例子，我們考慮兩個子句考慮兩個子句: : Py,f(y) 進一步消解得消解式為: 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、本思想基本思想 把要解決的問題作為一個要證明的命題，其目標公式被否定并化把要解決的問題作為一個要證明的命題，其目標公式被否定并化成子句形，然后添加到命題公式集中去成子句形，然后添加到命題公式集中去, ,把消解反演系統(tǒng)應用于聯(lián)合把消解反演系統(tǒng)應用于聯(lián)合集，并推導出一個空子句集，并推導出一個空子句(NIL)(NIL)，產(chǎn)生一個矛盾，這說明目標公式的，產(chǎn)生一個矛盾，這說明目標公式的否定式不成立，即有目標公式成立，定理得證，問題得到解決。這與否定式不成立，即有目標公式成立，定理得證，問題得到解決。這與數(shù)學中反證法的思想十分相似。數(shù)學中反證法的思想十分相似。 2 2 消解反演消解反演給出一個公式集給出一

25、個公式集S S和自標公式和自標公式L L，通過反證或反演來求證目標公式，通過反證或反演來求證目標公式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)應用消解原理，力圖推導出一個表示矛盾的空子句應用消解原理，力圖推導出一個表示矛盾的空子句NILNIL。 3.1.3 3.1.3 消解反演求解過程消解反演求解過程 2022-2-2人工智能27(3) 消解反演舉例消解反演舉例 下面舉個例子來說明消解反演過程： 前提：

26、每個儲蓄錢的人都獲得利息。 結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢。證明：令S(x,y)表示x儲蓄y , M(x)表示“x是錢”， I(x)表示“x是利息”， E(x,y)表示x獲得y 于是上述命題寫成下列形式：結(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)該消解反演可以表示為一棵反演樹，如下圖所示。 2022-2-2人工智能29(4) 反演求解過程反演求解過程用反演樹求取對某個問題的答案，其過程如下：把由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定之否定的子句中去。按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。 答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個語句的一顆證明樹。由于變換關系涉及到把由目標公式的否定產(chǎn)生的每個子句變換為一個重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨地遵循公理。因此被變換的證明樹本身

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

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

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

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

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

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

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

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

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

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

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

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

40、個文字集。 逆向系統(tǒng)成功的終止條件是與或圖包含有某個終止在事實節(jié)點上的一致解圖。 3.事實表示與終止條件事實表示與終止條件 已知事實：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)；狗為動物 R4: CAT(x4

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

42、夠構(gòu)成一個組合的系統(tǒng)，使它具有正向和逆向兩系統(tǒng)的優(yōu)點，以求克服各自的缺點(局限性)。 正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的基礎上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標和表示事實的兩個與或圖結(jié)構(gòu)組成。這些與或圖最初用來表示給出的事實和目標的某些表達式集合，現(xiàn)在這些表達式的形式不受約束。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。 組合演繹系統(tǒng)的主要復雜之處在于其終止條件，終止涉及兩個圖結(jié)構(gòu)之間的適當交接處。 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ī)則對符號串進行置換運算。后來，美國的紐厄爾和西蒙利用這個原對符號串進行置換運算。后來，美國的紐厄爾和西蒙利用這個原理建立一個人類的認知模型理建立一個人類的認知模型(1965年年)。同時，斯坦福大學利用產(chǎn)。同時，斯坦福大學利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設計出第一個專家系統(tǒng)生式系統(tǒng)結(jié)構(gòu)設計出第一個專家系統(tǒng)DENDRAL。產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概念為基礎的產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概念為基礎的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的

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