人工智能第五章確定性推理

第四章確定性推理1/22/202314.1確定性推理概述第四章確定性推理

4.1概述1/22/20232推理推理是指按照某種策略從巳知事實(shí)出發(fā)去推出結(jié)論的過程智能系統(tǒng)的推理過程實(shí)際上就是一種思維過程。智能系統(tǒng)的推理過程是通過推理機(jī)來完成的。推理機(jī)就是智能系統(tǒng)中用來實(shí)現(xiàn)推理的程序。按照推理過程所用知識(shí)的確定性，推理可分為確定性推理和不確定性推理。第四章確定性推理

4.1概述1/22/20233事實(shí)事實(shí)是推理過程中按知識(shí)表示方式表示的已知的知識(shí)推理所用的事實(shí)可分為兩種情況:與求解問題有關(guān)的初始證據(jù)．推理過程中所得到的中間結(jié)論。第四章確定性推理

4.1概述

1/22/20234推理的基本問題智能系統(tǒng)的推理包括兩個(gè)基本問題：一個(gè)是推理的方法一個(gè)是推理的控制策略推理方法主要解決：在推理過程中前提與結(jié)論之間的邏輯關(guān)系在非精確性推理中不確定性的傳遞問題第四章確定性推理

4.1概述

1/22/20235推理方法的分類推理可以有多種不同的分類方法按照推理的邏輯基礎(chǔ)分類：演繹推理歸納推理默認(rèn)推理按照所用知識(shí)的確定性分類：確定性推理不確定性推理按照推理過程的單調(diào)性分類（推理過程所得到的結(jié)論是否越來越接近目標(biāo)）：?jiǎn)握{(diào)推理非單調(diào)推理第四章確定性推理

4.1概述

1/22/20236演繹推理

從已知的一般性知識(shí)出發(fā)，去推出蘊(yùn)含在這些已知知識(shí)中的適合于某種個(gè)別情況的結(jié)論。它是一種由一般到個(gè)別的推理方法。核心是三段論第四章確定性推理

4.1概述

1/22/20237歸納推理從一類事物的大量特殊事例出發(fā)，去推出該類事物的一般性結(jié)論。它是一種由個(gè)別到一般的推理方法。基本思想：先從已知事實(shí)中猜測(cè)出一個(gè)結(jié)論，然后對(duì)這個(gè)結(jié)論的正確性加以證明確認(rèn)數(shù)學(xué)歸納法就是歸納推理的一種典型例子。按照所選事例的廣泛性，歸納推理可分為：完全歸納推理和不完全歸納推理；按照推理所使用的方法可分為：枚舉歸納推理、類比歸納推理、統(tǒng)計(jì)歸納推理和差異歸納推理等。第四章確定性推理

4.1概述

1/22/20238默認(rèn)推理

在知識(shí)不完全的倩況下，假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理，因此也稱為缺省推理。在推理過程中．如果發(fā)現(xiàn)原先的假設(shè)不正確，就撤銷原來的假設(shè)以及由此假設(shè)所推出的所有結(jié)論。重新按新情況進(jìn)行推理。解決了在一個(gè)不完備的知識(shí)集中進(jìn)行推理的問題。第四章確定性推理

4.1概述

1/22/20239推理過程的單單調(diào)性按照推理過程程所得到的結(jié)結(jié)論是否越來來越接近日標(biāo)標(biāo)，推理可分分為單調(diào)推理理與非單調(diào)推推理。單調(diào)推理：在推理過程中中，每當(dāng)使用用新的知識(shí)后后，所得到的的結(jié)論會(huì)越來來越接近于目目標(biāo)不會(huì)出現(xiàn)反復(fù)復(fù)情況，即不不會(huì)由于新知知識(shí)的加入否否定了前面推推出的結(jié)論。。非單調(diào)推理：：在推理過程中中，當(dāng)某些新新知識(shí)加入后后，會(huì)否定原原來推出的結(jié)結(jié)論。非單調(diào)推理往往往是在知識(shí)識(shí)不完全的情情況下發(fā)生的的。第四章確定定性推理4.1概述1/7/202310推理控制策略略推理的控制策策略是在推理理過程中采用用的、解決如如何使用領(lǐng)域域知識(shí)使推理理過程盡快達(dá)達(dá)到目標(biāo)的策策略。第四章確定定性推理4.1概述1/7/202311推理控制策略略分類智能系統(tǒng)的的推理過程程一般表現(xiàn)現(xiàn)為一種搜搜索過程，，因此，推推理的控制制策略又可可分為推理理策略和搜搜索策略。。推理策略主主要解決推推理方向、、沖突消解解等問題。。搜索策略主主要解決推推理線路、、推理效果果、推理效效率等問題題。第四章確確定性推理理4.1概述述1/7/202312推理方向推理方向確確定推理過過程是從初初始證據(jù)開開始到目標(biāo)標(biāo)，還是從從目標(biāo)開始始到初始證證據(jù)。按照照對(duì)推理方方向的控制制，推理可可分為正向向推理、逆逆向推理、、混合推理理及雙向推推理四種情情況。第四章確確定性推理理4.1概述述1/7/202313正向推理正向推理是一一種從已知事事實(shí)出發(fā)、正正向使用推理理規(guī)則的推理理方式，亦稱稱為數(shù)據(jù)驅(qū)動(dòng)動(dòng)推理?；舅枷胧牵海河脩粜枰孪认忍峁┮唤M初初始證據(jù)，并并將其放入綜綜合數(shù)據(jù)庫(kù)。。推理機(jī)根據(jù)綜綜合數(shù)據(jù)庫(kù)中中的已有事實(shí)實(shí)，到知識(shí)庫(kù)庫(kù)中尋找當(dāng)前前可用知識(shí)，，形成一個(gè)當(dāng)當(dāng)前可用知識(shí)識(shí)集。按照沖突消解解策略，從該該知識(shí)集中選選擇一條知識(shí)識(shí)進(jìn)行推理，，并將新推出出的事實(shí)加入入綜合數(shù)據(jù)庫(kù)庫(kù)，作為后面面繼續(xù)推理時(shí)時(shí)可用的巳知知事實(shí)，重復(fù)這一過程程，直到求出出所需要的解解或者知識(shí)庫(kù)庫(kù)中再無可用用知識(shí)為止第四章確定定性推理4.1概述1/7/202314逆向推理逆向推理是一一種從以某個(gè)個(gè)假設(shè)目標(biāo)作作為出發(fā)點(diǎn)的的推理方法，，亦稱為目標(biāo)標(biāo)驅(qū)動(dòng)推理基本思想是：：將要求證的目目標(biāo)(稱為假假設(shè))構(gòu)成一一個(gè)假設(shè)集。。取一個(gè)假設(shè)對(duì)對(duì)其進(jìn)行驗(yàn)證證，若在綜合數(shù)據(jù)據(jù)庫(kù)里，則假假設(shè)成立若能被用戶認(rèn)認(rèn)定為事實(shí)，，則假設(shè)成立立，并放入綜綜合數(shù)據(jù)庫(kù)若可由知識(shí)庫(kù)庫(kù)中的一個(gè)或或多個(gè)知識(shí)導(dǎo)導(dǎo)出，則這些些知識(shí)構(gòu)成可可用知識(shí)集。。按照沖突消消解策略，從從該知識(shí)集中中選擇一條知知識(shí)，將其前前提中的所有有子條件作為為新的假設(shè)加加入假設(shè)集。。重復(fù)這一過程程，直到假設(shè)設(shè)集為空或假假設(shè)集非空但但可用知識(shí)集集空為止第四章確定定性推理4.1概述1/7/202315混合推推理正向推推理和和逆向向推理理都有有各自自的優(yōu)優(yōu)缺點(diǎn)點(diǎn)。當(dāng)當(dāng)問題題較復(fù)復(fù)雜時(shí)時(shí)，單單獨(dú)使使用其其中哪哪一種種，都都會(huì)影影響到到推理理效率率。為了取取長(zhǎng)補(bǔ)補(bǔ)短．．可將將它們們結(jié)合合起來來使用用。這種把把正向向推理理和逆逆向推推理結(jié)結(jié)合起起來所所進(jìn)行行的推推理稱稱為混混合推推理。。第四章章確確定性性推理理4.1概述述1/7/202316混合推推理的的實(shí)現(xiàn)現(xiàn)方法法混合推推理可可有多多種具具體的的實(shí)現(xiàn)現(xiàn)方法法先正向向推理理，后后逆向向推理理的方方法先逆向向推理理，后后正向向推理理的方方法采用隨隨機(jī)選選擇正正向和和逆向向推理理的方方法（（雙向向混合合推理理）第四章章確確定性性推理理4.1概述述1/7/202317混合推推理的的適用用場(chǎng)合合已知事事實(shí)不不夠充充分。。由正向向推理理推出出的結(jié)結(jié)論可可信度度不高高希望得得出更更多的的結(jié)論論希望從從正反反兩個(gè)個(gè)方向向同時(shí)時(shí)進(jìn)行行推理理第四章章確確定性性推理理4.1概述述1/7/202318沖突消消解策策略沖突消消解策策略是是指當(dāng)當(dāng)推理理過程程有多多條知知識(shí)可可用時(shí)時(shí)，如如何從從這多多條可可用知知識(shí)中中選出出一條條最佳佳知識(shí)識(shí)用于于推理理的策策略。。沖突消解解的基本本思想是是對(duì)可用用知識(shí)進(jìn)進(jìn)行排序序。常用的沖沖突消解解策略有有：特殊知識(shí)識(shí)優(yōu)先新鮮知識(shí)識(shí)優(yōu)先差異性大大的知識(shí)識(shí)優(yōu)先領(lǐng)域特點(diǎn)點(diǎn)知識(shí)優(yōu)優(yōu)先上下文關(guān)關(guān)系知識(shí)識(shí)優(yōu)先前提條件件少的知知識(shí)優(yōu)先第四章確確定性性推理4.1概概述1/7/202319自然演繹繹推理從一組己己知為真真的事實(shí)實(shí)出發(fā)，，直接運(yùn)運(yùn)用經(jīng)典典邏輯中中的推理理規(guī)則推推出結(jié)論論的過程程稱為自自然演繹繹推理。。在自然演演繹推理理中，需需要避免免兩類錯(cuò)錯(cuò)誤：肯定后件的的錯(cuò)誤和否否定前件的的錯(cuò)誤。優(yōu)點(diǎn)：定理證明過過程自然，，易于理解解，有豐富富的推理規(guī)規(guī)則主要缺點(diǎn)：：容易產(chǎn)生知知識(shí)爆炸，，推理過程程中得到的的中間結(jié)論論一般按指指數(shù)規(guī)律遞遞增，對(duì)于于復(fù)雜問題題的推理不不利，甚至至難以實(shí)現(xiàn)現(xiàn)。因此，提出出了歸結(jié)演演繹推理第四章確確定性推理理4.2自然演繹推推理1/7/202320歸結(jié)演繹推理理歸結(jié)演繹推理理是一種基于于歸結(jié)原理的的推理方法。。歸結(jié)原理亦稱稱消解原理，，是魯賓遜1965年提提出的歸結(jié)演繹推理理實(shí)際上是一一種“反正法法”，基本思想：推理就是要對(duì)對(duì)前提P和結(jié)結(jié)論Q，證明明PQ永真。這就要證明PQ在任何一個(gè)個(gè)非空的個(gè)體體域上都是永永真的。這將將是非常困難難的，甚至是是不可實(shí)現(xiàn)的的。而用反證法，，只要能夠證證明～(PQ)是不可滿滿足的。第四章確定定性推理4.3歸結(jié)演繹推理1/7/202321子句和子句集集原子謂詞公式式及其否定都都稱為文字文字的析取構(gòu)構(gòu)成的公式稱稱為子句不包含任何文文字的子句稱稱為空了句空子句不包含含任何文字，，因此，不能能被任何指派派所滿足所以空子句是是不可滿足的的子句集中的子子句之間是合合取關(guān)系含空子句的子子句集也就一一定是不可滿滿足的。第四章確定定性推理4.3歸結(jié)演繹推理1/7/202322謂詞公式轉(zhuǎn)化化為子句集消去蘊(yùn)涵符號(hào)號(hào)：～P∨Q取代P→Q減少否定符號(hào)號(hào)的管轄域?qū)ψ兞繕?biāo)準(zhǔn)化化消去存在量詞詞化為前束形化為合取范式：如如：PΛ(P∨Q）Λ(～P∨Q）消去全稱量詞詞獲得子句集更換變量名第四章確定定性推理4.3歸結(jié)演繹推理1/7/202323化子句句集例例例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消消蘊(yùn)蘊(yùn)涵符符理論根根據(jù)：：ab=>~ab(z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,移移動(dòng)動(dòng)否定定符理論根根據(jù)：：~(ab)=>~a~b~(ab)=>~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é)演繹推推理1/7/202324化子句句集例例（續(xù)1）3,變變量量標(biāo)準(zhǔn)準(zhǔn)化即：對(duì)于不不同的約束束，對(duì)應(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化）原則：對(duì)于于一個(gè)受存存在量詞約約束的變量量，如果他他不受全程程量詞約束束，則該變變量用一個(gè)個(gè)常量代替替，如果他他受全程量量詞約束，，則該變量量用一個(gè)函函數(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é)演繹推理1/7/202325化子句集例例（續(xù)2））6,化為為合取范式式即(ab)(cd)(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é)演繹推理1/7/202326化子句集例例（續(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é)演繹推理1/7/202327歸結(jié)(消解)原理理基本思想首先把欲證證明問題的的結(jié)論否定定，并加入入子句集，，得到一個(gè)個(gè)擴(kuò)充的子子句集S’’。檢驗(yàn)子句集集S’是否否含有空子子句若不含空子子句，則繼繼續(xù)使用歸歸結(jié)法，在在子句集中中選擇合適適的子句進(jìn)進(jìn)行歸結(jié)直至導(dǎo)出空空子句或不不能繼續(xù)歸歸結(jié)為止。。第四章確確定性推理理4.3歸結(jié)演繹推理1/7/202328歸結(jié)原理分類魯賓遜歸結(jié)結(jié)原理可分分為:命題邏輯歸歸結(jié)原理謂詞邏輯歸歸結(jié)原理第四章確確定性推理理4.3歸結(jié)演繹推理1/7/202329歸結(jié)式歸結(jié)推理理的核心心是求兩兩個(gè)子句句的歸結(jié)結(jié)式若P是原原子謂詞詞公式，，則稱P與~P為互補(bǔ)補(bǔ)文字設(shè)C1和和C2是是子句集集中的任任意兩個(gè)個(gè)子句如果C1中的文文字L1與C2中的文文字L2互補(bǔ)那么可從從C1和和C2中中分別消消去L1和L2并將C1和C2中余下下的部分分按析取取關(guān)系構(gòu)構(gòu)成一個(gè)個(gè)新的子子句C12，則稱這一一過程為為歸結(jié)，，稱C12為C1和C2的歸結(jié)結(jié)式，C1和C2為C12的的親本子子句。第四章確確定性性推理4.3歸結(jié)演繹推理理1/7/202330消解過程舉例例E2∨E1（（前提）～E2∨E3（（前提）（消解式）E1∨E3（（結(jié)論）第四章確定定性推理4.2歸結(jié)演繹推理1/7/202331命題邏輯的消消解推理舉例例假言推理：P～P∨Q(P→Q）消解式：Q合并：P∨Q～P∨Q消解式：Q∨Q=Q重言式：P∨Q～P∨～Q消解式：P∨～P或Q∨～Q空子句：P～P消解式：NIL三段論：～～P∨Q(P→Q）～Q∨R(Q→R））消解式：～P∨R(P→Q）第四章確定定性推理4.2歸結(jié)演繹推理1/7/202332謂詞邏輯的的消解推理理舉例B(x)～B(x)∨C(x）消解式：C(x)P(x)∨Q(x）～Q[f(y)]消解式：P[f(y)]置換：f(y)/xP[x,f(y)]∨Q(x)∨R[f(a),y]～P[f(f(a)),z]∨R(z,w）消解式：Q[f(f(a))]∨R[f(a),y]∨R[f(y),w]置換：f(f(a))/x,f(y)/z第四章確確定性推理理4.2歸結(jié)演繹推理1/7/202333消解反演消解反演是利用消解原理進(jìn)進(jìn)行推理的的過程。消解反演的的推理過程程:給定公式集集S和目標(biāo)公公式L證明公式L的步步驟如下：：否定L，得～L把～L添加到S中去把新產(chǎn)生的的集合{～～L,S}化成成子句集應(yīng)用消解原原理力圖推推導(dǎo)出一個(gè)個(gè)表示矛盾盾的空子句句第四章確確定性推理理4.2歸結(jié)演繹推理1/7/202334命題邏輯消解解反演的例子子設(shè)公理集：P,(PQ)R,(ST)Q,T求證：R子句集：(1)P(2)~P~QR(3)~SQ(4)~TQ(5)T(6)~R（目標(biāo)求反反）化子句集：(PQ)R=>~(PQ)R=>~P~QR(ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ)=>{~SQ,~TQ}第四章確定定性推理4.2歸結(jié)演繹推理1/7/202335命題邏輯消消解反演的的例子（續(xù)續(xù)）子句集：(1)P(2)~P~QR(3)~SQ(4)~TQ(5)T(6)~R（目標(biāo)標(biāo)求反）歸結(jié)：(7)~P~Q(2,6)(8)~Q(1,7)(9)~T(4,8)(10)nil(5,9)第四章確確定性推理理4.2歸結(jié)演繹推理1/7/202336謂詞邏輯輯消解反反演的例例子例：已知：IfFidogoeswhereverJohngoesandifJohnisatschool,whereisFido?(x)[AT(John,x)AT(Fido,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é)演繹推理理1/7/202337~AT(Fido,x)~AT(John,y)AT(Fido,y)子句集： ~AT(John,y)AT(Fido,y) AT(John,School) ~AT(Fido,x)~AT(John,x){x/y}AT(John,School)nil{School/x}AT(Fido,School)謂詞邏輯消解解反演的例子子（續(xù)）第四章確定定性推理4.2歸結(jié)演繹推理1/7/202338基于消消解原原理的的問答答系統(tǒng)統(tǒng)消解原原理主主要用用來解解決證證明的的問題題，但但有時(shí)時(shí)我們們希望望得到到如x=?時(shí)，，W(x)為真真的回回答消解原原理是是將結(jié)結(jié)論的的否定定作為為前提提進(jìn)行行歸結(jié)結(jié)，而而為了了回答答問題題，用用由結(jié)結(jié)論的的否定定構(gòu)成成的重重言式式作為為前提提進(jìn)行行歸結(jié)結(jié)，得得到的的結(jié)論論是問問題的的回答答而不不是空空語(yǔ)句句。這這個(gè)過過程稱稱為修修改證證明過過程（（或修修改歸歸結(jié)過過程））。下面以以猴子子摘香香蕉問問題為為例來來說明明第四章章確確定性性推理理4.2歸結(jié)演繹推推理1/7/202339用消解解原理理解猴猴子摘摘香蕉蕉問題題為了把把狀態(tài)態(tài)空間間的算算符描描述與與謂詞詞演算算結(jié)合合起來來，將將狀態(tài)態(tài)添到到謂詞詞上；；將算符符看成成是把把一種種狀態(tài)態(tài)映射射成另另一種種狀態(tài)態(tài)的函函數(shù)；；問題簡(jiǎn)簡(jiǎn)化成成沒有有g(shù)oto()規(guī)則則；c第四章章確確定性性推理理4.2歸結(jié)演繹推推理1/7/202340猴子摘摘香蕉蕉問題題的表表示問題可可以描描述如如下：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)第四章確定定性推理4.2歸結(jié)演繹推理1/7/202341猴子摘香蕉問問題的子句集集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é)演繹推理1/7/202342~HB(s5)~ON(s3)~AT(box,c,s3)HB(grasp(s3))~ON(s3)~AT(box,c,s3){grasp(s3)/s5}ON(climb(s2)){climb(s2)/s3}~AT(box,c,climb(s2))~ON(s0)ON(s1)AT(box,x1,push(x1,s1)){s0/s1}AT(box,x1,push(x1,s0))~AT(box,x4,s4)AT(box,x4,climb(s4)){x4/x1,push(x4,s0)/s4}AT(box,x4,climb(push(x4,s0)))NIL{c/x4,push(c,s0)/s2}HB(s5)HB(grasp(s3))HB(grasp(climb(s2)))HB(grasp(climb(push(c,s0))))猴子摘摘香蕉蕉問題題的（（修正正）消消解樹樹第四章章確確定性性推理理4.2歸結(jié)演繹推推理1/7/202343歸結(jié)反反演的的搜索索策略略歸結(jié)反反演過過程是是“運(yùn)運(yùn)用歸歸結(jié)規(guī)規(guī)則直直到產(chǎn)產(chǎn)生空空子句句為止止”在對(duì)子子句集集進(jìn)行行歸結(jié)結(jié)時(shí)，，一個(gè)個(gè)關(guān)鍵鍵問題題是如如何選選擇子子句進(jìn)進(jìn)行歸歸結(jié)。。如果對(duì)對(duì)任意意一對(duì)對(duì)可以以歸結(jié)結(jié)的子子句都都做歸歸結(jié)，，這樣樣不僅僅消耗耗很多多的時(shí)時(shí)間，，還會(huì)會(huì)產(chǎn)生生許多多無用用的歸歸結(jié)式式，占占用很很多空空間因此，，需要要研究究有效效的歸歸結(jié)控控制（（搜索索）策策略。。歸結(jié)搜搜索策策略一一般包包括：：排序序策略略和限限制策策略第四章章確確定性性推理理4.2歸結(jié)演繹推推理1/7/202344排序策略歸結(jié)順序與與狀態(tài)空間間的擴(kuò)展順順序類似。。狀態(tài)空間的的搜索問題題有多種搜搜索策略。。把原始子句句看成0層層歸結(jié)式。。（i+1））層的歸結(jié)結(jié)式是一個(gè)個(gè)i層歸結(jié)結(jié)式和一個(gè)個(gè)j(j≤≤i)層歸歸結(jié)式進(jìn)行行歸結(jié)所得得到的歸結(jié)結(jié)式。寬度優(yōu)先：：先生成第1層的所有有歸結(jié)式．．然后是第第2層所有有的歸結(jié)式式，依次類類推，直到到產(chǎn)生空子子句或不能能再進(jìn)行歸歸結(jié)為止。。深度優(yōu)先：：產(chǎn)生一個(gè)第第1層的歸歸結(jié)式，然然后用第1層的歸結(jié)結(jié)式和第0層的歸結(jié)結(jié)式進(jìn)行歸歸結(jié)，得到到第2層的的歸結(jié)式，，直到產(chǎn)生生空子句結(jié)結(jié)束，或者者不能歸結(jié)結(jié)，則回溯溯到其他的的上層子句句繼續(xù)歸結(jié)結(jié)單元優(yōu)先：：在歸結(jié)過程程中優(yōu)先考考慮僅由一一個(gè)文字構(gòu)構(gòu)成的子句句，這樣的的子句稱為為單元子句句。第四章確確定性推理理4.2歸結(jié)演繹推理1/7/202345限制策略略限制策略略不涉及及被歸結(jié)結(jié)子句的的排序．．只允許許某些歸歸結(jié)發(fā)生生。其中中幾種限限制歸結(jié)結(jié)策略：：刪除策略略支持集策策略。線性輸入入策略。。祖先過濾濾策略。。第四章確確定性性推理4.2歸結(jié)演繹推理理1/7/202346刪除策略如果在歸結(jié)時(shí)時(shí)能把子句集集中的無用子子句刪除掉，，這樣就會(huì)縮縮小尋找范圍圍，減少比較較次數(shù)。從而而提高歸結(jié)的的效率。刪除策略有幾幾種刪除方法法：(1)純文字字刪除法。(2)重言式式刪除法。(3)包孕刪刪除法第四章確定定性推理4.2歸結(jié)演繹推理1/7/202347純文字刪除法法如果某文字L在子句集中中不存在可與與之互補(bǔ)的文文字~L，則則稱該文字為為純文字。在歸結(jié)時(shí)純文文字不可能被被消去，因而而用包含它的的子句進(jìn)行歸歸結(jié)時(shí)不可能能得到空子句句。因此，這樣的的子句對(duì)歸結(jié)結(jié)是無意義的的，把它從子子句集中刪去去，不會(huì)影響響子句集的不不可滿足性。。例如，子句集集：S＝{PVQVR，~QVR，，Q，~R}可以看出，P是純文字，，因此可將子子句PVQVR從S中刪去。第四章確定定性推理4.2歸結(jié)演繹推理1/7/202348重言式式刪除除法如果一一個(gè)子子句中中同時(shí)時(shí)包含含互補(bǔ)補(bǔ)文字字對(duì)，，則稱稱該子子句為為重言言式。。例如，，P(x)VQ(x)V~P(x)是重重言式式。重言式式是真真值為為真的的子句句。對(duì)于一一個(gè)子子句集集，增增加或或刪去去一個(gè)個(gè)重言言式子子句都都不會(huì)會(huì)影響響它的的不可可滿足足性，，因而可可從子子句集集中刪刪去重重言式式。第四章章確確定性性推理理4.2歸結(jié)演繹推推理1/7/202349包孕刪刪除法法設(shè)C1，C2是是兩個(gè)個(gè)子句句，若若存在在置換換σ，，使得得C1σ?C2，，則稱稱子句句C2包孕C1例如，，P(a)VQ(y)包包孕P(x)(σσ={a/x})P(a)VQ(y)包孕孕Q(y)對(duì)于一一個(gè)子子句集集，刪刪去一一個(gè)被被別的的子句句包孕孕的子子句，，不會(huì)會(huì)影響響它的的不可可滿足足性。。因而可可從子子句集集中刪刪去被被包孕孕的子子句。。第四章章確確定性性推理理4.2歸結(jié)演繹推推理1/7/202350支持集策略支持集策略：：每次歸結(jié)時(shí)．．參與歸結(jié)的的子句中至少少應(yīng)有一個(gè)是是由目標(biāo)公式式的否定所得得到的子句，，或者是它們們的后裔后裔的定義：：設(shè)α1是子子句α1與另外外某子句的歸歸結(jié)式是α1的后裔α1的后裔裔與其他子句句的歸結(jié)式是是α1的后后裔。支持集策略是是完備的。即即對(duì)一個(gè)不可可滿足的子句句集運(yùn)用支持持集策略進(jìn)行行歸結(jié)，最終終總會(huì)導(dǎo)出空空子句。第四章確定定性推理4.2歸結(jié)演繹推理1/7/202351線性輸入策策略線性輸入策策略：參加歸結(jié)結(jié)的兩個(gè)子子句中至少少有一個(gè)是是初始子句句集中的子子句。線性輸入策策略是不完完備的。對(duì)對(duì)于某些不不可滿足的的子句集，，無法用線線性輸入歸歸結(jié)得到結(jié)結(jié)果。第四章確確定性推理理4.2歸結(jié)演繹推理1/7/202352祖先過濾策略略祖先過濾策略略：參與歸結(jié)的的兩個(gè)子句中中至少有一個(gè)個(gè)是初始子句句集中的子句句，或者一個(gè)個(gè)子句是另一一個(gè)子句的祖祖先。祖先過濾策略略是線性輸入入策略的改進(jìn)進(jìn)策略，它是是完備的。第四章確定定性推理4.2歸結(jié)演繹推理1/7/202353消解方法小結(jié)結(jié)求子句集，進(jìn)進(jìn)行歸結(jié)，方方法簡(jiǎn)單通過修改證明明樹的方法，，提取回答方法通用求解效率低，，不宜引入啟啟發(fā)信息不宜理解推理理過程第四章確定定性推理4.2歸結(jié)演繹推理1/7/202354基于規(guī)規(guī)則的的演繹繹推理理（一一）歸結(jié)反反演系系統(tǒng)解解決問問題的的效率率低下下歸結(jié)演演繹并并非人人類的的自然然思維維方式式，不不利于于人們們從自自然思思維的的角度度組織織問題題的求求解和和提供供問題題求解解所需需的知知識(shí)基于規(guī)則的的演繹繹推理理，運(yùn)運(yùn)用推推理規(guī)規(guī)則，，直接接推導(dǎo)導(dǎo)目標(biāo)標(biāo)公式式這符合合人的的自然然思維維方式式，也也能通通過規(guī)規(guī)則(作為為啟發(fā)發(fā)式知知識(shí))更有有效地地引導(dǎo)導(dǎo)演繹繹推理理過程程?；谝?guī)規(guī)則的的演繹繹推理理成為為比歸歸結(jié)反反演更更有效效的技技術(shù)，，廣泛泛地應(yīng)應(yīng)用于于許多多問題題求解解中第四章章確確定性性推理理4.3基于于規(guī)則的的演繹推推理1/7/202355基于規(guī)規(guī)則的的演繹繹推理理(二二)它把知識(shí)分分為兩類：：規(guī)則和事事實(shí)規(guī)則表示為ifthen形式式事實(shí)表示為與或或形規(guī)則作為啟發(fā)式式知識(shí)，引引導(dǎo)演繹推推理過程。。事實(shí)是有關(guān)問題狀狀態(tài)和環(huán)境境的知識(shí)，，規(guī)則演繹的的任務(wù)就是是從給定的的事實(shí)證明明某個(gè)目標(biāo)標(biāo)公式成立立。采用直接法法而不是反反演系統(tǒng)證證明目標(biāo)公公式，強(qiáng)調(diào)調(diào)用規(guī)則進(jìn)進(jìn)行演繹，故稱稱基于規(guī)則則的演繹推推理.分為兩類:正向演繹和逆向演繹第四章確確定性推理理4.3基于于規(guī)則的演繹推理1/7/202356基于規(guī)則的的正向演繹繹推理將非蘊(yùn)涵式式部分的事事實(shí)表示成成與或形，，可用與或或圖表示將蘊(yùn)涵式部分分的事實(shí)表表示成規(guī)則規(guī)則表示成成形式：LW其中，L是是單文字，，W是與或或形，變量量受全稱量量詞約束將目標(biāo)公式式表示成子子句集正向演繹推推理的過程程,就是將規(guī)規(guī)則運(yùn)用于于事實(shí)與或或圖,對(duì)與與或圖進(jìn)行行擴(kuò)展變換換的過程當(dāng)與或圖的的葉節(jié)點(diǎn)包包含目標(biāo)公式的的子句集時(shí)時(shí)，推理成成功第四章確確定性推理理4.3基于于規(guī)則的演繹推理———正向演繹1/7/202357化目標(biāo)公公式為子句句集大部分分步驟驟與歸歸結(jié)原原理中中化子子句集集步驟驟相同同消存在在量詞詞(skolem化））過程不不同。。對(duì)于一一個(gè)受受存在在量詞詞約束束的變變量，，消去去原則則：如果他他不受受全程程量詞詞約束束，則則該變變量用用一個(gè)個(gè)常量量代替替如果他他受全全程量量詞約約束，，則該該變量量用一一個(gè)函函數(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ī)則的的演繹推推理———正向演演繹1/7/202358事實(shí)表達(dá)式的的與或圖表示示用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(v)~P(v)第四章確定定性推理4.3基于規(guī)則的演繹推理———正向演繹1/7/202359將規(guī)則則變換換為限限定形形式如果規(guī)規(guī)則不不是形形式：：LW其中，，L是是單文文字，，W是是與或或形，，變量量受全全稱量量詞約約束則首先先變換換為這這種形形式例：(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)(恢復(fù)復(fù)蘊(yùn)涵涵式)例：(L1L2)W=>L1W和L2W第四章章確確定性性推理理4.3基于于規(guī)則的的演繹推推理———正向演演繹1/7/202360對(duì)與或圖圖作變換換例例：事實(shí)：((PQ)R)(S(TU))規(guī)則：S(XY)Z事實(shí)的與或圖與與規(guī)則對(duì)其其進(jìn)行的的變換過過程如下下圖：第四章確確定性性推理4.3基基于規(guī)則的演繹推理理——正向演繹繹1/7/202361((PQ)R)(S(TU))(PQ)RPQRPQS(TU)STUTUSXYZXYPQSPQTUSRRTUPQXZPQYZRXZRYZ規(guī)則的子句：：S(XY)Z=>~S(XY)Z=>~SXZ~SYZ結(jié)論：加入規(guī)規(guī)則后得到的的解圖，是事事實(shí)與規(guī)則對(duì)對(duì)應(yīng)子句的歸歸結(jié)式第四章確定定性推理4.3基于規(guī)則的演繹推理———正向演繹1/7/202362目標(biāo)公式作作為終止條條件應(yīng)用規(guī)則進(jìn)進(jìn)行推理的的目的是為為了證明某某個(gè)目標(biāo)公公式在正向推理理系統(tǒng)中，，這種目標(biāo)標(biāo)表達(dá)式只只限于可證明的表表達(dá)式，尤其是可可證明的文文字析取形形的目標(biāo)公公式表達(dá)式式在與或圖的的產(chǎn)生過程程中，目標(biāo)標(biāo)文字或規(guī)規(guī)則與圖中中文字節(jié)點(diǎn)點(diǎn)匹配時(shí)，，產(chǎn)生新后后裔節(jié)點(diǎn)，，標(biāo)記為匹匹配的目標(biāo)標(biāo)文字。當(dāng)當(dāng)產(chǎn)生的圖圖包含有終終止在目標(biāo)標(biāo)節(jié)點(diǎn)上的的一個(gè)解圖圖時(shí)，系統(tǒng)統(tǒng)便成功地地結(jié)束。第四章確確定性推理理4.3基于于規(guī)則的演繹推理———正向演繹1/7/202363例：事實(shí)：AB規(guī)則集：ACDBEG目標(biāo)公式：：CGABAACDBBEGCG目標(biāo)目標(biāo)公式作作為終止條條件例一匹配弧第四章確確定性推理理4.3基于于規(guī)則的演繹推理———正向演繹1/7/202364目標(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ī)則對(duì)其進(jìn)進(jìn)行的變換換過程如下下圖：第四章確確定性推理理4.3基于于規(guī)則的演繹推推理———正向演演繹1/7/202365P(x,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/y}S(A)X(B)Q(B,A){B/x}U(A)R(B,B){B/y}V(B)例二的的與或或圖第四章章確確定性性推理理4.3基于于規(guī)則的的演繹推推理———正向演演繹1/7/202366基于規(guī)規(guī)則的的逆向演演繹推推理將目標(biāo)標(biāo)表達(dá)達(dá)式表表示成成與或或形將規(guī)則則限制制為下下列形形式：：WL其中，，L是是單文文字，，W是是與或或形，，變量量受全全稱量量詞約約束如規(guī)則形為：：WL1L2，則則變換換為：：WL1和和WL2事實(shí)表表達(dá)式式均限限制為為文字字合取取形，，形如如：F1F2…FnFi(i＝＝1,2……n)為單單文字字．且且都可可單獨(dú)獨(dú)起作作用推理過過程：：從目目標(biāo)公公式的的與／／或樹樹出發(fā)發(fā)，不不斷用用規(guī)則則的后后件和和與／／或樹樹的葉葉節(jié)點(diǎn)點(diǎn)進(jìn)行行匹配配，并并將匹匹配成成功的的規(guī)則則用匹匹配弧弧加入入與／／或樹樹中，，直到到產(chǎn)生生某個(gè)個(gè)終止止在事事實(shí)節(jié)節(jié)點(diǎn)上上的解解圖為為止。。第四章確確定性性推理4.3基基于規(guī)則的演繹推理理—