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

第二章知識(shí)表示方法2.1狀態(tài)空間法2.2問(wèn)題歸約法2.3謂詞邏輯法2.4語(yǔ)義網(wǎng)絡(luò)法2.5其他方法2.6小結(jié)22.1狀態(tài)空間法

（StateSpaceRepresentation）問(wèn)題求解技術(shù)主要是兩個(gè)方面：?jiǎn)栴}的表示求解的方法狀態(tài)空間法狀態(tài)（state）算符（operator）狀態(tài)空間方法32.1.1

問(wèn)題狀態(tài)描述定義狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合。算符：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。問(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)空間法42.

狀態(tài)空間表示概念詳釋例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState2.1狀態(tài)空間法5例:三數(shù)碼難題

123123123312312312初始棋局目標(biāo)棋局2.1狀態(tài)空間法678例：十五數(shù)碼難題（15puzzleproblem）初始狀態(tài)目標(biāo)狀態(tài)9101112有向圖路徑代價(jià)圖的顯示說(shuō)明圖的隱示說(shuō)明2.1.2狀態(tài)圖示法AB2.1狀態(tài)空間法132.1.3狀態(tài)空間表示舉例產(chǎn)生式系統(tǒng)（productionsystem）一個(gè)總數(shù)據(jù)庫(kù)：它含有與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫(kù)可能簡(jiǎn)單，或許復(fù)雜。一套規(guī)則：它對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作運(yùn)算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時(shí)所完成的動(dòng)作。一個(gè)控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫(kù)的終止條件滿足時(shí)，就停止計(jì)算。2.1狀態(tài)空間法14

狀態(tài)空間表示舉例例：猴子和香蕉問(wèn)題2.1狀態(tài)空間法15解題過(guò)程1用四元表列（W,x,Y,z）來(lái)表示這個(gè)問(wèn)題的狀態(tài)其中，

W－猴子的水平位置

x－當(dāng)猴子在箱子頂上時(shí)取x=1；否則取x=0

Y－箱子的水平位置

z－當(dāng)猴子摘到香蕉時(shí)取z=1；否則取z=016解題過(guò)程2這個(gè)問(wèn)題的操作（算符）如下：2goto（U）表示猴子走到水平位置U或者用產(chǎn)生式規(guī)則表示為 （W，0，Y，z）goto（U）（U，0，Y，z）2.1狀態(tài)空間法17pushbox（V）猴子把箱子推到水平位置V，即有

（W，0，W，z）pushbox（V）（V，0，V，z）climbbox猴子爬上箱頂，即有

（W，0，W，z）climbbox（W，1，W，z）2.1狀態(tài)空間法18grasp猴子摘到香蕉，即有

（c，1，c，0）grasp（c，1，c，1）

該初始狀態(tài)變換為目標(biāo)狀態(tài)的操作序列為

{goto(b),pushbox(c),climbbox,grasp}2.1狀態(tài)空間法19(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)goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）猴子和香蕉問(wèn)題的狀態(tài)空間圖goto（U）U=V2.1狀態(tài)空間法202.2問(wèn)題歸約法

（ProblemReductionRepresentation）子問(wèn)題1子問(wèn)題n原始問(wèn)題子問(wèn)題集本原問(wèn)題21

問(wèn)題歸約表示的組成部分：一個(gè)初始問(wèn)題描述；一套把問(wèn)題變換為子問(wèn)題的操作符；一套本原問(wèn)題描述。問(wèn)題歸約的實(shí)質(zhì)：從目標(biāo)(要解決的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。2.2問(wèn)題規(guī)約法222.2.1問(wèn)題歸約描述

（ProblemReductionDescription）梵塔難題123CBA2.2問(wèn)題規(guī)約法23梵塔難題2.2.1問(wèn)題歸約描述(a)初始狀態(tài)(b)目標(biāo)狀態(tài)24問(wèn)題規(guī)約原始問(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盤至柱子3的雙圓盤難題25歸約過(guò)程26解題過(guò)程（3個(gè)圓盤問(wèn)題）1231231231231231231231232.2問(wèn)題規(guī)約法27梵塔問(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ī)約法28多圓盤梵塔難題演示2.2問(wèn)題規(guī)約法292.2.2與或圖表示1.與圖、或圖、與或圖2.2問(wèn)題規(guī)約法ABCD與圖ABC或圖302.2問(wèn)題規(guī)約法BCDEFGAHMBCDEFGAN312.一些關(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)：只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（M，N，H）。

與節(jié)點(diǎn)：只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的節(jié)點(diǎn)集合，如（B,C)和（D,E,F）各個(gè)結(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記323.定義2.2問(wèn)題規(guī)約法與或圖例子ttttttttt（a）（b）有解節(jié)點(diǎn)無(wú)解節(jié)點(diǎn)終葉節(jié)點(diǎn)33不可解節(jié)點(diǎn)的一般定義沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。全部后裔為不可解的非終葉節(jié)點(diǎn)且含有或后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。后裔至少有一個(gè)為不可解的非終葉節(jié)點(diǎn)且含有與后繼節(jié)點(diǎn)，此非終葉節(jié)點(diǎn)才是不可解的。與或圖構(gòu)成規(guī)則2.2問(wèn)題規(guī)約法34梵塔問(wèn)題歸約圖（與或圖）352.3謂詞邏輯法邏輯語(yǔ)句形式語(yǔ)言2.3.1謂詞演算

1.語(yǔ)法和語(yǔ)義基本符號(hào)謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)、常量符號(hào)、括號(hào)和逗號(hào)原子公式362.3謂詞邏輯法1原子公式(atomicformulas)由若干謂詞符號(hào)和項(xiàng)組成的謂詞演算。原子公式是謂詞演算基本積木塊。

機(jī)器人(ROBOT)在１號(hào)房間(r1)內(nèi)的原子公式：

372.3謂詞邏輯法2“李的母親和他的父親結(jié)婚”這句話的原子公式表示如下：

38連詞和量詞(Connective&Quantifiers)連詞與及合?。╟onjunction)或及析?。╠isjunction）蘊(yùn)涵（Implication）非（Not）量詞全稱量詞（UniversalQuantifiers)存在量詞

(ExistentialQuantifiers)2.3謂詞邏輯法392.3謂詞邏輯法連詞

與·合?。╟onjunction）:合取就是用連詞∧把幾個(gè)公式連接起來(lái)而構(gòu)成的公式。(我喜愛(ài)音樂(lè)和繪畫。)LIKE(I，MUSIC)∧LIKE(I，PAINTING)

(我喜愛(ài)音樂(lè)和繪畫。)

40或·析?。╠isjunction）:析取就是用連詞∨把幾個(gè)公式連接起來(lái)而構(gòu)成的公式。

PLAYS(LILI，BASKETBALL)∨PLAYS(LILI，F(xiàn)OOTBALL)(李力打籃球或踢足球。)(李力打籃球或踢足球。)

41蘊(yùn)涵"=>"表示"如果-那么"的語(yǔ)句RUNS(LIUHUA，F(xiàn)ASTEST)WINS(LIUHUA，CHAMPION)

(如果劉華跑得最快，那么他取得冠軍)

42非（NOT）表示否定，～、┑均可表示。

～I(xiàn)NROOM(ROBOT，r2)

(機(jī)器人不在2號(hào)房間內(nèi)。)

43(2)量詞

全稱量詞(UniversalQuantifier)若一個(gè)原子公式P(x)，對(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é)生都穿彩色制服)

44存在量詞(ExistentialQuantifier)

若一個(gè)原子公式P(x)，至少有一個(gè)變?cè)猉，可使P(X)為T值，則用(

x)P(x)表示。(

x)INROOM(x,r1)(1號(hào)房間內(nèi)有個(gè)物體)

452.3.2謂詞公式原子公式的的定義：用P(x1，x2，…，xn)表示一個(gè)n元謂詞公式，其中P為n元謂詞，x1,x2,…，xn為客體變量或變?cè)?。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。2.3謂詞邏輯法46合適公式（WFF，well-formedformulas）合適公式的遞歸定義合適公式的性質(zhì)合適公式的真值等價(jià)（Equivalence)2.3謂詞邏輯法47合適公式的真值：

482.3.3置換與合一置換概念假元推理全稱化推理綜合推理定義就是在該表達(dá)式中用置換項(xiàng)置換變量性質(zhì)可結(jié)合的不可交換的2.3謂詞邏輯法49一個(gè)重要的推理規(guī)則是假元推理，這就是由合適公式W1和W1=>W2產(chǎn)生合適公式W2的運(yùn)算。另一個(gè)推理規(guī)則叫做全稱化推理，它是由合適公式(

x)W(x)產(chǎn)生合適公式W(A)，其中A為任意常量符號(hào)。

50s1={z/x,w/y}

s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}P[x,f(y),B]s1=P[z,f(w),B]P[x,f(y),B]s2=P[x,f(A),B]

P[x,f(y),B]s3=P[q(z),f(A),B]

P[x,f(y),B]s4=P[c,f(A),B]2)

51合一（Unification)合一：尋找項(xiàng)對(duì)變量的置換，以使兩表達(dá)式一致?？珊弦唬喝绻粋€(gè)置換s作用于表達(dá)式集{Ei}的每個(gè)元素，則我們用{Ei}s來(lái)表示置換例的集。我們稱表達(dá)式集{Ei}是可合一的。2.3謂詞邏輯法52P[x,f(y),B],P[x,f(B),B]的合一式為S={A/x,B/y}最簡(jiǎn)單合一：g={B/y}532.4語(yǔ)義網(wǎng)絡(luò)法

（SemanticNetworkRepresentation）語(yǔ)義網(wǎng)絡(luò)的結(jié)構(gòu)定義組成部分詞法結(jié)構(gòu)過(guò)程語(yǔ)義54表示占有關(guān)系和其它情況例：小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個(gè)。選擇語(yǔ)義基元試圖用一組基元來(lái)表示知識(shí)，以便簡(jiǎn)化表示，并可用簡(jiǎn)單的知識(shí)來(lái)表示更復(fù)雜的知識(shí)。2.4語(yǔ)義網(wǎng)絡(luò)法2.4.1二元語(yǔ)義網(wǎng)絡(luò)的表示552.4.1二元語(yǔ)義網(wǎng)絡(luò)的表示網(wǎng)絡(luò)表示562.4.2多元語(yǔ)義網(wǎng)絡(luò)的表示謂詞邏輯與語(yǔ)義網(wǎng)絡(luò)等效LIMINGMANISAISA（LIMING，MAN）或MAN（LIMING）（語(yǔ)義網(wǎng)絡(luò)）（謂詞邏輯）2.4語(yǔ)義網(wǎng)絡(luò)法57多元語(yǔ)義網(wǎng)絡(luò)表示的實(shí)質(zhì)把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。R(X1，X2，…，Xn)R12(X1，X2)∧R13(X1，X3)∧…∧R1n(X1，Xn)......Rn-1n(Xn-1，Xn)可轉(zhuǎn)換為2.4語(yǔ)義網(wǎng)絡(luò)法582.4.3連接詞和量化的表示合取三元變?yōu)槎M合析取加注析取界限，并標(biāo)記DIS，以免引起混淆。否定兩種表示方式：～或標(biāo)注NEG界限。2.4語(yǔ)義網(wǎng)絡(luò)法59蘊(yùn)涵在語(yǔ)義網(wǎng)絡(luò)中可用標(biāo)注ANTE和CONSE界限來(lái)表示蘊(yùn)涵關(guān)系。ANTE和CONSE界限分別用來(lái)把與先決條件(antec