人工智能教程習題及答案

人工智能教程

習題及答案

第一章緒論

1.1練習題

1.1什么是人類智能？它有哪些特征或特點？

1.2人工智能是何時、何地、怎樣誕生的？

1.3什么是人工智能？它的研究目標是什么？

1.4人工智能有哪些主要研究領域？

1.5人工智能有哪幾個主要學派？各自的特點是什么？

1.6什么是以符號處理為核心的方法？

1.7什么是以網(wǎng)絡連接為主的連接機制方法？

1.2習題參考斛答

(略)

第二章知識表示習題參考解答

2.3練習題

2.1什么是知識?它有哪些特性?有哪幾種分類方法？

2.2何謂知識表示？陳述性知識表示法與過程性知識表示法的區(qū)別是什么？

2.3在選擇知識的表示方法時，應該考慮哪些主要因素？

2.4一階謂詞邏輯表示法適合于表示哪種類型的知識?它有哪些特點？

2.5請寫出用一階謂詞邏輯表示法表示知識的步驟“

2.6設有下列語句，請用相應的謂詞公式把它們表示出來：

(1)有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。

(2)他每天下午都去玩足球。

(3)太原市的夏天既干燥又炎熱。

(4)所有人都有飯吃。

(5)喜歡玩籃球的人必喜歡玩排球。

(6)要想出國留學，必須通過外語考試。

2.7房內(nèi)有一只猴子、一個箱子，天花板上掛了一串香蕉，其位置關系如圖2.11所

示，猴子為了拿到香蕉，它必須把箱子推到香蕉下面，然后再爬到箱子上。請定義必要的謂

詞，寫出問題的初始狀態(tài)(即圖2.16所示的狀態(tài))、目標狀態(tài)(猴子拿到了香蕉，站在箱子

上，箱子位于位置b)。

圖2.11猴子摘香蕉問題

2.8對習題2.7中的猴子摘香蕉問題，利用一階謂詞邏輯表述一個行動規(guī)劃，使問題

從初始狀態(tài)變化到目標狀態(tài)。

2.9產(chǎn)生式的基本形式是什么？它與謂詞邏輯中的蘊含式有什么共同處及不同處？

2.10何謂產(chǎn)生式系統(tǒng)？它由哪幾部分組成？

2.11產(chǎn)生式系統(tǒng)中，推理機的推理方式有哪幾種？在產(chǎn)生式推理過程中，如果發(fā)生

策略沖突，如何解決？

2.12設有下列八數(shù)碼難題：

在一個3x3的方框內(nèi)放有8個編號的小方塊，緊鄰空位的小方塊可以移入到空位上，

通過平移小方塊可將某一布局變換為另一布局(如圖2.12所示)。請用產(chǎn)生式規(guī)則表示移動

小方塊的操作。

6

圖2.12習題2.12的圖圖2,13習題2.13的圖

2.13推銷員旅行問題：

設有五個相互可直達且距離已知的城市A、B、C、D、E,如圖2.13所示，推銷員從城

市A出發(fā)，去其它四城市各旅行一次，最后再回到城市A,請找出一條最短的旅行路線。用

產(chǎn)生式規(guī)則表示旅行過程，

2.14何謂語義網(wǎng)絡？語義網(wǎng)絡表示法的特點是什么？

2.15語義網(wǎng)絡表示法與產(chǎn)生式表示法、謂詞邏輯表示法之間的關系如何？

2.16用語義網(wǎng)絡表示下列知識：

(1)所有的鴿子都是鳥；

(2)所有的鴿子都有翅膀；

(3)信鴿是一種鴿子，它有翅膀，能識途。

2.17請對下列命題分別寫出它的語義網(wǎng)絡：

(1)每個學生都有多本書。

(2)孫老師從2月至7月給計算機應用專業(yè)講《網(wǎng)絡技術》課程。

(3)雪地上留下一串串腳印，有的大，有的小，有的深，有的淺。

(4)王麗萍是天發(fā)電腦公司的經(jīng)理，她35歲，住在南內(nèi)環(huán)街68號。

2.18請把下列命題用一個語義網(wǎng)絡表示出來：

(1)豬和羊都是動物；

(2)豬和羊都是偶蹄動物和哺乳動物；

(3)野豬是豬，但生長在森林中；

(4)山羊是羊，且頭上長著角；

(5)綿羊是一種羊，它能生產(chǎn)羊毛。

(3)根據(jù)所要表達的知識的語義，用適當?shù)穆?lián)接符號將各個謂詞聯(lián)接起來，形成謂詞

公式。

2.6解：

(1)有的人喜歡梅花，有的人喜歡菊花，有的人既喜歡梅花又喜歡菊花。

定義謂詞及個體。設LIKE(x,y)表示x喜歡y,Meihua表示梅花，Juhua表示菊花，則:

(3x)LIKE(x.Meihua)A(3y)LIKE(y,Jiilnia)A(3Z)(LIKE(Z,Mcihua)ALIKE(z.Juhua>

(2)李明每天下午都去玩足球。

定義謂詞及個體。設PLAYFB(x,y)表示x在y下午玩足球，Liming表示李明，貝IJ：

(Vy)(PLAYFB(Liming,y)

(3)太原市的夏天既干燥又炎熱。

定義謂詞及個體。設STATE(xyz)表示x市在y季干氣候處于z狀態(tài)。這是一個三元一

階謂詞，所涉及的個體有：太原，夏天，干燥，炎熱。將個體代入謂詞：

STATE(太原，夏天干燥)，STATE(太原，夏天炎熱)，

根據(jù)題意將各謂詞用適當?shù)倪B接符連接起來。

STATE(太原，夏天干燥)ASTATE(太原，夏天淡熱］

(4)所有人都有飯吃。

定義謂詞及個體。設Havefood(x)表示x有飯吃，則根據(jù)題意有：

(Vx)(Havcfood(x))

(5)喜歡玩籃球的人必喜歡玩排球。

定義謂詞及個體。設Likeplay(x,y)表示x喜歡玩yo所涉及的個體有：籃球，排球。將

個體代入謂詞，并根據(jù)題意將各謂詞用適當?shù)倪B接符連接起來。

0x)(Likeplay(x,籃球)—>Likeplay(x,排球))

(6)要想出國留學，必須通過外語考試。

定義謂詞及個體。設Want(x,y)表示x想y,Pass(x,y)表示x通過y。定義個體：goabrod

表示出國學習，language表示外語。將個體代入謂詞，并根據(jù)題意將各謂詞用適當?shù)倪B接

符連接起來。

(Vx)(~Pass(x,flanguage)—>?want(x,goabrod))

2.7解：根據(jù)謂詞知識表示的步驟求解問題如下：

解法一：

本問題涉及的常量定義為：

猴子：Monkey,箱子：Box,香蕉:Banana,位置：a,b,c

定義謂詞如下

SITE(x,y):表示x在y處；

HANG(x.y):表示x懸掛在y處；

ON(x,y):表示x站在y上；

HOLDS(y,w):表示y手里拿著wo

根據(jù)問題的描述將問題的初始狀態(tài)和目標狀態(tài)分別用謂詞公式表示如下：

問題的初始狀態(tài)表示：

SITE(Monkey,a)AHANG(Banana,b)ASITE(Box,c)A-ON(Monkey.Box)A?

HOLDS(Monkey,Banana)

問題的目標狀態(tài)表示：

SITE(Monkey,b)A~HANG(Banana,b)ASITE(Box,b)AON(Monkey,Box)A

HOLDS(Monkey,Banana)

解法二：

本問題涉及的常量定義為：

猴子：Monkey,箱子：Box,香蕉:Banana,位置：a,b,c

定義謂詞如下

SITE(x,y):表示x在y處；

ONBOX(x):表示x站在箱子頂上；

HOLDS(x):表示x摘到了香蕉。

根據(jù)問題的描述將問題的初始狀態(tài)和目標狀態(tài)分別用謂詞公式表示如下：

問題的初始狀態(tài)表示：

SITE(Monkey,a)ASITE(Box,c)A-ONBOX(Monkey)A-HOLDS(Monkey)

問題的目標狀態(tài)表示

SITE(Box,b)ASITE(Monkey,b)AONBOX(Monkey)AHOLDS(Monkey)

從上述兩種解法可以看出，只要謂詞定義不同，問題的初始狀態(tài)和目標狀態(tài)就不同，

所以，對于同樣的知識，不同的人表示的結(jié)果可能不同。

2.8解：本問題的關鍵就是制定一組操作，將初始狀態(tài)轉(zhuǎn)換為目標狀態(tài)。為了用謂詞公

式表示操作，可將操作分為條件(為完成相應操作所必須具備的條件)和動作兩部分。條件

易于用謂詞公式表示,而動作則可通過執(zhí)行它前后的狀態(tài)變化表示出來，即由于動作的執(zhí)行,

當前狀態(tài)中刪去了某些謂詞公式而又增加一些謂詞公式從而得到了新的狀態(tài)，通過這種狀態(tài)

中謂詞公式的增減來描述動作。

定義四個操作謂詞如下，操作的條件和動作可用謂詞公式的增刪表示：

1.goto(x,y)：從x處走到y(tǒng)處。

條件：SITE(Monkey,x)

動作：刪除SITE(Monkey,x);增加SITE(Monkey,y)

2.pushbox(x.y)：將箱子從x處推到y(tǒng)處。

條件：SITE(Monkey,x)ASITE(Box,x)A-ONBOX(Monkey)

動作：刪除SITE(Monkey,x),SITE(Box,x);增加SITE(Monkey,y),SITE(Box,y)

3.climbbox：爬到箱子頂上。

條件：?ONBOX(Monkey)

動作：刪除~ONBOX(Monkey)；增加ONBOX(Monkey)

4.grasp:摘下香蕉。

條件：?HOLDS(Monkey)/\ONBOX(Monkey)ASITE(Monkey,b)

動作：刪除~HOLDS(Monkey)；增加HOLDS(Monkey)

在執(zhí)行某一操作前，先檢查當前狀態(tài)是否滿足其前提條件，若滿足，則執(zhí)行該操作，否

則，檢查另一操作的條件是否被滿足。檢查的方法就是當前的狀態(tài)中是否蘊含了操作所要求

的條件。在定義了操作謂詞后，就可以給出從初始狀態(tài)到目標狀態(tài)的求解過程。在求斛過程

中，當進行條件檢查時，要進行適當?shù)淖兞看鷵Q。

SITE(Monkey,a)

SITE(Boxx)

~ONBOX(Monkey)

~HOLDS(Monkey)

Ugoto(x,y),用a代x,用c代y

SITE(Monkey,c)

SITE(B<)x,c)

~ONBOX(Monkey)

?HOLDS(Monkcy)

Upushbox(x,y),用c代x,用b代y

SITE(Monkey,b)

SITE(Box,b)

~ONBOX(Monkey)

?HOLDS(Monkey)

Uclimbox

SITE(Monkey.b)

SITE(Box,b)

ONBOX(Monkey)

?HOLDS(Monkcy)

Ugrasp

SITE(Monkey,h)

SITE(Box,b)

ONBOX(Monkey)

HOLDS(Monkey)

2.9答：(略)

2.10答：(略)

2.11答：(略)

2.12解：首先，建立棋盤變換的產(chǎn)生式規(guī)則。如果把棋盤的每一種布局看作是一個狀

態(tài)矩陣，本題就變成了從初始狀態(tài)矩陣到目標狀態(tài)矩陣的一種變化。

所謂棋盤狀態(tài)的變化就是希望棋盤上空格周圍的棋子能走進空格，這也可以理解為移動空

格，只要實現(xiàn)空格的上、下、左、右四種移動即可?？赏ㄟ^建立四個條件-操作型的產(chǎn)生式

規(guī)則，來實現(xiàn)這四種移動，

設S”為狀態(tài)矩陣中的第i行和第j列的數(shù)碼，io,jo表示空格所在的行和列，如果在狀態(tài)

矩陣中用。來表示空格的話，則建立如下四條產(chǎn)生式規(guī)則：

R1:if(jo-1^1)thenoeginS眾o：=Siouo-i);Si(xjo-i):=Oend空格左移

R2:if(io-1^1)thenoeginS眾o：=Sw-”o；Soo-?jo：=0end空格上移

R3:if(jo+lW3)thenbeginS@o：=S,<w+i);Sio(jo^i):=0end空格右移

R4：if(io+lW3)thenbeginS@o：=S(Q.I￡Soo.i加:二0end空格下移

然后，建立綜合數(shù)據(jù)庫。將棋盤的布局表示為狀態(tài)矩陣的形式存入綜合數(shù)據(jù)庫，例如,

可以將本題的初始布局和目標布局以矩陣形式表示為：

983193

So=160Sg=804

754765

綜合數(shù)據(jù)庫中，存放初始和目標狀態(tài)矩陣以及變換過程中的中間矩陣。

在建立了規(guī)則集和綜合數(shù)據(jù)庫后，就可以按照產(chǎn)生式規(guī)則進行狀態(tài)變換，實現(xiàn)推理求解。

在進行推理時，可能會有多條產(chǎn)生式規(guī)則的條件部分和綜合數(shù)據(jù)庫中的已有事實相符，這樣

就有可能激活多條規(guī)則，究竟采用哪一條規(guī)則作為啟用規(guī)則，這就是沖突解決策略問題。解

決沖突的策略有專一性排序、規(guī)則順序等多種，也可以使用一些啟發(fā)性的信息，根據(jù)具體問

題選擇。在本題中，我們采用一個啟發(fā)式函數(shù)h(x),它表示節(jié)點x所對應的棋盤中與目標節(jié)

點對應的棋盤中棋子位置不同的個數(shù)。這里，綜合數(shù)據(jù)庫中的初始狀態(tài)矩陣，能滿足規(guī)則

RI.R2,R4的條件，所以有三條匹配規(guī)則。利用啟發(fā)式函數(shù)決定哪一條規(guī)則為啟用規(guī)則。

因為規(guī)則R4的啟發(fā)式函數(shù)值h(x)=5,規(guī)則R1的h(x)=6,規(guī)則R2的h(x)=7,也就是說，

規(guī)則R4所得到的新狀態(tài)與目標狀態(tài)差距最小，所以啟用規(guī)則R4,依此類推，可以得到到達

目標狀態(tài)的規(guī)則執(zhí)行序列：

R4,RI,R2,R2,RI,R4,R3

其執(zhí)行過程如圖2.14所示

圖2.14習題2.12執(zhí)行過程

2.13解：設綜合數(shù)據(jù)庫中包含了已訪問過的城市名的列表、未訪問過的城市名列表和

各城市間的距離表。初始時刻，已訪問過的城市名列表口只有A,未訪問過的城市名列表中

有B.C.D.Eo定義如下謂詞：

not-visit(x)：表示未訪問過城市x;

visit-all():表示已沒有未訪問過的城市；

goto(x):表示去訪問城市x,并將x加入已訪問的城市列表中，從未訪問過的城市列表

中刪除。

則建立如下的產(chǎn)牛式規(guī)則：

RI:not-visit(x)—?goto(x)

R2:visit-allO-*goto(A)

當未訪問過的城市列表不為空時，激活規(guī)則R1；否則，激活規(guī)則R2。

如果未訪問過的城市列表中城市個數(shù)多于一個時，這時規(guī)則R1的實例就不止一個。比

如，在剛開始時，就有四條規(guī)則(分別針對x二A,x=B,x=C,x=D)被激活，這時可以根據(jù)綜

合數(shù)據(jù)庫中的城市間距離，構(gòu)造一個啟發(fā)式函數(shù)h(x)來解決規(guī)則沖突，決定某一條規(guī)見為啟

用規(guī)則。例如在剛開始從A出發(fā)時，決定下一訪問城市時，由于B與A的距離最近，所以

依此類推，推銷員走的路徑為、、這時未訪問過的城市列表中已經(jīng)為空，規(guī)則

x：=BoEDCo

R2被激活，返回城市A。

2.14答：(略)

2.15答：(略)

2.16解：(1)本知識涉及的對象有3個：鳥、鴿子、信鴿。信鴿是一種鴿子，除了它

們本身的屬性外，具有鴿子的一般特性。而鴿子又是一種鳥，鳥所具有的屬性它也具有。

(2)信鴿與鴿子之間是一種類屬關系，鴿子和鳥之間也是一種類屬關系，它們都可以

用AKO表示。

(3)整理各對象節(jié)點之間的屬性，使上層節(jié)點所具有的屬性不再在下層節(jié)點中標出。

(4)將各對象作為一個節(jié)點，而它們之間的關系作為弧，則得到圖2.15所示的語義

網(wǎng)絡。

|/有羽毛

能識途一|俏鵠產(chǎn)工子件斗一彳飛一會飛翔

,I能吃食

受過訓練飛翔帶哨聲會吃叫

圖2.15有關鴿子的語義網(wǎng)絡

2.17解：(1)這是一個帶有全稱量詞的語義網(wǎng)絡，如圖2.16所示。其中，s是全稱變

量，代表任一個學生；h是存在變量，表示某次擁有；bs也是存在量詞，代表多本書；s,h,

bs及其語義聯(lián)系構(gòu)成一個子網(wǎng)，是一個子空間，表示每個學生都擁有多本書；節(jié)點g代表

該子空間，由弧F指向具所代表的子空間的具體形式，弧v指出s是一個全稱變量。節(jié)點

GS代表整個空間。

學生擁有多本書

g

圖2.16"每個學生都有多本書”的語義網(wǎng)絡

(2)根據(jù)題意得到如圖2.17所示的語義網(wǎng)絡，這里要指出的是，設立“講課”很有必

要，由它向外引出的弧不僅可以指出講課的主體，而且可以指出講課的起止時間。

網(wǎng)絡技術,

客體2

主體序磯?■叁計算機應用

麗?是_生「孫老師11

時間

結(jié)束于一T而1~-

圖2.17有關講課的語義網(wǎng)絡

(3)根據(jù)題意，這是一個有合取和析取的語義網(wǎng)絡，如圖2.18所示。

圖2.18有關雪地上腳印的語義網(wǎng)絡

(4)此題較簡單，根據(jù)題意，其語義網(wǎng)絡如圖2.19所示

肉內(nèi)環(huán)街68號卜■竺丁萩電腦公司卜衛(wèi)主函薄J

是

圖2.19有關電腦公司的語義網(wǎng)絡

2.18解：按照語義網(wǎng)絡知識表示步驟來首先進行解題分析：

(1)問題涉及的對象有動物、偶蹄動物、哺乳動物、豬、羊、野豬、山羊、綿羊共8

個對象。各對象的屬性可以根據(jù)常識給出，不過，這里特別給出了山羊有角，綿羊能產(chǎn)羊毛

的特點。

(2)羊和豬與偶蹄動物、哺乳動物間是類屬關系，偶蹄動物、哺乳動物與動物間也是

類屬關系，野豬與豬，山羊、綿羊與羊之間都是類屬關系，可用AKO表示。

(3)根據(jù)信息繼承性原則，各上層節(jié)點的屬性下層都具有，在下層都不再標出，以避

免屬性信息重復。

(4)根據(jù)上面的分析，本題共涉及8個對象，各時象的屬性以及它們之間的關系已在

上面指出，所以本題的語義網(wǎng)絡應是由8個節(jié)點構(gòu)成的有向圖，弧上的標注以及各節(jié)點的標

注已在上面指出。語義網(wǎng)絡圖如圖2.20所示。

圖2.20有關豬和羊的語義網(wǎng)絡

2.19答：框架是一種描述所論對象屬性的數(shù)據(jù)結(jié)構(gòu)。所論的對象可以是一個事物、一

個事件或者一個概念。一個框架由若干個“槽”組成，每個“槽”又可劃分為若干個“側(cè)面

一個槽用于描述所論及對象的某一方面的屬性，一個側(cè)面用于描述相應屬性的一個方面。槽

和側(cè)面所具有的屬性值分別稱為槽值和側(cè)面值。槽值可以是邏輯型或數(shù)字型的，具體的值可

以是程序、條件、默認值或是一個子框架。框架一般可表示成如下形式：

框架名

〈槽名1>

〈側(cè)面11>

m>-<?nki>

<側(cè)面lni>

〈值lnil>-<filnikm>

〈槽名2>

〈側(cè)面12>

〈值121>…〈值12L>

〈側(cè)面ln?>

（值lrhlA-v值In21n2>

2.20答：（略）

2.21解：由于學生框架類似于一個變量，并未指定某個具體的學生，所以，其定義應

該如下，若要描述某個具體的學生，則只要將他的相應屬性填入到這個框架的各個槽中即可。

框架名：〈學生〉

姓名：單位（姓和名）

年齡：單位（歲）

性別：范圍（男，女）

缺?。校?/p>

健康狀況：范圍（健康，一般，差）

缺?。ㄒ话悖?/p>

所在系別：單位（系）

專業(yè)：范圍（系中所包含的專業(yè)）

入學時間：單位（年，月）

畢業(yè)時間：單位（年，月）

成績：范圍（優(yōu)，良，中，差）

缺省(良)

是否學生干部：范圍(是，否)

缺省(否)

2.22答：(略)

2.23答：(略)

2.24答：由表示一個問題的全部狀態(tài)及一切可用算符構(gòu)成的集合稱為該問題的狀態(tài)空

間。它一般由三部分構(gòu)成：問題的所有可能初始狀態(tài)構(gòu)成的集合S；算符集合F；目標狀態(tài)

集合G。即可用一個三元組(S.F.G)表示問題的狀態(tài)空間。

2.25答：(略)

2.26解：用狀態(tài)空叵法進行表示。根據(jù)狀態(tài)空間表示問題的步驟，問題求解如下：

第一步，定義問題狀態(tài)的描述形式。

設SK二(M,Ny,C)表示修道士和野人在河的左岸的狀態(tài)，其中，N,表示修道士在左岸的實

際人數(shù)，M表示也人在左岸的實際人數(shù)，C用來指示船是否在左岸(C=l表示在左岸，C

二0表示不在左岸)O

第二步，用所定義的狀態(tài)描述形式把問題的所有可能狀態(tài)都表示出來，并確定出問題的

初始狀態(tài)集和目標狀態(tài)集,

對于狀態(tài)SK=(Nx,Ny,C)來說，由于M,Ny的取值有0,1,2,3四種可能，C的取值有0

和1兩種可能，所以本問題所有可能的狀態(tài)共有4x4x2=32種。各狀態(tài)的形式描述如下：

S月3,31,S五(3,2.1),S2=(3.1,l),S3=(3,0,l),

S4=(3,3,0；,X320),S6=(3.1,0),S尸(300),

Sk(2,3工，?二(2,2,1),510=(2,1,1),S/(2,0,1),

512=(2,3,0,Si3=⑵2,0),SH=(2,1,0),SI5=(2,0,0),

SI6=(1.3,1),Si7=(L2,l),S19=(l,0,l)1

520=(1,3,C),S2I=(1,2,0),S22=(l,l,0),S23=(l,0,0),

324=(0,3,1),325=(0,2,1),S26=(0,l,l),S27=(0,0,l),

528=(0,3,0),S29=(Q,2,Q),S行(0,1,0),S3尸(000).

在這些狀態(tài)中，由于有安全約束條件——任何岸邊野人的數(shù)量都不得超過傳教士的數(shù)量

(即NxNNy),所以只有20個狀態(tài)是合法的，像(1,2,1)(1.3,1)和(2,3,1)等都是不合法的

狀態(tài)。而由于這些不合法狀杰的存在，又會導致某些合法狀態(tài)是不可到達的。這樣，這個問

題總共只有16種可到達的合法狀態(tài)，以下劃線表示。

問題的初始狀態(tài)集為：S={So}={(313.1)},目標狀態(tài)集為：G=偈產(chǎn){(0,0,0)}

第三步，定義一組用于狀態(tài)變換算符F。

定義算符L(i,j)表示劃船將i個傳教士和j個野人送到右岸的操作；算符R(i,j)表示劃

船從右岸將i個傳教士和j個野人帶回左岸的操作。由于過河的船每次最多載兩個人，所以,

i+jW2,這樣定義的算符組F中只可能有如下10個算符：

F：L(l,0：i,L(2,0),L(l,l),L(0,l),L(0,2)

R(1.0),R(2,0),R(l,l),R(0,l),R(0,2)

至此，該問題的狀態(tài)空間(S,F,G)構(gòu)造完成。這就完成了對問題的狀態(tài)空間表示。

為了求解該問題，根據(jù)該狀態(tài)空間的16種可到達合法狀態(tài)和10種算符，構(gòu)造它的狀

態(tài)轉(zhuǎn)換圖，如圖2.21所示。

圖2.21傳教士和野人問題的狀態(tài)轉(zhuǎn)換圖

在圖2.21所示的狀態(tài)空間圖中，每個節(jié)點只能取L、R操作之一，這取決于變量C的取

值，即船是在左岸還是在右岸，若船在左岸(即C=l),則只能取L操作，若船在右岸，則

只能取R操作°從初始節(jié)點(331)(狀態(tài)So)到目標節(jié)點(0,0,0)(狀態(tài)SG的任何一條

通路都是問題的一個解。具中：

L(l,l),R(l,0),L(0,2),R(0,l),L(2,0),R(l,l),L(2,0),RiO,l),L(0,2),R(0,l),L(0,2)是算符

最少的解之一。

2.27解：用狀態(tài)空間法進行表示。根據(jù)狀態(tài)空間表示問題的步驟，問題求解如下：

第一步，定義問題狀態(tài)的描述形式。

以四元組SK=(I,h,j,m)作為狀態(tài)變量，表示農(nóng)夫、狐貍、雞和小米是否在左岸，每

個元素共有兩個取值1或0,1表示在左岸，。表示不在左岸。

第二步，用所定義的狀態(tài)變量把問題的所有可能狀態(tài)都表示出來，并確定出問題的初

始狀態(tài)集和目標狀態(tài)集。

由于狀態(tài)變量有4個元素，每個元素有2種取值，所以共有16種可能狀態(tài)。各狀態(tài)的

形式描述如下：

So=(ltl,l.l),S1=(1,1,1,0),s2=(l,1,0,1).s3=(l,1,0,0)

S4=(l,0,1,1),Ss=(l,0,1,0),s6=(l,0,0,1),S/=(l,0,0,0)

S8=(0,1,1,1),S9=(o,1,1,0),S!0=(0,1,0,1),Sn=(0,l,0,0)

S12=(0,0,1,1),S13=(O.O,1,O),S14=(0,0,0,1),S15=(0,0,0,0)

問題的初始狀態(tài)集為：S={SO}={(1,1,1,1)},目標狀態(tài)集為：G={Si5}={(0,0,0,0))

第三步，定義一組用于狀態(tài)變換的算符F。

由于船上除了農(nóng)夫外，每次只能載狐貍、雞和小米中的一樣，且每次農(nóng)夫都必須在船

上，故定義算符如下：

L(fj)表示從左岸將第j樣東西送到右岸。二1表示狐貍，戶2表示雞門二3表示小米j=0

表示除農(nóng)夫外不載任何東西)，f表示農(nóng)夫始終在船上。

R(f.j)表示從右岸將第j樣東西帶回左岸。

所以，所定義的算符組F中可能有8種算符：

F：L(f,0),L(f,l),L(f,2),L(f,3),R(f,0),R(f,l),R(f,2),R(f,3)

這里要指出的是，操作算符中的f可以不要，也就是說，完全可以把操作算符定義成

L(j)和Rfflo這里加上f是為了表示農(nóng)夫總是在船上劃船。

至此，該問題的狀態(tài)空間(S.F,G)構(gòu)造完成。這就完成了對問題的狀態(tài)空間表示，

為了求解該問題，根據(jù)該狀態(tài)空間的16種狀態(tài)和8種算符，構(gòu)造它的狀態(tài)轉(zhuǎn)換圖，如

圖2.22所示。

圖2.22農(nóng)夫、狐貍、雞和小米過河問題狀態(tài)轉(zhuǎn)換圖

在圖2.22所示的狀態(tài)轉(zhuǎn)換圖中，每個節(jié)點只能取L、R操作之一，這取決于狀態(tài)變量中

第一個元素I的取值。若1=1,表明農(nóng)夫在左岸，船也就在左岸(因為農(nóng)夫始終和船相隨)，

這時只能取L操作。若1=0,表明船在右岸，則只能取R操作。從初始節(jié)點(LLL1)(狀態(tài)

So)到目標節(jié)點(0,0.0。)(狀態(tài)5遙)的任何一條通路都是問題的一個解。其中：

L(f,2),R(f,O),L(f,3),R(f,2),L(f,l),R(f,O),L(f,3)

是算符最少的解之一，如圖2.23所示。

2.28解：根據(jù)狀態(tài)空間表示問題的步驟，問題求解如下：

(1)定義狀態(tài)變量

設SK二(w,X,y,z)為狀態(tài)變量。W表示猴子在地面上的位置，x表示猴子是否在箱子

頂上(x=l表示在箱子頂上，x=0表示不在箱子頂上)，y表示箱子在地面上的位置，z表示

表示猴子是否摘到香蕉(z=1表示摘到香蕉，z=0表示沒有摘到香蕉)，猴子和箱子在地面

的位置可能是a,b,Co

(2)列出所有狀態(tài)，確定出初始狀態(tài)及和目標狀態(tài)集。

由于w,y的取值可能是a,b,c,而x,z的取值可能是0或1,所以，這個問題共有3、2

*3x2=36個狀態(tài)。如(a,C,cQ),(a,0,b,0),(a,0c0),???,(b.0b0),(b,Lb@(b,Lb,l)這里就不一一列

出了，狀態(tài)空間圖這里也不畫出了。

根據(jù)題意，在這36種狀態(tài)中，初始狀態(tài)S「gQ,c,0),目標狀態(tài)Su-(b,l,b,1)

(3)定義一組用于狀態(tài)變換的算符F,實現(xiàn)狀態(tài)間的轉(zhuǎn)換。

定義操作算符組如下：

F：①goto(x,y)：猴子從x處走到y(tǒng)處。

②pushbox(x,y)：猴子將箱子從x處推到y(tǒng)處，

③climbbox:猴子爬到箱子頂上。

④grasp:猴子摘下香蕉。

至此，該問題的狀態(tài)空間(So.F,S9)構(gòu)造完成。

可以從一個含有36個狀態(tài)狀態(tài)空間圖(其中有很多狀態(tài)是不必要的)中找到一條從初

始狀態(tài)到目標狀態(tài)的最短路徑，其所對應的操作符序列如下，它就是該問題的解。

goto(a,c),pushbox(c.b),climbox,grasp

第三章確定性推理方法習題參考斛答

3.1練習題

3.1什么是命題？請寫出3個真值為T及真值為F的命題。

3.2什么是謂詞？什么是謂詞個體及個體域？函數(shù)與謂詞的區(qū)別是什么？

3.3謂詞邏輯和命題邏輯的關系如何？有何異同？

3.4什么是謂詞的項？什么是謂詞的階？請寫出謂詞的一般形式。

3.5什么是謂詞公式？什么是謂詞公式的解釋？設D={L2},試給出謂詞公式

(3x)(Vy)(P(x,y)-Q(x,y))

的所有解釋，并且對每一種解釋指出該謂詞公式的真值。

3.6對下列謂詞公式分別指出哪些是約束變元？哪些是自由變元？并指出各量詞的轄域。

(1)(Vx)(P(x,y)v(3y)(Q(x,y)AR(x,y?)

(2)(3z)(Vy)(P(z,y)vQ(z,x))vR(u,v)

(3)(Vx)(~P(x,f(x))v(3z)(Q(x,z)A~R(x,z)))

(Vz)((3y)(0t)(P(z,t)vQ(y,t))AR(z,y))

(5)(Vz)(3y)(P(z,y)v(3z)((Vy)(P(z,y)AQ(z,y)v(3z)Q(z,y))))

3.7什么是謂詞公式的永真性、永假性、可滿足性、等價性及永真蘊含？

3.8什么是置換？什么是合一？什么是最一般的合一？

3.9判斷以下公式對是否可合一；若可合一，則求出最一般的合一：

⑴P(a.b),P(x.y)

⑵P(f(z).b),P(y.x)

⑶P(f(x),y),p(y.f(a))

(4)P(f(y).y.x).P(x,f(a),f(b))

⑸P(x.y).P(y.x)

3.10什么是范式？請寫出前束型范式與SKOLEM范式的形式。

3.11什么是子句？什么是子句集？請寫出求謂詞公式子句集的步驟。

3.12謂詞公式與它的子句集等值嗎？在什么情況下它們才會等價？

3.13把下列謂詞公式分別化為相應的子句集：

(1)(Vz)(Vy)(P(z,y)AQ(z,y))

(2)(Vx)(Vy)(P(x,y)^Q(x,y))

⑶(Vx)(3y)(P(x,y)v(Q(x,y)R(x,y)))

(4)(Vx)(Vy)(3z)(P(x,y)->Q(x,y)vR(x,z))

(5)(3x)(3y)(Vz)(3u)(Vv)(3w)(P(x,y,z,u,v,w)A(Q(Xy,z,u,v,w)v~R(x,z,w)))

3.14判斷下列子句集中哪些是不可滿足的：

(1)S={~PvQ,~Q,P,~P}

(2)S={PvQ,~PvQ,Pv~Q,~Pv~Q}

(3)S={P(y)vQ(y)rP(f(x))vR(a)}

(4)S={?P(x)vQ(x),~P(y)vR(y),P(a),S(a),-S(z)v~R(z)}

(5)S={-P(x)v~Q(y>/~L(x,y),P(a),~R(z)vL(a,z),R(b),Q(b)}

(6)S={~P(x)vQ(f(x),a),~P(h(y))vQ(f(h(y))a)v~P(z)}

(7)S={P(x)vQ(x)vR(x),~P(y)vR(y),~Q(a),~R(b)}

(8)S={P(x)vQ(x),~Q(y)vR(y),~P(z)vQ(z),~R(u)}

3.15為什么要引入Herbrand理論？什么是H域？如何求子句集的H域？

3.16什么是原子集？如何求子句集的原子集？

3.17什么是H域解釋?如何用域D上的一個解釋I構(gòu)造H域上的解釋「呢？

3.18假設子句集S={P(z)VQ(z),R(f(t))},S中不出現(xiàn)個體常至符號。設個體域D={1,2}。由H域和

原子集的定義：

H={a,f(a),f(f(a)),-)

A={P(a),Q(a),R(a),P(fi：a)),Q(f(a)),R(f(a)),-)

如果設I是D上的解釋，并作如下的設定

I：<(1)f(2)P(l)P(2)Q(l)(^2)R(l)R(2)

22TFFTFT

請構(gòu)造H域上的一個解釋「與I相對應，且使Sh.二T。

3.19引入Robinson的歸結(jié)原理有何意義？其基本思想是什么？

3.20請寫出應用歸結(jié)原理進行定理證明的步驟，

3.21對下列各題分別證明G是否為E,E…，F(xiàn),的邏輯結(jié)論。

(1)F1:(3x)(3y)P(x,y)

G:(Vy)(3x)P(x,y)

(2)Fl:(Vx)(P(x)A(Q(a)vQ(b)))

G:(3x)(P(x)AQ(x))

(3)Fl:(3x)(3y)(P(f(x))AQ(f(b)))

G:P(f(a))AP(y)AQ(y)

(4)Fl:(Vx)(P(x)-(X/y)(Q(y?~Ux,y)))

F2:(3x)(P(x)A(Vy)(R(y)TL(X,y)))

G:"X)(R(X)T~Q(X))

(5)Fl:(Vx)(P(x)->(Q(x)AR(x)))

F2:(3x)(P(x)AS(X))

G:(3x)(S(x)AR(x))

(6)Fl:(Vz)(A(z)\-B(z)->(3y)(D(zy)AC(y)))

F2:(3Z)(E(Z)AA(Z)A(Vy)(D(zy)fE(y)))

F3:(Vz)(E(x)B(z))

G:(3Z)(E(Z)AC(Z))

3.22證明：

(Vy)(Q(y)->(B(y)AC(y)))A(3y)(Q(y)人D(y))->(3y)(D(y)AC(y))

3.23某單位招聘工作人員，張三、李四、王五三人應試，經(jīng)面試后單位有如下想法：

(1)如果錄取張三而不錄取李四，則一定錄取王五。

(2)如果錄取李四，則一定錄取王五。

(3)三人中至少要錄取一人。

求證：王五一定會被單位錄取。

3.24每個儲蓄錢的人就是為了獲得利息。求證：對某個人來說，如果不能獲得利息，則他就不會儲

蓄錢。

3.25請寫出利用歸結(jié)原理求解問題答案的步驟，

3.26應用歸結(jié)原理求解下列問題：

設張三、李四和王五三人中有人從不說真話，也有人從不說假話。某人向這三人分別提出同一個問題：

誰是說假話者？張三答：?李四和王五都是說假話者”；李四答："張三和王五都是說假話者.；王五答：“張

三和李四中至少有一個說假話者“。求誰是說假話者，誰是說真話者？

3.27已知樊臻的老師是張先生，樊臻與李偉是同班同學。如果x與y是同班同學，則x的老師也是y

的老師。請問李偉的老師是誰？

3.28什么是完備的歸結(jié)控制策略？有哪些歸結(jié)控制策略是完備的？

3.29設已知：

(1)能閱讀的人是識字的。

(2)海豚不識字。

(3)有些海豚是很聰明的。

用輸入歸結(jié)策略證明：有些很聰明的人并不識字。

3.30用輸入歸結(jié)策略是否可證明下列子句集的不可滿足性？

S={PVQtQVR,RVW,~RV-P,~WV~Q,~QV~R}

3.2習題參考斛答

3.1答：(略)

3.2答：(略)

3.3答：(略)

3.4答：(略)

3.5解：

在謂詞公式0x)(Wy)(P(、y)fQJy))中沒有包括個體常量和函數(shù)，所以，可以直接為謂

詞指派真值。設：

P(1.1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=F

Q(l,l)=T,Q(l,2)=F,Q(2,1)=T,Q(2.2)=F

在這種解釋下，對某一個x(x=l或x=2)對所有的y(即y=1或y=2)都不能使P(x,y)的真值

為T,所以，在此解釋下，P(x,y)的真值為F。同理，Q(x")的真值也為F。根據(jù)謂詞邏輯真值

表可知：在該解釋下，上述謂詞公式的真值為To

上述謂詞公式在D〃L2｝上共有256種解釋，這里不再一一列出，讀者可自己列出其中的幾

個，并求出其真值。

3.6解：

(1)P(x,y),Q(x,y)和R(x,y)中的x以及Q(xy),R(x,y)中的y是約束變元。P(x,y)中的y是自由

變元。量詞x的轄域使整個公式，量詞v的轄域是(Q(x,y)AR(x,y))o

(2)z和y是約束變元。x,u,v是自由變元。z和y轄域都是P(z,y)vQ(z,x)。

(3)x和z均是約束變元，沒有自由變元。x的轄域是整個公式,z的轄域是Q(x,z)A~R：x,z)。

(4)z、y和t均是約束變元。沒有自由變元。z和y的轄域是整個公式，t的轄域是P(z,t)

vQ(y.t)?

(5)本小題比較復雜，表面上只涉及兩個變元z和y,實際上公式中后面的兩個z和一個y

都可看成是另外的變量，因此，可作變元替換將公式變換為：

,,,,

(Vz)(3y)(P(Z,y)v(3z,)((Vy)(P(Z；y,)AQ(z',y)v(3z'')Q(Z;y))))

公式中的變元就成為z、v、z'v/z1,五個變元。z和y的轄域是整個公式，z,和

V'的轄域是P(z',y')人Q(z',y')v0z'')Q(z",y'),而7'為Q(「y)。

3.7答：(略)

3.8答：(略)

3.9解:

(1)P(a,b)與P(x,y)是可合一的。o={a/x,b/y}

(2)P(f(z),b)與P(x,y)是可合一的。o={f(z)/x,b/y}

(3)P(f(x),y)與P(y,f(a：)是可合一的。根據(jù)最一般合一求取算法，可得。={f(a)/y,a/x}

(4)P(f(y),y,x)與P(x,f(a),f(b))是不可合一的。

(5)P(x,y)與P(y,x)是可合一的。。={y/x}或。={x/y}

3.10答：

范式就是標準型。謂詞演算中，一般有兩種范式，一種叫前束形范式，另一種叫斯克林

(Skolem)范式。一個謂詞公式，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且

它的轄域一直延伸到公式之末，同時公式中不出現(xiàn)連接河一＞及這種形式的公式稱作前

束形范式。它的一般形式是

(QlXl)(Q2X2)-(QnXn)M(Xl,X2I-,Xn)

其中，Q(i二l,2rn)是存在量詞或全稱量詞，而母式M(X1,X2,…,xj不再含有量詞。

從前束形范式中消去全部存在量詞所得到的公式稱為Skolem標準型，它的一般形式是

(VXl)(VX2)-(VXn)M(Xl,X2,-,Xn)

3.11答：

子句就是由一些文字組成的析取式。而所謂文字是指原子或原子的否定。不含有任何

連接詞的謂詞公式叫做原子或原子公式。由子句構(gòu)成的集合稱為子句集。

求謂詞公式G的子句集的步驟如下：

(a)消去謂詞公式G中的蘊涵(一＞)和雙條件符號(一)，以一AVB代替A-B,以

(AAB)V(-AA~B)替換A—B。

(b)減少否定符號(~)的轄域，使否定符號最多只作用到一個謂詞上。

(c)重新命名變元名，使所有的變元的名字均不同，并且自由變元及約束變元亦不同。

(d)消去存在量詞。這里分兩種情況，一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域

內(nèi)，此時，只要用一個新的個體常量替換該存在量詞約天的變元，就可以消去存在量詞；另

一種情況是，存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如，

(Vxi)(Vx2)-(Vxn)(3y)P(Xi,x2,-,Xn,y)

此時,變元y實際受前面的變元xi,X2,X,、的約束，需要用Skolem函數(shù)f(x】,x2t…,4)

替換y即可將存在量詞y消去，得到：

(VXl)(VX2)-?(VXn)P(Xl,X2,'.Xn,f(Xl,X2,'.Xn))

(e)把全稱量詞全部移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整

個部分。

(f)母式化為合取范式：任何母式都可以寫成由一些謂詞公式和謂詞公式否定的析取的

有限集組成的合取。

(g)消去全稱量詞。

(h)對變元進行更名，是不同子句中的變元不同名。

(i)消去合取符號九將各子句寫成子居積合的形式。

3.12答：(略)

3.13解：

(1)因為"z)(Dy)(P(z,y)八Q(z,y))已經(jīng)是一個Skolem標準型，P(z,y)八Q(z,y)已是合取范

式，以逗號代替人.得子句集：S={P(z,y),Q(z,y)}

(2)首先將謂詞公式(以)”丫)似、丫)一(^(%丫))化為Skolem標準型：

(Vx)(Vy)(-P(x,y)vQ(x,y))

消去全稱量詞，并將母式化為子句集

S={~P(x,y)vQ(x.y)}

(3)首先將謂詞公式(Dx)(3y)(P(x,y)v(Q(x,y)->R(x,y)))化為Skolem標準型：

第一步：消去f號

(Dx)(3y)(P(x,y)v(~Q(x,y)vR(x,y)))

第二步：消去存在量詞，用Skolem函數(shù)f(x)代替y

(Vx)(P(xf(x)?~Q(x,f(x))vR(x,f(x)))

第三步：消去全稱量詞，并將母式化為子句集

S={P(x,f(x)卜~Qx,f(x))vR(x,f(x))}

(4)首先將謂詞公式(X/x)(Vy)0z)(P(%y)->Q(x,y)vR(x,z))化為Skolem標準型：

第一步：消去一號

(Vx)(Vy)(3z)(-P(x,y)vQ(x,y)vR(x.z))

第二步：消去存在量詞，用Skolem函數(shù)f(x,y)代替z

(Vx)(Vy)(~P(x,y)vQ(x,y)vR(x,f(x,y)))

第三步：消去全稱量詞，并將母式化為子句集

S={~P(x,y)vQ(x.y)vR(xJ(x,y))}

(5)將謂詞公式(3x)(3y)(Vz)(3u)(Vv)(3w)(P(x,y,z,u,v,w)A(Q(X,y,Z,U,V,W)V~R(x,z,w)))

化為Skolem標準型：

第一步：消去存在量詞x.y,以常量a,b分別代之

(Vz)(3u)(Vv)(3w)(P(a,b,z,u,v,w)八(Q(a,b,z,u.v,w)v~R(a,z,w)))

第二步：消去存在量詞u,由于u在全稱量詞z的轄域內(nèi)，令Skolem函數(shù)u二f⑵

(Vz)(Vv)(3w)(P(a,b,z,f(z),v,w)A(Q(a,b,z,f(z),v,w)v~R(a,z,w)))

再消去存在量詞w,由于w在全稱量詞z和v的轄域內(nèi)，令Skolem函數(shù)w=q(z,v)

(Vz)(Vv)(P(a,b,z,f(z),v,g(z,v))A(Q(a,b,z,f(z),v,g(z,v1)v~R(a,z,^z,v))))

第三步：消去全稱量詞，