知識(shí)表示方法

1、第二章知識(shí)表示方法教學(xué)內(nèi)容(狀態(tài)空間法.問題歸約法.謂詞邏輯智能系統(tǒng)問題求解所采用的幾種主要的知識(shí)表示方法 法.語義網(wǎng)絡(luò)法)以及基于不同表示法的問題求解方法.教學(xué)重點(diǎn)1 .狀態(tài)空間表示法中問題的狀態(tài)描述.改變狀態(tài)的操作和問題目標(biāo)狀態(tài)的搜索；2 .問題規(guī)約的一般步驟.規(guī)約的與或圖表示；3 .謂詞邏輯的語法和語義.量詞的轄域.謂詞公式的置換與合一；4 .語義網(wǎng)絡(luò)的構(gòu)成.語義基元的選擇.語義網(wǎng)絡(luò)的推理等.教學(xué)難點(diǎn)狀態(tài)描述與狀態(tài)空間圖示.問題歸約機(jī)制.置換與合一.教學(xué)方法課堂教學(xué)為主,同時(shí)結(jié)合?離散數(shù)學(xué)?等已學(xué)的內(nèi)容實(shí)時(shí)提問.收集學(xué)生學(xué)習(xí)情況,充分利用網(wǎng)絡(luò)課程中的多媒體素材來表示抽象概念.教學(xué)要求1

2、.重點(diǎn)掌握用狀態(tài)空間法.問題歸約法.謂詞邏輯法.語義網(wǎng)絡(luò)法來描述問題.解決問題；2 .掌握這些表示方法之間的差異；并對(duì)其它表示方法有一般了解2.1 狀態(tài)空間法教學(xué)內(nèi)容本節(jié)討論基于解答空間的問題表示和求解方法,即狀態(tài)空間法,它以狀態(tài)和操作符為根底來表示和求解問題.教學(xué)重點(diǎn)問題的狀態(tài)描述,操作符.教學(xué)難點(diǎn)選擇一個(gè)好的狀態(tài)描述與狀態(tài)空間表示方案.教學(xué)方法以課堂教學(xué)為主；充分利用網(wǎng)絡(luò)課程中的多媒體素材來闡述抽象概念.教學(xué)要求重點(diǎn)掌握對(duì)某個(gè)問題的狀態(tài)空間描述,學(xué)會(huì)組織狀態(tài)空間圖.用搜索圖來求解問題.2.1.1 問題狀態(tài)描述1 .根本概念狀態(tài)(state)它是為描述某類不同事物間的差異而引入的一組最少變量

3、q0,q1,q的有序集合,其矢量形式如下：Q=q0,q1,qn (2.1)式中每個(gè)元素qi(i=0,1,n)集合的分量,稱為狀態(tài)變量.給定每個(gè)分量的一組值就得到一個(gè) 具體的狀態(tài),如Qk=q 0 k,q1k,qnk (2.2)操作符(operator)稱使問題從一種狀態(tài)變化到另一種狀態(tài)的手段為操作符或算符.狀態(tài)空間(state space)它是表示一個(gè)問題全部可能狀態(tài)及其關(guān)系的圖,它包含所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標(biāo)狀態(tài)集合 Go因此,狀態(tài)空間記為三元狀態(tài)(S,F,G).提問1.列舉已經(jīng)學(xué)習(xí)過的狀態(tài)概念,并比擬之.2 .列舉操作符.3 .狀態(tài)空間描述要完成一個(gè)問題的狀態(tài)描述,

4、必須確定3件事：(1)狀態(tài)描述方式,特別是初始狀態(tài)描述；(2)操作符集合及其對(duì)?態(tài)描述的作用 ；(3)目標(biāo)狀態(tài)描述的特性.舉例列舉幾個(gè)日常生活中狀態(tài)與操作符的例子,如:棋局.講解初始狀態(tài)、操作符、中間狀態(tài)與目標(biāo)狀態(tài)之間的關(guān)系；講解三數(shù)碼難題的狀態(tài)變化過程.討論 每走一步后,棋局都變化了,以此來理解問題的狀態(tài)空間.4 .1.2狀態(tài)圖示法圖的根本概念圖是一個(gè)包含節(jié)點(diǎn)(不一定是有限的節(jié)點(diǎn))和節(jié)點(diǎn)間弧線的集合.假設(shè)圖中每條弧線均標(biāo)有方 向,那么稱這種圖為有向圖 (directed graph).代價(jià)(cost)是給各弧線指定數(shù)值以表示加在相應(yīng)操作符上的代價(jià).圖的顯式說明是指各節(jié)點(diǎn)及其具有代價(jià)的弧線由一

5、張說明確給出.圖的隱式說明：是指各節(jié)點(diǎn)及其具有代價(jià)的弧線不能由一張說明確給出.提問舉已經(jīng)學(xué)習(xí)過的有向圖、路徑及代價(jià)等的概念.舉例針對(duì)三數(shù)碼難題的狀態(tài)變化過程講解圖的幾個(gè)根本概念2.2問題規(guī)約法教學(xué)內(nèi)容知識(shí)表示的歸約法,即問題的描述,通過一系列變換把此問題最終變?yōu)橐粋€(gè)子 問題集合；這些子問題的解可以直接得到,從而解決了初始問題的方法.教學(xué)重點(diǎn) 問題歸約的根本思想,問題描述,問題變換的操作符,與或圖表示.教學(xué)難點(diǎn) 如何把初始問題變換為子問題 ,與或圖表示方法.教學(xué)方法課堂教學(xué)為主,充分利用網(wǎng)絡(luò)課程中的相關(guān)多媒體素材來表示抽象概念.教學(xué)要求通過梵塔難題重點(diǎn)掌握問題歸約法的機(jī)理和問題歸約描述方法.學(xué)會(huì)

6、用與或圖表示歸約問題.2.2.1 問題歸約描述1 .問題歸約法的概念問題歸約是將初始問題變?yōu)橐粋€(gè)本原問題集合.2 .問題歸約法的組成局部(1) 一個(gè)初始問題描述；(2) 一套把問題變換為子問題的操作符；(3) 一套本原問題描述.3 .例如：梵塔難題問題有3個(gè)柱子(1,2,3)和3個(gè)不同尺寸的圓盤(A,B,C).在每個(gè)圓盤的中央有個(gè)孔,所以圓盤可以堆疊在柱子上.最初,全部3個(gè)圓盤都堆在柱子 1上:最大的圓盤 C在底部,最小的圓盤A 在頂部.要求把所有圓盤都移到柱子3上,每次只許移動(dòng)一個(gè),而且只能先搬動(dòng)柱子頂部的圓盤,還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上.歸約過程(1)移動(dòng)圓盤A和B至柱子

7、2的雙圓盤難題；(2)移動(dòng)圓盤C至柱子3的單圓盤難題；(3)移動(dòng)圓盤A和B至柱子3的雙圓盤難題.講述梵塔問題的來源.提問一圓盤問題要走幾步 ？?jī)蓤A盤問題要走幾步？三個(gè).四個(gè).等？2.2.2與或圖1 .與或圖的概念用一個(gè)類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合,畫出歸約問題圖.2 .與或圖的有關(guān)術(shù)語父節(jié)點(diǎn)是一個(gè)初始問題或是可分解為子問題的問題節(jié)點(diǎn)；子節(jié)點(diǎn)是一個(gè)初始問題或是子問題分解的子問題節(jié)點(diǎn)；或節(jié)點(diǎn)只要解決某個(gè)問題就可解決其父輩問題的節(jié)點(diǎn)集合；與節(jié)點(diǎn)只有解決所有子問題,才能解決其父輩問題的節(jié)點(diǎn)集合；終葉節(jié)點(diǎn)是對(duì)應(yīng)于原問題的本原節(jié)點(diǎn).提問 對(duì)于一個(gè)與或圖,指出圖中的父節(jié)點(diǎn)、子節(jié)點(diǎn)、或節(jié)點(diǎn)

8、、與節(jié)點(diǎn)、弧線和終葉節(jié)點(diǎn).可解節(jié)點(diǎn)與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納如下：(1)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(由于它們與本原問題相關(guān)連 ).(2)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn) 此非終葉節(jié)點(diǎn)才是可解的.(3)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn) 節(jié)點(diǎn)才是可解的.不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)的一般定義歸納于下：(1)沒有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn).(2)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn) 點(diǎn)才是不可解的.(3)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn) 終葉節(jié)點(diǎn)才是不可解的.提問 對(duì)于一個(gè)與或圖,指出圖中的終葉節(jié)點(diǎn)、,那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí),那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí),此非終葉,那么只有當(dāng)其全部后

9、裔為不可解時(shí),此非終葉節(jié),那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí),此非可解節(jié)點(diǎn)、不可解節(jié)點(diǎn).3 .與或圖構(gòu)圖規(guī)那么(1)與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問題或問題集合.圖中起始節(jié)點(diǎn)對(duì)應(yīng)原始 問題.(2)對(duì)應(yīng)于本原問題的節(jié)點(diǎn),叫做終葉節(jié)點(diǎn).(3)有向弧線自A指向后繼節(jié)點(diǎn),表示所求得的子問題集合.(4) 一般對(duì)于代表兩個(gè)或兩個(gè)以上子問題集合的每個(gè)節(jié)點(diǎn),有向弧線從此節(jié)點(diǎn)指向集合中的各個(gè)節(jié)點(diǎn).(5)在特殊#況下,當(dāng)只有一個(gè)算符可應(yīng)用于問題A,而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問題的某個(gè)集合時(shí),由上述規(guī)那么(3)和規(guī)那么(4)所產(chǎn)生的圖可以得到簡(jiǎn)化.提問 對(duì)于三圓盤梵塔難題根據(jù)構(gòu)圖規(guī)那么畫出其歸約圖,并

10、指出圖中的終葉節(jié)點(diǎn)、可解節(jié)點(diǎn)、 不可解節(jié)點(diǎn)2.3謂詞邏輯法教學(xué)內(nèi)容 本節(jié)主要講述問題的謂詞邏輯表示的根本方法.教學(xué)重點(diǎn) 謂詞邏輯、謂詞公式、謂詞演算、置換與合一.教學(xué)難點(diǎn) 如何選擇謂詞,問題的謂詞邏輯表示及運(yùn)算.教學(xué)方法 課堂教學(xué)為主,充分利用網(wǎng)絡(luò)課程中的例如程序.教學(xué)要求重點(diǎn)掌握謂詞邏輯表示的語言與方法,掌握謂詞公式的性質(zhì)及謂詞演算,學(xué)會(huì)謂詞 公式的置換與合一.2.3.1謂詞演算1 .語法和語義謂詞邏輯的根本組成局部是謂詞、變量、函數(shù)和常量,并用圓括弧、方括弧、花括弧和逗號(hào)隔開.2 .連詞和量詞連詞有八(與卜V (或),全稱量詞(產(chǎn)工),存在量詞日工).3 .幾個(gè)有關(guān)定義用連詞人把幾個(gè)公式連

11、接起來而構(gòu)成的公式叫做合取,而此合取式的每個(gè)組成局部叫做合取項(xiàng).一些適宜公式所構(gòu)成的任一合取也是一個(gè)適宜公式.用連詞V把幾個(gè)公式連接起來所構(gòu)成的公式叫做析取,而此析取式的每一組成局部叫做析取項(xiàng).一些適宜公式所構(gòu)成的任一析取也是一個(gè)適宜公式.用連詞=連接兩個(gè)公式所構(gòu)成的公式叫做蘊(yùn)涵.稱蘊(yùn)涵的左式為前項(xiàng),右式為后項(xiàng).如果前項(xiàng)和后項(xiàng)都是適宜公式,那么蘊(yùn)涵也是適宜公式前面具有符號(hào)的公式叫做否認(rèn).一個(gè)適宜公式的否認(rèn)也是適宜公式.如果一個(gè)適宜公式中某個(gè)變量是經(jīng)過量化的,那么稱這個(gè)變量為約束變量,否那么為自由變量.稱所有變量都是受約束的適宜公式為句子.4 .3.2謂詞公式1.謂詞適宜公式的定義在謂詞演算中適

12、宜公式的遞歸定義如下：(1)原子謂詞公式是適宜公式.(2)假設(shè)A為適宜公式,那么A也是一個(gè)適宜公式.(3)假設(shè)A和B都是適宜公式,那么(A A B),(A V B),(A=B)和(A- B)也都是適宜公式.(4)假設(shè)A是適宜公式,x為A中的自由變?cè)?那么(x)A和(x)A都是適宜公式.(5)只有按上述規(guī)那么(1)至(4)求得的那些公式,才是適宜公式.舉例試把以下命題表示為謂詞公式：任何整數(shù)或者為正或者為負(fù).提問指出此例題謂詞公式中的量詞.連詞及蘊(yùn)涵符號(hào).2.3.3置換與合1 .置換一個(gè)表達(dá)式的置換就是在該表達(dá)式中用置換項(xiàng)置換變量.一般說來,置換是可結(jié)合的,但置換是不可交換的.2 .合一尋找項(xiàng)對(duì)

13、變量的置換,以使兩表達(dá)式一致,叫做合一 (unification) o如果一個(gè)置換s作用于表 達(dá)式集Ei的每個(gè)元素,那么用Eis來表示置換例的集.稱表達(dá)式集 Ei是可合一的舉例 表達(dá)式 Px,f(y),B的一個(gè)置換為 s1=z/x,w/y那么:Px,f(y),Bs1=Pz,f(w),B2.4語義網(wǎng)絡(luò)法 教學(xué)內(nèi)容本節(jié)主要講述知識(shí)的語義網(wǎng)絡(luò)表示法.教學(xué)重點(diǎn) 語義網(wǎng)絡(luò)表示的詞法、結(jié)構(gòu)、過程、語義.教學(xué)難點(diǎn) 如何選擇節(jié)點(diǎn)和弧線來構(gòu)成語義網(wǎng)絡(luò).教學(xué)方法課堂教學(xué)教學(xué)要求 重點(diǎn)掌握語義網(wǎng)絡(luò)的結(jié)構(gòu),掌握二元語義網(wǎng)絡(luò)表示方法 ,了解語義網(wǎng)絡(luò)的特點(diǎn).2.4.1 二元語義網(wǎng)絡(luò)的表示1 .語義網(wǎng)絡(luò)的根本概念語義網(wǎng)絡(luò)是

14、知識(shí)的一種結(jié)構(gòu)化圖解表示,它由節(jié)點(diǎn)和弧線或鏈線組成.節(jié)點(diǎn)用于表示實(shí)體、概念和情況等,弧線用于表示節(jié)點(diǎn)間的關(guān)系.語義網(wǎng)絡(luò)表示由以下 4個(gè)相關(guān)局部組成：(1)詞法局部決定表示詞匯表中允許有哪些符號(hào),它涉及各個(gè)節(jié)點(diǎn)和弧線.(2)結(jié)構(gòu)局部表達(dá)符號(hào)排列的約束條件,指定各弧線連接的節(jié)點(diǎn)對(duì).(3)過程局部說明訪問過程,這些過程能用來建立和修正描述,以及答復(fù)相關(guān)問題.(4)語義局部確定與描述相關(guān)的(聯(lián)想)意義的方法即確定有關(guān)節(jié)點(diǎn)的排列及其占有物和對(duì)應(yīng)弧線.2 .二元語義網(wǎng)絡(luò)的表示用兩個(gè)節(jié)點(diǎn)和一條弧線可以表示一個(gè)簡(jiǎn)單的事實(shí),對(duì)于表示占有關(guān)系的語義網(wǎng)絡(luò),是通過允許節(jié)點(diǎn)既可以表示一個(gè)物體或一組物體,也可以表示情況和

15、動(dòng)作.每一情況節(jié)點(diǎn)可以有一組向外的弧(事例弧),稱為事例框,用以說明與該事例有關(guān)的各種變量.在選擇節(jié)點(diǎn)時(shí),首先要弄清節(jié)點(diǎn)是用于表示根本的物體或概念的,或是用于多種目的的.否那么,如果語義網(wǎng)絡(luò)只被用來表示一個(gè)特定的物體或概念,那么當(dāng)有更多的實(shí)例時(shí)就需要更多的語義網(wǎng)絡(luò).選擇語義基元就是試圖用一組基元來表示知識(shí).這些基元描述根本知識(shí),并以圖解表示的形式相互聯(lián)系.舉例 用二元語義網(wǎng)絡(luò)表示：小燕是一只燕子,燕子是鳥；巢-1是小燕的巢,巢-1是巢中的一個(gè).2.4.2 多元語義網(wǎng)絡(luò)的表示語義網(wǎng)絡(luò)是一種網(wǎng)絡(luò)結(jié)構(gòu).節(jié)點(diǎn)之間以鏈相連.從本質(zhì)上講,接點(diǎn)之間的連接是二元關(guān)系.語義網(wǎng)絡(luò)從本質(zhì)上來說,只能表示二元關(guān)系,如

16、果所要表示的事實(shí)是多元關(guān)系 那么把這個(gè)多元 關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合 ,或二元關(guān)系的合取.舉例 用“Liming is a man時(shí)語義網(wǎng)絡(luò)和謂詞邏輯表示說明謂詞邏輯與語義網(wǎng)絡(luò)的等效性.2.4.3 連詞和量化的表示可以用語義網(wǎng)絡(luò)表示謂詞邏輯法中的各種連詞及量化.1 .合取多元關(guān)系可以被轉(zhuǎn)換成一組二元關(guān)系的合取,從而可以用語義網(wǎng)絡(luò)的形式表示出來.2 .析取在語義網(wǎng)絡(luò)中,為與合取關(guān)系相區(qū)別,在析取關(guān)系的連接上加注析取界限,并標(biāo)記DIS.3 .否認(rèn)采用ISA和PART OF關(guān)系或標(biāo)注 NEG界限來表示否認(rèn).4 .蘊(yùn)涵在語義網(wǎng)絡(luò)中可用標(biāo)注 ANTE和CONSE界限來表示蘊(yùn)涵關(guān)系.5 .量化存在量化在語義網(wǎng)絡(luò)中可直接用ISA鏈來表示.而全稱量化就要用分割方法來表示2.5小結(jié)狀態(tài)空間法是一種基于解答空間的問題表示和求解方法.從某個(gè)初始狀態(tài)開始,每次加一個(gè)操作符,遞增地建立起操作符的試驗(yàn)序列,直到到達(dá)目標(biāo)狀態(tài)為止.問題歸約法從目標(biāo)要解決的問題出發(fā),逆向推理,通過一系列變換把初始問題變換為