第二章知識表示方法

1、第二章 知識表示方法2.1 狀態(tài)空間法2.2 問題歸約法2.3 謂詞邏輯法2.4 語義網(wǎng)絡法2.5 框架表示法2.6 本體技術2.7 過程表示CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU每種以每種以知識知識和和符號操作符號操作為基礎的智能系統(tǒng)，其為基礎的智能系統(tǒng)，其問題求解方法一般需要對解答過程進行某種搜索。問題求解方法一般需要對解答過程進行某種搜索。不過，在搜索過程開始之前，必須先用某種方法或不過，在搜索過程開始之前，必須先用某種方法或某幾種方法的混合來某幾種方法的混合來表示

2、問題表示問題。本章主要討論知識表示的問題，介紹了本章主要討論知識表示的問題，介紹了7種知種知識表示方法：狀態(tài)空間法、問題歸約法、謂詞演算識表示方法：狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡法、框架表示法、本體技術和過程表法、語義網(wǎng)絡法、框架表示法、本體技術和過程表示法。其中要求掌握示法。其中要求掌握狀態(tài)空間法、問題歸約法、謂狀態(tài)空間法、問題歸約法、謂詞演算法、語義網(wǎng)絡法的要點及其之間的關系詞演算法、語義網(wǎng)絡法的要點及其之間的關系。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

3、1.1.知識表示的基本概念知識表示的基本概念知識表示實際上就是對人類知識的一種描述，知識表示實際上就是對人類知識的一種描述，以以把人類知識表示成機器能夠處理的數(shù)據(jù)結構。知識表把人類知識表示成機器能夠處理的數(shù)據(jù)結構。知識表示的過程就是把知識編碼成某種數(shù)據(jù)結構的過程示的過程就是把知識編碼成某種數(shù)據(jù)結構的過程。 2. 知識表示方法分類知識表示方法分類(1)(1)從作用范圍來劃分從作用范圍來劃分: :常識性、領域性常識性、領域性 (2)(2)從知識的作用及表示來劃分：事實性、過程從知識的作用及表示來劃分：事實性、過程性、控制性性、控制性 (3)(3)從知識的確定性來劃分：確定性、不確定性從知識的確定性

4、來劃分：確定性、不確定性 (4)(4)從知識的結構及表現(xiàn)形式來劃分：邏輯性、從知識的結構及表現(xiàn)形式來劃分：邏輯性、形象性形象性CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.1 狀態(tài)空間法問題求解涉及歸約、推斷、決策、規(guī)劃、常識推理、定問題求解涉及歸約、推斷、決策、規(guī)劃、常識推理、定理證明等相關的過程?，F(xiàn)實世界中理證明等相關的過程?，F(xiàn)實世界中問題求解過程問題求解過程可以可以看做是看做是一個一個搜索搜索或者或者推理推理過程。過程。 推理過程實際上也是一個搜索過程推理過程實際上也是

5、一個搜索過程，它在知識庫中搜索，它在知識庫中搜索和前提條件相匹配的規(guī)則，而后利用這些規(guī)則進行推理。所和前提條件相匹配的規(guī)則，而后利用這些規(guī)則進行推理。所以，以，任何問題求解的本質都是一個搜索過程任何問題求解的本質都是一個搜索過程，并且發(fā)現(xiàn)許多，并且發(fā)現(xiàn)許多問題求解方法常常采用問題求解方法常常采用試探式搜索方法試探式搜索方法。也就是說，這些方。也就是說，這些方法是通過在某個可能的解空間內搜尋一個解來求解問題。這法是通過在某個可能的解空間內搜尋一個解來求解問題。這種種基于解答空間的問題表示和求解方法就是狀態(tài)空間法基于解答空間的問題表示和求解方法就是狀態(tài)空間法，它，它是是以狀態(tài)和算符為基礎來表示和求

6、解問題以狀態(tài)和算符為基礎來表示和求解問題的。的。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU狀態(tài)狀態(tài)(state)(state)：表示問題解法過程中每：表示問題解法過程中每一步問題狀況的數(shù)據(jù)結構；一步問題狀況的數(shù)據(jù)結構； 舉例：天氣、身體指標、棋局對弈等舉例：天氣、身體指標、棋局對弈等算符算符(operator)(operator)：把問題從一種狀態(tài)變：把問題從一種狀態(tài)變換為另一種狀態(tài)的手段或操作；換為另一種狀態(tài)的手段或操作；CSUCSUCSUCSUCSUCSUCSUCSUCS

7、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU例例1 1 農(nóng)夫、狐貍、雞、小米在一條河的左岸，現(xiàn)在要農(nóng)夫、狐貍、雞、小米在一條河的左岸，現(xiàn)在要把它們全部送到右岸去。農(nóng)夫有一條船，過河時，除把它們全部送到右岸去。農(nóng)夫有一條船，過河時，除農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣，且農(nóng)夫外，船上至多能載狐貍、雞和小米中的一樣，且狐貍要吃雞，雞要吃小米，除非農(nóng)夫在。試用狀態(tài)表狐貍要吃雞，雞要吃小米，除非農(nóng)夫在。試用狀態(tài)表示法規(guī)劃出一個確保全部對象安全過河的計劃。示法規(guī)劃出一個確保全部對象安全過河的計劃。提示：提示：用四元向量用四元向量(

8、農(nóng)夫、狐貍、雞、小米農(nóng)夫、狐貍、雞、小米)表示狀態(tài)表示狀態(tài)，每個每個分量取分量取0或或1，1表示船在左岸，表示船在左岸，0在右岸；在右岸； 把每次過河的一種具體安排作為一個算符，例如把每次過河的一種具體安排作為一個算符，例如可用可用L(f，j)表示從左岸將第表示從左岸將第j樣東西送到右岸樣東西送到右岸(j1是狐是狐貍貍，j2是雞，是雞，j3是小米，是小米，j0表示除農(nóng)夫外不載任表示除農(nóng)夫外不載任何東西何東西)，f表示農(nóng)夫始終在船上。表示農(nóng)夫始終在船上。R(f，j)表示從右岸表示從右岸將第將第j樣東西送到左岸樣東西送到左岸。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

9、CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU(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)夫、狐貍、雞、

10、小米）過河問題（農(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)CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.1.1 問題狀態(tài)描述1.形式化形式化定義定義狀態(tài)狀態(tài)(state)：為描述某類不同事物間差別而引入的一組：為描述某類不同事物間差別而引入

11、的一組最少最少變變量量 q0, q1, , qn 的的有序集合，其矢量形式為：有序集合，其矢量形式為：Q=q0, q1, , qnT 式中每個元素式中每個元素qi (i=0,1，n)為集合的分量，稱為為集合的分量，稱為狀態(tài)變量狀態(tài)變量。算符算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。操作符可為符或算符。操作符可為走步走步、過程過程、規(guī)則規(guī)則、數(shù)學算子數(shù)學算子、運算符號運算符號或或邏輯符號邏輯符號等。等。問題的狀態(tài)空間問題的狀態(tài)空間：是一個表示某問題全部可能狀態(tài)及其關系：是一個表示某問題全部可能狀態(tài)及其關系的的圖圖，狀態(tài)空間記為三

12、元結構，狀態(tài)空間記為三元結構(S，F(xiàn)，G)，即，即初始狀態(tài)集合初始狀態(tài)集合S、操操作算符集合作算符集合F以及以及目標狀態(tài)集合目標狀態(tài)集合G。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.狀態(tài)空間表示法詳釋狀態(tài)空間表示法詳釋我們先用我們先用數(shù)碼難題數(shù)碼難題(puzzle problem)來說明狀態(tài)空間表示的來說明狀態(tài)空間表示的概念。由概念。由15個編有個編有1至至15并放在并放在44方格棋盤上的可走動的棋方格棋盤上的可走動的棋子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋

13、子走子組成。棋盤上總有一格是空的，以便可能讓空格周圍的棋子走進空格，這也可以理解為移動空格。圖中繪出了兩種棋局，即進空格，這也可以理解為移動空格。圖中繪出了兩種棋局，即初初始棋局和目標棋局始棋局和目標棋局（書本（書本29頁圖頁圖2.1），它們對應于該下棋問題），它們對應于該下棋問題的的初始狀態(tài)初始狀態(tài)和和目標狀態(tài)目標狀態(tài)。如何把初始棋局變換為目標棋局呢？問題的解答就是某個合如何把初始棋局變換為目標棋局呢？問題的解答就是某個合適的棋子走步序列，如適的棋子走步序列，如“左移棋子左移棋子12，下移棋子，下移棋子15，右移棋子，右移棋子4，”等等。等等。1515數(shù)碼難題數(shù)碼難題最直接的求解方法是嘗試各

14、種不同走步最直接的求解方法是嘗試各種不同走步，直到偶，直到偶然得到目標棋局為止，這種嘗試然得到目標棋局為止，這種嘗試本質上是本質上是一種試探性的搜索一種試探性的搜索。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU從初始棋局開始，試探由每一合法走步得到的各種新棋局，從初始棋局開始，試探由每一合法走步得到的各種新棋局，然后計算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達然后計算再走一步而得到的下一組棋局。這樣繼續(xù)下去，直至達到目標棋局為止。到目標棋局為止。把初始狀態(tài)可達到的各狀

15、態(tài)所組成的空間設想把初始狀態(tài)可達到的各狀態(tài)所組成的空間設想為一幅由各種狀態(tài)對應的節(jié)點組成的圖，為一幅由各種狀態(tài)對應的節(jié)點組成的圖，這種圖稱為這種圖稱為狀態(tài)圖。狀態(tài)圖。圖圖中中每個節(jié)點標有它所代表的棋局每個節(jié)點標有它所代表的棋局。首先把適用的算符用于初始狀。首先把適用的算符用于初始狀態(tài)，產(chǎn)生新的狀態(tài)；然后，再把另一些適用算符用于這些新的狀態(tài)，產(chǎn)生新的狀態(tài)；然后，再把另一些適用算符用于這些新的狀態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標狀態(tài)為止。（態(tài)；這樣繼續(xù)下去，直至產(chǎn)生目標狀態(tài)為止。（29頁圖頁圖2.2） CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

16、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU我們用我們用狀態(tài)空間法狀態(tài)空間法表示下述過程：表示下述過程：首先將適用的首先將適用的算符算符作用于初始狀態(tài)作用于初始狀態(tài)，產(chǎn)生中間狀態(tài)，再選擇適用的，產(chǎn)生中間狀態(tài)，再選擇適用的算符算符作用于當前狀態(tài)；遞增地作用于當前狀態(tài)；遞增地建立起算符試驗序列，建立起算符試驗序列，直到達到目標狀態(tài)為止直到達到目標狀態(tài)為止。某個問題的狀態(tài)描述，須經(jīng)歷如下某個問題的狀態(tài)描述，須經(jīng)歷如下3個步驟個步驟： （1）定義）定義狀態(tài)的描述方式狀態(tài)的描述方式； （2）用所定義的狀態(tài)描述形式把問題的所有可能）用所定義的狀態(tài)描述形式把問題的所有可能狀態(tài)表示出來，關鍵

17、是狀態(tài)表示出來，關鍵是確定問題的初始狀態(tài)確定問題的初始狀態(tài)描述描述集合集合和和目標狀態(tài)目標狀態(tài)描述描述集合集合； （3 3）定義）定義一組算符一組算符，利用這組算符可把問題由一，利用這組算符可把問題由一種狀態(tài)轉變?yōu)榱硪环N狀態(tài)。種狀態(tài)轉變?yōu)榱硪环N狀態(tài)。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU需要說明的是：需要說明的是： 可能存在可能存在多個算符序列多個算符序列都可使問題達到目標狀都可使問題達到目標狀態(tài)，這就得到態(tài)，這就得到多個解多個解。其中，有的所使用算符較少，。其中，有的所

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

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

20、一對節(jié)點用弧線連接起來，從一：一對節(jié)點用弧線連接起來，從一個節(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é)點或祖先；CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

21、UCSUCSUCSUCSUCSUCSUCSUCSU 路徑路徑：某個節(jié)點序列：某個節(jié)點序列 (ni1, ni2, , nik ) ，當，當j=2，3，k時，如果對于每一個時，如果對于每一個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é)點所有弧線代價之和。 顯式表示顯式

22、表示：各狀態(tài)節(jié)點及其具有代價的弧線由一張表明確：各狀態(tài)節(jié)點及其具有代價的弧線由一張表明確給出。此表可能列出該圖中的每一節(jié)點、它的后繼節(jié)點以及連給出。此表可能列出該圖中的每一節(jié)點、它的后繼節(jié)點以及連接弧線的代價。接弧線的代價。 隱式表示隱式表示：節(jié)點的無限集合：節(jié)點的無限集合si作為作為起始節(jié)點是已知起始節(jié)點是已知。后后繼節(jié)點算符繼節(jié)點算符L也已知也已知，它作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部，它作用于任一節(jié)點以產(chǎn)生該節(jié)點的全部后繼節(jié)點和各連接弧線的代價。后繼節(jié)點和各連接弧線的代價。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

23、UCSUCSUCSUCSUCSUCSUCSU2.圖的顯式和隱式表示圖的顯式和隱式表示 圖可以被顯式說明或隱式說明，圖可以被顯式說明或隱式說明，顯式表示對于大型的圖顯式表示對于大型的圖不切實際的不切實際的，而對于有無限節(jié)點集合的圖更是不可能。，而對于有無限節(jié)點集合的圖更是不可能?？紤]引入后繼節(jié)點算符的方法來隱式表示狀態(tài)空間圖?？紤]引入后繼節(jié)點算符的方法來隱式表示狀態(tài)空間圖。后繼節(jié)點算符集后繼節(jié)點算符集L也是已知的，也是已知的，把適用的后繼算符應用于把適用的后繼算符應用于si的成員和它們的后繼節(jié)點以及這些后繼節(jié)點的后繼節(jié)點的成員和它們的后繼節(jié)點以及這些后繼節(jié)點的后繼節(jié)點，如，如此無限制地進行下去，

24、此無限制地進行下去，最后由最后由L和和si所規(guī)定的隱式圖變?yōu)轱@所規(guī)定的隱式圖變?yōu)轱@示圖示圖。把后繼算符作用于節(jié)點的過程，實際上就是擴展該節(jié)。把后繼算符作用于節(jié)點的過程，實際上就是擴展該節(jié)點的過程。因此，通過搜索狀態(tài)空間以求得算符序列的解答點的過程。因此，通過搜索狀態(tài)空間以求得算符序列的解答過程，就是使隱式圖變?yōu)轱@式并包含目標的過程。過程，就是使隱式圖變?yōu)轱@式并包含目標的過程。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU問題的表示對求解工作量有很大的影響。人們顯然希望問題的表示

25、對求解工作量有很大的影響。人們顯然希望用用較小的狀態(tài)空間表示較小的狀態(tài)空間表示。許多似乎很難的問題，當表示適當時就。許多似乎很難的問題，當表示適當時就可能具有小而簡單的狀態(tài)空間。如對十五數(shù)碼難題的初始狀態(tài)可能具有小而簡單的狀態(tài)空間。如對十五數(shù)碼難題的初始狀態(tài)表示，可規(guī)定表示，可規(guī)定15460條算符，即左移棋子條算符，即左移棋子1，右移棋子，右移棋子1，上移棋子，上移棋子1，下移棋子，下移棋子1，左移棋子，左移棋子2，下移棋子，下移棋子15，但，但我們很快就會發(fā)現(xiàn)，只要左右上下移動空格，那么就可用我們很快就會發(fā)現(xiàn)，只要左右上下移動空格，那么就可用4條條算符代替上述算符代替上述60條算符?？梢?，移

26、動空格是一種較好的表示條算符?？梢?，移動空格是一種較好的表示。因此，。因此，對于同一問題，表示方法可能有多種。對于同一問題，表示方法可能有多種。在求解問題時在求解問題時, ,首先應考慮如何表示問題，之后再改進表示方法首先應考慮如何表示問題，之后再改進表示方法。 2.1.3 狀態(tài)空間表示舉例 下面介紹另一個狀態(tài)空間表示的例子下面介紹另一個狀態(tài)空間表示的例子CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU例例2猴子和香蕉問題猴子和香蕉問題( monkey and banana prob

27、lem )在一個房間內有一只猴子在一個房間內有一只猴子(可把這只猴子看做一個機器人可把這只猴子看做一個機器人)、一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足一個箱子和一束香蕉。香蕉掛在天花板下方，但猴子的高度不足以碰到它。那么這只猴子怎樣才能摘到香蕉呢？圖以碰到它。那么這只猴子怎樣才能摘到香蕉呢？圖2.4表示出猴表示出猴子、香蕉和箱子在房間內的相對位置子、香蕉和箱子在房間內的相對位置。 用一個四元表列用一個四元表列(W, x, Y, z)來表示這個問題的狀態(tài)，來表示這個問題的狀態(tài)，W猴子的水平位置猴子的水平位置x當猴子在箱子頂上時取當猴子在箱子頂上時取x=1；否則取；否則取x=0Y

28、箱子的水平位置箱子的水平位置 z當猴子摘到香蕉時取當猴子摘到香蕉時取z=1；否則??；否則取z=0CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU這個問題中的這個問題中的操作操作(算符算符)用產(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，

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

30、） （W，1，W，z）在應用算符在應用算符climbbox時也必須注意到，猴子和箱子時也必須注意到，猴子和箱子應當在同一位置上，而且猴子不在箱頂上，即應當在同一位置上，而且猴子不在箱頂上，即x=0。(4) grasp：猴子摘到香蕉，即有：猴子摘到香蕉，即有（c，1，c，0） （c，1，c，1）其中，其中，c是香蕉正下方的地板位置，在應用算符是香蕉正下方的地板位置，在應用算符grasp時，要求猴子和箱子都在位置時，要求猴子和箱子都在位置c上，并且猴子已在上，并且猴子已在箱子頂上，即箱子頂上，即x=1。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCS

31、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU本問題中，令初始狀態(tài)為本問題中，令初始狀態(tài)為(a, 0, b, 0)。這時，。這時，goto(U)是唯一是唯一適用的操作，并導致下一狀態(tài)適用的操作，并導致下一狀態(tài)(U, 0, b, 0)，把所有適用的操作繼，把所有適用的操作繼續(xù)應用于每個狀態(tài)，直至任何最后一列元素為續(xù)應用于每個狀態(tài)，直至任何最后一列元素為1的目標狀態(tài)表列的目標狀態(tài)表列出現(xiàn)，我們就能夠得到狀態(tài)空間圖出現(xiàn)，我們就能夠得到狀態(tài)空間圖。goto(b)，pushbox(c)，climbbox，grasp 目標狀態(tài)目標狀態(tài)V=c，climbbox(b，1，b，0)（U，0

32、，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=VgraspCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.2 問題歸約法問題歸約是一種問題表示與求解方法問題歸約是一種問題表示與求解方法。已知原始問題的描已知原始問題的描述，通過一系列變換把原問題變?yōu)橐粋€子問題的集合，集合里述，通過一系列變換把原問題變?yōu)橐粋€子問題的集合

33、，集合里的每個子問題被進一步簡化為子子問題，最終的這些子問題的每個子問題被進一步簡化為子子問題，最終的這些子問題的解答可以直接得到，從而得到原始問題的解答。的解答可以直接得到，從而得到原始問題的解答。本原問題本原問題其解答可其解答可通過一步通過一步（運算、走步、操作等）而（運算、走步、操作等）而直接得到的子問題。直接得到的子問題。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.1 問題歸約描述示例：梵塔難題（河內塔、漢諾塔，起源于古印度）示例：梵塔難題（河內塔、漢諾塔，起源

34、于古印度）最初，由大到小的最初，由大到小的3 3個圓盤自下而上都堆在柱子個圓盤自下而上都堆在柱子1 1上，要上，要求把所有圓盤都移到柱子求把所有圓盤都移到柱子3 3上。上。要求：要求：(1) (1) 一次只能移一個盤子；一次只能移一個盤子；(2) (2) 盤子只許在三根柱子上存放；盤子只許在三根柱子上存放； (3) (3) 永遠不許有大盤壓著小盤。永遠不許有大盤壓著小盤。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU分析過程：分析過程：1、要把所有圓盤移至柱子、要把所有圓盤移至

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

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

37、UCSUCSUCSUCSUCSUCSU（2）移動圓盤）移動圓盤C從柱子從柱子1至柱子至柱子3的單圓盤問題；的單圓盤問題；（3）移動圓盤）移動圓盤A和和B從柱子從柱子2至柱子至柱子3的雙圓盤問題。的雙圓盤問題。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU可以看出，分解后的子問題都比原始問題要簡單。其可以看出，分解后的子問題都比原始問題要簡單。其中中子問子問題題2 2可作為本原問題可作為本原問題考慮，因為它的求解只包含一步移動操作?？紤]，因為它的求解只包含一步移動操作。應用一系列相

38、似的推理，應用一系列相似的推理，子問題子問題1 1和和子問題子問題3 3也也可進一步被歸約為可進一步被歸約為本原問題本原問題。下面給出梵塔問題的。下面給出梵塔問題的歸約過程圖歸約過程圖（也稱做（也稱做與或圖與或圖）。思考：思考：1 1圓盤問題要走幾步？圓盤問題要走幾步？2 2圓盤問題要走幾步？圓盤問題要走幾步？3 3個，個，4 4個，個， ,64 ,64個呢？個呢？CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU解題過程（解題過程（3 3個圓盤問題）個圓盤問題）按照前面的歸約過程圖

39、可以給出詳細的解題過程圖。按照前面的歸約過程圖可以給出詳細的解題過程圖。123123123123123123123123CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU問題歸約法的實質：問題歸約法的實質：從目標從目標（要解決的問題要解決的問題）出發(fā)逆向推理，原問題分解為若干出發(fā)逆向推理，原問題分解為若干個子問題以及子子問題，直至最后把初始問題歸約（簡化）為個子問題以及子子問題，直至最后把初始問題歸約（簡化）為一個平凡的本原問題集合。一個平凡的本原問題集合。問題歸約表示法可由下面三部

40、分組成：問題歸約表示法可由下面三部分組成： 一個初始問題描述一個初始問題描述（可用表列、數(shù)組、樹、字符串等形式）（可用表列、數(shù)組、樹、字符串等形式） 一套把問題變換為子問題的操作符一套把問題變換為子問題的操作符（通過一系列操作將原問題（通過一系列操作將原問題變換為等價問題）變換為等價問題） 一套本原問題描述一套本原問題描述（本原子問題的解答可直接由一步得到）（本原子問題的解答可直接由一步得到）CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU問題歸約方法可以應用狀態(tài)、算符和目標這些問

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

42、或能直接得到解答。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.2.2 與或圖表示1.與或圖的概念與或圖的概念一般，我們用一個類似圖的結構來表示把問題歸約為后繼一般，我們用一個類似圖的結構來表示把問題歸約為后繼問題的替換集合，這種結構圖叫做問題的替換集合，這種結構圖叫做問題歸約圖問題歸約圖，或叫，或叫與或圖與或圖。如下圖所示：如下圖所示： ABCD與圖ABC或圖CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU

43、CSUCSUCSUCSUCSUCSUCSUCSUBCDEFGAHMBCDEFGANCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.一些關于一些關于與或圖的術語與或圖的術語介紹一些術語：介紹一些術語：父節(jié)點父節(jié)點、子子( (后繼后繼) )節(jié)點節(jié)點、弧線弧線、起始節(jié)點起始節(jié)點。終葉節(jié)點終葉節(jié)點：對應于本原問題的節(jié)點。：對應于本原問題的節(jié)點?；蚬?jié)點或節(jié)點：只要解決該問題就可解決其父輩問題的節(jié)點集合，如：只要解決該問題就可解決其父輩問題的節(jié)點集合，如( (M，N，H) )。與節(jié)點與節(jié)點

44、：只有解決所有子問題，才能解決其父輩問題的節(jié)點集：只有解決所有子問題，才能解決其父輩問題的節(jié)點集合，如合，如( (B，C)和和( (D，E，F(xiàn))各結點之間用一段小圓弧連接標記。各結點之間用一段小圓弧連接標記。HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點終葉節(jié)點CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU 與或圖中與或圖中可解節(jié)點可解節(jié)點的一般定義：的一般定義： (1) 終葉節(jié)點是可解節(jié)點終葉節(jié)點是可解節(jié)點（因為它們（因為它們與本原問題相關連與本原問題相關連）。）。 (2)

45、如果某個如果某個非終葉節(jié)點含有或后繼節(jié)點非終葉節(jié)點含有或后繼節(jié)點，那么只要當其后繼，那么只要當其后繼節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。節(jié)點至少有一個是可解的時，此非終葉節(jié)點才是可解的。 (3) 如果某個如果某個非終葉節(jié)點含有與后繼節(jié)點非終葉節(jié)點含有與后繼節(jié)點，那么只有當其后繼，那么只有當其后繼節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。節(jié)點全部為可解時，此非終葉節(jié)點才是可解的。 終葉節(jié)點用字母終葉節(jié)點用字母t表示表示（對應于本原問題），（對應于本原問題），有解節(jié)點用小圓有解節(jié)點用小圓點表示，不可解節(jié)點用小圓圈表示點表示，不可解節(jié)點用小圓圈表示。 相應地可給出相應地可給出不可解節(jié)點

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

47、UCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUt有解節(jié)點終葉節(jié)點與或圖例子與或圖例子無解節(jié)點tttttttt（a）（c）CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU 綜合前面所述，下面給出與或圖的構成規(guī)則：綜合前面所述，下面給出與或圖的構成規(guī)則： (1) 與或圖中的每個節(jié)點代表一個要解決的單一問題或問題與或圖中的每個節(jié)點代表一個要解決的單一問題或問題集合。圖中所含集合。圖中所含起始節(jié)點對應于原始問題起始節(jié)點對應于原始問題。 (2)

48、對應于本原問題的節(jié)點，叫做終葉節(jié)點，它沒有后裔對應于本原問題的節(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é)點。由于只有當于只有當該集

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

50、且只有一個父輩節(jié)點。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.3 謂詞邏輯法謂詞演算能夠表達命題邏輯所不能表達的復雜問題。更具謂詞演算能夠表達命題邏輯所不能表達的復雜問題。更具體地說，一階謂詞邏輯法具有：體地說，一階謂詞邏輯法具有：自然性自然性、精確性精確性、有限性有限性和和易易實現(xiàn)實現(xiàn)的特點，適宜于精確知識表示和相應的邏輯推理。的特點，適宜于精確知識表示和相應的邏輯推理。2.3.1 謂詞演算1.語法和語義語法和語義(Syntax & Semantics)基本符號基本符號

51、：謂詞符號、變量符號、函數(shù)符號、常量符號、：謂詞符號、變量符號、函數(shù)符號、常量符號、括號和逗號。括號和逗號。 常量符號常量符號：用來表示論域內的物體或實體，可以是具體的，：用來表示論域內的物體或實體，可以是具體的，也可以是抽象的。也可以是抽象的。變量符號變量符號：表示不明確涉及哪一個個體。：表示不明確涉及哪一個個體。函數(shù)符號函數(shù)符號：表示某個體與其他個體之間的：表示某個體與其他個體之間的映射關系映射關系。 謂詞符號謂詞符號：用于刻畫個體的性質、狀態(tài)或個體間的：用于刻畫個體的性質、狀態(tài)或個體間的非映射非映射關系關系，謂詞的語義是由使用者根據(jù)需要人為地定義，當謂詞的，謂詞的語義是由使用者根據(jù)需要人

52、為地定義，當謂詞的變量用特定個體取代時，謂詞就具有一確定的邏輯真值變量用特定個體取代時，謂詞就具有一確定的邏輯真值T或或F。 CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU原子公式原子公式：由單個謂詞符號和項（個體常量、變量、函數(shù)）：由單個謂詞符號和項（個體常量、變量、函數(shù)）構成的公式。原子公式是謂詞演算基本積木塊。構成的公式。原子公式是謂詞演算基本積木塊。例如，要表示例如，要表示“機器人（機器人（ROBOT）在號房間（）在號房間（r1）內）內”，如下圖所示，可以應用原子公式：如

53、下圖所示，可以應用原子公式： 當機器人（當機器人（ROBOT）移到房間移到房間r2時，原子公式可以表示為：時，原子公式可以表示為：INROOM (ROBOT，r2) 這兩個原子公式的通用形式就是：這兩個原子公式的通用形式就是： CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2.連詞和量詞連詞和量詞(Connective & Quantifiers)(1) 連詞連詞與與合取合取（conjunction）：合取就是用連詞）：合取就是用連詞把幾個謂詞公把幾個謂詞公式連接起來而構成的公式

54、，式連接起來而構成的公式，合取項是合取式的每個組成部分合取項是合取式的每個組成部分。 例：例：LIKE( I，MUSIC )LIKE( I，PAINTING ) 或或析取析取（disjunction）：析取就是用連詞）：析取就是用連詞把幾個謂詞公式把幾個謂詞公式連接起來而構成的公式，連接起來而構成的公式，析取項是析取式的每個組成部分析取項是析取式的每個組成部分。 例：例：PLAYS( LIULI，BASKETBALL )PLAYS( LIULI，F(xiàn)OOTBALL )又如又如，“李的母親和他的父李的母親和他的父親結婚親結婚”這句話的原子公式為：這句話的原子公式為：這里使用了兩個函數(shù)關系。這里使用

55、了兩個函數(shù)關系。CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU蘊涵蘊涵（Implication）：蘊涵）：蘊涵“”表示表示“如果如果-那么那么”的語句。的語句。用連詞用連詞連接兩個公式所構成的公式叫做蘊涵。連接兩個公式所構成的公式叫做蘊涵。IFA THEN B 前項前項（左部左部） 后項后項（右部右部） 例：例：RUNS( LIUHUA，F(xiàn)ASTEST ) WINS( LIUHUA，CHAMPION ) 非（非（NOT）：表示否定，、：表示否定，、均可表示。均可表示。 例：例：I

56、NROOM( ROBOT，r2 )（機器人不在（機器人不在2號房間內。）號房間內。） (2) 量量詞詞全稱量詞全稱量詞(Universal Quantifier)：若一個原子公式：若一個原子公式P(x)，對，對于所有可能變量于所有可能變量x都具有都具有T值，則用值，則用( x)P(x)表示。表示。 例：例：( x)ROBOT(x) COLOR(x，GRAY) ( x)Student(x) Uniform(x，Color) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU存在量詞存在

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

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

59、式公式。原子謂詞公式是合式公式。(2) 若若A為合式公式，則為合式公式，則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為正的或者為負的。為正的或者為負的。設設I(x)表示表示“

60、x是整數(shù)是整數(shù)”，P(x)表示表示“x是正數(shù)是正數(shù)”，N(x)表示表示“x是是負數(shù)負數(shù)”( x) I(x) (P(x)N(x) CSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSUCSU2. 合式公式的性質合式公式的性質如果如果P和和Q是兩個合式公式，則由這兩個合式公式所組成的是兩個合式公式，則由這兩個合式公式所組成的復合表達式可由下列真值表給出：復合表達式可由下列真值表給出： 等價等價（）：如果兩個合式公式，無論如何解釋，其真值表：如果兩個合式公式，無論如何解釋，其真值表都是相同的，那么我