人工智能教程習(xí)題及答案

人工智能教程

習(xí)題及答案

第一章緒論

1.1練習(xí)題

1.1什么是人類智能？它有哪些特征或特點(diǎn)？

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

1.3什么是人工智能？它的研究目標(biāo)是什么？

1.4人工智能有哪些主要研究領(lǐng)域？

1.5人工智能有哪幾個(gè)主要學(xué)派？各自的特點(diǎn)是什么？

1.6什么是以符號(hào)處理為核心的方法？

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

1.2習(xí)題參考斛答

(略)

第二章知識(shí)表示習(xí)題參考解答

2.3練習(xí)題

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

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

2.3在選擇知識(shí)的表示方法時(shí)，應(yīng)該考慮哪些主要因素？

2.4一階謂詞邏輯表示法適合于表示哪種類型的知識(shí)?它有哪些特點(diǎn)？

2.5請(qǐng)寫出用一階謂詞邏輯表示法表示知識(shí)的步驟“

2.6設(shè)有下列語(yǔ)句，請(qǐng)用相應(yīng)的謂詞公式把它們表示出來(lái)：

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

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

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

(4)所有人都有飯吃。

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

(6)要想出國(guó)留學(xué)，必須通過(guò)外語(yǔ)考試。

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

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

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

上，箱子位于位置b)。

圖2.11猴子摘香蕉問(wèn)題

2.8對(duì)習(xí)題2.7中的猴子摘香蕉問(wèn)題，利用一階謂詞邏輯表述一個(gè)行動(dòng)規(guī)劃，使問(wèn)題

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

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

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

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

策略沖突，如何解決？

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

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

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

小方塊的操作。

6

圖2.12習(xí)題2.12的圖圖2,13習(xí)題2.13的圖

2.13推銷員旅行問(wèn)題：

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

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

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

2.14何謂語(yǔ)義網(wǎng)絡(luò)？語(yǔ)義網(wǎng)絡(luò)表示法的特點(diǎn)是什么？

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

2.16用語(yǔ)義網(wǎng)絡(luò)表示下列知識(shí)：

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

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

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

2.17請(qǐng)對(duì)下列命題分別寫出它的語(yǔ)義網(wǎng)絡(luò)：

(1)每個(gè)學(xué)生都有多本書。

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

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

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

2.18請(qǐng)把下列命題用一個(gè)語(yǔ)義網(wǎng)絡(luò)表示出來(lái)：

(1)豬和羊都是動(dòng)物；

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

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

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

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

(3)根據(jù)所要表達(dá)的知識(shí)的語(yǔ)義，用適當(dāng)?shù)穆?lián)接符號(hào)將各個(gè)謂詞聯(lián)接起來(lái)，形成謂詞

公式。

2.6解：

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

定義謂詞及個(gè)體。設(shè)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)李明每天下午都去玩足球。

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

(Vy)(PLAYFB(Liming,y)

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

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

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

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

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

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

(4)所有人都有飯吃。

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

(Vx)(Havcfood(x))

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

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

個(gè)體代入謂詞，并根據(jù)題意將各謂詞用適當(dāng)?shù)倪B接符連接起來(lái)。

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

(6)要想出國(guó)留學(xué)，必須通過(guò)外語(yǔ)考試。

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

表示出國(guó)學(xué)習(xí)，language表示外語(yǔ)。將個(gè)體代入謂詞，并根據(jù)題意將各謂詞用適當(dāng)?shù)倪B接

符連接起來(lái)。

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

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

解法一：

本問(wèn)題涉及的常量定義為：

猴子：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ù)問(wèn)題的描述將問(wèn)題的初始狀態(tài)和目標(biāo)狀態(tài)分別用謂詞公式表示如下：

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

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

HOLDS(Monkey,Banana)

問(wèn)題的目標(biāo)狀態(tài)表示：

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

HOLDS(Monkey,Banana)

解法二：

本問(wèn)題涉及的常量定義為：

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

定義謂詞如下

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

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

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

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

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

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

問(wèn)題的目標(biāo)狀態(tài)表示

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

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

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

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

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

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

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

中謂詞公式的增減來(lái)描述動(dòng)作。

定義四個(gè)操作謂詞如下，操作的條件和動(dòng)作可用謂詞公式的增刪表示：

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

條件：SITE(Monkey,x)

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

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

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

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

3.climbbox：爬到箱子頂上。

條件：?ONBOX(Monkey)

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

4.grasp:摘下香蕉。

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

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

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

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

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

中，當(dāng)進(jìn)行條件檢查時(shí)，要進(jìn)行適當(dāng)?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ī)則。如果把棋盤的每一種布局看作是一個(gè)狀

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

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

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

規(guī)則，來(lái)實(shí)現(xiàn)這四種移動(dòng)，

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

矩陣中用。來(lá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ù)庫(kù)。將棋盤的布局表示為狀態(tài)矩陣的形式存入綜合數(shù)據(jù)庫(kù)，例如,

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

983193

So=160Sg=804

754765

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

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

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

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

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

題選擇。在本題中，我們采用一個(gè)啟發(fā)式函數(shù)h(x),它表示節(jié)點(diǎn)x所對(duì)應(yīng)的棋盤中與目標(biāo)節(jié)

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

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

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

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

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

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

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

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

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

各城市間的距離表。初始時(shí)刻，已訪問(wèn)過(guò)的城市名列表口只有A,未訪問(wèn)過(guò)的城市名列表中

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

not-visit(x)：表示未訪問(wèn)過(guò)城市x;

visit-all():表示已沒有未訪問(wèn)過(guò)的城市；

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

中刪除。

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

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

R2:visit-allO-*goto(A)

當(dāng)未訪問(wèn)過(guò)的城市列表不為空時(shí)，激活規(guī)則R1；否則，激活規(guī)則R2。

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

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

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

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

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

x：=BoEDCo

R2被激活，返回城市A。

2.14答：(略)

2.15答：(略)

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

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

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

用AKO表示。

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

(4)將各對(duì)象作為一個(gè)節(jié)點(diǎn)，而它們之間的關(guān)系作為弧，則得到圖2.15所示的語(yǔ)義

網(wǎng)絡(luò)。

|/有羽毛

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

,I能吃食

受過(guò)訓(xùn)練飛翔帶哨聲會(huì)吃叫

圖2.15有關(guān)鴿子的語(yǔ)義網(wǎng)絡(luò)

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

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

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

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

GS代表整個(gè)空間。

學(xué)生擁有多本書

g

圖2.16"每個(gè)學(xué)生都有多本書”的語(yǔ)義網(wǎng)絡(luò)

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

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

網(wǎng)絡(luò)技術(shù),

客體2

主體序磯?■叁計(jì)算機(jī)應(yīng)用

麗?是_生「孫老師11

時(shí)間

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

圖2.17有關(guān)講課的語(yǔ)義網(wǎng)絡(luò)

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

圖2.18有關(guān)雪地上腳印的語(yǔ)義網(wǎng)絡(luò)

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

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

是

圖2.19有關(guān)電腦公司的語(yǔ)義網(wǎng)絡(luò)

2.18解：按照語(yǔ)義網(wǎng)絡(luò)知識(shí)表示步驟來(lái)首先進(jìn)行解題分析：

(1)問(wèn)題涉及的對(duì)象有動(dòng)物、偶蹄動(dòng)物、哺乳動(dòng)物、豬、羊、野豬、山羊、綿羊共8

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

的特點(diǎn)。

(2)羊和豬與偶蹄動(dòng)物、哺乳動(dòng)物間是類屬關(guān)系，偶蹄動(dòng)物、哺乳動(dòng)物與動(dòng)物間也是

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

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

免屬性信息重復(fù)。

(4)根據(jù)上面的分析，本題共涉及8個(gè)對(duì)象，各時(shí)象的屬性以及它們之間的關(guān)系已在

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

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

圖2.20有關(guān)豬和羊的語(yǔ)義網(wǎng)絡(luò)

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

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

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

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

以是程序、條件、默認(rèn)值或是一個(gè)子框架?？蚣芤话憧杀硎境扇缦滦问剑?/p>

框架名

〈槽名1>

〈側(cè)面11>

m>-<?nki>

<側(cè)面lni>

〈值lnil>-<filnikm>

〈槽名2>

〈側(cè)面12>

〈值121>…〈值12L>

〈側(cè)面ln?>

（值lrhlA-v值In21n2>

2.20答：（略）

2.21解：由于學(xué)生框架類似于一個(gè)變量，并未指定某個(gè)具體的學(xué)生，所以，其定義應(yīng)

該如下，若要描述某個(gè)具體的學(xué)生，則只要將他的相應(yīng)屬性填入到這個(gè)框架的各個(gè)槽中即可。

框架名：〈學(xué)生〉

姓名：?jiǎn)挝唬ㄐ蘸兔?/p>

年齡：?jiǎn)挝唬q）

性別：范圍（男，女）

缺?。校?/p>

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

缺省（一般）

所在系別：?jiǎn)挝唬ㄏ担?/p>

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

入學(xué)時(shí)間：?jiǎn)挝唬?，月?/p>

畢業(yè)時(shí)間：?jiǎn)挝唬?，月?/p>

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

缺省(良)

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

缺省(否)

2.22答：(略)

2.23答：(略)

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

間。它一般由三部分構(gòu)成：?jiǎn)栴}的所有可能初始狀態(tài)構(gòu)成的集合S；算符集合F；目標(biāo)狀態(tài)

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

2.25答：(略)

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

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

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

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

二0表示不在左岸)O

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

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

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

和1兩種可能，所以本問(wèn)題所有可能的狀態(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ù)量都不得超過(guò)傳教士的數(shù)量

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

狀態(tài)。而由于這些不合法狀杰的存在，又會(huì)導(dǎo)致某些合法狀態(tài)是不可到達(dá)的。這樣，這個(gè)問(wèn)

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

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

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

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

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

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

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)

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

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

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

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

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

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

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

通路都是問(wèn)題的一個(gè)解。具中：

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ìn)行表示。根據(jù)狀態(tài)空間表示問(wèn)題的步驟，問(wèn)題求解如下：

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

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

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

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

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

由于狀態(tài)變量有4個(gè)元素，每個(gè)元素有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)

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

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

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

上，故定義算符如下：

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

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

R(f.j)表示從右岸將第j樣?xùn)|西帶回左岸。

所以，所定義的算符組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可以不要，也就是說(shuō)，完全可以把操作算符定義成

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

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

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

圖2.22所示。

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

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

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

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

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

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)空間表示問(wèn)題的步驟，問(wèn)題求解如下：

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

設(shè)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)及和目標(biāo)狀態(tài)集。

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

*3x2=36個(gè)狀態(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),目標(biāo)狀態(tài)Su-(b,l,b,1)

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

定義操作算符組如下：

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

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

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

④grasp:猴子摘下香蕉。

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

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

始狀態(tài)到目標(biāo)狀態(tài)的最短路徑，其所對(duì)應(yīng)的操作符序列如下，它就是該問(wèn)題的解。

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

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

3.1練習(xí)題

3.1什么是命題？請(qǐng)寫出3個(gè)真值為T及真值為F的命題。

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

3.3謂詞邏輯和命題邏輯的關(guān)系如何？有何異同？

3.4什么是謂詞的項(xiàng)？什么是謂詞的階？請(qǐng)寫出謂詞的一般形式。

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

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

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

3.6對(duì)下列謂詞公式分別指出哪些是約束變?cè)?？哪些是自由變?cè)?？并指出各量詞的轄域。

(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什么是謂詞公式的永真性、永假性、可滿足性、等價(jià)性及永真蘊(yùn)含？

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

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

⑴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什么是范式？請(qǐng)寫出前束型范式與SKOLEM范式的形式。

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

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

3.13把下列謂詞公式分別化為相應(yīng)的子句集：

(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上的一個(gè)解釋I構(gòu)造H域上的解釋「呢？

3.18假設(shè)子句集S={P(z)VQ(z),R(f(t))},S中不出現(xiàn)個(gè)體常至符號(hào)。設(shè)個(gè)體域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)),-)

如果設(shè)I是D上的解釋，并作如下的設(shè)定

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

22TFFTFT

請(qǐng)構(gòu)造H域上的一個(gè)解釋「與I相對(duì)應(yīng)，且使Sh.二T。

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

3.20請(qǐng)寫出應(yīng)用歸結(jié)原理進(jìn)行定理證明的步驟，

3.21對(duì)下列各題分別證明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某單位招聘工作人員，張三、李四、王五三人應(yīng)試，經(jīng)面試后單位有如下想法：

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

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

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

求證：王五一定會(huì)被單位錄取。

3.24每個(gè)儲(chǔ)蓄錢的人就是為了獲得利息。求證：對(duì)某個(gè)人來(lái)說(shuō)，如果不能獲得利息，則他就不會(huì)儲(chǔ)

蓄錢。

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

3.26應(yīng)用歸結(jié)原理求解下列問(wèn)題：

設(shè)張三、李四和王五三人中有人從不說(shuō)真話，也有人從不說(shuō)假話。某人向這三人分別提出同一個(gè)問(wèn)題：

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

三和李四中至少有一個(gè)說(shuō)假話者“。求誰(shuí)是說(shuō)假話者，誰(shuí)是說(shuō)真話者？

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

的老師。請(qǐng)問(wèn)李偉的老師是誰(shuí)？

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

3.29設(shè)已知：

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

(2)海豚不識(shí)字。

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

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

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

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

3.2習(xí)題參考斛答

3.1答：(略)

3.2答：(略)

3.3答：(略)

3.4答：(略)

3.5解：

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

詞指派真值。設(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

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

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

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

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

個(gè)，并求出其真值。

3.6解：

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

變?cè)Ａ吭~x的轄域使整個(gè)公式，量詞v的轄域是(Q(x,y)AR(x,y))o

(2)z和y是約束變?cè),u,v是自由變?cè)?。z和y轄域都是P(z,y)vQ(z,x)。

(3)x和z均是約束變?cè)瑳]有自由變?cè)?。x的轄域是整個(gè)公式,z的轄域是Q(x,z)A~R：x,z)。

(4)z、y和t均是約束變?cè)]有自由變?cè)和y的轄域是整個(gè)公式，t的轄域是P(z,t)

vQ(y.t)?

(5)本小題比較復(fù)雜，表面上只涉及兩個(gè)變?cè)獄和y,實(shí)際上公式中后面的兩個(gè)z和一個(gè)y

都可看成是另外的變量，因此，可作變?cè)鎿Q將公式變換為：

,,,,

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

公式中的變?cè)统蔀閦、v、z'v/z1,五個(gè)變?cè)和y的轄域是整個(gè)公式，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答：

范式就是標(biāo)準(zhǔn)型。謂詞演算中，一般有兩種范式，一種叫前束形范式，另一種叫斯克林

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

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

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

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

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

從前束形范式中消去全部存在量詞所得到的公式稱為Skolem標(biāo)準(zhǔn)型，它的一般形式是

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

3.11答：

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

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

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

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

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

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

(c)重新命名變?cè)?，使所有的變?cè)拿志煌?，并且自由變?cè)凹s束變?cè)嗖煌?/p>

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

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

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

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

此時(shí),變?cè)獃實(shí)際受前面的變?cè)獂i,X2,X,、的約束，需要用Skolem函數(shù)f(x】,x2t…,4)

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

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

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

個(gè)部分。

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

有限集組成的合取。

(g)消去全稱量詞。

(h)對(duì)變?cè)M(jìn)行更名，是不同子句中的變?cè)煌?/p>

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

3.12答：(略)

3.13解：

(1)因?yàn)?z)(Dy)(P(z,y)八Q(z,y))已經(jīng)是一個(gè)Skolem標(biāo)準(zhǔn)型，P(z,y)八Q(z,y)已是合取范

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

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

(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標(biāo)準(zhǔn)型：

第一步：消去f號(hào)

(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標(biāo)準(zhǔn)型：

第一步：消去一號(hào)

(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標(biāo)準(zhǔn)型：

第一步：消去存在量詞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))))

第三步：消去全稱量詞，