人工智能與其應(yīng)用-知識表示

人工智能與其應(yīng)用_知識表示第一頁，共114頁。知識表示的基本概念

知識表示：研究用機(jī)器表示知識的可行性、有效性的一般方法，是一種數(shù)據(jù)結(jié)構(gòu)與控制結(jié)構(gòu)的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組描述事物的約定，以把人類知識表示成機(jī)器能處理的數(shù)據(jù)結(jié)構(gòu)。第二頁，共114頁。人工智能系統(tǒng)所關(guān)心的知識事實

有關(guān)問題環(huán)境的一些事物的知識，常以“…是…”的形式出現(xiàn)。如事物的分類、屬性、事物間關(guān)系、科學(xué)事實、客觀事實等。如雪是白色的、鳥有翅膀、張三李四是好朋友、這輛車是張三的。規(guī)則有關(guān)問題中與事物的行動、動作相聯(lián)系的因果關(guān)系知識，是動態(tài)的，常以“如果…那么…”形式出現(xiàn)。

控制有關(guān)問題的求解步驟、技巧性知識，告訴怎么做一件事。

元知識有關(guān)知識的知識，是知識庫中的高層知識。包括怎樣使用規(guī)則、解釋規(guī)則、校驗規(guī)則、解釋程序結(jié)構(gòu)等知識。第三頁，共114頁。2.1狀態(tài)空間法問題求解問題求解(problemsolving)是個大課題，它涉及歸約、推斷、決策、規(guī)劃、常識推理、定理證明和相關(guān)過程的核心概念。在分析了人工智能研究中運(yùn)用的問題求解方法之后，就會發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。也就是說，這些方法是通過在某個可能的解空間內(nèi)尋找一個解來求解問題的。狀態(tài)空間法：基于解答空間的問題表示和求解方法，它是以狀態(tài)和算符(operator)為基礎(chǔ)來表示和求解問題的。第四頁，共114頁。2.1狀態(tài)空間法1.問題求解技術(shù)兩個主要的方面

(1)問題的表示：如果描述方法不對，對問題求解會帶來很大的困難；(2)求解的方法：采用試探搜索方法。

2.狀態(tài)空間法三要點(diǎn)

(1)狀態(tài)（state）(2)算符（operator）(3)狀態(tài)空間方法第五頁，共114頁。2.1狀態(tài)空間法2.1.1問題狀態(tài)描述

1.定義

狀態(tài)(state)：為描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0,q1,…,qn]T式中每個元素qi(i=0,1,,n)為集合的分量,稱為狀態(tài)變量,給定每個分量的一組值就得到一個具體的狀態(tài),如Qk=[q0k,q1k,…,qnk]T式中每個元素qi(i=0,1，…，n)為集合的分量，稱為狀態(tài)變量。算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號或邏輯符號等。問題的狀態(tài)空間(statespace)：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標(biāo)狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。第六頁，共114頁。2.1狀態(tài)空間法2.狀態(tài)空間表示詳釋

讓我們先用數(shù)碼難題(puzzleproblem)來說明狀態(tài)空間表示的概念。由15個編有1至15并放在4×4方格棋盤上的可走動的棋子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進(jìn)空格，這也可以理解為移動空格。圖中繪出了兩種棋局，即初始棋局和目標(biāo)棋局，它們對應(yīng)于該下棋問題的初始狀態(tài)和目標(biāo)狀態(tài)。

如何把初始棋局變換為目標(biāo)棋局呢？問題的解答就是某個合適的棋子走步序列，如"左移棋子12，下移棋子15，右移棋子4，…"等等。

第七頁，共114頁。2.1狀態(tài)空間法2.狀態(tài)空間表示詳釋狀態(tài)空間法：從某個初始狀態(tài)開始，每次加一個操作符，遞增的建立起操作符的試驗序列，直到達(dá)到目標(biāo)狀態(tài)為止。尋找狀態(tài)空間的全部過程包括從舊的狀態(tài)描述產(chǎn)生新的狀態(tài)描述，以及此后檢驗這些新的狀態(tài)描述，看是否達(dá)到了該目標(biāo)狀態(tài)。對于最優(yōu)化問題找到任一目標(biāo)狀態(tài)是不夠的，必須按某個準(zhǔn)則實現(xiàn)最優(yōu)化路徑。P26完成目標(biāo)狀態(tài)的三件事：１狀態(tài)描述方式，特別是初始狀態(tài)描述；２操作符集合及其對狀態(tài)描述的作用；３目標(biāo)狀態(tài)的特性。第八頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

為了對狀態(tài)空間圖有更深入的了解，這里介紹一下圖論中的幾個術(shù)語和圖的正式表示法。

1.圖論中的幾個術(shù)語

節(jié)點(diǎn)(node)：圖形上的匯合點(diǎn)，用來表示狀態(tài)、事件和時間關(guān)系的匯合，也可用來指示通路的匯合；弧線(arc)：節(jié)點(diǎn)間的連接線；

有向圖(directedgraph)：一對節(jié)點(diǎn)用弧線連接起來，從一個節(jié)點(diǎn)指向另一個節(jié)點(diǎn)。后繼節(jié)點(diǎn)(descendantnode)與父輩節(jié)點(diǎn)(parentnode)：如果某條弧線從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj，那么節(jié)點(diǎn)nj就叫做節(jié)點(diǎn)ni的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)ni叫做節(jié)點(diǎn)nj的父輩節(jié)點(diǎn)或祖先。第九頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

1.圖論中的幾個術(shù)語

路徑：某個節(jié)點(diǎn)序列(ni1,ni2,…,nik)當(dāng)j=2，3，…，k時，如果對于每一個ni，j-1都有一個后繼節(jié)點(diǎn)nij存在，那么就把這個節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)ni1至節(jié)點(diǎn)nik的長度為k的路徑。代價：用c(ni,nj)來表示從節(jié)點(diǎn)ni指向節(jié)點(diǎn)nj的那段弧線的代價。兩節(jié)點(diǎn)間路徑的代價等于連接該路徑上各節(jié)點(diǎn)的所有弧線代價之和。顯式表示：各節(jié)點(diǎn)及其具有代價的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線的代價。隱式表示：節(jié)點(diǎn)的無限集合{si}作為起始節(jié)點(diǎn)是已知的。后繼節(jié)點(diǎn)算符Γ也是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線的代價。第十頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

2.圖的顯式和隱式表示

一個圖可由顯式說明也可由隱式說明。顯然，顯式說明對于大型的圖是不切實際的，而對于具有無限節(jié)點(diǎn)集合的圖則是不可能的。

此外，引入后繼節(jié)點(diǎn)算符的概念是方便的。后繼節(jié)點(diǎn)算符Γ也是已知的，它能作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線的代價把后繼算符應(yīng)用于{si}的成員和它們的后繼節(jié)點(diǎn)以及這些后繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)，如此無限制地進(jìn)行下去，最后使得由Γ和{si}所規(guī)定的隱式圖變?yōu)轱@示圖。問題的表示對求解工作量有很大的影響。人們顯然希望有較小的狀態(tài)空間表示。許多似乎很難的問題，當(dāng)表示適當(dāng)時就可能具有小而簡單的狀態(tài)空間。第十一頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法根據(jù)問題狀態(tài)、操作符和目標(biāo)條件選擇各種表示，是高效率問題求解必須的。各種問題都可以用狀態(tài)空間加以表示，并用狀態(tài)空間搜索法來求解。第十二頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

1.產(chǎn)生式系統(tǒng)（ProductionSystem）

·一個總數(shù)據(jù)庫(globaldatabase)：它含有與具體任務(wù)有關(guān)的信息；隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫可能小得像數(shù)字矩陣那樣簡單，或許大得如檢索文件結(jié)構(gòu)那么復(fù)雜?！ひ惶滓?guī)則：它對數(shù)據(jù)庫進(jìn)行操作運(yùn)算。每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用時所完成的動作。用規(guī)則來改變數(shù)據(jù)庫就象用算符來改變狀態(tài)一樣。·一個控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫的終止條件滿足時，就停止計算。控制策略由控制系統(tǒng)選擇和確定。第十三頁，共114頁。推銷員旅行問題總數(shù)據(jù)庫：到目前為止所訪問的城市；規(guī)則對應(yīng)于決策：即下一步走向城市Ａ，下一步走向城市Ｂ，…，下一步走向城市Ｅ，一條規(guī)則必須能把某個數(shù)據(jù)庫變?yōu)橐粋€合法數(shù)據(jù)庫，否則不適應(yīng)這個數(shù)據(jù)庫；任一以Ａ為起點(diǎn)和終點(diǎn)，并出現(xiàn)所有其它城市的總數(shù)據(jù)庫，都滿足終止條件．第十四頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

2.狀態(tài)空間表示舉例

例2猴子和香蕉問題(monkeyandbananaproblem)

在一個房間內(nèi)有一只猴子(可把這只猴子看做一個機(jī)器人)、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢?圖2.4表示出猴子、香蕉和箱子在房間內(nèi)的相對位置。猴子和香蕉...

用一個四元表列(W,X,Y,Z)來表示這個問題的狀態(tài)，

其中

W－猴子的水平位置

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

Y－箱子的水平位置

Z－當(dāng)猴子摘到香蕉時取Z=1；否則取Z=0

圖2.4猴子和香蕉問題第十五頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

這個問題中的操作(算符)如下：

(1)goto(U)猴子走到水平位置U，或者用產(chǎn)生式規(guī)則表示為：(W，0，Y，z)(U，0，Y，z)(2.3)即應(yīng)用操作goto(U)，能把狀態(tài)(W，0，Y，z)變換為狀態(tài)(U，0，Y，z)。

(2)pushbox(V)猴子把箱子推到水平位置V，即有(W，0，W，z)(V，0，V，z)(2.4)應(yīng)當(dāng)注意的是，要應(yīng)用算符pushbox(V)，就要求產(chǎn)生式規(guī)則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。這種強(qiáng)加于操作的適用性條件，叫做產(chǎn)生式規(guī)則的先決條件。

第十六頁，共114頁。2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

這個問題中的操作(算符)如下：

(3)climbbox猴子爬上箱頂，即有(W，0，W，z)(W，1，W，z)(2.5)在應(yīng)用算符climbbox時也必須注意到，猴子和箱子應(yīng)當(dāng)在同一位置上，而且猴子不在箱頂上。

(4)grasp猴子摘到香蕉，即有(c,1,c,0)(c,1,c,1)(2.6)其中，c是香蕉正下方的地板位置，在應(yīng)用算符grasp時，要求猴子和箱子都在位置c上，并且猴子已在箱子頂上。第十七頁，共114頁。2.1狀態(tài)空間法

對于規(guī)則(2)，只有當(dāng)算符pushbox(V)的先決條件，即猴子與箱子在同一位置上而且猴子不在箱頂上這些條件得到滿足時，算符pushbox(V)才是適用的。這一操作算符的作用是猴子把箱子推到位置V。在這一表示中，目標(biāo)狀態(tài)的集合可由任何最后元素為1的表列來描述。令初始狀態(tài)為(a,0,b,0)

這時，goto(U)是唯一適用的操作，并導(dǎo)致下一狀態(tài)(U,0,b,0)?，F(xiàn)在有3個適用的操作，即goto(U)，pushbox(V)和climbbox(若U=b)。猴子和香蕉問題的狀態(tài)空間圖第十八頁，共114頁。2.2問題歸約法

2.2.1問題歸約描述

先把問題分解為子問題和子-子問題，然后解決較小的問題。對該問題的某個具體子集的解答就意味著對原始問題的一個解答。問題歸約表示的組成部分：一個初始問題描述；一套把問題變換為子問題的操作符；一套本原問題描述。問題歸約的實質(zhì)：從目標(biāo)(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。

第十九頁，共114頁。2.2問題歸約法

2.2.1問題歸約描述１梵塔難題

有3個柱子(1，2和3)和3個不同尺寸的圓盤（A，B和C）。在每個圓盤的中心有一個孔，所以圓盤可以堆疊在柱子上。最初，3個圓盤都堆在柱子1上：最大的圓盤C在底部，最小的圓盤A在頂部。要求把所有圓盤都移到柱子3上，每次只許移動一個，而且只能先搬動柱子頂部的圓盤，還不許把尺寸較大的圓盤堆放在尺寸較小的圓盤上。這個問題的初始配置和目標(biāo)配置如圖2.6所示。第二十頁，共114頁。2.2問題歸約法

解題過程：

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

將原始難題歸約（簡化）為下列子難題：移動圓盤A和B至柱子2的雙圓盤難題，如圖(a)所示。第二十一頁，共114頁。2.2問題歸約法

圖2.7梵塔問題解答(a)圖2.8梵塔問題解答(b)圖2.9梵塔問題解答(c)第二十二頁，共114頁。2.2問題歸約法

梵塔問題歸約圖：子問題2可作為本原問題考慮，因為它的解只包含一步移動。應(yīng)用一系列相似的推理，子問題1和子問題3也可被歸約為本原問題，如圖2.10所示。這種圖式結(jié)構(gòu)，叫做與或圖(AND/ORgraph)。

它能有效地說明如何由問題歸約法求得問題的解答。梵塔問題歸約圖第二十三頁，共114頁。2.2問題歸約法

2.2.1問題歸約描述２問題歸約描述問題歸約方法應(yīng)用算符把問題描述變換為子問題描述，問題描述可以用多種數(shù)據(jù)結(jié)構(gòu)形式，包括表列、樹、字符串、矢量、數(shù)組等。梵塔問題采用包含兩個數(shù)列的表列來描述,[(113),（333)]表示把配置（113）變換為配置（333）。用狀態(tài)空間表示的三元組合（S，F(xiàn)，G）來規(guī)定與描述問題，有關(guān)子問題可以當(dāng)作狀態(tài)空間中的兩個一定的“腳踏石”之間尋找路徑來辨別。梵塔問題中的子問題[（111）=>（122）]，[（122）=>（322）]，[（322）=>（333）]，規(guī)定了最后的路徑將要通過“腳踏石”狀態(tài)（122）和（322）。第二十四頁，共114頁。2.2問題歸約法

2.2.2與或圖表示

與圖、或圖、與或圖：

一般地，我們用一個類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合，這種結(jié)構(gòu)圖叫做問題歸約圖，或叫與或圖。如下圖所示:（引入附加節(jié)點(diǎn)使含有一個以上后繼問題的每個集合能夠聚集在它們各自的父輩節(jié)點(diǎn)之下。）子問題替換集合結(jié)構(gòu)圖與或圖

第二十五頁，共114頁。2.2問題歸約法

2.2.2問題歸約描述

一些關(guān)于與或圖的術(shù)語：終葉節(jié)點(diǎn)：對應(yīng)于原問題的本原節(jié)點(diǎn)?；蚬?jié)點(diǎn)：只要解決某個問題就可解決其父輩問題的節(jié)點(diǎn)集合，如（M，N，H）。與節(jié)點(diǎn)：只有解決所有子問題，才能解決其父輩問題的節(jié)點(diǎn)集合，如（B,C)和（D,E,F）各個結(jié)點(diǎn)之間用一端小圓弧連接標(biāo)記。

第二十六頁，共114頁。2.2問題歸約法

2.2.2問題歸約描述

與或圖：由與節(jié)點(diǎn)及或節(jié)點(diǎn)組成的結(jié)構(gòu)圖。可解節(jié)點(diǎn)的一般定義：

(1)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)(因為它們與本原問題相關(guān)連)。

(2)如果某個非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼節(jié)點(diǎn)至少有一個是可解的時，此非終葉節(jié)點(diǎn)才是可解的。

(3)如果某個非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)全部為可解時，此非終葉節(jié)點(diǎn)才是可解的。圖2.15與或圖例子第二十七頁，共114頁。2.2問題歸約法

2.2.2問題歸約描述

不可解節(jié)點(diǎn)的一般定義:

(1)沒有后裔的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。(2)如果某個非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時，此非終葉節(jié)點(diǎn)才是不可解的。(3)如果某個非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔至少有一個為不可解時，此非終葉節(jié)點(diǎn)才是不可解的。

第二十八頁，共114頁。2.2問題歸約法

2.2.2問題歸約描述

與或圖構(gòu)成規(guī)則

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

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

(3)對于把算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個子問題集合；有向弧線自A指向后繼節(jié)點(diǎn)表示所求得的子問題集合，如下圖所示，把問題A歸約為3個不同的子問題集合N，M，H(或節(jié)點(diǎn))。

圖2.16與或樹第二十九頁，共114頁。2.2問題歸約法

2.2.2問題歸約描述

與或圖構(gòu)成規(guī)則(4)一般對于代表兩個或兩個以上子問題集合的每個節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問題集合中的各個節(jié)點(diǎn)。由于只有當(dāng)集合中所有的項都有解時，這個子問題的集合才能獲得解答，所以這些子問題節(jié)點(diǎn)叫做與節(jié)點(diǎn)。

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

因此，代表子問題集合的中間或節(jié)點(diǎn)可以被略去，如右圖所示。

圖2.16與或樹第三十頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

1.語法和語義(Syntax&Semantics)

謂詞邏輯的基本組成部分：謂詞符號、變量符號、函數(shù)符號和常量符號，并用圓括號、方括號、花括號和逗號隔開，表示論域內(nèi)的關(guān)系。原子公式(atomicformulas)由若干謂詞符號和項組成的謂詞演算。原子公式是謂詞演算基本積木塊。例如，要表示＂機(jī)器人(ROBOT)在１號房間(r1)內(nèi)＂，如圖2.19所示，可以應(yīng)用原子公式:第三十一頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

1.語法和語義(Syntax&Semantics)

當(dāng)機(jī)器人ROBOT移到房間r2時，原子公式可以表示為：INROOM(ROBOT,r2)這兩個原子公式的通用形式就是

又如,“李的母親和他的父親結(jié)婚”這句話的原子公式表示如下：第三十二頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

2.連詞和量詞(Connective&Quantifiers)(1)連詞

與·合取（conjunction）合取就是用連詞∧把幾個公式連接起來而構(gòu)成的公式。合取項是合取式的每個組成部分。例：LIKE(I，MUSIC)∧LIKE(I，PAINTING)(我喜愛音樂和繪畫。)

第三十三頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

2.連詞和量詞(Connective&Quantifiers)或·析?。╠isjunction）析取就是用連詞∨把幾個公式連接起來而構(gòu)成的公式。析取項是析取式的每個組成部分。例：PLAYS(LILI，BASKETBALL)∨PLAYS(LILI，F(xiàn)OOTBALL)(李力打籃球或踢足球。)

第三十四頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

2.連詞和量詞(Connective&Quantifiers)

(1)連詞

蘊(yùn)涵"=>"表示"如果-那么"的語句。用連詞=>連接兩個公式所構(gòu)成的公式叫做蘊(yùn)涵。IF=>THEN前項后項(左式)(右式)例：RUNS(LIUHUA，F(xiàn)ASTEST)=>TWINS(LIUHUA，CHAMPION)(如果劉華跑得最快，那么他取得冠軍)非（NOT）表示否定，～、┑均可表示否定。例：～I(xiàn)NROOM(ROBOT，r2)(機(jī)器人不在2號房間內(nèi)。)第三十五頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

2.連詞和量詞(Connective&Quantifiers)

(2)量詞

全稱量詞(UniversalQuantifier)若一個原子公式P(x)，對于所有可能變量x都具有T值，則用(x)P(x)表示。例：(x)[ROBOT(x)=>COLOR(x,GRAY)](所有的機(jī)器人都是灰色的）(x)[Student(x)=>Uniform(x,Color)](所有學(xué)生都穿彩色制服)第三十六頁，共114頁。2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

2.連詞和量詞(Connective&Quantifiers)

(2)量詞

存在量詞(ExistentialQuantifier)

若一個原子公式P(x)，至少有一個變元X，可使P(X)為T值，則用(x)P(x)表示。例：(x)INROOM(x,r1)(1號房間內(nèi)有個物體)量化變元(QuantifiedVariables)被量化了的變元x-約束變量。第三十七頁，共114頁。2.3

謂詞邏輯法

2.3.2謂詞公式（PredicateFormulas）

1.謂詞公式的定義

原子謂詞公式：用P(x1,x2,…,xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,…xn為客體變量或變元。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。

分子謂詞公式：可以用連詞把原子謂詞公式組成復(fù)合謂詞公式，并把它叫做分子謂詞公式。

合適公式(WFF,well-formedformulas)的遞歸定義：

(1)原子謂詞公式是合適公式。

(2)若A為合適公式，則～A也是一個合適公式。

(3)若A和B都是合適公式，則(A∧B),(A∨B),(A=>B),(A←→B)也都是合適公式。

(4)若A是合適公式，x為A中的自由變元，則(x)A,(x)A都是合適公式。

(5)只有按上述規(guī)則(1)至(4)求得的那些公式，才是合適公式。第三十八頁，共114頁。2.3

謂詞邏輯法

2.3.2謂詞公式（PredicateFormulas）

1.謂詞公式的定義

例題："對于所有的x，如果x是整數(shù)，則x或為正的或者為負(fù)的。"(x)(I(x)=>(P(x)∨N(x)))I(x)表示"x是整數(shù)"，P(x)表示"x是正數(shù)"，N(x)表示"x是負(fù)數(shù)"。第三十九頁，共114頁。2.3

謂詞邏輯法

2.3.2謂詞公式（PredicateFormulas）

2.合適公式的性質(zhì)

合適公式的真值：p36表2-1真值表第四十頁，共114頁。2.3

謂詞邏輯法

2.3.3置換與合一（Substitution&Unification）

1.置換

在謂詞邏輯中，有些推理規(guī)則可應(yīng)用于一定的合適公式和合適公式集，以產(chǎn)生新的合適公式。一個重要的推理規(guī)則是假元推理，這就是由合適公式W1和W1=>W2產(chǎn)生合適公式W2的運(yùn)算。另一個推理規(guī)則叫做全稱化推理，它是由合適公式(x)W(x)產(chǎn)生合適公式W(A)，其中A為任意常量符號。

假元推理：

全稱化推理：

綜合推理：

第四十一頁，共114頁。2.3

謂詞邏輯法

2.3.3置換與合一（Substitution&Unification）

1.置換

置換：用項(A)替換函數(shù)表達(dá)式中的變量(x)，記為ES，即表示一個表達(dá)式E(Expression)用一個置換S(Substitution)而得到的表達(dá)式的置換。

例1表達(dá)式P[x,f(y),B]的4個置換為s1={z/x,w/y}s2={A/y}s3={q(z)/x,A/y}s4={c/x,A/y}我們用Es來表示一個表達(dá)式E用置換s所得到的表達(dá)式的置換。于是，我們可得到P[x,f(y),B]的4個置換的例，如下：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]

第四十二頁，共114頁。2.3

謂詞邏輯法

2.3.3置換與合一（Substitution&Unification）

2.性質(zhì)

可結(jié)合律(LS1)S2=L(S1S2)(L表示一表達(dá)式)(S1S2)S3=S1(S2S3)置換是可結(jié)合的。用s1s2表示兩個置換s1和s2的合成。L表示一表達(dá)式，則有(Ls1)s2=L(s1s2)以及(s1s2)s3=s1(s2s3)

即用s1和s2相繼作用于表達(dá)式L是同用s1s2作用于L一樣的。

一般說來，置換是不可交換的，即s1s2≠s2s13.合一(unification)P38合一：尋找項對變量的置換，以使兩表達(dá)式一致。

可合一：如果一個置換s作用于表達(dá)式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達(dá)式集{Ei}是可合一的。第四十三頁，共114頁。2.3

謂詞邏輯法2.3.3置換與合一（Substitution&Unification）

例:表達(dá)式集P[x,f(y),B],P[x,f(B),B]的合一者為:s={A/x,B/y}因為P[x,f(y),B]s=P[x,f(B),B]=P[A,f(B),B]

即s使表達(dá)式成為單一形式:P[A,f(B),B],但最簡單的合一者為:s’={B/Y}

第四十四頁，共114頁。2.4語義網(wǎng)絡(luò)法

語義網(wǎng)絡(luò)是1968年Quilian在研究人類聯(lián)想記憶時提出的心理學(xué)模型，認(rèn)為記憶是由概念間的聯(lián)系來實現(xiàn)的。1972年，Simmons首先將語義網(wǎng)絡(luò)表示法用于自然語言理解系統(tǒng)。

語義網(wǎng)絡(luò)的結(jié)構(gòu)：語義網(wǎng)絡(luò)是知識的一種圖解表示，它由節(jié)點(diǎn)和弧線或鏈線組成。節(jié)點(diǎn)用于表示實體、概念和情況等，弧線用于表示節(jié)點(diǎn)間的關(guān)系。組成部分:1詞法部分：決定表示詞匯表中允許有哪些符號，它涉及各個節(jié)點(diǎn)和弧線。2結(jié)構(gòu)部分：敘述符號排列的約束條件，指定各弧線連接的節(jié)點(diǎn)對。3過程部分：說明訪問過程，這些過程能用來建立和修正描述，以及回答相關(guān)問題。4語義部分：確定與描述相關(guān)的(聯(lián)想)意義的方法即確定有關(guān)節(jié)點(diǎn)的排列及其占有物和對應(yīng)弧線。第四十五頁，共114頁。2.4語義網(wǎng)絡(luò)法2.4.1二元語義網(wǎng)絡(luò)的表示(RepresentationofTwo-ElementSemanticNetwork)

1.表示簡單的事實

例1.所有的燕子都是鳥

第四十六頁，共114頁。2.4語義網(wǎng)絡(luò)法2.4.1二元語義網(wǎng)絡(luò)的表示(RepresentationofTwo-ElementSemanticNetwork)

2.表示占有關(guān)系和其它情況P40例2.小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。

3.選擇語義基元

試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復(fù)雜的知識。

第四十七頁，共114頁。第四十八頁，共114頁。2.4語義網(wǎng)絡(luò)法例3.我椅子的顏色是咖啡色的；椅子包套是皮革；椅子是一種家具；椅子是座位的一部分；椅子的所有者是X；X是個人，如下圖所示：

第四十九頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.2多元語義網(wǎng)絡(luò)的表示

語義網(wǎng)絡(luò)是一種網(wǎng)絡(luò)結(jié)構(gòu)。節(jié)點(diǎn)之間以鏈相連。多元語義網(wǎng)絡(luò)表示的實質(zhì)：把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。如果所要表示的知識是一元關(guān)系，例如，要表示李明是一個人，這在謂詞邏輯中可表示為MAN(LIMING)。用語義網(wǎng)絡(luò)，這就可以表示為:與這樣的表示法相等效的關(guān)系在謂詞邏輯中表示為ISA(LIMING，MAN)。這說明語義網(wǎng)絡(luò)可以毫無困難地表示一元關(guān)系。第五十頁，共114頁。2.4語義網(wǎng)絡(luò)法

例如：要表達(dá)北京大學(xué)(BEIJINGUniversity,簡稱BU)和清華大學(xué)(TSINGHUAUniversity,簡稱TU)兩?；@球隊在北大進(jìn)行的一場比賽的比分是85比89。若用謂詞邏輯可表示為SCORE(BU，TU，(85-89))。這個表示式中包含3項，而語義網(wǎng)絡(luò)從本質(zhì)上來說，只能表示二元關(guān)系。解決這個矛盾的一種方法是把這個多元關(guān)系轉(zhuǎn)化成一組二元關(guān)系的組合，或二元關(guān)系的合取。具體來說，多元關(guān)系R(X1，X2，…，Xn)總可以轉(zhuǎn)換成R1(X11，X12)∧R2(X21，X22)∧…∧Rn(Xn1,Xn2)圖2.20多元關(guān)系的語義網(wǎng)絡(luò)表示

第五十一頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

在語義網(wǎng)絡(luò)知識表達(dá)方法中，賦予網(wǎng)絡(luò)結(jié)構(gòu)的含義完全決定于管理這個網(wǎng)絡(luò)的過程的特性。為了便于以下的敘述，對所用符號作進(jìn)一步的規(guī)定。區(qū)分在鏈的頭部和在鏈的尾部的節(jié)點(diǎn)，把在鏈的尾部的節(jié)點(diǎn)稱為值節(jié)點(diǎn)。另外，我們還規(guī)定節(jié)點(diǎn)的槽相當(dāng)于鏈，不過取不同的名字而已。在圖2.28中磚塊12(BRICK12)有3個鏈，構(gòu)成兩個槽。其中一個槽只有一個值，另外一個槽有兩個值。我們說顏色槽(COLOR)填入紅色(RED)，ISA槽填入了磚塊(BRICK)和玩具(TOY)。圖2.28語義網(wǎng)絡(luò)的槽和數(shù)值第五十二頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

語義網(wǎng)絡(luò)中的推理過程主要有兩種:一種是繼承，另一種是匹配。以下我們分別介紹這兩種過程。

1.繼承

在語義網(wǎng)絡(luò)中所謂的繼承是把對事物的描述從概念節(jié)點(diǎn)或類節(jié)點(diǎn)傳遞到實例節(jié)點(diǎn)。例如在圖2.29上所示的語義網(wǎng)絡(luò)中BRICK是概念節(jié)點(diǎn)，BRICK12是一個實例節(jié)點(diǎn)。BRICK節(jié)點(diǎn)在SHAPE(外形)槽，其中填入了RECTANGULAR(矩形)，說明磚塊的外形是矩形的。這個描述可以通過ISA鏈傳遞給實例節(jié)點(diǎn)BRICK12。因此，雖然BRICK12節(jié)點(diǎn)沒有SHAPE槽，但可以從這個語義網(wǎng)絡(luò)推理出BRICK12的外形是矩形的。圖2.29語義網(wǎng)絡(luò)的值繼承第五十三頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

1.繼承

這種推理過程，類似于人的思維過程。一旦知道了某種事物的身份以后，可以聯(lián)想起很多關(guān)于這件事物的一般描述。例如，我們通常認(rèn)為鯨魚很大，鳥比較小，城堡很古老，運(yùn)動員很健壯。這就像我們用每種事物的典型情況來描述各種事物--鯨魚、鳥、城堡和運(yùn)動員--那樣。

一共有3種繼承過程：值繼承、"如果需要"繼承和"默認(rèn)"繼承。

第五十四頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

語義網(wǎng)絡(luò)中的推理過程主要有兩種:一種是繼承，另一種是匹配。以下我們分別介紹這兩種過程。

1.繼承

(1)值繼承

除了ISA鏈以外，另外還有一種AKO(是某種)鏈也可被用于語義網(wǎng)絡(luò)中的描述或特性的繼承。AKO是A-KIND-OF的縮寫。

總之，ISA和AKO鏈直接地表示類的成員關(guān)系以及子類和類之間的關(guān)系，提供了一種把知識從某一層傳遞到另一層的途徑。

為了能利用語義網(wǎng)絡(luò)的繼承特性進(jìn)行推理我們還需要一個搜索程序用來在合適的節(jié)點(diǎn)尋找合適的槽。

第五十五頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

1.繼承

(2)“如果需要”繼承

在某些情況下，當(dāng)我們不知道槽值時，可以利用已知信息來計算。例如，我們可以根據(jù)體積和物質(zhì)的密度來計算積木的重量。進(jìn)行上述計算的程序稱為if-needed(如果需要)程序。

為了儲存進(jìn)行上述計算的程序，我們需要改進(jìn)節(jié)點(diǎn)槽值的結(jié)構(gòu)，允許槽有幾種類型的值，而不只是一個類型。為此，每個槽又可以有若干個側(cè)面，以儲存這些不同類型的值。這樣，以前我們討論的原始意義上的值就放“值側(cè)面”中，if-needed程序，存放在IF-NEEDED側(cè)面中。

例如在圖2.30(a)中，一個重量確定程序存放在BLOCK節(jié)點(diǎn)的WEIGHT槽的IF-NEEDED側(cè)面中。第五十六頁，共114頁。圖2.30語義網(wǎng)絡(luò)的"如果需要"繼承第五十七頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

1.繼承

(3)“缺省”繼承

某些情況下，當(dāng)我們對事物所作的假設(shè)不是十分有把握時，最好對所作的假設(shè)加上“可能”這樣的字眼。例如，我們可以認(rèn)為法官可能是誠實的，但不一定是；或認(rèn)為寶石可能是很昂貴的，但不一定是。

我們把這種具有相當(dāng)程度的真實性，但又不能十分肯定的值稱為“缺省”值。這種類型的值被放入槽的DEFAULT(缺省)側(cè)面中.例如，在圖2.31中，網(wǎng)絡(luò)所表示的含義是：從整體來說，積木的顏色很可能是藍(lán)色的，但在磚塊中，顏色可能是紅的。對BLOCK和BRICK節(jié)點(diǎn)來說，在COLOR槽中找到的側(cè)面都是DEFAULT側(cè)面，在圖中以括弧加以標(biāo)志圖2.31語義網(wǎng)絡(luò)的"缺省"繼承第五十八頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

2.匹配

至今我們所討論的是類節(jié)點(diǎn)和實例節(jié)點(diǎn)，例如BRICK和BRICK12之間的繼承值。現(xiàn)在我們轉(zhuǎn)向討論更為困難一些的問題。當(dāng)解決涉及由幾部分組成的事物時，如圖2.32中的玩具房(TOY-HOUSE)和玩具房-77(TOY-HOUSE77)，繼承過程將如何進(jìn)行。我們不僅必須制定如何把值從玩具房傳遞到玩具房-77的路徑，而且必須制定把值從玩具房部件傳遞到玩具房-77部件的路徑。

第五十九頁，共114頁。

例如，很明顯，由于TOY-HOUSE77是TOY-HOUSE的一個實例，所以它必須有兩個部件，一個是磚塊，另一個是楔塊(wedge)。另外，作為玩具房的一個部件的磚塊必須支撐楔塊。在圖2.32中，玩具房-77部件以及它們之間的鏈，都用虛線畫的節(jié)點(diǎn)的箭頭來表示。因為這些知識是通過繼承而間接知道的，并不是通過實際的節(jié)點(diǎn)和鏈直接知道的。因此，我們說虛線所表示的節(jié)點(diǎn)和箭頭表示的鏈?zhǔn)翘摴?jié)點(diǎn)和虛鏈。圖2.32虛節(jié)點(diǎn)和虛鏈

第六十頁，共114頁。圖2.32虛節(jié)點(diǎn)和虛鏈

沒有必要從TOYHOUSE節(jié)點(diǎn)把這些節(jié)點(diǎn)和鏈復(fù)制到TOY-HOUSE77節(jié)點(diǎn)去，除非我們需要在這些復(fù)制節(jié)點(diǎn)加上玩具房-77所特有的信息。例如，如果我們要表示玩具房-77的磚塊的顏色是紅的，就必須為TOY-HOUSE77建立一個BRICK節(jié)點(diǎn)，并把RED放在這個BRICK節(jié)點(diǎn)的COLOR槽中。假設(shè)我們把RED放在作為玩具房部件的BRICK節(jié)點(diǎn)的COLOR槽中，這將意味著所有玩具房的磚都是紅色的，而不是只在由玩具房-77所描述的特定房子中的磚是紅色的。第六十一頁，共114頁。2.4語義網(wǎng)絡(luò)法

2.4.3語義網(wǎng)絡(luò)的推理過程

現(xiàn)在我們來研究圖2.33中的結(jié)構(gòu)35(STRUCTURE35)。已知這個結(jié)構(gòu)有兩個部件，一個磚塊BRICK12和一個楔塊WEDGE18。一旦在STRUCTURE35和TOY-HOUSE之間放上ISA鏈，我們就知道BRICK12必須支撐WEDGE18。在圖2.18上用虛線箭頭表示BRICK12和WEDGE18之間的SUPPORT虛鏈。因為很容易做部件匹配，所以虛線箭頭的位置和方向很容易確定。WEDGE18肯定和作為TOY-HOUSE的一個部件的楔塊相匹配，而BRICK12肯定和磚塊相匹配。圖2.33部件匹配第六十二頁，共114頁。2.5框架表示法心理學(xué)的研究結(jié)果表明，在人類日常的思維和理解活動中，當(dāng)分析和解釋遇到的新情況時，要使用到過去經(jīng)驗中積累的知識。這些知識規(guī)模巨大而且以很好的組織形式保留在人們的記憶中。例如:當(dāng)我們走進(jìn)一家從來沒來過的飯店時，根據(jù)以往的經(jīng)驗，可以預(yù)見在這家飯店我們將會看到菜單、桌子、服務(wù)員等等。當(dāng)我們走進(jìn)教室時，可以預(yù)見在教室里可以看到椅子、黑板等等。我們試圖用以往的經(jīng)驗來分析解釋當(dāng)前所遇到的情況。第六十三頁，共114頁。2.5框架表示法當(dāng)然，我們無法把過去的經(jīng)驗一一都存在腦子里，而只能以一個通用的數(shù)據(jù)結(jié)構(gòu)的形式存儲以往的經(jīng)驗。這樣的數(shù)據(jù)結(jié)構(gòu)稱為框架?？蚣芴峁┝艘粋€結(jié)構(gòu)，一種組織。在這個結(jié)構(gòu)或組織中，新的資料可以用從過去的經(jīng)驗中得到的概念來分析和解釋。因此，框架是一種結(jié)構(gòu)化表示法。

通常框架采用語義網(wǎng)絡(luò)中的節(jié)點(diǎn)-槽-值表示結(jié)構(gòu)。所以框架也可以定義為是一組語義網(wǎng)絡(luò)的節(jié)點(diǎn)和槽，這組節(jié)點(diǎn)和槽可以描述格式固定的事物、行動和事件。語義網(wǎng)絡(luò)可看做節(jié)點(diǎn)和弧線的集合，也可以視為框架的集合。

第六十四頁，共114頁。2.5框架表示法2.5.1框架的構(gòu)成

框架通常由描述事物的各個方面的槽組成，每個槽可以擁有若干個側(cè)面，而每個側(cè)面又可以擁有若干個值。這些內(nèi)容可以根據(jù)具體問題的具體需要來取舍，一個框架的一般結(jié)構(gòu)如下：

<框架名>

<槽1><側(cè)面11><值111>…<側(cè)面12><值121>……

<槽2><側(cè)面21><值211>…

…

…

<槽n><側(cè)面n1><值n11>…

…

<側(cè)面nm><值nm1>…

第六十五頁，共114頁。2.5框架表示法2.5.1框架的構(gòu)成較簡單的情景是用框架來表示諸如人和房子等事物。例如，一個人可以用其職業(yè)、身高和體重等項描述，因而可以用這些項目組成框架的槽。當(dāng)描述一個具體的人時，再用這些項目的具體值填入到相應(yīng)的槽中。表2.3給出的是描述John的框架。

對于大多數(shù)問題，不能這樣簡單地用一個框架表示出來，必須同時使用許多框架,組成一個框架系統(tǒng)。表2.3簡單框架示例JOHN的描述框架第六十六頁，共114頁。2.5框架表示法一個框架系統(tǒng)

圖2.32所示的就是表示立方體的一個視圖的框架。圖中，最高層的框架，用isa槽說明它是一個立方體，并由region槽指示出它所擁有的3個可見面A、B、E。而A、B、E又分別用3個框架來具體描述。用mustbe槽指示出它們必須是一個平行四邊形。

圖2.32一個立體視圖的框架表示第六十七頁，共114頁。2.5框架表示法一個框架系統(tǒng)

為了能從各個不同的角度來描述物體，可以對不同角度的視圖分別建立框架，然后再把它們聯(lián)系起來組成一個框架系統(tǒng)。圖2.35所示的就是從3個不同的角度來研究一個立方體的例子。為了簡便起見，圖中略去了一些細(xì)節(jié)，在表示立方體表面的槽中，用實線與可見面連接，用虛線與不可見面連接。

圖2.35表示立方體的框架系統(tǒng)第六十八頁，共114頁。2.5框架表示法以下是另一個框架系統(tǒng)的例子

"今天一次強(qiáng)度為里氏8.5級的強(qiáng)烈地震襲擊了下斯洛文尼亞(LowSlabovia)地區(qū)，造成25人死亡和5億美元的財產(chǎn)損失。下斯洛文尼亞地區(qū)主席說，多年來，靠近薩迪豪金斯斷層的重災(zāi)區(qū)一直是一個危險地區(qū)。可以用圖2.36中虛線部分所示的EARTHQUAKE13框架來表示這一新聞。圖2.36表示災(zāi)害事件的框架系統(tǒng)

第六十九頁，共114頁。

圖中在鏈上標(biāo)明的地點(diǎn)(place)、日期(day)、傷亡(fatalities)、損失(damage)、震級(magnitude)、斷層(fault)是槽的名稱。在節(jié)點(diǎn)中填入相應(yīng)的填充值。

這個框架可以發(fā)展成框架系統(tǒng)，以描述更復(fù)雜更廣泛的事件。例如，向上移動一層的話，可以把地震看成是一種災(zāi)害事件(disasterevent)，除此之外還可以有洪水(flood)、颶風(fēng)(huricane)等災(zāi)害事件、它們組成一個DISASTEREVENT的基本框架。如向下移動一層，在每個槽中也可以填入一個框架。例如FATALITIES、也可以用一個框架來描述。

第七十頁，共114頁。2.5框架表示法

顯而易見，這種框架系統(tǒng)具有樹狀結(jié)構(gòu)。樹狀結(jié)構(gòu)框架系統(tǒng)的每個節(jié)點(diǎn)具有如下框架結(jié)構(gòu)形式：框架名AKOVALUE<值>PROPDEFAULT<表1>SFIF-NEEDED<算術(shù)表達(dá)式>CONFLICTADD<表2>其中框架名用類名表示。AKO是一個槽，VALUE是它的側(cè)面，通過填寫<值>的內(nèi)容表示出該框架屬于哪一類。PROP槽用來記錄該節(jié)點(diǎn)所具有的特性，其側(cè)面DEFAULT表示該槽的內(nèi)容是可以進(jìn)行缺省繼承的，即當(dāng)<表1>為非NIL時，PROP的槽值為<表1>，當(dāng)<表1>為NIL時，PROP的槽值用其父節(jié)點(diǎn)的PROP槽值來代替。第七十一頁，共114頁。2.5框架表示法2.5.2框架的推理

框架是一種復(fù)雜結(jié)構(gòu)的語義網(wǎng)絡(luò)。因此語義網(wǎng)絡(luò)推理中的匹配和特性繼承在框架系統(tǒng)中也可以實行。除此以外，由于框架用于描述具有固定格式的事物、動作和事件，因此可以在新的情況下，推論出未被觀察到的事實?？蚣苡靡韵聨追N途徑來幫助實現(xiàn)這一點(diǎn)：

(1)框架包含它所描述的情況或物體的多方面的信息。這些信息可以被引用，就像已經(jīng)直接觀察到這些信息一樣。(2)框架包含物體必須具有的屬性。在填充框架的各個槽時，要用到這些屬性。

(3)框架描述它們所代表的概念的典型事例。如果某一情況在很多方面和一個框架相匹配，只有少部分相互之間存在不同之處。這些不同之處很可能對應(yīng)于當(dāng)前情況的重要方面，也許應(yīng)該對這些不同之處作出解答。因此，如果一個椅子被認(rèn)為應(yīng)有4條腿，而某一椅子只有3條腿，那么或許這把椅子需要修理。

第七十二頁，共114頁。2.5框架表示法2.5.2框架的推理

用一個框架來具體體現(xiàn)一個特定情況的過程，經(jīng)常不是很順利的。但當(dāng)這個過程碰到障礙時，經(jīng)常不必放棄原來的努力去從頭開始，而是有很多辦法可想的：(1)選擇和當(dāng)前情況相對應(yīng)的當(dāng)前的框架片斷，并把這個框架片斷和候補(bǔ)框架相匹配。選擇最佳匹配。如果當(dāng)前的框架，總的來說差不多是可以接受的，則許多已經(jīng)做的，有關(guān)建立子結(jié)構(gòu)以填入這個框架的工作將可保留。(2)盡管當(dāng)前的框架和要描述的情況之間有不相匹配的地方，但是仍然可以繼續(xù)應(yīng)用這個框架。例如，所研究的只有3條腿的椅子，可能是一個破椅子或是有另一個在椅子前面的物體擋住了一條腿。框架的某一部分包含關(guān)于哪些特性是允許不相匹配的信息。同樣的，也有一般的啟發(fā)性原則，比如一個漏失某項期望特性的框架(可能由于被擋住視線造成的)比另一個多了某一項不應(yīng)有的特性的框架更適合當(dāng)前的情況。舉例來說，一個人只有一條腿比說一個人有3條腿或有尾巴更合乎情理些。

第七十三頁，共114頁。2.5框架表示法2.5.2框架的推理

(3)查詢框架之間專門保存的鏈，以提出應(yīng)朝哪個方向進(jìn)行試探的建議。這種鏈的例子與圖2.35所示網(wǎng)絡(luò)相似。例如，如果和CHAIR框架匹配時，發(fā)現(xiàn)沒有靠背，并且太寬，這時就建議用BENCH(條凳)框架；如果太高，并且沒有靠背，就建議用STOOL(凳子)框架。圖2.37相似網(wǎng)絡(luò)第七十四頁，共114頁。2.5框架表示法2.5.2框架的推理

(4)沿著框架系統(tǒng)排列的層次結(jié)構(gòu)向上移動(即從狗框架→哺乳動物框架→動物框架)，直到找到一個足夠通用，并不與已有事實矛盾的框架。如果框架足夠具體，可以提供所要求的知識，那就采用這個框架。或者建立一個新的、正好在匹配的框架下一層的框架。

第七十五頁，共114頁。2.6劇本(script)表示

劇本是框架的一種特殊形式，它用一組槽來描述某些事件的發(fā)生序列，就像劇本中的事件序列一樣，故稱為"劇本"。

2.6.1劇本的構(gòu)成

一個劇本一般由以下各部分組成：

(1)開場條件給出在劇本中描述的事件發(fā)生的前提條件。

(2)角色用來表示在劇本所描述的事件中可能出現(xiàn)的有關(guān)人物的一些槽。

(3)道具這是用來表示在劇本所描述的事件中可能出現(xiàn)的有關(guān)物體的一些槽。

(4)場景描述事件發(fā)生的真實順序，可以由多個場景組成，每個場景又可以是其它的劇本。

(5)結(jié)果給出在劇本所描述的事件發(fā)生以后通常所產(chǎn)生的結(jié)果。

第七十六頁，共114頁。2.6劇本(script)表示

劇本是框架的一種特殊形式，它用一組槽來描述某些事件的發(fā)生序列，就像劇本中的事件序列一樣，故稱為“劇本”。

2.6.1劇本的構(gòu)成

下面以餐廳劇本為例說明劇本各個部分的組成。

(1)開場條件

(a)顧客餓了，需要進(jìn)餐。(b)顧客有足夠的錢(2)角色

顧客，服務(wù)員，廚師，老板。

(3)道具

食品，桌子，菜單，錢。

第七十七頁，共114頁。2.6劇本(script)表示

2.6.1劇本的構(gòu)成(4)場景

場景1進(jìn)入餐廳

(a)顧客走入餐廳。(b)尋找桌子。

(c)在桌子旁坐下。

場景2點(diǎn)菜

(a)服務(wù)員給顧客菜單。(b)顧客點(diǎn)菜。

(c)顧客把菜單還給服務(wù)員。(d)顧客等待服務(wù)員送菜。場景3等待

(a)服務(wù)員把顧客所點(diǎn)的菜告訴廚師。(b)廚師做菜。場景4吃菜

(a)廚師把做好的菜給服務(wù)員。(b)服務(wù)員給顧客送菜。

(c)顧客吃菜。

場景5離開

(a)服務(wù)員拿來帳單。(b)顧客付錢給服務(wù)員。

(c)顧客離開餐廳。

第七十八頁，共114頁。2.6劇本(script)表示

2.6.1劇本的構(gòu)成

(5)結(jié)果

(a)顧客吃了飯，不餓了。(b)顧客花了錢。

(c)老板掙了錢。(d)餐廳食品少了。第七十九頁，共114頁。2.6劇本(script)表示

2.6.2劇本的推理

劇本是有用的知識表達(dá)結(jié)構(gòu)，因為在現(xiàn)實世界中事件發(fā)生的某種模式來自事件之間的因果關(guān)系。事件中的主人公完成一個動作后才能完成另一個動作。劇本中所描述的事件形成一個巨大的因果鏈，這個鏈的起點(diǎn)是一組開場條件，滿足這些開場條件，劇本中的事件才能產(chǎn)生。鏈的終點(diǎn)是一組結(jié)果，有了這組結(jié)果，以后的事件或事件序列(可能用其他的劇本來描述)才能發(fā)生。在這個鏈內(nèi)一件事情和前后的事情都相互聯(lián)系。前面的事件，使當(dāng)前的事件有可能產(chǎn)生，而當(dāng)前事件又使后面的事件有可能產(chǎn)生。第八十頁，共114頁。2.6劇本(script)表示

2.6.2劇本的推理

如已知某一劇本適用于所給定的情形，劇本在預(yù)言一些沒有直接提到的事件方面特別有用。同時劇本對表示已經(jīng)提到的事件之間的關(guān)系也很有用。例如，要表示某人點(diǎn)了燉牛肉這道菜和此人吃牛肉之間是什么聯(lián)系，就可以利用劇本。但在應(yīng)用某一劇本以前，必須先準(zhǔn)備好劇本，也就是先要確定這個劇本適用于當(dāng)前的情形。根據(jù)劇本的重要性，可以有二種準(zhǔn)備劇本的方法。

(1)對于不屬于事件核心部分的劇本，只需設(shè)置指向該劇本的指針即可，以便當(dāng)它成為核心時啟用，如對于餐廳劇本，在下述事件中應(yīng)采用這種方法：

蘇珊在去博物館的路上經(jīng)過她喜歡的餐廳。她非常喜歡這次的畢加索作品展覽會。

(2)對于符合事件核心部分的劇本，則應(yīng)使用在當(dāng)前事件中涉及到的具體對象和人物去填寫劇本的槽。劇本的前提、道具、角色和事件等常能起到啟用劇本的指示器的作用。

一旦劇本被啟用，則可以應(yīng)用它來進(jìn)行推理。其中最重要的是運(yùn)用劇本可以預(yù)測沒有明顯提及的事件的發(fā)生。

第八十一頁，共114頁。2.6劇本(script)表示

2.6.2劇本的推理

例如，對于以下情節(jié)：

"昨晚，約翰到了餐廳。他訂了牛排。當(dāng)他要付款時發(fā)現(xiàn)錢已用光。因為開始下雨了，所以他趕緊回家了"。

如果有人提問：

"昨晚，約翰吃飯了嗎?"

雖然在上面的情節(jié)中并沒有提到約翰吃沒吃飯的問題，但借助于餐廳劇本，可以回答：“他吃了。”這是因為啟用了餐廳劇本，情節(jié)中的所有事件與劇本中所預(yù)測的事件序列相對應(yīng)，因而可以推斷出整個事件正常進(jìn)行時所得出的結(jié)果。

但是，一旦一個典型的事件被中斷，也就是給定情節(jié)中的某個事件與劇本中的事件不能對應(yīng)時，則劇本便不能預(yù)測被中斷以后的事件了。第八十二頁，共114頁。2.6劇本(script)表示

2.7.2劇本的推理

例如如下情節(jié)：

“約翰走進(jìn)餐廳。他被帶到餐桌旁。訂了一大塊牛排之后，他坐在那兒等了許久。于是，他生氣地走了。”

該情節(jié)中，因為要久等，所以約翰走了，這一事件改變了餐廳劇本中所預(yù)測的事件序列，因而被中斷了，這時就不能推斷約翰是否付了帳等情節(jié)，但仍然可以推斷出他看了菜單，這是因為看菜單事件發(fā)生在中斷之前。從該例也可以看出，利用劇本可以將事情的注意力集中在“因為久等，約翰生氣了”這樣一些特殊事件的發(fā)生上。

劇本結(jié)構(gòu)，比起框架這樣的一些通用結(jié)構(gòu)來，要呆板得多，知識表達(dá)的范圍也很窄，因此不適用于表達(dá)各種知識，但對于表達(dá)預(yù)先構(gòu)思好的特定知識，如理解故事情節(jié)等，是非常有效的。第八十三頁，共114頁。2.7過程(procedure)表示

過程式表示就是將有關(guān)某一問題領(lǐng)域的知識，連同如何使用這些知識的方法，均隱式地表達(dá)為一個求解問題的過程。過程式不像陳述式那樣具有固定的形式，如何描述知識完全取決于具體的問題。下面以八數(shù)碼問題為例，給出一種求解該問題的過程式描述。

我們用一個3×3的方格陣來表示該問題的一個狀態(tài)，為敘述上的方便，我們用a～i來標(biāo)記這9個方格，如圖2.38(a)所示。問題的目標(biāo)狀態(tài)設(shè)定為圖2.38(b)。當(dāng)任意給定一初始狀態(tài)后，求解該問題的過程如下：

圖2.38狀態(tài)的描述及其目標(biāo)狀態(tài)第八十四頁，共114頁。2.7過程(procedure)表示

(1)首先移動棋牌，使得棋子1和空格均不在位置c上。

(2)依次移動棋牌，使得空格位置沿圖2.39(a)所示的箭頭方向移動，直到棋子1位于a為止。

(3)依次移動將牌，使得空格位置沿圖2.39(b)所示的箭頭方向移動，直到數(shù)碼2位于b為止。若這時剛好數(shù)碼3在位置c，則轉(zhuǎn)(6)。圖2.39空格移動方向示意圖

第八十五頁，共114頁。2.7過程(procedure)表示

(4)依次移動將牌，使得空格位置沿圖2.39(c)所示的箭頭方向移動，直到數(shù)碼3位于e為止。這時空格剛好在位置d。

經(jīng)過以上4步，得到的狀態(tài)如圖2.40(a)所示。其中"×"表示除空格以外的任何將牌。

(5)依次移動將牌，使得空格位置沿圖2.39(d)所示的箭頭方向移動，直到空格又回到了d為止。此時狀態(tài)如圖2.40(b)所示。

(6)依次移動將牌，使得空格位置沿圖2.39(e)所示的箭頭方向移動，直到數(shù)碼4在位置f為止。若這時剛好數(shù)碼5在位置i則轉(zhuǎn)(9)。第八十六頁，共114頁。2.7過程(procedure)表示

(7)依次移動將牌，使得空格位置沿圖2.39(f)所示的箭頭方向移動，直到數(shù)碼5位于e為止。這時空格剛好在位置d。

(8)依次移動將牌，使得空格位置沿圖2.39(g)所示的箭頭方向移動，直到空格又回到位置d為止。

(9)依次移動將牌，使得空格位置沿圖2.39(h)所示的箭頭方向移動，直到數(shù)碼6在位置h為止，若這時數(shù)碼7、8分別在位置g和d，則問題得解，否則，說明由所給初始狀態(tài)達(dá)不到所要求的目標(biāo)狀態(tài)。

第八十七頁，共114頁。2.7過程(procedure)表示

圖2.41給出了應(yīng)用以上過程求解一個具體的八數(shù)碼問題的例子，其中(1)～(9)9個狀態(tài)分別對應(yīng)了以上過程的(1)～(9)9個步驟結(jié)束時所達(dá)到的狀態(tài)。

從圖2.41可以看出，這樣得到的解路顯然不是最佳的，但是按這樣的一種過程編寫的計算機(jī)程序具有非常高的求解效率.

第八十八頁，共114頁。2.8小結(jié)本章所討論的知識表示問題是人工智能研究的核心問題之一。知識表示方法很多，本章介紹了其中的7種，有圖示法和公式法，陳述式表示和過程式表示等。

狀態(tài)空間法是一種基于解答空間的問題表示和求解方法，它是以狀態(tài)和操作符為基礎(chǔ)的。在利用狀態(tài)空間圖表示時，我們從某個初始狀態(tài)開始，每次加一個操作符，遞增地建立起操作符的試驗序列，直到達(dá)到目標(biāo)狀態(tài)為止。由于狀態(tài)空間法需要擴(kuò)展過多的節(jié)點(diǎn)，容易出現(xiàn)"組合爆炸"，因而只適用于表示比較簡單的問題。

問題歸約法從目標(biāo)(要解決的問題)出發(fā)，逆向推理，通過一系列變換把初始問題變換為子問題集合和子-子問題集合，直至最后歸約為一個平凡的本原問題集合。這些本原問題的解可以直接得到從而解決了初始問題，用與或圖來有效地說明問題歸約法的求解途徑。

第八十九頁，共114頁。2.8小結(jié)第九十頁，共114頁。2.8小結(jié)

謂詞邏輯法采用謂詞合適公式和一階謂詞演算把要解決的問題變?yōu)橐粋€有待證明的問題，然后采用消解定理和消解反演來證明一個新語句是從已知的正確語句導(dǎo)出的，從而證明這個新語句也是正確的。

語義網(wǎng)絡(luò)是知識的一種圖解表示，它由節(jié)點(diǎn)和弧線或鏈線組成。節(jié)點(diǎn)用于表示實體、概念和情況等，弧線用于表示節(jié)點(diǎn)間的關(guān)系。

框架是一種結(jié)構(gòu)化表示方法。框架通常由指定事物各個方面的槽組成，每個槽擁有若干個側(cè)面，而每個側(cè)面又可擁有若干個值。大多數(shù)實用系統(tǒng)必須同時使用許多框架，并可把它們聯(lián)成一個框架系