第1講知識(shí)表示

人工智能第一講知識(shí)表示2第1講知識(shí)表示知識(shí)與知識(shí)表示的概念狀態(tài)空間表示法問(wèn)題歸約及與或圖表示法謂詞邏輯表示法產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法32.1.1知識(shí)的概念知識(shí)：在長(zhǎng)期的生活及社會(huì)實(shí)踐中、在科學(xué)研究及實(shí)驗(yàn)中積累起來(lái)的對(duì)客觀世界的認(rèn)識(shí)與經(jīng)驗(yàn)。知識(shí)：把有關(guān)信息關(guān)聯(lián)在一起所形成的信息結(jié)構(gòu)。知識(shí)反映了客觀世界中事物之間的關(guān)系，不同事物或者相同事物間的不同關(guān)系形成了不同的知識(shí)。信息關(guān)聯(lián)形式：“如果…，則…”如果大雁向南飛，則冬天就要來(lái)臨了例：雪是白色的。——

事實(shí)如果頭疼且流鼻涕，則有可能患了感冒?！?guī)則4相對(duì)正確性任何知識(shí)都是在一定的條件及環(huán)境下產(chǎn)生的，在這種條件及環(huán)境下才是正確的。2.1.2知識(shí)的特征1+1=2（十進(jìn)制）1+1=10（二進(jìn)制）知識(shí)狀態(tài)：“真”，“假”，“中間狀態(tài)”不確定性隨機(jī)性模糊性經(jīng)驗(yàn)性不完全性52.1.2知識(shí)的特征3.

可表示性與可利用性知識(shí)的可表示性：知識(shí)可以用適當(dāng)形式表示出來(lái)，如用語(yǔ)言、文字、圖形、神經(jīng)網(wǎng)絡(luò)等。知識(shí)的可利用性：知識(shí)可以被利用。62.1.3知識(shí)的分類(lèi)按知識(shí)的作用范圍分類(lèi)常識(shí)性知識(shí)：通用性知識(shí)。領(lǐng)域性知識(shí)：專(zhuān)業(yè)性知識(shí)。按知識(shí)的作用及表示事實(shí)性知識(shí)：有關(guān)概念、事實(shí)、事物的屬性及狀態(tài)等。過(guò)程性知識(shí)：有關(guān)系統(tǒng)狀態(tài)變化、問(wèn)題求解過(guò)程的操作、演算和行動(dòng)的知識(shí)?？刂菩灾R(shí)（深層知識(shí)或元知識(shí)）：關(guān)于如何運(yùn)用已有的知識(shí)進(jìn)行問(wèn)題求解的知識(shí)。醋是酸的。北京是中國(guó)的首都。一年有12個(gè)月。例：從北京到上海是乘飛機(jī)還是火車(chē)的問(wèn)題表示如下：事實(shí)性知識(shí)：北京、上海、飛機(jī)、時(shí)間、費(fèi)用…過(guò)程性知識(shí)：乘飛機(jī)、坐火車(chē)控制性知識(shí)：乘飛機(jī)較快、較貴；坐火車(chē)較慢、較便宜72.1.3知識(shí)的分類(lèi)按知識(shí)的結(jié)構(gòu)及表現(xiàn)形式邏輯性知識(shí)：反映人類(lèi)邏輯思維過(guò)程的知識(shí)。形象性知識(shí)：通過(guò)事物的形象建立起來(lái)的知識(shí)。按知識(shí)的確定性確定性知識(shí)：可指出其真值為“真“或”假“的知識(shí)，是精確性的知識(shí)。不確定性知識(shí)：具有不精確、不完全及模糊性等特性的知識(shí)。82.1.4知識(shí)的表示知識(shí)表示（KnowledgeRepresentation）:將人類(lèi)知識(shí)形式化或者模型化。知識(shí)表示是對(duì)知識(shí)的一種描述，或者說(shuō)是一組約定，一種計(jì)算機(jī)可以接受的用于描述知識(shí)的數(shù)據(jù)結(jié)構(gòu)。9第2章知識(shí)表示知識(shí)與知識(shí)表示的概念狀態(tài)空間表示法問(wèn)題歸約及與或圖表示法謂詞邏輯表示法產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法2.2狀態(tài)空間表示法問(wèn)題求解技術(shù)主要是兩個(gè)方面：?jiǎn)栴}的表示：同一問(wèn)題有多種不同的表示求解的方法*1：許多問(wèn)題求解方法采用試探搜索方法狀態(tài)空間法：基于解答空間的問(wèn)題表示和求解方法*2狀態(tài)（state）算符（operator）狀態(tài)空間10112.2狀態(tài)空間表示法定義:狀態(tài)(state)：為描述某類(lèi)不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合，其矢量形式如下：式中每個(gè)元素qi(i=0,1，…，n)為集合的分量，稱(chēng)為狀態(tài)變量。122.2狀態(tài)空間表示法132.2狀態(tài)空間表示法給定每個(gè)變量的一組值就得到一個(gè)具體的狀態(tài)，如

Qk=[q0k，q1k，...，qnk]T

它只是問(wèn)題所有可能狀態(tài)的羅列，還必須描述這些狀態(tài)之間的可能變化。所謂操作，或稱(chēng)為算子是引起狀態(tài)中的某分量發(fā)生改變，從而使問(wèn)題由一個(gè)具體狀態(tài)A變化為另一具體狀態(tài)B的作用。142.2狀態(tài)空間表示法算符：使問(wèn)題從一種狀態(tài)變化為另一種狀態(tài)的手段稱(chēng)為操作符或算符。操作符可為走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。要完成某個(gè)問(wèn)題的狀態(tài)描述，必須確定三件事：

1.該狀態(tài)描述方式，特別是初始狀態(tài)描述；

2.操作符集合及其對(duì)狀態(tài)描述的作用；

3.目標(biāo)狀態(tài)描述的特性。問(wèn)題的狀態(tài)空間(statespace)：是一個(gè)表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說(shuō)明的集合，即所有可能的問(wèn)題初始狀態(tài)集合S(初始狀態(tài)S0∈S)、操作符集合F以及目標(biāo)狀態(tài)集合G(GS)?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。狀態(tài)空間可用有向圖來(lái)表示152.2狀態(tài)空間表示法162.2狀態(tài)空間表示法狀態(tài)空間的一個(gè)解使一個(gè)有限的操作算子序列，它使初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)：S0-f1->S1-f2->...fk->G

17N個(gè)傳教士，N個(gè)野人，一條船，可同時(shí)乘坐k個(gè)人乘渡。傳教士為安全起見(jiàn)，應(yīng)如何規(guī)定擺渡方案，使得任何時(shí)刻，當(dāng)傳教士與野人在同一地點(diǎn)(河兩岸以及船上)時(shí)，野人數(shù)目總是不超過(guò)傳教士的數(shù)目。傳教士與野人均可擺渡。例：傳教士與野人問(wèn)題（M-C問(wèn)題）：以N=3(傳教士或野人數(shù))，k=2(每條船的載人數(shù))為例求解。求解過(guò)程如下：1.狀態(tài)描述用(m,c,b)表示左岸傳教士人數(shù)m、野人人數(shù)c和船的狀態(tài)b（b=0無(wú)船，b=1有船）：0≤m,c≤3,b∈{0,1}。2.操作描述

(1)IF(m,c,1)THEN(m-1,c,0)

(2)IF

(m,

c,

0)

THEN

(m+1,

c,

1)

(3)IF

(m,

c,

1)

THEN

(m,

c-1,

0)

(4)IF

(m,

c,

0)

THEN

(m,

c+1,

1)

(5)IF(m,c,1)THEN(m-1,c-1,0)

(6)IF(m,c,0)THEN(m+1,c+1,1)

(7)IF(m,c,1)THEN(m-2,c,0)

(8)IF(m,c,0)THEN(m+2,c,1)

(9)IF(m,c,1)THEN(m,c-2,0)

(10)IF(m,c,0)THEN(m,c+2,1)3.初始狀態(tài)：(3,3,1)4.結(jié)束狀態(tài)：（0,0,0）19第2章知識(shí)表示知識(shí)與知識(shí)表示的概念狀態(tài)空間表示法問(wèn)題歸約及與或圖表示法謂詞邏輯表示法產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法202.3.1問(wèn)題歸約法問(wèn)題歸約(problemreduction)是另一種問(wèn)題描述與求解方法。先把問(wèn)題分解為子問(wèn)題和子-子問(wèn)題，然后解決較小的問(wèn)題。對(duì)該問(wèn)題的某個(gè)具體子集的解答就意味著對(duì)原始問(wèn)題的一個(gè)解答。21

問(wèn)題歸約描述問(wèn)題歸約表示的組成部分：一個(gè)初始問(wèn)題描述；一套把問(wèn)題變換為子問(wèn)題的操作符；一套本原問(wèn)題描述。其中的每一個(gè)問(wèn)題是不證明的，自然成立的，如公理、已知的實(shí)事等（本原問(wèn)題集）問(wèn)題歸約的實(shí)質(zhì)：從目標(biāo)(要解決的問(wèn)題)出發(fā)逆向推理，建立子問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)平凡的本原問(wèn)題集合。22梵塔難題

有3個(gè)柱子(1，2和3)和3個(gè)不同尺寸的圓盤(pán)（A，B和C）。在每個(gè)圓盤(pán)的中心有一個(gè)孔，所以圓盤(pán)可以堆疊在柱子上。最初，3個(gè)圓盤(pán)都堆在柱子1上：最大的圓盤(pán)C在底部，最小的圓盤(pán)A在頂部。要求把所有圓盤(pán)都移到柱子3上，每次只許移動(dòng)一個(gè)，而且只能先搬動(dòng)柱子頂部的圓盤(pán)，還不許把尺寸較大的圓盤(pán)堆放在尺寸較小的圓盤(pán)上。這個(gè)問(wèn)題的初始配置和目標(biāo)配置如圖所示。圖梵塔問(wèn)題23梵塔難題

解題過(guò)程：

將原始問(wèn)題歸約為一個(gè)較簡(jiǎn)單問(wèn)題集合，要把所有圓盤(pán)都移至柱子3，我們必須首先把圓盤(pán)C移至柱子3；而且在移動(dòng)圓盤(pán)C至柱子3之前，要求柱子3必須是空的。只有在移開(kāi)圓盤(pán)A和B之后，才能移動(dòng)圓盤(pán)C；而且圓盤(pán)A和B最好不要移至柱子3就不能把圓盤(pán)C移至柱子3。因此，首先應(yīng)該把圓盤(pán)A和B移到柱子2上。然后才能夠進(jìn)行關(guān)鍵的一步，把圓盤(pán)C從柱子1移至柱子3，并繼續(xù)解決難題的其余部分。

將原始難題歸約（簡(jiǎn)化）為下列子難題：移動(dòng)圓盤(pán)A和B至柱子2的雙圓盤(pán)難題，如圖(a)所示。24梵塔難題把原始難題歸約（簡(jiǎn)化）為以下三個(gè)子難題：移動(dòng)圓盤(pán)A和B至柱子2的雙圓盤(pán)難題；如圖(a)所示移動(dòng)圓盤(pán)C至柱子3的單圓盤(pán)難題；如圖(b)所示移動(dòng)圓盤(pán)A和B至柱子3雙圓盤(pán)難題；如圖(c)所示25梵塔難題圖2.7梵塔問(wèn)題解答(a)圖2.8梵塔問(wèn)題解答(b)圖2.9梵塔問(wèn)題解答(c)26梵塔難題梵塔問(wèn)題歸約圖：子問(wèn)題2可作為本原問(wèn)題考慮，因?yàn)樗慕庵话徊揭苿?dòng)。應(yīng)用一系列相似的推理，子問(wèn)題1和子問(wèn)題3也可被歸約為本原問(wèn)題，如圖2.10所示。這種圖式結(jié)構(gòu)，叫做與或圖(AND/ORgraph)。

它能有效地說(shuō)明如何由問(wèn)題歸約法求得問(wèn)題的解答。圖2.10梵塔問(wèn)題歸約圖27問(wèn)題歸約法把一個(gè)問(wèn)題描述變換為一個(gè)歸約或后繼問(wèn)題描述的集合，這是由問(wèn)題歸約算符進(jìn)行的。變換所得所有后繼問(wèn)題的解就意味著父輩問(wèn)題的一個(gè)解。所有問(wèn)題歸約的目的是最終產(chǎn)生具有明顯解答的本原問(wèn)題。這些問(wèn)題可能是能夠由狀態(tài)空間搜索中走動(dòng)一步來(lái)解決的問(wèn)題，或者可能是別的具有已知解答的更復(fù)雜的問(wèn)題。282.與或圖表示

一般地，我們用一個(gè)類(lèi)似圖的結(jié)構(gòu)來(lái)表示把問(wèn)題歸約為后繼問(wèn)題的替換集合，這種結(jié)構(gòu)圖叫做問(wèn)題歸約圖，或叫與或圖。如下圖所示:圖2.13子問(wèn)題集合圖2.14與或圖29一些關(guān)于與或圖的術(shù)語(yǔ)：父節(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)記。與或圖：由與節(jié)點(diǎn)及或節(jié)點(diǎn)組成的結(jié)構(gòu)圖。

30可解節(jié)點(diǎn)的一般定義(1)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因?yàn)樗鼈兣c本原問(wèn)題相關(guān)連)。(2)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。(3)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。31不可解節(jié)點(diǎn)的一般定義:(1)沒(méi)有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。(2)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。(3)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。32圖2.15中，終葉節(jié)點(diǎn)用字母t表示，有解節(jié)點(diǎn)用小原點(diǎn)表示，而解圖用粗線分支表示。

圖2.15與或圖例子33與或圖構(gòu)成規(guī)則

(1)與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問(wèn)題或問(wèn)題集合。圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題。

(2)對(duì)應(yīng)于本原問(wèn)題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒(méi)有后裔。

(3)對(duì)于把算符應(yīng)用于問(wèn)題A的每種可能情況，都把問(wèn)題變換為一個(gè)子問(wèn)題集合；有向弧線自A指向后繼節(jié)點(diǎn)表示所求得的子問(wèn)題集合。

(4)一般對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。由于只有當(dāng)集合中所有的項(xiàng)都有解時(shí)，這個(gè)子問(wèn)題的集合才能獲得解答，所以這些子問(wèn)題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。

(5)在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題A，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由上述規(guī)則3和規(guī)則4所產(chǎn)生的圖可以得到簡(jiǎn)化。

因此，代表子問(wèn)題集合的中間或節(jié)點(diǎn)可以被略去，如右圖所示。圖2.16與或樹(shù)34第2章知識(shí)表示知識(shí)與知識(shí)表示的概念狀態(tài)空間表示法問(wèn)題歸約及與或圖表示法謂詞邏輯表示法產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法352.2謂詞邏輯表示法362.2.1命題太陽(yáng)從西邊出來(lái)。372.2.2謂詞382.2.2謂詞392.2.3402.2.3謂詞公式412.2.3謂詞公式422.2.3謂詞公式432.2.3謂詞公式442.2.3謂詞公式452.2.3謂詞公式462.2.4謂詞公式的性質(zhì)472.2.4謂詞公式的性質(zhì)482.2.4謂詞公式的性質(zhì)49502.2.5謂詞邏輯知識(shí)表示方法512.2.5謂詞邏輯知識(shí)表示方法52

例2有下列知識(shí)： 劉歡比他父親出名。 高揚(yáng)是計(jì)算機(jī)系的一名學(xué)生，但他不喜歡編程序。 人人愛(ài)勞動(dòng)。

為了用謂詞公式表示上述知識(shí)，首先需要定義謂詞：

Bigger(x,y):x比y出名。

Computer(x):x是計(jì)算機(jī)系的學(xué)生。

Like(x,y):x喜歡y。

Love(x,y):x熱愛(ài)y。

Man(x):x是人。 然后用謂詞公式把上述知識(shí)表示為：

Bigger（Liuhong,father(Liuhong)) Computer(Gaoyang)∧

Like(Gaoyang,programing) (x)(Man(x)Love(x,labour)2.2.5謂詞邏輯知識(shí)表示方法53例3設(shè)有下列知識(shí)自然數(shù)都是大于零的整數(shù)所有整數(shù)不是偶數(shù)就是奇數(shù)偶數(shù)除以2是整數(shù)首先定義謂詞如下：n(x):x是自然數(shù)I(x):x是整數(shù)E(x):x是偶數(shù)O(x):x是奇數(shù)GZ(x):x大于零另外用函數(shù)S(x)表示x除以2.此時(shí)，上述知識(shí)可用謂詞公式分別表示為：(x)（n(x)GZ(x)∧I(x)）(x)(I(x)E(x)∨O(x))(x)(E(x)I(s(x))2.2.5謂詞邏輯知識(shí)表示方法54例.設(shè)在房?jī)?nèi)c處有一機(jī)器人，在a及b處各有一張桌子，a桌上有一個(gè)盒子，為了讓機(jī)器人從c處出發(fā)把盒子從a處拿到b處的桌上，然后再回到c處，需要制定相應(yīng)的行動(dòng)規(guī)劃。下面用一階謂詞邏輯描述機(jī)器人的行動(dòng)過(guò)程。該例子中，不僅要用謂詞表示事物的狀態(tài)、位置，還要表示其行動(dòng)。cab設(shè)相關(guān)謂詞的定義如下：

table(x):x是桌子

empty(y):y手中是空的

at(y，z)：y在z的附近

holds(y,w):y拿著won(w,x):w在x的上面

其中，x的個(gè)體域是{a,b};y的個(gè)體域是{robot};z的個(gè)體域是{a,b,c};w的個(gè)體域是{box}2.2.5謂詞邏輯知識(shí)表示方法55問(wèn)題的初始狀態(tài)是：at(robot,c)empty(robot)on(box,a)table(a)table(b)問(wèn)題的目標(biāo)狀態(tài)是：at(robot,c)empty(robot)on(box,b)table(a)table(b)機(jī)器人的目標(biāo)是把問(wèn)題的初始狀態(tài)轉(zhuǎn)化為目標(biāo)狀態(tài)，其間它必須完成一系列的操作。cab2.2.5謂詞邏輯知識(shí)表示方法56操作一般可以分為條件和動(dòng)作兩部分。?條件可以很容易的用謂詞公式表示，?動(dòng)作可以通過(guò)動(dòng)作前后的狀態(tài)變化表示出來(lái)，即只要指出動(dòng)作后應(yīng)從動(dòng)作前的狀態(tài)中刪去和增加什么謂詞就描述了相應(yīng)的動(dòng)作。機(jī)器人為了把盒子從a處拿到b處，應(yīng)執(zhí)行如下三個(gè)操作：goto(x,y):從x處走到y(tǒng)處；pick_up(x):在x處拿起盒子；set_done(x):在x處放下盒子。這三個(gè)操作分別用條件和動(dòng)作表示如下：1.Goto(x,y)條件：at(robot,x)動(dòng)作 刪除：at(robot,x)增加：at(robot,y)2.Pick_up(x)條件：on(box,x)∧table(x)∧empty(robot)∧at(robot,x)動(dòng)作 刪除：empty(robot)∧on(box,x)增加:holds(robot,box)2.2.5謂詞邏輯知識(shí)表示方法573.Set_down(x)條件：at(robot,x)∧table(x)∧holds(robot,box)動(dòng)作 刪除：holds(robot,box)增加：empty(robot)∧on(box,x)操作步驟：機(jī)器人在執(zhí)行每一個(gè)操作前，總要先檢查當(dāng)前狀態(tài)是否可使所要求的條件得到滿(mǎn)足。若能滿(mǎn)足，就執(zhí)行相應(yīng)的操作，否則就檢查下一個(gè)操作所要求的條件。所謂檢查當(dāng)前狀態(tài)是否滿(mǎn)足所要求的條件，其實(shí)是一個(gè)定理證明的過(guò)程，即證明當(dāng)前狀態(tài)是否蘊(yùn)含操作所要求的條件，若蘊(yùn)含表示當(dāng)前所要求的條件得到了滿(mǎn)足。機(jī)器人行動(dòng)規(guī)劃問(wèn)題的求解過(guò)程如下：(其中，在檢查條件的滿(mǎn)足性時(shí)要進(jìn)行變量的代換。)2.2.5謂詞邏輯知識(shí)表示方法58At(robot,c)Empty(robot) 狀態(tài)1(初始狀態(tài))On(box,a) 用c代換xTable(a) 用a代換yTable(b)

goto(x,y)At(robot,a)Empty(robot) 狀態(tài)2On(box,a) 用a代換xTable(a)Table(b) pick-up(x)At(robot,a)Hold(robot,box) 狀態(tài)3Table(a) 用a代換xTable(b) 用b代換y

goto(x,y)

At(robot,b)Hold(robot,box) 狀態(tài)4Table(a) 用b代換xTable(b)

setdown(x)

At(robot,b)empty(robot) 狀態(tài)5on(box,b) 用b代換xTable(a) 用c代換yTable(b)

goto(x,y)At(robot,c)empty(robot) 狀態(tài)6on(box,b) (目標(biāo)狀態(tài))Table(a)Table(b)cab2.2.5謂詞邏輯知識(shí)表示方法592.2.6謂詞邏輯知識(shí)表示方法的特點(diǎn)60第2章知識(shí)表示知識(shí)與知識(shí)表示的概念狀態(tài)空間表示法問(wèn)題歸約及與或圖表示法謂詞邏輯表示法產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法612.3產(chǎn)生式622.3.1產(chǎn)生式632.3.1產(chǎn)生式642.3.1產(chǎn)生式652.3.1產(chǎn)生式662.3.1產(chǎn)生式672.3.2產(chǎn)生式系統(tǒng)682.3.2產(chǎn)生式系統(tǒng)692.3.2產(chǎn)生式系統(tǒng)702.3.3產(chǎn)生式系統(tǒng)的例子——?jiǎng)游镒R(shí)別系統(tǒng)712.3.3產(chǎn)生式系統(tǒng)的例子——?jiǎng)游镒R(shí)別系統(tǒng)722.3.3產(chǎn)生式系統(tǒng)的例子——?jiǎng)游镒R(shí)別系統(tǒng)732.3.3產(chǎn)生式系統(tǒng)的例子——?jiǎng)游镒R(shí)別系統(tǒng)742.3.3產(chǎn)生式系統(tǒng)的例子——?jiǎng)游镒R(shí)別系統(tǒng)752.3.3產(chǎn)生式系統(tǒng)的例子——?jiǎng)游镒R(shí)別系統(tǒng)76演繹型(正向)產(chǎn)生式系統(tǒng)獵豹深褐色毛發(fā)有花斑點(diǎn)食肉動(dòng)物食肉哺乳動(dòng)物外形特征有毛發(fā)尖利的牙齒有爪子前視眼R3R2R1深褐色毛發(fā)有花斑點(diǎn)有毛發(fā)尖利的牙齒有爪子前視眼推理方向：

事實(shí)結(jié)論77正向推理的產(chǎn)生式系統(tǒng)算法中的符號(hào)：

DB:存放事實(shí)和中間結(jié)果的事實(shí)庫(kù)；

KB:存放知識(shí)的規(guī)則庫(kù)；

RS:當(dāng)前所有觸發(fā)規(guī)則構(gòu)成的沖突集合。

78正向推理的產(chǎn)生式系統(tǒng)初始事實(shí)放入事實(shí)庫(kù)DBDB中有目標(biāo)？KB中有適用規(guī)則？匹配，將所有觸發(fā)規(guī)則放入沖突集RS

RS

為空？成功，退出失敗，退出用戶(hù)要補(bǔ)充新事實(shí)？

新事實(shí)加入事實(shí)庫(kù)DB是否是是否是否否79正向推理的產(chǎn)生式系統(tǒng)按規(guī)定的沖突解決策略從RS中選擇一條規(guī)則執(zhí)行。執(zhí)行結(jié)果加入事實(shí)庫(kù)DBAB80逆向推理的產(chǎn)生式系統(tǒng)

特點(diǎn)-目標(biāo)驅(qū)動(dòng)：

從假設(shè)的待證目標(biāo)出發(fā)，逆向地運(yùn)用規(guī)則，求證所有支持目標(biāo)所需的條件是否成立。被逆向使用的規(guī)則稱(chēng)為B規(guī)則。

例：假設(shè)待證目標(biāo)： {G

}；事實(shí)證據(jù)庫(kù)：{}

規(guī)則集： {R1:if

BandCthen

G, R2:ifDthen

B,……}

推理后事實(shí)證據(jù)庫(kù)：

{B,C}；{C,D}；……81逆向推理的產(chǎn)生式系統(tǒng)實(shí)例（1）動(dòng)物識(shí)別產(chǎn)生式系統(tǒng):G=“A是獵豹？”

已有知識(shí)（規(guī)則庫(kù)）：R1：

IF

X是食肉動(dòng)物∧X毛發(fā)是深褐色∧X有花斑點(diǎn)

THENX是獵豹。R2：

IF(X是哺乳動(dòng)物)∨(X食肉)∨(X有尖利的牙齒∧X有爪子∧X有前視眼)THENX是食肉動(dòng)物。R3：IFX有毛發(fā)

THENX是哺乳動(dòng)物

已知事實(shí)（事實(shí)庫(kù)）：

A有毛發(fā)；A有尖利的牙齒；A有爪子；A有前視眼；

A毛發(fā)是深褐色；A有花斑點(diǎn)；82推理方向：

目標(biāo)事實(shí)逆向推理的產(chǎn)生式系統(tǒng)實(shí)例（2）獵豹有花斑點(diǎn)食肉動(dòng)物食肉哺乳動(dòng)物外形特征有毛發(fā)尖利的牙齒有爪子前視眼R3R2R1深褐色毛發(fā)深褐色毛發(fā)有花斑點(diǎn)有毛發(fā)尖利的牙齒有爪子前視眼83逆向推理的產(chǎn)生式系統(tǒng)算法中的符號(hào)：

DB:存放最終事實(shí)和中間證據(jù)的事實(shí)證據(jù)庫(kù)；

KB:存放知識(shí)的規(guī)則庫(kù)；

RS:當(dāng)前所有觸發(fā)規(guī)則構(gòu)成的沖突集合。

84逆向推理的產(chǎn)生式系統(tǒng)假設(shè)待證目標(biāo)DB有支持目標(biāo)的事實(shí)KB中有支持目標(biāo)的規(guī)則匹配，將所有觸發(fā)規(guī)則放入沖突集RS目標(biāo)成立，退出事實(shí)支持假設(shè)目標(biāo)，事實(shí)送DB

用戶(hù)補(bǔ)充新事實(shí)？

詢(xún)問(wèn)用戶(hù)是否是否是否AB

目標(biāo)不成立,退出

RS

為空？是否85A選擇規(guī)則的一個(gè)前提條件作為新的待證目標(biāo)。B從RS中選擇一條觸發(fā)規(guī)則逆向推理的產(chǎn)生式系統(tǒng)86正（逆）向產(chǎn)生式系統(tǒng)的比較特點(diǎn)正向推理逆向推理推理驅(qū)動(dòng)方式數(shù)據(jù)驅(qū)動(dòng)目標(biāo)驅(qū)動(dòng)優(yōu)點(diǎn)算法簡(jiǎn)單，易于實(shí)現(xiàn)搜索目的性強(qiáng)，推理效率高

缺點(diǎn)1、搜索目的性弱，可能求解出多個(gè)無(wú)關(guān)的結(jié)論；2、匹配時(shí)，要遍歷整個(gè)規(guī)則庫(kù)，推理效率低。1、確定目標(biāo)的時(shí)候，具有盲目性，可能產(chǎn)生假目標(biāo)2、當(dāng)規(guī)則的后件是操作而非斷言時(shí)，即反應(yīng)型系統(tǒng)，不宜使用此法

用途主要用于已知初始數(shù)據(jù)，不知目標(biāo)的推理；或是解空間大的一類(lèi)推理。主要用于結(jié)論單一或已知目標(biāo)求證的一類(lèi)推理。應(yīng)用監(jiān)控、預(yù)測(cè)、規(guī)劃、設(shè)計(jì)等選擇、分類(lèi)、故障診斷等872.3.4產(chǎn)生式表示的特點(diǎn)88第2章知識(shí)表示知識(shí)與知識(shí)表示的概念狀態(tài)空間表示法問(wèn)題歸約及與或圖表示法謂詞邏輯表示法產(chǎn)生式表示法語(yǔ)義網(wǎng)絡(luò)表示法891.概述

語(yǔ)義網(wǎng)絡(luò)1968年由J.R.Quillian提出，開(kāi)始是作為人類(lèi)聯(lián)想記憶的一個(gè)顯式心理學(xué)模型提出，隨后在AI中用于自然語(yǔ)言理解，表示命題信息（具有邏輯真的事實(shí)）。目前語(yǔ)義網(wǎng)絡(luò)已廣泛應(yīng)用于人工智能的許多領(lǐng)域，是一種表達(dá)能力強(qiáng)而且靈活的知識(shí)表達(dá)方式。

?語(yǔ)義網(wǎng)絡(luò)是通過(guò)概念及其語(yǔ)義關(guān)系來(lái)表示知識(shí)的一種網(wǎng)絡(luò)圖

；

?從圖論的觀點(diǎn)看，他們就是一個(gè)“帶標(biāo)識(shí)的有向圖”；

?語(yǔ)義網(wǎng)絡(luò)由節(jié)點(diǎn)和節(jié)點(diǎn)間的弧組成；節(jié)點(diǎn)表示各種事物，概念，情況，屬性，動(dòng)作，狀況等；弧表示各種語(yǔ)義聯(lián)系，指明他所連接的節(jié)點(diǎn)間的各種語(yǔ)義聯(lián)系；

?節(jié)點(diǎn)和弧都必須帶有標(biāo)識(shí)，以便區(qū)分各種不同對(duì)象以及對(duì)象間的各種不同語(yǔ)義聯(lián)系；

?每個(gè)節(jié)點(diǎn)可以帶有若干屬性，一般用框架或元組表示；

?節(jié)點(diǎn)還可以是一個(gè)語(yǔ)義子網(wǎng)絡(luò)，形成一個(gè)多層次的嵌套結(jié)構(gòu)。

知識(shí)的語(yǔ)義網(wǎng)絡(luò)表示方法90

一個(gè)最簡(jiǎn)單的語(yǔ)義網(wǎng)絡(luò)是如下一個(gè)三元組：

（節(jié)點(diǎn)1，弧，節(jié)點(diǎn)2）它可用圖表示，稱(chēng)為一個(gè)基本網(wǎng)元。

其中，A,B分別代表兩個(gè)節(jié)點(diǎn)；RAB表示A與B之間的語(yǔ)某種語(yǔ)義聯(lián)系。

例如：

其中，在獵狗與狗之間的語(yǔ)義關(guān)系”是一種”具體的指出了獵狗與狗的語(yǔ)義關(guān)系，即獵狗是狗的一種，兩者之間存在類(lèi)屬關(guān)系。這里，弧線的方向是有意義的，需要根據(jù)事務(wù)間的關(guān)系確定。例如在表示類(lèi)屬關(guān)系時(shí)，箭頭所指的節(jié)點(diǎn)代表上層概念，而箭尾的節(jié)點(diǎn)代表下層概念。ABRAB獵狗狗是一種91常用的語(yǔ)義聯(lián)系

語(yǔ)義聯(lián)系反映了節(jié)點(diǎn)間的語(yǔ)義關(guān)系。下面列出一些常用的語(yǔ)義聯(lián)系，用作參考：1．A-Member-of聯(lián)系它表示個(gè)體與集體之間的關(guān)系，它們之間有屬性繼承權(quán)和屬性更改權(quán)。例如：張三是工會(huì)會(huì)員。張三工會(huì)A-Member-of2．Composed–of聯(lián)系它表示構(gòu)成聯(lián)系，是一種一對(duì)多的聯(lián)系，被它連接的節(jié)點(diǎn)不具有屬性繼承性。例如：整數(shù)由正整數(shù)、負(fù)整數(shù)及零組成。整數(shù)與正整數(shù)零負(fù)整數(shù)Composed–of923.have聯(lián)系它表示屬性或事物的占有關(guān)系。鳥(niǎo)翅膀have4.Before,after,at聯(lián)系它們是用來(lái)表示事件之間的時(shí)間先后關(guān)系，其中,before表示一個(gè)事件在另一個(gè)事件之前發(fā)生，after表示一個(gè)事件在另一個(gè)事件之后發(fā)生，

at表示某一事件發(fā)生的時(shí)間唐朝宋朝before5.located-on聯(lián)系這些聯(lián)系用來(lái)表示事物間的位置關(guān)系。6.similar-to，near-to聯(lián)系這些語(yǔ)義聯(lián)系用來(lái)表示事物間的相似和接近的聯(lián)系。書(shū)桌子located-on貓虎similar-to此外，ISA、AKO、Infer燈也可用作語(yǔ)義網(wǎng)絡(luò)。93當(dāng)把多個(gè)基本網(wǎng)元用相應(yīng)語(yǔ)義聯(lián)系關(guān)聯(lián)在一起時(shí)，就可得到一個(gè)語(yǔ)義網(wǎng)絡(luò)。例如：由三個(gè)基本網(wǎng)元，經(jīng)合并后可得到一個(gè)語(yǔ)義網(wǎng)絡(luò)。ABBCACRABRBCRACABCRABRBCRAC語(yǔ)義網(wǎng)絡(luò)的BNF描述：<語(yǔ)義網(wǎng)絡(luò)>::=<基本網(wǎng)元>|Merge(<基本網(wǎng)元>，…）<基本網(wǎng)元>::=<節(jié)點(diǎn)><語(yǔ)義聯(lián)系><節(jié)點(diǎn)><節(jié)點(diǎn)>::=（<屬性—值對(duì)>，…）<屬性—值對(duì)>::=<屬性名>:<屬性值>）<語(yǔ)義聯(lián)系>::=<系統(tǒng)預(yù)定義語(yǔ)義聯(lián)系>|<用戶(hù)自定義語(yǔ)義聯(lián)系>）其中，Merge(…)是一個(gè)合并過(guò)程，它把括弧中的所有基本網(wǎng)元關(guān)聯(lián)在一起，即把相同的節(jié)點(diǎn)合并為一個(gè)，從而構(gòu)成一個(gè)語(yǔ)義網(wǎng)絡(luò)。942.知識(shí)的語(yǔ)義網(wǎng)絡(luò)表示

語(yǔ)義網(wǎng)絡(luò)可以表示事實(shí)性的知識(shí)，也可以表示有關(guān)事實(shí)性知識(shí)之間的復(fù)雜聯(lián)系。

(1)用語(yǔ)義網(wǎng)絡(luò)表示事實(shí)

：表示節(jié)點(diǎn)——

：表示狐：該節(jié)點(diǎn)描述對(duì)象的屬性

該語(yǔ)義網(wǎng)絡(luò)表示了獵狗是一種狗，且進(jìn)一步指出狗是一種動(dòng)物，并且分別指出他們所具有的屬性。（做這些只要在圖中增加一個(gè)節(jié)點(diǎn)和一條弧，并對(duì)每個(gè)節(jié)點(diǎn)附上相應(yīng)的屬性就可以了。）?

語(yǔ)義網(wǎng)絡(luò)具有屬性繼承的特性，即下層概念可以繼承上層概念的屬性，這樣就可以在下層概念中只列出它獨(dú)有的屬性。?

另外下層概念還可以對(duì)其上層概念的屬性作進(jìn)一步的細(xì)化，補(bǔ)充，變異，使之能更準(zhǔn)確的反映下層概念的特征。

獵狗

狗

動(dòng)物吃肉身上有毛有生命能狩獵有尾巴能運(yùn)動(dòng)跑得快

會(huì)吃Ⅰ.一般表示95Ⅱ.表示稍復(fù)雜系統(tǒng)：在一些稍復(fù)雜的事實(shí)性知識(shí)中，經(jīng)常會(huì)用到像“并且“及“或者“這樣的連接詞。（用謂詞公式表示時(shí)，可用合取符號(hào)和析取符號(hào)把他們表示出來(lái)），語(yǔ)義網(wǎng)絡(luò)可以通過(guò)增設(shè)合取節(jié)點(diǎn)及析取節(jié)點(diǎn)來(lái)表示。例如：與會(huì)者有男，有女，有年老的，有年青的。其語(yǔ)義網(wǎng)絡(luò)為：

（其中，A,B,C,D分別

代表四種不同情況的與會(huì)者）

人

與會(huì)者ABCD

與或或

男

女

年老

年輕狀態(tài)狀態(tài)狀態(tài)狀態(tài)部分部分部分部分是96Ⅲ.表示某一情況，某一事件或者某個(gè)動(dòng)作：上述例子中的節(jié)點(diǎn)都是用來(lái)表示一個(gè)事物或是一個(gè)具體概念的，其實(shí)，節(jié)點(diǎn)還可以表示某一情況，某一事件或者某個(gè)動(dòng)作。此時(shí)，節(jié)點(diǎn)可以有一組向外的弧，用于指出不同的情況，例如當(dāng)用節(jié)點(diǎn)表示某一動(dòng)作時(shí)，向外的弧可用來(lái)指出動(dòng)作的主體及客體。

例1：有如下事實(shí)：張山給肖紅一本書(shū)

(可把張山給肖紅一本書(shū)作為一個(gè)事件，并在語(yǔ)義網(wǎng)絡(luò)中增設(shè)一個(gè)“事件”節(jié)點(diǎn))一本書(shū)

給予事件

張山

肖紅

給客體2客體1動(dòng)作主體97小信使鴿子鳥(niǎo)占有窩鳥(niǎo)窩春天時(shí)間秋天情況是一只占有者是一種是一種占有物開(kāi)始于結(jié)束于是是

其中，“占有”

為一個(gè)動(dòng)作節(jié)點(diǎn)，通過(guò)它，不僅可以描述占有“窩”，還可描述占有“窩”的時(shí)間。例2：有下述事實(shí)：“小信使”這只鴿子從春天到秋天占有一個(gè)窩。98

(2)用語(yǔ)義網(wǎng)絡(luò)表示有關(guān)事實(shí)間的關(guān)系

語(yǔ)義網(wǎng)絡(luò)可以描述事物間多種復(fù)雜的語(yǔ)義關(guān)系，下面是常用的幾種：

Ⅰ.分類(lèi)關(guān)系：指事物間的類(lèi)屬關(guān)系。如“是一種”等。動(dòng)物

魚(yú)

八哥

鴕鳥(niǎo)鯊魚(yú)草魚(yú)鳥(niǎo)會(huì)學(xué)人語(yǔ)善鳴不會(huì)飛善奔走有牙吃肉是一種是一種是一種是一種是一種是一種吃生活在水中會(huì)游泳能運(yùn)動(dòng)會(huì)吃會(huì)飛有羽毛

下層概念節(jié)點(diǎn)除了可繼承，細(xì)化，補(bǔ)充上層概念節(jié)點(diǎn)的屬性外，還出現(xiàn)了變異的情況：鳥(niǎo)是鴕鳥(niǎo)的上層概念節(jié)點(diǎn)，其屬性是有羽毛，會(huì)飛，但鴕鳥(niǎo)只是繼承了有羽毛這一屬性，把鳥(niǎo)的會(huì)飛變異為不會(huì)飛，善奔走。

99Ⅱ.聚集關(guān)系：如果下層概念是其上層概念的一方面或者一個(gè)部分，則稱(chēng)它們是聚集關(guān)系。教學(xué)教師課程學(xué)生部分部分部分Ⅲ.推論關(guān)系：如果一個(gè)概念可由另一個(gè)概念推出，則稱(chēng)它們之間存在推論關(guān)系。需進(jìn)食饑餓推出Ⅳ.時(shí)間、位置關(guān)系：思遠(yuǎn)公司朱雀大街位于100

Ⅴ.多元關(guān)系：在語(yǔ)義網(wǎng)絡(luò)中，一條弧只能從一個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)，適合于表示一個(gè)二元關(guān)系。但在許多情況下需要用一種關(guān)系把幾個(gè)事物聯(lián)系起來(lái)。例如對(duì)于如下事實(shí)：

鄭州位于西安和北京之間。

為了在語(yǔ)義網(wǎng)絡(luò)中描述多元關(guān)系，可以用節(jié)點(diǎn)來(lái)表示關(guān)系。位置關(guān)系鄭州北京西安居中邊界_1邊界_2101(3)用語(yǔ)義網(wǎng)絡(luò)表示比較復(fù)雜的知識(shí)

設(shè)有如下兩個(gè)事實(shí)：張三的自行車(chē)是飛鴿牌，黑色，28型李四的自行車(chē)是金獅牌，紅色，26型將其用語(yǔ)義網(wǎng)絡(luò)描述出來(lái)。

[分析]?

如寫(xiě)成兩個(gè)網(wǎng)絡(luò)，很容易，但對(duì)知識(shí)的利用帶來(lái)不便，如何寫(xiě)成一個(gè)呢？

?

分析事實(shí)發(fā)現(xiàn)，它們都是關(guān)于自行車(chē)的，因此只要把自行車(chē)作為一個(gè)通用概念用一個(gè)節(jié)點(diǎn)表示，而把張三李四的自行車(chē)作為他們的實(shí)例。這樣，就很容易用一個(gè)語(yǔ)義網(wǎng)絡(luò)把它們表示出來(lái)，當(dāng)要