安徽大學(xué)高級人工智能2

人工智能ArtificialIntelligence第二章知識表示與推理2.1知識表示的普通方法2.2圖搜索戰(zhàn)略2.3普通搜索與推理技術(shù)2.4A*算法2.5消解原理2.6規(guī)那么演義系統(tǒng)2.7產(chǎn)生式系統(tǒng)2.8系統(tǒng)組織技術(shù)2.1知識表示的普通方法普通計算機科學(xué)數(shù)據(jù)構(gòu)造+算法人工智能(知識表示+搜索)+推理1/6/20243安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.1知識表示的普通方法問題求解技術(shù)主要是兩個方面：問題的表示求解的方法形狀空間法形狀〔state〕算符〔operator〕形狀空間方法1/6/20244安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.1知識表示的普通方法問題規(guī)約法大問題化為假設(shè)干小問題本原問題謂詞邏輯法合式公式消解算法(歸結(jié))1/6/20245安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.1知識表示的普通方法語義網(wǎng)絡(luò)法結(jié)點表示概念弧表示關(guān)系框架法槽、側(cè)面層次構(gòu)造框架可以嵌套框架1/6/20246安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.1知識表示的普通方法劇本場景角色事件過程問題求解的算法1/6/20247安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.2圖搜索戰(zhàn)略圖搜索控制戰(zhàn)略

一種在圖中尋覓途徑的方法。

圖中每個節(jié)點對應(yīng)一個形狀，每條連線對應(yīng)一個操作符。這些節(jié)點和連線(即形狀與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)那么來標(biāo)志。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)那么序列問題就等價于求得圖中的一條途徑問題。圖搜索過程圖1/6/20248安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.2圖搜索戰(zhàn)略開場把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目的節(jié)點嗎？把n的后繼節(jié)點放入OPEN表中，提供前往節(jié)點n的指針修正指針方向重排OPEN表失敗勝利是是否否1/6/20249安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.3普通搜索與推理技術(shù)盲目搜索特點：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價搜索等。啟發(fā)式搜索特點：重排OPEN表，選擇最有希望的節(jié)點加以擴展；估價函數(shù)種類：有序搜索、A*算法、AO*算法等1/6/202410安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.4A*算法1、為什么需求啟發(fā)式搜索盲目搜索效率低，耗費過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)方式。2、定義進展搜索技術(shù)普通需求某些有關(guān)詳細(xì)問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。1/6/202411安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.4A*算法3、啟發(fā)式搜索戰(zhàn)略 有關(guān)詳細(xì)問題領(lǐng)域的信息經(jīng)?？梢杂脕砗喕阉?。一個比較靈敏(但代價也較大)的利用啟發(fā)信息的方法是運用某些準(zhǔn)那么來重新陳列每一步OPEN表中一切節(jié)點的順序。然后，搜索就能夠沿著某個被以為是最有希望的邊緣區(qū)段向外擴展。運用這種排序過程，需求某些估算節(jié)點“希望〞的量度，這種量度叫做估價函數(shù)(evalutionfunction)。1/6/202412安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.4A*算法4、估價函數(shù) 為獲得某些節(jié)點“希望〞的啟發(fā)信息，提供一個評定侯選擴展節(jié)點的方法，以便確定哪個節(jié)點最有能夠在通向目的的最正確途徑上。

f(n)——表示節(jié)點n的估價函數(shù)值 建立估價函數(shù)的普通方法：試圖確定一個處在最正確途徑上的節(jié)點的概率；提出恣意節(jié)點與目的集之間的間隔量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點來決議棋局的得分?jǐn)?shù)。這些特點被以為與向目的節(jié)點前進一步的希望程度有關(guān)。1/6/202413安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.4A*算法估價函數(shù)的定義：

對節(jié)點n定義f*(n)=g*(n)+h*(n),表示從S開場約束經(jīng)過節(jié)點n的一條最正確途徑的代價。

希望估價函數(shù)f定義為：f(n)=g(n)+h(n)

——g是g*的估計，h是h*的估計A*算法的定義：

定義1在GRAPHSEARCH過程中，假設(shè)第8步的重排OPEN表是根據(jù)f(x)=g(x)+h(x)進展的，那么稱該過程為A算法。定義2在A算法中，假設(shè)對一切的x存在h(x)≤h*(x),那么稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。定義3采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)g=0時，A*算法就變?yōu)橛行蛩阉魉惴?；h=0時，A*算法就變?yōu)榈却鷥r搜索算法。1/6/202414安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.4A*算法開場把S放入OPEN表，估價函數(shù)f=hOPEN=NIL？選取OPEN表中未設(shè)置過的、f值最小的節(jié)點BESTNODE放入CLOSED表BESTNODE為目的節(jié)點嗎？計算g(SUC)=g(BES)+k(BES,SUC)失敗勝利是否是否擴展BESTNODE，產(chǎn)生后繼節(jié)點SUCCESSOR建立從SUCCESSOR前往BESTNODE的指針AB

1/6/202415安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.4A*算法SUC∈OPEN？SUC是OLD的復(fù)本,把OLD添加到BESTNODE的后繼節(jié)點表中g(shù)(SUC)<g(OLD)？計算f值是否是否重新確定OLD的父輩節(jié)點為BESTNODE，并修正父輩節(jié)點的g值和f值，記下g(OLD)把SUCCESSOR放入OPEN表，并參與BESTNODE的后裔表ABSUC=CLOSED？A否是1/6/202416安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗1A*算法實驗例子:八數(shù)碼難題〔8-puzzleproblem〕1238456712384567〔目的形狀〕規(guī)定：牌可以移入臨近的空格，不許斜向挪動，也不前往先輩節(jié)點。12384567〔初始形狀〕1/6/202417安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗1A*算法實驗實驗內(nèi)容：用A*算法求解8數(shù)碼和15數(shù)碼難題實驗報考要求畫出A*算法求解流程圖，給出中心程序。畫出8數(shù)碼求解圖分析估價函數(shù)對搜索算法的影響。分析A*算法的特點。1/6/202418安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5消解原理回想： 原子公式〔atomicformulas〕P(x),Q(x,y) 文字—一個原子公式及其否認(rèn)?！玃(x),R(x,y,z) 子句—由文字的析取組成的適宜公式。P(x)∨~Q(x,y) 消解—對謂詞演算公式進展分解和化簡，消去一些符號，以求得導(dǎo)出子句。2.5.1子句集的求取步驟：共9步。1/6/202419安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院例子:將以下謂詞演算公式化為一個子句集(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}開場：消去蘊涵符號只運用∨和～符號，以～A∨B交換AB。(1)(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}1/6/202420安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院(2)減少否認(rèn)符號的轄域每個否認(rèn)符號～最多只用到一個謂詞符號上，并反復(fù)運用狄·摩根定律。(3)對變量規(guī)范化對啞元〔虛擬變量〕改名，以保證每個量詞有其本人獨一的啞元。(2)(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)］｝｝1/6/202421安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院(4)消去存在量詞以Skolem函數(shù)替代存在量詞內(nèi)的約束變量，然后消去存在量詞化為前束形把一切全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形={前綴}{母式}全稱量詞串無量詞公式(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))］｝｝1/6/202422安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否認(rèn)的析取的有限集組成的合取。(7)消去全稱量詞一切余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。(6)(x)(y)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝(7)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝1/6/202423安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院(8)消去連詞符號∧用{A,B}替代(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9)改換變量稱號可以改換變量符號的稱號，使一個變量符號不出如今一個以上的子句中。(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)］1/6/202424安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.2消解推理規(guī)那么消解式的定義

令L1，L2為兩恣意原子公式；L1和L2具有一樣的謂詞符號，但普通具有不同的變量。知兩子句L1∨α和～L2∨β,假設(shè)L1和L2具有最普通合一σ，那么經(jīng)過消解可以從這兩個父輩子句推導(dǎo)出一個新子句(α∨β)σ。這個新子句叫做消解式。消解式求法取兩個子句，進展析取，然后消去互補對。1/6/202425安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.2消解推理規(guī)那么P ~P∨QQ1、假言推理2、合并P∨Q ~P∨QQ3、重言式P∨Q ~P∨~QTP∨~PQ∨~Q5、三段論~P∨Q ~Q∨R~P∨R4、矛盾P ~PF1/6/202426安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.3含有變量的消解式要把消解推理規(guī)那么推行到含有變量的子句，必需找到一個作用于父輩子句的置換，使父輩子句含有互補文字。含有變量的子句之消解式例2.1B(x) ～B(x)∨C(x)C(x)1/6/202427安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.3含有變量的消解式例2.3P[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}例2.2P(x)∨Q(x) ～Q[f(y)] P[f(y)]σ={f(y)/x}1/6/202428安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.4消解反演求解過程消解反演給出{S}，L否認(rèn)L，得～L；把～L添加到S中去；把新產(chǎn)生的集合｛～L，S｝化成子句集；運用消解原理，力圖推導(dǎo)出一個表示矛盾的空子句例子—儲蓄問題前提：每個儲蓄錢的人都獲得利息。結(jié)論：假設(shè)沒有利息，那么就沒有人去儲蓄錢1/6/202429安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.4消解反演求解過程(1〕規(guī)定原子公式： S(x,y)表示“x儲蓄y〞M(x)表示“x是錢〞 I(x)表示“x是利息〞 E(x，y)表示“x獲得y〞(2〕用謂詞公式表示前提和結(jié)論：前提：(x)[(y)(S(x,y))∧M(y)][(y)(I(y)∧E(x,y))]結(jié)論：～(x)I(x)(x)(y)[M(y)～S(x,y)](3)化為子句形證明：1/6/202430安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院把前提化為子句形：1)～S(x,y)∨～M(y)∨I(f(x))2)～S(x,y)∨～M(y)∨E(x,f(x))把結(jié)論化為子句形：3)～I(z)4)S(a,b)5)M(b)(4)消解反演求NIL圖3.12儲蓄問題反演樹子句〔1〕子句〔3〕f(x)/z～M(b)NIL子句〔5〕子句〔7〕子句〔4〕{a/x,b/y}～S(x,y)∨～M(y)子句〔6〕～(x)I(x)(x)(y)[M(y)～S(x,y)](x)I(x)∨(x)(y)[~M(y)∨～S(x,y)]否認(rèn)：～{(x)I(x)∨(x)(y)[~∨～S(x,y)]}(x)I(x)∧(x)(y)[M(y)∧S(x,y)]1/6/202431安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院反演求解過程從反演樹求取答案步驟把由目的公式的否認(rèn)產(chǎn)生的每個子句添加到目的公式否認(rèn)之否認(rèn)的子句中去。按照反演樹，執(zhí)行和以前一樣的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。本質(zhì)把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。1/6/202432安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院運用消解反演求解如下問題：無論約翰(John)到哪里去，菲多(Fido)也就去那里，那么假設(shè)約翰在學(xué)校里，菲多在哪里呢?x在y:AT(x,y)用謂詞公式表示前提和結(jié)論：前提：(x)[AT(JOHN,x)AT(FIDO,x)]AT(JOHN,SCHOOL)結(jié)論：(x)AT(FIDO,x)結(jié)論的否認(rèn)：~AT(FIDO,x)1/6/202433安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院化為子句集：~AT(JOHN,x)∨AT(FIDO,x)AT(JOHN,SCHOOL)~AT(FIDO,x)~AT(JOHN,y)∨AT(FIDO,y)~AT(FIDO,x)~AT(JOHN,x){x/y}AT(JOHN,SCHOOL)NIL{SCHOOL/x}~AT(JOHN,y)∨AT(FIDO,y)~AT(FIDO,x)∨AT(FIDO,x)~AT(JOHN,x)∨AT(FIDO,x){x/y}AT(JOHN,SCHOOL)AT(FIDO,SCHOOL){SCHOOL/x}1/6/202434安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.5含形狀項的回答語句的求取猴子和香蕉問題1/6/202435安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.5含形狀項的回答語句的求取{~ONBOX(S0)，AT(box,b,S0)，AT(monkey,a,S0)，~HB(S0)}pushbox(x,S)：在形狀S下，猴子把箱子推到程度位置xclimbbox(S)：在形狀S下，猴子爬上箱頂grasp(S)：在形狀S下，猴子摘到香蕉1/6/202436安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.5含形狀項的回答語句的求取(x)(S){~ONBOX(S)AT(box,x,pushbox(x,S))}(S){ONBOX(climbbox(S))}(S){ONBOX(S)∧AT(box,c,S)HB(grasp(S))}(x)(S){AT(box,x,S)AT(box,x,climbbox(S))}~ONBOX(S0)(S)HB(S)要證的結(jié)論1/6/202437安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.5含形狀項的回答語句的求取ONBOX(S)∨AT(box,x,pushbox(x,S))ONBOX(climbbox(S))~ONBOX(S)∨~AT(box,c,S)∨HB(grasp(S))~AT(box,x,S)∨AT(box,x,climbbox(S))~ONBOX(S0)目的的非：~HB(S)1/6/202438安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.5.5含形狀項的回答語句的求取ONBOX(S1)∨AT(box,x,pushbox(x,S1))ONBOX(climbbox(S2))~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3))~AT(box,x,S4)∨AT(box,x,climbbox(S4))~ONBOX(S0)目的的非：~HB(S5)1/6/202439安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院~HB(S5)~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3))~ONBOX(S3)∨~AT(box,c,S3){grasp(S3)/S5}ONBOX(climbbox(S2)){climbbox(S2)/S3}~AT(box,c,climbbox(S2))~AT(box,x,S4)∨AT(box,x,climbbox(S4)){S4/S2,c/x}~ONBOX(S0)~AT(box,c,S4)ONBOX(S1)∨AT(box,x,pushbox(x,S1)){pushbox(x,S1)/S4,c/x}ONBOX(S1){S0/S1}NIL1/6/202440安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院~HB(S5)∨HB(S5)~ONBOX(S3)∨~AT(box,c,S3)∨HB(grasp(S3))HB(grasp(S3))∨~ONBOX(S3)∨~AT(box,c,S3){grasp(S3)/S5}ONBOX(climbbox(S2)){climbbox(S2)/S3}HB(grasp(climbbox(S2)))∨~AT(box,c,climbbox(S2))~AT(box,x,S4)∨AT(box,x,climbbox(S4)){S4/S2,c/x}~ONBOX(S0)HB(grasp(climbbox(S4)))∨~AT(box,c,S4)ONBOX(S1)∨AT(box,x,pushbox(x,S1)){pushbox(x,S1)/S4,c/x}HB(grasp(climbbox(pushbox(c,S1))))∨ONBOX(S1){S0/S1}HB(grasp(climbbox(pushbox(c,S0))))1/6/202441安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗2子句消解實驗一、實驗?zāi)康模? 了解含有變量的子句如何運用消解規(guī)那么，掌握子句消解的原理和規(guī)那么，能熟練進展恣意兩個子句的消解，了解消解推理的某些常用規(guī)那么。

二、實驗原理： 對子句集進展消解推理，得到相應(yīng)的結(jié)論。為了對含有變量的子句運用消解規(guī)那么，我們必需找到一個置換，作用于父輩子句使其含有互補文字。消解兩個子句時，能夠有一個以上的消解式。三、實驗條件

硬件：微型計算機。 任選一種流行言語。1/6/202442安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗2子句消解實驗四、實驗內(nèi)容：

編寫消解程序。

輸入子句，檢查消解結(jié)果。

根據(jù)消解過程了解消解原理和常用規(guī)那么。

五、實驗步驟(2-3人一組)： 1.

語法分析程序，產(chǎn)生文字集合； 2.

兩個文字集合進展消解，結(jié)果為新的文字集合； 3.

用戶界面設(shè)計； 4.

分析消解過程，寫消解實驗報告?！裁咳恕?/6/202443安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.6規(guī)那么演繹系統(tǒng)定義基于規(guī)那么的問題求解系統(tǒng)運用If→Then規(guī)那么來建立，每個if能夠與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為任務(wù)內(nèi)存(黑板)，then部分用于規(guī)定放入任務(wù)內(nèi)存的新斷言。這種基于規(guī)那么的系統(tǒng)叫做規(guī)那么演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項。1/6/202444安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.6.1規(guī)那么正向演繹系統(tǒng)定義正向規(guī)那么演繹系統(tǒng)是從現(xiàn)實到目的進展操作的，即從情況條件到動作進展推理的，也就是從if到then的方向進展推理的。求解過程現(xiàn)實表達(dá)式的與或形變換在基于規(guī)那么的正向演繹系統(tǒng)中，我們把現(xiàn)實表示為非蘊涵方式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。1/6/202445安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院1.現(xiàn)實表達(dá)式的與或形變換例如：(u)(v){Q(v,u)∧~[(R(v)∨P(v))∧S(A,v)]}表示為非蘊涵方式的與或形：{A/u}Q(v,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}2.6.1規(guī)那么正向演繹系統(tǒng)1/6/202446安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.現(xiàn)實表達(dá)式的與或圖表示Q(v,A)∧{[~R(v)∧~P(v)]∨~S(A,v)}Q(v,A)[~R(v)∧~P(v)]∨~S(A,v)~R(v)∧~P(v)~S(A,v)~R(v)~P(v)圖2.8一個現(xiàn)實表達(dá)式的與或樹表示子句集：Q(v,A)~R(v)∨~S(A,v)~P(v)∨~S(A,v)換名：Q(w,A)~R(v)∨~S(A,v)~P(x)∨~S(A,x)1/6/202447安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院與或圖的F規(guī)那么變換這些規(guī)那么是建立在某個問題轄域中普通陳說性知識的蘊涵公式根底上的。我們把允許用作規(guī)那么的公式類型限制為以下方式： LW 式中：L是單文字；W為與或形的獨一公式。下面的證明限定：目的是可以證明的，目的是析取關(guān)系2.6.1規(guī)那么正向演繹系統(tǒng)1/6/202448安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院例如：(x){[(y)(z)P(x,y,z)](u)Q(x,u)}1)暫時消去蘊涵符號：(x){~[(y)(z)P(x,y,z)]∨(u)Q(x,u)}2)減小否認(rèn)符號的轄域：(x){[(y)(z)~P(x,y,z)]∨(u)Q(x,u)}3)進展Skolem規(guī)范化：(x){[(y)~P(x,y,f(x,y))]∨(u)Q(x,u)}4)換名并消去全稱量詞：~P(x,y,f(x,y))∨Q(x,u)5)恢復(fù)蘊涵式：P(x,y,f(x,y))Q(x,u)1/6/202449安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院[(P∨Q)∧R]∨[S∧(T∨U)]P∨Q(P∨Q)∧RT∨UPQRS∧(T∨U)STU圖2.9不含變量的與或圖1/6/202450安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院[(P∨Q)∧R]∨[S∧(T∨U)]P∨Q(P∨Q)∧RT∨UPQRS∧(T∨U)STU圖2.10運用LW規(guī)那么得到的與或圖SX∧YZXYP∨Q∨X∨ZP∨Q∨Y∨ZR∨X∨ZR∨Y∨Z1/6/202451安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院(A∨B)現(xiàn)實:A∨B規(guī)那么:AC∧D,BE∧G目的:C∨G(析取)CDCAABBEGG~A∨C~C~G~B∨GA∨B~A~B~BNIL結(jié)論：以目的節(jié)點作為終止解圖時，系統(tǒng)勝利終止。1/6/202452安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.6.2規(guī)那么逆向演繹系統(tǒng)定義逆向規(guī)那么演繹系統(tǒng)是從then向if進展推理的，即從目的或動作向現(xiàn)實或情況條件進展推理的。求解過程目的表達(dá)式的與或方式與或圖的B規(guī)那么變換,WL,L是單文字；W為與或形的公式作為終止條件的現(xiàn)實節(jié)點的一致解圖1/6/202453安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.6.2規(guī)那么逆向演繹系統(tǒng)例如：(y)(x){P(x)[Q(x,y)∧~[P(x)∧S(y)]]}化成與或形：~P(f(y))∨{Q(f(y),y)∧[~P(f(y))∨~S(y)]}~P(f(y))∨{Q(f(y),y)∧[~P(f(y))∨~S(y)]}{Q(f(y),y)∧[~P(f(y))∨~S(y)]}~P(f(y))[~P(f(y))∨~S(y)]Q(f(y),y)~S(y)~P(f(y))目的子句是文字的合?。簙P(f(z))Q(f(y),y)∧~P(f(y))Q(f(x),x)∧~S(x)1/6/202454安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院例： F1:DOG(FIDO)；狗的名字叫Fido F2:~BARKS(FIDO)；Fido不叫的 F3:WAGS-TAIL(FIDO)；Fido搖尾巴 F4:MEOWS(MYRTLE)；貓咪的名字叫Myrtle R1:[WAGS-TAIL(x1)∧DOG(x1)]FRIENDLY(x1)； 搖尾巴的狗是溫順的狗 R2:[FRIENDLY(x2)∧~BARKS(x2)]~AFRAID(y2,x2)； 溫順而不叫的東西是不值得害怕的 R3:DOG(x3)ANIMAL(x3)；狗是動物 R4:CAT(x4)ANIMAL(x4)；貓是動物 R5:MEOWS(x5)CAT(x5)；貓咪是貓問題：能否存在一只貓和一條狗，使得這只貓不怕這條狗〔找到一只不怕狗的貓〕？ (x)(y)[CAT(x)∧DOG(y)∧~AFRAID(x,y)]1/6/202455安徽大學(xué)計算機科學(xué)與技術(shù)學(xué)院CAT(x)∧DOG(y)∧~AFRAID(x,y)CAT(x)DOG(y)~AFRAID(x,y)WAGS-TAIL(FIDO)DOG(FIDO)DOG(y)~AFRAID(y2,x2)FRIENDLY(y)~AFRAID(x,y)WAGS-TAIL(y){FIDO/y}{FIDO/y}~BARKS(FIDO)MEOWS(MYRTLE){y/x1}{FIDO/y}{MYRTLE/x}R1DOG(FIDO){FIDO/y}~BARKS(y){x/y2,y/x2}R2MEOWS