第二章知識表示方法

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

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

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

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

5、常采用試探式搜索方法試探式搜索方法。也就是說，這些方。也就是說，這些方法是通過在某個可能的解空間內(nèi)搜尋一個解來求解問題。這法是通過在某個可能的解空間內(nèi)搜尋一個解來求解問題。這種種基于解答空間的問題表示和求解方法就是狀態(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)、棋局對弈等舉例：天氣、身體指標(biāo)、棋局

6、對弈等算符算符(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)夫有一條船，過河時，除把它們?nèi)克偷接野度ァ＾r(nóng)夫有一條船，過河時，除農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣，且農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣，且狐貍要吃雞，雞要吃小米，除非農(nóng)夫在。試用狀態(tài)表狐貍要吃雞，雞要吃小米，除非農(nóng)夫在。試用狀態(tài)表示法規(guī)劃出一個確保全部對

7、象安全過河的計劃。示法規(guī)劃出一個確保全部對象安全過河的計劃。提示：提示：用四元向量用四元向量(農(nóng)夫、狐貍、雞、小米農(nóng)夫、狐貍、雞、小米)表示狀態(tài)表示狀態(tài)，每個每個分量取分量取0或或1，1表示船在左岸，表示船在左岸，0在右岸；在右岸； 把每次過河的一種具體安排作為一個算符，例如把每次過河的一種具體安排作為一個算符，例如可用可用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 式中每個元素式中每個元素qi (i=0,1，n)為集合的分量，稱為為集合的分量，稱為狀態(tài)變量狀態(tài)變量。算符算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為符或算符。操作符可為走步走步、過程過程、規(guī)則規(guī)則、數(shù)學(xué)算子數(shù)學(xué)算子、運算符號運算符號或或邏輯符號邏輯符號等。等。問題的狀態(tài)空間問題的狀態(tài)空間：是一個表示某問題全部可能狀態(tài)及其關(guān)系：是一個表示某問題全部可能狀態(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個編有個編有1至至15并放在并放在44方格棋盤上的可走動的棋子方格棋盤上的可走動的棋子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進空格，這也可以理解為移動空格。圖中繪出了兩種棋局，即空格，這也可以理解為移動空格。圖中繪出了兩種棋局，即初始初始棋局和目標(biāo)棋局棋局和目標(biāo)棋局（書本（書本29頁圖頁圖

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

13、棋局開始，試探由每一合法走步得到的各種新棋局，從初始棋局開始，試探由每一合法走步得到的各種新棋局，然后計算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達(dá)然后計算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達(dá)到目標(biāo)棋局為止。到目標(biāo)棋局為止。把初始狀態(tài)可達(dá)到的各狀態(tài)所組成的空間設(shè)想把初始狀態(tài)可達(dá)到的各狀態(tài)所組成的空間設(shè)想為一幅由各種狀態(tài)對應(yīng)的節(jié)點組成的圖，為一幅由各種狀態(tài)對應(yīng)的節(jié)點組成的圖，這種圖稱為這種圖稱為狀態(tài)圖。狀態(tài)圖。圖圖中中每個節(jié)點標(biāo)有它所代表的棋局每個節(jié)點標(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)；遞增地建立起算符試驗序列，建立起算符試驗序列，直到達(dá)到目標(biāo)狀態(tài)為止直到達(dá)到目標(biāo)狀態(tài)為止。某個問題的狀態(tài)描述，須經(jīng)歷如下某個問題的狀態(tài)描述，須經(jīng)歷如下3個步驟個步

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需要說明的是：需要說明的是： 可能存在可能存在多個算符序列多個算符序列都可使問題達(dá)到目標(biāo)狀都可使問題達(dá)到目標(biāo)狀態(tài)，這就得到態(tài)，這就得到多個解

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

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

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

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

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

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

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

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

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

25、狀態(tài)，W猴子的水平位置猴子的水平位置x當(dāng)猴子在箱子頂上時取當(dāng)猴子在箱子頂上時取x=1；否則?。环駝t取x=0Y箱子的水平位置箱子的水平位置 z當(dāng)猴子摘到香蕉時取當(dāng)猴子摘到香蕉時取z=1；否則??；否則取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSU這個問題中的這個問題中的操作操作(算符算符)用產(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。這種強加于操作的適用性條件，叫做。這種強加于操作的適用性條件，叫做產(chǎn)生式規(guī)則的先決條件產(chǎn)生式規(guī)則的先決條件。CSUCSUCSUCSUCSUCSUCSUCSUCSU (3) climbbox：猴子爬上箱頂，即有：猴子爬上箱頂，即有（W，0，W，z） （W，1，W，z）在應(yīng)用算符在應(yīng)用算符climbbox時也必須注意到，猴子和箱子時也必須注意到，猴子和箱

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時，要求猴子和箱子都在位置時，要求猴子和箱子都在位置c上，并且猴子已在上，并且猴子已在箱子頂上，即箱子頂上，即x=1。 CSUCSUCSUCSUCSUCSUCSUCSUCSU本問題中，令初始狀態(tài)為本問題中，令初始狀態(tài)為(a, 0, b, 0)。這時，。這時，goto(U)是唯一是唯一適用的操作，并導(dǎo)致下一狀態(tài)適用的操作，

28、并導(dǎo)致下一狀態(tài)(U, 0, b, 0)，把所有適用的操作繼，把所有適用的操作繼續(xù)應(yīng)用于每個狀態(tài)，直至任何最后一列元素為續(xù)應(yīng)用于每個狀態(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)橐粋€子問題的集合，集合里述，通過一系列變換把原問題變?yōu)橐粋€子問題的集合，集合里的每個子問題被進一步簡化為子子問題，最終的這些子問題的每個子問題被進一步簡化為子子問題，最終的這些子問題的解答可以直接得到，從而得到原始問題的解答。的解答可以直接得到，從而得到原始問題的解答。本原問題本原問題其解答可其解答可通過一步通過一步（運算、走步、操作等）而（運算、走步、操作等）而直接得到的子問題。直接得到的

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

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

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

33、子從柱子2至柱子至柱子3的雙圓盤問題。的雙圓盤問題。CSUCSUCSUCSUCSUCSUCSUCSUCSU可以看出，分解后的子問題都比原始問題要簡單。其可以看出，分解后的子問題都比原始問題要簡單。其中子問中子問題題2 2可作為本原問題可作為本原問題考慮，因為它的求解只包含一步移動操作?？紤]，因為它的求解只包含一步移動操作。應(yīng)用一系列相似的推理，應(yīng)用一系列相似的推理，子問題子問題1 1和和子問題子問題3 3也也可進一步被歸約為可進一步被歸約為本原問題本原問題。下面給出梵塔問題的。下面給出梵塔問題的歸約過程圖歸約過程圖（也稱做（也稱做與或圖與或圖）。）。思考：思考：1 1圓盤問題要走幾步？圓盤問題

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

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

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

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

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

39、SUCSU 與或圖中與或圖中可解節(jié)點可解節(jié)點的一般定義：的一般定義： (1) 終葉節(jié)點是可解節(jié)點終葉節(jié)點是可解節(jié)點（因為它們（因為它們與本原問題相關(guān)連與本原問題相關(guān)連）。）。 (2) 如果某個如果某個非終葉節(jié)點含有或后繼節(jié)點非終葉節(jié)點含有或后繼節(jié)點，那么只要當(dāng)其后繼，那么只要當(dāng)其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。 (3) 如果某個如果某個非終葉節(jié)點含有與后繼節(jié)點非終葉節(jié)點含有與后繼節(jié)點，那么只有當(dāng)其后繼，那么只有當(dāng)其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。 終葉節(jié)點用字母終葉節(jié)

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

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

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

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

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

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

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

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

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

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

50、UCSUCSUCSUCSUCSU存在量詞存在量詞(Existential Quantifier)：若一個原子公式：若一個原子公式P(x)，至，至少有一個變元少有一個變元x，可使得，可使得P(x)為為T值，則用值，則用( x)P(x)表示。表示。 例：例：( x)INROOM(x，r1)（1號房間內(nèi)有個物體）號房間內(nèi)有個物體）量化變元量化變元(Quantified Variables)：被全稱或存在量詞量化了：被全稱或存在量詞量化了的變元的變元x，也稱，也稱約束變量約束變量，沒有被量化的變量稱為，沒有被量化的變量稱為自由變量自由變量。 2.3.2 謂詞公式1.謂詞公式的定義謂詞公式的定義原子謂詞

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

52、式公式，則A也是一個合式公式。也是一個合式公式。(3) 若若A和和B都是合式公式，則都是合式公式，則(AB)，(AB)，(AB), (AB)也都是合式公式。也都是合式公式。(4) 若若A是合式公式，是合式公式，x為為A中的自由變元，則中的自由變元，則( x)A，( x)A是合是合式公式。式公式。(5) 只有按上述規(guī)則只有按上述規(guī)則(1)至至(4)求得的那些公式，才是合式公式。求得的那些公式，才是合式公式。例題：對于所有的例題：對于所有的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是兩個合式公式，則由這兩個合式公式所組成的是兩個合式公式，則由這兩個合式公式所組成的復(fù)合表達(dá)式可由下列真值表給出：復(fù)合表達(dá)式可由下列真值表給出： 等價等價（）：如果兩個合式公式，無論如何解釋，其真值表：如果兩個合式公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是都是相同的，那么我們就稱此兩合式公式是等價或等值等價或等值的。的。應(yīng)用上述真值表，能夠確立下列應(yīng)用上述真值表，能夠確立下列等價關(guān)系等價關(guān)系：(1) 否定

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

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

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

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

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

59、例：人人愛勞動；所有整數(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：要想出國留學(xué)，必須通過外語考試：要想出國留學(xué)，必須通過外語考試(默認(rèn)的論域為人默認(rèn)的論域為人)定義謂詞：設(shè)定義謂

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