第二章知識(shí)表示方法

1、中南大學(xué) 智能系統(tǒng)與智能軟件研究所第二章 知識(shí)表示方法2.1 狀態(tài)空間法2.2 問題歸約法2.3 謂詞邏輯法2.4 語義網(wǎng)絡(luò)法2.5 框架表示法2.6 本體技術(shù)2.7 過程表示CSUCSUCSUCSUCSUCSUCSUCSUCSU每種以每種以知識(shí)知識(shí)和和符號(hào)操作符號(hào)操作為基礎(chǔ)的智能系統(tǒng)，其為基礎(chǔ)的智能系統(tǒng)，其問題求解方法一般需要對(duì)解答過程進(jìn)行某種搜索。問題求解方法一般需要對(duì)解答過程進(jìn)行某種搜索。不過，在搜索過程開始之前，必須先用某種方法或不過，在搜索過程開始之前，必須先用某種方法或某幾種方法的混合來某幾種方法的混合來表示問題表示問題。本章主要討論知識(shí)表示的問題，介紹了本章主要討論知識(shí)表示的問題

2、，介紹了7種知種知識(shí)表示方法：狀態(tài)空間法、問題歸約法、謂詞演算識(shí)表示方法：狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法、框架表示法、本體技術(shù)和過程表法、語義網(wǎng)絡(luò)法、框架表示法、本體技術(shù)和過程表示法。其中要求掌握示法。其中要求掌握狀態(tài)空間法、問題歸約法、謂狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡(luò)法的要點(diǎn)及其之間的關(guān)系詞演算法、語義網(wǎng)絡(luò)法的要點(diǎn)及其之間的關(guān)系。CSUCSUCSUCSUCSUCSUCSUCSUCSU1.1.知識(shí)表示的基本概念知識(shí)表示的基本概念知識(shí)表示實(shí)際上就是對(duì)人類知識(shí)的一種描述，知識(shí)表示實(shí)際上就是對(duì)人類知識(shí)的一種描述，以以把人類知識(shí)表示成機(jī)器能夠處理的數(shù)據(jù)結(jié)構(gòu)。知識(shí)表把人類知

3、識(shí)表示成機(jī)器能夠處理的數(shù)據(jù)結(jié)構(gòu)。知識(shí)表示的過程就是把知識(shí)編碼成某種數(shù)據(jù)結(jié)構(gòu)的過程示的過程就是把知識(shí)編碼成某種數(shù)據(jù)結(jié)構(gòu)的過程。 2. 知識(shí)表示方法分類知識(shí)表示方法分類(1)(1)從作用范圍來劃分從作用范圍來劃分: :常識(shí)性、領(lǐng)域性常識(shí)性、領(lǐng)域性 (2)(2)從知識(shí)的作用及表示來劃分：事實(shí)性、過程從知識(shí)的作用及表示來劃分：事實(shí)性、過程性、控制性性、控制性 (3)(3)從知識(shí)的確定性來劃分：確定性、不確定性從知識(shí)的確定性來劃分：確定性、不確定性 (4)(4)從知識(shí)的結(jié)構(gòu)及表現(xiàn)形式來劃分：邏輯性、從知識(shí)的結(jié)構(gòu)及表現(xiàn)形式來劃分：邏輯性、形象性形象性CSUCSUCSUCSUCSUCSUCSUCSUCSU2

4、.1 狀態(tài)空間法問題求解涉及歸約、推斷、決策、規(guī)劃、常識(shí)推理、定問題求解涉及歸約、推斷、決策、規(guī)劃、常識(shí)推理、定理證明等相關(guān)的過程?，F(xiàn)實(shí)世界中理證明等相關(guān)的過程?，F(xiàn)實(shí)世界中問題求解過程問題求解過程可以可以看做是看做是一個(gè)一個(gè)搜索搜索或者或者推理推理過程。過程。 推理過程實(shí)際上也是一個(gè)搜索過程推理過程實(shí)際上也是一個(gè)搜索過程，它在知識(shí)庫(kù)中搜索，它在知識(shí)庫(kù)中搜索和前提條件相匹配的規(guī)則，而后利用這些規(guī)則進(jìn)行推理。所和前提條件相匹配的規(guī)則，而后利用這些規(guī)則進(jìn)行推理。所以，以，任何問題求解的本質(zhì)都是一個(gè)搜索過程任何問題求解的本質(zhì)都是一個(gè)搜索過程，并且發(fā)現(xiàn)許多，并且發(fā)現(xiàn)許多問題求解方法常常采用問題求解方法常

5、常采用試探式搜索方法試探式搜索方法。也就是說，這些方。也就是說，這些方法是通過在某個(gè)可能的解空間內(nèi)搜尋一個(gè)解來求解問題。這法是通過在某個(gè)可能的解空間內(nèi)搜尋一個(gè)解來求解問題。這種種基于解答空間的問題表示和求解方法就是狀態(tài)空間法基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它，它是是以狀態(tài)和算符為基礎(chǔ)來表示和求解問題以狀態(tài)和算符為基礎(chǔ)來表示和求解問題的。的。CSUCSUCSUCSUCSUCSUCSUCSUCSU狀態(tài)狀態(tài)(state)(state)：表示問題解法過程中每：表示問題解法過程中每一步問題狀況的數(shù)據(jù)結(jié)構(gòu)；一步問題狀況的數(shù)據(jù)結(jié)構(gòu)； 舉例：天氣、身體指標(biāo)、棋局對(duì)弈等舉例：天氣、身體指標(biāo)、棋局

6、對(duì)弈等算符算符(operator)(operator)：把問題從一種狀態(tài)變：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段或操作；換為另一種狀態(tài)的手段或操作；CSUCSUCSUCSUCSUCSUCSUCSUCSU例例1 1 農(nóng)夫、狐貍、雞、小米在一條河的左岸，現(xiàn)在要農(nóng)夫、狐貍、雞、小米在一條河的左岸，現(xiàn)在要把它們?nèi)克偷接野度?。農(nóng)夫有一條船，過河時(shí)，除把它們?nèi)克偷接野度?。農(nóng)夫有一條船，過河時(shí)，除農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣，且農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣，且狐貍要吃雞，雞要吃小米，除非農(nóng)夫在。試用狀態(tài)表狐貍要吃雞，雞要吃小米，除非農(nóng)夫在。試用狀態(tài)表示法規(guī)劃出一個(gè)確保全部對(duì)

7、象安全過河的計(jì)劃。示法規(guī)劃出一個(gè)確保全部對(duì)象安全過河的計(jì)劃。提示：提示：用四元向量用四元向量(農(nóng)夫、狐貍、雞、小米農(nóng)夫、狐貍、雞、小米)表示狀態(tài)表示狀態(tài)，每個(gè)每個(gè)分量取分量取0或或1，1表示船在左岸，表示船在左岸，0在右岸；在右岸； 把每次過河的一種具體安排作為一個(gè)算符，例如把每次過河的一種具體安排作為一個(gè)算符，例如可用可用L(f，j)表示從左岸將第表示從左岸將第j樣?xùn)|西送到右岸樣?xùn)|西送到右岸(j1是狐是狐貍，貍，j2是雞，是雞，j3是小米，是小米，j0表示除農(nóng)夫外不載任表示除農(nóng)夫外不載任何東西何東西)，f表示農(nóng)夫始終在船上。表示農(nóng)夫始終在船上。R(f，j)表示從右岸表示從右岸將第將第j樣?xùn)|西

8、送到左岸樣?xùn)|西送到左岸。CSUCSUCSUCSUCSUCSUCSUCSUCSU(1,1,1,1)(1,1,1,1)(0,1,0,1)(0,1,0,1)L(f,2)L(f,2)R(f,2)R(f,2)(1,1,0,1)(1,1,0,1)R(f,0)R(f,0)L(f,0)L(f,0)L(f,3)L(f,3)L(f,1)L(f,1)(0,0,0,1)(0,0,0,1)(0,1,0,0)(0,1,0,0)R(f,2)R(f,2)L(f,2)L(f,2)L(f,2)L(f,2)R(f,2)R(f,2)(1,1,1,0)(1,1,1,0)(1,0,1,1)(1,0,1,1)（農(nóng)夫、狐貍、雞、小米）過河問

9、題（農(nóng)夫、狐貍、雞、小米）過河問題L(f,1)L(f,1)L(f,3)L(f,3)(0,0,1,0)(0,0,1,0)R(f,0)R(f,0)L(f,0)L(f,0)(1,0,1,0)(1,0,1,0)(0,0,0,0)(0,0,0,0)L(f,2)L(f,2)R(f,2)R(f,2)CSUCSUCSUCSUCSUCSUCSUCSUCSU2.1.1 問題狀態(tài)描述1.形式化形式化定義定義狀態(tài)狀態(tài)(state)：為描述某類不同事物間差別而引入的一組：為描述某類不同事物間差別而引入的一組最少最少變變量量 q0, q1, , qn 的的有序集合，其矢量形式為：有序集合，其矢量形式為：Q=q0, q1,

10、 , qnT 式中每個(gè)元素式中每個(gè)元素qi (i=0,1，n)為集合的分量，稱為為集合的分量，稱為狀態(tài)變量狀態(tài)變量。算符算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為符或算符。操作符可為走步走步、過程過程、規(guī)則規(guī)則、數(shù)學(xué)算子數(shù)學(xué)算子、運(yùn)算符號(hào)運(yùn)算符號(hào)或或邏輯符號(hào)邏輯符號(hào)等。等。問題的狀態(tài)空間問題的狀態(tài)空間：是一個(gè)表示某問題全部可能狀態(tài)及其關(guān)系：是一個(gè)表示某問題全部可能狀態(tài)及其關(guān)系的的圖圖，狀態(tài)空間記為三元結(jié)構(gòu)，狀態(tài)空間記為三元結(jié)構(gòu)(S，F(xiàn)，G)，即，即初始狀態(tài)集合初始狀態(tài)集合S、操操作算符集合作算符集合F以及以及目標(biāo)狀態(tài)

11、集合目標(biāo)狀態(tài)集合G。CSUCSUCSUCSUCSUCSUCSUCSUCSU2.狀態(tài)空間表示法詳釋狀態(tài)空間表示法詳釋我們先用我們先用數(shù)碼難題數(shù)碼難題(puzzle problem)來說明狀態(tài)空間表示的來說明狀態(tài)空間表示的概念。由概念。由15個(gè)編有個(gè)編有1至至15并放在并放在44方格棋盤上的可走動(dòng)的棋子方格棋盤上的可走動(dòng)的棋子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進(jìn)組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進(jìn)空格，這也可以理解為移動(dòng)空格。圖中繪出了兩種棋局，即空格，這也可以理解為移動(dòng)空格。圖中繪出了兩種棋局，即初始初始棋局和目標(biāo)棋局棋局和目標(biāo)棋局（書本（書本29頁圖頁圖

12、2.1），它們對(duì)應(yīng)于該下棋問題的），它們對(duì)應(yīng)于該下棋問題的初始狀態(tài)初始狀態(tài)和和目標(biāo)狀態(tài)目標(biāo)狀態(tài)。如何把初始棋局變換為目標(biāo)棋局呢？問題的解答就是某個(gè)合如何把初始棋局變換為目標(biāo)棋局呢？問題的解答就是某個(gè)合適的棋子走步序列，如適的棋子走步序列，如“左移棋子左移棋子12，下移棋子，下移棋子15，右移棋子，右移棋子4，”等等。等等。1515數(shù)碼難題數(shù)碼難題最直接的求解方法是嘗試各種不同走步最直接的求解方法是嘗試各種不同走步，直到偶，直到偶然得到目標(biāo)棋局為止，這種嘗試然得到目標(biāo)棋局為止，這種嘗試本質(zhì)上是本質(zhì)上是一種試探性的搜索一種試探性的搜索。 CSUCSUCSUCSUCSUCSUCSUCSUCSU從初始

13、棋局開始，試探由每一合法走步得到的各種新棋局，從初始棋局開始，試探由每一合法走步得到的各種新棋局，然后計(jì)算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達(dá)然后計(jì)算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達(dá)到目標(biāo)棋局為止。到目標(biāo)棋局為止。把初始狀態(tài)可達(dá)到的各狀態(tài)所組成的空間設(shè)想把初始狀態(tài)可達(dá)到的各狀態(tài)所組成的空間設(shè)想為一幅由各種狀態(tài)對(duì)應(yīng)的節(jié)點(diǎn)組成的圖，為一幅由各種狀態(tài)對(duì)應(yīng)的節(jié)點(diǎn)組成的圖，這種圖稱為這種圖稱為狀態(tài)圖。狀態(tài)圖。圖圖中中每個(gè)節(jié)點(diǎn)標(biāo)有它所代表的棋局每個(gè)節(jié)點(diǎn)標(biāo)有它所代表的棋局。首先把適用的算符用于初始狀。首先把適用的算符用于初始狀態(tài)，產(chǎn)生新的狀態(tài)；然后，再把另一些適用算符用于這些新的

14、狀態(tài)，產(chǎn)生新的狀態(tài)；然后，再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止。（態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標(biāo)狀態(tài)為止。（29頁圖頁圖2.2） CSUCSUCSUCSUCSUCSUCSUCSUCSU我們用我們用狀態(tài)空間法狀態(tài)空間法表示下述過程：表示下述過程：首先將適用的首先將適用的算符算符作用于初始狀態(tài)作用于初始狀態(tài)，產(chǎn)生中間狀態(tài)，再選擇適用的，產(chǎn)生中間狀態(tài)，再選擇適用的算符算符作用于當(dāng)前狀態(tài)；遞增地作用于當(dāng)前狀態(tài)；遞增地建立起算符試驗(yàn)序列，建立起算符試驗(yàn)序列，直到達(dá)到目標(biāo)狀態(tài)為止直到達(dá)到目標(biāo)狀態(tài)為止。某個(gè)問題的狀態(tài)描述，須經(jīng)歷如下某個(gè)問題的狀態(tài)描述，須經(jīng)歷如下3個(gè)步驟個(gè)步

15、驟： （1）定義）定義狀態(tài)的描述方式狀態(tài)的描述方式； （2）用所定義的狀態(tài)描述形式把問題的所有可能）用所定義的狀態(tài)描述形式把問題的所有可能狀態(tài)表示出來，關(guān)鍵是狀態(tài)表示出來，關(guān)鍵是確定問題的初始狀態(tài)確定問題的初始狀態(tài)描述描述集合集合和和目標(biāo)狀態(tài)目標(biāo)狀態(tài)描述描述集合集合； （3 3）定義）定義一組算符一組算符，利用這組算符可把問題由一，利用這組算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。CSUCSUCSUCSUCSUCSUCSUCSUCSU需要說明的是：需要說明的是： 可能存在可能存在多個(gè)算符序列多個(gè)算符序列都可使問題達(dá)到目標(biāo)狀都可使問題達(dá)到目標(biāo)狀態(tài)，這就得到態(tài)，這就得到多個(gè)解

16、多個(gè)解。其中，有的所使用算符較少，。其中，有的所使用算符較少，有的則較多，把有的則較多，把使用算符最少的解使用算符最少的解稱為稱為最優(yōu)解最優(yōu)解。 對(duì)任何一個(gè)狀態(tài)，可對(duì)任何一個(gè)狀態(tài)，可適用算符可能不止一個(gè)適用算符可能不止一個(gè)，這樣由一個(gè)狀態(tài)所這樣由一個(gè)狀態(tài)所生成的后繼狀態(tài)可能有多個(gè)生成的后繼狀態(tài)可能有多個(gè)，首先，首先使用哪一個(gè)適用的算符呢？這屬于使用哪一個(gè)適用的算符呢？這屬于搜索策略搜索策略問題（問題（搜搜索算法索算法），不同搜索策略其算符操作的順序可能不相），不同搜索策略其算符操作的順序可能不相同，這就可能導(dǎo)致多組不同的解。同，這就可能導(dǎo)致多組不同的解。CSUCSUCSUCSUCSUCSUCS

17、UCSUCSU2.1.2 狀態(tài)圖示法對(duì)于下棋問題曾用狀態(tài)圖來描述狀態(tài)空間，這里介紹一下圖對(duì)于下棋問題曾用狀態(tài)圖來描述狀態(tài)空間，這里介紹一下圖論中的幾個(gè)術(shù)語和圖的正式表示法。論中的幾個(gè)術(shù)語和圖的正式表示法。1. 圖論中的幾個(gè)術(shù)語圖論中的幾個(gè)術(shù)語 節(jié)點(diǎn)節(jié)點(diǎn)(node)：圖形上的匯合點(diǎn)，用來表示狀態(tài)、事件和時(shí)：圖形上的匯合點(diǎn)，用來表示狀態(tài)、事件和時(shí)間關(guān)系的匯合，如下棋中的每一步棋局；間關(guān)系的匯合，如下棋中的每一步棋局； 弧線弧線(arc)：節(jié)點(diǎn)間的連接線，代表算符；：節(jié)點(diǎn)間的連接線，代表算符； 有向圖有向圖(directed graph)：一對(duì)節(jié)點(diǎn)用弧線連接起來，從一：一對(duì)節(jié)點(diǎn)用弧線連接起來，從一個(gè)

18、節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)，反映了狀態(tài)的變更情況；個(gè)節(jié)點(diǎn)指向另一個(gè)節(jié)點(diǎn)，反映了狀態(tài)的變更情況； 后繼節(jié)點(diǎn)后繼節(jié)點(diǎn)(descendant node)與與父輩節(jié)點(diǎn)父輩節(jié)點(diǎn)(parent node)：如果：如果某條弧線從節(jié)點(diǎn)某條弧線從節(jié)點(diǎn) ni 指向節(jié)點(diǎn)指向節(jié)點(diǎn) nj ，那么節(jié)點(diǎn)，那么節(jié)點(diǎn) nj 就叫做節(jié)點(diǎn)就叫做節(jié)點(diǎn) ni 的后的后繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn)繼節(jié)點(diǎn)或后裔，而節(jié)點(diǎn) ni 叫做節(jié)點(diǎn)叫做節(jié)點(diǎn) nj 的父輩節(jié)點(diǎn)或祖先；的父輩節(jié)點(diǎn)或祖先；CSUCSUCSUCSUCSUCSUCSUCSUCSU 路徑路徑：某個(gè)節(jié)點(diǎn)序列：某個(gè)節(jié)點(diǎn)序列 (ni1, ni2, , nik ) ，當(dāng)，當(dāng)j=2，3，k時(shí)，如果對(duì)于每一個(gè)

19、時(shí)，如果對(duì)于每一個(gè)ni, j-1都有一個(gè)后繼節(jié)點(diǎn)都有一個(gè)后繼節(jié)點(diǎn)nij存在，那么就把存在，那么就把這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)這個(gè)節(jié)點(diǎn)序列叫做從節(jié)點(diǎn)ni1至節(jié)點(diǎn)至節(jié)點(diǎn)nik的長(zhǎng)度為的長(zhǎng)度為k的路徑。的路徑。 代價(jià)代價(jià)：用：用c(ni, nj) 來表示從節(jié)點(diǎn)來表示從節(jié)點(diǎn)ni指向指向nj的弧線的代價(jià)。的弧線的代價(jià)。兩節(jié)點(diǎn)間路徑代價(jià)等于連接該路徑上各節(jié)點(diǎn)所有弧線代價(jià)之和。兩節(jié)點(diǎn)間路徑代價(jià)等于連接該路徑上各節(jié)點(diǎn)所有弧線代價(jià)之和。 顯式表示顯式表示：各狀態(tài)節(jié)點(diǎn)及其具有代價(jià)的弧線由一張表明：各狀態(tài)節(jié)點(diǎn)及其具有代價(jià)的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及確給出。此表可能列出該圖中的每

20、一節(jié)點(diǎn)、它的后繼節(jié)點(diǎn)以及連接弧線的代價(jià)。連接弧線的代價(jià)。 隱式表示隱式表示：節(jié)點(diǎn)的無限集合：節(jié)點(diǎn)的無限集合si作為作為起始節(jié)點(diǎn)是已知起始節(jié)點(diǎn)是已知。后后繼節(jié)點(diǎn)算符繼節(jié)點(diǎn)算符L也已知也已知，它作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部，它作用于任一節(jié)點(diǎn)以產(chǎn)生該節(jié)點(diǎn)的全部后繼節(jié)點(diǎn)和各連接弧線的代價(jià)。后繼節(jié)點(diǎn)和各連接弧線的代價(jià)。CSUCSUCSUCSUCSUCSUCSUCSUCSU2.圖的顯式和隱式表示圖的顯式和隱式表示 圖可以被顯式說明或隱式說明，圖可以被顯式說明或隱式說明，顯式表示對(duì)于大型的圖顯式表示對(duì)于大型的圖不切實(shí)際的不切實(shí)際的，而對(duì)于有無限節(jié)點(diǎn)集合的圖更是不可能。，而對(duì)于有無限節(jié)點(diǎn)集合的圖更是不可能

21、。考慮引入后繼節(jié)點(diǎn)算符的方法來隱式表示狀態(tài)空間圖。考慮引入后繼節(jié)點(diǎn)算符的方法來隱式表示狀態(tài)空間圖。后繼節(jié)點(diǎn)算符集后繼節(jié)點(diǎn)算符集L也是已知的，也是已知的，把適用的后繼算符應(yīng)用于把適用的后繼算符應(yīng)用于si的成員和它們的后繼節(jié)點(diǎn)以及這些后繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)的成員和它們的后繼節(jié)點(diǎn)以及這些后繼節(jié)點(diǎn)的后繼節(jié)點(diǎn)，如，如此無限制地進(jìn)行下去，此無限制地進(jìn)行下去，最后由最后由L和和si所規(guī)定的隱式圖變?yōu)轱@所規(guī)定的隱式圖變?yōu)轱@示圖示圖。把后繼算符作用于節(jié)點(diǎn)的過程，實(shí)際上就是擴(kuò)展該節(jié)。把后繼算符作用于節(jié)點(diǎn)的過程，實(shí)際上就是擴(kuò)展該節(jié)點(diǎn)的過程。因此，通過搜索狀態(tài)空間以求得算符序列的解答點(diǎn)的過程。因此，通過搜索狀態(tài)空間以求得

22、算符序列的解答過程，就是使隱式圖變?yōu)轱@式并包含目標(biāo)的過程。過程，就是使隱式圖變?yōu)轱@式并包含目標(biāo)的過程。 CSUCSUCSUCSUCSUCSUCSUCSUCSU問題的表示對(duì)求解工作量有很大的影響。人們顯然希望問題的表示對(duì)求解工作量有很大的影響。人們顯然希望用用較小的狀態(tài)空間表示較小的狀態(tài)空間表示。許多似乎很難的問題，當(dāng)表示適當(dāng)時(shí)就。許多似乎很難的問題，當(dāng)表示適當(dāng)時(shí)就可能具有小而簡(jiǎn)單的狀態(tài)空間。如對(duì)十五數(shù)碼難題的初始狀態(tài)可能具有小而簡(jiǎn)單的狀態(tài)空間。如對(duì)十五數(shù)碼難題的初始狀態(tài)表示，可規(guī)定表示，可規(guī)定15460條算符，即左移棋子條算符，即左移棋子1，右移棋子，右移棋子1，上移棋子上移棋子1，下移棋子，

23、下移棋子1，左移棋子，左移棋子2，下移棋子，下移棋子15，但我們，但我們很快就會(huì)發(fā)現(xiàn)，只要左右上下移動(dòng)空格，那么就可用很快就會(huì)發(fā)現(xiàn)，只要左右上下移動(dòng)空格，那么就可用4條算符條算符代替上述代替上述60條算符?？梢姡苿?dòng)空格是一種較好的表示。因條算符。可見，移動(dòng)空格是一種較好的表示。因此，此，對(duì)于同一問題，表示方法可能有多種。對(duì)于同一問題，表示方法可能有多種。在求解問題時(shí)在求解問題時(shí), ,首首先應(yīng)考慮如何表示問題，之后再改進(jìn)表示方法先應(yīng)考慮如何表示問題，之后再改進(jìn)表示方法。 2.1.3 狀態(tài)空間表示舉例 下面介紹另一個(gè)狀態(tài)空間表示的例子下面介紹另一個(gè)狀態(tài)空間表示的例子CSUCSUCSUCSUCSU

24、CSUCSUCSUCSU例例2猴子和香蕉問題猴子和香蕉問題( monkey and banana problem )在一個(gè)房間內(nèi)有一只猴子在一個(gè)房間內(nèi)有一只猴子(可把這只猴子看做一個(gè)機(jī)器人可把這只猴子看做一個(gè)機(jī)器人)、一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足一個(gè)箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢？圖以碰到它。那么這只猴子怎樣才能摘到香蕉呢？圖2.4表示出猴表示出猴子、香蕉和箱子在房間內(nèi)的相對(duì)位置。子、香蕉和箱子在房間內(nèi)的相對(duì)位置。 用一個(gè)四元表列用一個(gè)四元表列(W, x, Y, z)來表示這個(gè)問題的狀態(tài)，來表示這個(gè)問題的

25、狀態(tài)，W猴子的水平位置猴子的水平位置x當(dāng)猴子在箱子頂上時(shí)取當(dāng)猴子在箱子頂上時(shí)取x=1；否則?。环駝t取x=0Y箱子的水平位置箱子的水平位置 z當(dāng)猴子摘到香蕉時(shí)取當(dāng)猴子摘到香蕉時(shí)取z=1；否則取；否則取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSU這個(gè)問題中的這個(gè)問題中的操作操作(算符算符)用產(chǎn)生式規(guī)則表示用產(chǎn)生式規(guī)則表示如下：如下：(1) goto(U)：表示猴子走到水平位置：表示猴子走到水平位置U，用產(chǎn)生式，用產(chǎn)生式規(guī)則表示為規(guī)則表示為（W，0，Y，z） （U，0，Y，z）(2) pushbox(V)：表示猴子把箱子推到了水平位置：表示猴子把箱子推到了水平位置V，即有，即有（W，

26、0，W，z） （V，0，V，z）注意：要應(yīng)用算符注意：要應(yīng)用算符pushbox(V)，就要求產(chǎn)生式規(guī)則，就要求產(chǎn)生式規(guī)則的左邊，猴子與箱子必須在同一位置上，且猴子不在箱的左邊，猴子與箱子必須在同一位置上，且猴子不在箱子頂上子頂上，即，即x=0=0。這種強(qiáng)加于操作的適用性條件，叫做。這種強(qiáng)加于操作的適用性條件，叫做產(chǎn)生式規(guī)則的先決條件產(chǎn)生式規(guī)則的先決條件。CSUCSUCSUCSUCSUCSUCSUCSUCSU (3) climbbox：猴子爬上箱頂，即有：猴子爬上箱頂，即有（W，0，W，z） （W，1，W，z）在應(yīng)用算符在應(yīng)用算符climbbox時(shí)也必須注意到，猴子和箱子時(shí)也必須注意到，猴子和箱

27、子應(yīng)當(dāng)在同一位置上，而且猴子不在箱頂上，即應(yīng)當(dāng)在同一位置上，而且猴子不在箱頂上，即x=0。(4) grasp：猴子摘到香蕉，即有：猴子摘到香蕉，即有（c，1，c，0） （c，1，c，1）其中，其中，c是香蕉正下方的地板位置，在應(yīng)用算符是香蕉正下方的地板位置，在應(yīng)用算符grasp時(shí)，要求猴子和箱子都在位置時(shí)，要求猴子和箱子都在位置c上，并且猴子已在上，并且猴子已在箱子頂上，即箱子頂上，即x=1。 CSUCSUCSUCSUCSUCSUCSUCSUCSU本問題中，令初始狀態(tài)為本問題中，令初始狀態(tài)為(a, 0, b, 0)。這時(shí)，。這時(shí)，goto(U)是唯一是唯一適用的操作，并導(dǎo)致下一狀態(tài)適用的操作，

28、并導(dǎo)致下一狀態(tài)(U, 0, b, 0)，把所有適用的操作繼，把所有適用的操作繼續(xù)應(yīng)用于每個(gè)狀態(tài)，直至任何最后一列元素為續(xù)應(yīng)用于每個(gè)狀態(tài)，直至任何最后一列元素為1的目標(biāo)狀態(tài)表列的目標(biāo)狀態(tài)表列出現(xiàn)，我們就能夠得到狀態(tài)空間圖出現(xiàn)，我們就能夠得到狀態(tài)空間圖。goto(b)，pushbox(c)，climbbox，grasp 目標(biāo)狀態(tài)目標(biāo)狀態(tài)V=c，climbbox(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=Vgr

29、aspCSUCSUCSUCSUCSUCSUCSUCSUCSU2.2 問題歸約法問題歸約是一種問題表示與求解方法問題歸約是一種問題表示與求解方法。已知原始問題的描已知原始問題的描述，通過一系列變換把原問題變?yōu)橐粋€(gè)子問題的集合，集合里述，通過一系列變換把原問題變?yōu)橐粋€(gè)子問題的集合，集合里的每個(gè)子問題被進(jìn)一步簡(jiǎn)化為子子問題，最終的這些子問題的每個(gè)子問題被進(jìn)一步簡(jiǎn)化為子子問題，最終的這些子問題的解答可以直接得到，從而得到原始問題的解答。的解答可以直接得到，從而得到原始問題的解答。本原問題本原問題其解答可其解答可通過一步通過一步（運(yùn)算、走步、操作等）而（運(yùn)算、走步、操作等）而直接得到的子問題。直接得到的

30、子問題。CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.1 問題歸約描述示例：梵塔難題（河內(nèi)塔、漢諾塔，起源于古印度）示例：梵塔難題（河內(nèi)塔、漢諾塔，起源于古印度）最初，由大到小的最初，由大到小的3 3個(gè)圓盤自下而上都堆在柱子個(gè)圓盤自下而上都堆在柱子1 1上，要上，要求把所有圓盤都移到柱子求把所有圓盤都移到柱子3 3上。上。要求：要求：(1) (1) 一次只能移一個(gè)盤子；一次只能移一個(gè)盤子；(2) (2) 盤子只許在三根柱子上存放；盤子只許在三根柱子上存放； (3) (3) 永遠(yuǎn)不許有大盤壓著小盤。永遠(yuǎn)不許有大盤壓著小盤。 CSUCSUCSUCSUCSUCSUCSUCSUCSU分

31、析過程：分析過程：1、要把所有圓盤移至柱子、要把所有圓盤移至柱子3，必須先把最大的圓盤，必須先把最大的圓盤C移至柱子移至柱子3；而且在移動(dòng)圓盤；而且在移動(dòng)圓盤C至柱子至柱子3之前，要求柱之前，要求柱子子3必須是空的。必須是空的。2、只有在移開圓盤、只有在移開圓盤A和和B之后，才能移動(dòng)圓盤之后，才能移動(dòng)圓盤C；且圓；且圓盤盤A和和B最好不要移至柱子最好不要移至柱子3，否則會(huì)出現(xiàn)大盤壓著小，否則會(huì)出現(xiàn)大盤壓著小盤，就不能把圓盤盤，就不能把圓盤C移至柱子移至柱子3。因此，首先應(yīng)該把圓。因此，首先應(yīng)該把圓盤盤A和和B從柱子從柱子1移到柱子移到柱子2上；上；3、然后才能、然后才能進(jìn)行關(guān)鍵的一步進(jìn)行關(guān)鍵的

32、一步，把圓盤，把圓盤C從柱子從柱子1移至移至柱子柱子3，并繼續(xù)解決問題的余下部分，把圓盤，并繼續(xù)解決問題的余下部分，把圓盤A和和B從從柱子柱子2移至柱子移至柱子3。CSUCSUCSUCSUCSUCSUCSUCSUCSU歸約過程：歸約過程：上述討論使得原始問題歸約（簡(jiǎn)化）為下上述討論使得原始問題歸約（簡(jiǎn)化）為下列列3 3個(gè)子問題：個(gè)子問題： （1）移動(dòng)圓盤）移動(dòng)圓盤A和和B從柱子從柱子1至柱子至柱子2的的雙圓雙圓盤問題盤問題；CSUCSUCSUCSUCSUCSUCSUCSUCSU（2）移動(dòng)圓盤）移動(dòng)圓盤C從柱子從柱子1至柱子至柱子3的單圓盤問題；的單圓盤問題；（3）移動(dòng)圓盤）移動(dòng)圓盤A和和B從柱

33、子從柱子2至柱子至柱子3的雙圓盤問題。的雙圓盤問題。CSUCSUCSUCSUCSUCSUCSUCSUCSU可以看出，分解后的子問題都比原始問題要簡(jiǎn)單。其可以看出，分解后的子問題都比原始問題要簡(jiǎn)單。其中子問中子問題題2 2可作為本原問題可作為本原問題考慮，因?yàn)樗那蠼庵话徊揭苿?dòng)操作。考慮，因?yàn)樗那蠼庵话徊揭苿?dòng)操作。應(yīng)用一系列相似的推理，應(yīng)用一系列相似的推理，子問題子問題1 1和和子問題子問題3 3也也可進(jìn)一步被歸約為可進(jìn)一步被歸約為本原問題本原問題。下面給出梵塔問題的。下面給出梵塔問題的歸約過程圖歸約過程圖（也稱做（也稱做與或圖與或圖）。）。思考：思考：1 1圓盤問題要走幾步？圓盤問題

34、要走幾步？2 2圓盤問題要走幾步？圓盤問題要走幾步？3 3個(gè)，個(gè)，4 4個(gè)，個(gè)， ,64 ,64個(gè)呢？個(gè)呢？CSUCSUCSUCSUCSUCSUCSUCSUCSU解題過程（解題過程（3 3個(gè)圓盤問題）個(gè)圓盤問題）按照前面的歸約過程圖可以給出詳細(xì)的解題過程圖。按照前面的歸約過程圖可以給出詳細(xì)的解題過程圖。123123123123123123123123CSUCSUCSUCSUCSUCSUCSUCSUCSU問題歸約法的實(shí)質(zhì)：?jiǎn)栴}歸約法的實(shí)質(zhì)：從目標(biāo)從目標(biāo)（要解決的問題要解決的問題）出發(fā)逆向推理，原問題分解為若干出發(fā)逆向推理，原問題分解為若干個(gè)子問題以及子子問題，直至最后把初始問題歸約（簡(jiǎn)化）為個(gè)子

35、問題以及子子問題，直至最后把初始問題歸約（簡(jiǎn)化）為一個(gè)平凡的本原問題集合。一個(gè)平凡的本原問題集合。問題歸約表示法可由下面三部分組成：?jiǎn)栴}歸約表示法可由下面三部分組成： 一個(gè)初始問題描述一個(gè)初始問題描述（可用表列、數(shù)組、樹、字符串等形式）（可用表列、數(shù)組、樹、字符串等形式） 一套把問題變換為子問題的操作符一套把問題變換為子問題的操作符（通過一系列操作將原問題（通過一系列操作將原問題變換為等價(jià)問題）變換為等價(jià)問題） 一套本原問題描述一套本原問題描述（本原子問題的解答可直接由一步得到）（本原子問題的解答可直接由一步得到）CSUCSUCSUCSUCSUCSUCSUCSUCSU問題歸約方法可以應(yīng)用狀態(tài)、

36、算符和目標(biāo)這些問題歸約方法可以應(yīng)用狀態(tài)、算符和目標(biāo)這些表示法來描述問題，這表示法來描述問題，這并不意味著問題歸約法和狀并不意味著問題歸約法和狀態(tài)空間法是一樣態(tài)空間法是一樣的。的。 把一個(gè)初始問題描述變換為一個(gè)歸約或后繼問把一個(gè)初始問題描述變換為一個(gè)歸約或后繼問題描述的集合，題描述的集合，由問題歸約算符進(jìn)行由問題歸約算符進(jìn)行，變換所得所，變換所得所有后繼問題的解就是父輩問題的一個(gè)解。有后繼問題的解就是父輩問題的一個(gè)解。 所所有問題歸約的目的是產(chǎn)生具有明顯解答的本有問題歸約的目的是產(chǎn)生具有明顯解答的本原子問題原子問題。本原子問題可由解答空間搜索走動(dòng)一步。本原子問題可由解答空間搜索走動(dòng)一步解決或能直

37、接得到解答。解決或能直接得到解答。 CSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.2 與或圖表示1.與或圖的概念與或圖的概念一般，我們用一個(gè)類似圖的結(jié)構(gòu)來表示把問題歸約為后繼一般，我們用一個(gè)類似圖的結(jié)構(gòu)來表示把問題歸約為后繼問題的替換集合，這種結(jié)構(gòu)圖叫做問題的替換集合，這種結(jié)構(gòu)圖叫做問題歸約圖問題歸約圖，或叫，或叫與或圖與或圖。如下圖所示：如下圖所示： ABCD與圖ABC或圖CSUCSUCSUCSUCSUCSUCSUCSUCSUBCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSU2.一些關(guān)于一些關(guān)于與或圖的術(shù)語與或圖的術(shù)語介紹一些術(shù)語：介紹一

38、些術(shù)語：父節(jié)點(diǎn)父節(jié)點(diǎn)、子子( (后繼后繼) )節(jié)點(diǎn)節(jié)點(diǎn)、弧線弧線、起始節(jié)點(diǎn)起始節(jié)點(diǎn)。終葉節(jié)點(diǎn)終葉節(jié)點(diǎn)：對(duì)應(yīng)于本原問題的節(jié)點(diǎn)。：對(duì)應(yīng)于本原問題的節(jié)點(diǎn)。或節(jié)點(diǎn)或節(jié)點(diǎn)：只要解決該問題就可解決其父輩問題的節(jié)點(diǎn)集合，如：只要解決該問題就可解決其父輩問題的節(jié)點(diǎn)集合，如( (M，N，H) )。與節(jié)點(diǎn)與節(jié)點(diǎn)：只有解決所有子問題，才能解決其父輩問題的節(jié)點(diǎn)集：只有解決所有子問題，才能解決其父輩問題的節(jié)點(diǎn)集合，如合，如( (B，C)和和( (D，E，F(xiàn))各結(jié)點(diǎn)之間用一段小圓弧連接標(biāo)記。各結(jié)點(diǎn)之間用一段小圓弧連接標(biāo)記。HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn)弧線或節(jié)點(diǎn)子節(jié)點(diǎn)終葉節(jié)點(diǎn)CSUCSUCSUCSUCSUCSUCSUC

39、SUCSU 與或圖中與或圖中可解節(jié)點(diǎn)可解節(jié)點(diǎn)的一般定義：的一般定義： (1) 終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)（因?yàn)樗鼈儯ㄒ驗(yàn)樗鼈兣c本原問題相關(guān)連與本原問題相關(guān)連）。）。 (2) 如果某個(gè)如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只要當(dāng)其后繼，那么只要當(dāng)其后繼節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。節(jié)點(diǎn)至少有一個(gè)是可解的時(shí)，此非終葉節(jié)點(diǎn)才是可解的。 (3) 如果某個(gè)如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只有當(dāng)其后繼，那么只有當(dāng)其后繼節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。節(jié)點(diǎn)全部為可解時(shí)，此非終葉節(jié)點(diǎn)才是可解的。 終葉節(jié)點(diǎn)用字母終葉節(jié)

40、點(diǎn)用字母t表示表示（對(duì)應(yīng)于本原問題），（對(duì)應(yīng)于本原問題），有解節(jié)點(diǎn)用小圓有解節(jié)點(diǎn)用小圓點(diǎn)表示，不可解節(jié)點(diǎn)用小圓圈表示點(diǎn)表示，不可解節(jié)點(diǎn)用小圓圈表示。 相應(yīng)地可給出相應(yīng)地可給出不可解節(jié)點(diǎn)不可解節(jié)點(diǎn)的一般定義：的一般定義： (1) 完全沒有后繼節(jié)點(diǎn)的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。完全沒有后繼節(jié)點(diǎn)的非終葉節(jié)點(diǎn)為不可解節(jié)點(diǎn)。 (2) 如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部如果某個(gè)非終葉節(jié)點(diǎn)含有或后繼節(jié)點(diǎn)，那么只有當(dāng)其全部后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。后裔為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。 (3) 如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，那么只要當(dāng)其后裔如果某個(gè)非終葉節(jié)點(diǎn)含有與后繼節(jié)點(diǎn)，

41、那么只要當(dāng)其后裔至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。至少有一個(gè)為不可解時(shí)，此非終葉節(jié)點(diǎn)才是不可解的。 CSUCSUCSUCSUCSUCSUCSUCSUCSUt有解節(jié)點(diǎn)終葉節(jié)點(diǎn)與或圖例子與或圖例子無解節(jié)點(diǎn)tttttttt（a）（c）CSUCSUCSUCSUCSUCSUCSUCSUCSU 綜合前面所述，下面給出與或圖的構(gòu)成規(guī)則：綜合前面所述，下面給出與或圖的構(gòu)成規(guī)則： (1) 與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問題或問題與或圖中的每個(gè)節(jié)點(diǎn)代表一個(gè)要解決的單一問題或問題集合。圖中所含集合。圖中所含起始節(jié)點(diǎn)對(duì)應(yīng)于原始問題起始節(jié)點(diǎn)對(duì)應(yīng)于原始問題。 (2) 對(duì)應(yīng)于本原問題的節(jié)點(diǎn)，叫做終葉節(jié)

42、點(diǎn)，它沒有后裔對(duì)應(yīng)于本原問題的節(jié)點(diǎn)，叫做終葉節(jié)點(diǎn)，它沒有后裔。 (3) 有向弧線自問題有向弧線自問題A指向后繼節(jié)點(diǎn)表示所求得的子問題集合：指向后繼節(jié)點(diǎn)表示所求得的子問題集合：N，M和和H。子問題集合子問題集合：N，M和和H中任何一個(gè)有解答，問題中任何一個(gè)有解答，問題A就可解答就可解答。所以。所以N，M和和H叫做叫做或節(jié)點(diǎn)或節(jié)點(diǎn)。 (4) 一般對(duì)于代表一般對(duì)于代表有兩個(gè)或兩個(gè)以上子問題集合的每個(gè)非終有兩個(gè)或兩個(gè)以上子問題集合的每個(gè)非終葉節(jié)點(diǎn)葉節(jié)點(diǎn)，有向弧線從此節(jié)點(diǎn)指向此子問題集合中的各個(gè)節(jié)點(diǎn)。由，有向弧線從此節(jié)點(diǎn)指向此子問題集合中的各個(gè)節(jié)點(diǎn)。由于只有當(dāng)于只有當(dāng)該集合中所有的項(xiàng)都有解時(shí)該集合中所有

43、的項(xiàng)都有解時(shí)，這，這個(gè)子問題的集合才能獲個(gè)子問題的集合才能獲得解答得解答，所以這些子問題節(jié)點(diǎn)叫做，所以這些子問題節(jié)點(diǎn)叫做與節(jié)點(diǎn)與節(jié)點(diǎn)。 (5) 在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問題在特殊情況下，當(dāng)只有一個(gè)算符可應(yīng)用于問題A，而且這，而且這個(gè)算符產(chǎn)生具有一個(gè)以上子問題的某個(gè)集合時(shí)，由上述規(guī)則個(gè)算符產(chǎn)生具有一個(gè)以上子問題的某個(gè)集合時(shí)，由上述規(guī)則3和和規(guī)則規(guī)則4所產(chǎn)生的圖可以得到簡(jiǎn)化。因此，代表子問題集合的中間所產(chǎn)生的圖可以得到簡(jiǎn)化。因此，代表子問題集合的中間或節(jié)點(diǎn)可以被略去?；蚬?jié)點(diǎn)可以被略去。 除起始節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且只有一個(gè)父輩節(jié)點(diǎn)。除起始節(jié)點(diǎn)外，每個(gè)節(jié)點(diǎn)有且只有一個(gè)父輩節(jié)點(diǎn)。CSUCSU

44、CSUCSUCSUCSUCSUCSUCSU2.3 謂詞邏輯法謂詞演算能夠表達(dá)命題邏輯所不能表達(dá)的復(fù)雜問題。更具謂詞演算能夠表達(dá)命題邏輯所不能表達(dá)的復(fù)雜問題。更具體地說，一階謂詞邏輯法具有：體地說，一階謂詞邏輯法具有：自然性自然性、精確性精確性、有限性有限性和和易易實(shí)現(xiàn)實(shí)現(xiàn)的特點(diǎn)，適宜于精確知識(shí)表示和相應(yīng)的邏輯推理。的特點(diǎn)，適宜于精確知識(shí)表示和相應(yīng)的邏輯推理。2.3.1 謂詞演算1.語法和語義語法和語義(Syntax & Semantics)基本符號(hào)基本符號(hào)：謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)、常量符號(hào)、：謂詞符號(hào)、變量符號(hào)、函數(shù)符號(hào)、常量符號(hào)、括號(hào)和逗號(hào)。括號(hào)和逗號(hào)。 常量符號(hào)常量符號(hào)：用來

45、表示論域內(nèi)的物體或?qū)嶓w，可以是具體的，：用來表示論域內(nèi)的物體或?qū)嶓w，可以是具體的，也可以是抽象的。也可以是抽象的。變量符號(hào)變量符號(hào)：表示不明確涉及哪一個(gè)個(gè)體。：表示不明確涉及哪一個(gè)個(gè)體。函數(shù)符號(hào)函數(shù)符號(hào)：表示某個(gè)體與其他個(gè)體之間的：表示某個(gè)體與其他個(gè)體之間的映射關(guān)系映射關(guān)系。 謂詞符號(hào)謂詞符號(hào)：用于刻畫個(gè)體的性質(zhì)、狀態(tài)或個(gè)體間的：用于刻畫個(gè)體的性質(zhì)、狀態(tài)或個(gè)體間的非映射非映射關(guān)系關(guān)系，謂詞的語義是由使用者根據(jù)需要人為地定義，當(dāng)謂詞的，謂詞的語義是由使用者根據(jù)需要人為地定義，當(dāng)謂詞的變量用特定個(gè)體取代時(shí)，謂詞就具有一確定的邏輯真值變量用特定個(gè)體取代時(shí)，謂詞就具有一確定的邏輯真值T或或F。 CSU

46、CSUCSUCSUCSUCSUCSUCSUCSU原子公式原子公式：由單個(gè)謂詞符號(hào)和項(xiàng)（個(gè)體常量、變量、函數(shù)）：由單個(gè)謂詞符號(hào)和項(xiàng)（個(gè)體常量、變量、函數(shù)）構(gòu)成的公式。原子公式是謂詞演算基本積木塊。構(gòu)成的公式。原子公式是謂詞演算基本積木塊。例如，要表示例如，要表示“機(jī)器人（機(jī)器人（ROBOT）在號(hào)房間（）在號(hào)房間（r1）內(nèi)）內(nèi)”，如下圖所示，可以應(yīng)用原子公式：如下圖所示，可以應(yīng)用原子公式： 當(dāng)機(jī)器人（當(dāng)機(jī)器人（ROBOT）移到房間移到房間r2時(shí)，原子公式可以表示為：時(shí)，原子公式可以表示為：INROOM (ROBOT，r2) 這兩個(gè)原子公式的通用形式就是：這兩個(gè)原子公式的通用形式就是： CSUCSU

47、CSUCSUCSUCSUCSUCSUCSU2.連詞和量詞連詞和量詞(Connective & Quantifiers)(1) 連詞連詞與與合取合?。╟onjunction）：合取就是用連詞）：合取就是用連詞把幾個(gè)謂詞公把幾個(gè)謂詞公式連接起來而構(gòu)成的公式，式連接起來而構(gòu)成的公式，合取項(xiàng)是合取式的每個(gè)組成部分合取項(xiàng)是合取式的每個(gè)組成部分。 例：例：LIKE( I，MUSIC )LIKE( I，PAINTING ) 或或析取析取（disjunction）：析取就是用連詞）：析取就是用連詞把幾個(gè)謂詞公式把幾個(gè)謂詞公式連接起來而構(gòu)成的公式，連接起來而構(gòu)成的公式，析取項(xiàng)是析取式的每個(gè)組成部分析取項(xiàng)

48、是析取式的每個(gè)組成部分。 例：例：PLAYS( LIULI，BASKETBALL )PLAYS( LIULI，F(xiàn)OOTBALL )又如又如，“李的母親和他的父李的母親和他的父親結(jié)婚親結(jié)婚”這句話的原子公式為：這句話的原子公式為：這里使用了兩個(gè)函數(shù)關(guān)系。這里使用了兩個(gè)函數(shù)關(guān)系。CSUCSUCSUCSUCSUCSUCSUCSUCSU蘊(yùn)涵蘊(yùn)涵（Implication）：蘊(yùn)涵）：蘊(yùn)涵“”表示表示“如果如果-那么那么”的語句。的語句。用連詞用連詞連接兩個(gè)公式所構(gòu)成的公式叫做蘊(yùn)涵。連接兩個(gè)公式所構(gòu)成的公式叫做蘊(yùn)涵。IFA THEN B 前項(xiàng)前項(xiàng)（左部左部） 后項(xiàng)后項(xiàng)（右部右部） 例：例：RUNS( LIU

49、HUA，F(xiàn)ASTEST ) WINS( LIUHUA，CHAMPION ) 非（非（NOT）：表示否定，、：表示否定，、均可表示。均可表示。 例：例：INROOM( ROBOT，r2 )（機(jī)器人不在（機(jī)器人不在2號(hào)房間內(nèi)。）號(hào)房間內(nèi)。） (2) 量量詞詞全稱量詞全稱量詞(Universal Quantifier)：若一個(gè)原子公式：若一個(gè)原子公式P(x)，對(duì)，對(duì)于所有可能變量于所有可能變量x都具有都具有T值，則用值，則用( x)P(x)表示。表示。 例：例：( x)ROBOT(x) COLOR(x，GRAY) ( x)Student(x) Uniform(x，Color) CSUCSUCSUCS

50、UCSUCSUCSUCSUCSU存在量詞存在量詞(Existential Quantifier)：若一個(gè)原子公式：若一個(gè)原子公式P(x)，至，至少有一個(gè)變?cè)儆幸粋€(gè)變?cè)獂，可使得，可使得P(x)為為T值，則用值，則用( x)P(x)表示。表示。 例：例：( x)INROOM(x，r1)（1號(hào)房間內(nèi)有個(gè)物體）號(hào)房間內(nèi)有個(gè)物體）量化變?cè)炕冊(cè)?Quantified Variables)：被全稱或存在量詞量化了：被全稱或存在量詞量化了的變?cè)淖冊(cè)獂，也稱，也稱約束變量約束變量，沒有被量化的變量稱為，沒有被量化的變量稱為自由變量自由變量。 2.3.2 謂詞公式1.謂詞公式的定義謂詞公式的定義原子謂詞

51、公式原子謂詞公式：用：用P(x1，x2，xn)表示一個(gè)表示一個(gè)n元謂詞公式元謂詞公式其中其中P為為n元謂詞，元謂詞，x1，x2，xn為客體變量或變?cè)?。通常把為客體變量或變?cè)Ｍǔ０裀(x1，x2，xn)叫做原子公式，或原子謂詞公式。叫做原子公式，或原子謂詞公式。 CSUCSUCSUCSUCSUCSUCSUCSUCSU合式謂詞公式合式謂詞公式：由連詞、量詞把原子公式組成：由連詞、量詞把原子公式組成復(fù)合謂詞公式復(fù)合謂詞公式合式公式合式公式(WFF，well-formed formulas)的遞歸定義的遞歸定義：(1) 原子謂詞公式是合式公式。原子謂詞公式是合式公式。(2) 若若A為合式公式，則為合

52、式公式，則A也是一個(gè)合式公式。也是一個(gè)合式公式。(3) 若若A和和B都是合式公式，則都是合式公式，則(AB)，(AB)，(AB), (AB)也都是合式公式。也都是合式公式。(4) 若若A是合式公式，是合式公式，x為為A中的自由變?cè)?，則中的自由變?cè)?，則( x)A，( x)A是合是合式公式。式公式。(5) 只有按上述規(guī)則只有按上述規(guī)則(1)至至(4)求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。例題：對(duì)于所有的例題：對(duì)于所有的x，如果，如果x是整數(shù)，則是整數(shù)，則x為正的或者為負(fù)的。為正的或者為負(fù)的。設(shè)設(shè)I(x)表示表示“x是整數(shù)是整數(shù)”，P(x)表示表示“x是正數(shù)是正數(shù)”，N(x)表

53、示表示“x是是負(fù)數(shù)負(fù)數(shù)”( x) I(x) (P(x)N(x) CSUCSUCSUCSUCSUCSUCSUCSUCSU2. 合式公式的性質(zhì)合式公式的性質(zhì)如果如果P和和Q是兩個(gè)合式公式，則由這兩個(gè)合式公式所組成的是兩個(gè)合式公式，則由這兩個(gè)合式公式所組成的復(fù)合表達(dá)式可由下列真值表給出：復(fù)合表達(dá)式可由下列真值表給出： 等價(jià)等價(jià)（）：如果兩個(gè)合式公式，無論如何解釋，其真值表：如果兩個(gè)合式公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是都是相同的，那么我們就稱此兩合式公式是等價(jià)或等值等價(jià)或等值的。的。應(yīng)用上述真值表，能夠確立下列應(yīng)用上述真值表，能夠確立下列等價(jià)關(guān)系等價(jià)關(guān)系：(1) 否定

54、之否定否定之否定(P)等價(jià)于等價(jià)于P (2) PQ等價(jià)于等價(jià)于PQ（該公式常用來消除邏輯蘊(yùn)含符號(hào)）（該公式常用來消除邏輯蘊(yùn)含符號(hào)） CSUCSUCSUCSUCSUCSUCSUCSUCSU(3) 狄狄摩根定律摩根定律(PQ)等價(jià)于等價(jià)于PQ (PQ)等價(jià)于等價(jià)于PQ(4) 分配律分配律P(QR)等價(jià)于等價(jià)于(PQ)(PR)P(QR)等價(jià)于等價(jià)于(PQ)(PR)(5) 交換律交換律PQ等價(jià)于等價(jià)于QP PQ等價(jià)于等價(jià)于QP(6) 結(jié)合律結(jié)合律(PQ)R等價(jià)于等價(jià)于P(QR)(PQ)R等價(jià)于等價(jià)于P(QR)(7) 逆否律逆否律PQ等價(jià)于等價(jià)于QPCSUCSUCSUCSUCSUCSUCSUCSUCSU

55、此外，由對(duì)量詞的處理還可建立下列等價(jià)關(guān)系：此外，由對(duì)量詞的處理還可建立下列等價(jià)關(guān)系：(8) ( x) P(x)等價(jià)于等價(jià)于( x)P(x) ( x) P(x)等價(jià)于等價(jià)于( x)P(x)(9) ( x)P(x)Q(x)等價(jià)于等價(jià)于( x)P(x)( x)Q(x) ( x)P(x)Q(x)等價(jià)于等價(jià)于( x)P(x)( x)Q(x)(10) ( x)P(x)等價(jià)于等價(jià)于( y)P(y)( x)P(x)等價(jià)于等價(jià)于( y)P(y)上述最后兩個(gè)等價(jià)關(guān)系說明，上述最后兩個(gè)等價(jià)關(guān)系說明，在一個(gè)量化表達(dá)式中出現(xiàn)的在一個(gè)量化表達(dá)式中出現(xiàn)的量化變量是一類虛元量化變量是一類虛元，它可以用任何一個(gè)不在表達(dá)式中出現(xiàn)

56、過，它可以用任何一個(gè)不在表達(dá)式中出現(xiàn)過的其它變量符號(hào)來代替。的其它變量符號(hào)來代替。 CSUCSUCSUCSUCSUCSUCSUCSUCSU下面舉一個(gè)用謂詞演算來表示的英文句子的實(shí)例：下面舉一個(gè)用謂詞演算來表示的英文句子的實(shí)例：For every set x，there is a set y，such that the cardinality of y is greater than the cardinality of x這個(gè)英文句子可用謂詞演算表示為：這個(gè)英文句子可用謂詞演算表示為：( x)SET(x) ( y)( u)( v)SET(y)CARD(x，u)CARD(y，v)G(v，u)用用

57、一階謂詞邏輯法表示知識(shí)的步驟一階謂詞邏輯法表示知識(shí)的步驟如下：如下：(a)定義定義謂詞謂詞及及個(gè)體個(gè)體，確定每個(gè)謂詞和個(gè)體的確切含義；，確定每個(gè)謂詞和個(gè)體的確切含義；(b)根據(jù)所要表達(dá)的事物或概念，為每個(gè)謂詞中的根據(jù)所要表達(dá)的事物或概念，為每個(gè)謂詞中的變?cè)x以變?cè)x以特定的值，并考慮量化情況特定的值，并考慮量化情況；(c)根據(jù)所要表達(dá)的知識(shí)的語義，用根據(jù)所要表達(dá)的知識(shí)的語義，用適當(dāng)?shù)倪B接符號(hào)將各個(gè)適當(dāng)?shù)倪B接符號(hào)將各個(gè)謂詞連接起來謂詞連接起來，形成謂詞公式。，形成謂詞公式。 CSUCSUCSUCSUCSUCSUCSUCSUCSU例：太原市的夏天既干燥又炎熱例：太原市的夏天既干燥又炎熱首先定義謂詞

58、及個(gè)體：設(shè)首先定義謂詞及個(gè)體：設(shè)STATE（x，y，z）表示）表示x市在市在y季季節(jié)氣候處于節(jié)氣候處于z狀態(tài)。這是一個(gè)三元一階謂詞，涉及的個(gè)體有：太狀態(tài)。這是一個(gè)三元一階謂詞，涉及的個(gè)體有：太原，夏天，干燥或炎熱。將個(gè)體代入謂詞有原，夏天，干燥或炎熱。將個(gè)體代入謂詞有STATE（太原，夏天，干燥）和（太原，夏天，干燥）和STATE（太原，夏天，炎熱）（太原，夏天，炎熱）最后根據(jù)語義用聯(lián)結(jié)詞將它們聯(lián)結(jié)起來，得到最后根據(jù)語義用聯(lián)結(jié)詞將它們聯(lián)結(jié)起來，得到STATE（太原，夏天，干燥）（太原，夏天，干燥）STATE（太原，夏天，炎熱）（太原，夏天，炎熱） 例：人人愛勞動(dòng)；所有整數(shù)要么是偶數(shù)要么就是奇數(shù)

59、例：人人愛勞動(dòng)；所有整數(shù)要么是偶數(shù)要么就是奇數(shù)首先定義謂詞如下：首先定義謂詞如下：MAN（x）：）：x是人；是人；LOVE（x，y）：）：x愛愛y； I（x）：）：x是整數(shù)；是整數(shù)； E（x）：）：x是偶數(shù)；是偶數(shù)； O（x）：）：x是奇數(shù)；是奇數(shù)；根據(jù)題意用適當(dāng)?shù)倪B接符聯(lián)結(jié)起來，則有根據(jù)題意用適當(dāng)?shù)倪B接符聯(lián)結(jié)起來，則有 （ x x）（）（MAN（x） LOVE（x，labour） （ x x）I（x）（E（x）O（x） CSUCSUCSUCSUCSUCSUCSUCSUCSU例例3：要想出國(guó)留學(xué)，必須通過外語考試：要想出國(guó)留學(xué)，必須通過外語考試(默認(rèn)的論域?yàn)槿四J(rèn)的論域?yàn)槿?定義謂詞：設(shè)定義謂

60、詞：設(shè)Want（x，y）表示）表示x想要想要y， Pass（x，y）表示）表示x通過通過y； 定義個(gè)體：定義個(gè)體：goabroad表示出國(guó)留學(xué)，表示出國(guó)留學(xué)，flanguage表示外語考試；表示外語考試； 將個(gè)體代入謂詞，并按題意用適當(dāng)?shù)倪B接符聯(lián)結(jié)起來，將個(gè)體代入謂詞，并按題意用適當(dāng)?shù)倪B接符聯(lián)結(jié)起來，（ x）Pass（x，flanguage）Want（x，goabroad）3. 一階謂詞邏輯表示的特點(diǎn)一階謂詞邏輯表示的特點(diǎn)(1)自然性自然性：接近于自然語言的形式，表示問題易于被人理解；：接近于自然語言的形式，表示問題易于被人理解；(2)精確性精確性：具有精確的邏輯真值，適宜于表示精確性知識(shí)；：具有精確的邏輯真