人工智能及其應用知識

第二章知識表示

本章主要討論知識表示問題，介紹7種知識表示方法：狀態(tài)空間法、問題歸約法、謂詞演算法、語義網絡法、框架表示、本體技術、過程表示。

掌握狀態(tài)空間法、問題歸約法、謂詞演算法、語義網絡法的要點及其之間的關系，了解框架表示、本體技術、過程表示。?知識表示的基本概念

知識表示：研究用機器表示知識的可行性、有效性的一般方法，是一種數據結構與控制結構的統(tǒng)一體，既考慮知識的存儲又考慮知識的使用。知識表示可看成是一組描述事物的約定，以把人類知識表示成機器能處理的數據結構。?人工智能系統(tǒng)所關心的知識事實

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

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

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

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

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

(1)狀態(tài)（state）(2)算符（operator）(3)狀態(tài)空間方法?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ī)則、數學算子、運算符號或邏輯符號等。問題的狀態(tài)空間(statespace)：是一個表示該問題全部可能狀態(tài)及其關系的圖，它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標狀態(tài)集合G?？砂褷顟B(tài)空間記為三元狀態(tài)(S，F(xiàn)，G)。?2.1狀態(tài)空間法2.狀態(tài)空間表示詳釋

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

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

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

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

1.圖論中的幾個術語

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

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

1.圖論中的幾個術語

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

2.圖的顯式和隱式表示

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

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

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

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

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

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

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

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

其中

W－猴子的水平位置

X－當猴子在箱子頂上時取X=1；否則取X=0

Y－箱子的水平位置

Z－當猴子摘到香蕉時取Z=1；否則取Z=0

圖2.4猴子和香蕉問題?2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

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

(1)goto(U)猴子走到水平位置U，或者用產生式規(guī)則表示為：(W，0，Y，z)(U，0，Y，z)(2.3)即應用操作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)應當注意的是，要應用算符pushbox(V)，就要求產生式規(guī)則的左邊，猴子與箱子必須在同一位置上，并且，猴子不是在箱子頂上。這種強加于操作的適用性條件，叫做產生式規(guī)則的先決條件。

?2.1狀態(tài)空間法2.1.2狀態(tài)圖示法

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

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

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

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

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

2.2.1問題歸約描述

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

?2.2問題歸約法

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

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

解題過程：

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

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

圖2.7梵塔問題解答(a)圖2.8梵塔問題解答(b)圖2.9梵塔問題解答(c)?2.2問題歸約法

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

它能有效地說明如何由問題歸約法求得問題的解答。梵塔問題歸約圖?2.2問題歸約法

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

2.2.2與或圖表示

與圖、或圖、與或圖：

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

?2.2問題歸約法

2.2.2問題歸約描述

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

?2.2問題歸約法

2.2.2問題歸約描述

與或圖：由與節(jié)點及或節(jié)點組成的結構圖?？山夤?jié)點的一般定義：

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

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

(3)如果某個非終葉節(jié)點含有與后繼節(jié)點，那么只有當其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。圖2.15與或圖例子?2.2問題歸約法

2.2.2問題歸約描述

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

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

?2.2問題歸約法

2.2.2問題歸約描述

與或圖構成規(guī)則

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

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

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

圖2.16與或樹?2.2問題歸約法

2.2.2問題歸約描述

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

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

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

圖2.16與或樹?2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

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

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

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

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

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

又如,“李的母親和他的父親結婚”這句話的原子公式表示如下：?2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

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

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

?2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

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

?2.3

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

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

(1)連詞

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

謂詞邏輯法

2.3.1謂詞演算（PredicateCalculus）

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

(2)量詞

全稱量詞(UniversalQuantifier)若一個原子公式P(x)，對于所有可能變量x都具有T值，則用(x)P(x)表示。例：(x)[ROBOT(x)=>COLOR(x,GRAY)](所有的機器人都是灰色的）(x)[Student(x)=>Uniform(x,Color)](所有學生都穿彩色制服)?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號房間內有個物體)量化變元(QuantifiedVariables)被量化了的變元x-約束變量。?2.3

謂詞邏輯法

2.3.2謂詞公式（PredicateFormulas）

1.謂詞公式的定義

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

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

合適公式(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)求得的那些公式，才是合適公式。?2.3

謂詞邏輯法

2.3.2謂詞公式（PredicateFormulas）

1.謂詞公式的定義

例題："對于所有的x，如果x是整數，則x或為正的或者為負的。"(x)(I(x)=>(P(x)∨N(x)))I(x)表示"x是整數"，P(x)表示"x是正數"，N(x)表示"x是負數"。?2.3

謂詞邏輯法

2.3.2謂詞公式（PredicateFormulas）

2.合適公式的性質

合適公式的真值：p36表2-1真值表?2.3

謂詞邏輯法

2.3.3置換與合一（Substitution&Unification）

1.置換

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

假元推理：

全稱化推理：

綜合推理：

?2.3

謂詞邏輯法

2.3.3置換與合一（Substitution&Unification）

1.置換

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

例1表達式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來表示一個表達式E用置換s所得到的表達式的置換。于是，我們可得到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]

?2.3

謂詞邏輯法

2.3.3置換與合一（Substitution&Unification）

2.性質

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

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

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

可合一：如果一個置換s作用于表達式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達式集{Ei}是可合一的。?2.3

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

例:表達式集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使表達式成為單一形式:P[A,f(B),B],但最簡單的合一者為:s’={B/Y}

?2.4語義網絡法

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

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

1.表示簡單的事實

例1.所有的燕子都是鳥

?2.4語義網絡法2.4.1二元語義網絡的表示(RepresentationofTwo-ElementSemanticNetwork)

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

3.選擇語義基元

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

??2.4語義網絡法例3.我椅子的顏色是咖啡色的；椅子包套是皮革；椅子是一種家具；椅子是座位的一部分；椅子的所有者是X；X是個人，如下圖所示：

?2.4語義網絡法

2.4.2多元語義網絡的表示

語義網絡是一種網絡結構。節(jié)點之間以鏈相連。多元語義網絡表示的實質：把多元關系轉化為一組二元關系的組合，或二元關系的合取。如果所要表示的知識是一元關系，例如，要表示李明是一個人，這在謂詞邏輯中可表示為MAN(LIMING)。用語義網絡，這就可以表示為:與這樣的表示法相等效的關系在謂詞邏輯中表示為ISA(LIMING，MAN)。這說明語義網絡可以毫無困難地表示一元關系。?2.4語義網絡法

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

?2.4語義網絡法

2.4.3語義網絡的推理過程

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

2.4.3語義網絡的推理過程

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

1.繼承

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

2.4.3語義網絡的推理過程

1.繼承

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

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

?2.4語義網絡法

2.4.3語義網絡的推理過程

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

1.繼承

(1)值繼承

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

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

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

?2.4語義網絡法

2.4.3語義網絡的推理過程

1.繼承

(2)“如果需要”繼承

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

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

例如在圖2.30(a)中，一個重量確定程序存放在BLOCK節(jié)點的WEIGHT槽的IF-NEEDED側面中。?圖2.30語義網絡的"如果需要"繼承?2.4語義網絡法

2.4.3語義網絡的推理過程

1.繼承

(3)“缺省”繼承

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

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

2.4.3語義網絡的推理過程

2.匹配

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

?

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

?圖2.32虛節(jié)點和虛鏈

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

2.4.3語義網絡的推理過程

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

通?？蚣懿捎谜Z義網絡中的節(jié)點-槽-值表示結構。所以框架也可以定義為是一組語義網絡的節(jié)點和槽，這組節(jié)點和槽可以描述格式固定的事物、行動和事件。語義網絡可看做節(jié)點和弧線的集合，也可以視為框架的集合。

?2.5框架表示法2.5.1框架的構成

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

<框架名>

<槽1><側面11><值111>…<側面12><值121>……

<槽2><側面21><值211>…

…

…

<槽n><側面n1><值n11>…

…

<側面nm><值nm1>…

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

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

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

圖2.32一個立體視圖的框架表示?2.5框架表示法一個框架系統(tǒng)

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

圖2.35表示立方體的框架系統(tǒng)?2.5框架表示法以下是另一個框架系統(tǒng)的例子

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

?

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

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

?2.5框架表示法

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

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

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

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

?2.5框架表示法2.5.2框架的推理

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

?2.5框架表示法2.5.2框架的推理

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

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

?2.6劇本(script)表示

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

2.6.1劇本的構成

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

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

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

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

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

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

?2.6劇本(script)表示

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

2.6.1劇本的構成

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

(1)開場條件

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

顧客，服務員，廚師，老板。

(3)道具

食品，桌子，菜單，錢。

?2.6劇本(script)表示

2.6.1劇本的構成(4)場景

場景1進入餐廳

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

(c)在桌子旁坐下。

場景2點菜

(a)服務員給顧客菜單。(b)顧客點菜。

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

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

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

(c)顧客吃菜。

場景5離開

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

(c)顧客離開餐廳。

?2.6劇本(script)表示

2.6.1劇本的構成

(5)結果

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

(c)老板掙了錢。(d)餐廳食品少了。?2.6劇本(script)表示

2.6.2劇本的推理

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

2.6.2劇本的推理

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

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

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

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

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

?2.6劇本(script)表示

2.6.2劇本的推理

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

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

如果有人提問：

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

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

但是，一旦一個典型的事件被中斷，也就是給定情節(jié)中的某個事件與劇本中的事件不能對應時，則劇本便不能預測被中斷以后的事件了。?2.6劇本(script)表示

2.7.2劇本的推理

例如如下情節(jié)：

“約翰走進餐廳。他被帶到餐桌旁。訂了一大塊牛排之后，他坐在那兒等了許久。于是，他生氣地走了?！?/p>

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

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

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

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

圖2.38狀態(tài)的描述及其目標狀態(tài)?2.7過程(procedure)表示

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

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

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

?2.7過程(procedure)表示

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

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

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

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

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

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

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

?2.7過程(procedure)表示

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

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

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

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

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

?2.8小結?2.8小結

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

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

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

劇本是框架的一種特殊形式，它使用一組槽來描述事件的發(fā)生序列。本體技術特別適用于描述順序性動作或事件，但使用不如框架靈活，因此應用范圍也不如框架那么廣泛。

過程是一種知識的過程式表示，它將某一有關問題領域知識同這些使用方法一起，隱式地表示為一個問題求解過程。過程表示用程序來描述問題，具有很高的問題求解效率。由于知識隱含在程序中難以操作，所以適用范圍較窄。?作業(yè)1用謂詞公式表示下列句子（1）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。

（2）他每天下午都去打籃球。（3）西安市的夏天既干燥又炎熱。（4）并不是每一個人都喜歡吃臭豆腐。（5）喜歡讀《三國演義》的人必讀《水滸》。（6）欲窮千里目，更上一層樓。2教材P542-7?（1）有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花

又喜歡菊花。MAN（X）：X是人LIKE（X，Y）：X喜歡Y。（代表全稱符號，代表存在符號）

((X)(MAN(X)=>LIKE(X,MEIFLOWER))?((Y)(MAN(Y)=>LIKE(Y,JUFLOWER))?((Z)(MAN(Z)=>(LIKE(Z,MEIFLOWER)?LIKE(Z,JUFLOWER))?（2）他每天下午都去打籃球。TIME(X):X是下午PLAY（X，Y）：X去打Y

（X）TIME（X）=>PLAY（HE，BASKETBALL）?（3）西安市的夏天既干燥又炎熱。SUMMER（X）：X處于夏天DRY（X）：X很干燥HOT（X）：X很炎熱

SUMMER（Xi’an）=>DRY（Xi’an）?HOT（Xi’an）?（4）并不是每一個人都喜歡吃臭豆腐。MAN（X）：X是人LIKE（X，Y）：X喜歡吃Y

┐（（X）MAN（X）=>LIKE（X，CHOUDOUFU））?（5）喜歡讀《三國演義》的人必讀《水滸》。MAN（X）：X是人LIKE（X，Y）：X喜歡讀Y(X）MAN（X）?LIKE（X，《SANGUOYANYI》）=>LIKE（X，《SHUIHU》）?（6）欲窮千里目，更上一層樓。MAN（X）：X是人EYE（X）：X想窮千里目UP（X）：X要更上一層樓(X）MAN（X）?EYE（X）=>UP（X）?2－6答：定義如下謂詞：P(x,y)：xperformsytask（x完成y任務）； Q(y)：yrequiresintelligence(y需要智能)C(x)：xisacomputersystem(x是一個計算機系統(tǒng))I(x)：xisintelligent(x是智能的)(?每個儲蓄錢的人都獲得利息。

令S(x,y)表示"x儲蓄y"M(x)表示"x是錢"

I(x)表示"x是利息"

E(x，y)表示"x獲得y"?如果無論約翰(John)到哪里去，菲多(Fido)也就去那里(x)[AT(JOHN,X)=>AT(FIDO,X)]?李明住在一棟黃色的房子里

Lives(x,y)：表示"x住在y"Color(x,y)：表示"x的顏色為y"Lives(li,house)∧Color(house,yellow)?每個人都有心臟H(x)：表示"x有心臟"P(x)：表示"x是人"(x)[H(x)=>P(x)]?

在我們班中，并非所有同學都能取得優(yōu)秀成績S(x)：表示"x是同學"C(x)：表示"x在我們班中"E(x)：表示"x能取得優(yōu)秀成績"

~x((S(x)∧C(x))=>E(x))或者x(S(x)∧C(x)∧~E(x))。?教室里有同學在講話。

S(x)：表示"x是同學"R(x)：表示"x在教室里"T(x)：表示"x在講話"x(S(x)∧R(x)∧T(x))?傳教士和野人問題可以這樣過河：1先讓一個傳教士和一個野人過，再由一個傳教士把船開回來；2讓傳教士再把一個野人度過河去，再由傳教士把船開回來；這時河對岸有兩個野人．沒過河的有三個傳教士和一個野人．3讓兩個傳教士過河，并且都留在河對岸．讓一個野人把船開回來．4讓野人把最后的一個傳教士度過對岸；再由野人把船開回來．這時河對岸有一個野人和三個傳教士；5最后兩個野人一起過河．?傳教士和人問題2個野人去，1個野人回2個野人去，1個野人回2個傳教士去，1個野人與1個傳教士回2個傳教士去，1個野人回2個野人去，1個野人回2個野人去，完成?作業(yè)2．請對下列命題分別寫出它的語義網絡：（1）錢老師從6月至8月給會計班講《市場經濟學》課程。（2）張三是大發(fā)電腦公司的經理，他35歲，住在飛天胡同68號。（3）甲隊與乙隊進行藍球比賽，最后以89：102的比分結束。?錢老師從6月至8月給會計班講《市場經濟學》課程?張三是大發(fā)電腦公司的經理，他35歲，住在飛天胡同68號??甲隊與乙隊進行藍球比賽，最后以89：102的比分結束

??演講完畢，謝謝觀看！附錄資料：人工智能簡介?AboutTeachingPlan基本要求：人工智能是計算機科學中涉及研究、設計和應用智能機器的一個分支，是目前迅速發(fā)展的一門新興學科，新思想新方法層出不窮。其基本思想是利用機器來模仿和執(zhí)行人腦的功能，如判斷、推理、證明、識別、感知、理解、設計、思考、規(guī)劃、學習和問題求解等思維活動。對于培養(yǎng)學生計算機技術的應用能力，開闊思路和視野，有重要意義。

?AboutTeachingPlan因此，要求學生掌握知識表示和問題求解的幾種常用方法，尤其是不確定性推理；掌握機器學習基本概念，了解幾種機器學習方法尤其是神經網絡學習方法；掌握專家系統(tǒng)的概念，了解專家系統(tǒng)設計方法，掌握一些智能控制方法，了解國內外人工智能研究尤其是機器人的最新進展；具有一定的人工智能編程設計能力（利用Lisp或Prolog語言）。?AboutTeachingPlan課程內容以及學時分配人工智能引論(1) 人工智能概念及與計算機的關系，研究途徑、內容和應用領域概況介紹，其他最新材料。符號主義、連接主義、行為主義三大流派人工智能數學基礎(1)知識表示方法（2） 狀態(tài)空間法、問題歸約法，謂詞邏輯法、產生式表示法（動物識別系統(tǒng)）；CLIPS語言；語義網絡法、框架法（這是結構化表示）；劇本、過程、Petri網、面向對象的表示。?AboutTeachingPlan 搜索技術和策略（3-4）狀態(tài)空間法，盲目搜索和啟發(fā)式搜索，A*算法；海伯倫理論、消解原理和策略；與\或形推理和搜索策略；其他求解技術。 不確定推理技術（3-4）主觀Bayes理論；可信度方法和證據理論；系統(tǒng)組織技術；非單調推理；Rete快速算法；模糊推理技術；基于語義網絡和框架不確定推理； 專家系統(tǒng)（2）專家系統(tǒng)概念、結構和知識獲??；黑板模型、知識組織、管理及系統(tǒng)建造和開發(fā)工具；專家系統(tǒng)舉例及編程。

人工智能程序設計（1）人工智能語言基本機制：LISP和PROLOG。?AboutTeachingPlan 模式識別導論（3）模式識別專題：概率模式識別。模式識別專題：結構模式識別 機器學習（1）：機械,解釋經驗,事例,歸納,概念,類比學習等；統(tǒng)計,結構,模糊模式識別。 專題講座（3次） 1)神經網絡基本理論和應用 (史奎凡課程：安排于人工智能理論與應用課程內)； 2)智能體（Agent）； 3)自然語言處理； 4)智能控制和機器人科學 智能控制的結構理論和研究領域，智能控制系統(tǒng)及應用示例；機器人規(guī)劃、機器視覺和自然語言理解等。?AboutTeachingPlan 實踐：1) 搜索技術和策略2) 不確定推理技術3) 專家系統(tǒng)：動物識別系統(tǒng)4) 模式識別技術5) 調研： 搜索技術和策略、不確定推理技術、統(tǒng)計模式識別、機器學習等四個領域進展報告。?ChapterOne:BriefIntroductiontoArtificialIntelligence1.WhatisAI?人工智能（ArtificialIntelligence,AI）是當前科學技發(fā)展的一門前沿學科，同時也是一門新思想，新觀念，新理論，新技術不斷出現(xiàn)的新興學科以及正在發(fā)展的學科。它是在計算機科學，控制論，信息論，神經心理學，哲學，語言學等多種學科研究的基礎發(fā)展起來的，因此又可把它看作是一門綜合性的邊緣學科。它的出現(xiàn)及所取得的成就引起了人們的高度重視,并取得了很高的評價。有的人把它與空間技術，原子能技術一起并譽為20世紀的三大科學技術成就。?