第二章知識(shí)表示方法

1、第二章 知識(shí)表示方法2.1 狀態(tài)空間法2.2 問(wèn)題歸約法2.3 謂詞邏輯法2.4 語(yǔ)義網(wǎng)絡(luò)法2.5 其他方法2.6 小結(jié)CSUCSUCSUCSUCSUCSUCSUCSUCSU22.1狀態(tài)空間法（State Space Representation）v問(wèn)題求解技術(shù)主要是兩個(gè)方面：v問(wèn)題的表示v求解的方法v狀態(tài)空間法v狀態(tài)（state）v算符（operator）v狀態(tài)空間方法CSUCSUCSUCSUCSUCSUCSUCSUCSU32.1.1 問(wèn)題狀態(tài)描述v定義v狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。v算符：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算

2、符。v問(wèn)題的狀態(tài)空間：是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說(shuō)明的集合，即三元狀態(tài)（S，F(xiàn)，G）。其中所有可能的問(wèn)題初始狀態(tài)集合S、操作符集合F以及目標(biāo)狀態(tài)集合G。2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU42. 狀態(tài)空間表示概念詳釋v例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU5例:三數(shù)碼難題123123123312312312初始棋局目標(biāo)棋局2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU6CSUCSUC

3、SUCSUCSUCSUCSUCSUCSU7CSUCSUCSUCSUCSUCSUCSUCSUCSU8例：例：十五數(shù)碼難題v（15 puzzle problem）119415131275861321014123456789101112131415初始狀態(tài)初始狀態(tài)目標(biāo)狀態(tài)目標(biāo)狀態(tài)CSUCSUCSUCSUCSUCSUCSUCSUCSU9CSUCSUCSUCSUCSUCSUCSUCSUCSU10CSUCSUCSUCSUCSUCSUCSUCSUCSU11CSUCSUCSUCSUCSUCSUCSUCSUCSU12v有向圖v路徑v代價(jià)v圖的顯示說(shuō)明v圖的隱示說(shuō)明2.1.2 狀態(tài)圖示法AB2.1 狀態(tài)空間法CS

4、UCSUCSUCSUCSUCSUCSUCSUCSU132.1.3 狀態(tài)空間表示舉例v產(chǎn)生式系統(tǒng)（production system）v一個(gè)總數(shù)據(jù)庫(kù)：它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫(kù)可能簡(jiǎn)單，或許復(fù)雜。v一套規(guī)則：它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。v一個(gè)控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算。2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU14 狀態(tài)空間表示舉例狀態(tài)空間表示舉例v例：猴子和香蕉問(wèn)題2.1 狀態(tài)空間法CSUCSUCSUCSUCS

5、UCSUCSUCSUCSU15解題過(guò)程1v用四元 表列（W,x,Y,z）來(lái)表示這個(gè)問(wèn)題的狀態(tài)v其中，vW猴子的水平位置vx當(dāng)猴子在箱子頂上時(shí)取x=1；否則取x=0vY箱子的水平位置vz當(dāng)猴子摘到香蕉時(shí)取z=1；否則取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSU16解題過(guò)程2v這個(gè)問(wèn)題的操作（算符）如下：v2 goto（U）表示猴子走到水平位置Uv或者用產(chǎn)生式規(guī)則表示為（W，0，Y，z） goto（U） （U，0，Y，z）2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU17vpushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbo

6、x（V） （V，0，V，z）vclimbbox猴子爬上箱頂，即有（W，0，W，z） climbbox （W，1，W，z）2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU18vgrasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1） v該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為goto(b),pushbox(c),climbbox,grasp2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU19(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目標(biāo)狀態(tài)目標(biāo)狀態(tài)

7、goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉問(wèn)題的狀態(tài)空間圖猴子和香蕉問(wèn)題的狀態(tài)空間圖goto（U）U=V2.1 狀態(tài)空間法CSUCSUCSUCSUCSUCSUCSUCSUCSU202.2 問(wèn)題歸約法（Problem Reduction Representation）子問(wèn)題子問(wèn)題1子問(wèn)題子問(wèn)題n原始問(wèn)題原始問(wèn)題子問(wèn)題集本本原原問(wèn)問(wèn)題題CSUCSUCSUCSUCSUCSUCSUCSUCSU21v 問(wèn)題歸約表示的組成部分：v一個(gè)初始問(wèn)題描述；v一套把問(wèn)題變換為子問(wèn)題的操作符；v一套本原問(wèn)題描述。v問(wèn)題歸約的實(shí)質(zhì)：v從目標(biāo)(要解決的問(wèn)題)出發(fā)

8、逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。2.2 問(wèn)題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSU222.2.1 問(wèn)題歸約描述 （Problem Reduction Description）v梵塔難題123CBA2.2 問(wèn)題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSU23v梵塔難題2.2.1 問(wèn)題歸約描述(a) 初始狀態(tài)(b) 目標(biāo)狀態(tài)CSUCSUCSUCSUCSUCSUCSUCSUCSU24問(wèn)題規(guī)約v原始問(wèn)題歸約（簡(jiǎn)化）為三個(gè)子問(wèn)題1、移動(dòng)A，B盤至柱子2的雙圓盤難題2、移動(dòng)圓盤C至柱子3的單圓盤問(wèn)題3、移動(dòng)A，B

9、盤至柱子3的雙圓盤難題CSUCSUCSUCSUCSUCSUCSUCSUCSU25v歸約過(guò)程CSUCSUCSUCSUCSUCSUCSUCSUCSU26解題過(guò)程（3個(gè)圓盤問(wèn)題）1231231231231231231231232.2 問(wèn)題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSU27梵塔問(wèn)題歸約圖（113） （123） （111） （113） （123） （122） （111） （333） （122） （322） （111） （122） （322） （333） （321） （331） （322） （321） （331） （333） 2.2 問(wèn)題規(guī)約法CSUCSUCSUCSUCSUC

10、SUCSUCSUCSU28多圓盤梵塔難題演示2.2 問(wèn)題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSU292.2.2與或圖表示v1.與圖、或圖、與或圖2.2 問(wèn)題規(guī)約法ABCD與圖ABC或圖CSUCSUCSUCSUCSUCSUCSUCSUCSU302.2 問(wèn)題規(guī)約法BCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSU312.一些關(guān)于與或圖的術(shù)語(yǔ)2.2 問(wèn)題規(guī)約法HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn)弧線或節(jié)點(diǎn)子節(jié)點(diǎn)終葉節(jié)點(diǎn) 終葉節(jié)點(diǎn)：對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)。終葉節(jié)點(diǎn)：對(duì)應(yīng)于原問(wèn)題的本原節(jié)點(diǎn)?；蚬?jié)點(diǎn)：只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（或

11、節(jié)點(diǎn)：只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（M，N，H）。）。與節(jié)點(diǎn)：只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（與節(jié)點(diǎn)：只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（B,C)和和 （D,E,F）各個(gè)結(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記）各個(gè)結(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記 CSUCSUCSUCSUCSUCSUCSUCSUCSU323.定義2.2 問(wèn)題規(guī)約法與或圖例子與或圖例子ttttttttt（a）（b）有解節(jié)點(diǎn)無(wú)解節(jié)點(diǎn)終葉節(jié)點(diǎn)CSUCSUCSUCSUCSUCSUCSUCSUCSU33v不可解節(jié)點(diǎn)的一般定義v沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。v全部后裔為不可解的非終葉節(jié)點(diǎn)且

12、含有或后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。v后裔至少有一個(gè)為不可解的非終葉節(jié)點(diǎn)且含有與后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。v與或圖構(gòu)成規(guī)則2.2 問(wèn)題規(guī)約法CSUCSUCSUCSUCSUCSUCSUCSUCSU34v梵塔問(wèn)題歸約圖（與或圖與或圖）CSUCSUCSUCSUCSUCSUCSUCSUCSU352.3 謂詞邏輯法v邏輯語(yǔ)句v形式語(yǔ)言2.3.1 謂詞演算v 1. 語(yǔ)法和語(yǔ)義v基本符號(hào)v謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)、 常量符號(hào)、括號(hào)和逗號(hào)v原子公式CSUCSUCSUCSUCSUCSUCSUCSUCSU362.3 謂詞邏輯法1原子公式(atomic formulas)由若干謂詞符號(hào)和項(xiàng)組成的

13、謂詞演算。原子公式是謂詞演算基本積木塊。機(jī)器人(ROBOT)在號(hào)房間(r1)內(nèi)的原子公式： CSUCSUCSUCSUCSUCSUCSUCSUCSU372.3 謂詞邏輯法2“李的母親和他的父親結(jié)婚”這句話的原子公式表示如下： CSUCSUCSUCSUCSUCSUCSUCSUCSU38v連詞和量詞(Connective &Quantifiers)v連詞v與及合?。╟onjunction)v或及析?。╠isjunction）v蘊(yùn)涵（Implication）v非（Not）v量詞v全稱量詞（Universal Quantifiers)v存在量詞 (Existential Quantifiers)2.3

14、謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSU392.3 謂詞邏輯法連詞連詞與與合取（合?。╟onjunctionconjunction）: :合取就是用連詞合取就是用連詞把幾個(gè)把幾個(gè) 公式連接起來(lái)而構(gòu)成的公式。公式連接起來(lái)而構(gòu)成的公式。(我喜愛音樂(lè)和繪畫。)LIKE(I，MUSIC)LIKE(I，PAINTING) (我喜愛音樂(lè)和繪畫。) CSUCSUCSUCSUCSUCSUCSUCSUCSU40或析?。╠isjunction）:析取就是用連詞把幾個(gè)公式 連接起來(lái)而構(gòu)成的公式。 PLAYS(LILI，BASKETBALL)PLAYS(LILI，F(xiàn)OOTBALL)(李力打籃球

15、或踢足球。)(李力打籃球或踢足球。) CSUCSUCSUCSUCSUCSUCSUCSUCSU41蘊(yùn)涵蘊(yùn)涵=表示表示如果如果-那么那么的語(yǔ)句的語(yǔ)句 RUNS(LIUHUA，F(xiàn)ASTEST) WINS(LIUHUA，CHAMPION) (如果劉華跑得最快，那么他取得冠軍) CSUCSUCSUCSUCSUCSUCSUCSUCSU42非（非（NOT） 表示否定，表示否定，、均可表示。INROOM(ROBOT，r2) (機(jī)器人不在2號(hào)房間內(nèi)。) CSUCSUCSUCSUCSUCSUCSUCSUCSU43(2) 量詞量詞 全稱量詞全稱量詞(Universal Quantifier)若一個(gè)原子公式若一個(gè)原子

16、公式P(x)，對(duì)于所有可能變量對(duì)于所有可能變量x都具有都具有T值，則用值，則用( x)P(x)表示。(所有的機(jī)器人都是灰色的）( x)Student(x) = Uniform(x,Color) (所有學(xué)生都穿彩色制服)( x)ROBOT(x) = COLOR(x,GRAY) (所有的機(jī)器人都是灰色的） ( x)Student(x) = Uniform(x,Color) (所有學(xué)生都穿彩色制服) CSUCSUCSUCSUCSUCSUCSUCSUCSU44存在量詞存在量詞(Existential Quantifier)若一個(gè)原子公式P(x)，至少有一個(gè)變?cè)猉，可使P(X)為T值，則用( x)P(x

17、)表示。 ( x)INROOM(x,r1) (1號(hào)房間內(nèi)有個(gè)物體) CSUCSUCSUCSUCSUCSUCSUCSUCSU452.3.2 謂詞公式v原子公式的的定義：v用P(x1，x2，xn)表示一個(gè)n元謂詞公式，其中P為n元謂詞，x1,x2,，xn為客體變量或變?cè)?。通常把P(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。v分子謂詞公式v可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSU46v合適公式（WFF，well-formed formulas）v合適公式的遞歸定義v合適公式的性質(zhì)v合適公

18、式的真值v等價(jià)（Equivalence)2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSU47合適公式的真值：CSUCSUCSUCSUCSUCSUCSUCSUCSU482.3.3 置換與合一v置換v概念v假元推理v全稱化推理v綜合推理v定義v就是在該表達(dá)式中用置換項(xiàng)置換變量v性質(zhì)v可結(jié)合的v不可交換的2.3 謂詞邏輯法CSUCSUCSUCSUCSUCSUCSUCSUCSU49一個(gè)重要的推理規(guī)則是假元推理，這就是由合適公式W1和W1=W2產(chǎn)生合適公式W2的運(yùn)算。另一個(gè)推理規(guī)則叫做全稱化推理，它是由合適公式( x)W(x)產(chǎn)生合適公式W(A)，其中A為任意常量符號(hào)。CSUCS

19、UCSUCSUCSUCSUCSUCSUCSU50s1=z/x,w/y s2=A/y s3=q(z)/x,A/y s4=c/x,A/y Px,f(y),Bs1=Pz,f(w),BPx,f(y),Bs2=Px,f(A),B Px,f(y),Bs3=Pq(z),f(A),B Px,f(y),Bs4=Pc,f(A),B2) CSUCSUCSUCSUCSUCSUCSUCSUCSU51v合一（Unification)v合一：尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致。v可合一：如果一個(gè)置換s作用于表達(dá)式集Ei的每個(gè)元素，則我們用Ei s來(lái)表示置換例的集。我們稱表達(dá)式集Ei是可合一的。2.3 謂詞邏輯法CSUCS

20、UCSUCSUCSUCSUCSUCSUCSU52Px,f(y),B, Px,f(B),B 的合一式為S=A/x, B/y最簡(jiǎn)單合一：g=B/yCSUCSUCSUCSUCSUCSUCSUCSUCSU532.4 語(yǔ)義網(wǎng)絡(luò)法 （Semantic Network Representation）v語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu)v定義v組成部分v詞法v結(jié)構(gòu)v過(guò)程v語(yǔ)義CSUCSUCSUCSUCSUCSUCSUCSUCSU54v表示占有關(guān)系和其它情況v例： 小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個(gè)。v選擇語(yǔ)義基元v試圖用一組基元來(lái)表示知識(shí)，以便簡(jiǎn)化表示，并可用簡(jiǎn)單的知識(shí)來(lái)表示更復(fù)雜的知識(shí)。2.4 語(yǔ)義

21、網(wǎng)絡(luò)法2.4. 1 二元語(yǔ)義網(wǎng)絡(luò)的表示CSUCSUCSUCSUCSUCSUCSUCSUCSU552.4.1 二元語(yǔ)義網(wǎng)絡(luò)的表示ComputerMicro-ComputerHard DiscMornitorCPURAMPC/XTMy-ComputerMePersonIS-PART-OFIS-PART-OFIS-PART-OFIS-PART-OFISAISAISAOWNERISA網(wǎng)絡(luò)表示網(wǎng)絡(luò)表示CSUCSUCSUCSUCSUCSUCSUCSUCSU562.4.2 多元語(yǔ)義網(wǎng)絡(luò)的表示v謂詞邏輯與語(yǔ)義網(wǎng)絡(luò)等效LIMINGMANISAISA（LIMING，MAN）或）或 MAN（LIMING）（語(yǔ)義網(wǎng)絡(luò)

22、）（語(yǔ)義網(wǎng)絡(luò)）（謂詞邏輯）（謂詞邏輯）2.4 語(yǔ)義網(wǎng)絡(luò)法CSUCSUCSUCSUCSUCSUCSUCSUCSU57v多元語(yǔ)義網(wǎng)絡(luò)表示的實(shí)質(zhì)v把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。R(XR(X1 1，X X2 2，X Xn n) )R R1212(X(X1 1，X X2 2)R)R1313(X(X1 1，X X3 3) R R1n1n(X(X1 1，X Xn n) ). R Rn-1 nn-1 n(X(Xn-1n-1，X Xn n) )可轉(zhuǎn)換為可轉(zhuǎn)換為2.4 語(yǔ)義網(wǎng)絡(luò)法CSUCSUCSUCSUCSUCSUCSUCSUCSU582.4.3 連接詞和量化的表示v合取v三元變?yōu)槎M合v析取v加注析取界限，并標(biāo)記DIS，以免引起混淆。v否定v兩種表示方式：或標(biāo)注NEG界限。2.4 語(yǔ)義網(wǎng)絡(luò)法CSUCSUCSUCSUCSUCSUCSUCSUCSU59v蘊(yùn)涵v在語(yǔ)義網(wǎng)絡(luò)中可用標(biāo)注ANTE和CONSE界限來(lái)表示蘊(yùn)涵關(guān)系。ANTE和CONSE界限分別用來(lái)把與先決條件(antecedent)及與結(jié)果(consequence)相關(guān)的鏈聯(lián)系在一起。v量化v存在量化ISA鏈