人工智能1ppt課件

1,第二部分知識(shí)表示方法,2,知識(shí)是一切智能行為的基礎(chǔ)，也是人工智能的重要研究對(duì)象。要使計(jì)算機(jī)具有智能，就必須使它具有知識(shí)，而要使計(jì)算機(jī)具有知識(shí)，首先必須解決知識(shí)的表示問題。知識(shí)表示包括知識(shí)表示的概念和知識(shí)表示方法。對(duì)知識(shí)表示方法，又可根據(jù)所表示知識(shí)的確定化程度，分為確定性知識(shí)表示和不確定性知識(shí)表示。,3,知識(shí)與知識(shí)表示的概念狀態(tài)空間法問題規(guī)約法謂詞邏輯法語義網(wǎng)絡(luò)法框架表示法,內(nèi)容提要,4,1.知識(shí)與知識(shí)表示的概念,知識(shí)1）.知識(shí)的屬性2）.知識(shí)的類型二.知識(shí)表示1）.知識(shí)表示的要求2）.知識(shí)表示觀點(diǎn)3）.知識(shí)表示的方法,5,知識(shí)是人們?cè)诟脑炜陀^世界的實(shí)踐中積累起來的認(rèn)識(shí)和經(jīng)驗(yàn)。通常，人們對(duì)客觀世界的描述是通過數(shù)據(jù)和信息來實(shí)現(xiàn)的。數(shù)據(jù)和信息是兩個(gè)密切相關(guān)的概念。數(shù)據(jù)是信息的載體和表示，信息是數(shù)據(jù)在特定場(chǎng)合下的含義，或者說信息是數(shù)據(jù)的語義。,一.知識(shí),6,知識(shí)是對(duì)信息進(jìn)行智能性加工所形成的對(duì)客觀世界規(guī)律性的認(rèn)識(shí)。把有關(guān)信息關(guān)聯(lián)在一起所形成的信息結(jié)構(gòu)稱為知識(shí)。“信息”與“關(guān)聯(lián)”是構(gòu)成知識(shí)的兩個(gè)要素。,信息之間關(guān)聯(lián)的形式可以多種多樣，其中最常用的一種形式是：如果，那么。例如，“如果他學(xué)過人工智能課程，那么他應(yīng)該知道什么叫知識(shí)”。,7,（1）真假性與相對(duì)性,1）.知識(shí)的屬性：,真假性是指可以通過實(shí)踐或推理來證明知識(shí)為真或?yàn)榧佟Ｏ鄬?duì)性是指知識(shí)的真與假是相對(duì)于某些條件、環(huán)境及時(shí)間而言的，即知識(shí)一般不是無條件的真或無條件的假，而是相對(duì)于一定條件的。,8,知識(shí)的不確定性包括不完備性、不確定性與模糊性：,（2）不確定性,知識(shí)的不完備性是指在解決問題時(shí)不具備解決該問題所需要的全部知識(shí)。知識(shí)的不確定性是指知識(shí)所具有的既不能完全被確定為真，又不能完全被確定為假的特性。知識(shí)的模糊性是指知識(shí)的“邊界”不明確的特性。,9,矛盾性是指同一個(gè)知識(shí)集中的不同知識(shí)之間相互對(duì)立或不一致，即從這些知識(shí)出發(fā)，會(huì)推出不一致的結(jié)論。相容性是指同一個(gè)知識(shí)集中的所有知識(shí)之間互相不矛盾。,（3）矛盾性和相容性,10,可表示性是指知識(shí)可以用適當(dāng)?shù)男问奖硎境鰜?。例如語言、文字、圖形、神經(jīng)元網(wǎng)絡(luò)等?？衫眯允侵钢R(shí)可以被用來解決各種各樣的問題。,（4）可表示性與可利用性,11,（1）按知識(shí)的性質(zhì)：,2）.知識(shí)的類型：,概念命題公理定理規(guī)則方法,12,常識(shí)性知識(shí)：是指通用通識(shí)的知識(shí)。即人們普遍知道的、適應(yīng)于所有領(lǐng)域的知識(shí)。領(lǐng)域性知識(shí)：是指面向某個(gè)具體專業(yè)的專業(yè)性知識(shí)，這些知識(shí)只有該領(lǐng)域的專業(yè)人員才能夠掌握和運(yùn)用它。,（2）按知識(shí)的作用范圍：,13,事實(shí)性知識(shí)：也稱敘述性知識(shí)，是用來描述問題或事物的概念、屬性、狀態(tài)、環(huán)境及條件等情況的知識(shí)。過程性知識(shí)：是用來描述問題求解過程所需要的操作、演算或行為等規(guī)律性的知識(shí)，它指出在問題求解過程中如何使用那些與問題有關(guān)的事實(shí)性知識(shí)，即用來說明在那些敘述性知識(shí)成立的時(shí)候該怎么辦?？刂菩灾R(shí)：也稱元知識(shí)或超知識(shí)，是關(guān)于如何運(yùn)用已有知識(shí)進(jìn)行問題求解的知識(shí)，因此，也稱為關(guān)于知識(shí)的知識(shí)。,（3）按知識(shí)的作用,14,表層知識(shí)是指客觀事物的現(xiàn)象以及這些現(xiàn)象與結(jié)論之間關(guān)系的知識(shí)。深層知識(shí)是指事物本質(zhì)、因果關(guān)系內(nèi)涵、基本原理之類的知識(shí)。例如，理論知識(shí)、理性知識(shí)等。,（4）按知識(shí)的層次,15,確定性知識(shí)：是可以給出其真值為“真”或“假”的知識(shí)。這些知識(shí)是可以精確表示的知識(shí)。不確定性知識(shí)：是指具有“不確定”特性的知識(shí)。不確定性的概念包含不精確、不完備和模糊。,（5）按知識(shí)的確定性,16,邏輯性知識(shí)：是反映人類邏輯思維過程的知識(shí)，例如人類的經(jīng)驗(yàn)性知識(shí)。它對(duì)應(yīng)著邏輯思維。形象性知識(shí)：是通過事物的形象建立起來的知識(shí)，它對(duì)應(yīng)著形象思維。例如，一個(gè)人的相貌，要用文字來描述非常困難，但要親眼見到這個(gè)人，就很容易在頭腦中形成這個(gè)人的概念。,（6）按知識(shí)的結(jié)構(gòu)及表現(xiàn)形式,17,所謂知識(shí)表示是對(duì)知識(shí)的一種描述，即用一些約定的符號(hào)把知識(shí)編碼成一組計(jì)算機(jī)可以接受的數(shù)據(jù)結(jié)構(gòu)。所謂知識(shí)表示過程就是把知識(shí)編碼成某種數(shù)據(jù)結(jié)構(gòu)的過程。同一知識(shí)可以有多種不同的表示形式，而不同表示形式所產(chǎn)生的效果又可能不一樣。,二.知識(shí)表示,18,（1）表示能力知識(shí)表示能力是指能否正確、有效地將問題求解所需要的各種知識(shí)表示出來。知識(shí)表示能力包括以下三個(gè)方面：一是知識(shí)表示范圍的廣泛性；二是領(lǐng)域知識(shí)表示的高效性；三是對(duì)非確定性知識(shí)表示的支持程度。,1）.知識(shí)表示的要求,19,（2）可利用性知識(shí)的利用是指使用知識(shí)進(jì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)，便于直接由計(jì)算機(jī)對(duì)其進(jìn)行處理。（5）自然性與可理解性自然性是指知識(shí)表示形式要符合人們的日常習(xí)慣和思維方式?？衫斫庑允侵杆硎镜闹R(shí)應(yīng)易讀、易懂、易獲取、易維護(hù)。,21,（1）陳述性觀點(diǎn)陳述性知識(shí)表示（Declarativeknowledgerepresentation）是指以陳述的方式把知識(shí)用一定的數(shù)據(jù)結(jié)構(gòu)表示出來，即把知識(shí)看作一種特殊的數(shù)據(jù)，知識(shí)表示說明描述的對(duì)象是什么，不涉及如何運(yùn)用知識(shí)的問題。,2）.知識(shí)表示觀點(diǎn)：,22,（2）過程性觀點(diǎn)過程性知識(shí)表示（Proceduralknowledgerepresentation）是指以程序（亦稱為過程）的方式把知識(shí)表示出來，即把知識(shí)寓于程序之中，把知識(shí)表示和運(yùn)用知識(shí)結(jié)合起來。,23,知識(shí)表示方法又稱為知識(shí)表示技術(shù)，其表示形式被稱為知識(shí)表示模式。目前，使用較多的知識(shí)表示方法有:狀態(tài)空間法問題歸約法謂詞邏輯法語義網(wǎng)絡(luò)法框架表示法劇本表示法過程表示法面向?qū)ο蟊硎痉?3）.知識(shí)表示方法：,24,問題的狀態(tài)描述二.狀態(tài)圖示法三.狀態(tài)空間表示舉例,2.狀態(tài)空間法,25,對(duì)人工智能研究中運(yùn)用的問題求解方法進(jìn)行綜合分析，可以發(fā)現(xiàn)許多問題求解方法是采用試探搜索方法的。是通過在某個(gè)可能的解空間內(nèi)尋找一個(gè)解來求解問題的。這種基于解答空間的問題表示和求解方法就是狀態(tài)空間法。狀態(tài)空間法是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。,26,實(shí)例：十五數(shù)碼難題,一.問題的狀態(tài)描述,如何把初始棋局變換為目標(biāo)棋局？,27,最直接的求解方法：嘗試各種不同的走步，直到偶然得到目標(biāo)棋局為止，即試探搜索。,28,對(duì)十五數(shù)碼難題的問題描述和求解過程進(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)空間法：從某個(gè)初始狀態(tài)開始，每次加一個(gè)操作符，遞增地建立起操作符的試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止。狀態(tài)圖：初始狀態(tài)可達(dá)到的各狀態(tài)所對(duì)應(yīng)的節(jié)點(diǎn)組成的圖。,29,問題狀態(tài)的描述：狀態(tài)：為描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合，其矢量形式如下：Q=q0，q1，qn狀態(tài)變量：狀態(tài)集合中的每個(gè)元素qi（i=0,1,n）。具體狀態(tài)：給定每個(gè)分量的一組值。如Qk=q0k，q1k，qnk操作符：使問題從一種狀態(tài)變換到另一種狀態(tài)的手段，也叫算符。算符可以是走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號(hào)或邏輯符號(hào)等。問題的狀態(tài)空間：表示該問題全部可能狀態(tài)及其關(guān)系的圖。它包含三種說明的集合，即所有可能的問題初始狀態(tài)集合S、操作符集合F以及目標(biāo)狀態(tài)集合G。狀態(tài)空間可記為三元組（S，F(xiàn)，G）,30,圖論中的幾個(gè)術(shù)語：圖；有向圖；后繼節(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è)圖來表示某個(gè)狀態(tài)空間時(shí)，圖中各節(jié)點(diǎn)標(biāo)上相應(yīng)的狀態(tài)描述，而有向弧線旁邊標(biāo)上算符。尋找從一種狀態(tài)變換為另一種狀態(tài)的某個(gè)算符序列問題等價(jià)于尋找圖的某一路徑問題。,二.狀態(tài)圖示法,31,圖的顯式說明：圖中的各節(jié)點(diǎn)及其具有代價(jià)的弧線由一張圖或表明確給出。圖的隱式說明：圖中的節(jié)點(diǎn)集合是無限的，但起始節(jié)點(diǎn)是已知的，而且引入后繼算符的概念是方便的。把后繼節(jié)點(diǎn)算符作用于任一節(jié)點(diǎn)可以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線的代價(jià)。搜索某個(gè)狀態(tài)空間以求得算符序列的一個(gè)解答過程，就是使隱式圖足夠大的一部分變?yōu)轱@式以便包含目標(biāo)的過程，這是狀態(tài)空間問題求解的基礎(chǔ)。問題的表示對(duì)求解工作量有很大的影響。,32,問題的狀態(tài)表示方法涉及在狀態(tài)描述中如何應(yīng)用變量。須用一個(gè)包含變量的表達(dá)式來描述狀態(tài)的全部集合，而不僅僅描述一個(gè)狀態(tài)。用常量取代表達(dá)式中的變量，就可得到一個(gè)具體的狀態(tài)描述。用來描述一個(gè)狀態(tài)集合的含有變量的表達(dá)式，叫做狀態(tài)描述模式。,33,三.狀態(tài)空間表示舉例,實(shí)例：猴子摘香蕉問題,acb,34,問題狀態(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）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,猴子摘香蕉問題的狀態(tài)空間圖,37,練習(xí)題(野人和傳教士渡河問題）：,有3個(gè)傳教士和3個(gè)野人來到河邊，打算乘一艘小船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過河去？,38,3.問題歸約法,問題規(guī)約的描述二.與或圖表示三.問題歸約機(jī)理,39,問題歸約法：有許多問題可以通過一系列變換變?yōu)橐粋€(gè)子問題集；這些子問題的解可以直接得到；通過解決這些子問題，從而就解決了初始問題。,40,實(shí)例：梵塔問題,一.問題的歸約描述,如何由初始配置變換為目標(biāo)配置？,41,求解思路：把原始問題歸約為一個(gè)比較簡(jiǎn)單的問題的集合,要把所有圓盤都移至柱子3，必須先把圓盤C移至柱子3；而且在移動(dòng)圓盤C至柱子3之前，柱子3必須是空的。只有在移開圓盤A和B之后，才能移動(dòng)圓盤C；而且圓盤A和B不能在柱子3。因此，應(yīng)該把A和B移到柱子2上。把圓盤C從柱子1移動(dòng)到柱子3，并繼續(xù)解決其余部分的移動(dòng)問題。,（移動(dòng)A、B-2）,（移動(dòng)C-3）,（移動(dòng)A、B-3）,42,通過以上分析，把原始問題歸約為3個(gè)子問題：（1）移動(dòng)A、B-2雙圓盤問題：可進(jìn)一步歸約（2）移動(dòng)C-3單圓盤問題：可直接求解-本原問題（3）移動(dòng)A、B-3雙圓盤問題：可進(jìn)一步歸約,與或圖：可以有效說明問題歸約法的求解過程。,梵塔問題歸約圖,43,問題歸約描述：采用問題歸約法描述與求解問題，問題歸約表示由三部分組成：,（1）一個(gè)初始問題描述如：（111），（333）（2）一套把問題變換為子問題的操作符問題歸約算符如：移動(dòng)A、B-2等（3）一套本原問題描述如：（122），（322）,本原問題：是可直接求解或具有已知解答的問題，出現(xiàn)本原問題即可停止搜索。問題歸約法的實(shí)質(zhì)：從目標(biāo)（要解決的問題）出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個(gè)本原問題集合。問題歸約的目的：最終產(chǎn)生具有明顯解答的本原問題。,44,二.與或圖表示,用問題歸約法描述和求解問題的過程可以用與或圖來表示。,例如：?jiǎn)栴}A既可由求解問題B和C，也可由求解問題D、E和F，或者由單獨(dú)求解問題G來解決。這一關(guān)系可由右圖所示的結(jié)構(gòu)圖來表示。,45,為了使含有一個(gè)以上后繼問題的每個(gè)集合能夠聚集在它們各自的父輩節(jié)點(diǎn)之下，在上述結(jié)構(gòu)圖中引入附加節(jié)點(diǎn)。如右圖，可以認(rèn)為問題A被歸約為單一子問題N、M和H，N、M和H叫或節(jié)點(diǎn)。問題N被歸約為子問題B和C的單一集合，要求解N就必須求解所有的子問題，因此，B和C叫做與節(jié)點(diǎn)。各個(gè)與節(jié)點(diǎn)用跨接指向其后繼節(jié)點(diǎn)的弧線的小段圓弧加以標(biāo)記。這樣形成的結(jié)構(gòu)圖就叫與或圖。,46,關(guān)于與或圖的幾點(diǎn)說明：在與或圖中，如果一個(gè)節(jié)點(diǎn)有后繼節(jié)點(diǎn)，那么這些后繼節(jié)點(diǎn)既可全為與節(jié)點(diǎn)，也可全為或節(jié)點(diǎn)。特殊情況下，可能不出現(xiàn)任何與節(jié)點(diǎn)，如在狀態(tài)空間圖中就不存在與節(jié)點(diǎn)，即狀態(tài)空間圖是普通圖，因此可以說問題歸約法是比狀態(tài)空間法更通用的問題求解方法。通過與或圖，在某個(gè)問題描述中應(yīng)用問題歸約算符，可以依次產(chǎn)生出一個(gè)中間或節(jié)點(diǎn)和與節(jié)點(diǎn)后繼，從而可以用與或圖來表示問題歸約方法的相關(guān)結(jié)構(gòu)。在與或圖中，起始節(jié)點(diǎn)對(duì)應(yīng)于原始問題描述，葉子節(jié)點(diǎn)對(duì)應(yīng)于本原問題描述。,47,引入與或圖后，問題求解過程就轉(zhuǎn)換為與或圖上的搜索過程，搜索的目的是要表明起始節(jié)點(diǎn)有解，在與或圖中一個(gè)可解節(jié)點(diǎn)的一般定義可以歸納為：（1）葉子節(jié)點(diǎn)是可解節(jié)點(diǎ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)才是可解的。在上述定義基礎(chǔ)上，可以給出解圖的定義：解圖是那些可解節(jié)點(diǎn)的子圖，這些節(jié)點(diǎn)能夠證明其初始節(jié)點(diǎn)是可解的。,48,當(dāng)與或圖中某些非葉節(jié)點(diǎn)完全沒有后繼節(jié)點(diǎn)時(shí)，我們就說它是不可解的。這些不可解節(jié)點(diǎn)的出現(xiàn)可能意味著圖中另外一些節(jié)點(diǎn)也是不可解的。不可解節(jié)點(diǎn)的一般定義可以歸納為：（1）沒有后繼的非葉節(jié)點(diǎn)是不可解節(jié)點(diǎn)。（2）如果某個(gè)非葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后繼節(jié)點(diǎn)不可解時(shí)，該非葉節(jié)點(diǎn)才是不可解的。（3）如果某個(gè)非葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)不可解時(shí)，該非葉節(jié)點(diǎn)才是不可解的。,與狀態(tài)空間圖求解類似，一般很少用顯式圖來搜索，而是用由初始問題描述和問題歸約算符所定義的隱式圖來搜索，從而，問題求解過程實(shí)際上就是生成與或圖的足夠部分，以證明初始節(jié)點(diǎn)可解。,49,綜上所述，與或圖的構(gòu)成規(guī)則可以概括如下：（1）與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問題或問題集合，起始節(jié)點(diǎn)對(duì)應(yīng)于原始問題。（2）對(duì)應(yīng)于本原問題的節(jié)點(diǎn)，叫做葉子節(jié)點(diǎn)，它沒有后繼。（3）對(duì)于把問題歸約算符應(yīng)用于問題A的每種可能情況，都把問題變換為一個(gè)子問題的集合，有向弧線由A指向后繼節(jié)點(diǎn)，表示所求得的子問題集合。如問題A可歸約為不同的子問題集合N、M和H，只要N、M和H有一個(gè)可解，則A可解，所以N、M和H稱為或節(jié)點(diǎn)。,50,（4）對(duì)于代表兩個(gè)或兩個(gè)以上子問題集合的每個(gè)節(jié)點(diǎn)，有向弧線從該節(jié)點(diǎn)指向該子問題集合中的各個(gè)節(jié)點(diǎn)。因?yàn)橹挥挟?dāng)集合中的所有項(xiàng)都有解時(shí)，該子問題才有解，所以這些子問題節(jié)點(diǎn)叫與節(jié)點(diǎn)。為了和或節(jié)點(diǎn)進(jìn)行區(qū)分，把具有共同父輩的與節(jié)點(diǎn)后裔的所有弧線用另外一段小弧線連接起來。（5）特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問題A，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問題的某個(gè)集合時(shí)，由（3）和（4）所產(chǎn)生的圖可以得到簡(jiǎn)化，將代表子問題集合的中間或節(jié)點(diǎn)略去。利用上述規(guī)則生成的與或圖中，每個(gè)節(jié)點(diǎn)代表一個(gè)問題或問題集合，除起始節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)，所以這樣的與或圖實(shí)際是與或樹。,51,三.問題歸約機(jī)理,出發(fā)點(diǎn)引入關(guān)鍵算符：對(duì)于狀態(tài)空間的搜索問題，雖然尋求某個(gè)解答中的整個(gè)算符序列比較困難，但規(guī)定這些算符中的一個(gè)卻往往比較容易。如果某個(gè)算符被認(rèn)為是求解問題的決定性步驟，那么就很容易找到這樣一個(gè)算符。例如，梵塔難題中“移動(dòng)C-3”這個(gè)算符就是求解問題的決定性步驟，也很容易找到該算符，這種具有決定性作用的算符叫做關(guān)鍵算符。,52,關(guān)鍵算符的作用：確定了某個(gè)關(guān)鍵算符后，就可以以該關(guān)鍵算符為基礎(chǔ)進(jìn)行問題歸約。例如，在三元狀態(tài)（S，F(xiàn)，G）表示的問題中，假設(shè)F中的某個(gè)f是關(guān)鍵算符，那么可以認(rèn)為（S，F(xiàn)，G）的第一個(gè)后繼問題是一個(gè)對(duì)應(yīng)于尋找一條通向某一f適用的狀態(tài)的路徑問題，令Gf表示f適用的所有狀態(tài)的集合，則該后繼問題是由（S，F(xiàn)，Gf）描述的子問題。一旦該子問題得到解決，就可以進(jìn)一步解決由（g，F(xiàn)，f（g）所表示的子問題，其中g(shù)Gf，f（g）表示把f應(yīng)用于g而得到的狀態(tài)，因?yàn)樵撟訂栴}是僅由應(yīng)用關(guān)鍵算符f就可以解決，所以是本原問題。于是，剩下的就是解決由（f（g），F(xiàn)，G）所描述的子問題。,53,關(guān)鍵算符的作用：一旦確定了某個(gè)關(guān)鍵算符f，就可以把問題歸約為如下三個(gè)子問題：（1）（S，F(xiàn)，Gf）；（2）（g，F(xiàn)，f（g）；（3）（f（g），F(xiàn)，G）。,問題（2）是本原問題問題（1）和（3）可以用直接的狀態(tài)空間搜索技術(shù)或進(jìn)一步的問題歸約來求解（尋找子問題的關(guān)鍵算符，進(jìn)一步歸約下去）,54,關(guān)鍵算符的作用：對(duì)于許多問題，往往無法預(yù)先知道哪個(gè)算符是關(guān)鍵算符，只能推測(cè)某個(gè)算符的子集，該子集中的某個(gè)算符可能是關(guān)鍵算符。因此，用該子集中的每個(gè)算符產(chǎn)生后繼子問題，這樣就建立起了一個(gè)與或圖。,可見，要應(yīng)用這種方法，首先必須尋找狀態(tài)空間搜索問題的候選關(guān)鍵算符集合。,如何尋找候選關(guān)鍵算符呢？計(jì)算某個(gè)問題的差別,55,什么是差別？實(shí)例：猴子摘香蕉問題把4個(gè)算符的作用結(jié)果和使用條件重寫如下：,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)鍵算符和差別的歸約過程：,首先計(jì)算初始問題的差別，（a，0，b，0）不滿足目標(biāo)測(cè)試的原因在于其最后一個(gè)元素不是1。與歸約這個(gè)差別相關(guān)的關(guān)鍵算符是f4=grasp，用f4來歸約初始問題，得到如下子問題：（1）（a，0，b，0），F(xiàn)，Gf4）（2）（S1，F(xiàn)，f4（S1）（本原問題）（3）（f4（S1），F(xiàn)，G）（本原問題）其中Gf4是適用于算符f4的狀態(tài)描述集合，S1Gf4,57,要求解問題（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歸約問題（1），得到如下子問題：（1-1）（a，0，b，0），F(xiàn)，Gf2）（1-2）（S11，F(xiàn)，f2（S11）（本原問題）（1-3）（f2（S11），F(xiàn)，Gf4）Gf2是適用于算符f2的狀態(tài)描述集合，S11Gf2,58,現(xiàn)在必須求解問題（1-1），所以仍需要先計(jì)算其差別。此差別為：,猴子不在b處,f1=goto（b）,與差別相關(guān)的關(guān)鍵算符,用關(guān)鍵算符f1歸約問題（1-1），得到如下子問題：（1-11）（a，0，b，0），F(xiàn)，Gf1）（差別為0，本原問題，可直接用f1求解）（1-12）（S111，F(xiàn)，f1（S111）（本原問題）（1-13）（f1（S111），F(xiàn)，Gf2）Gf1是適用于算符f1的狀態(tài)描述集合，S111Gf1。,59,現(xiàn)在需要求解問題（1-13），由于f1（S111）=（b，0，b，0），所以問題（1-13）變?yōu)椋海╞，0，b，0），F(xiàn)，Gf2），這個(gè)問題也是本原問題，可以直接用f2求解。,把先前產(chǎn)生的問題求解過程繼續(xù)下去，直到最后解答此初始問題為止。,60,通過該實(shí)例分析，可以看出：?jiǎn)栴}（S，F(xiàn)，G）的差別就是用S的元對(duì)由集合G規(guī)定的目標(biāo)進(jìn)行測(cè)試失敗原因的部分表列（如果S的某個(gè)元是在G中，那么該問題就獲得解決，也就不存在差別）。例如，如果目標(biāo)集合G由某個(gè)狀態(tài)條件集合所規(guī)定，而且某個(gè)sS滿足這些條件中的某些但不是全部條件，那么差別可由不能被s滿足的條件的部分表列組成。如果這些條件能夠按其重要性分類，那么應(yīng)該選擇最重要的不滿足條件作為差別。當(dāng)把每個(gè)可能的差別與某些算符或算符集合結(jié)合起來時(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ù)理邏輯是一門研究推理的科學(xué)，它作為人工智能的基礎(chǔ)，在人工智能的發(fā)展中占有重要地位。人工智能中用到的邏輯可分為兩大類：一類是一階經(jīng)典命題邏輯和謂詞邏輯；另一類是除經(jīng)典邏輯以外的那些邏輯。這里所說的謂詞邏輯法涉及一階經(jīng)典命題邏輯和謂詞邏輯。,63,一階謂詞邏輯知識(shí)表示中所需要的邏輯基礎(chǔ)包括：命題、謂詞、連詞、量詞、謂詞公式等。邏輯推理所需要的邏輯基礎(chǔ)部分放到“邏輯推理”章討論。,一.謂詞邏輯表示法的邏輯基礎(chǔ),64,1命題與真值定義：一個(gè)陳述句稱為一個(gè)斷言。凡有真假意義的斷言稱為命題。命題的意義通常稱為真值，它只有真假兩種情況。當(dāng)命題的意義為真時(shí)，則稱該命題的真值為真，記為T；反之，則稱該命題的真值為假，記為F。在命題邏輯中，命題通常用大寫的英文字母來表示。一個(gè)命題不能同時(shí)既為真又為假。例如：“天安門城樓在長(zhǎng)安街的北邊”是一個(gè)真值為T的命題“天安門廣場(chǎng)在長(zhǎng)安街的北邊”則是一個(gè)真值為F的命題,65,關(guān)于命題：一個(gè)命題可在一定條件下為真，在另一種條件下為假。例如，命題“北京今天有雨”，需要根據(jù)當(dāng)天的實(shí)際情況來決定其真值。沒有真假意義的感嘆句、疑問句等都不是命題。例如，“今天好冷??！”和“今天的溫度有多少度？”都不是命題。命題的優(yōu)點(diǎn)是簡(jiǎn)單、明確；其主要缺點(diǎn)是無法描述客觀事物的結(jié)構(gòu)及其邏輯特征，也無法表示不同事物間的共性。,66,2論域和謂詞論域是由所討論對(duì)象全體構(gòu)成的非空集合。論域中的元素稱為個(gè)體，論域也常稱為個(gè)體域。例如，整數(shù)的個(gè)體域是由所有整數(shù)構(gòu)成的集合，每個(gè)整數(shù)都是該個(gè)體域中的一個(gè)個(gè)體。在謂詞邏輯中，命題是用謂詞來表示的。一個(gè)謂詞可分為謂詞名和個(gè)體兩部分。其中，個(gè)體是命題中的主語，用來表示某個(gè)獨(dú)立存在的事物或者某個(gè)抽象的概念；謂詞名是命題的謂語，用來表示個(gè)體的性質(zhì)、狀態(tài)或個(gè)體之間的關(guān)系等。例如，對(duì)于命題“王宏是學(xué)生”可用謂詞表示為STUDENT（Wanghong）。其中，Wanghong是個(gè)體，代表王宏；STUDENT是謂詞名，說明王宏是學(xué)生的這一特征。通常，謂詞名用大寫英文字母表示，個(gè)體用小寫英文字母表示。,67,謂詞定義：定義：設(shè)D是個(gè)體域，P：DnT，F(xiàn)是一個(gè)映射，其中Dn=(x1,x2,xn)|x1,x2,xnD則稱P是一個(gè)n元謂詞（n=1,2,）,記為P(x1,x2,xn)。其中,x1,x2,xn為個(gè)體變?cè)?。在謂詞中，個(gè)體可以是常量、變?cè)蚝瘮?shù)。例如，“x6”，可用謂詞表示為Greater（x，6）,其中x是變?cè)?。再如，“王宏的父親是教師”可用謂詞表示為TEACHER（father（Wanghong)，其中father（Wanghong）是一個(gè)函數(shù)。,68,函數(shù)定義：定義：設(shè)D是個(gè)體域，f：DnD是一個(gè)映射，則稱f是D上的一個(gè)n元函數(shù)，記作:f(x1,x2,xn)(n=1,2,)其中X1，X2，Xn是個(gè)體變?cè)?。謂詞和函數(shù)從形式上看很相似，容易混淆。但它們是兩個(gè)完全不同的概念。謂詞的真值是真和假，而函數(shù)無真值可言，其值是個(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ù)，稱它為一階謂詞。如果某個(gè)xi本身又是一個(gè)一階謂詞，則稱它為二階謂詞。只討論一階謂詞,70,3.連接詞和量詞在一階謂詞邏輯中共有5個(gè)連接詞和2個(gè)量詞。命題邏輯可看作謂詞邏輯的一種特殊形式，一階謂詞邏輯中的5個(gè)連接詞也都適應(yīng)于命題邏輯，但2個(gè)量詞僅適應(yīng)于謂詞邏輯。,71,（1）連接詞連接詞是用來連接簡(jiǎn)單命題，并由簡(jiǎn)單命題構(gòu)成復(fù)合命題的邏輯運(yùn)算符號(hào)。包括：稱為“非“或者“否定”。它表示對(duì)其后面的命題的否定，使該命題的真值與原來相反。例如，對(duì)命題P，若其原來的真值為T，則P（讀作非P）的真值為F；若其原來的真值為F，則P的真值為T：稱為“析取”。它表示所連結(jié)的兩個(gè)命題之間具有“或”的關(guān)系：稱為“合取”。它表示所連結(jié)的兩個(gè)命題之間具有“與”的關(guān)系：稱為“條件”或“蘊(yùn)含”。它表示“若則”的語義。例如，對(duì)命題P和Q，蘊(yùn)含式PQ表示“P蘊(yùn)含Q”，讀作“如果P，則Q”，其中P稱為條件的前件，Q稱為條件的后件。：稱為“雙條件”。它表示“當(dāng)且僅當(dāng)”的語義。例如，對(duì)命題P和Q，PQ表示“P當(dāng)且僅當(dāng)Q”，即讀作“P當(dāng)且僅當(dāng)Q”。,72,對(duì)以上連接詞的定義，可用下表所給出的謂詞邏輯真值表來表示：,73,（2）量詞量詞是由量詞符號(hào)和被其量化的變?cè)M成的表達(dá)式，用來對(duì)謂詞中的個(gè)體作出量的規(guī)定。在一階謂詞邏輯中引入了2個(gè)量詞符號(hào)，一個(gè)是全稱量詞符號(hào)“”，意思是“所有的”、“任一個(gè)”；另一個(gè)是存在量詞符號(hào)“彐”，意思是“至少有一個(gè)”、“存在有”。例如X是一個(gè)全稱量詞，表示“對(duì)論域中的所有個(gè)體?！?，讀作“對(duì)于所有x”；彐x是一個(gè)存在量詞，表示“在論域中存在個(gè)體X”，讀作“存在x”。全稱量詞的定義：命題（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á)式稱為合式公式（即謂詞公式）。對(duì)合式公式的定義將涉及到“項(xiàng)”的概念，下面分別給出它們的定義。定義：項(xiàng)滿足如下規(guī)則：（1）單獨(dú)一個(gè)個(gè)體詞是項(xiàng)；（2）若t1，t2,，tn是項(xiàng)，f是n元函數(shù)，則f(t1,t2,tn)是項(xiàng)；（3）由（1）、（2）生成的表達(dá)式是項(xiàng)?？梢?，項(xiàng)是把個(gè)體常量、個(gè)體變量和函數(shù)統(tǒng)一起來的概念。,定義：原子謂詞公式的含義為：若t1，t2，tn是項(xiàng)，P是謂詞符號(hào)，則稱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è)定義是合式公式的形成規(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)括起來的合式公式稱為該量詞的轄域，轄域內(nèi)與量詞中同名的變?cè)Q為約束變?cè)?，不受約束的變?cè)Q為自由變?cè)?。例如：（x)(P(x,y)Q(x,y)R(x,y),5.自由變?cè)图s束變?cè)?77,謂詞邏輯不僅可以用來表示事物的狀態(tài)、屬性、概念等事實(shí)性知識(shí)，也可以用來表示事物的因果關(guān)系，即規(guī)則。對(duì)事實(shí)性知識(shí)，通常是用否定、析取或合取符號(hào)連接起來的謂詞公式表示。對(duì)事物間的因果關(guān)系，通常用蘊(yùn)含式表示，例如，對(duì)“如果x，則y”,可表示為“xy”。當(dāng)用謂詞邏輯表示知識(shí)時(shí)，首先需要根據(jù)所表示的知識(shí)定義謂詞，然后再用連接詞或量詞把這些謂詞連結(jié)起來，形成一個(gè)謂詞公式。,二.謂詞邏輯表示方法,78,此時(shí)，該知識(shí)可用謂詞表示為：(x)(彐y)(PERSON（x）HASFATHER(x,y),例1：用謂詞邏輯表示知識(shí)“每個(gè)人都有一個(gè)父親”,首先定義謂詞：PERSON（x）：表示x是人。HASFATHER(x,y)：表示x有父親y。,79,首先定義謂詞：TEACHER（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ù)”,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ī)器人移盒子問題設(shè)在一房間里，c處有一個(gè)機(jī)器人，a和b處各有一張桌子，分別稱為a桌和b桌，a桌子上有一盒子。要求機(jī)器人從c處出發(fā)把盒子從a桌上拿到b桌上，然后再回到c處。請(qǐng)用謂詞邏輯來描述機(jī)器人的行動(dòng)過程。,前面討論了一階謂詞邏輯的基礎(chǔ)和邏輯知識(shí)表示方法，為加深對(duì)這些內(nèi)容的理解，下面舉個(gè)邏輯表示法的應(yīng)用例子。,A,B,C,三.謂詞邏輯表示的應(yīng)用,83,在這個(gè)例子中，不僅要用謂詞公式來描述事物的狀態(tài)、位置，而且還要用謂詞公式表示動(dòng)作。為此，需要定義如下謂詞公式：TABLE(x):x是桌子EMPTY(y):y手中是空的AT(y,z):y在z的附近HOLDS(y,w):y拿著wON（w，x）：w在x桌面上。,其中：x的個(gè)體域是：y的個(gè)體域是：z的個(gè)體域是：w的個(gè)體域是：,a，b,robot,a，b，c,box,84,問題的初始狀態(tài)：AT（robot,c）EMPTY（robot）ON（box，a）TABLE（a）TABLE（b）,問題的目標(biāo)狀態(tài)：AT（robot，c）EMPTY（robot）ON（box，b）TABLE（a）TABLE（b）,使用規(guī)則！,85,機(jī)器人行動(dòng)的目標(biāo)是把問題的初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)，而要實(shí)現(xiàn)問題狀態(tài)的轉(zhuǎn)換需要完成一系列的操作。對(duì)于每個(gè)操作，一般都可分為條件和動(dòng)作兩個(gè)部分：條件部分用來說明執(zhí)行該操作必須具備的先決條件，動(dòng)作部分給出了該操作對(duì)問題狀態(tài)的改變情況。條件部分可用謂詞公式來表示，動(dòng)作部分則是通過在執(zhí)行該操作前的問題狀態(tài)中刪去和增加相應(yīng)的謂詞來實(shí)現(xià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），ON（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ī)劃問題的求解過程。其中，在檢查先決條件是否滿足時(shí)還需要進(jìn)行變量的置換。,88,狀態(tài)l（初始狀態(tài)）AT(robot,c)開始EMPTY（robot）=ON（box，a）TABLE（a）TABLE（b）,Goto（x，y）=用c代換x，a代換y,狀態(tài)2AT（robot,a）EMPTY（robot）ON（box,a）TABLE（a）TABLE（b）,Pickup（x）用a代換x,狀態(tài)3AT（robot，a）HOLDS（robot，box）TABLE（a）TABLE（b）,Goto（x，y）用a代換x，b代換y,狀態(tài)4AT（robot，b）HOLDS（robot，box）TABLE（a）TABLE（b）,Setdown（x）=用b代換x,狀態(tài)5AT(robot,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）自然一階謂詞邏輯是一種接近于自然語言的形式語言系統(tǒng)，謂詞邏輯表示法接近于人們對(duì)問題的直觀理解，易于被人們接受。（2）明確邏輯表示法對(duì)如何由簡(jiǎn)單陳述句構(gòu)造復(fù)雜陳述句的方法有明確規(guī)定，如連接詞、量詞的用法與含義等。對(duì)于用邏輯表示法表示的知識(shí)，人們都可以按照一種標(biāo)準(zhǔn)的方法去解釋它，因此用這種方法表示的知識(shí)明確、易于理解。,四.謂詞邏輯表示的特性,90,（3）精確謂詞邏輯是一種二值邏輯，其謂詞公式的真值只有“真”與“假”，因此可用來表示精確知識(shí)，并可保證經(jīng)演演繹推理所得結(jié)論的精確性。（4）靈活邏輯表示法把知識(shí)和處理知識(shí)的程序有效地分開。在使用這種方法表示知識(shí)時(shí)，無須考慮程序中處理知識(shí)的細(xì)節(jié)。,（5）模塊化在邏輯表示法中，各條知識(shí)都是相對(duì)獨(dú)立的，它們之間不直接發(fā)生聯(lián)系。因此添加、刪除、修改知識(shí)的工作比較容易進(jìn)行。,91,邏輯表示法也存在一些不足，其主要缺點(diǎn)如下：（1）知識(shí)表示能力差邏輯表示法只能表示確定性知識(shí)，而不能表示非確定性知識(shí)，如不精確、模糊性知識(shí)。實(shí)際上，人類的大部分知識(shí)都不同程度地具有不確定性，使得它表示知識(shí)的范圍和能力受到了一定的限制。另外，邏輯表示法還難以表示過程性知識(shí)和啟發(fā)性知識(shí)。（2）知識(shí)庫管理困難邏輯表示法缺乏知識(shí)的組織原則，利用這種表示法所形成的知識(shí)庫管理比較困難。（3）存在組合爆炸由于邏輯表示法難以表示啟發(fā)性知識(shí)，因此在推理過程中只能盲目地使用推理規(guī)則。當(dāng)系統(tǒng)知識(shí)量較大時(shí)，容易發(fā)生組合爆炸。（4）系統(tǒng)效率低邏輯表示法的推理過程是根據(jù)形式邏輯進(jìn)行的。它把推理演算與知識(shí)含義截然分開，拋棄了表達(dá)內(nèi)容中所含有的語義信息，往往使推理過程冗長(zhǎng)，降低了系統(tǒng)效率。,92,設(shè)機(jī)器人有一只機(jī)械手，要處理的世界有一張桌子，桌上可堆放若干相同的方積木塊。積木世界的布局如下圖所示。,練習(xí)題：機(jī)器人摞積木問題,提示：機(jī)械手有4個(gè)操作積木的典型動(dòng)作：從桌面上揀起一塊積木；將手中的積木放到桌面上；在積木上再摞上一塊積木；從積木上面揀起一塊積木。,93,5.語義網(wǎng)絡(luò)法,語義網(wǎng)絡(luò)的基本概念1）.什么是語義網(wǎng)絡(luò)2）.語義的基本關(guān)系二.事物和概念的表示三.情景和動(dòng)作的表示四.邏輯關(guān)系的表示五.語義網(wǎng)絡(luò)的推理過程,94,語義網(wǎng)絡(luò)是奎廉（JRQullian）1968年在研究人類聯(lián)想記憶時(shí)提出的一種心理學(xué)模型，他認(rèn)為記憶是由概念間的聯(lián)系實(shí)現(xiàn)的。隨后，奎廉又把它用作知識(shí)表示。1972年，西蒙在自然語言理解系統(tǒng)中也采用了語義網(wǎng)絡(luò)表示法。1975年，亨德里克（GGHendrix）對(duì)全稱量詞的表示提出了語義網(wǎng)絡(luò)分區(qū)技術(shù)。目前，語義網(wǎng)絡(luò)已成為人工智能中應(yīng)用較多的一種知識(shí)表示方法。,95,語義網(wǎng)絡(luò)是一種用實(shí)體及其語義關(guān)系來表達(dá)知識(shí)的有向圖。其中，結(jié)點(diǎn)代表實(shí)體，表示各種事物、概念、情況、屬性、狀態(tài)、事件、動(dòng)作等；弧線代表語義關(guān)系，表示它所連結(jié)的兩個(gè)實(shí)體之間的語義聯(lián)系。在語義網(wǎng)絡(luò)中，每一個(gè)結(jié)點(diǎn)和弧都必須帶有標(biāo)識(shí)，這些標(biāo)識(shí)用來說明它所代表的實(shí)體或語義。,一.語義網(wǎng)絡(luò)的基本概念,1.什么是語義網(wǎng)絡(luò),96,從結(jié)構(gòu)上看，語義網(wǎng)絡(luò)一般是由一些最基本的語義單元構(gòu)成的，這種最基本的語義單元被稱為語義基元。一個(gè)語義基元可用如下三元組：（結(jié)點(diǎn)1，弧，結(jié)點(diǎn)2）來表示。對(duì)該三元組，如果用A、B分別表示其中的兩個(gè)結(jié)點(diǎn)，用R表示A與B之間的某種語義聯(lián)系，則它所對(duì)應(yīng)的基本網(wǎng)元表示為：,97,當(dāng)把多個(gè)語義基元用相應(yīng)的語義聯(lián)系關(guān)聯(lián)在一起時(shí)，就形成了一個(gè)語義網(wǎng)絡(luò)。在語義網(wǎng)絡(luò)中，弧的方向是有意義的，不能隨意調(diào)換。,例：用語義基元描述“鴕鳥是一種鳥”這一事實(shí)。由于“鴕鳥”與“鳥”之間的語義聯(lián)系為“是一種”，因此在此語義網(wǎng)絡(luò)中，弧被標(biāo)識(shí)為“是一種”。如下圖。,98,語義網(wǎng)絡(luò)表示和謂詞邏輯表示之間有一定的對(duì)應(yīng)表示能力。從邏輯表示來看，一個(gè)語義網(wǎng)絡(luò)相當(dāng)于一組二元謂詞。因?yàn)槿M（結(jié)點(diǎn)1，弧，結(jié)點(diǎn)2）可寫成P（個(gè)體1，個(gè)體2），其中結(jié)點(diǎn)1、結(jié)點(diǎn)2分別對(duì)應(yīng)個(gè)體1、個(gè)體2，而孤及其上的標(biāo)識(shí)是由謂詞P來體現(xiàn)的。,99,從功能上講，語義網(wǎng)絡(luò)可以描述任何事物間的任意復(fù)雜關(guān)系。但是，這種描述是通過把許多基本的語義關(guān)系關(guān)聯(lián)到一起來實(shí)現(xiàn)的。基本語義關(guān)系是構(gòu)成復(fù)雜語義關(guān)系的基石，也是語義網(wǎng)絡(luò)知識(shí)表示的基礎(chǔ)。但由于基本語義關(guān)系的多樣性和靈活性，因此又不可能對(duì)其進(jìn)行全面討論。作為參考，下面給出的僅是一些最常用的基本語義關(guān)系。,2.基本的語義關(guān)系,100,（1）類屬關(guān)系類屬關(guān)系是指具有共同屬性的不同事物間的分類關(guān)系、成員關(guān)系或?qū)嵗P(guān)系。它體現(xiàn)的是“具體與抽象”、“個(gè)體與集體”的概念。類屬關(guān)系的一個(gè)最主要特征是屬性的繼承性，處在具體層的結(jié)點(diǎn)可以繼承抽象層結(jié)點(diǎn)的所有屬性。常用的類屬關(guān)系有：AKind-of：含義為“是一種”，表示一個(gè)事物是另一個(gè)事物的一種類型。A-Member-of：含義為“是一員”，表示一個(gè)事物是另一個(gè)事物的一個(gè)成員。isa：含義為“是一個(gè)”，表示一個(gè)事物是另一個(gè)事物的一個(gè)實(shí)例。,101,例如：分類關(guān)系“鳥是一種動(dòng)物”可用下圖所示的語義網(wǎng)絡(luò)來表示。它說明鳥是動(dòng)物的一種類型，并可繼承動(dòng)物的所有屬性。,實(shí)例關(guān)系“李剛是人”可用下圖所示的語義網(wǎng)絡(luò)來表示。,成員關(guān)系“張強(qiáng)是共青團(tuán)員”可用下圖所示的語義網(wǎng)絡(luò)來表示。,在類屬關(guān)系中，具體層結(jié)點(diǎn)除具有抽象層結(jié)點(diǎn)的所有屬性外，還可以增加一些自己的個(gè)性，甚至還能夠?qū)Τ橄髮咏Y(jié)點(diǎn)的某些屬性加以更改。例如，所有的動(dòng)物都具有能運(yùn)動(dòng)、會(huì)吃等屬性。而鳥類作為動(dòng)物的一種，除具有動(dòng)物的這些屬性外，還具有會(huì)飛、有翅膀等個(gè)性。,102,（2）包含關(guān)系包含關(guān)系也稱為聚類關(guān)系，是指具有組織或結(jié)構(gòu)特征的“部分與整體”之間的關(guān)系。它和類屬關(guān)系的最主要區(qū)別是包含關(guān)系一般不具備屬性的繼承性。常用的包含關(guān)系是：Partof：含義為“是一部分”，表示一個(gè)事物是另一個(gè)事物的一部分。,103,例如，“大腦是人的一部分”可用下圖所示的語義網(wǎng)絡(luò)來表示。,再如，“黑板是墻的一部分”可用下圖來表示。,對(duì)于這兩個(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)的事情。例如，“鳥有翅膀”可用下圖所示的語義網(wǎng)絡(luò)來表示。,鳥,翅膀,Have,屬性關(guān)系,105,（4）時(shí)間關(guān)系時(shí)間關(guān)系是指不同事件在其發(fā)生時(shí)間方面的先后次序關(guān)系。常用的時(shí)間關(guān)系有：before：含義為“在前”，表示一個(gè)事件在另一個(gè)事件之前發(fā)生。after：含義為“在后”，表示一個(gè)事件在另一個(gè)事件之后發(fā)生。,例如，“澳門回歸在香港回歸之后”可用下圖所示的語義網(wǎng)絡(luò)來表示。,106,（5）位置關(guān)系位置關(guān)系是指不同事物在位置方面的關(guān)系。常用的位置關(guān)系有：Located-at：含義為“在”，表示某一物體所在的位置Locatedon：含義為“在上”，表示某一物體在另一物體之上Located-under：含義為“在下”，表示某一物體在另一物體之下Located-inside：含義為“在內(nèi)”，表示某一物體在另一物體之內(nèi)Locatedoutside：含義為“在外”，表示某一物體在另一物體之外,例如，“書在桌子上”可用下圖所示的語義網(wǎng)絡(luò)來表示,107,（6）相近關(guān)系相近關(guān)系是指不同事物在形狀、內(nèi)容等方面相似或接近。常用的相近關(guān)系有：Similarto：含義為“相似”，表示某一事物與另一事物相似。Nearto：含義為“接近”，表示某一事物與另一事物接近。,例如，“貓似虎”可用下圖所示的語義網(wǎng)絡(luò)來表示,貓,虎,Similar-to,相似關(guān)系,108,（7）推論關(guān)系推論關(guān)系是指從一個(gè)概念推出另一個(gè)概念的語義關(guān)系。例如，“由成績(jī)好推出學(xué)習(xí)努力”可用下圖所示的語義網(wǎng)絡(luò)來表示。,109,所謂一元關(guān)系是指可以用一元謂詞P(x)表示的關(guān)系。其中，個(gè)體X為實(shí)體，謂詞P說明實(shí)體的性質(zhì)、屬性等。一元關(guān)系描述的是一些最簡(jiǎn)單、最直觀的事物或概念，常用：“是”、“有”、“會(huì)”、“能”等語義關(guān)系來說明。例如，“雪是白的”就是一個(gè)一元關(guān)系。按道理講，語義網(wǎng)絡(luò)描述的是兩個(gè)結(jié)點(diǎn)之間的二元關(guān)系。那么如何用它來描述一元關(guān)系呢？通常的做法是用結(jié)點(diǎn)1表示實(shí)體，用結(jié)點(diǎn)2表示實(shí)體的性質(zhì)或?qū)傩缘?，用弧表示結(jié)點(diǎn)1和結(jié)點(diǎn)2之間的語義關(guān)系。例如，“李剛是人”是一個(gè)一元關(guān)系，其語義網(wǎng)絡(luò)如下圖所示。,李剛,人,is-a,實(shí)例關(guān)系,二.事物和概念的表示,1.用語義網(wǎng)絡(luò)表示一元關(guān)系,110,為了進(jìn)一步說明一元關(guān)系的語義網(wǎng)絡(luò)表示，下面再給出一個(gè)例子。例：用語義網(wǎng)絡(luò)表示“動(dòng)物能運(yùn)動(dòng)、會(huì)吃”。在這個(gè)例子中，能運(yùn)動(dòng)和會(huì)吃是動(dòng)物的兩個(gè)屬性。其表示方法是在“動(dòng)物”結(jié)點(diǎn)上增加它具有的屬性“能運(yùn)動(dòng)”、“會(huì)吃”。如下圖。,從這些例子可以看出，盡管語義網(wǎng)絡(luò)描述的是兩個(gè)結(jié)點(diǎn)之間的二元關(guān)系，但它同樣可以很方便地表示一元關(guān)系。,111,所謂二元關(guān)系是指可用二元謂詞P(x,y)表示的關(guān)系。其中，個(gè)體x，y為實(shí)體，謂詞P說明兩個(gè)實(shí)體之間的關(guān)系。二元關(guān)系可以很方便地用語義網(wǎng)絡(luò)來表示，前面介紹了一些常用二元關(guān)系的表示方法，下面主要討論較復(fù)雜關(guān)系的表示方法。有些關(guān)系看起來比較復(fù)雜，但可以較容易地分解成一些相對(duì)獨(dú)立的二元關(guān)系或一元關(guān)系。對(duì)于這類問題，可先給出每個(gè)二元關(guān)系或一元關(guān)系的語義網(wǎng)絡(luò)表示，然后再把它們關(guān)聯(lián)到一起，得到問題的完整表示。,2.用語義網(wǎng)絡(luò)表示二元關(guān)系,112,例：用語義網(wǎng)絡(luò)