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

第3章推理技術(shù)2023/2/31《人工智能》3.1消解原理3.2規(guī)則演繹系統(tǒng)3.3產(chǎn)生式系統(tǒng)3.4基于概率的推理3.5可信度方法3.6證據(jù)理論3.7模糊推理3.8非單調(diào)推理本章主要內(nèi)容：2023/2/32《人工智能》

上一章中我們討論了一些簡單搜索的基本原理。但對于許多比較復(fù)雜的系統(tǒng)和問題，如果采用上一章討論過的搜索方法，那么很難甚至無法使問題獲得解決的。需要應(yīng)用一些更先進(jìn)的推理技術(shù)和系統(tǒng)求解這種比較復(fù)雜的問題。

所謂推理就是按某種策略由已知判斷推出另一判斷的思維過程。一般來說，推理都包括兩種判斷：一種是已知的判斷，包括已知的知識和已知事實；另一種是由已知判斷推出的新判斷，即推理的結(jié)論。

下面我們首先討論一下與推理相關(guān)的一些概念。2023/2/33《人工智能》推理方式及其分類1.演繹推理、歸納推理、默認(rèn)推理 演繹推理：從一般到特殊。例如三段論。 歸納推理：從個體到一般。 默認(rèn)推理：缺省推理，在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理。2.確定性、不確定性推理3.單調(diào)性、非單調(diào)推理 推出的結(jié)論是否單調(diào)增加。4.啟發(fā)式、非啟發(fā)式推理 所謂啟發(fā)性知識是指與問題有關(guān)且能加快推理進(jìn)程、求得問題最優(yōu)解的知識。5.基于知識的推理、統(tǒng)計推理、直覺推理 從方法論的角度劃分。2023/2/34《人工智能》推理的控制策略推理的控制策略主要包括：推理方向、搜索策略、沖突消解策略、求解策略及限制策略。1.、正向推理正向推理的基本思想是：從用戶提供的初始已知事實出發(fā)，在知識庫KB中找出當(dāng)前可適用的知識，構(gòu)成可適用知識集KS，然后按某種沖突消解策略從KS中選出一條知識進(jìn)行推理，并將推出的新事實加入到數(shù)據(jù)庫中作為下一步推理的已知事實。如此重復(fù)進(jìn)行這一過程，直到求得了所要求的解或者知識庫中再無可使用的知識為止。2、逆向推理

逆向推理的基本思想是：首先選定一個假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說明原假設(shè)是成立的；若無論如何都找不到所需要的證據(jù)，則說明原假設(shè)不成立，此時需要另作新的假設(shè)。2023/2/35《人工智能》推理的控制策略（2）3.混合推理先正向后逆向推理先逆向后正向推理4.雙向推理正向推理與逆向推理同時進(jìn)行，且在推理過程中的某一步上“碰頭”。5.求解策略只求一個解，還是求所有解以及最優(yōu)解。6.限制策略限制推理的深度、寬度、時間、空間等等。2023/2/36《人工智能》沖突消解策略沖突：多個知識都匹配成功。在產(chǎn)生式系統(tǒng)中對于正向推理：多條產(chǎn)生式前件都與已知事實匹配成功多組不同事實都與同一規(guī)則前件匹配成功對于逆向推理：多條規(guī)則后件都和同一個假設(shè)匹配成功多條規(guī)則后件可與多個假設(shè)匹配成功沖突消解的基本思想都是對知識進(jìn)行排序。2023/2/37《人工智能》幾種沖突消解策略按針對性排序 前件中條件詳細(xì)(多)的規(guī)則先推。按已知事實的新鮮性排序 新鮮事實(剛得到的局部結(jié)論)越多(越新鮮)的規(guī)則先推。按匹配度排序 在不確定性匹配中，計算兩個知識模式的相似度(匹配度)，并對其排序，相似度高的規(guī)則先推。按領(lǐng)域問題特點排序按上下文限制排序 把規(guī)則按照下上文分組，并只能選取組中的規(guī)則。按冗余限制排序 冗余知識越少的規(guī)則先推。按條件個數(shù)排序 條件少的規(guī)則先推。2023/2/38《人工智能》所謂模式匹配是指對兩個知識模式(例如兩個謂詞公式、框架片斷、語義網(wǎng)絡(luò)片斷)的比較與耦合，及檢查這兩個知識模式是否完全一致或者近似一致。按匹配時兩個知識模式的相似程度，模式匹配可分為確定性匹配與不確定性匹配。確定性匹配是指兩個知識模式完全一致，或者經(jīng)過變量代換后變得完全一致。 例如：

P1: father(李四，李小四)andman(李小四) P2: father(x,y)andman(y)不確定性匹配是指兩個知識模式不完全一致，但是它們的相似程度又在規(guī)定的限度內(nèi)。

模式匹配2023/2/39《人工智能》1、變量代換定義

代換是一個形如{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)/x,f(x)/y}不是代換{g(a)/x,f(x)/y}是代換2023/2/310《人工智能》2、代換的復(fù)合定義：

設(shè)θ={t1/x1,t2/x2,…,tn/xn}λ={u1/y1,u2/y2,…,um/ym}

是兩個代換，則此兩個代換的復(fù)合也是一個代換，它是從{t1λ/x1,t2λ/x2,…,tnλ/xn,u1/y1,u2/y2,…,um/ym}中刪去如下兩種元素：

tiλ/xi

當(dāng)tiλ=xi ui/yi

當(dāng)yi∈{x1,x2,…,xn}后剩下的元素所構(gòu)成的集合，記為θ°λ。注：tiλ表示對ti運(yùn)用λ代換。實際上θ°λ就是對一個公式先運(yùn)用θ代換，然后再運(yùn)用λ代換。2023/2/311《人工智能》3、代換的例子例如，設(shè)有代換θ={f(y)/x,z/y}λ={a/x,b/y,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/z}2023/2/312《人工智能》4、公式集的合一定義：

設(shè)有公式集F={F1,F2,…,Fn}，若存在一個代換λ使得F1λ=F2λ=…=Fnλ則稱λ為公式集F的一個合一，且稱F1,F2,…,Fn是可合一的。例如，設(shè)有公式集F={P(x,y,f(y)),P(a,g(x),z)}則下式是它的一個合一：λ={a/x,g(a)/y,f(g(a))/z}一個公式集的合一一般不唯一。定義：設(shè)σ是公式集F的一個合一，如果對任一個合一θ都存在一個代換λ，使得θ=σ°λ，則稱σ是一個最一般的合一。最一般合一是唯一的。2023/2/313《人工智能》求取最一般合一差異集：兩個公式中相同位置處不同符號的集合。例如：F1:P(x,y,z),F2:P(x,f(a),h(b))則D1={y,f(a)},D2={z,h(b)}求取最一般合一的算法：令k=0,Fk=F,σk=ε。ε是空代換。若Fk只含一個表達(dá)式，則算法停止，σk就是最一般合一。找出Fk的差異集Dk。若Dk中存在元素xk和tk，其中xk是變元，tk是項，且xk不在tk中出現(xiàn)，則置：σK+1=σk°{tk/xk}Fk+1=Fk{tk/xk}k=k+1然后轉(zhuǎn)(2)。若不存在這樣的xk和tk則算法停止。算法終止，F(xiàn)的最一般合一不存在。2023/2/314《人工智能》求取最一般合一的例子例如，設(shè)F={P(a,x,f(g(y))),P(z,f(z),f(u))}求其最一般合一。令F0=F,σ0=ε。F0中有兩個表達(dá)式，所以σ0不是最一般合一。差異集D0={a,z}。σ1=σ0°{a/z}={a/z} F1={P(a,x,f(g(y))),P(a,f(a),f(u))}。D1={x,f(a)}。σ2=σ1°{f(a)/x}={a/z,f(a)/x} F2=F1{f(a)/x}={P(a,f(a),f(g(y))),P(a,f(a),f(u))}。D2={g(y),u}。σ3=σ2°{g(y)/u}={a/z,f(a)/x,g(y)/u}F3=F2{g(y)/u}={P(a,f(a),f(g(y))),P(a,f(a),f(g(y)))}。因為F3中只有一個表達(dá)式，所以就是最一般合一，即

{a/z,f(a)/x,g(y)/u}2023/2/315《人工智能》3.1

消解原理

消解原理是針對謂詞邏輯表示的問題進(jìn)行求解方法，也叫做歸結(jié)原理。主要內(nèi)容包括子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。消解原理的基礎(chǔ)知識：謂詞公式、某些推理規(guī)則以及置換合一等概念。在謂詞邏輯中，把原子謂詞公式及其否定統(tǒng)稱為文字。任何文字的析取式稱為子句。例如：P(x)∨Q(x),?P(x,f(x))∨Q(x,g(x))不包含任何文字的子句稱為空子句?？兆泳洳缓形淖?，不能被任何解釋滿足，所以空子句是永假的，不可滿足的。2023/2/316《人工智能》3.1.1化為子句集(1)消去蘊(yùn)涵符號：只應(yīng)用∨和～符號，以～A∨B替換A=>B。例如：(2)減少否定符號的轄域：每個否定符號～最多只用到一個謂詞符號上，并反復(fù)應(yīng)用狄·摩根定律。例如：上式經(jīng)等價變換后在說明消解過程之前,我們首先說明任一謂詞演算公式可以化成一個子句集。其變換過程由下列九個步驟組成：2023/2/317《人工智能》(3)對變量標(biāo)準(zhǔn)化：使不同量詞約束的變元有不同的名字，通過變量更名來完成。例如，上式經(jīng)變換后(4)消去存在量詞：分兩種情況

a）存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)，則只要用一個新的個體常量替換受該量詞約束的變元。b）存在量詞位于一個或者多個全稱量詞的轄域內(nèi)，此時要用Skolem函數(shù)f(x1,x2,…,xn)替換受該存在量詞約束的變元。上式中存在量詞(y)及(z)都位于(x)的轄域內(nèi)，所以需要用Skolem函數(shù)替換，設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后得到3.1.1化為子句集（2）

2023/2/318《人工智能》(5)化為前束形：把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為前束形。

3.1.1化為子句集（3）

(6)化為合取范式：任何公式都可寫成由一些謂詞和(或)謂詞的否定的析取的有限集組成的合取式。這種公式叫做合取范式。我們可以反復(fù)應(yīng)用分配律。把任一公式化成合取范式。前面的公式經(jīng)變換得(7)消去全稱量詞

：到了這一步，所有余下的量詞均被全稱量詞量化了。同時全稱量詞的次序也不重要了。因此，我們可以消消去全稱量詞。

2023/2/319《人工智能》(8)消去合取詞：用“，”代替符號∧，最后得到一個有限集，其中每個公式是文字的析取。任一個只由文字的析取構(gòu)成的合式公式叫做一個子句。例如，上式經(jīng)變換后得3.1.1化為子句集（4）

(9)更換變量名稱：使一個變量符號不出現(xiàn)在一個以上的子句中。上式在更改變量名后，可以得到子句集：2023/2/320《人工智能》定義：設(shè)L1為任一原子公式，L2為另一原子公式，且具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β，如果L1和L2具有最一般合一者σ，那么通過消解可以從這兩個父輩子句推導(dǎo)出一個新子句(α∨β)σ。這個新子句叫做消解式。它是由取這兩個子句的析取，然后消去互補(bǔ)對而得到的。如：

3.1.2消解推理規(guī)則

a)假言推理b)合并2023/2/321《人工智能》c)重言式d)重言式e)三段論f)空子句（矛盾）

從以上各例可見，消解可以合并幾個運(yùn)算為一簡單的推理規(guī)則。2023/2/322《人工智能》定理

若C12是子句C1與C2的消解式，則C12是C1與C2邏輯結(jié)論。證明：設(shè)C1=L∨C`1,C2=?L∨C`2,則C12=C`1∨C`2消解推理規(guī)則的正確性

2023/2/323《人工智能》推論1設(shè)C1與C2是子句集S中的兩個子句，C12是它們的消解式。若用C12代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性，即S1的不可滿足性＝>S的不可滿足性推論2設(shè)C1與C2是子句集S中的兩個子句，C12是它們的消解式。若把C12加入S中得到新子句集S2，則S與S2在不可滿足的意義上是等價的，即S2的不可滿足性<＝>S的不可滿足性兩個推論

2023/2/324《人工智能》

為了對含有變量的子句使用消解規(guī)則，必須找到一個置換，作用于父輩子句使其含有互補(bǔ)文字。消解兩個子句時，可能有一個以上的消解式。不過，在任何情況下，它們最多具有有限個消解式。作為例子，我們考慮兩個子句:P[y,f(y)]

進(jìn)一步消解得消解式為:P[x,f(A)]∨P[x,f(y)]∨～P[y,f(A)]

那么得到消解式:Q(y)，～Q(z)

如果取P[z,f(y)]∨～Q(z)∨Q(y)

那么得到消解式:P[x,f(A)]，～P[z,f(A)]

如果取P[x,f(A)]∨P[x,f(y)]∨Q(y)和

～P[z,f(A)]∨～Q(z)2023/2/325《人工智能》1基本思想

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

2消解反演

給出一個公式集S和自標(biāo)公式L，通過反證或反演來求證目標(biāo)公式L，其證明步驟如下：

(1)否定L，得～L；

(2)把～L添加到S中去；

(3)把新產(chǎn)生的集合｛～L，S｝化成子句集；

(4)應(yīng)用消解原理，力圖推導(dǎo)出一個表示矛盾的空子句NIL。3.1.3消解反演求解過程

2023/2/326《人工智能》(3)消解反演舉例

下面舉個例子來說明消解反演過程：前提：每個儲蓄錢的人都獲得利息。

結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢。證明：令S(x,y)表示"x儲蓄y",

M(x)表示“x是錢”，I(x)表示“x是利息”，E(x,y)表示"x獲得y

于是上述命題寫成下列形式：結(jié)論：2023/2/327《人工智能》用化為子句集方法，可把前提化為下列的子句集：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(xiàn)(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),M(b)}該消解反演可以表示為一棵反演樹，如下圖所示。

2023/2/328《人工智能》(4)反演求解過程

用反演樹求取對某個問題的答案，其過程如下：把由目標(biāo)公式的否定產(chǎn)生的每個子句添加到目標(biāo)公式否定之否定的子句中去。按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。

答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個語句的一顆證明樹。由于變換關(guān)系涉及到把由目標(biāo)公式的否定產(chǎn)生的每個子句變換為一個重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨(dú)地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。2023/2/329《人工智能》下面通過一個簡單的例子說明消解反演求解過程

“如果無論約翰(John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢?”這個問題說明了兩個事實，然后提出一個問題，而問題的答案大概可從這兩個事實推導(dǎo)出。這兩個事實可以解釋為下列公式集S：求解的目標(biāo)為：如果我們首先證明目標(biāo)公式在邏輯上遵循S，然后尋求一個存在x的例，那么就能解決“菲多在哪里”的問題。關(guān)鍵想法是把問題化為一個包含某個存在量詞的目標(biāo)公式，使得此存在量詞量化變量表示對該問題的一個解答。2023/2/330《人工智能》對本例應(yīng)用消解反演求解過程，我們有：(1)目標(biāo)公式否定的子句形式為:～AT(Fido,x)，把它添加至目標(biāo)公式的否定之否定的子句中去，得到重言式：～AT(Fido,x)∨AT(Fido,x)(2)用反演樹進(jìn)行消解，并在根部得到子句:AT(Fido，School)(3)從根部求得答案AT(Ffido，School)

2023/2/331《人工智能》

(5)消解策略消解的一般過程：設(shè)子句集S={C1,C2,…Cn}，則消解的一般過程是：S內(nèi)任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱為第一級歸結(jié)式，記為S1。把S與S1內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱為第二級歸結(jié)式，記為S2。S和S1內(nèi)的子句與S2內(nèi)的任意子句兩兩逐一進(jìn)行歸結(jié)，得到一組歸結(jié)式，稱為第三級歸結(jié)式，記為S3。如此繼續(xù)，直到出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)為止。

2023/2/332《人工智能》可以通過一些策略來提高消解推理的效率，這些策略稱為消解策略。策略可分為兩大類：1、刪除策略： 刪除某些無用的子句來縮小歸結(jié)的范圍。2、限制策略： 通過對參加歸結(jié)的子句進(jìn)行種種限制，盡可能減小歸結(jié)的盲目性，使其盡快地歸結(jié)出空子句。2023/2/333《人工智能》純文字刪除法如果某文字L在子句集中不存在可與之互補(bǔ)的文字?L，則稱該文字為純文字。包含純文字的子句可以刪除。重言式刪除法 如果一個子句中同時包含互補(bǔ)文字對，則該字句稱為重言式。重言式是永遠(yuǎn)為真的子句，可以刪除。包孕刪除法 設(shè)有子句C1和C2，如果存在一個代換σ，使得：

C1σC2，則稱C1包孕于C2。此時把包孕的子句C2刪除，不會影響子句集的不可滿足性。刪除策略2023/2/334《人工智能》支持集策略限制：每一次歸結(jié)時，親本子句中至少有一個是由目標(biāo)公式的否定所得到的子句，或者是它們的后裔?？梢宰C明，支持集策略是完備的。線性輸入策略 限制：參加歸結(jié)的兩個子句中必須至少有一個是初始子句集中的子句。線性輸入策略是不完備的。單文字子句策略限制：參加歸結(jié)的兩個子句中必須至少有一個是單文字子句。單文字子句策略是不完備的。祖先過濾策略限制：參加歸結(jié)的子句滿足：(1)C1和C2中至少有一個是初始子句集中的子句?；?2)C1和C2中一個是另外一個的祖先子句。祖先過濾策略是完備的。限制策略2023/2/335《人工智能》3.2

規(guī)則演繹系統(tǒng)

對于許多公式來說，子句形是一種低效率的表達(dá)式，因為一些重要信息可能在求取子句形過程中丟失。本節(jié)將研究采用易于敘述的if-then(如果-那么)規(guī)則來求解問題。

在所有基于規(guī)則系統(tǒng)中，每個if可能與某斷言集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rulebaseddeductionsystem)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項?；谝?guī)則的演繹系統(tǒng)和產(chǎn)生式系統(tǒng)，均有正向推理和逆向推理兩種推理方式。2023/2/336《人工智能》1.事實表達(dá)式的與或形變換

在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實表示為非蘊(yùn)涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。我們不想把這些事實化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換為叫做與或形的非蘊(yùn)涵形式。要把一個公式化為與或形，可采用下列步驟：3.2.1規(guī)則正向演繹系統(tǒng)利用(W1→W2)和(～W1∨W2)的等價關(guān)系，消去符號→(如果存在該符號的話)。實際上，在事實中間很少有符號→出現(xiàn)，因為可把蘊(yùn)涵式表示為規(guī)則。用狄·摩根定律把否定符號移進(jìn)括號內(nèi)，直到每個否定符號的轄域最多只含有一個謂詞為止。對所得到的表達(dá)式進(jìn)行Skolem化和前束化。對全稱量詞轄域內(nèi)的變量進(jìn)行改名和變量標(biāo)準(zhǔn)化，而存在量詞量化變量用Skolem函數(shù)代替。刪去全稱量詞，而任何余下的變量都被認(rèn)為具有全稱量化作用。2023/2/337《人工智能》例如，有事實表達(dá)式對變量更名標(biāo)準(zhǔn)化，使得同一變量不出現(xiàn)在事實表達(dá)式的不同主要合取式中。更名后得表達(dá)式：

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)}

與或形表達(dá)式是由符號∧和∨連接的一些文字的子表達(dá)式組成的。呈與或形的表達(dá)式并不是子句形，而是接近于原始表達(dá)式形式，特別是它的子表達(dá)式不是復(fù)合產(chǎn)生的。2023/2/338《人工智能》2.事實表達(dá)式的與或圖表示將上例與或形的事實表達(dá)式用與或圖來表示。

表示某個事實表達(dá)式的與或圖的葉節(jié)點均由表達(dá)式中的文字來標(biāo)記。圖中標(biāo)記有整個事實表達(dá)式的節(jié)點，稱為根節(jié)點，它在圖中沒有祖先。

注意與或標(biāo)記與普通與或圖的區(qū)別2023/2/339《人工智能》3.與或圖的F規(guī)則變換把允許用作規(guī)則的公式類型限制為下列形式：L→W式中：L是單文字；W為與或形的唯一公式。

把形式為LW的規(guī)則應(yīng)用到任一個具有葉節(jié)點n并由文字L標(biāo)記的與或圖上，可以得到一個新的與或圖。在新的圖上，節(jié)點n由一個單線連接符接到后繼節(jié)點(也由L標(biāo)記)，它是表示為W的一個與或圖結(jié)構(gòu)的根節(jié)點。例如，把規(guī)則S=>(X∧Y)∨Z應(yīng)用于圖1中標(biāo)有S的葉節(jié)點上。所得到的新與或圖結(jié)構(gòu)表示于圖2。圖1圖22023/2/340《人工智能》4.目標(biāo)公式與終止條件在正向演繹系統(tǒng)中，要求目標(biāo)公式用子句來表示，即文字的析取形式?？捎糜梦淖旨硎敬四繕?biāo)公式。

當(dāng)正向演繹系統(tǒng)產(chǎn)生一個含有以目標(biāo)節(jié)點作為終止的解圖時，此系統(tǒng)就成功地終止。例如：已知事實：A∨B

規(guī)則：A=>C∧D，B=>E∧G

目標(biāo):C∨G

推理過程如圖所示。

2023/2/341《人工智能》

基于規(guī)則的逆向演繹系統(tǒng)，其操作過程與正向演繹系統(tǒng)相反，即為從目標(biāo)到事實的操作過程，從then到if的推理過程。

1.

目標(biāo)表達(dá)式的與或形式

逆向演繹系統(tǒng)能夠處理任意形式的目標(biāo)表達(dá)式。首先，采用與變換事實表達(dá)式同樣的過程，把目標(biāo)公式化成與或形。即消去蘊(yùn)涵符號，把否定符號移進(jìn)括號內(nèi)，對全稱量詞Skolem化并刪去存在量詞。留在目標(biāo)表達(dá)式與或形中的變量假定都已存在量詞量化。

3.2.2規(guī)則逆向演繹系統(tǒng)設(shè)目標(biāo)表達(dá)式被化成與或形：～P(f(y))∨{Q(f(y),y)∧[～P(f(y))∨～S(y)]}

式中，f(y)為一Skolem函數(shù)。對目標(biāo)的主要析取式中的變量分離標(biāo)準(zhǔn)化可得

～P(f(z))∨{Q(f(y),y)∧[～P(f(y))∨～S(y)]}

2023/2/342《人工智能》

與或形的目標(biāo)公式也可以表示為與或圖。不過，與事實表達(dá)式的與或圖不同的是，對于目標(biāo)表達(dá)式，與或圖中的k線連接符用來分開合取關(guān)系的子表達(dá)式。

上面所用的目標(biāo)公式的與或圖如圖所示

2023/2/343《人工智能》

B規(guī)則是建立在確定的蘊(yùn)涵式基礎(chǔ)上的，正如正向系統(tǒng)的F規(guī)則一樣。不過，在正向演繹系統(tǒng)中把這些B規(guī)則限制為：

W=>L

其中，W為任一與或形公式，L為文字，而且蘊(yùn)涵式中任何變量的量詞轄域為整個蘊(yùn)涵式。其次，把B規(guī)則限制為這種形式的蘊(yùn)涵式還可以簡化匹配，使之不會引起重大的實際困難。此外，可以把像W=>(L1∧L2)這樣的蘊(yùn)涵式化為兩個規(guī)則W=>L1和W=>L2。

2.與或圖的B規(guī)則變換2023/2/344《人工智能》

逆向系統(tǒng)中的事實表達(dá)式均限制為文字合取形，它可以表示為一個文字集。

逆向系統(tǒng)成功的終止條件是與或圖包含有某個終止在事實節(jié)點上的一致解圖。

3.事實表示與終止條件已知事實：F1:DOG(FIDO)；狗的名字叫FidoF2:～BARKS(FIDO)；Fido是不叫的

F3:WAGSTAIL(FIDO)；Fido搖尾巴

F4:MEOWS(MYRTLE)；貓咪的名字叫Myrtle規(guī)則：R1:[WAGSTAIL(x1)∧DOG(x1)]=>FRIENDLY(x1)；

R2:[FRIENDLY(x2)∧～BARKS(x2)]=>～AFRAID(y2,x2)；

R3:DOG(x3)=>ANIMAL(x3)；狗為動物

R4:CAT(x4)=>ANIMAL(x4)；貓為動物

R5:MEOWS(x5)=>CAT(x5)；貓咪是貓

問題：是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?

2023/2/345《人工智能》用目標(biāo)表達(dá)式表示此問題為:CAT(x)∧DOG(y)∧～AFRAID(x,y)

我們就得到該問題的回答語句為：

CAT(MYRTLE)∧DOG(FIDO)∧～AFRAID(MYRTLE,FIDO)2023/2/346《人工智能》

正向演繹系統(tǒng)能夠處理任意形式的if表達(dá)式，但被限制在then表達(dá)式為由文字析取組成的一些表達(dá)式。逆向演繹系統(tǒng)能夠處理任意形式的then表達(dá)式，但被限制在if表達(dá)式為文字合取組成的一些表達(dá)式。我們希望能夠構(gòu)成一個組合的系統(tǒng)，使它具有正向和逆向兩系統(tǒng)的優(yōu)點，以求克服各自的缺點(局限性)。

正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標(biāo)和表示事實的兩個與或圖結(jié)構(gòu)組成。這些與或圖最初用來表示給出的事實和目標(biāo)的某些表達(dá)式集合，現(xiàn)在這些表達(dá)式的形式不受約束。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。組合演繹系統(tǒng)的主要復(fù)雜之處在于其終止條件，終止涉及兩個圖結(jié)構(gòu)之間的適當(dāng)交接處。3.2.3雙向演繹系統(tǒng)2023/2/347《人工智能》3.3

產(chǎn)生式系統(tǒng)

產(chǎn)生式系統(tǒng)(productionsystem)首先是由波斯特(Post)于1943年提出的產(chǎn)生式規(guī)則(productionrule)而得名的。他們用這種規(guī)則對符號串進(jìn)行置換運(yùn)算。后來，美國的紐厄爾和西蒙利用這個原理建立一個人類的認(rèn)知模型(1965年)。同時，斯坦福大學(xué)利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設(shè)計出第一個專家系統(tǒng)DENDRAL。產(chǎn)生式系統(tǒng)用來描述若干個不同的以一個基本概念為基礎(chǔ)的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：用事實表示靜態(tài)知識，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)則，因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)(rulebasedsystem)。2023/2/348《人工智能》

產(chǎn)生式系統(tǒng)由3個部分組成，即總數(shù)據(jù)庫(或全局?jǐn)?shù)據(jù)庫)、產(chǎn)生式規(guī)則和控制策略。各部分間的關(guān)系如圖所示。

3.3.1產(chǎn)生式系統(tǒng)的組成產(chǎn)生式規(guī)則是一個以"如果滿足這個條件，就應(yīng)當(dāng)采取某些操作"形式表示的語句。例如，

規(guī)則:

如果

某