人工智能-第三搜索推理技術(shù)

搜索推理技術(shù)

從問題的表示到問題的解決是一個求解的過程，也就是搜索過程。在這一過程中，采用適當?shù)乃阉骷夹g(shù)，包括各種規(guī)則、過程和算法等推理技術(shù)，力求找到問題的解答。本章首先介紹圖搜索策略的一般過程，接著討論一些早期的搜索技術(shù)或用于解決比較簡單問題的搜索原理，然后研究一些比較新的能夠求解比較復(fù)雜問題的推理技術(shù)。2021/5/91第三確定性推理§3.1圖搜索策略§3.2盲目搜索§3.3啟發(fā)式搜索§3.4消解原理§3.5規(guī)則演繹系統(tǒng)§3.6產(chǎn)生式系統(tǒng)§3.7非單調(diào)推理2021/5/92第三搜索推理技術(shù)

一般一個問題可以用好幾種搜索技術(shù)解決,選擇一種好的搜索技術(shù)對解決問題的效率很有關(guān)系,甚至關(guān)系到求解問題有沒有解。

搜索方法好的標準,一般認為有兩個：

(1)搜索空間小;

(2)解最佳。Sg2021/5/93§3.1圖搜索策略§3.1圖搜索策略一.問題描述(圖搜索問題描述)

把求解問題看成一個狀態(tài)圖，求初始節(jié)點到目標節(jié)點的路徑。2021/5/94§3.1.1圖搜索策略回顧一下圖論中幾個術(shù)語的含義。節(jié)點深度：根節(jié)點的深度為0,其他節(jié)點的深度規(guī)定為父節(jié)點深度加1,即dn+1=dn+1。路徑：設(shè)一節(jié)點序列為(n0、n1,…,ni,…,nk),對i=1,2,…,k,若節(jié)點ni-1都具有一個后繼節(jié)點ni,則該節(jié)點序列稱為節(jié)點n0到節(jié)點nK長度為k的一條路徑。路徑耗散值：令C(ni,nj)為節(jié)點ni到nj這段路徑(或弧線)的耗散值,一條路徑的耗散值等于連接這條路徑各節(jié)點間所有弧線耗散值的總和。路徑耗散值可按如下式遞歸公式計算:

C(ni,t)=C(ni,nj)+C(nj,t)

C(nj,t)為ni→t這條路徑的耗散值。2021/5/95§3.1.1圖搜索策略回顧一下圖論中幾個術(shù)語的含義。擴展一個節(jié)點:后繼節(jié)點操作符(相當于可應(yīng)用規(guī)則)作用到節(jié)點(對應(yīng)于某一狀態(tài)描述)上,生成出其所有后繼節(jié)點(新狀態(tài)),并給出連接弧線的耗散值(相當于使用規(guī)則的代價),這個過程叫做擴展一個節(jié)點。擴展節(jié)點可使定義的隱含圖生成為顯式表示的狀態(tài)空間圖。

2021/5/96§3.1.1圖搜索策略二.圖搜索過程

S～起始結(jié)點G～搜索圖

OPEN～表存放未擴展節(jié)點

CLOSED～表存放已擴展節(jié)點1.圖搜索過程

(1)建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN的未擴展節(jié)點表中。

(2)建立一個叫做CLOSED的已擴展節(jié)點表，其初始為空表。

(3)LOOP:若OPEN表是空表，則失敗退出。

(4)選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中，稱此節(jié)點為節(jié)點n。2021/5/97§3.1.1圖搜索策略(5)若n為一目標節(jié)點n，則有解并成功退出。此解是追蹤圖G中沿著指針從n到s這條路徑而得到的。

(6)擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼結(jié)點添入圖G中。

(7)對于那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設(shè)置一個通向n的指針。把M的這些成員加進OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已經(jīng)在CLOSED表上的每一個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。

(8)按某一任意方式或按某個探試值，重排OPEN表。

(9)GOLOOP2021/5/98§3.1.1圖搜索策略

舉例：SABCDEMFS1.SOPEN(S)CLOSED()2.AOPEN(A,B)CLOSED(S)3.BOPRN(B,C,D)CLOSED(S,A)4.COPEN(C,D,E)CLOSED(S,A,B)5.DOPEN(D,E)CLOSED(S,A,B,C)6.EOPEN(E,M,F)CLOSED(S,A,B,C,D)7.N求解目標節(jié)點235647384×2021/5/99§3.1.1圖搜索策略2.流程圖

開始把S放表入OPEN表中OPEN表為空表把第一個節(jié)點n從OPEN表移至CLOSED表N為目標節(jié)點把節(jié)點n的后繼節(jié)點放入OPEN表，提供返回節(jié)點n的指針修正指針方向重排OPEN表失敗成功是是①②③2021/5/910§3.1.1圖搜索策略2021/5/911§3.1.1圖搜索策略2021/5/912§3.1.1圖搜索策略2021/5/913§3.1.1圖搜索策略2021/5/914§3.1.1圖搜索策略2021/5/915§3.1.1圖搜索策略

3.遺留問題①n的某后繼節(jié)點已在OPEN表中或CLOSED表中有了是否需要修改指針，對已存在的后繼節(jié)點②按什么方式重排OPEN表寬度優(yōu)先搜索深度優(yōu)先搜索等代價搜索搜索控制方法2021/5/916§3.2盲目搜索

盲目搜索是不利用問題的有關(guān)信息,而根據(jù)事先確定好的某種固定的搜索方法進行搜索，又叫做無信息搜索。一般只適用于求解比較簡單的問題。典型的盲目搜索方法是深度優(yōu)先搜索和寬度優(yōu)先搜索(亦稱廣度優(yōu)先搜索),這是兩處基本搜索方法。

2021/5/917§3.2盲目搜索一.寬度優(yōu)先搜索(一).寬度優(yōu)先搜索

以接近起始節(jié)點的程度依次擴展節(jié)點

從根結(jié)點開始,每次都要掃遍同層的各個結(jié)點,若沒有找到目標,則再往下一層掃描(掃描下一層的所有子結(jié)點),直到找到目標或沒有找到目標退出系統(tǒng)(此種屬于沒有解的情況)。2021/5/918§3.2盲目搜索(二).流程算法擴展節(jié)點：把它的后繼節(jié)點放入OPEN表的末端1.搜索算法⑴把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)⑵如果OPEN表是一個空表，則沒有解，失敗退出；否則繼續(xù)。⑶把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。⑷擴展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向第⑵步。⑸把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。⑹如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第⑵步2021/5/919§3.2盲目搜索2.流程圖

開始把S放表入OPEN表OPEN表為空表把第一個節(jié)點n從OPEN表移至CLOSED表把節(jié)點n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針失敗成功是是是否有任何后繼節(jié)點為目標節(jié)點？2021/5/920§3.2盲目搜索3.舉例：八數(shù)碼難題

初始棋局

目標棋局2831476512384765283147652318476528316475283147652831476583214765283714652318476523184765283164752831647528143765283145768321476528371465123847652341876528364175283167542814376528314576832147658132476528374615283714651237846512384756123456789101112131415161718192021222325262728S0Sg2021/5/921§3.2盲目搜索(三).寬度優(yōu)先搜索的性質(zhì)當問題有解時，一定能找到解當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解方法與問題無關(guān)，具有通用性效率較低屬于圖搜索方法2021/5/922§3.2盲目搜索二．深度優(yōu)先搜索(一).深度優(yōu)先搜索總是先擴展最新產(chǎn)生的節(jié)點2021/5/923§3.2盲目搜索(二).OPEN表的排列算法

對于許多問題，其狀態(tài)搜索樹的深度可能為無限深或者可能至少要比某個可接受的解答序列的已知深度上限還要深，為了避免考慮太長的路徑：

1.深度界限：規(guī)定的一個節(jié)點擴展的最大深度

2.擴展節(jié)點：若不等于最大深度，將后裔節(jié)點放入OPEN表的前頭。2021/5/924§3.2盲目搜索3.搜索算法⑴把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)⑵如果OPEN表是一個空表，則失敗退出。⑶把第一個節(jié)點(節(jié)點n)從OPEN表移到CLOSED表。⑷如果節(jié)點n的深度等于最大深度，則轉(zhuǎn)向第⑵步。⑸擴展節(jié)點n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向(2.)⑹如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解答，成功退出；否則轉(zhuǎn)向第⑵步2021/5/925§3.2盲目搜索4.流程圖

開始把S放表入OPEN表OPEN表為空表把OPEN表中第一個節(jié)點n移至CLOSED表擴展節(jié)點n，把后裔放入OPEN表的前頭失敗成功是是是否有任何后繼節(jié)點為目標節(jié)點？S是否為目標節(jié)點？節(jié)點n的深度是否等于深度界限？是成功是否2021/5/926§3.2盲目搜索5.舉例231847652318476528314765231847652831476528316475283147652831647528316475283714658321476528143765283145761237846512384765283641752831675483214765283714652814376528314576123456789abcd12384765目標2021/5/927§3.2盲目搜索(三).深度優(yōu)先搜索的性質(zhì)一般不能保證找到最優(yōu)解當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制最壞情況時，搜索空間等同于窮舉是一個通用的與問題無關(guān)的方法2021/5/928§3.2盲目搜索三、等代價搜索(一).等代價搜索

1.問題的提出：有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解，這可通過代價來描述2.代價

(1)從節(jié)點I到它的后繼節(jié)點j的連線弧線代價記為C(i,j).(2)從起始節(jié)點到任一節(jié)點i的路徑代價記為g(i).3.等價搜索每次擴展的是代價最小的節(jié)點。2021/5/929§3.2盲目搜索(二).擴展算法擴展節(jié)點I

對于節(jié)點I的每個后繼節(jié)點，計算g(j)=g(i)+c(i,j)

按g(j)升序插入到OPEN表中。2021/5/930§3.3啟發(fā)式搜索

啟發(fā)式搜索是利用問題擁有的啟發(fā)信息來引導(dǎo)搜索,達到減少搜索范圍,降低問題復(fù)雜度的目的,這種利用啟發(fā)信息的搜索過程都稱為啟發(fā)式搜索方法。2021/5/931§3.3啟發(fā)式搜索§3.3.1啟發(fā)式搜索策略一.啟發(fā)信息1.啟發(fā)信息：具體問題領(lǐng)域的可用來簡化搜索的特性信息2.種類：(1)用于決定要擴展的下一個節(jié)點(以免象寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展)(2)在擴展一個節(jié)點的過程中，用于決定要生成那一個或那幾個后繼節(jié)點(以免盲目地同時生成所有可能的節(jié)點)(3)用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點2021/5/932§3.3啟發(fā)式搜索§3.3.1啟發(fā)式搜索策略二.啟發(fā)式搜索1.啟發(fā)式搜索：利用啟發(fā)信息的搜索方法。本節(jié)只討論利用第一種啟發(fā)信息的搜索2.有序搜索：利用第一種啟發(fā)信息，總是選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。2021/5/933§3.3啟發(fā)式搜索§3.3.2估價函數(shù)一.估價函數(shù)用來估算節(jié)點希望程度的量度二.估價函數(shù)考慮因素1.起始節(jié)點到此節(jié)點的距離(以減少搜索工作量為出發(fā)點)2.經(jīng)過此節(jié)點到達目標的代價(以最小代價為出發(fā)點)三.估價函數(shù)表示

f(n)我們可以用f函數(shù)來排列GRAPHSEARCH第8步中OPEN表上的節(jié)點。2021/5/934§3.3啟發(fā)式搜索§3.3.3有序搜索一.有序搜索算法開始把S放表入OPEN表，計算f(s)OPEN=NIL?選取OPEN表中f值最小的節(jié)點I放入CLOSED表擴展i,得后繼節(jié)點j，計算f(j),提供返回i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功是是i=Sg2021/5/935§3.3啟發(fā)式搜索

其中擴展節(jié)點i有下列幾步對有i的每一個后繼節(jié)點j:1.計算f(j)2.如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。3.如果j已在OPEN表上或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值。如果新的f值較小，則⑴以此新值取代舊值⑵從j指向i,而不是指向它的父輩節(jié)點。⑶如果節(jié)點j在CLOSED表中，則把它移回OPEN表。2021/5/936§3.3啟發(fā)式搜索

有序搜索的有效性直接取決于f的選擇二.舉例八數(shù)碼難題起始節(jié)點目標節(jié)點選用的估價函數(shù)f(n)=d(n)+w(n)d(n)是搜索樹中節(jié)點n的深度W(n)用來計算對應(yīng)于節(jié)點n中錯放棋子個數(shù)這樣起始節(jié)點f=0+4=42831647512347652021/5/9372021/5/938§3.3啟發(fā)式搜索1.OPEN={<1>}CLOSED={}2.OPEN={<3,1>、<2,1>、<4,1>}

CLOSED={<1,0>}3.OPEN={<5,3>、<6,3>、<2,1>、<4,1>、<7,3>}CLOSED={<1,0>、<3,1>}4.OPEN={<6,3>、<2,1>、<4,1>、<7,3>、<8,5>、<9,5>}CLOSED={<1,0>、<3,1>、<5,3>}5.OPEN={<10,6>、<2,1>、<4,1>、<7,3>、<8,5>、<9,5>、<11,6>}CLOSED={<1,0>、<3,1>、<5,3>、<6,3>}6.OPEN={<12,10>、<2,1>、<4,1>、<7,3>、<8,5>、<9,5>、<11,6>}CLOSED={<1,0>、<3,1>、<5,3>、<6,3>、<10,6>}7.OPEN={<13,12>、<2,1>、<4,1>、<7,3>、<8,5>、<9,5>、<11,6>、<14,12>}CLOSED={<1,0>、<3,1>、<5,3>、<6,3>、<10,6>、<12,10>}2021/5/939§3.3啟發(fā)式搜索三.小結(jié)

1.寬度優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。對于寬度優(yōu)先搜索，我們選擇f(i)作為節(jié)點i的深度。對于等代價搜索，f(i)是從起始節(jié)點至節(jié)點i這段路徑的代價。

2.有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準確的希望量度，那么f的選擇將涉及兩個方面的內(nèi)容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意

。2021/5/940§3.3啟發(fā)式搜索三.小結(jié)

3.節(jié)點希望量度以及某個具體估價函數(shù)的合適程度取決于手頭的問題情況。根據(jù)所要求的解答類型，可以把問題分為下列三種：

⑴假設(shè)狀態(tài)空間含有幾條不同代價的解答路徑，其問題是要求得最優(yōu)解答。⑵類似第一種情況，但難度相當大，實踐上不可能。處理該種情況的關(guān)鍵問題：如何通過適當?shù)乃阉髟囼炚业胶玫?但不是最優(yōu)的)解答；如何限制搜索試驗的范圍和所產(chǎn)生的解答與最優(yōu)解答的差異程度。⑶不考慮解答的最優(yōu)化；或者只存在一個解，或者任何一個解與其他解一樣好。問題是如何使搜索試驗的次數(shù)最少，而不是像第二種情況那樣試圖使某些搜索試驗和解答代價的綜合指標最小。2021/5/941§3.3啟發(fā)式搜索§3.3.4A*算法一.符號定義k(ni,nj):任意兩點ni和nj之間最小代價路徑的實際代價h*(n):節(jié)點n到目標集合{ti}上所有k(n,tj)中最小的一個g*(n)=k(s,n)f*(n)=g*(n)+h*(n)2021/5/942§3.3啟發(fā)式搜索§3.3.4A*算法二.定義設(shè)函數(shù)f是f*的一個估計

f(n)=g(n)+h(n)

其中g(shù)(n)是g*(n)的估計、h(n)是h*(n)的估計1.A算法：如果在圖搜索的第8步，依據(jù)f(n)=g(n)+h(n)重排OPEN表在A算法中，如果對所有x存在h(x)≤h*(n)，則稱h(x)為h*(n)的下界2.A*算法采用h*(n)的下界h(x)為啟發(fā)函數(shù)的A算法2021/5/943§3.3啟發(fā)式搜索三.A*算法選取f最小的節(jié)點擴展對每個后繼節(jié)點：1.建立后繼節(jié)點返回到該節(jié)點的指針2.計算g(suc)=g(bes)+g(best,suc)3.若suc已在OPEN表，suc=old，若g(suc)<g(old)，重新確定OLD的父輩節(jié)點為BES，并修改g值和f值4.若suc已在CLOSE表,suc=old，若g(suc)<g(old)，重新確定OLD的父輩節(jié)點為BES，并修改g值和f值5.把suc放入OPEN表，添進bestnode的后裔表6.計算f值。2021/5/944A*算法流程是開始把S放入OPEN表，記f=hOpen=NIL選取OPEN表上未設(shè)置過的具有最小f值的節(jié)點BESTNODE放入CLOSED表BESTNODE是目標節(jié)點嗎擴展BESTNODE產(chǎn)生其后繼節(jié)點SUCCESSOR建立從SUCCESSOR返回BESTNODE的指針計算f(suc)=g(suc)+h(bes,suc)suc∈OPEN?suc∈CLOSED?Suc=old,把它添到BESTNODE的后繼節(jié)點表中g(shù)(suc)<g(old)?重新確定OLD的父輩節(jié)點為BESTNODE，并修正父輩節(jié)點的g值和f值，記下g(OLD)計算f值把SUCCESSOR放入OPEN表，添進BESTNODE的后裔表失敗成功是是是是2021/5/945§3.3啟發(fā)式搜索四.A*算法的可采納性

A*算法是可采納的，即如果從初始結(jié)點到一個目標結(jié)點存在一條路徑，則A*算法必然以找到一條最佳路徑結(jié)束。啟發(fā)式函數(shù)h(n)對A*算法的效率起著重要影響，它的選取取決于問題領(lǐng)域所擁有的信息量。當h(n)=0時，反映了完全沒有啟發(fā)式信息的情況，這時搜索效率很低，h(n)越接近h*(n)，其信息量越大，搜索效率越高。2021/5/946§3.3啟發(fā)式搜索§3.3.5雙向搜索一.搜索方向

1.正向搜索：從初始狀態(tài)開始到目標狀態(tài)的搜索

2.逆向搜索：從目標狀態(tài)到初始狀態(tài)的搜索二.雙向搜索同時向兩個方向搜索，直至兩個方向的搜索邊域會合的搜索初始節(jié)點目標節(jié)點雙向搜索終止邊界單向搜索終止邊界2021/5/947§3.2啟發(fā)式搜索§3.2.5雙向搜索三.搜索方向的選擇具體情況具體分析例：寬度優(yōu)先搜索，雙向搜索過程比單向搜索擴展的節(jié)點要少許多啟發(fā)搜索，若啟發(fā)函數(shù)不精確，雙向搜索邊域互相穿過而不相交，那樣雙向過程擴展的節(jié)點數(shù)可能會是單向擴展節(jié)點的兩倍。初始節(jié)點目標節(jié)點逆向搜索邊界正向搜索邊界2021/5/948§3.4消解原理基本思想：根據(jù)E1∨E2和~E2∨E3

=>E1∨E2

（~E2=>E1和E2=>E3=>E1∨E2

）

在證明某個邏輯式為真時，先假設(shè)它為假，再與已知事實進行消解，得出矛盾，由此證明了邏輯式。即反證思想。2021/5/949§3.4消解原理

消解原理由J.A.Robinson由1965年提出。與演繹法完全不同，新的邏輯演算算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。而消解方法是自動推理、自動推導(dǎo)證明用的。（“數(shù)學定理機器證明”）2021/5/950§3.4消解原理消解過程

將命題寫成合取范式求出子句集對子句集使用消解推理規(guī)則消解式作為新子句參加消解消解式為空子句，S是不可滿足的（矛盾），原命題成立。2021/5/951§3.4消解原理

§3.4.1化為子句集

§3.4.2消解推理規(guī)則

§3.4.3含有變量的消解式

§3.4.4消解反演求解過程

§3.4.5含狀態(tài)項的回答語句的求取2021/5/952§3.4.1化為子句集例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1.消蘊涵符 理論根據(jù)：ab=>~ab (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2.移動否定符減少否定符號的轄域(反復(fù)應(yīng)用狄.摸根定律)

理論根據(jù)：~(ab)=>~a~b ~(ab)=>~a~b~(~a)=>a ~(x)P(x)=>(x)~P(x) ~(x)P(x)=>(x)~P(x)

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}2021/5/953§3.4.1化為子句集3.變量標準化(讓每個量詞有自己唯一的啞元)

即：對于不同的約束，對應(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化）

原則：對于一個受存在量詞約束的變量，如果他不受全程量詞約束，則該變量用一個常量代替，如果他受全程量詞約束，則該變量用一個skolem函數(shù)代替。

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}

=>(x){[(~P(x)~Q(x))R(f(x))]U(a)}

若消去的存在量詞不在任何一個全程量詞的轄域內(nèi)，skolem函數(shù)即是常數(shù)2021/5/954§3.3.1化為子句集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)]}2021/5/955§3.4.1化為子句集8.消去連詞符號∧，表示為子句集用{A，B}代替{A∧B}{~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)}使一個變量符號不出現(xiàn)在一個以上的子句中2021/5/956§3.4.1化為子句集舉例：(x){P(x)=>{(y)[P(y)=>P(f(x,y))]∧~

(y)[Q(x,y)=>P(y)]}}1.(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)]}}}(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧(y)[Q(x,y)∧~P(y)]}}3.(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧(w)[Q(x,w)∧~P(w)]}}4.(x){~P(x)∨{(y)[~P(y)∨P(f(x,y))]∧[Q(x,g(x))∧~P(g(x))]}}

其中w=g(x)為一skolem函數(shù)5.(x)(y){~P(x)∨{[~P(y)∨P(f(x,y))]∧[Q(x,g(x))∧~P(g(x))]}}

前綴母式6.(x)(y){[~P(x)∨~P(y)∨P(f(x,y))]∧[~P(x)∨Q(x,g(x))]∧[~P(x)∨~P(g(x))]}2021/5/957§3.4.1化為子句集7.[~P(x)∨~P(y)∨P(f(x,y))]∧[~P(x)∨Q(x,g(x))]∧[~P(x)∨~P(g(x))]8.~P(x)∨~P(y)∨P(f(x,y))~P(x)∨Q(x,g(x))~P(x)∨~P(g(x))9.~P(x1)∨~P(y)∨P(f(x1,y))~P(x2)∨Q(x2,g(x2))~P(x3)∨~P(g(x3))

可以證明，如果公式x在邏輯上遵循公式集s，那么x在邏輯上也遵循由s的公式變換成的子句集，因此子句是表示公式的一個完善的一般形式。在定理證明系統(tǒng)中，消解作為推理規(guī)則使用時，從公式集來證明某個定理，首先要把公式集化為子句集。2021/5/958§3.4.2消解推理規(guī)則L1、L2分別是原子公式，具有相同的謂詞符號，但一般具有不同的變量。已知：L1∨σ、~L2∨?，如果L1和L2具有最一般合一者λ，可以導(dǎo)出(σ∨?)λ消解式2021/5/959§3.4.2消解推理規(guī)則1.假言推理

父輩子句

P~P∨Q(P=>Q)

消解式Q2.合并父輩子句

P∨Q

~P∨Q

消解式Q∨Q=Q2021/5/960§3.4.2消解推理規(guī)則3.重言式

父輩子句

P∨Q

~P∨~Q

消解式Q∨~QP∨~P4.空子句(矛盾)

父輩子句

P~P

消解式NIL2021/5/961§3.4.2消解推理規(guī)則5.鏈式(三段論)

父輩子句

~P∨Q(P=>Q)

~Q∨R(Q=>P)

消解式~

P∨R(P=>R)2021/5/962§3.4.3含有變量的消解式

設(shè){li}是{Li}的一個子集，{mi}是{Mi}的一個子集，使得集{li}和{~mi}的并集存在最一般的合一者λ，消解兩個子句{Li}和{Mi}，得到的消解式

{{Li}-{li}}λ∪{{Mi}-{mi}}λ

注意：消解兩個子句時，因為有多種選擇{li}和{mi}的方法，可能有一個以上的消解式，但最多有有限個消解式。2021/5/963§3.4.3含有變量的消解式例：兩個子句

P[x，f(A)]∨P[x，f(y)]∨Q(y)

~P[z，f(A)]∨~Q(z)(1)取{li}={P[x，f(A)]}{mi}={~P[z，f(A)]}

得消解式P[z，f(y)]∨~Q(z)∨Q(y)(2)取{li}={Q(y)}{mi}={~Q(z)}

得消解式P[x，f(A)]∨P[x，f(y)]∨~P[y，f(A)]進一步消解得消解式為P[y，f(y)]2021/5/964§3.4.4消解反演求解過程

要證明某個命題，其目標公式被否定并化成子句形，添加到命題公式集中去，把消解反演系統(tǒng)應(yīng)用于聯(lián)合集，并推導(dǎo)出一個空子句(NIL)，產(chǎn)生一個矛盾，從而使定理得到證明。2021/5/965§3.4.4消解反演求解過程一.消解反演公式集S，目標公式L，通過反演求證目標公式L.證明步驟：

1.否定L，得~L;

2.把~L添加到S中去；

3.把新產(chǎn)生的集合{~L，S}化成子句集；

4.應(yīng)用消解原理，力圖推導(dǎo)出一個表示矛盾的空子句；2021/5/966§3.4.4消解反演求解過程舉例：前提：每個儲蓄錢的人都獲得利息結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢令：S(x,y)表示(x儲蓄y)M(x)表示“x是錢”

L(x)表示“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

)2021/5/967§3.4.4消解反演求解過程前提：(x)[(y)(S(x,y)∧M(y)=>(y)(I(y)∧E(x,y))]化為子句形

(x)[~(y)(S(x,y)∧M(y))∨(y)(I(y)∧E(x,y))](x)[

(y)(~(S(x,y)∧M(y)))∨(y)(I(y)∧E(x,y))](x)[

(y)(~S(x,y)∨~M(y)))∨(y)(I(y)∧E(x,y))]

令y=f(x)為skolem函數(shù)，則可得子句形如下

(1)~S(x,y)∨~M(y)))∨I(f(x))(2)~S(x,y)∨~M(y)))∨E(x,f(x))2021/5/968§3.4.4消解反演求解過程結(jié)論的否定：~(

~(x)I(x)=>(x)(y)(M(y)=>~S(x,y

))化為子句形

~(

(x)I(x)∨(x)(y)(~M(y)∨~S(x,y

))(~(x)I(x))∧(~(x)(y)(~M(y)∨~S(x,y

)))

((x)(~I(x)))∧(~(x)(y)(~M(y)∨~S(x,y

)))

((x)(~I(x)))∧((x)(~(y)(~M(y)∨~S(x,y

))))

((x)(~I(x)))∧((x)

(y)(~(~M(y)∨~S(x,y

))))((x)(~I(x)))∧((x)

(y)(M(y)∧S(x,y

)))變量分離標準化后得子句：

(3)~I(z)(4)S(a,b)(5)M(b)2021/5/969§3.4.4消解反演求解過程消解過程(1)~S(x,y)∨~M(y)))∨I(f(x))(3)~I(z){f(x)/z}(6)~S(x,y)∨~M(y)))(4)S(a,b){a/x,b/y}(7)~M(b)

(5)M(b)NIL儲蓄問題反演樹2021/5/970§3.4.4消解反演求解過程例2：設(shè)公理集：

(x)(R(x)L(x)) (x)(D(x)~L(x)) (x)(D(x)I(x))求證：(x)(I(x)~R(x))化子句集：

(x)(R(x)L(x))=>(x)(~R(x)L(x))=>~R(x)L(x)

(1)2021/5/971§3.4.4消解反演求解過程(x)(D(x)~L(x))=>(x)(~D(x)~L(x))=>~D(x)~L(x)(2) (x)(D(x)I(x))=>D(A)I(A)=>D(A)(3) I(A)(4)2021/5/972§3.4.4消解反演求解過程目標求反：

~(x)(I(x)~R(x))=>(x)~(I(x)~R(x))=>(x)(~I(x)R(x))=>~I(x)R(x)(5)換名后得字句集：

~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)2021/5/973例題得歸結(jié)樹 ~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)I(A)~I(x5)R(x5)R(A){A/x5}~R(x1)L(x1)L(A){A/x1}~D(x2)~L(x2)~D(A){A/x2}D(A)nil2021/5/974§3.4.4消解反演求解過程二.反演求解過程從反演樹求取對某個問題的答案過程：

1.由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定之否定的子句中去;

2.按照反演樹，執(zhí)行和以前相同的消解，直到根部得到某個子句止；

3.用根部的子句作為一個回答語句；根部的子句在邏輯上遵循公理加上重言式，因而也單獨地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。2021/5/975§3.4.4消解反演求解過程舉例：如果無論約翰到哪里去，菲多也就去那里，那么如果約翰在學校里，菲多在哪里呢？公式集：(x)[AT(John,x)=>AT(Fido,x)]AT(John,school)通過證明(x)(AT(Fido,x))在邏輯上遵循S,尋求一個存在x的例，就能解決“菲多在哪里”的問題目標公式的否定：

(x)(~AT(Fido,x))2021/5/976§3.4.4消解反演求解過程目標公式的否定：(x)(~AT(Fido,x))

子句形為~AT(Fido,x)用反演樹進行消解~AT(Fido,x)~AT(John,x)∨AT(Fido,x)~AT(John,x)AT(John,school)Nil2021/5/977§3.4.4消解反演求解過程目標公式的否定：(x)(~AT(Fido,x))

子句形為~AT(Fido,x)

重言式為~AT(Fido,x)∨AT(Fido,x)用反演樹進行消解~AT(Fido,x)∨AT(Fido,x)~AT(John,x)∨AT(Fido,x)~AT(John,x)∨AT(Fido,x)AT(John,school)AT(Fido,school)在根部得到子句AT(Fido,school)，它就是這個問題的合適答案。2021/5/978§3.4.4消解反演求解過程

提取回答的過程先進行歸結(jié)，證明結(jié)論的正確性；用重言式代替結(jié)論求反得到的子句；按照證明過程，進行歸結(jié)；最后，在原來為空的地方，得到的就是提取的回答。修改后的證明樹稱為修改證明樹2021/5/979作業(yè)

2021/5/980作業(yè)證明：前提：1)小李(Li)喜歡容易(Easy)的課程(Course)。x[(Course(x)Easy(x))Like(Li,x))]2)小李不喜歡難(Difficult)的課程.x[(Course(x)Difficult(x))Like(Li,x)]3)工程類(Eng)課程都是難的。x[(Course(x)Eng(x))Difficult(x)]4)物理類(Phy)課程都是容易的。x[(Course(x)Phy(x))Easy(x)]5)小吳(Wu)喜歡所有小李不喜歡的課程。x[(Course(x)Like(Li,x))Like(Wu,x)]6)Phy200是物理類課程。

Course(Phy200)Phy(Phy200)7)Eng300是工程類課程

Course(Eng300)Eng(Eng300)2021/5/981作業(yè)化為子句集：Course(x1)Easy(x1)Like(Li,x1)(1)Course(x2)Difficult(x2)Like(Li,x2)(2)Course(x3)Eng(x3)Difficult(x3)(3)Course(x4)Phy(x4)Easy(x4)(4)Course(x5)Like(Li,x5)Like(Wu,x5)(5)Course(Phy200)(6)Phy(Phy200)(7)Course(Eng300)(8)Eng(Eng300)(9)目標：2小吳喜歡Eng300課程

Like(Wu,Eng300)目標取反：Like(Wu,Eng300)（10）2021/5/982作業(yè)歸結(jié)過程：Like(Wu,Eng300)(10)Course(x5)Like(Li,x5)Like(Wu,x5)(5)Course(Eng300)Like(Li,Eng300)Course(x2)Difficult(x2)Like(Li,x2)(2)Course(Eng300)Difficult(Eng300)Course(x3)Eng(x3)Difficult(x3)(3)Course(Eng300)Eng(Eng300)Course(Eng300)(8)Eng(Eng300)Eng(Eng300)(9)NIL目標1得證.2021/5/983作業(yè)目標2小李喜歡什么課程xLike(Li,x)目標取反：Like(li,x)（11）歸結(jié)過程Course(x1)Easy(x1)Like(Li,x1)(1)Like(li,x)（11）Course(x1)Easy(x1)Course(x4)Phy(x4)Easy(x4)(4)Course(x4)Phy(x4)Course(Phy200)(6)Phy(Phy200)Phy(Phy200)(7)Nil2021/5/984作業(yè)反演求解：Course(x1)Easy(x1)Like(Li,x1)(1)Like(li,x)Like(li,x)

Course(x1)Easy(x1)Like(li,x1)

Course(x4)Phy(x4)Easy(x4)(4)Course(x4)Phy(x4)Like(li,x4)

Course(Phy200)(6)Phy(Phy200)Like(li,Phy200)

Phy(Phy200)(7)

Like(li,Phy200)

由此得出小李喜歡Phy200.2021/5/985§3.5規(guī)則演繹系統(tǒng)基于規(guī)則的問題求解系統(tǒng)用下述規(guī)則來建立：

If→Then

其中：

if可能與某斷言集中的一個或多個斷言匹配有時then部分用于產(chǎn)生新斷言，這種基于規(guī)則的系統(tǒng)叫做規(guī)則演義系統(tǒng)；有時then部分用于規(guī)定動作，這種系統(tǒng)叫做產(chǎn)生式系統(tǒng)。2021/5/986§3.5規(guī)則演繹系統(tǒng)

將有關(guān)問題的知識和信息劃分成規(guī)則與事實兩種類型。規(guī)則有包含蘊涵形式的表達式表示，事實由無蘊涵形式的表達式表示，這種推理系統(tǒng)稱為基于規(guī)則的演繹系統(tǒng)。2021/5/987§3.5.1規(guī)則正向演繹系統(tǒng)正向推理：從if部分向then部分推理的過程事實目標規(guī)則2021/5/9883.5.1規(guī)則正向演繹系統(tǒng)一.事實表達式的與或形變換二.事實表達式的與或圖表示三.與或圖的F規(guī)則變換四.作為終止條件的目標公式2021/5/989一.事實表達式的與或形變換1.事實化為與或形表示與或形無量詞約束否定符只作用于單個文字只有“與”、“或”2021/5/990一.事實表達式的與或形變換2.變換過程⑴消去蘊涵符“”⑵減少否定符號“”的轄域⑶進行skolem化和前束化⑷對變量標準化、使得同一變量不出現(xiàn)在事實表達式的不同主要合取式中⑸刪除全程量詞2021/5/991一.事實表達式的與或形變換例：事實表達式(u)(v){Q(v,u)∧[(R(v)V(P(v))∧S(u,v)]}減少否定符號“”的轄域(u)(v){Q(v,u)∧[(R(v)∧(P(v))V

S(u,v)]}進行skolem化Q(v,A)∧[(R(v)∧(P(v))V

S(A,v)]對變量標準化Q(w,A)∧[(R(v)∧(P(v))V

S(A,v)]2021/5/992二.事實表達式的與或圖表示

將表達式作為節(jié)點，子表達式作為后繼節(jié)點，若為析取關(guān)系，要用“K”線連接符來標注，葉節(jié)點均由表達式中的文字來標注。2021/5/993二.事實表達式的與或圖表示例：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)子句集：Q(w,A)、~R(v)~S(A,v)、~P(v)~S(A,v)因此，可把與或圖看做是對子句集的簡潔表示一般把事實表達式的與或圖表示倒過來畫，根節(jié)點在最下面、后繼節(jié)點在上

2021/5/994三.與或圖的F規(guī)則變換1.規(guī)則的形式

LW其中，L是單文字，W是與或形且假設(shè)出現(xiàn)在蘊涵式中的任何變量都有全稱量詞作用于整個蘊涵式如果不符合要求，可轉(zhuǎn)化為符合要求步驟：⑴暫時消去蘊涵符號⑵減少否定轄域⑶進行Skolem化⑷把所有全程量詞移至前面后消去⑸恢復(fù)蘊涵式2021/5/995三.與或圖的F規(guī)則變換例：(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)=>P(x,y,f(x,y))Q(x,u)P(x1,y1,f(x1,y1))Q(x1,u1) 換名例：(L1L2)W =>L1W和L2W2021/5/996三.與或圖的F規(guī)則變換2.將F規(guī)則作用到與或圖上

將LW形式的規(guī)則應(yīng)用到標有L標記的葉節(jié)點的與或圖上，得到一個新的與或圖例如：下列與或圖((PQ)R)(S(TU))(PQ)RS(TU)PQRSTUPQTU2021/5/997三.與或圖的F規(guī)則變換應(yīng)用S(X∧Y)∨Z規(guī)則后得到的與或圖((PQ)R)(S(TU))(PQ)RS(TU)PQRSTUPQTUSXYZXYPQSPQTUSRRTUPQXZPQYZRXZRYZ規(guī)則的子句：

S(XY)Z=>~S(XY)Z=>~SXZ

~SYZ2021/5/998四.作為終止條件的目標公式

目標公式為文字析取形式目標文字和規(guī)則可用來對與或圖添加后繼結(jié)點，當一個目標文字與該圖中文字節(jié)點n上的一個文字相匹配時，對該圖添這個節(jié)點n的新后裔，并標記為匹配的目標文字，用匹配弧接到它的父輩節(jié)點上直到包含有終止在目標節(jié)點上的解圖時，系統(tǒng)便成功地結(jié)束。例如：

事實：AB

規(guī)則集：ACDBEG

目標公式：CG2021/5/999四.作為終止條件的目標公式

正向演繹證明；

當正向演繹系統(tǒng)產(chǎn)生一個含有以目標節(jié)點作為終止的解圖時，此系統(tǒng)就成功地終止。ABABACDBEGCG目標2021/5/9100五.含有變量的情況事實表達式化成與或形規(guī)則化成LW的形式，其中L為單文字目標用Skolem化的對偶形式，即消去全稱量詞，用Skolem函數(shù)代替保留存在量詞對析取元作變量換名例：(y)(x)(P(x,y)Q(x,y))=>(y)(P(f(y),y)Q(f(y),y))=>P(f(y1),y1)Q(f(y2),y2) 換名規(guī)則每使用一次，都要進行一次換名2021/5/9101五.含有變量的情況例：事實：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)P(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)2021/5/9102五.含有變量的情況一致解圖如果一個解圖中所涉及的置換是一致的，則該解圖稱為一致解圖。設(shè)有置換集{u1,u2,…,un},其中:ui={ti1/vi1,…,in/vin}，定義表達式：U1=(v1,1,…,v1,m1,…,vn,1,…,vn,mn) U2=(t1,1,…,t1,m1,…,tn,1,…,tn,mn)

置換集{u1,u2,…,un}稱為一致的，當且僅當U1和U2是可合一的。U1、U2的mgu是{u1,u2,…,un}的合一復(fù)合。置換集的合一復(fù)合運算是可結(jié)合和可交換的。2021/5/9103一致置換舉例2021/5/9104舉例事實：

~D(F)(B(F)I(F))規(guī)則：

R1:~D(x)~T(x) R2:B(y)N(y)目標：

~T(u)N(v)2021/5/9105~D(F)(B(F)I(F))~D(F)B(F)I(F)B(F)I(F)~D(x){F/x}~T(F)R1~T(u){F/u}B(y){F/y}N(F)R2N(v){F/v}目標目標U1=(x,u,y,v)U2=(F,F,F,F)合一復(fù)合u：{F/x,F/u,F/y,F/v}作用于目標：

[~T(u)N(v)]u=~T(F)N(F)2021/5/9106正向演繹系統(tǒng)小結(jié)事實表達式為與或形規(guī)則形式：LW,其中L為單文字目標公式為文字析取對事實和規(guī)則進行Skolem化，消去存在量詞，變量受全稱量詞約束，對主合取元和規(guī)則中的變量換名用“對偶形”對目標進行Skolem化，消去全稱量詞，變量受存在量詞約束，對析取元中的變量換名事實表達成與或樹，其中，“”對應(yīng)樹中“與”，“”對應(yīng)樹中“或”從事實出發(fā)，正向應(yīng)用規(guī)則，到得到目標節(jié)點為結(jié)束的一致解圖為止存在合一復(fù)合時，則解圖是一致的2021/5/9107§3.5.2規(guī)則逆向演繹系統(tǒng)一.推理過程二.目標表達式的與或形三.與或圖的B規(guī)則變換四.作為終止條件的事實節(jié)點的一致解圖2021/5/9108一.推理過程

從目標公式出發(fā)，逆向應(yīng)用規(guī)則不斷推導(dǎo)出子目標，直至所有子目標就是給定的事實為止。換言之，目標公式通過逆向推理找到了支持其成立的所有依據(jù)。2021/5/9109二.目標表達式的與或形1.將目標表達式化為與或形

消去蘊涵符“”把否定符移進符號括號內(nèi)對全程量詞Skolem化刪去存在量詞主要析取式中的變量分離標準化2.將與或形的目標公式用下述形式的與或圖表示“合取”關(guān)系的子表達式要用K線連接符注明2021/5/9110舉例：(y)(x){P(x)=>[Q(x,y)∧~[R(x)∧S(y)]])

化為與或形為

~P(f(y))

{Q(f(y),y)∧[~R(f(y))

~

S(y)]}

分離標準化后

~P(f(z))

{Q(f(y),y)∧[~R(f(y))

~

S(y)]}與或圖為：~P(f(z)){Q(f(y),y)∧[~R(f(y))∧~S(y)]}~P(f(z)){Q(f(y),y)∧[~R(f(y))

~S(y)]}Q(f(y),y)~R(f(y))

~S(y)~R(f(y))~S(y)2021/5/9111二.目標表達式的與或形

目標公式的子句形是目標子句的析取，而目標子句則是文字的合取

上例中的子句集為：~P(f(z))Q(f(y),y)∧~R(f(y))Q(f(y),y)∧~S(y)2021/5/9112三.與或圖的B規(guī)則變換1.規(guī)則的形式

W=>L

其中W為任一與或形公式，L為文字且蘊涵式中任何變量的量詞轄域為整個蘊涵式

W=>(L1∧L2)可化為兩個規(guī)則：W=>L1和W=>L22.把B規(guī)則作用到目標與或圖上在目標公式的與或圖中，如果有一個文字L’能夠與L合一，則可應(yīng)用B規(guī)則W=>L。應(yīng)用的結(jié)果是將L’結(jié)點通過一個標有L和L’的最簡合一者u的匹配弧與結(jié)點L相連，結(jié)點L作為W的與或圖的根結(jié)點。一條規(guī)則可使用多次，每次都使用不同的變量。2021/5/9113四.作為終止條件的事實節(jié)點的一致解圖

逆向系統(tǒng)中的事實表達式均限制為文字合取形，它可以表示為一個文字集。當一個事實文字和標在該圖文字節(jié)點上的文字相匹配時，就可把相應(yīng)的后裔事實節(jié)點添加到該與或圖中去。這個事實節(jié)點通過標有mgu的匹配弧與匹配的子目標文字節(jié)點連接起來。同一個事實文字可以多次重復(fù)使用，每次用不同變量。

逆向系統(tǒng)成功的終止條件是與或圖包含有某個終止在事實節(jié)點上的一致解圖。2021/5/9114舉例：事實：F1:DOG(FIDO)