最新人工智能09559

1、1 第二部分 知識(shí)表示方法 2 知識(shí)是一切智能行為的基礎(chǔ)，也是人工智能的重要 研究對(duì)象。要使計(jì)算機(jī)具有智能，就必須使它具有知 識(shí)，而要使計(jì)算機(jī)具有知識(shí)，首先必須解決知識(shí)的表 示問(wèn)題。 知識(shí)表示包括知識(shí)表示的概念和知識(shí)表示方法。對(duì) 知識(shí)表示方法，又可根據(jù)所表示知識(shí)的確定化程度， 分為確定性知識(shí)表示和不確定性知識(shí)表示。 3 v 知識(shí)與知識(shí)表示的概念 v 狀態(tài)空間法 v 問(wèn)題規(guī)約法 v 謂詞邏輯法 v 語(yǔ)義網(wǎng)絡(luò)法 v 框架表示法 內(nèi)容提要 4 1. 知識(shí)與知識(shí)表示的概念 知識(shí) 1）.知識(shí)的屬性 2）.知識(shí)的類(lèi)型 二.知識(shí)表示 1）.知識(shí)表示的要求 2）.知識(shí)表示觀點(diǎn) 3）.知識(shí)表示的方法 5 知識(shí)是

2、人們?cè)诟脑炜陀^世界的實(shí)踐中積累起來(lái)的認(rèn)識(shí) 和經(jīng)驗(yàn)。 通常，人們對(duì)客觀世界的描述是通過(guò)數(shù)據(jù)和信息來(lái)實(shí) 現(xiàn)的。 數(shù)據(jù)和信息是兩個(gè)密切相關(guān)的概念。數(shù)據(jù)是信息的載 體和表示，信息是數(shù)據(jù)在特定場(chǎng)合下的含義，或者說(shuō)信息 是數(shù)據(jù)的語(yǔ)義。 一. 知識(shí) 6 知識(shí)是對(duì)信息進(jìn)行智能性加工所形成的對(duì)客觀世界規(guī)律性 的認(rèn)識(shí)。 把有關(guān)信息關(guān)聯(lián)在一起所形成的信息結(jié)構(gòu)稱(chēng)為知識(shí)。 “信息”與“關(guān)聯(lián)”是構(gòu)成知識(shí)的兩個(gè)要素。 信息之間關(guān)聯(lián)的形式可以多種多樣，其中最常用的一種 形式是： 如果，那么。 例如，“如果他學(xué)過(guò)人工智能課程，那么他應(yīng)該知道什 么叫知識(shí)”。 7 （1）真假性與相對(duì)性 1）.知識(shí)的屬性： 真假性是指可以通過(guò)實(shí)踐或

3、推理來(lái)證明知識(shí)為真 或?yàn)榧佟?相對(duì)性是指知識(shí)的真與假是相對(duì)于某些條件、環(huán) 境及時(shí)間而言的，即知識(shí)一般不是無(wú)條件的真或無(wú)條 件的假，而是相對(duì)于一定條件的。 8 知識(shí)的不確定性包括不完備性、不確定性與模糊性： （2）不確定性 知識(shí)的不完備性是指在解決問(wèn)題時(shí)不具備解決該問(wèn)題 所需要的全部知識(shí)。 知識(shí)的不確定性是指知識(shí)所具有的既不能完全被確定 為真，又不能完全被確定為假的特性。 知識(shí)的模糊性是指知識(shí)的“邊界”不明確的特性。 9 矛盾性是指同一個(gè)知識(shí)集中的不同知識(shí)之間相互對(duì)立或不 一致，即從這些知識(shí)出發(fā)，會(huì)推出不一致的結(jié)論。 相容性是指同一個(gè)知識(shí)集中的所有知識(shí)之間互相不矛盾。 （3）矛盾性和相容性 10

4、 可表示性是指知識(shí)可以用適當(dāng)?shù)男问奖硎境鰜?lái)。例如語(yǔ)言 、文字、圖形、神經(jīng)元網(wǎng)絡(luò)等。 可利用性是指知識(shí)可以被用來(lái)解決各種各樣的問(wèn)題。 （4）可表示性與可利用性 11 （1）按知識(shí)的性質(zhì)： 2）.知識(shí)的類(lèi)型： 概念 命題 公理 定理 規(guī)則 方法 12 常識(shí)性知識(shí)：是指通用通識(shí)的知識(shí)。即人們普遍知道的、 適應(yīng)于所有領(lǐng)域的知識(shí)。 領(lǐng)域性知識(shí)：是指面向某個(gè)具體專(zhuān)業(yè)的專(zhuān)業(yè)性知識(shí)，這些 知識(shí)只有該領(lǐng)域的專(zhuān)業(yè)人員才能夠掌握和運(yùn)用它。 （2）按知識(shí)的作用范圍： 13 事實(shí)性知識(shí)：也稱(chēng)敘述性知識(shí)，是用來(lái)描述問(wèn)題或事物的概 念、屬性、狀態(tài)、環(huán)境及條件等情況的知識(shí)。 過(guò)程性知識(shí)：是用來(lái)描述問(wèn)題求解過(guò)程所需要的操作、演

5、算 或行為等規(guī)律性的知識(shí)，它指出在問(wèn)題求解過(guò)程中如何使用那 些與問(wèn)題有關(guān)的事實(shí)性知識(shí)，即用來(lái)說(shuō)明在那些敘述性知識(shí)成 立的時(shí)候該怎么辦。 控制性知識(shí)：也稱(chēng)元知識(shí)或超知識(shí)，是關(guān)于如何運(yùn)用已有知 識(shí)進(jìn)行問(wèn)題求解的知識(shí)，因此，也稱(chēng)為關(guān)于知識(shí)的知識(shí)。 （3）按知識(shí)的作用 14 表層知識(shí)是指客觀事物的現(xiàn)象以及這些現(xiàn)象與結(jié)論之間關(guān) 系的知識(shí)。 深層知識(shí)是指事物本質(zhì)、因果關(guān)系內(nèi)涵、基本原理之類(lèi)的 知識(shí)。例如，理論知識(shí)、理性知識(shí)等。 （4）按知識(shí)的層次 15 確定性知識(shí)：是可以給出其真值為“真”或“假”的知識(shí)。 這些知識(shí)是可以精確表示的知識(shí)。 不確定性知識(shí)：是指具有“不確定”特性的知識(shí)。不確定 性的概念包含不精

6、確、不完備和模糊。 （5）按知識(shí)的確定性 16 邏輯性知識(shí)：是反映人類(lèi)邏輯思維過(guò)程的知識(shí)，例如人 類(lèi)的經(jīng)驗(yàn)性知識(shí)。它對(duì)應(yīng)著邏輯思維。 形象性知識(shí)：是通過(guò)事物的形象建立起來(lái)的知識(shí)，它對(duì) 應(yīng)著形象思維。例如，一個(gè)人的相貌，要用文字來(lái)描述非 常困難，但要親眼見(jiàn)到這個(gè)人，就很容易在頭腦中形成這 個(gè)人的概念。 （6）按知識(shí)的結(jié)構(gòu)及表現(xiàn)形式 17 所謂知識(shí)表示是對(duì)知識(shí)的一種描述，即用一些約定的符 號(hào)把知識(shí)編碼成一組計(jì)算機(jī)可以接受的數(shù)據(jù)結(jié)構(gòu)。所謂知識(shí) 表示過(guò)程就是把知識(shí)編碼成某種數(shù)據(jù)結(jié)構(gòu)的過(guò)程。 同一知識(shí)可以有多種不同的表示形式，而不同表示形式 所產(chǎn)生的效果又可能不一樣。 二. 知識(shí)表示 18 （1）表示能

7、力 知識(shí)表示能力是指能否正確、有效地將問(wèn)題求解所需要 的各種知識(shí)表示出來(lái)。知識(shí)表示能力包括以下三個(gè)方面： 一是知識(shí)表示范圍的廣泛性； 二是領(lǐng)域知識(shí)表示的高效性； 三是對(duì)非確定性知識(shí)表示的支持程度。 1）.知識(shí)表示的要求 19 （2）可利用性 知識(shí)的利用是指使用知識(shí)進(jìn)行推理，以求得問(wèn)題的 解。知識(shí)的可利用性包括對(duì)推理的適應(yīng)性和對(duì)高效算法 的支持性。 （3）可組織性與可維護(hù)性 知識(shí)的組織是指把有關(guān)知識(shí)按照某種方式組成一種知 識(shí)結(jié)構(gòu)。知識(shí)維護(hù)是指在保證知識(shí)的一致性與完整性的前 提下對(duì)知識(shí)所進(jìn)行的增加、刪除、修改等操作。 20 （4）可實(shí)現(xiàn)性 所謂可實(shí)現(xiàn)性是指知識(shí)表示要便于在計(jì)算機(jī)上實(shí)現(xiàn)，便 于直接由

8、計(jì)算機(jī)對(duì)其進(jìn)行處理。 （5）自然性與可理解性 自然性是指知識(shí)表示形式要符合人們的日常習(xí)慣和思維 方式?？衫斫庑允侵杆硎镜闹R(shí)應(yīng)易讀、易懂、易獲取、 易維護(hù)。 21 （1）陳述性觀點(diǎn) 陳述性知識(shí)表示（Declarative knowledge representation）是指以陳述的方式把知識(shí)用一定的數(shù)據(jù)結(jié) 構(gòu)表示出來(lái)，即把知識(shí)看作一種特殊的數(shù)據(jù)，知識(shí)表示說(shuō)明 描述的對(duì)象是什么，不涉及如何運(yùn)用知識(shí)的問(wèn)題。 2）.知識(shí)表示觀點(diǎn)： 22 （2）過(guò)程性觀點(diǎn) 過(guò)程性知識(shí)表示（Procedural knowledge representation）是指以程序（亦稱(chēng)為過(guò)程）的方式把知識(shí) 表示出來(lái)，即把知

9、識(shí)寓于程序之中，把知識(shí)表示和運(yùn)用知識(shí) 結(jié)合起來(lái)。 23 知識(shí)表示方法又稱(chēng)為知識(shí)表示技術(shù)，其表示形式被稱(chēng)為 知識(shí)表示模式。目前，使用較多的知識(shí)表示方法有: 狀態(tài)空間法 問(wèn)題歸約法 謂詞邏輯法 語(yǔ)義網(wǎng)絡(luò)法 框架表示法 劇本表示法 過(guò)程表示法 面向?qū)ο蟊硎痉?3）.知識(shí)表示方法： 24 問(wèn)題的狀態(tài)描述 二. 狀態(tài)圖示法 三. 狀態(tài)空間表示舉例 2. 狀態(tài)空間法 25 對(duì)人工智能研究中運(yùn)用的問(wèn)題求解方法進(jìn)行綜合分析，可以發(fā) 現(xiàn)許多問(wèn)題求解方法是采用試探搜索方法的。 是通過(guò)在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來(lái)求解問(wèn)題的。 這種基于解答空間的問(wèn)題表示和求解方法就是狀態(tài)空間法。 狀態(tài)空間法是以狀態(tài)和算符為基礎(chǔ)來(lái)

10、表示和求解問(wèn)題的。 26 實(shí)例：十五數(shù)碼難題 一. 問(wèn)題的狀態(tài)描述 如何把初始棋局變換為目標(biāo)棋局？ 27 最直接的求解方法：嘗試各種不同的走步，直到偶然得到目標(biāo) 棋局為止，即試探搜索。 28 對(duì)十五數(shù)碼難題的問(wèn)題描述和求解過(guò)程進(jìn)行分析： 初始狀態(tài)：初始棋局 11，9，4，15，1，3，0，12，7，5，8，6，13，2，10，14 操作符：走步 右移棋子3，下移棋子4，左移棋子12，. （60條） 或者：移動(dòng)空格 （4條） 目標(biāo)狀態(tài)：目標(biāo)棋局 1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，0 狀態(tài)空間法狀態(tài)空間法：從某個(gè)初始狀態(tài)開(kāi)始，每次加一個(gè)操作符，遞增地建 立起操

11、作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止。 狀態(tài)圖狀態(tài)圖：初始狀態(tài)可達(dá)到的各狀態(tài)所對(duì)應(yīng)的節(jié)點(diǎn)組成的圖。 29 問(wèn)題狀態(tài)的描述： 狀態(tài)狀態(tài)：為描述某類(lèi)不同事物間的差別而引入的一組最少變量q0， q1，qn的有序集合，其矢量形式如下： Q=q0，q1，qn 狀態(tài)變量狀態(tài)變量：狀態(tài)集合中的每個(gè)元素qi（i=0,1,n）。 具體狀態(tài)具體狀態(tài)：給定每個(gè)分量的一組值。如 Qk=q0k，q1k，qnk 操作符操作符：使問(wèn)題從一種狀態(tài)變換到另一種狀態(tài)的手段，也叫算算 符符。算符可以是走步、過(guò)程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏 輯符號(hào)等。 問(wèn)題的狀態(tài)空間問(wèn)題的狀態(tài)空間：表示該問(wèn)題全部可能狀態(tài)及其關(guān)系的圖。它 包含三種

12、說(shuō)明的集合，即所有可能的問(wèn)題初始狀態(tài)集合S、操作 符集合F以及目標(biāo)狀態(tài)集合G。 狀態(tài)空間可記為三元組（S，F(xiàn)，G） 30 圖論中的幾個(gè)術(shù)語(yǔ)： 圖；有向圖；后繼節(jié)點(diǎn)（后裔）；父輩節(jié)點(diǎn)（祖先）； 路徑（長(zhǎng)度為k的路徑）；節(jié)點(diǎn)nj是從節(jié)點(diǎn)ni可達(dá)到的路徑； 代價(jià)；兩節(jié)點(diǎn)間路徑的代價(jià)。 當(dāng)用一個(gè)圖來(lái)表示某個(gè)狀態(tài)空間時(shí)，圖中各節(jié)點(diǎn)標(biāo)上相應(yīng)的狀 態(tài)描述，而有向弧線旁邊標(biāo)上算符。 尋找從一種狀態(tài)變換為另一種狀態(tài)的某個(gè)算符序列問(wèn)題等價(jià)于 尋找圖的某一路徑問(wèn)題。 二. 狀態(tài)圖示法 31 圖的顯式說(shuō)明：圖中的各節(jié)點(diǎn)及其具有代價(jià)的弧線由一張 圖或表明確給出。 圖的隱式說(shuō)明：圖中的節(jié)點(diǎn)集合是無(wú)限的，但起始節(jié)點(diǎn)是 已知

13、的，而且引入后繼算符的概念是方便的。把后繼節(jié)點(diǎn)算符 作用于任一節(jié)點(diǎn)可以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線 的代價(jià)。 搜索某個(gè)狀態(tài)空間以求得算符序列的一個(gè)解答過(guò)程，就是 使隱式圖足夠大的一部分變?yōu)轱@式以便包含目標(biāo)的過(guò)程，這是 狀態(tài)空間問(wèn)題求解的基礎(chǔ)。 問(wèn)題的表示對(duì)求解工作量有很大的影響問(wèn)題的表示對(duì)求解工作量有很大的影響。 32 問(wèn)題的狀態(tài)表示方法涉及在狀態(tài)描述中如何應(yīng)用變量。 須用一個(gè)包含變量的表達(dá)式來(lái)描述狀態(tài)的全部集合，而 不僅僅描述一個(gè)狀態(tài)。 用常量取代表達(dá)式中的變量，就可得到一個(gè)具體的狀 態(tài)描述。用來(lái)描述一個(gè)狀態(tài)集合的含有變量的表達(dá)式， 叫做狀態(tài)描述模式。 33 三. 狀態(tài)空間表示舉例

14、實(shí)例： 猴子摘香蕉問(wèn)題 a c b 箱子箱子 34 問(wèn)題狀態(tài)的表示：四元組（W，x，Y，z） W：猴子的水平位置。W=a，b，c。 x：當(dāng)猴子在箱子頂上時(shí)取x=1；否則取x=0。 Y：箱子的水平位置。Y=a，b，c。 z：當(dāng)猴子摘到香蕉時(shí)取z=1；否則取z=0。 初始狀態(tài)：（a，0，b，0） 目標(biāo)狀態(tài)：（c，1，c，1） 35 算符集合： goto(b)：猴子走到水平位置b。 （a，0，b，z） goto(U) （b，0，b，z） pushbox(c)：猴子把箱子推到水平位置c。 （b，0，b，z） pushbox(V) （c，0，c，z） climbbox：猴子爬上箱頂。 （ c，0，c，z

15、 ） climbbox （ c，1，c，z ） grasp：猴子摘到香蕉。 （c，1，c，0） grasp （c，1，c，1） 算符的適用性條件：強(qiáng)加于操作的實(shí)用性條件。 如：應(yīng)用算符pushbox(c)時(shí)，要求猴子與箱子必須在同一位置 36 操作序列：goto(b)，pushbox(c)，climbbox，grasp 猴子摘香蕉問(wèn)題的狀態(tài)空間圖 37 練習(xí)題(野人和傳教士渡河問(wèn)題）： 有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一艘小船從右 岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果 野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他 們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去？ 38

16、 3. 問(wèn)題歸約法 問(wèn)題規(guī)約的描述 二.與或圖表示 三.問(wèn)題歸約機(jī)理 39 問(wèn)題歸約法： 有許多問(wèn)題可以通過(guò)一系列變換變?yōu)橐粋€(gè)子問(wèn)題集； 這些子問(wèn)題的解可以直接得到； 通過(guò)解決這些子問(wèn)題，從而就解決了初始問(wèn)題。 40 實(shí)例：梵塔問(wèn)題 一. 問(wèn)題的歸約描述 如何由初始配置變換為目標(biāo)配置？ 123123 初始配置初始配置 目標(biāo)配置目標(biāo)配置 41 求解思路：把原始問(wèn)題歸約為一個(gè)比較簡(jiǎn)單的問(wèn)題的集合 A B C 123 A B C 123 111122 A BC 123 A B C 123 122322 A BC 123 A B C 123 322333 要把所有圓盤(pán)都移至柱子3，必須 先把圓盤(pán)C移至

17、柱子3；而且在移動(dòng)圓 盤(pán)C至柱子3之前，柱子3必須是空的。 只有在移開(kāi)圓盤(pán)A和B之后，才能 移動(dòng)圓盤(pán)C；而且圓盤(pán)A和B不能在柱 子3。因此，應(yīng)該把A和B移到柱子2 上。 把圓盤(pán)C從柱子1移動(dòng)到柱子3，并 繼續(xù)解決其余部分的移動(dòng)問(wèn)題。 （移動(dòng)A、B - 2） （移動(dòng)C - 3） （移動(dòng)A、B - 3） 42 通過(guò)以上分析，把原始問(wèn)題歸約為3個(gè)子問(wèn)題： （1） 移動(dòng)A、B - 2 雙圓盤(pán)問(wèn)題：可進(jìn)一步歸約 （2） 移動(dòng)C - 3 單圓盤(pán)問(wèn)題：可直接求解-本原問(wèn)題 （3） 移動(dòng)A、B - 3 雙圓盤(pán)問(wèn)題：可進(jìn)一步歸約 與或圖：可以有效說(shuō)明問(wèn)題歸約法的求解過(guò)程。 梵塔問(wèn)題歸約圖 43 問(wèn)題歸約描述：

18、采用問(wèn)題歸約法描述與求解問(wèn)題， 問(wèn)題歸約表示由三部分組成： （1）一個(gè)初始問(wèn)題描述 如：（111），（333） （2）一套把問(wèn)題變換為子問(wèn)題的操作符問(wèn)題歸約算符問(wèn)題歸約算符 如：移動(dòng)A、B - 2 等 （3）一套本原問(wèn)題描述 如：（122），（322） 本原問(wèn)題本原問(wèn)題：是可直接求解或具有已知解答的問(wèn)題，出現(xiàn)本原問(wèn)題即可 停止搜索。 問(wèn)題歸約法的實(shí)質(zhì)：從目標(biāo)（要解決的問(wèn)題）出發(fā)逆向推理逆向推理，建立子 問(wèn)題以及子問(wèn)題的子問(wèn)題，直至最后把初始問(wèn)題歸約為一個(gè)本原問(wèn)題 集合。 問(wèn)題歸約的目的：最終產(chǎn)生具有明顯解答的本原問(wèn)題。 44 二. 與或圖表示 用問(wèn)題歸約法描述和求解問(wèn)題的過(guò)程可以用與或圖來(lái) 表

19、示。 例如：?jiǎn)栴}A既可由求解問(wèn)題B和C， 也可由求解問(wèn)題D、E和F，或者由 單獨(dú)求解問(wèn)題G來(lái)解決。這一關(guān)系可 由右圖所示的結(jié)構(gòu)圖來(lái)表示。 45 為了使含有一個(gè)以上后繼問(wèn)題的每個(gè)集合 能夠聚集在它們各自的父輩節(jié)點(diǎn)之下，在 上述結(jié)構(gòu)圖中引入附加節(jié)點(diǎn)。 如右圖，可以認(rèn)為問(wèn)題A被歸約為單一子 問(wèn)題N、M和H，N、M和H叫或節(jié)點(diǎn)或節(jié)點(diǎn)。問(wèn) 題N被歸約為子問(wèn)題B和C的單一集合，要 求解N就必須求解所有的子問(wèn)題，因此， B和C叫做與節(jié)點(diǎn)與節(jié)點(diǎn)。各個(gè)與節(jié)點(diǎn)用跨接指 向其后繼節(jié)點(diǎn)的弧線的小段圓弧加以標(biāo)記。 這樣形成的結(jié)構(gòu)圖就叫與或圖。 46 關(guān)于與或圖的幾點(diǎn)說(shuō)明： 在與或圖中，如果一個(gè)節(jié)點(diǎn)有后繼節(jié)點(diǎn)，那么這些后

20、繼節(jié)點(diǎn) 既可全為與節(jié)點(diǎn)，也可全為或節(jié)點(diǎn)。 特殊情況下，可能不出現(xiàn)任何與節(jié)點(diǎn)，如在狀態(tài)空間圖中就 不存在與節(jié)點(diǎn)，即狀態(tài)空間圖是普通圖普通圖，因此可以說(shuō)問(wèn)題歸約 法是比狀態(tài)空間法更通用的問(wèn)題求解方法。 通過(guò)與或圖，在某個(gè)問(wèn)題描述中應(yīng)用問(wèn)題歸約算符，可以依 次產(chǎn)生出一個(gè)中間或節(jié)點(diǎn)和與節(jié)點(diǎn)后繼，從而可以用與或圖來(lái) 表示問(wèn)題歸約方法的相關(guān)結(jié)構(gòu)。 在與或圖中，起始節(jié)點(diǎn)對(duì)應(yīng)于原始問(wèn)題描述，葉子節(jié)點(diǎn)對(duì)應(yīng) 于本原問(wèn)題描述。 47 引入與或圖后，問(wèn)題求解過(guò)程就轉(zhuǎn)換為與或圖上的搜索過(guò) 程，搜索的目的是要表明起始節(jié)點(diǎn)有解，在與或圖中一個(gè)可解 節(jié)點(diǎn)的一般定義可以歸納為： （1）葉子節(jié)點(diǎn)是可解節(jié)點(diǎn)（本原問(wèn)題）。 （2）如

21、果某個(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)才是可解的。 在上述定義基礎(chǔ)上，可以給出解圖的定義：解圖解圖是那些可 解節(jié)點(diǎn)的子圖，這些節(jié)點(diǎn)能夠證明其初始節(jié)點(diǎn)是可解的。 48 當(dāng)與或圖中某些非葉節(jié)點(diǎn)完全沒(méi)有后繼節(jié)點(diǎn)時(shí)，我們就說(shuō) 它是不可解的。這些不可解節(jié)點(diǎn)的出現(xiàn)可能意味著圖中另外一 些節(jié)點(diǎn)也是不可解的。不可解節(jié)點(diǎn)的一般定義可以歸納為： （1）沒(méi)有后繼的非葉節(jié)點(diǎn)是不可解節(jié)點(diǎn)。 （2）如果某個(gè)非葉節(jié)點(diǎn)含有或或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部 后繼節(jié)點(diǎn)不可解時(shí)，該非葉節(jié)點(diǎn)才是

22、不可解的。 （3）如果某個(gè)非葉節(jié)點(diǎn)含有與與后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼 節(jié)點(diǎn)至少有一個(gè)不可解時(shí)，該非葉節(jié)點(diǎn)才是不可解的。 與狀態(tài)空間圖求解類(lèi)似，一般很少用顯式圖來(lái)搜索，而是 用由初始問(wèn)題描述和問(wèn)題歸約算符所定義的隱式圖來(lái)搜索，從 而，問(wèn)題求解過(guò)程實(shí)際上就是生成與或圖的足夠部分，以證明 初始節(jié)點(diǎn)可解。 49 綜上所述，與或圖的構(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ì)于把問(wèn)題歸約算符應(yīng)用于問(wèn)題A的每種可能情況，都把 問(wèn)題變換為一個(gè)子問(wèn)題的集合，有向弧線由A指向后繼節(jié)

23、點(diǎn)，表 示所求得的子問(wèn)題集合。如問(wèn)題A可歸約為不同的子問(wèn)題集合N、 M和H，只要N、M和H有一個(gè)可解，則A可解，所以N、M和H稱(chēng) 為或節(jié)點(diǎn)。 50 （4）對(duì)于代表兩個(gè)或兩個(gè)以上子問(wèn)題集合的每個(gè)節(jié)點(diǎn)，有向弧 線從該節(jié)點(diǎn)指向該子問(wèn)題集合中的各個(gè)節(jié)點(diǎn)。因?yàn)橹挥挟?dāng)集合 中的所有項(xiàng)都有解時(shí)，該子問(wèn)題才有解，所以這些子問(wèn)題節(jié)點(diǎn) 叫與節(jié)點(diǎn)。為了和或節(jié)點(diǎn)進(jìn)行區(qū)分，把具有共同父輩的與節(jié)點(diǎn) 后裔的所有弧線用另外一段小弧線連接起來(lái)。 （5）特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問(wèn)題A，而且這個(gè) 算符產(chǎn)生具有一個(gè)以上子問(wèn)題的某個(gè)集合時(shí)，由（3）和（4） 所產(chǎn)生的圖可以得到簡(jiǎn)化，將代表子問(wèn)題集合的中間或節(jié)點(diǎn)略 去。 利用上

24、述規(guī)則生成的與或圖中，每個(gè)節(jié)點(diǎn)代表一個(gè)問(wèn)題或 問(wèn)題集合，除起始節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，所以這 樣的與或圖實(shí)際是與或樹(shù)與或樹(shù)。 51 三. 問(wèn)題歸約機(jī)理 出發(fā)點(diǎn)引入關(guān)鍵算符： 對(duì)于狀態(tài)空間的搜索問(wèn)題，雖然尋求某個(gè)解答中的整 個(gè)算符序列比較困難，但規(guī)定這些算符中的一個(gè)卻往往比 較容易。如果某個(gè)算符被認(rèn)為是求解問(wèn)題的決定性步驟， 那么就很容易找到這樣一個(gè)算符。例如，梵塔難題中“移 動(dòng)C - 3”這個(gè)算符就是求解問(wèn)題的決定性步驟，也很容易 找到該算符，這種具有決定性作用的算符叫做關(guān)鍵算符關(guān)鍵算符。 52 關(guān)鍵算符的作用： 確定了某個(gè)關(guān)鍵算符后，就可以以該關(guān)鍵算符為基礎(chǔ)進(jìn)行 問(wèn)題歸約。 例如，在

25、三元狀態(tài)（S，F(xiàn)，G）表示的問(wèn)題中，假設(shè)F中的 某個(gè)f是關(guān)鍵算符，那么可以認(rèn)為（S，F(xiàn)，G）的第一個(gè)后繼問(wèn) 題是一個(gè)對(duì)應(yīng)于尋找一條通向某一f適用的狀態(tài)的路徑問(wèn)題，令 Gf表示f適用的所有狀態(tài)的集合，則該后繼問(wèn)題是由（S，F(xiàn)， Gf ） 描述的子問(wèn)題。 一旦該子問(wèn)題得到解決，就可以進(jìn)一步解決由（g，F(xiàn)，f （g）所表示的子問(wèn)題，其中g(shù) Gf ，f（g）表示把f應(yīng)用于 g而得到的狀態(tài)，因?yàn)樵撟訂?wèn)題是僅由應(yīng)用關(guān)鍵算符f就可以解決， 所以是本原問(wèn)題。于是，剩下的就是解決由（ f（g），F(xiàn)，G ） 所描述的子問(wèn)題。 53 關(guān)鍵算符的作用： 一旦確定了某個(gè)關(guān)鍵算符f，就可以把問(wèn)題歸約為如下三個(gè)子問(wèn)題： （

26、1）（S，F(xiàn)， Gf ）； （2）（g，F(xiàn)，f（g）； （3）（ f（g），F(xiàn)，G ）。 問(wèn)題（2）是本原問(wèn)題 問(wèn)題（1）和（3）可以用直接的狀態(tài)空間搜索技術(shù)或進(jìn)一步的問(wèn)題 歸約來(lái)求解（尋找子問(wèn)題的關(guān)鍵算符，進(jìn)一步歸約下去） 54 關(guān)鍵算符的作用： 對(duì)于許多問(wèn)題，往往無(wú)法預(yù)先知道哪個(gè)算符是關(guān)鍵算符， 只能推測(cè)某個(gè)算符的子集，該子集中的某個(gè)算符可能是關(guān)鍵算 符。因此，用該子集中的每個(gè)算符產(chǎn)生后繼子問(wèn)題，這樣就建 立起了一個(gè)與或圖。 可見(jiàn)，要應(yīng)用這種方法，首先必須尋找狀態(tài)空間搜索問(wèn)題的 候選關(guān)鍵算符集合。 如何尋找候選關(guān)鍵算符呢？如何尋找候選關(guān)鍵算符呢？計(jì)算某個(gè)問(wèn)題的差別計(jì)算某個(gè)問(wèn)題的差別 55

27、什么是差別？ 實(shí)例：猴子摘香蕉問(wèn)題 把4個(gè)算符的作用結(jié)果和使用條件重寫(xiě)如下： f1：（W，0，Y，z） goto(U) （U，0，Y，z） f2：（W，0，W，z） pushbox(V) （V，0，V，z） f3：（W，0，W，z） climbbox （W，1，W，z） f4：（c，1，c，0） grasp （c，1，c，1） 初始狀態(tài)： （a，0，b，0） 算符集合： F=f1，f2，f3，f4 滿足目標(biāo)條件的狀態(tài)集合：G 56 應(yīng)用關(guān)鍵算符和差別的歸約過(guò)程： 首先計(jì)算初始問(wèn)題的差別， （a，0，b，0） 不滿足目標(biāo) 測(cè)試的原因在于其最后一個(gè)元素不是1。與歸約這個(gè)差別相關(guān) 的關(guān)鍵算符是f4=

28、grasp，用f4來(lái)歸約初始問(wèn)題，得到如下子問(wèn)題： （1）（a，0，b，0），F(xiàn)，Gf4） （2）（S1，F(xiàn)，f4（S1） （本原問(wèn)題） （3） （f4（S1），F(xiàn)，G） （本原問(wèn)題） 其中Gf4是適用于算符f4的狀態(tài)描述集合，S1 Gf4 57 要求解問(wèn)題（1），就要先計(jì)算其差別。由（a，0，b，0） 所描述的狀態(tài)不在Gf4中，差別如下： 箱子不在c處 猴子不在c處 猴子不在箱子上 f2=pushbox（c） f1=goto（c） f3=climbbox 與差別相關(guān) 的關(guān)鍵算符 用關(guān)鍵算符f2歸約問(wèn)題（1），得到如下子問(wèn)題： （1-1）（a，0，b，0），F(xiàn)，Gf2） （1-2）（S11，F(xiàn)

29、，f2（S11） （本原問(wèn)題） （1-3） （f2（S11），F(xiàn)， Gf4 ） Gf2是適用于算符f2的狀態(tài)描述集合，S11 Gf2 58 現(xiàn)在必須求解問(wèn)題（1-1），所以仍需要先計(jì)算其差別。此 差別為： 猴子不在b處f1=goto（b） 與差別相關(guān) 的關(guān)鍵算符 用關(guān)鍵算符f1歸約問(wèn)題（1-1），得到如下子問(wèn)題： （1-11）（a，0，b，0），F(xiàn)，Gf1） （差別為0，本原問(wèn)題，可直接用f1求解） （1-12）（S111，F(xiàn)，f1（S111） （本原問(wèn)題） （1-13） （f1（S111），F(xiàn)， Gf2 ） Gf1是適用于算符f1的狀態(tài)描述集合，S111 Gf1 。 59 現(xiàn)在需要求解問(wèn)題（

30、1-13），由于f1（S111）=（b，0， b，0），所以問(wèn)題（1-13）變?yōu)椋?（ （b，0，b，0） ，F(xiàn)， Gf2 ） ，這個(gè)問(wèn)題也是本原問(wèn)題，可以直接用f2求解。 把先前產(chǎn)生的問(wèn)題求解過(guò)程繼續(xù)下去，直到最后解 答此初始問(wèn)題為止。 60 通過(guò)該實(shí)例分析，可以看出： 問(wèn)題（S，F(xiàn)，G）的差別差別就是用S的元對(duì)由集合G規(guī)定的目 標(biāo)進(jìn)行測(cè)試失敗原因的部分表列（如果S的某個(gè)元是在G中，那 么該問(wèn)題就獲得解決，也就不存在差別）。 例如，如果目標(biāo)集合G由某個(gè)狀態(tài)條件集合所規(guī)定，而且某 個(gè)s S滿足這些條件中的某些但不是全部條件，那么差別可由 不能被s滿足的條件的部分表列組成。如果這些條件能夠按其重

31、 要性分類(lèi)，那么應(yīng)該選擇最重要的不滿足條件作為差別。 當(dāng)把每個(gè)可能的差別與某些算符或算符集合結(jié)合起來(lái)時(shí)， 這些算符就是候選關(guān)鍵算符。只有當(dāng)應(yīng)用某個(gè)算符是與消去某 個(gè)差別相關(guān)時(shí)，該算符才與該差別結(jié)合在一起。 61 4. 謂詞邏輯法 謂詞邏輯表示法的邏輯基礎(chǔ) 1）.命題與真值 2）.論域和謂詞 3）.連接詞和量詞 4）.項(xiàng)與合式公式 二.謂詞邏輯表示方法 三.謂詞邏輯的應(yīng)用 四.謂詞表示的特性 62 謂詞邏輯表示法是一種基于數(shù)理邏輯的知識(shí)表示方式。數(shù) 理邏輯是一門(mén)研究推理的科學(xué)，它作為人工智能的基礎(chǔ)，在人 工智能的發(fā)展中占有重要地位。人工智能中用到的邏輯可分為 兩大類(lèi)：一類(lèi)是一階經(jīng)典命題邏輯和謂詞

32、邏輯；另一類(lèi)是除經(jīng) 典邏輯以外的那些邏輯。 這里所說(shuō)的謂詞邏輯法涉及一階經(jīng)典命題邏輯和謂詞邏輯。 63 一階謂詞邏輯知識(shí)表示中所需要的邏輯基礎(chǔ)包括： 命題、謂詞、連詞、量詞、謂詞公式等。 邏輯推理所需要的邏輯基礎(chǔ)部分放到“邏輯推理” 章討論。 一. 謂詞邏輯表示法的邏輯基礎(chǔ) 64 1命題與真值 定義：一個(gè)陳述句稱(chēng)為一個(gè)斷言。凡有真假意義的斷言稱(chēng) 為命題。 命題的意義通常稱(chēng)為真值，它只有真假兩種情況。當(dāng)命題 的意義為真時(shí)，則稱(chēng)該命題的真值為真，記為T(mén)；反之，則稱(chēng)該 命題的真值為假，記為F。在命題邏輯中，命題通常用大寫(xiě)的英 文字母來(lái)表示。 一個(gè)命題不能同時(shí)既為真又為假。 例如： “天安門(mén)城樓在長(zhǎng)安

33、街的北邊” 是一個(gè)真值為T(mén)的命題 “天安門(mén)廣場(chǎng)在長(zhǎng)安街的北邊” 則是一個(gè)真值為F的命 題 65 關(guān)于命題： 一個(gè)命題可在一定條件下為真，在另一種條件下為假。例 如，命題“北京今天有雨”，需要根據(jù)當(dāng)天的實(shí)際情況來(lái)決 定其真值。 沒(méi)有真假意義的感嘆句、疑問(wèn)句等都不是命題。例如， “今天好冷??！”和“今天的溫度有多少度？”都不是命題。 命題的優(yōu)點(diǎn)是簡(jiǎn)單、明確；其主要缺點(diǎn)是無(wú)法描述客觀事 物的結(jié)構(gòu)及其邏輯特征，也無(wú)法表示不同事物間的共性。 66 2論域和謂詞 論域是由所討論對(duì)象全體構(gòu)成的非空集合。論域中的元素稱(chēng) 為個(gè)體，論域也常稱(chēng)為個(gè)體域。例如，整數(shù)的個(gè)體域是由所有整 數(shù)構(gòu)成的集合，每個(gè)整數(shù)都是該個(gè)體

34、域中的一個(gè)個(gè)體。 在謂詞邏輯中，命題是用謂詞來(lái)表示的。一個(gè)謂詞可分為謂 詞名和個(gè)體兩部分。其中，個(gè)體是命題中的主語(yǔ)，用來(lái)表示某個(gè) 獨(dú)立存在的事物或者某個(gè)抽象的概念；謂詞名是命題的謂語(yǔ)，用 來(lái)表示個(gè)體的性質(zhì)、狀態(tài)或個(gè)體之間的關(guān)系等。 例如，對(duì)于命題“王宏是學(xué)生”可用謂詞表示為STUDENT（ Wanghong）。其中，Wanghong是個(gè)體，代表王宏；STUDENT是謂詞 名，說(shuō)明王宏是學(xué)生的這一特征。通常，謂詞名用大寫(xiě)英文字母 表示，個(gè)體用小寫(xiě)英文字母表示。 67 謂詞定義： 定義：設(shè)D是個(gè)體域，P：DnT，F(xiàn)是一個(gè)映射，其中 Dn =(x1,x2,xn)|x1,x2,xnD 則稱(chēng)P是一個(gè)n元

35、謂詞（n=1,2,）,記為P(x1,x2,xn)。其中 ,x1,x2,xn 為個(gè)體變?cè)?在謂詞中，個(gè)體可以是常量、變?cè)蚝瘮?shù)。 例如，“x6”，可用謂詞表示為Greater（x，6）,其中x是 變?cè)?。再如，“王宏的父親是教師”可用謂詞表示為T(mén)EACHER（ father（Wanghong)，其中 father（Wanghong）是一個(gè)函數(shù)。 68 函數(shù)定義： 定義：設(shè) D是個(gè)體域，f：DnD是一個(gè)映射，則稱(chēng) f是 D上 的一個(gè) n元函數(shù)，記作: f(x1,x2,xn) (n=1,2,) 其中X1，X2，Xn是個(gè)體變?cè)?謂詞和函數(shù)從形式上看很相似，容易混淆。但它們是兩 個(gè)完全不同的概念。謂詞

36、的真值是真和假，而函數(shù)無(wú)真值可 言，其值是個(gè)體域中的某個(gè)個(gè)體。謂詞實(shí)現(xiàn)的是從個(gè)體域中 的個(gè)體到T或F的映射，而函數(shù)所實(shí)現(xiàn)的是同一個(gè)體域中從一 個(gè)個(gè)體到另一個(gè)個(gè)體的映射。在謂詞邏輯中，函數(shù)本身不能 單獨(dú)使用，它必須嵌入到謂詞之中。 69 在謂詞P(x1,x2,xn)中，如果xi(i=1,2,n) 都是個(gè) 體常量、變?cè)蚝瘮?shù)，稱(chēng)它為一階謂詞。如果某個(gè)xi本身又 是一個(gè)一階謂詞，則稱(chēng)它為二階謂詞。 只討論一階謂詞 70 3. 連接詞和量詞 在一階謂詞邏輯中共有5個(gè)連接詞和2個(gè)量詞。命題邏輯可 看作謂詞邏輯的一種特殊形式，一階謂詞邏輯中的5個(gè)連接詞 也都適應(yīng)于命題邏輯，但2個(gè)量詞僅適應(yīng)于謂詞邏輯。 7

37、1 （1）連接詞 連接詞是用來(lái)連接簡(jiǎn)單命題，并由簡(jiǎn)單命題構(gòu)成復(fù)合命題的邏輯 運(yùn)算符號(hào)。包括： ：稱(chēng)為“非“或者“否定”。它表示對(duì)其后面的命題的否定，使該 命題的真值與原來(lái)相反。例如，對(duì)命題P，若其原來(lái)的真值為T(mén)，則P （讀作非P）的真值為F；若其原來(lái)的真值為F，則P的真值為T(mén) ：稱(chēng)為“析取”。它表示所連結(jié)的兩個(gè)命題之間具有“或”的關(guān)系 ：稱(chēng)為“合取”。它表示所連結(jié)的兩個(gè)命題之間具有“與”的關(guān)系 ：稱(chēng)為“條件”或“蘊(yùn)含”。它表示“若則”的語(yǔ)義。 例如，對(duì)命題 P和 Q，蘊(yùn)含式 PQ表示“P蘊(yùn)含Q”，讀作“如果P， 則Q”，其中P稱(chēng)為條件的前件，Q稱(chēng)為條件的后件。 ：稱(chēng)為“雙條件”。它表示“當(dāng)且僅

38、當(dāng)”的語(yǔ)義。例如，對(duì)命題 P和Q， PQ表示“P當(dāng)且僅當(dāng) Q”，即讀作“P當(dāng)且僅當(dāng) Q”。 72 對(duì)以上連接詞的定義，可用下表所給出的謂詞邏輯真值表 來(lái)表示： P QPPQPQPQPQ TTFTTTT TFFTFFF FTTTFTF FFTFFTT 73 （2）量詞 量詞是由量詞符號(hào)和被其量化的變?cè)M成的表達(dá)式，用來(lái) 對(duì)謂詞中的個(gè)體作出量的規(guī)定。 在一階謂詞邏輯中引入了2個(gè)量詞符號(hào)，一個(gè)是全稱(chēng)量詞全稱(chēng)量詞符 號(hào)“ ”，意思是“所有的”、“任一個(gè)”；另一個(gè)是存在量詞存在量詞 符號(hào)“彐”，意思是“至少有一個(gè)”、“存在有”。 例如 X是一個(gè)全稱(chēng)量詞，表示“對(duì)論域中的所有個(gè)體?！保?讀作“對(duì)于所有x

39、”；彐x是一個(gè)存在量詞，表示“在論域中存在 個(gè)體X”，讀作“存在x”。 全稱(chēng)量詞的定義：命題（ x）P(x) 為真，當(dāng)且僅當(dāng)對(duì)論域 中的所有x，都有P（x）為真。命題（ x）P（x）為假，當(dāng)且僅 當(dāng)至少存在一個(gè)x0D，使得P（x0）為假。 存在量詞的定義：命題（彐x）P（x）為真，當(dāng)且僅當(dāng)至少 存在一個(gè)x0D，使得P（x0）為真。命題(彐x）P（x）為假，當(dāng) 且僅當(dāng)對(duì)論域中的所有x，都有P（x）為假。 74 在一階謂詞演算中，合法的表達(dá)式稱(chēng)為合式公式（即謂詞公式）。 對(duì)合式公式的定義將涉及到“項(xiàng)”的概念，下面分別給出它們的定 義。 定義：項(xiàng)滿足如下規(guī)則： （1）單獨(dú)一個(gè)個(gè)體詞是項(xiàng)； （2）若t

40、1，t2,，tn是項(xiàng)，f是n元函數(shù)，則f(t1,t2,tn)是 項(xiàng)； （3）由（1）、（2）生成的表達(dá)式是項(xiàng)。 可見(jiàn)，項(xiàng)是把個(gè)體常量、個(gè)體變量和函數(shù)統(tǒng)一起來(lái)的概念。 定義：原子謂詞公式的含義為： 若t1，t2，tn是項(xiàng)，P是謂詞符號(hào)，則稱(chēng) P（ t1,t2,tn ）為原子謂詞公式。 4.項(xiàng)與合式公式 75 定義：滿足如下規(guī)則的謂詞演算可得到合式公式： （1）單個(gè)原子謂詞公式是合式公式； （2）若A是合式公式，則A也是合式公式； （3）若A、B都是合式公式，則AB，AB，AB， AB也都是合式公式； （4）若A是合式公式，x是項(xiàng)，則（ x)A和(彐x）A也都 是合式公式。 這個(gè)定義是合式公式的形

41、成規(guī)則，按照這些規(guī)則可以形 成任意復(fù)雜的合式公式。例如，P（x，y）Q（y)，( x） (A（x）B（x) ，（彐x）A(x）（ y）R（x，y）B （y）都是合式公式。 在合式公式中，連接詞之間的優(yōu)先級(jí)別是： ， 76 當(dāng)一個(gè)謂詞公式含有量詞時(shí)，區(qū)分個(gè)體變?cè)欠袷芰吭~ 的約束是很重要的。 位于量詞后面的單個(gè)謂詞或者用括號(hào)括起來(lái)的合式公式 稱(chēng)為該量詞的轄域，轄域內(nèi)與量詞中同名的變?cè)Q(chēng)為約束變 元，不受約束的變?cè)Q(chēng)為自由變?cè)?例如： （ x)(P(x,y)Q(x,y) R(x,y) 5.自由變?cè)图s束變?cè)?77 謂詞邏輯不僅可以用來(lái)表示事物的狀態(tài)、屬性、概念等事實(shí) 性知識(shí)，也可以用來(lái)表示事物的

42、因果關(guān)系，即規(guī)則。 對(duì)事實(shí)性知識(shí)，通常是用否定、析取或合取符號(hào)連接起來(lái)的 謂詞公式表示。 對(duì)事物間的因果關(guān)系，通常用蘊(yùn)含式表示，例如，對(duì)“如果 x，則y”,可表示為“xy”。 當(dāng)用謂詞邏輯表示知識(shí)時(shí)，首先需要根據(jù)所表示的知識(shí)定義 謂詞，然后再用連接詞或量詞把這些謂詞連結(jié)起來(lái)，形成一個(gè)謂 詞公式。 二. 謂詞邏輯表示方法 78 此時(shí)，該知識(shí)可用謂詞表示為： ( x)(彐y)(PERSON（x）HASFATHER(x,y) 例1：用謂詞邏輯表示知識(shí)“每個(gè)人都有一個(gè)父親” 首先定義謂詞：PERSON（x）：表示x是人。 HASFATHER(x,y) ：表示x有父親y。 79 首先定義謂詞： TEAC

43、HER（x）：表示x是教師。 STUDENT（y）：表示y是學(xué)生。 TEACHES（x，y）：表示x是y的老師。 例2：用謂詞邏輯表示知識(shí)“所有教師都有自己的學(xué)生” 此時(shí)，該知識(shí)可用謂詞表示為： ( x)(彐y)(TEACHER(x) TEACHES(x,y) STUDENT(y) 該謂詞公式可讀作：對(duì)所有x，如果x是一個(gè)教師，那 么一定存在一個(gè)個(gè)體y，x是y的老師，且y是一個(gè)學(xué)生。 80 首先定義謂詞：I（x）：x是整數(shù)。 E（x）：x是偶數(shù)。 O（x）：x是奇數(shù)。 此時(shí)，該知識(shí)可用謂詞表示為： （ x）(I(x) E(x) O(x) 例3：用謂詞邏輯表示知識(shí)“所有的整數(shù)不是偶數(shù)就是奇數(shù)”

44、81 首先定義謂詞： COMPUTER（x）：表示x是計(jì)算機(jī)系的學(xué)生。 CLASSMATE（x，y）：表示x是y的同班同學(xué)。 LIKE（x，y）：表示x喜歡y。 例4：用謂詞邏輯表示如下知識(shí)： 王宏是計(jì)算機(jī)系的一名學(xué)生。 李明是王宏的同班同學(xué)。 凡是計(jì)算機(jī)系的學(xué)生都喜歡編程序。 此時(shí)，可用謂詞公式把上述知識(shí)表示為： COMPUTER（Wanghong）. CLASSMATE（Liming，Wanghong）. （ x）（COMPUTER（x) LIKE(x,programing). 82 例：機(jī)器人移盒子問(wèn)題 設(shè)在一房間里，c處有一個(gè)機(jī)器人，a和b處各有一張桌子，分 別稱(chēng)為a桌和b桌，a桌子上

45、有一盒子。要求機(jī)器人從c處出發(fā)把盒 子從a桌上拿到b桌上，然后再回到c處。請(qǐng)用謂詞邏輯來(lái)描述機(jī)器 人的行動(dòng)過(guò)程。 前面討論了一階謂詞邏輯的基礎(chǔ)和邏輯知識(shí)表示方法，為 加深對(duì)這些內(nèi)容的理解，下面舉個(gè)邏輯表示法的應(yīng)用例子。 A B C 三. 謂詞邏輯表示的應(yīng)用 83 在這個(gè)例子中，不僅要用謂詞公式來(lái)描述事物的狀態(tài)、 位置，而且還要用謂詞公式表示動(dòng)作。為此，需要定義如下 謂詞公式： TABLE(x): x是桌子 EMPTY(y): y手中是空的 AT(y,z): y在z的附近 HOLDS(y,w): y拿著w ON（w，x）： w在x桌面上。 其中： x的個(gè)體域是： y的個(gè)體域是： z的個(gè)體域是：

46、w的個(gè)體域是： a a，b b robotrobot a a，b b，c c box box 84 問(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） 使用規(guī)則！使用規(guī)則！ 85 機(jī)器人行動(dòng)的目標(biāo)是把問(wèn)題的初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)，而 要實(shí)現(xiàn)問(wèn)題狀態(tài)的轉(zhuǎn)換需要完成一系列的操作。對(duì)于每個(gè)操作， 一般都可分為條件和動(dòng)作兩個(gè)部分： 條件部分用來(lái)說(shuō)明執(zhí)行該操作必須具備的先決條件， 動(dòng)作部分給出了該操作對(duì)問(wèn)題狀態(tài)

47、的改變情況。 條件部分可用謂詞公式來(lái)表示，動(dòng)作部分則是通過(guò)在執(zhí)行該 操作前的問(wèn)題狀態(tài)中刪去和增加相應(yīng)的謂詞來(lái)實(shí)現(xiàn)的 在本問(wèn)題中，機(jī)器人需要執(zhí)行以下三個(gè)操作： Goto（x，y）：從x處走到y(tǒng)處。 Pickup（x）：在x處拿起盒子。 Setdown（x）：在x處放下盒子。 86 這三個(gè)操作對(duì)應(yīng)的條件與動(dòng)作如下： Goto（x,y） 條件： AT（robot,x） 動(dòng)作：刪除表： AT（robot,x） 添加表： AT（robot,y） Pickup（x） 條件：ON（box,x），TABLE（x）， AT（robot,x），EMPTY（robot） 動(dòng)作：刪除表：EMPTY（robot）， O

48、N（box，x） 添加表：HOLDS（robot,box） Setdown（x） 條件：AT（robot,x），TABLE（x）， HOLDS（robot,box） 動(dòng)作：刪除表：HOLDS（robot,box） 添加表：EMPTY（robot）， ON（box,x） 87 機(jī)器人在執(zhí)行每一操作之前，都需要檢查當(dāng)前狀態(tài)是否 可以滿足該操作的先決條件。如果滿足，就執(zhí)行相應(yīng)的操作， 否則就檢查下一個(gè)操作所要求的先決條件。 作為謂詞邏輯知識(shí)表示方法的應(yīng)用，下面給出這個(gè)機(jī)器 人行動(dòng)規(guī)劃問(wèn)題的求解過(guò)程。其中，在檢查先決條件是否滿 足時(shí)還需要進(jìn)行變量的置換。 88 狀態(tài)l（初始狀態(tài)） AT(robot,c

49、) 開(kāi)始 EMPTY（robot） = ON（box，a） TABLE（a） TABLE（b） Goto（x，y） = 用 c代換 x，a代換 y 狀態(tài)2 AT（robot,a） EMPTY（robot） ON（box,a） TABLE（a） TABLE（b） Pickup（x） 用a代換x 狀態(tài)3 AT（robot，a） HOLDS（robot，box） TABLE（a） TABLE（b） Goto（x，y） 用a代換x，b代換y 狀態(tài)4 AT（robot，b） HOLDS（robot，box） TABLE（a） TABLE（b） Setdown（x） = 用b代換x 狀態(tài)5 AT(robo

50、t,b) EMPTY（robot） ON(box,b) TABLE（a） TABLE（b） Goto（x，y） = 用b代換x，c代換y 狀態(tài)6（目標(biāo)狀態(tài)） AT（robot，c） EMPTY（robot） ON(box,b) TABLE（a） TABLE（b） 89 邏輯知識(shí)表示的主要特點(diǎn)是建立在某種形式邏輯的基礎(chǔ)上， 并利用了邏輯方法研究推理的規(guī)律，即條件與結(jié)論之間的蘊(yùn)含 關(guān)系。邏輯表示法的主要優(yōu)點(diǎn)包括： （1）自然 一階謂詞邏輯是一種接近于自然語(yǔ)言的形式語(yǔ)言系統(tǒng)，謂 詞邏輯表示法接近于人們對(duì)問(wèn)題的直觀理解，易于被人們接受。 （2）明確 邏輯表示法對(duì)如何由簡(jiǎn)單陳述句構(gòu)造復(fù)雜陳述句的方法有

51、明確規(guī)定，如連接詞、量詞的用法與含義等。對(duì)于用邏輯表示 法表示的知識(shí)，人們都可以按照一種標(biāo)準(zhǔn)的方法去解釋它，因 此用這種方法表示的知識(shí)明確、易于理解。 四. 謂詞邏輯表示的特性 90 （3）精確 謂詞邏輯是一種二值邏輯，其謂詞公式的真值只有“真” 與“假”，因此可用來(lái)表示精確知識(shí)，并可保證經(jīng)演演繹推 理所得結(jié)論的精確性。 （4）靈活 邏輯表示法把知識(shí)和處理知識(shí)的程序有效地分開(kāi)。在使 用這種方法表示知識(shí)時(shí)，無(wú)須考慮程序中處理知識(shí)的細(xì)節(jié)。 （5）模塊化 在邏輯表示法中，各條知識(shí)都是相對(duì)獨(dú)立的，它們之 間不直接發(fā)生聯(lián)系。因此添加、刪除、修改知識(shí)的工作比 較容易進(jìn)行。 91 邏輯表示法也存在一些不足，

52、其主要缺點(diǎn)如下： （1）知識(shí)表示能力差 邏輯表示法只能表示確定性知識(shí)，而不能表示非確定性知識(shí)， 如不精確、模糊性知識(shí)。實(shí)際上，人類(lèi)的大部分知識(shí)都不同程度地 具有不確定性，使得它表示知識(shí)的范圍和能力受到了一定的限制。 另外，邏輯表示法還難以表示過(guò)程性知識(shí)和啟發(fā)性知識(shí)。 （2）知識(shí)庫(kù)管理困難 邏輯表示法缺乏知識(shí)的組織原則，利用這種表示法所形成的知 識(shí)庫(kù)管理比較困難。 （3）存在組合爆炸 由于邏輯表示法難以表示啟發(fā)性知識(shí)，因此在推理過(guò)程中只能 盲目地使用推理規(guī)則。當(dāng)系統(tǒng)知識(shí)量較大時(shí)，容易發(fā)生組合爆炸。 （4）系統(tǒng)效率低 邏輯表示法的推理過(guò)程是根據(jù)形式邏輯進(jìn)行的。它把推理演算 與知識(shí)含義截然分開(kāi)，拋棄

53、了表達(dá)內(nèi)容中所含有的語(yǔ)義信息，往往 使推理過(guò)程冗長(zhǎng)，降低了系統(tǒng)效率。 92 設(shè)機(jī)器人有一只機(jī)械手，要處理的世界有一張桌子，桌上可 堆放若干相同的方積木塊。積木世界的布局如下圖所示。 練習(xí)題：機(jī)器人摞積木問(wèn)題 B 機(jī)械手機(jī)械手 A C C B A 初始初始 目標(biāo)目標(biāo) 提示：機(jī)械手有4個(gè)操作積木的典型動(dòng)作： 從桌面上揀起一塊積木；將手中的積木放到桌面上； 在積木上再摞上一塊積木；從積木上面揀起一塊積木。 93 5. 語(yǔ)義網(wǎng)絡(luò)法 語(yǔ)義網(wǎng)絡(luò)的基本概念 1）.什么是語(yǔ)義網(wǎng)絡(luò) 2）.語(yǔ)義的基本關(guān)系 二.事物和概念的表示 三.情景和動(dòng)作的表示 四.邏輯關(guān)系的表示 五.語(yǔ)義網(wǎng)絡(luò)的推理過(guò)程 94 語(yǔ)義網(wǎng)絡(luò)是奎廉

54、（JRQullian）1968年在研究人類(lèi)聯(lián) 想記憶時(shí)提出的一種心理學(xué)模型，他認(rèn)為記憶是由概念間的 聯(lián)系實(shí)現(xiàn)的。隨后，奎廉又把它用作知識(shí)表示。 1972年，西蒙在自然語(yǔ)言理解系統(tǒng)中也采用了語(yǔ)義網(wǎng)絡(luò) 表示法。 1975年，亨德里克（GGHendrix）對(duì)全稱(chēng)量詞的表示 提出了語(yǔ)義網(wǎng)絡(luò)分區(qū)技術(shù)。 目前，語(yǔ)義網(wǎng)絡(luò)已成為人工智能中應(yīng)用較多的一種知識(shí) 表示方法。 95 語(yǔ)義網(wǎng)絡(luò)是一種用實(shí)體及其語(yǔ)義關(guān)系來(lái)表達(dá)知識(shí)的有向圖。 其中，結(jié)點(diǎn)代表實(shí)體結(jié)點(diǎn)代表實(shí)體，表示各種事物、概念、情況、屬性、狀態(tài)、 事件、動(dòng)作等；弧線代表語(yǔ)義關(guān)系弧線代表語(yǔ)義關(guān)系，表示它所連結(jié)的兩個(gè)實(shí)體之 間的語(yǔ)義聯(lián)系。 在語(yǔ)義網(wǎng)絡(luò)中，每一個(gè)結(jié)

55、點(diǎn)和弧都必須帶有標(biāo)識(shí)，這些標(biāo)識(shí) 用來(lái)說(shuō)明它所代表的實(shí)體或語(yǔ)義。 一. 語(yǔ)義網(wǎng)絡(luò)的基本概念 1. 什么是語(yǔ)義網(wǎng)絡(luò) 96 從結(jié)構(gòu)上看，語(yǔ)義網(wǎng)絡(luò)一般是由一些最基本的語(yǔ)義單元 構(gòu)成的，這種最基本的語(yǔ)義單元被稱(chēng)為語(yǔ)義基元語(yǔ)義基元。一個(gè)語(yǔ)義 基元可用如下三元組： （結(jié)點(diǎn)1，弧，結(jié)點(diǎn)2） 來(lái)表示。對(duì)該三元組，如果用A、B分別表示其中的兩個(gè)結(jié)點(diǎn)， 用R表示A與B之間的某種語(yǔ)義聯(lián)系，則它所對(duì)應(yīng)的基本網(wǎng)元表 示為： AB R 97 當(dāng)把多個(gè)語(yǔ)義基元用相應(yīng)的語(yǔ)義聯(lián)系關(guān)聯(lián)在一起時(shí)，就 形成了一個(gè)語(yǔ)義網(wǎng)絡(luò)。在語(yǔ)義網(wǎng)絡(luò)中，弧的方向是有意義的 ，不能隨意調(diào)換。 鴕鳥(niǎo)鴕鳥(niǎo) 鳥(niǎo)鳥(niǎo) 是一種 例：用語(yǔ)義基元描述“鴕鳥(niǎo)是一種鳥(niǎo)”這一

56、事實(shí)。 由于“鴕鳥(niǎo)”與“鳥(niǎo)”之間的語(yǔ)義聯(lián)系為“是一種”，因此 在此語(yǔ)義網(wǎng)絡(luò)中，弧被標(biāo)識(shí)為“是一種”。如下圖。 98 語(yǔ)義網(wǎng)絡(luò)表示和謂詞邏輯表示之間有一定的對(duì)應(yīng)表示能力。從 邏輯表示來(lái)看，一個(gè)語(yǔ)義網(wǎng)絡(luò)相當(dāng)于一組二元謂詞。 因?yàn)槿M（結(jié)點(diǎn)1，弧，結(jié)點(diǎn)2）可寫(xiě)成P（個(gè)體1，個(gè)體2）， 其中結(jié)點(diǎn)1、結(jié)點(diǎn)2分別對(duì)應(yīng)個(gè)體1、個(gè)體2，而孤及其上的標(biāo)識(shí)是由 謂詞P來(lái)體現(xiàn)的。 雪雪 白色白色 顏色顏色 顏色顏色( ( 雪雪, , 白色白色) ) 99 從功能上講，語(yǔ)義網(wǎng)絡(luò)可以描述任何事物間的任意復(fù)雜關(guān) 系。但是，這種描述是通過(guò)把許多基本的語(yǔ)義關(guān)系關(guān)聯(lián)到一起 來(lái)實(shí)現(xiàn)的。 基本語(yǔ)義關(guān)系是構(gòu)成復(fù)雜語(yǔ)義關(guān)系的基石，也

57、是語(yǔ)義網(wǎng)絡(luò) 知識(shí)表示的基礎(chǔ)。但由于基本語(yǔ)義關(guān)系的多樣性和靈活性，因 此又不可能對(duì)其進(jìn)行全面討論。作為參考，下面給出的僅是一 些最常用的基本語(yǔ)義關(guān)系。 2. 基本的語(yǔ)義關(guān)系 100 （1）類(lèi)屬關(guān)系 類(lèi)屬關(guān)系是指具有共同屬性的不同事物間的分類(lèi)關(guān)系、成員 關(guān)系或?qū)嵗P(guān)系。它體現(xiàn)的是“具體與抽象”、“個(gè)體與集體” 的概念。類(lèi)屬關(guān)系的一個(gè)最主要特征是屬性的繼承性，處在具體 層的結(jié)點(diǎn)可以繼承抽象層結(jié)點(diǎn)的所有屬性。常用的類(lèi)屬關(guān)系有： AKind-of：含義為“是一種”，表示一個(gè)事物是另一個(gè)事 物的一種類(lèi)型。 A-Member-of：含義為“是一員”，表示一個(gè)事物是另一個(gè)事 物的一個(gè)成員。 isa：含義為“是

58、一個(gè)”，表示一個(gè)事物是另一個(gè)事物的一 個(gè)實(shí)例。 101 例如：分類(lèi)關(guān)系“鳥(niǎo)是一種動(dòng)物”可用下圖所示的語(yǔ)義網(wǎng)絡(luò)來(lái)表 示。它說(shuō)明鳥(niǎo)是動(dòng)物的一種類(lèi)型，并可繼承動(dòng)物的所有屬性。 鳥(niǎo)類(lèi) 動(dòng)物 A-Kind-ofA-Kind-of 分類(lèi)關(guān)系分類(lèi)關(guān)系 張強(qiáng) 共青團(tuán) A-Memder-ofA-Memder-of 成員關(guān)系成員關(guān)系 李剛 人 is-ais-a 實(shí)例關(guān)系實(shí)例關(guān)系 實(shí)例關(guān)系“李剛是人”可用下圖所示的語(yǔ)義網(wǎng)絡(luò)來(lái)表示。 成員關(guān)系“張強(qiáng)是共青團(tuán)員”可用下圖所示的語(yǔ)義網(wǎng)絡(luò)來(lái)表示。 在類(lèi)屬關(guān)系中，具體層結(jié)點(diǎn)除具有抽象層結(jié)點(diǎn)的所有屬性外，還可以 增加一些自己的個(gè)性，甚至還能夠?qū)Τ橄髮咏Y(jié)點(diǎn)的某些屬性加以更改。例

59、如，所有的動(dòng)物都具有能運(yùn)動(dòng)、會(huì)吃等屬性。而鳥(niǎo)類(lèi)作為動(dòng)物的一種，除 具有動(dòng)物的這些屬性外，還具有會(huì)飛、有翅膀等個(gè)性。 102 （2）包含關(guān)系 包含關(guān)系也稱(chēng)為聚類(lèi)關(guān)系，是指具有組織或結(jié)構(gòu)特征 的“部分與整體”之間的關(guān)系。它和類(lèi)屬關(guān)系的最主要區(qū) 別是包含關(guān)系一般不具備屬性的繼承性。常用的包含關(guān)系 是： Partof：含義為“是一部分”，表示一個(gè)事物是另 一個(gè)事物的一部分。 103 例如，“大腦是人的一部分”可用下圖所示的語(yǔ)義網(wǎng)絡(luò)來(lái)表示。 黑板 墻 Part-ofPart-of 包含關(guān)系包含關(guān)系 大腦 人體 Part-ofPart-of 包含關(guān)系包含關(guān)系 再如，“黑板是墻的一部分”可用下圖來(lái)表示。 對(duì)

60、于這兩個(gè)例子，從繼承性的角度看，大腦不一定具有人的 各種屬性，黑板也不具有墻的各種屬性。 104 （3）屬性關(guān)系 屬性關(guān)系是指事物和其屬性之間的關(guān)系。常用的屬性關(guān)系有： Have：含義為“有”，表示一個(gè)結(jié)點(diǎn)具有另一個(gè)結(jié)點(diǎn)所描述的 屬性。 Can：含義是“能”、“會(huì)”，表示一個(gè)結(jié)點(diǎn)能做另一個(gè)結(jié)點(diǎn) 的事情。 例如，“鳥(niǎo)有翅膀”可用下圖所示的語(yǔ)義網(wǎng)絡(luò)來(lái)表示。 鳥(niǎo) 翅膀 HaveHave 屬性關(guān)系屬性關(guān)系 105 （4）時(shí)間關(guān)系 時(shí)間關(guān)系是指不同事件在其發(fā)生時(shí)間方面的先后次序關(guān)系 。常用的時(shí)間關(guān)系有： before：含義為“在前”，表示一個(gè)事件在另一個(gè)事件之 前發(fā)生。 after：含義為“在后”，表示