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

搜索推理技術(shù)

從問(wèn)題的表示到問(wèn)題的解決是一個(gè)求解的過(guò)程，也就是搜索過(guò)程。在這一過(guò)程中，采用適當(dāng)?shù)乃阉骷夹g(shù)，包括各種規(guī)則、過(guò)程和算法等推理技術(shù)，力求找到問(wèn)題的解答。本章首先介紹圖搜索策略的一般過(guò)程，接著討論一些早期的搜索技術(shù)或用于解決比較簡(jiǎn)單問(wèn)題的搜索原理，然后研究一些比較新的能夠求解比較復(fù)雜問(wèn)題的推理技術(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ù)

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

搜索方法好的標(biāo)準(zhǔn),一般認(rèn)為有兩個(gè)：

(1)搜索空間小;

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

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

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

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

2021/5/96§3.1.1圖搜索策略二.圖搜索過(guò)程

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

OPEN～表存放未擴(kuò)展節(jié)點(diǎn)

CLOSED～表存放已擴(kuò)展節(jié)點(diǎn)1.圖搜索過(guò)程

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

(2)建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。

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

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

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

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

(8)按某一任意方式或按某個(gè)探試值，重排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求解目標(biāo)節(jié)點(diǎn)235647384×2021/5/99§3.1.1圖搜索策略2.流程圖

開(kāi)始把S放表入OPEN表中OPEN表為空表把第一個(gè)節(jié)點(diǎn)n從OPEN表移至CLOSED表N為目標(biāo)節(jié)點(diǎn)把節(jié)點(diǎn)n的后繼節(jié)點(diǎn)放入OPEN表，提供返回節(jié)點(diǎn)n的指針修正指針?lè)较蛑嘏臤PEN表失敗成功是是①②③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.遺留問(wèn)題①n的某后繼節(jié)點(diǎn)已在OPEN表中或CLOSED表中有了是否需要修改指針，對(duì)已存在的后繼節(jié)點(diǎn)②按什么方式重排OPEN表寬度優(yōu)先搜索深度優(yōu)先搜索等代價(jià)搜索搜索控制方法2021/5/916§3.2盲目搜索

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

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

以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)

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

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

初始棋局

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

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

1.深度界限：規(guī)定的一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度

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

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

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

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

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

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

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

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

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

有序搜索的有效性直接取決于f的選擇二.舉例八數(shù)碼難題起始節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)選用的估價(jià)函數(shù)f(n)=d(n)+w(n)d(n)是搜索樹(shù)中節(jié)點(diǎn)n的深度W(n)用來(lái)計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n中錯(cuò)放棋子個(gè)數(shù)這樣起始節(jié)點(diǎn)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)先搜索、等代價(jià)搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。對(duì)于寬度優(yōu)先搜索，我們選擇f(i)作為節(jié)點(diǎn)i的深度。對(duì)于等代價(jià)搜索，f(i)是從起始節(jié)點(diǎn)至節(jié)點(diǎn)i這段路徑的代價(jià)。

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

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

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

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

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

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

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

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

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

=>E1∨E2

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

）

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

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

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

§3.4.1化為子句集

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

§3.4.3含有變量的消解式

§3.4.4消解反演求解過(guò)程

§3.4.5含狀態(tài)項(xiàng)的回答語(yǔ)句的求取2021/5/952§3.4.1化為子句集例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1.消蘊(yùn)涵符 理論根據(jù)：ab=>~ab (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2.移動(dòng)否定符減少否定符號(hào)的轄域(反復(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.變量標(biāo)準(zhǔn)化(讓每個(gè)量詞有自己唯一的啞元)

即：對(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è)skolem函數(shù)代替。

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

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

若消去的存在量詞不在任何一個(gè)全程量詞的轄域內(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.消去連詞符號(hào)∧，表示為子句集用{A，B}代替{A∧B}{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}

最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取，稱(chēng)作一個(gè)子句。9.變量標(biāo)準(zhǔn)化（變量換名）{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中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的公式變換成的子句集，因此子句是表示公式的一個(gè)完善的一般形式。在定理證明系統(tǒng)中，消解作為推理規(guī)則使用時(shí)，從公式集來(lái)證明某個(gè)定理，首先要把公式集化為子句集。2021/5/958§3.4.2消解推理規(guī)則L1、L2分別是原子公式，具有相同的謂詞符號(hào)，但一般具有不同的變量。已知：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.鏈?zhǔn)?三段論)

父輩子句

~P∨Q(P=>Q)

~Q∨R(Q=>P)

消解式~

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

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

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

注意：消解兩個(gè)子句時(shí)，因?yàn)橛卸喾N選擇{li}和{mi}的方法，可能有一個(gè)以上的消解式，但最多有有限個(gè)消解式。2021/5/963§3.4.3含有變量的消解式例：兩個(gè)子句

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)]進(jìn)一步消解得消解式為P[y，f(y)]2021/5/964§3.4.4消解反演求解過(guò)程

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

1.否定L，得~L;

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

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

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

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消解反演求解過(guò)程前提：(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消解反演求解過(guò)程結(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

)))變量分離標(biāo)準(zhǔn)化后得子句：

(3)~I(z)(4)S(a,b)(5)M(b)2021/5/969§3.4.4消解反演求解過(guò)程消解過(guò)程(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儲(chǔ)蓄問(wèn)題反演樹(shù)2021/5/970§3.4.4消解反演求解過(guò)程例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消解反演求解過(guò)程(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消解反演求解過(guò)程目標(biāo)求反：

~(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é)樹(shù) ~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消解反演求解過(guò)程二.反演求解過(guò)程從反演樹(shù)求取對(duì)某個(gè)問(wèn)題的答案過(guò)程：

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

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

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

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

子句形為~AT(Fido,x)用反演樹(shù)進(jìn)行消解~AT(Fido,x)~AT(John,x)∨AT(Fido,x)~AT(John,x)AT(John,school)Nil2021/5/977§3.4.4消解反演求解過(guò)程目標(biāo)公式的否定：(x)(~AT(Fido,x))

子句形為~AT(Fido,x)

重言式為~AT(Fido,x)∨AT(Fido,x)用反演樹(shù)進(jìn)行消解~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)，它就是這個(gè)問(wèn)題的合適答案。2021/5/978§3.4.4消解反演求解過(guò)程

提取回答的過(guò)程先進(jìn)行歸結(jié)，證明結(jié)論的正確性；用重言式代替結(jié)論求反得到的子句；按照證明過(guò)程，進(jìn)行歸結(jié)；最后，在原來(lái)為空的地方，得到的就是提取的回答。修改后的證明樹(shù)稱(chēng)為修改證明樹(shù)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)工程類(lèi)(Eng)課程都是難的。x[(Course(x)Eng(x))Difficult(x)]4)物理類(lèi)(Phy)課程都是容易的。x[(Course(x)Phy(x))Easy(x)]5)小吳(Wu)喜歡所有小李不喜歡的課程。x[(Course(x)Like(Li,x))Like(Wu,x)]6)Phy200是物理類(lèi)課程。

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

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)目標(biāo)：2小吳喜歡Eng300課程

Like(Wu,Eng300)目標(biāo)取反：Like(Wu,Eng300)（10）2021/5/982作業(yè)歸結(jié)過(guò)程：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目標(biāo)1得證.2021/5/983作業(yè)目標(biāo)2小李喜歡什么課程xLike(Li,x)目標(biāo)取反：Like(li,x)（11）歸結(jié)過(guò)程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ī)則的問(wèn)題求解系統(tǒng)用下述規(guī)則來(lái)建立：

If→Then

其中：

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

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

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

S(A,v)]對(duì)變量標(biāo)準(zhǔn)化Q(w,A)∧[(R(v)∧(P(v))V

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

將表達(dá)式作為節(jié)點(diǎn)，子表達(dá)式作為后繼節(jié)點(diǎn)，若為析取關(guān)系，要用“K”線連接符來(lái)標(biāo)注，葉節(jié)點(diǎn)均由表達(dá)式中的文字來(lái)標(biāo)注。2021/5/993二.事實(shí)表達(dá)式的與或圖表示例：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)因此，可把與或圖看做是對(duì)子句集的簡(jiǎn)潔表示一般把事實(shí)表達(dá)式的與或圖表示倒過(guò)來(lái)畫(huà)，根節(jié)點(diǎn)在最下面、后繼節(jié)點(diǎn)在上

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

LW其中，L是單文字，W是與或形且假設(shè)出現(xiàn)在蘊(yùn)涵式中的任何變量都有全稱(chēng)量詞作用于整個(gè)蘊(yùn)涵式如果不符合要求，可轉(zhuǎn)化為符合要求步驟：⑴暫時(shí)消去蘊(yùn)涵符號(hào)⑵減少否定轄域⑶進(jìn)行Skolem化⑷把所有全程量詞移至前面后消去⑸恢復(fù)蘊(yùn)涵式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)用到標(biāo)有L標(biāo)記的葉節(jié)點(diǎn)的與或圖上，得到一個(gè)新的與或圖例如：下列與或圖((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四.作為終止條件的目標(biāo)公式

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

事實(shí)：AB

規(guī)則集：ACDBEG

目標(biāo)公式：CG2021/5/999四.作為終止條件的目標(biāo)公式

正向演繹證明；

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

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

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

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

~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}目標(biāo)目標(biāo)U1=(x,u,y,v)U2=(F,F,F,F)合一復(fù)合u：{F/x,F/u,F/y,F/v}作用于目標(biāo)：

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

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

消去蘊(yùn)涵符“”把否定符移進(jìn)符號(hào)括號(hào)內(nèi)對(duì)全程量詞Skolem化刪去存在量詞主要析取式中的變量分離標(biāo)準(zhǔn)化2.將與或形的目標(biāo)公式用下述形式的與或圖表示“合取”關(guān)系的子表達(dá)式要用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)]}

分離標(biāo)準(zhǔn)化后

~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二.目標(biāo)表達(dá)式的與或形

目標(biāo)公式的子句形是目標(biāo)子句的析取，而目標(biāo)子句則是文字的合取

上例中的子句集為：~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為文字且蘊(yùn)涵式中任何變量的量詞轄域?yàn)檎麄€(gè)蘊(yùn)涵式

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

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

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