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

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

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

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

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

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

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

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

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

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

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

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

12、Q）l消去全稱量詞l獲得子句集l更換變量名 第四章 確定性推理 4.3歸結(jié)演繹推理 242022-6-27化子句集例化子句集例例：(z) (x)(y)(P(x) Q(x) R(y) U(z)1, 消蘊(yùn)涵符理論根據(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歸結(jié)演繹推理 252022-6-27化子句集例化子句集例（續(xù)1）3, 變量標(biāo)準(zhǔn)化即：

13、對于不同的約束，對應(yīng)于不同的變量(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歸結(jié)演繹推理 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歸結(jié)演繹推理 272022-6-27化子句集例化子句集例（續(xù)3）8, 表示為子句集 P(x) R(f(x)U(a), Q(x) R(f(x)U(a)9, 變量標(biāo)準(zhǔn)化（變量換名）P(x1) R(f(x1)U(a), Q(x2) R(f(x2)U(a)第四章 確定性推理 4.3歸結(jié)演繹推理 282022

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

16、中的文字L1與C2中的文字L2互補(bǔ)l那么可從C1和C2中分別消去L1和L2l并將C1和C2中余下的部分按析取關(guān)系構(gòu)成一個新的子句C12，l則稱這一過程為歸結(jié)，l稱C12為C1和C2的歸結(jié)式，C1和C2為C12的親本子句。第四章 確定性推理 4.3歸結(jié)演繹推理 312022-6-27消解過程舉例消解過程舉例l E2 E1 （前提）l E2 E3 （前提）l （消解式） E1 E3 （結(jié)論） 第四章 確定性推理 4.2歸結(jié)演繹推理 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歸結(jié)演繹推理 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歸結(jié)演繹推理 342022-6-27消解反演消解反演l消解反演是利用消解原理進(jìn)行推理

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

19、結(jié)演繹推理 362022-6-27命題邏輯消解反演的例子（續(xù)）命題邏輯消解反演的例子（續(xù)）子句集：(1) P(2) PQR(3) SQ(4) TQ(5) T(6) R（目標(biāo)求反）歸結(jié)：(7) PQ (2, 6)(8) Q (1, 7) (9) T (4, 8) (10) nil (5, 9)第四章 確定性推理 4.2歸結(jié)演繹推理 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歸結(jié)演繹推理 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歸結(jié)演繹推理 392022-6-27基于消解原理的問答系統(tǒng)基于消解原理的問答系統(tǒng)l消解原理主要用來解決證明的問題，但有時我們希望得到如x=?時，W(x)為真的回答l消解原理是將結(jié)論的否定作為前提進(jìn)行歸結(jié)，而為了回答問題，用由結(jié)論的否定構(gòu)成的重言式作為前提進(jìn)行歸結(jié)，得到的結(jié)論是問題的回答而不是空語句。這個過程稱為修改證明過程（或修改歸結(jié)過程）。l下面以猴子摘香蕉問題為例來說明第四章 確定性推理 4.2歸結(jié)演繹推理 402022-6-27用消解原理解猴子摘香蕉問題用消解原理解猴子摘香蕉問題l為了把狀態(tài)空

22、間的算符描述與謂詞演算結(jié)合起來，將狀態(tài)添到謂詞上；l將算符看成是把一種狀態(tài)映射成另一種狀態(tài)的函數(shù)；l問題簡化成沒有g(shù)oto()規(guī)則；c第四章 確定性推理 4.2歸結(jié)演繹推理 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歸結(jié)演繹推理 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歸結(jié)演繹推理 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歸結(jié)演繹推理 442022-6-27歸結(jié)反演的搜索策略歸結(jié)反演的搜索策略l 歸結(jié)反演過程是“運(yùn)用歸結(jié)規(guī)則直到產(chǎn)生空子句為止”l在對子句集進(jìn)行歸結(jié)時，一個關(guān)鍵問題是如何選擇子句進(jìn)行歸結(jié)。l如果對任意一對可以歸結(jié)的子句都做歸結(jié)，這樣不僅消耗很多的時間，還會產(chǎn)生許多無用的歸結(jié)式，占用很多空間l因此，需要研究有效的歸結(jié)控制（搜索）策略。l歸結(jié)搜索策略一般包括：排序策略和限制策略第四章 確定性推理 4.2歸結(jié)演繹推理 452022-6-27排序策略排序策略l歸結(jié)順序與狀態(tài)空間的擴(kuò)展順序類似。l狀態(tài)空間的搜索問題有多種搜索策略。l把原始子句看成0層歸結(jié)式。

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

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

28、去，不會影響子句集的不可滿足性。l例如，子句集：SPV Q VR， Q VR，Q，Rl可以看出，P是純文字，因此可將子句PV Q VR從S中刪去。第四章 確定性推理 4.2歸結(jié)演繹推理 492022-6-27重言式刪除法重言式刪除法l如果一個子句中同時包含互補(bǔ)文字對，則稱該子句為重言式。l例如，P(x)VQ(x)V P(x)是重言式。l重言式是真值為真的子句。l對于一個子句集，增加或刪去一個重言式子句都不會影響它的不可滿足性，l因而可從子句集中刪去重言式。第四章 確定性推理 4.2歸結(jié)演繹推理 502022-6-27包孕刪除法包孕刪除法l設(shè)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歸結(jié)演繹推理 512022-6-27限制策略：支持集策略限制策略：支持集策略l支持集策略：支持集策略：每次歸結(jié)時參與歸結(jié)的子句中至少應(yīng)有一個是由目標(biāo)公式的否定所得到的子句，或者是它們的后裔l后裔的定義：設(shè)1是子句1 與另外某子句的歸結(jié)式是1 的后裔1 的后裔與其他子句的歸結(jié)式是1 的后裔。l支持集策略是完備的。即對一個不可滿足的子句集運(yùn)用支持集策略進(jìn)行歸結(jié)，最終

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

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

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

33、與或形，可用與或圖表示l將蘊(yùn)涵式部分的事實(shí)表示成規(guī)則l規(guī)則表示成形式：L W 其中，L是單文字，W是與或形，變量受全稱量詞約束l將目標(biāo)公式表示成子句集l正向演繹推理的過程正向演繹推理的過程,就是將規(guī)則運(yùn)用于事實(shí)與或圖,對與或圖進(jìn)行擴(kuò)展變換的過程l當(dāng)與或圖的葉節(jié)點(diǎn)包含目標(biāo)公式的子句集時，推理成功第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹582022-6-27化化目標(biāo)公式目標(biāo)公式為子句集為子句集l大部分步驟與歸結(jié)原理中化子句集步驟相同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)隱含目標(biāo)公式的變量都受存在量詞的約束第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹592022-6-27事實(shí)表達(dá)式的與或圖表示事實(shí)表達(dá)式的與或圖表示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、) (恢復(fù)蘊(yùn)涵式)l例：(L1 L2) W = L1 W 和 L2 W 第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹612022-6-27對與或圖作變換例對與或圖作變換例l例：事實(shí)：(P Q) R) (S (T U)規(guī)則：S (X Y) Z l事實(shí)的與或圖與規(guī)則對其進(jìn)行的變換過程如下圖：第四章 確定性推理 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結(jié)論：加入規(guī)則后得到的解圖，是事實(shí)與規(guī)則對應(yīng)子句的歸結(jié)式第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹632022-6-27目標(biāo)公式作為終止條件目標(biāo)公式作為終止條件l應(yīng)用規(guī)則進(jìn)行推理的目的是為了證明某個目標(biāo)公式l在正向推理系統(tǒng)中，這種目標(biāo)表達(dá)式只限于可證明的表達(dá)式，尤其是可證明的文字析取形的目標(biāo)公式表達(dá)式l在與或圖的產(chǎn)生過程中，目標(biāo)文字或規(guī)則與圖中文字節(jié)點(diǎn)匹配時，產(chǎn)生新后裔節(jié)點(diǎn)，標(biāo)記為匹配的目標(biāo)文字。當(dāng)產(chǎn)生的圖包含有終止在目標(biāo)節(jié)點(diǎn)上的一個解圖時，系統(tǒng)便成功地結(jié)束。 第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹642022-6-27例：事

38、實(shí)：A B規(guī)則集： A C D B E G目標(biāo)公式： C GA BAACDBBEGCG目標(biāo)目標(biāo)公式作為終止條件例一目標(biāo)公式作為終止條件例一匹配弧第四章 確定性推理 4.3基于規(guī)則的演繹推理正向演繹652022-6-27目標(biāo)公式作為終止條件例二目標(biāo)公式作為終止條件例二例：事實(shí)：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) 目標(biāo)：S(A) X(B) (U(A) V(B)事實(shí)的與或圖與規(guī)則對其進(jìn)行的變換過程如下圖： 第四章 確定性推理 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將目標(biāo)表達(dá)式表示成與或形l將規(guī)則限制為下列形式：W L 其中，L是單文字，W是與或形，變量受全稱量詞約束如規(guī)則形為： W L1 L2，則變換為： W L1 和 W L2l 事實(shí)表達(dá)式均限制為文字合取形，形如：l F1 F2 Fn Fi(i1,2n)為單文字且都可單獨(dú)起作用l 推理過程：從目標(biāo)公式的與或樹出發(fā)，不斷用規(guī)則的后件和與或樹的葉節(jié)點(diǎn)進(jìn)行匹配，并將匹配成功的規(guī)則用匹配弧加入與或樹中，直到產(chǎn)生某個終止在事實(shí)節(jié)點(diǎn)上的解圖為止。第四章