人工智能與知識(shí)工程搜索推理技術(shù)2分析課件

1、3.5 消解原理3.6 規(guī)則演繹系統(tǒng)3.7 產(chǎn)生式系統(tǒng)3.8 系統(tǒng)組織技術(shù)3搜索推理技術(shù)1推理的基本概念推理是指按照某種策略從已知事實(shí)出發(fā)去推出結(jié)論的過程。其中，推理所用的事實(shí)可分為兩種：一種是與求解問題有關(guān)的初始證據(jù)；另一種是推理過程中所得到的中間結(jié)論。通常，智能系統(tǒng)的推理過程是通過推理機(jī)來完成的。所謂推理機(jī)就是智能系統(tǒng)用來實(shí)現(xiàn)推理的那些程序。例，在醫(yī)療診斷專家系統(tǒng)中，所有與診斷有關(guān)的醫(yī)療常識(shí)和專家經(jīng)驗(yàn)都被保存在知識(shí)庫中。當(dāng)系統(tǒng)開始診斷疾病時(shí)，首先把病人的癥狀和檢查結(jié)果放到事實(shí)庫中，然后再從事實(shí)庫中的這些初始證據(jù)出發(fā)，按照某種策略在知識(shí)庫中尋找可以匹配的知識(shí)，如果得到的是一些中間結(jié)論，則需要

2、把它們作為已知事實(shí)放入事實(shí)庫中，并繼續(xù)尋找可以匹配的知識(shí)，如此反復(fù)進(jìn)行，直到推出最終結(jié)論為止。由初始事實(shí)出發(fā)到推出最終結(jié)論的過程就是推理，實(shí)現(xiàn)這一推理過程的程序稱為推理機(jī)。2推理的基本概念（續(xù)）智能系統(tǒng)的推理包括兩個(gè)基本問題：一個(gè)是推理的方法；另一個(gè)是推理的控制策略。推理方法主要解決在推理過程中前提與結(jié)論之間的邏輯關(guān)系，以及在非精確性推理中不確定性的傳遞問題。3推理的基本概念（續(xù)）1. 按推理的邏輯基礎(chǔ)分類 按照推理的邏輯基礎(chǔ)，常用的推理方法可分為演繹推理、歸納推理和默認(rèn)推理。(1)演繹推理。演繹推理是從已知的一般性知識(shí)出發(fā)，去推出組合在這些已知知識(shí)中適合于某種個(gè)別情況的結(jié)論的過程。它是一種由

3、一般到個(gè)別的推理方法，其核心是三段論，即假言推理、拒取式推理和假言三段論。常用的三段論是由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論三部分組成的。其中，大前提是由已知的一般性知識(shí)或推理過程得到的判斷；小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷；結(jié)論是由大前提推出的，并且適合于小前提的判斷。4推理的基本概念（續(xù)）（2）歸納推理歸納推理的前提是一些關(guān)于個(gè)別事物或現(xiàn)象的命題，而結(jié)論則是關(guān)于該類事物或現(xiàn)象的普遍性命題。歸納推理的結(jié)論所斷定的知識(shí)范圍超出了前提所斷定的知識(shí)范圍，因此，歸納推理的前提與結(jié)論之間的聯(lián)系不是必然性的，而是或然性的。也就是說，其前提真而結(jié)論假是可能的，所以，歸納推理是一種或然性推理?；?/p>

4、思想：先從已知事實(shí)中猜測出一個(gè)結(jié)論，然后對這個(gè)結(jié)論的正確性加以證明確認(rèn)。如果按照所選事例的廣泛性可分為完全歸納推理和不完全歸納推理。5推理的基本概念（續(xù)）3)默認(rèn)推理。默認(rèn)推理是在知識(shí)不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理，因此也稱為缺省推理。在推理過程中，如果發(fā)現(xiàn)原先的假設(shè)不正確，就撤銷原來的假設(shè)以及由此假設(shè)所推出的所有結(jié)論，重新對新情況進(jìn)行推理。由于默認(rèn)推理容許在推理過程中假設(shè)某些條件是成立的，這就解決了在一個(gè)不完備的知識(shí)集中進(jìn)行推理的問題。6推理的基本概念（續(xù)）2. 按照所用知識(shí)的確定性分類 確定性推理和不確定性推理3. 按推理過程的單調(diào)性分類 按照推理過程的單調(diào)性，或者說按照推

5、理過程所得到的結(jié)論是否越來越接近目標(biāo)，推理可分為單調(diào)推理與非單調(diào)推理兩類。4. 按照方法論分類 按照方法論，常見的推理有基于知識(shí)的推理、統(tǒng)計(jì)推理和直覺推理等?；谥R(shí)的推理，是指根據(jù)已掌握的事實(shí)，通過運(yùn)用知識(shí)進(jìn)行的推理。例如：醫(yī)生診斷疾病時(shí)，根據(jù)病人癥狀及檢驗(yàn)結(jié)果，運(yùn)用醫(yī)學(xué)知識(shí)進(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)的原因。直覺推理又稱為常識(shí)性推理，是指根據(jù)常識(shí)進(jìn)行的推理。例如，當(dāng)你猛然發(fā)現(xiàn)頭上有一物體掉落時(shí)，立即會(huì)意識(shí)到危險(xiǎn)，并立即躲開，這就是直覺推理。7推理的基本概念（續(xù)）推理的

6、控制策略智能系統(tǒng)的推理過程相當(dāng)于人類的思維過程，即求解問題的過程。問題求解的質(zhì)量與效率不僅依賴于所采用的求解方法，而且還依賴于求解問題的策略，即推理的控制策略。推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理過程盡快達(dá)到目標(biāo)的策略。由于智能系統(tǒng)的推理過程一般表現(xiàn)為一種搜索過程，因此，推理的控制策略又可分為推理策略和搜索策略。其中，推理策略主要解決推理方向、沖突消解等問題，如推理方向控制策略、求解策略、限制策略、沖突消解策略等，8推理的基本概念（續(xù)）推理方向用來確定推理的控制方式，即用來確定推理過程是從初始證據(jù)開始到目標(biāo)，還是從目標(biāo)開始到初始證據(jù)。按照對推理方向的控制，推理可分為正向推理、逆向推理、混合

7、推理及雙向推理等4種。求解策略是指僅求一個(gè)解，還是求所有解或最優(yōu)解等。限制策略是指為了防止無窮的推理，以及推理過程太長而對推理的深度、寬度、時(shí)間、空間等進(jìn)行限制的策略。沖突消解策略是指當(dāng)推理過程有多條知識(shí)可用時(shí)，如何從這多條可用知識(shí)中選出一條最佳知識(shí)用于推理的策略。目前已有多種消解沖突的策略，其基本思想都是對知識(shí)進(jìn)行排序，比如：按針對性排序；按已知事實(shí)的更新程度排序；按匹配程度排序；按產(chǎn)生知識(shí)冗余大小排序；按產(chǎn)生結(jié)論的條件個(gè)數(shù)排序等。93.5消解原理3.5.1 子句集的求取3.5.2 消解推理規(guī)則3.5.3 含有變量的消解式3.5.4 消解反演求解過程103.5消解原理(續(xù))知識(shí)表示方式:謂詞

8、公式解決問題:定理的自動(dòng)證明問題的自動(dòng)求解消解原理由Robinson于1965年提出，又稱為歸結(jié)原理。 將要證明的前提及結(jié)論合并在一起, 化為子句集,利用消解原理對子句集進(jìn)行消解, 如果得到空子句則成立,否則失敗.例:如果存在某個(gè)公理 E1E2 和另一公理E2 E3 ，那么 E1E3 在邏輯上成立。這就是消解，而稱 E1 E3 為 E1E2 和E2 E3 的消解式（resolvent ）。 113.5.1 子句集的求取相關(guān)概念文字: 原子謂詞公式及其否定統(tǒng)稱為文字。子句: 任何文字的析取式稱為子句。空子句: 不包含任何文字的子句稱為空子句。記為：或NIL子句集:由子句和空子句所構(gòu)成的集合稱為子

9、句集例: P(x, y)Q(x, y),P(x,y)U(x)V(y),Q(x, y)U(y)在謂詞邏輯中，任一謂詞演算公式可以化成一個(gè)子句集 123.5.1 子句集的求取（續(xù)）子句集的化簡步驟:例: (z)(x)(y)(P(x)Q(x)R(y)U(z)（1）利用等價(jià)關(guān)系消去蘊(yùn)涵和雙條件符(“”或“”)PQ PQ ,PQ ( PQ)( QP )對于本例有:( P(x)Q(x) R(y) ( P(x)Q(x)R(y)(z)(x)(y) (P(x)Q(x)R(y)U(z)133.5.1 子句集的求?。ɡm(xù)）（2）減小否定符號的轄域使得否定符只作用于謂詞符號(原子公式)。狄摩根定律和量詞轉(zhuǎn)換率( PQ

10、) PQ，( PQ ) PQ(x) P (x) P，(x) P (x)P對于本例有:(z)(x)(y) (P(x)Q(x)R(y)U(z)143.5.1 子句集的求取（續(xù)）（3）對變量標(biāo)準(zhǔn)化（變元換名）在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元(虛構(gòu)變量)，它可以在該轄域內(nèi)處處統(tǒng)一地被另一個(gè)沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。合式公式中變量的標(biāo)準(zhǔn)化，意味著對啞元改名以保證每個(gè)量詞有其自己唯一的啞元。 (x) P (x) (y) P (y)(x) P (x) (y) P (y)例： (x)A(x)(x)B(x)化為：(x)A(x)(y)B(y)153.5.1 子句集的求?。ɡm(xù)）（4

11、）消去存在量詞( skolem化)Skolem函數(shù): 在公式( y)( x)P(x,y)中，存在量詞是在全稱量詞的轄域內(nèi)，我們允許所存在的x可能依賴于y值。令這種依賴關(guān)系明顯地由函數(shù)g(y)所定義，它把每個(gè)y值映射到存在的那個(gè)x。這種函數(shù)叫做Skolem函數(shù)。 如果用Skolem函數(shù)代替存在的x,我們就可以消去全部存在量詞，并寫成： ( y)P(g(y),y)不在任何全稱量詞轄域內(nèi)的存在量詞約束的變元用具體沒有出現(xiàn)過的常量代替。( x)P(x)化為P(A)在全稱量詞轄域內(nèi)的存在量詞約束的變元用新的skolem函數(shù)符號代替。(z)(x)(y)(P(x)Q(x)R(y)U(z)化為 (x)(P(x

12、)Q(x)R(g(x)U(a)163.5.1 子句集的求?。ɡm(xù)）（5）化為前束范式（量詞左移）到這一步，已不留下任何存在量詞，而且每個(gè)全稱量詞都有自己的變量。把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。所得公式稱為前束形。前束形公式由前綴和母式組成，前綴由全稱量詞串組成，母式由沒有量詞的公式組成，即 前束形 = (前綴) (母 式) 全稱量詞串 無量詞公式 173.5.1 子句集的求?。ɡm(xù)）（6）化為合取范式(Skolem標(biāo)準(zhǔn)形)合取范式: 謂詞公式或謂詞公式的否定的析取的有限集合組成的合取, 叫做合取范式。結(jié)合律, 分配率( PQ )R P( QR )(

13、PQ ) R P( QR )P( QR ) ( PQ ) ( PR )P( QR ) ( PQ ) ( PR )對于本例有:(x)(P(x)Q(x)R(g(x)U(a)化為 (x)P(x)Q(x)R(g(x)U(a)結(jié)合律化為 (x)P(x)R(g(x)U(a)Q(x)R(g(x)U(a)183.5.1 子句集的求取（續(xù)）（7）消去全稱量詞:每個(gè)全稱量詞的轄域都是整個(gè)公式。P(x)R(f(x)U(a)Q(x)R(f(x)U(a)（8）消去連詞符號（表示為子句集）方法: 用A,B代替(AB)對于本例有：P(x)R(f(x)U(a),Q(x)R(f(x)U(a)193.5.1 子句集的求?。ɡm(xù)）（

14、9）更換變量名稱使任意兩個(gè)子句不出現(xiàn)同名的變量。對于本例有：P(x)R(f(x)U(a),Q(y)R(f(y)U(a)203.5.1 子句集的求?。ɡm(xù)）例：(x) P(x) (y) P(y) P(f(x, y)(y)Q(x, y) P(y)1：消去蘊(yùn)含符號 (x) P(x) (y) P(y) P(f(x, y)(y)Q(x, y) P(y)2：減否定符號轄域(x) P(x) (y) P(y) P(f(x, y)( y)Q(x, y) P(y)3:對變量標(biāo)準(zhǔn)化(x) P(x) (y) P(y) P(f(x, y)( q)Q(x, q) P(q)4：消去存在變量(Skolem函數(shù):q=W(x)(x

15、) P(x) (y) P(y) P(f(x, y)Q(x, W(x) P(W(x)5:化為前束形(x) (y) P(x) P(y) P(f(x, y)Q(x, W(x) P(W(x)6:化為合取范式(x) (y) (P(x) P(y) P(f(x, y)(P(x) Q(x, W(x) ) (P(x) P(W(x)213.5.1 子句集的求?。ɡm(xù)）7:消去全稱變量(P(x) P(y) P(f(x, y)(P(x) Q(x, W(x) ) (P(x) P(W(x)8:消去合取符P(x) P(y) P(f(x, y)，P(x) Q(x, W(x) , P(x) P(W(x)9: 更換變量名P(x)

16、P(y) P(f(x, y)，P(x1) Q(x1, W(x1) , P(x2) P(W(x2)223.5.1 子句集的求取（續(xù)）經(jīng)上述步驟化簡得到的標(biāo)準(zhǔn)式是經(jīng)過Skolem化的前束范式，通常也稱為S-標(biāo)準(zhǔn)形。要注意S-標(biāo)準(zhǔn)形不是唯一的，若把它記為Fs，則Fs僅僅是F（未Skolem化的前束式）的一個(gè)特例，取用不同的Skolem函數(shù)會(huì)得到不同的結(jié)果。當(dāng)F為非永假公式時(shí)，F(xiàn)s與F并不等價(jià)，但當(dāng)F為永假時(shí)，F(xiàn)s也一定是永假的，即Skolem化并不影響F的永假特性。這個(gè)結(jié)論很重要，可用定理形式描述如下：定理：若S是合式公式F的S-標(biāo)準(zhǔn)形之子句集，則F為永假的充要條件是S為不可滿足的。子句集中所有元素

17、（即子句）的合取式不為真，則稱該子句集為不可滿足的。謂詞演算體系中還有一些很重要的概念，如謂詞演算的可判定性問題、邏輯推論、推理規(guī)則的有效性、推理規(guī)則系統(tǒng)的完備性等等，對人工智能推理機(jī)制的研究都很有用。 233.5.2消解推理規(guī)則消解式:設(shè)C1=L1和C2= L2是兩個(gè)沒有公共變元的子句, L1和L2分別是原子公式（具有相同的謂詞符號，但一般具有不同的變量）。如果L1和L2存在最一般合一者 , 那么消解C1和C2推導(dǎo)出一個(gè)新子句() 稱為C1和C2的消解式。它是由取這兩個(gè)子句的析取，然后消去互補(bǔ)對而得到的。243.5.2消解推理規(guī)則(續(xù))a) 假言推理P PQ(即P Q) 消解式Qb) 合并P

18、Q PQ 消解式QQ=Qc) 重言式PQ PQ 消解式QQ 或PPd) 空子句P P 消解式NILe) 鏈?zhǔn)?三段論)PQ(即P Q) QR(即Q R)消解式PR(即P R)253.5.3含有變量的消解式對于含有變量的子句, 如果謂詞符號相同,而變量名不同, 則需要找一個(gè)置換作用于父輩子句, 使其含有互補(bǔ)文字, 再進(jìn)行消解。例1: B(x) B(x)C(x) 消解式C(x)例2: P(x) Q(x) Q(f(y) 置換 =f(y)/x 消解式P(f(y)例3: Px, f(y)Q(x) Rf(a),y Pf(f(a),z R(z,w) 置換 =f(f(a)/x, f(y)/z消解式: Qf(f

19、(a) Rf(a),y Rf(y),w263.5.4消解反演求解過程基本思想:反證法:在反證法中首先假定要證明的結(jié)論不成立，然后通過推導(dǎo)出存在矛盾的方法，反證出結(jié)論成立。在歸結(jié)法中首先對結(jié)論求反，然后將已知條件和結(jié)論的否定合在一起用子句集表達(dá)。如果該子句集存在矛盾，則證明了結(jié)論的正確性。 思路：設(shè)S是已知條件和結(jié)論的否定合并后所對應(yīng)的子句集。假定有一種變換方法，可以對S實(shí)施一系列的變換。而且該變換能夠保證變換前后的子句集，在不可滿足的意義下是等價(jià)的。這樣，如果最終得到的子句集是不可滿足的，就證明了子句集S是不可滿足的，從而證明結(jié)論成立。由前面謂詞公式轉(zhuǎn)化為子句集的過程可知，子句集中的子句是與的

20、關(guān)系，如果在子句集中出現(xiàn)了空子句，則說明該子句集是不可滿足的。因此，歸結(jié)過程就是尋找空子句的過程。如果把這一過程看作是搜索的話，初始狀態(tài)就是已知條件和結(jié)論的否定對應(yīng)的子句集，而目標(biāo)就是空子句，規(guī)則就是歸結(jié)。273.5.4消解反演求解過程1. 消解反演已知一個(gè)公式集S和目標(biāo)公式L, 通過反證或反演來求證目標(biāo)公式L, 證明步驟如下: 否定L, 得到L; 把L添加到S中去; 把新產(chǎn)生的集合L, S化成子句集; 應(yīng)用消解原理, 力圖推導(dǎo)出一個(gè)表示矛盾的空子句。283.5.4消解反演求解過程（續(xù)）反演求解的正確性 設(shè)公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個(gè)解釋也滿足L。決不會(huì)有滿足S的解釋能

21、夠滿足L的，所以不存在能夠滿足并集SL的解釋。如果一個(gè)公式集不能被任一解釋所滿足，那么這個(gè)公式是不可滿足的。因此，如果L在邏輯上遵循S，那么SL是不可滿足的?？梢宰C明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集SL消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從SL的子句消解得到空子句，那么L在邏輯上遵循S。 293.5.4消解反演求解過程（續(xù)）例: 已知: 每個(gè)儲(chǔ)蓄錢的人都獲得利息結(jié)論: 如果沒有利息, 那么就沒有人去儲(chǔ)蓄錢。證明: 定義謂詞:S(x,y): 表示”x儲(chǔ)蓄y”M(x): 表示”x是錢”I(x): 表示”

22、x是利息”E(x,y): 表示”x獲得y”已知: (x)(y)(S(x,y) M(y) (y)(I(y) E(x,y)結(jié)論: (x)I(x) (x) (y)(M(y) S(x,y)303.5.4消解反演求解過程（續(xù)）1. 否定結(jié)論: (x)I(x) (x) (y)(M(y) S(x,y)2. 把結(jié)論加入已知, 構(gòu)成新集合G:(x)(y)(S(x,y) M(y) (y)(I(y) E(x,y), (x)I(x)(x) (y)(M(y) S(x,y)3. 將集合G化為子句集（y=f(x)為Skolem函數(shù) ）(1) S(x,y)M(y) I(f(x)(2) S(x,y) M(y) E(x,f(x)

23、(3) I(z)(4) S(a,b)(5) M(b)313.5.4消解反演求解過程（續(xù)）4. 應(yīng)用消解原理進(jìn)行推導(dǎo)。(1) S(x,y)M(y) I(f(x)(2) S(x,y) M(y) E(x,f(x)(3) I(z)(4) S(a,b)(5) M(b)(6) S(x,y)M(y) (1)和(3)消解=f(x)/z(7) M(b) (6)和(4)消解=a/x,b/y(8) NIL (5)和(7)消解323.5.4消解反演求解過程（續(xù)）消解反演可以表示為一棵反演樹 333.5.4消解反演求解過程（續(xù)）歸結(jié)方法很簡單，但是即便是對于一個(gè)比較簡單的問題，往往可以進(jìn)行歸結(jié)的子句也比較多。如何從眾多

24、的可歸結(jié)的子句中選擇兩個(gè)子句，即為搜索策略問題。不同的搜索策略，會(huì)影響到系統(tǒng)的效率和開銷，同時(shí)也會(huì)涉及到完備性問題。搜索策略的目標(biāo)就是要找到一棵歸結(jié)反演樹。一個(gè)反演系統(tǒng)當(dāng)存在一個(gè)矛盾時(shí)，如果使用的一種策略，最終都將找到一棵反演樹（即能找到矛盾），則這種策略是完備的。在實(shí)際應(yīng)用中，有些策略雖不完備，但具有極高的效率，也是可取的。提高策略效率的一些作法是：只歸結(jié)含有互補(bǔ)對的文字；及時(shí)刪去出現(xiàn)的重言式和被其他子句所包含的子句；每次歸結(jié)都取與目標(biāo)公式否定式有關(guān)的子句作為母子句之一進(jìn)行歸結(jié)等等。 343.5.4消解反演求解過程（續(xù)）2. 反演求解過程問題的求解利用消解反演除了可以實(shí)現(xiàn)定理的自動(dòng)證明之外，

25、也可以對簡單問題進(jìn)行求解。例: 張和李是同班同學(xué)，如果x和y是同班同學(xué)，則x的教室也是y的教室，現(xiàn)在張?jiān)?02教室上課。問現(xiàn)在李在哪里上課？353.5.4消解反演求解過程（續(xù)）從反演樹求問題答案的過程：1. 把問題的已知條件用謂詞公式表示出來，并化為相應(yīng)的子句集；2. 把問題的目標(biāo)的否定用謂詞公式表示出來，并化為子句集；3. 對目標(biāo)否定子句集中的每個(gè)子句，構(gòu)造該子句的重言式（即把該目標(biāo)否子句和此目標(biāo)否定子句的否定之間再進(jìn)行析取所得到的子句），用這些重言式代替相應(yīng)的目標(biāo)否定子句，并把這些重言式加入到前提子句集中，得到一個(gè)新的子句集。363.5.4消解反演求解過程（續(xù)）4. 對這個(gè)新的子句集，應(yīng)用

26、消解原理求出其反演證明樹，這時(shí)證明樹的根子句不為空，稱這個(gè)證明樹為修改證明樹；5. 用修改證明樹的根子句作為回答語句，則答案就在此根子句中。373.5.4消解反演求解過程（續(xù)）例：如果無論約翰(JOHN)到哪里去,菲多(FIDO)也就去那里,那么如果約翰在學(xué)校里,菲多在哪里呢?解：定義謂詞：AT（x, y）:表示x在y處1. 已知的謂詞表示:(x)AT(JOHN,x) AT(FIDO,x),AT(JOHN, SCHOOL)化為子句集: AT(JOHN,y)AT(FIDO, y),AT(JOHN, SCHOOL) 383.5.4消解反演求解過程（續(xù)）2. 目標(biāo)否定的謂詞表示：(x)AT(FIDO

27、, x), (x) AT(FIDO, x)化為子句集: AT(FIDO, x) 3. 構(gòu)造目標(biāo)否定子句的重言式,并代替原子句 AT(FIDO, x)AT(FIDO, x) 4. 將3得到的子句集加入前提子句集中:G= AT(JOHN,y)AT(FIDO, y),AT(JOHN,SCHOOL) ,AT(FIDO,x)AT(FIDO, x)393.5.4消解反演求解過程（續(xù)）5. 對新子句集G應(yīng)用消解原理求出反演樹:G= AT(JOHN,y)AT(FIDO, y),AT(JOHN, SCHOOL) ,AT(FIDO,x)AT(FIDO, x)403.5.4消解反演求解過程（續(xù)）例：張某被盜，公安局

28、派出五個(gè)偵察員去調(diào)查。研究案情時(shí)，偵察員A說“趙與錢中至少有一人作案”；偵察員B說“錢與孫中至少有一人作案”；偵察員C說“孫與李中至少有一人作案”；偵察員D說“趙與孫中至少有一人與此案無關(guān)”；偵察員E說“錢與李中至少有一人與此案無關(guān)”。如果這五個(gè)偵察員的話都是可信的，試用消解反演推理求出誰是盜竊犯。定義謂詞：P（x）：x作案。 413.5.4消解反演求解過程（續(xù)）由五個(gè)偵察員的話為真，有P（z） P（q） （1）P（q）P（s） （2）P（s） P（l） （3）P（z） P（s） （4）P（q） P（l） （5）把結(jié)論的否定加入結(jié)論的否定的否定的子句中去，得：P（x）v P（x） （6）因?yàn)檫@

29、些全都是子句，所以化為子句集的步驟可以省略了。（1），（4）歸結(jié)得：P（q） P（s） （7）（2），（7）歸結(jié)得：p（q） （8）即：錢是盜竊犯。423.6 規(guī)則演繹系統(tǒng)消解反演的局限:實(shí)際應(yīng)用中, 很多的事實(shí)更直觀地表現(xiàn)為若干的規(guī)則 If Then ( 如果那么)其中If 部分稱為前項(xiàng), Then部分稱為后項(xiàng)。其中，If部分可能由幾個(gè)if組成，而Then部分可能由一個(gè)或一個(gè)以上的then組成 例: 表示為蘊(yùn)含式:ABC, ACB,ABC, BAC都與子句: ABC 等價(jià)一些重要信息在求取子句集過程中丟失;問題描述方式不自然。433.6 規(guī)則演繹系統(tǒng)（續(xù)）規(guī)則演繹系統(tǒng): 基于規(guī)則求解問題的系

30、統(tǒng)叫做規(guī)則演繹系統(tǒng).兩種推理方向 正向推理: 從if部分向then部分推理的過程, 叫做正向推理。 逆向推理: 從then部分向if部分推理的過程, 叫做逆向推理。按推理方向分類 規(guī)則正向演繹系統(tǒng): 從事實(shí)出發(fā)利用規(guī)則推導(dǎo)出結(jié)論。 規(guī)則逆向演繹系統(tǒng): 從目標(biāo)出發(fā)利用規(guī)則推導(dǎo)出事實(shí)。 規(guī)則雙向演繹系統(tǒng)443.6.1 規(guī)則正向演繹系統(tǒng)規(guī)則正向演繹系統(tǒng): 是從已知事實(shí)出發(fā),正向使用規(guī)則對事實(shí)表達(dá)式的與或樹進(jìn)行變換，直到找到一個(gè)含有目標(biāo)節(jié)點(diǎn)的一致解樹為止。已知事實(shí): 事實(shí)表達(dá)式的與或樹目標(biāo)表達(dá)式：限制為文字的析取式F規(guī)則: LW, 其中L為單文字, W為與或形。結(jié)束條件: 目標(biāo)表達(dá)式是析取式。 得到結(jié)

31、束于目標(biāo)節(jié)點(diǎn)的一致解樹。453.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）1. 事實(shí)表達(dá)式的與或形變換2. 事實(shí)表達(dá)式的與或樹表示3. 與或圖的F規(guī)則變換4. 目標(biāo)公式的表示形式5. 規(guī)則正向演繹推理過程463.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）1. 事實(shí)表達(dá)式的與或形變換規(guī)則正向演繹系統(tǒng)中要求事實(shí)表達(dá)式化簡為與或形。(1) 消去”蘊(yùn)含”和”雙條件”符號;(2) 減小否定符號的轄域, 使否定符號只作用于原子公式;(3) 利用Skolem函數(shù)消去存在量詞;(4) 對變量進(jìn)行換名，使得不同的主要合取式中，具有不同的變量名;(5) 隱去全稱量詞，默認(rèn)公式中的變量受全稱量詞約束。473.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）

32、例: (x) (y) (Q( y, x) (R(y) P(y)S(x, y)消去量詞化為:Q( y, a) (R(y) P(y) S(a, y)再變量更名化為:Q( z, a) (R(y) P(y) S(a, y)483.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）2. 事實(shí)表達(dá)式的與或樹(圖)表示子表達(dá)式間的與、或關(guān)系規(guī)定如下:當(dāng)母表達(dá)式為E1E2E3Ek時(shí)，則每一個(gè)子表達(dá)式Ei被表示成一個(gè)后繼節(jié)點(diǎn)，并由一個(gè)k-連接符來連接，即表示成與關(guān)系；當(dāng)母表達(dá)式為E1E2E3Ek時(shí)，則每一個(gè)子表達(dá)式Ei均由1-連接符連接，即表示成或關(guān)系。493.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）與或形表達(dá)的是一個(gè)事實(shí)，其邏輯值應(yīng)該為“

33、真”。對于與或形中用符號“”連接的部分，其邏輯值如果為真的話，其每一子部分單獨(dú)也必須為真。因此在與或圖中可以表示為“或”，表示每一子部分是獨(dú)立的。而對于與或形中用符號連接的部分，其邏輯值如果為真的話，并不說明其每一子部分也必須為真。只有它們共同在一起才為真，這些子部分之間是相互關(guān)聯(lián)的。因此在與或圖中用k連接符表示為與。503.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）Q( z, a) (R(y) P(y) S(a, y)事實(shí)表達(dá)的與或樹表達(dá)式513.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）與或樹所有結(jié)束于葉節(jié)點(diǎn)的解樹的求法從根節(jié)點(diǎn)(初始結(jié)點(diǎn))開始，正確選擇一個(gè)外向連接符，再從該連接符所指的每一個(gè)后繼節(jié)點(diǎn)出發(fā)，繼續(xù)選

34、一個(gè)外向連接符，如此進(jìn)行下去直到結(jié)束在葉結(jié)點(diǎn)上為止。例: 求上例中的事實(shí)表達(dá)式的與或樹的解樹523.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）533.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）與或樹的性質(zhì):事實(shí)表達(dá)式的子句集與事實(shí)表達(dá)式的與或樹解樹集是一一對應(yīng)的關(guān)系。事實(shí)表達(dá)式的與或樹解樹集中的每個(gè)解樹都對應(yīng)著子句集中的一個(gè)子句。解樹集中每個(gè)解樹的葉節(jié)點(diǎn)上的文字的析取就是子句集中的一個(gè)子句。例: Q( z, a) (R(y) P(y) S(a, y)化為子句集:Q( z, a), R(y)S(a, y), P(y)S(a, y)543.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）3. 與或圖的F規(guī)則變換規(guī)則是建立在某個(gè)問題轄域中普

35、通陳述性知識(shí)的蘊(yùn)涵公式基礎(chǔ)上的。把允許用作規(guī)則的公式類型限制為下列形式 F規(guī)則: LW其中, L為單文字, W為與或形唯一公式。假設(shè)出現(xiàn)在蘊(yùn)涵式中的任何變量都有全稱量化作用于整個(gè)蘊(yùn)涵式。這些事實(shí)和規(guī)則中的一些變量被分離標(biāo)準(zhǔn)化，使得沒有一個(gè)變量出現(xiàn)在一個(gè)以上的規(guī)則中，而且使規(guī)則變量不同于事實(shí)變量。單文字前項(xiàng)的任何蘊(yùn)涵式，不管其量化情況如何都可以化為某種量化轄域?yàn)檎麄€(gè)蘊(yùn)涵式的形式 553.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）F規(guī)則的化簡例: (x) (y) (z) P(x, y, z)(u) Q(x, u)(1) 暫時(shí)消去蘊(yùn)涵符號;(x) (y) (z) P(x, y, z) (u) Q(x, u)(2

36、) 減少否定符號的轄域, 使僅作用于文字;(x) (y) (z) P(x, y, z) (u) Q(x, u)(3) 消去存在量詞Skolem化;(x) (y) P(x, y, f(x,y) (u) Q(x, u)(4) 化成前束式并消去全稱量詞; P(x, y, f(x,y) Q(x, u)(5) 恢復(fù)蘊(yùn)涵式表示?；啚? P(x, y, f(x, y) Q(x, u)563.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）對規(guī)則作單文字前項(xiàng)的限制將大大簡化了應(yīng)用時(shí)的匹配過程，對非單文字前項(xiàng)的情況， (L1L2) W轉(zhuǎn)換成: L1 W, L2 W4. 目標(biāo)公式的表示形式 目標(biāo)公式要求: 子句形即文字的析取式

37、子句形的化簡步驟: 消去蘊(yùn)涵符; 減小否定符號的轄域;對變元標(biāo)準(zhǔn)化（變元換名）; 化為前束范式（量詞左移）; 消去全稱量詞( 對偶形式的skolem化); 進(jìn)行變元換名, 使不同的主析取元具有不同的變元; 消去存在量詞, 變量都受存在量詞的約束;573.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）例: (y) (x) (P (x, y)Q (x, y)用Skolem函數(shù)消去全稱量詞有:(y) (P ( f (y), y)Q ( f (y), y)進(jìn)行變量更名有:(y) (P ( f (y), y)(z) Q ( f (z), z)消去存在量詞:P ( f (y), y) Q ( f (z), z)583.6

38、.1 規(guī)則正向演繹系統(tǒng)（續(xù)）5. 規(guī)則正向演繹推理過程 規(guī)則正向演繹推理過程: 就是不斷的對事實(shí)表達(dá)式的與或樹施以F規(guī)則變換,直到找到一個(gè)一致解樹, 該解樹中的所有葉節(jié)點(diǎn)全部都與目標(biāo)公式中的文字匹配為止。如何進(jìn)行F規(guī)則變換?如何判斷終止?593.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)） 命題邏輯的規(guī)則正向演繹過程 F規(guī)則變換: 如果在與或樹中有一個(gè)葉節(jié)點(diǎn)剛好與某F規(guī)則LW的前件L匹配，則將該葉節(jié)點(diǎn)與L用一個(gè)匹配弧連接起來，將規(guī)則后件W添加到與或樹中。這樣, 就對與或樹用規(guī)則LW實(shí)施了一次變換, 得到了一個(gè)“更新”了的與或樹。例: 事實(shí)表達(dá)式的與或形為:(PQ)R)(S(TU)規(guī)則: S (XY)Z603

39、.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）應(yīng)用F規(guī)則得到的新與或樹613.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）與或樹的變換與子句集的消解分析: 事實(shí)表達(dá)式的子句集: S(PQ), SR, (TU)(PQ), (TU)R 規(guī)則S (XY)Z 對應(yīng)的子句集:S(XZ), S(YZ)規(guī)則變換: 新與或樹對應(yīng)的子句集 (TU)(PQ), (TU)R, (XZ)(PQ),(XZ)R, (YZ)(PQ), (YZ)R 623.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）消解: 將事實(shí)表達(dá)式和規(guī)則子句集合并S(PQ), SR, (TU)(PQ), (TU)R,S(XZ), S(YZ)作如下消解:S(PQ), S(XZ): (XZ)(PQ

40、)S(PQ), S(YZ): (YZ)(PQ)SR, S(XZ): (XZ)RSR, S(YZ): (YZ)R得新的子句集: (TU)(PQ), (TU)R, (XZ)(PQ), (XZ)R,(YZ)(PQ), (YZ)R 633.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）結(jié)論: 與或樹的規(guī)則變換與消解之間具有一定的聯(lián)系。應(yīng)用一條規(guī)則到與或樹的過程,以極其經(jīng)濟(jì)方式的達(dá)到了用其它方法要進(jìn)行的多次消解才能達(dá)到的目的。643.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）命題邏輯的規(guī)則演繹過程例: 事實(shí)表達(dá)式：AB規(guī)則集：A CDB EG目標(biāo)公式：CG653.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)） 謂詞邏輯的規(guī)則正向演繹過程a) 事實(shí)

41、表達(dá)式進(jìn)行與或樹表示;b) 規(guī)則轉(zhuǎn)換成F規(guī)則L W, 其中L為單文字,W為與或形;c) 目標(biāo)表達(dá)式變換成子句形;d) 對與或樹進(jìn)行F規(guī)則變換;e) 結(jié)束條件: 找到所有葉節(jié)點(diǎn)都與目標(biāo)節(jié)點(diǎn)匹配的一致解樹。663.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）F規(guī)則變換:設(shè)與或樹中有一個(gè)端節(jié)點(diǎn)的文字L和L可合一, mgu是u，則這條規(guī)則可應(yīng)用, 這時(shí)用匹配弧連接的后裔節(jié)點(diǎn)是L，它是規(guī)則后項(xiàng)Wu對應(yīng)的與或樹表示的根節(jié)點(diǎn), 在匹配弧上標(biāo)記有u, 表示用u置換后可與規(guī)則匹配。673.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）例:事實(shí)與或形表示: P(A,y)(Q(x,A)R(B,y)規(guī)則蘊(yùn)涵式: P(z, B) (S(z)X(B)

42、應(yīng)用一條規(guī)則的新與或樹683.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）上圖應(yīng)用規(guī)則變換后得到的與或樹有兩個(gè)解樹,對應(yīng)的兩個(gè)子句是S(A)X(B)Q(x, A)S(A)X(B)R(B, B)事實(shí)和規(guī)則組成的子句集, 對文字P進(jìn)行歸結(jié): P(A,y)Q(x,A) P(A,y)R(B,y) P(z, B) S(z)X(B) R(B,B)S(A)X(B) 歸結(jié)=A/z, B/y Q(x,A)S(A)X(B) 歸結(jié)=A/z, B/y結(jié)論: 規(guī)則的應(yīng)用結(jié)果是得到這條規(guī)則的應(yīng)用演繹出所有的邏輯推論。693.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）一致解樹一個(gè)具有一致置換的解樹稱為一致解樹。一致置換: 當(dāng)置換集沒有矛盾存在時(shí)，稱

43、該置換集是一致的，否則就是不一致的。例: 1= a/x, b/y 和2= b/x, c/z例: 設(shè)已知事實(shí)的與或形表示為:P(x,y)(Q(x)R(v,y)F規(guī)則為: P(u, v) S(u) N(v)目標(biāo)公式為:S(a) N(b) Q(c)703.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）謂詞邏輯的規(guī)則演繹過程713.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）一致置換的定義及判定算法設(shè)有一個(gè)置換集u1,u2,un, 其中ui =t1/v1,t2/v2, tm/vm是置換對集合,ti是項(xiàng),vi是變量。根據(jù)這個(gè)置換集，再定義兩個(gè)表達(dá)式:U1=v11,v12,v1m1,v21,v2m2,vn1,vnmnU2=t11,t1

44、2,t1m1,t21,t2m2,tn1,tnmn置換( u1,u2,un)稱為一致的, 當(dāng)且僅當(dāng)U1和U2是可合一的。(u1,u2,un )的合一復(fù)合(unifyingcomposition) u是U1和U2的最一般合一。723.6.1 規(guī)則正向演繹系統(tǒng)（續(xù)）幾個(gè)合一復(fù)合結(jié)果的實(shí)例733.6.2 規(guī)則逆向演繹系統(tǒng)規(guī)則逆向演繹推理: 從目標(biāo)表達(dá)式出發(fā)，反方向使用規(guī)則（B規(guī)則）對表示目標(biāo)的與或樹進(jìn)行變換，直到得到含有事實(shí)節(jié)點(diǎn)的一致解樹。目標(biāo)表達(dá)式: 目標(biāo)的與或樹事實(shí)表達(dá)式: 限制為文字的合取形。規(guī)則: B規(guī)則, WL 其中, W是任意形式的與或形，L是單文字終止條件: 得到含有事實(shí)節(jié)點(diǎn)的一致解樹。

45、743.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）1. 目標(biāo)表達(dá)式的與或形變換2. 目標(biāo)公式的與或樹表示3. B規(guī)則的表示形式4. 已知事實(shí)的表示形式5. 規(guī)則逆向演繹推理過程753.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）1. 目標(biāo)表達(dá)式的與或形變換(1) 消去”蘊(yùn)含”和”雙條件”符號;(2) 減小否定符號的轄域, 使否定符號只作用于原子公式;(3) 利用Skolem函數(shù)消去全稱量詞;(4) 對變量進(jìn)行換名，使得不同的主合取元，具有不同的變量名;(5) 隱去存在量詞，默認(rèn)公式中的變量受存在量詞約束。例: (y)(x)(P(x) (Q(x,y)(R(x)S(y)P(f(z) (Q(f(y),y) (R(f(y) S

46、(y)763.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）2. 目標(biāo)公式的與或樹表示規(guī)定子表達(dá)式間的析取用1連接符連接，即表示為“或”的關(guān)系，而子表達(dá)式的合取用k連接符連接，即表示為“與”的關(guān)系。目標(biāo)公式的與或樹表示773.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）與或樹解樹對應(yīng)的子句(文字的合取):P(f(z), Q(f(y),y)R(f(y), Q(f(y),y)S(y)目標(biāo)公式的析取范式中子句:P(f(z), Q(f(y),y)R(f(y), Q(f(y),y)S(y)3. B規(guī)則的表示形式 B規(guī)則形式限制為:WL其中, W是任意形式的與或形，L是單文字，它表示L可以由W推導(dǎo)出。783.6.2 規(guī)則逆向演繹系統(tǒng)（

47、續(xù)）B規(guī)則化簡：其中的變量受全稱量詞約束，如果有存在量詞，則將其Skolem化，消去存在量詞。當(dāng)B規(guī)則為WL1L2時(shí)，則可化簡為兩條規(guī)則WL1和WL2來處理。4. 已知事實(shí)的表示形式事實(shí)表達(dá)式均限制為文字合取形, 它可以表示為一個(gè)文字集并且進(jìn)行了普通的Skolem化簡，變量受全稱量詞約束。793.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）5. 規(guī)則逆向演繹推理過程: 就是不斷的對目標(biāo)公式的與或樹施以B規(guī)則變換，直到找到一個(gè)一致解樹，該解樹中的所有葉節(jié)點(diǎn)全部都與事實(shí)表達(dá)式中的文字匹配為止。B規(guī)則匹配和變換匹配:當(dāng)與或樹中有某個(gè)端點(diǎn)的文字和L可合一且mgu為u時(shí)，則B規(guī)則可應(yīng)用變換: 求出該葉節(jié)點(diǎn)與L的mgu

48、 u，將該葉節(jié)點(diǎn)與L用一個(gè)匹配弧連接起來，用u對W進(jìn)行置換，然后將Wu添加到與或樹中。成功終止條件: 與或樹包含終止在事實(shí)節(jié)點(diǎn)上的一致解樹。803.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）例: 設(shè)有如下事實(shí)和規(guī)則:事實(shí)：F1: DOG(FIDO)；狗的名字叫FidoF2: 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)

49、；溫順而又不叫的東西是不值得害怕的R3: DOG(x3) ANIMAL(x3)；狗為動(dòng)物R4: CAT(x4) ANIMAL(x4)；貓為動(dòng)物R5: MEOWS(x5) CAT(x5)；貓咪是貓問題：是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?813.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）1. 目標(biāo)表示為與或樹 目標(biāo)用謂詞公式表示:(x)(y)(CAT(x)DOG(y)AFRAID(x,y) 消去存在量詞化為與或形:CAT(x)DOG(y)AFRAID(x,y) 目標(biāo)公式表示成與或樹2. 規(guī)則符合B規(guī)則要求不需變換3. 事實(shí)是文字的合取形 DOG(FIDO), BARKS(FIDO), WAG

50、STAIL(FIDO), MEOWS(MYRTLE)4. 規(guī)則逆向推理: 分別應(yīng)用規(guī)則R5, R2, R1變換5. 找到一致解樹, 成功終止。82規(guī)則逆向演繹推理過程例833.6.2 規(guī)則逆向演繹系統(tǒng)（續(xù)）一致解樹.所有匹配弧上的置換集：x/x5，MYRTLE/x, FIDO/y, x/y2,y/x2, FIDO/y, y/x1, FIDO/y,FIDO/y沒有矛盾, 是一致置換集。回答語句：CAT(MYRTLE)DOG(FIDO)AFRAID(MYRTLE,FIDO)84853.6.3 規(guī)則雙向演繹系統(tǒng)正向演繹和逆向演繹推理的局限性:正向演繹推理要求: 目標(biāo)公式必須可化簡為文字的析取式。逆向

51、演繹推理要求: 事實(shí)表達(dá)式必須可化簡為文字的合取式。限制了正向和逆向推理的應(yīng)用范圍。規(guī)則雙向演繹推理任意形式的事實(shí)表達(dá)式和目標(biāo)公式。同時(shí)采用規(guī)則正向和規(guī)則逆向推理。863.6.3 規(guī)則雙向演繹系統(tǒng)（續(xù)）規(guī)則雙向演繹推理綜合數(shù)據(jù)庫: 事實(shí)表達(dá)式的與或樹(簡稱事實(shí)樹)和目標(biāo)公式的與或樹(簡稱目標(biāo)樹)。規(guī)則庫: F規(guī)則和B規(guī)則。規(guī)則雙向演繹推理: 運(yùn)用F規(guī)則對事實(shí)樹進(jìn)行變換, 運(yùn)用B規(guī)則對目標(biāo)樹進(jìn)行變換。終止條件: 事實(shí)樹與目標(biāo)樹的某個(gè)交接處。缺點(diǎn)：判斷困難, 較復(fù)雜。873.6.3 規(guī)則雙向演繹系統(tǒng)（續(xù)）終止條件:若標(biāo)記于事實(shí)文字節(jié)點(diǎn)L1和目標(biāo)文字節(jié)點(diǎn)L2上的文字有mgu u, 則在L1和L2之間

52、建立匹配棱線連接, 并用對應(yīng)的mgu u來標(biāo)記匹配棱線。對于初始綜合數(shù)據(jù)庫, 事實(shí)樹和目標(biāo)樹間的匹配棱線必須在葉節(jié)點(diǎn)之間。當(dāng)用F規(guī)則和B規(guī)則對圖進(jìn)行擴(kuò)展之后, 匹配就可以出現(xiàn)在任何文字節(jié)點(diǎn)上。例: 設(shè)已知事實(shí)和目標(biāo)分別為:事實(shí): Q(x,a) (R(x) S(a)目標(biāo): P(f(y) (Q(f(y),y) (R(f(y) S(y)88規(guī)則雙向推理過程例893.6.3 規(guī)則雙向演繹系統(tǒng)（續(xù)）終止條件:當(dāng)在事實(shí)樹與目標(biāo)樹之間建立了所有的可能匹配棱線之后, 目標(biāo)樹中根節(jié)點(diǎn)上的表達(dá)式是否已經(jīng)根據(jù)事實(shí)樹中根節(jié)點(diǎn)上的表達(dá)式和規(guī)則得到證明的問題仍然需要判定。判斷方法: 一個(gè)建立在事實(shí)節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)間一種叫做

53、CANCEL的對稱關(guān)系的基礎(chǔ)上的判定方法。903.6.3 規(guī)則雙向演繹系統(tǒng)（續(xù)）CANCEL的遞歸定義: 如果(n, m)中有一個(gè)為事實(shí)節(jié)點(diǎn), 另一個(gè)為目標(biāo)節(jié)點(diǎn), 如果n和m都由可合一的文字所標(biāo)記, 則稱這兩節(jié)點(diǎn)n和m互相CANCEL(即互相抵消), 否則如果n有外向k線連接符接至一個(gè)后繼節(jié)點(diǎn)集 Si 且對此集的每個(gè)元素CANCEL(Si, m) 都成立, 那么也稱這兩節(jié)點(diǎn)n和m互相CANCEL。913.6.3 規(guī)則雙向演繹系統(tǒng)（續(xù)）當(dāng)事實(shí)樹的根節(jié)點(diǎn)和目標(biāo)樹的根節(jié)點(diǎn)互相CANCEL時(shí), 我們得到一個(gè)候補(bǔ)解。在事實(shí)和目標(biāo)樹內(nèi)證明該目標(biāo)根節(jié)點(diǎn)和事實(shí)根節(jié)點(diǎn)互相CANCEL的圖結(jié)構(gòu)叫做候補(bǔ)CANCEL

54、圖。如果候補(bǔ)CANCEL圖中所有匹配的mgu都是一致的，那么這個(gè)候補(bǔ)解就是一個(gè)實(shí)際解。找到實(shí)際解, 推理成功, 目標(biāo)得證。923.6.3 規(guī)則雙向演繹系統(tǒng)（續(xù)）在本例中:黃色子圖為候選CANCEL圖置換集: f(y)/x, a/y 無矛盾, 是一致的。所以推理成功。933.7 產(chǎn)生式系統(tǒng)3.7.1 產(chǎn)生式系統(tǒng)的組成3.7.2 產(chǎn)生式系統(tǒng)的推理3.7.3 產(chǎn)生式系統(tǒng)的控制策略產(chǎn)生式系統(tǒng)(production system)首先是由波斯特(Post)于1943年提出的產(chǎn)生式規(guī)則(production rule)而得名的。他們用這種規(guī)則對符號串進(jìn)行置換運(yùn)算。后來，美國的紐厄爾和西蒙利用這個(gè)原理建立一

55、個(gè)人類的認(rèn)知模型(1965年)。同時(shí)，斯坦福大學(xué)利用產(chǎn)生式系統(tǒng)結(jié)構(gòu)設(shè)計(jì)出第一個(gè)專家系統(tǒng)DENDRAL。943.7 產(chǎn)生式系統(tǒng)（續(xù)）產(chǎn)生式系統(tǒng)用來描述若干個(gè)不同的以一個(gè)基本概念為基礎(chǔ)的系統(tǒng)。這個(gè)基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。在產(chǎn)生式系統(tǒng)中，論域的知識(shí)分為兩部分：用事實(shí)表示靜態(tài)知識(shí)，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識(shí)庫主要用于存儲(chǔ)規(guī)則，因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)(rule based system)。953.7 產(chǎn)生式系統(tǒng)（續(xù)）產(chǎn)生式系統(tǒng)中的知識(shí)表示1. 事實(shí)的表示：確定性的知識(shí)：命題、謂詞、三元組( 對象, 屬性, 值)

56、或(關(guān)系, 對象1, 對象2)老李和老張是朋友:（Friend, Lee, Chang）不確定性的知識(shí)：四元組(對象，屬性，值，可信度因子)極少數(shù)花的顏色是黑的:（花，顏色，黑，0.1)963.7 產(chǎn)生式系統(tǒng)（續(xù)）2. 推理過程和行為(規(guī)則)的表示產(chǎn)生式或規(guī)則：P QIF P THEN QP是產(chǎn)生式的前提，或稱為前件是一組結(jié)論或操作，或稱為后件IF (動(dòng)物,本領(lǐng),會(huì)下蛋) AND (動(dòng)物,本領(lǐng),會(huì)飛) THEN (動(dòng)物,類別,鳥)IF (病人,癥狀,咳嗽) AND (病人,癥狀,流涕)THEN (病人,疾病,感冒,0.85)973.7.1 產(chǎn)生式系統(tǒng)的組成1. 綜合數(shù)據(jù)庫：全局?jǐn)?shù)據(jù)庫，事實(shí)數(shù)據(jù)

57、庫2. 產(chǎn)生式規(guī)則庫：產(chǎn)生式規(guī)則3. 控制系統(tǒng)：控制策略, 推理機(jī)983.7.1 產(chǎn)生式系統(tǒng)的組成（續(xù)）1. 綜合數(shù)據(jù)庫是一個(gè)用來存放與求解問題有關(guān)的各種當(dāng)前信息的數(shù)據(jù)結(jié)構(gòu)。問題的初始狀態(tài)、事實(shí)、證據(jù)、中間推理結(jié)論及最后結(jié)果等。2. 產(chǎn)生式規(guī)則庫是用來存放與求解問題有關(guān)的某個(gè)領(lǐng)域知識(shí)的規(guī)則的集合及其交換規(guī)則。這里所說的產(chǎn)生式規(guī)則和謂詞邏輯中所討論的產(chǎn)生式規(guī)則，從形式上看都采用了IF-THEN的形式，但這里所討論的產(chǎn)生式更為通用。在謂詞運(yùn)算中的IF-THEN實(shí)質(zhì)上是表示了蘊(yùn)涵關(guān)系。也就是說要滿足相應(yīng)的真值表。這里所討論的條件和操作部分除了可以用謂詞邏輯表示外，還可以有其他多種表示形式，并不受相應(yīng)

58、的真值表的限制。 993.7.1 產(chǎn)生式系統(tǒng)的組成（續(xù)）3. 控制系統(tǒng)：(1) 匹配在這一步，把當(dāng)前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。當(dāng)按規(guī)則的操作部分去執(zhí)行時(shí)，稱這條規(guī)則為啟用規(guī)則。被觸發(fā)的規(guī)則不一定總是啟用規(guī)則，因?yàn)榭赡芡瑫r(shí)有幾條規(guī)則的條件部分被滿足，這就要在解決沖突步驟中來解決這個(gè)問題。在復(fù)雜的情況下，在數(shù)據(jù)庫和規(guī)則的條件部分之間可能要進(jìn)行近似匹配。 1003.7.1 產(chǎn)生式系統(tǒng)的組成（續(xù)）(2) 沖突解決 當(dāng)有一條以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時(shí)，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。 (a) 專一性排序 如果某一規(guī)則條件部分規(guī)定的

59、情況，比另一規(guī)則條件部分規(guī)定的情況更有針對性，則這條規(guī)則有較高的優(yōu)先級。 (b) 規(guī)則排序如果規(guī)則編排的順序就表示了啟用的優(yōu)先級，則稱之為規(guī)則排序。 (c) 數(shù)據(jù)排序把規(guī)則條件部分的所有條件按優(yōu)先級次序編排起來，運(yùn)行時(shí)首先使用在條件部分包含較高優(yōu)先級數(shù)據(jù)的規(guī)則。(d) 規(guī)模排序按規(guī)則的條件部分的規(guī)模排列優(yōu)先級，優(yōu)先使用被滿足的條件較多的規(guī)則。(e) 就近排序把最近使用的規(guī)則放在最優(yōu)先的位置。這和人類的行為有相似之處。如果某一規(guī)則經(jīng)常被使用，則人們傾向于更多地使用這條規(guī)則。 (f) 上下文限制把產(chǎn)生式規(guī)則按它們所描述的上下文分組，也就是說按上下文對規(guī)則分組。在某種上下文條件下，只能從與其相對應(yīng)的

60、那組規(guī)則中選擇可應(yīng)用的規(guī)則。不同的系統(tǒng)，使用上述這些策略的不同組合。如何選擇沖突解決策略完全是啟發(fā)式的。1013.7.1 產(chǎn)生式系統(tǒng)的組成（續(xù)）(3) 操作操作就是執(zhí)行規(guī)則的操作部分，經(jīng)過操作以后，當(dāng)前數(shù)據(jù)庫將被修改。然后，其他的規(guī)則有可能被使用。 1023.7.2 產(chǎn)生式系統(tǒng)的推理1033.7.2 產(chǎn)生式系統(tǒng)的推理（續(xù)）例：用于動(dòng)物識(shí)別的產(chǎn)生式系統(tǒng)1043.7.2 產(chǎn)生式系統(tǒng)的推理（續(xù)）初始綜合數(shù)據(jù)庫：有暗斑點(diǎn)，長脖子，長腿，有奶，有蹄目標(biāo)集合：長頸鹿，斑馬順序選擇規(guī)則試與事實(shí)匹配，將匹配成功的規(guī)則執(zhí)行并做標(biāo)記： r1匹配失敗，r2匹配成功:綜合數(shù)據(jù)庫：有暗斑點(diǎn)，長脖子，長腿，有奶，有蹄，哺