華中科技大學人工智能第四章確定性推理1

1、12022-6-27第四章第四章 確定性推理確定性推理22022-6-274.1 確定性確定性推理推理概述概述第四章 確定性推理 4.1概述32022-6-27推推 理理l推理是指按照某種策略從巳知事實出發(fā)去推出結論的過程l 智能系統(tǒng)的推理過程實際上就是一種思維過程。l智能系統(tǒng)的推理過程是通過推理機來完成的。l推理機就是智能系統(tǒng)中用來實現(xiàn)推理的程序。l按照推理過程所用知識的確定性，推理可分為確定性推理和不確定性推理。第四章 確定性推理 4.1概述42022-6-27事事 實實l事實是推理過程中按知識表示方式表示的已知的知識l推理所用的事實可分為兩種情況:與求解問題有關的初始證據(jù)推理過程中所得到

2、的中間結論。第四章 確定性推理 4.1概述 52022-6-27推理的基本問題推理的基本問題l智能系統(tǒng)的推理包括兩個基本問題：一個是推理的方法一個是推理的控制策略l 推理方法主要解決：在推理過程中前提與結論之間的邏輯關系在非精確性推理中不確定性的傳遞問題第四章 確定性推理 4.1概述 62022-6-27推理方法的分類推理方法的分類l推理可以有多種不同的分類方法l按照推理的邏輯基礎分類：演繹推理歸納推理默認推理l按照所用知識的確定性分類：確定性推理不確定性推理l按照推理過程的單調性分類（推理過程所得到的結論是否越來越接近目標）：單調推理非單調推理第四章 確定性推理 4.1概述 72022-6-

3、27演繹推理演繹推理l 從已知的一般性知識出發(fā)，去推出蘊含在這些已知知識中的適合于某種個別情況的結論。l它是一種由一般到個別的推理方法。l核心是三段論第四章 確定性推理 4.1概述 82022-6-27歸納推理l 從一類事物的大量特殊事例出發(fā)，去推出該類事物的一般性結論。l它是一種由個別到一般的推理方法。l基本思想：先從已知事實中猜測出一個結論，然后對這個結論的正確性加以證明確認l數(shù)學歸納法就是歸納推理的一種典型例子。l按照所選事例的廣泛性，歸納推理可分為：完全歸納推理和不完全歸納推理；l按照推理所使用的方法可分為：枚舉歸納推理、類比歸納推理、統(tǒng)計歸納推理和差異歸納推理等。第四章 確定性推理

4、4.1概述 92022-6-27默認推理l 在知識不完全的倩況下，假設某些條件已經(jīng)具備所進行的推理，因此也稱為缺省推理。l在推理過程中如果發(fā)現(xiàn)原先的假設不正確，就撤銷原來的假設以及由此假設所推出的所有結論。l重新按新情況進行推理。l解決了在一個不完備的知識集中進行推理的問題。第四章 確定性推理 4.1概述 102022-6-27推理過程的單調性l按照推理過程所得到的結論是否越來越接近日標，推理可分為單調推理與非單調推理。l單調推理：在推理過程中，每當使用新的知識后，所得到的結論會越來越接近于目標不會出現(xiàn)反復情況，即不會由于新知識的加入否定了前面推出的結論。l非單調推理：在推理過程中，當某些新知

5、識加入后，會否定原來推出的結論。l非單調推理往往是在知識不完全的情況下發(fā)生的。第四章 確定性推理 4.1概述 112022-6-27推理控制策略推理控制策略l推理的控制策略是在推理過程中采用的、解決如何使用領域知識使推理過程盡快達到目標的策略。第四章 確定性推理 4.1概述 122022-6-27推理控制策略推理控制策略分類分類l智能系統(tǒng)的推理過程一般表現(xiàn)為一種搜索過程，因此，推理的控制策略又可分為推理策略和搜索策略。l推理策略主要解決推理方向、沖突消解等問題。l搜索策略主要解決推理線路、推理效果、推理效率等問題。第四章 確定性推理 4.1概述 132022-6-27推理方向推理方向l推理方向

6、確定推理過程是從初始證據(jù)開始到目標，還是從目標開始到初始證據(jù)。按照對推理方向的控制，推理可分為正向推理、逆向推理、混合推理及雙向推理四種情況。第四章 確定性推理 4.1概述 142022-6-27正向正向推理推理l正向推理是一種從已知事實出發(fā)、正向使用推理規(guī)則的推理方式，亦稱為數(shù)據(jù)驅動推理。l基本思想是：用戶需要事先提供一組初始證據(jù)，并將其放入綜合數(shù)據(jù)庫。推理機根據(jù)綜合數(shù)據(jù)庫中的已有事實，到知識庫中尋找當前可用知識，形成一個當前可用知識集。按照沖突消解策略，從該知識集中選擇一條知識進行推理，并將新推出的事實加入綜合數(shù)據(jù)庫，作為后面繼續(xù)推理時可用的巳知事實，重復這一過程，直到求出所需要的解或者知

7、識庫中再無可用知識為止第四章 確定性推理 4.1概述 152022-6-27逆向逆向推理推理l逆向推理是一種從以某個假設目標作為出發(fā)點的推理方法，亦稱為目標驅動推理l基本思想是：將要求證的目標(稱為假設)構成一個假設集。取一個假設對其進行驗證，若在綜合數(shù)據(jù)庫里，則假設成立若能被用戶認定為事實，則假設成立，并放入綜合數(shù)據(jù)庫若可由知識庫中的一個或多個知識導出，則這些知識構成可用知識集。按照沖突消解策略，從該知識集中選擇一條知識，將其前提中的所有子條件作為新的假設加入假設集。重復這一過程，直到假設集為空或假設集非空但可用知識集空為止第四章 確定性推理 4.1概述 162022-6-27混合推理混合推

8、理l 正向推理和逆向推理都有各自的優(yōu)缺點。當問題較復雜時，單獨使用其中哪一種，都會影響到推理效率。l為了取長補短可將它們結合起來使用。l這種把正向推理和逆向推理結合起來所進行的推理稱為混合推理。第四章 確定性推理 4.1概述 172022-6-27混合推理的實現(xiàn)方法混合推理的實現(xiàn)方法l混合推理可有多種具體的實現(xiàn)方法混合推理可有多種具體的實現(xiàn)方法先正向推理，后逆向推理的方法先逆向推理，后正向推理的方法采用隨機選擇正向和逆向推理的方法（雙向混合推理）第四章 確定性推理 4.1概述 182022-6-27混合推理的適用場合混合推理的適用場合l已知事實不夠充分。l由正向推理推出的結論可信度不高l希望得

9、出更多的結論l希望從正反兩個方向同時進行推理第四章 確定性推理 4.1概述 192022-6-27沖突消解策略沖突消解策略l沖突消解策略是指當推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策略。l沖突消解的基本思想是對可用知識進行排序。l常用的沖突消解策略有：特殊知識優(yōu)先新鮮知識優(yōu)先差異性大的知識優(yōu)先領域特點知識優(yōu)先上下文關系知識優(yōu)先前提條件少的知識優(yōu)先第四章 確定性推理 4.1概述 202022-6-27自然演繹推理自然演繹推理l 從一組己知為真的事實出發(fā)，直接運用經(jīng)典邏輯中的推理規(guī)則推出結論的過程稱為自然演繹推理。l在自然演繹推理中，需要避免兩類錯誤：肯定后件的

10、錯誤和否定前件的錯誤。l優(yōu)點：定理證明過程自然，易于理解，有豐富的推理規(guī)則l主要缺點：容易產生知識爆炸，推理過程中得到的中間結論一般按指數(shù)規(guī)律遞增，對于復雜問題的推理不利，甚至難以實現(xiàn)。l因此，提出了歸結演繹推理因此，提出了歸結演繹推理第四章 確定性推理 4.2自然演繹推理 212022-6-27歸結演繹推理歸結演繹推理l 歸結演繹推理是一種基于歸結原理的推理方法。l歸結原理亦稱消解原理，是魯賓遜1965年提出的l歸結演繹推理實際上是一種“反正法”，基本思想： 推理就是要對前提P和結論Q，證明P Q永真。這就要證明P Q在任何一個非空的個體域上都是永真的。這將是非常困難的，甚至是不可實現(xiàn)的。而

11、用反證法，只要能夠證明(P Q)是不可滿足的。第四章 確定性推理 4.3歸結演繹推理 222022-6-27子句和子句集子句和子句集l原子謂詞公式及其否定都稱為文字l文字的析取構成的公式稱為子句l不包含任何文字的子句稱為空了句l空子句不包含任何文字，因此，不能被任何指派所滿足l所以空子句是不可滿足的l子句集中的子句之間是合取關系l含空子句的子句集也就一定是不可滿足的。第四章 確定性推理 4.3歸結演繹推理 232022-6-27謂詞公式轉化為子句集謂詞公式轉化為子句集l消去蘊涵符號： PQ取代PQl減少否定符號的管轄域l對變量標準化l消去存在量詞l化為前束形l化為合取范式： 如：P(PQ）(P

12、Q）l消去全稱量詞l獲得子句集l更換變量名 第四章 確定性推理 4.3歸結演繹推理 242022-6-27化子句集例化子句集例例：(z) (x)(y)(P(x) Q(x) R(y) U(z)1, 消蘊涵符理論根據(jù)：a b = a b(z) (x)(y)(P(x) Q(x) R(y) U(z)2, 移動否定符理論根據(jù)：(a b) = a b (a b) = a b (x)P(x)=(x)P(x) (x)P(x)=(x)P(x) (z) (x)(y)(P(x) Q(x) R(y) U(z)第四章 確定性推理 4.3歸結演繹推理 252022-6-27化子句集例化子句集例（續(xù)1）3, 變量標準化即：

13、對于不同的約束，對應于不同的變量(x)A(x) (x)B(x) = (x)A(x) (y)B(y)4, 量詞左移 (x)A(x) (y)B(y) = (x) (y) A(x) B(y)5, 消存在量詞 (skolem化）原則：對于一個受存在量詞約束的變量，如果他不受全程量詞約束，則該變量用一個常量代替，如果他受全程量詞約束，則該變量用一個函數(shù)代替。 (z) (x)(y)(P(x) Q(x) R(y) U(z) = (x) (P(x) Q(x) R(f(x) U(a)第四章 確定性推理 4.3歸結演繹推理 262022-6-27化子句集例（續(xù)化子句集例（續(xù)2）6, 化為合取范式即(ab) (cd

14、) (ef)的形式 (x)(P(x) Q(x) R(f(x)U(a)= (x)(P(x) Q(x) R(f(x)U(a)= (x)P(x) R(f(x)U(a) Q(x) R(f(x)U(a)7, 隱去全程量詞 P(x) R(f(x)U(a) Q(x) R(f(x)U(a)第四章 確定性推理 4.3歸結演繹推理 272022-6-27化子句集例化子句集例（續(xù)3）8, 表示為子句集 P(x) R(f(x)U(a), Q(x) R(f(x)U(a)9, 變量標準化（變量換名）P(x1) R(f(x1)U(a), Q(x2) R(f(x2)U(a)第四章 確定性推理 4.3歸結演繹推理 282022

15、-6-27歸結歸結(消解消解) )原理原理基本思想基本思想l首先把欲證明問題的結論否定，并加入子句集，得到一個擴充的子句集S。l檢驗子句集S是否含有空子句l若不含空子句，則繼續(xù)使用歸結法，在子句集中選擇合適的子句進行歸結l直至導出空子句或不能繼續(xù)歸結為止。第四章 確定性推理 4.3歸結演繹推理 292022-6-27歸結歸結原理分類原理分類l 魯賓遜歸結原理可分為:命題邏輯歸結原理謂詞邏輯歸結原理第四章 確定性推理 4.3歸結演繹推理 302022-6-27歸結式歸結式l歸結推理的核心是求兩個子句的歸結式l若P是原子謂詞公式，則稱P與P為互補文字l設C1和C2是子句集中的任意兩個子句l如果C1

16、中的文字L1與C2中的文字L2互補l那么可從C1和C2中分別消去L1和L2l并將C1和C2中余下的部分按析取關系構成一個新的子句C12，l則稱這一過程為歸結，l稱C12為C1和C2的歸結式，C1和C2為C12的親本子句。第四章 確定性推理 4.3歸結演繹推理 312022-6-27消解過程舉例消解過程舉例l E2 E1 （前提）l E2 E3 （前提）l （消解式） E1 E3 （結論） 第四章 確定性推理 4.2歸結演繹推理 322022-6-27命題邏輯的消解推理舉例命題邏輯的消解推理舉例假言推理：P PQ (PQ）消解式：Q合并：PQ PQ 消解式：QQ = Q 重言式：P Q PQ 消

17、解式：PP 或 QQ 空子句：P P 消解式：NIL 三段論： PQ (PQ） QR (QR）消解式：PR (PQ） 第四章 確定性推理 4.2歸結演繹推理 332022-6-27謂詞邏輯的消解推理舉例謂詞邏輯的消解推理舉例B(x) B(x)C(x）消解式：C(x)P(x)Q(x） Qf(y)消解式：Pf(y)置換：f(y)/xPx,f(y)Q(x)Rf(a),y Pf(f(a),zR(z,w） 消解式：Qf(f(a)Rf(a),yRf(y),w 置換：f(f(a)/x, f(y)/z第四章 確定性推理 4.2歸結演繹推理 342022-6-27消解反演消解反演l消解反演是利用消解原理進行推理

18、的過程。l消解反演的推理過程:給定公式集S和目標公式L證明公式L的步驟如下： l否定L ，得L l把L 添加到S中去l把新產生的集合L ,S化成子句集l應用消解原理力圖推導出一個表示矛盾的空子句 第四章 確定性推理 4.2歸結演繹推理 352022-6-27命題邏輯消解反演的例子命題邏輯消解反演的例子設公理集：P, (PQ) R,(ST) Q,T求證：R子句集：(1) P(2) PQR(3) SQ(4) TQ(5) T(6) R（目標求反）化子句集： (PQ) R= (PQ)R= PQR (ST) Q= (ST)Q= (ST)Q= (SQ) (TQ)= SQ, TQ第四章 確定性推理 4.2歸

19、結演繹推理 362022-6-27命題邏輯消解反演的例子（續(xù)）命題邏輯消解反演的例子（續(xù)）子句集：(1) P(2) PQR(3) SQ(4) TQ(5) T(6) R（目標求反）歸結：(7) PQ (2, 6)(8) Q (1, 7) (9) T (4, 8) (10) nil (5, 9)第四章 確定性推理 4.2歸結演繹推理 372022-6-27謂詞邏輯消解反演的例子謂詞邏輯消解反演的例子l例：已知：If Fido goes wherever John goes and if John is at school, where is Fido ?(x)AT(John, x) AT(Fido

20、, x) AT(John, School)求證：(x)AT(Fido, x)子句集：AT(John, y) AT(Fido, y)AT(John, School)AT(Fido, x) ( (x)AT(Fido, x) = ( x) AT(Fido, x) )第四章 確定性推理 4.2歸結演繹推理 382022-6-27AT(Fido, x)AT(John, y) AT(Fido, y)子句集： AT(John, y) AT(Fido, y)AT(John, School)AT(Fido, x)AT(John, x)x/yAT(John, School)nilSchool/xAT(Fido,

21、School)謂詞邏輯消解反演的例子（續(xù)）謂詞邏輯消解反演的例子（續(xù)）第四章 確定性推理 4.2歸結演繹推理 392022-6-27基于消解原理的問答系統(tǒng)基于消解原理的問答系統(tǒng)l消解原理主要用來解決證明的問題，但有時我們希望得到如x=?時，W(x)為真的回答l消解原理是將結論的否定作為前提進行歸結，而為了回答問題，用由結論的否定構成的重言式作為前提進行歸結，得到的結論是問題的回答而不是空語句。這個過程稱為修改證明過程（或修改歸結過程）。l下面以猴子摘香蕉問題為例來說明第四章 確定性推理 4.2歸結演繹推理 402022-6-27用消解原理解猴子摘香蕉問題用消解原理解猴子摘香蕉問題l為了把狀態(tài)空

22、間的算符描述與謂詞演算結合起來，將狀態(tài)添到謂詞上；l將算符看成是把一種狀態(tài)映射成另一種狀態(tài)的函數(shù)；l問題簡化成沒有goto()規(guī)則；c第四章 確定性推理 4.2歸結演繹推理 412022-6-27猴子摘香蕉問題的表示猴子摘香蕉問題的表示問題可以描述如下：1, ONBOX(s0)2, (x)(s)(ONBOX(s) AT(box, x, push(x, s)3, (s)(ONBOX(climbbox(s)4, (s)(ONBOX(s) AT(box, c, s) HB(grasp(s)5, (x)(s)(AT(box, x, s) AT(box, x, climb(s)求解：(s)HB(s)第四

23、章 確定性推理 4.2歸結演繹推理 422022-6-27猴子摘香蕉問題的子句集猴子摘香蕉問題的子句集1, ON(s0)2, ON(s1) AT(box, x1, push(x1, s1)3, ON(climb(s2)4, ON(s3) AT(box, c, s3) HB(grasp(s3)5, AT(box, x4, s4) AT(box, x4, climb(s4)6, HB(s5)第四章 確定性推理 4.2歸結演繹推理 432022-6-27HB(s5)ON(s3) AT(box, c, s3) HB(grasp(s3)ON(s3) AT(box, c, s3)grasp(s3)/s5O

24、N(climb(s2)climb(s2)/s3 AT(box, c, climb(s2) ON(s0) ON(s1) AT(box, x1, push(x1, s1)s0/s1AT(box, x1, push(x1, s0)AT(box, x4, s4) AT(box, x4, climb(s4)x4/x1,push(x4,s0)/s4AT(box, x4, climb(push(x4,s0)NILc/x4,push(c,s0)/s2HB(s5) HB(grasp(s3) HB(grasp(climb(s2)HB(grasp(climb(push(c,s0)猴子摘香蕉問題的（修正）消解樹猴子摘

25、香蕉問題的（修正）消解樹第四章 確定性推理 4.2歸結演繹推理 442022-6-27歸結反演的搜索策略歸結反演的搜索策略l 歸結反演過程是“運用歸結規(guī)則直到產生空子句為止”l在對子句集進行歸結時，一個關鍵問題是如何選擇子句進行歸結。l如果對任意一對可以歸結的子句都做歸結，這樣不僅消耗很多的時間，還會產生許多無用的歸結式，占用很多空間l因此，需要研究有效的歸結控制（搜索）策略。l歸結搜索策略一般包括：排序策略和限制策略第四章 確定性推理 4.2歸結演繹推理 452022-6-27排序策略排序策略l歸結順序與狀態(tài)空間的擴展順序類似。l狀態(tài)空間的搜索問題有多種搜索策略。l把原始子句看成0層歸結式。

26、l（i+1）層的歸結式是一個i層歸結式和一個j(ji)層歸結式進行歸結所得到的歸結式。l寬度優(yōu)先：先生成第1層的所有歸結式然后是第2層所有的歸結式，依次類推，直到產生空子句或不能再進行歸結為止。l深度優(yōu)先：產生一個第1層的歸結式，然后用第1層的歸結式和第0層的歸結式進行歸結，得到第2層的歸結式，直到產生空子句結束，或者不能歸結，則回溯到其他的上層子句繼續(xù)歸結l 單元優(yōu)先：在歸結過程中優(yōu)先考慮僅由一個文字構成的子句，這樣的子句稱為單元子句。第四章 確定性推理 4.2歸結演繹推理 462022-6-27限制策略限制策略l限制策略不涉及被歸結子句的排序只允許某些歸結發(fā)生。其中幾種限制歸結策略：l刪除

27、策略l支持集策略。l線性輸入策略。l祖先過濾策略。第四章 確定性推理 4.2歸結演繹推理 472022-6-27刪除策略刪除策略l如果在歸結時能把子句集中的無用子句刪除掉，這樣就會縮小尋找范圍，減少比較次數(shù)。從而提高歸結的效率。l刪除策略有幾種刪除方法： (1)純文字刪除法。 (2)重言式刪除法。 (3)包孕刪除法第四章 確定性推理 4.2歸結演繹推理 482022-6-27純文字刪除法純文字刪除法l如果某文字L在子句集中不存在可與之互補的文字L，則稱該文字為純文字。l在歸結時純文字不可能被消去，因而用包含它的子句進行歸結時不可能得到空子句。l因此，這樣的子句對歸結是無意義的，把它從子句集中刪

28、去，不會影響子句集的不可滿足性。l例如，子句集：SPV Q VR， Q VR，Q，Rl可以看出，P是純文字，因此可將子句PV Q VR從S中刪去。第四章 確定性推理 4.2歸結演繹推理 492022-6-27重言式刪除法重言式刪除法l如果一個子句中同時包含互補文字對，則稱該子句為重言式。l例如，P(x)VQ(x)V P(x)是重言式。l重言式是真值為真的子句。l對于一個子句集，增加或刪去一個重言式子句都不會影響它的不可滿足性，l因而可從子句集中刪去重言式。第四章 確定性推理 4.2歸結演繹推理 502022-6-27包孕刪除法包孕刪除法l設C1，C2是兩個子句，若存在置換，使得C1C2，則稱子

29、句C2包孕C1l例如，P(a)VQ(y)包孕P(x) (=a/x)l P(a)VQ(y)包孕Q(y) l對于一個子句集，刪去一個被別的子句包孕的子句，不會影響它的不可滿足性。l因而可從子句集中刪去被包孕的子句。第四章 確定性推理 4.2歸結演繹推理 512022-6-27限制策略：支持集策略限制策略：支持集策略l支持集策略：支持集策略：每次歸結時參與歸結的子句中至少應有一個是由目標公式的否定所得到的子句，或者是它們的后裔l后裔的定義：設1是子句1 與另外某子句的歸結式是1 的后裔1 的后裔與其他子句的歸結式是1 的后裔。l支持集策略是完備的。即對一個不可滿足的子句集運用支持集策略進行歸結，最終

30、總會導出空子句。第四章 確定性推理 4.2歸結演繹推理 522022-6-27限制策略：線性輸入策略限制策略：線性輸入策略l 線性輸入策略線性輸入策略：參加歸結的兩個子句中至少有一個是初始子句集中的子句。l線性輸入策略是不完備的。對于某些不可滿足的子句集，無法用線性輸入歸結得到結果。第四章 確定性推理 4.2歸結演繹推理 532022-6-27限制策略：祖先過濾策略限制策略：祖先過濾策略l祖先過濾策略祖先過濾策略：參與歸結的兩個子句中至少有一個是初始子句集中的子句，或者一個子句是另一個子句的祖先。l祖先過濾策略是線性輸入策略的改進策略，它是完備的。第四章 確定性推理 4.2歸結演繹推理 542

31、022-6-27消解方法小結消解方法小結l求子句集，進行歸結，方法簡單l通過修改證明樹的方法，提取回答l方法通用l求解效率低，不宜引入啟發(fā)信息l不宜理解推理過程第四章 確定性推理 4.2歸結演繹推理 552022-6-27基于規(guī)則的演繹推理（一）基于規(guī)則的演繹推理（一）l歸結反演系統(tǒng)解決問題的效率低下l歸結演繹并非人類的自然思維方式，不利于人們從自然思維的角度組織問題的求解和提供問題求解所需的知識l基于規(guī)則的演繹推理，運用推理規(guī)則，直接推導目標公式l這符合人的自然思維方式，也能通過規(guī)則(作為啟發(fā)式知識)更有效地引導演繹推理過程。l基于規(guī)則的演繹推理成為比歸結反演更有效的技術，廣泛地應用于許多問

32、題求解中第四章 確定性推理 4.3基于規(guī)則的演繹推理 562022-6-27基于規(guī)則的演繹推理基于規(guī)則的演繹推理(二二)l它把知識分為兩類：規(guī)則和事實規(guī)則表示為if then 形式事實表示為與或形l規(guī)則作為啟發(fā)式知識，引導演繹推理過程。 l事實是有關問題狀態(tài)和環(huán)境的知識，l規(guī)則演繹的任務就是從給定的事實證明某個目標公式成立。l采用直接法而不是反演系統(tǒng)證明目標公式，強調用規(guī)則進行演繹，故稱基于規(guī)則的演繹推理.l分為兩類:正向正向演繹演繹和逆向和逆向演繹演繹第四章 確定性推理 4.3基于規(guī)則的演繹推理 572022-6-27基于規(guī)則的正向演繹推理基于規(guī)則的正向演繹推理l 將非蘊涵式部分的事實表示成

33、與或形，可用與或圖表示l將蘊涵式部分的事實表示成規(guī)則l規(guī)則表示成形式：L W 其中，L是單文字，W是與或形，變量受全稱量詞約束l將目標公式表示成子句集l正向演繹推理的過程正向演繹推理的過程,就是將規(guī)則運用于事實與或圖,對與或圖進行擴展變換的過程l當與或圖的葉節(jié)點包含目標公式的子句集時，推理成功第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹582022-6-27化化目標公式目標公式為子句集為子句集l大部分步驟與歸結原理中化子句集步驟相同l消存在量詞 (skolem化）過程不同。對于一個受存在量詞約束的變量，消去原則：如果他不受全程量詞約束，則該變量用一個常量代替如果他受全程量詞約束，則該變

34、量用一個函數(shù)代替，且全稱量詞變?yōu)榇嬖诹吭~。 (z) (x)(y)(P(x) Q(x) R(y) U(z)= ( x) (P(x) Q(x) R(f(x) U(a)消存在量詞 (P(x) Q(x) R(f(x) U(a)隱含目標公式的變量都受存在量詞的約束第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹592022-6-27事實表達式的與或圖表示事實表達式的與或圖表示l用K連線表示析取，無連線表示合取例： Q(w, A)(R(v) P(v) S(A, v)Q(w, A)(R(v) P(v) S(A, v)Q(w, A)(R(v) P(v) S(A, v)R(v) P(v) S(A, v)R(

35、v)P(v)第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹602022-6-27將規(guī)則變換為限定形式將規(guī)則變換為限定形式l如果規(guī)則不是形式：L W其中，L是單文字，W是與或形，變量受全稱量詞約束則首先變換為這種形式l例：(x)(y)(z)P(x, y, z) (u)Q(x, u)= (x)(y)(z)P(x, y, z) (u)Q(x, u)= (x)(y)(z)P(x, y, z) (u)Q(x, u)= (x)(y)(z) (u)(P(x, y, z) Q(x, u)= P(x, y, f(x, y) Q(x, u) (Skolem化)= P(x, y, f(x, y) Q(x, u

36、) (恢復蘊涵式)l例：(L1 L2) W = L1 W 和 L2 W 第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹612022-6-27對與或圖作變換例對與或圖作變換例l例：事實：(P Q) R) (S (T U)規(guī)則：S (X Y) Z l事實的與或圖與規(guī)則對其進行的變換過程如下圖：第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹622022-6-27(P Q) R) (S (T U)(P Q) R P Q R PQS (T U)ST UTUSX YZX YP Q SP Q T US RR T UP Q X ZP Q Y ZR X ZR Y Z規(guī)則的子句： S (X Y) Z=

37、 S(X Y) Z= S X Z S Y Z結論：加入規(guī)則后得到的解圖，是事實與規(guī)則對應子句的歸結式第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹632022-6-27目標公式作為終止條件目標公式作為終止條件l應用規(guī)則進行推理的目的是為了證明某個目標公式l在正向推理系統(tǒng)中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式l在與或圖的產生過程中，目標文字或規(guī)則與圖中文字節(jié)點匹配時，產生新后裔節(jié)點，標記為匹配的目標文字。當產生的圖包含有終止在目標節(jié)點上的一個解圖時，系統(tǒng)便成功地結束。 第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹642022-6-27例：事

38、實：A B規(guī)則集： A C D B E G目標公式： C GA BAACDBBEGCG目標目標公式作為終止條件例一目標公式作為終止條件例一匹配弧第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹652022-6-27目標公式作為終止條件例二目標公式作為終止條件例二例：事實：P(x, y) (Q(x, A) R(B, y) 規(guī)則集： P(A, B) (S(A) X(B) Q(B, A) U(A) R(B, B) V(B) 目標：S(A) X(B) (U(A) V(B)事實的與或圖與規(guī)則對其進行的變換過程如下圖： 第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹662022-6-27P(x,

39、 y) (Q(x, A) R(B, y)P(x, y)Q(x, A) R(B, y)Q(x, A) R(B, y)P(A, B)A/x,B/yS(A)X(B)Q(B, A) B/xU(A) R(B, B)B/yV(B) 例二的與或圖例二的與或圖第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹672022-6-27基于規(guī)則的基于規(guī)則的逆向演繹推理逆向演繹推理l將目標表達式表示成與或形l將規(guī)則限制為下列形式：W L 其中，L是單文字，W是與或形，變量受全稱量詞約束如規(guī)則形為： W L1 L2，則變換為： W L1 和 W L2l 事實表達式均限制為文字合取形，形如：l F1 F2 Fn Fi(i1,2n)為單文字且都可單獨起作用l 推理過程：從目標公式的與或樹出發(fā)，不斷用規(guī)則的后件和與或樹的葉節(jié)點進行匹配，并將匹配成功的規(guī)則用匹配弧加入與或樹中，直到產生某個終止在事實節(jié)點上的解圖為止。第四章