人工智能第3章課后習(xí)題 參考答案

1、第3章 確定性推理部分參考答案3.8 判斷下列公式是否為可合一，若可合一，則求出其最一般合一。(1) p(a, b), p(x, y)(2) p(f(x), b), p(y, z)(3) p(f(x), y), p(y, f(b)(4) p(f(y), y, x), p(x, f(a), f(b) (5) p(x, y), p(y, x)解：(1) 可合一，其最一般和一為：=a/x, b/y。(2) 可合一，其最一般和一為：=y/f(x), b/z。(3) 可合一，其最一般和一為：= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一為：= y/x。3.11 把下列謂詞公式

2、化成子句集：(1) (x)(y)(p(x, y)q(x, y)(2) (x)(y)(p(x, y)q(x, y)(3) (x)(y)(p(x, y)(q(x, y)r(x, y)(4) (x) (y) (z)(p(x, y)q(x, y)r(x, z) 解：(1) 由于(x)(y)(p(x, y)q(x, y)已經(jīng)是skolem標(biāo)準(zhǔn)型，且p(x, y)q(x, y)已經(jīng)是合取范式，所以可直接消去全稱量詞、合取詞，得 p(x, y), q(x, y) 再進(jìn)行變?cè)獡Q名得子句集： s= p(x, y), q(u, v) (2) 對(duì)謂詞公式(x)(y)(p(x, y)q(x, y)，先消去連接詞“”得

3、：(x)(y)(p(x, y)q(x, y)此公式已為skolem標(biāo)準(zhǔn)型。 再消去全稱量詞得子句集： s=p(x, y)q(x, y) (3) 對(duì)謂詞公式(x)(y)(p(x, y)(q(x, y)r(x, y)，先消去連接詞“”得：(x)(y)(p(x, y)(q(x, y)r(x, y)此公式已為前束范式。再消去存在量詞，即用skolem函數(shù)f(x)替換y得：(x)(p(x, f(x)q(x, f(x)r(x, f(x)此公式已為skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得子句集： s=p(x, f(x)q(x, f(x)r(x, f(x) (4) 對(duì)謂詞(x) (y) (z)(p(x, y)

4、q(x, y)r(x, z)，先消去連接詞“”得：(x) (y) (z)(p(x, y)q(x, y)r(x, z)再消去存在量詞，即用skolem函數(shù)f(x)替換y得：(x) (y) (p(x, y)q(x, y)r(x, f(x,y)此公式已為skolem標(biāo)準(zhǔn)型。 最后消去全稱量詞得子句集：s=p(x, y)q(x, y)r(x, f(x,y)3-13 判斷下列子句集中哪些是不可滿足的：(1) pq, q, p, p(2) pq , pq, pq, pq (3) p(y)q(y) , p(f(x)r(a)(4) p(x)q(x) , p(y)r(y), p(a), s(a), s(z)r(

5、z)(5) p(x)q(f(x),a) , p(h(y)q(f(h(y), a)p(z)(6) p(x)q(x)r(x) , p(y)r(y), q(a), r(b) 解：(1) 不可滿足，其歸結(jié)過程為：pqqppnil(2) 不可滿足，其歸結(jié)過程為：pqpqqpqpqqnil(3) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4) 不可滿足，其歸結(jié)過程略(5) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6) 不可滿足，其歸結(jié)過程略 3.14 對(duì)下列各題分別證明g是否為f1,f2,fn的邏輯結(jié)論：(1) f: (x)(y)(p(x, y)g: (y)(x)(p(x, y)(2) f: (x)

6、(p(x)(q(a)q(b)g: (x) (p(x)q(x)(3) f: (x)(y)(p(f(x)(q(f(y)g: p(f(a)p(y)q(y)(4) f1: (x)(p(x)(y)(q(y)l(x.y)f2: (x) (p(x)(y)(r(y)l(x.y)g: (x)(r(x)q(x)(5) f1: (x)(p(x)(q(x)r(x)f2: (x) (p(x)s(x)g: (x) (s(x)r(x) 解：(1) 先將f和g化成子句集： s=p(a,b), p(x,b) 再對(duì)s進(jìn)行歸結(jié)：p(x,b)p(a,b)nil a/x 所以，g是f的邏輯結(jié)論(2) 先將f和g化成子句集由f得：s1=

7、p(x)，(q(a)q(b)由于g為： (x) (p(x)q(x)，即 (x) ( p(x) q(x)，可得： s2= p(x) q(x)因此，擴(kuò)充的子句集為：s= p(x)，(q(a)q(b)， p(x) q(x) 再對(duì)s進(jìn)行歸結(jié)：q(a)q(b)q(a) p(x) q(x) p(a)p(x)nilq(a)q(b) a/b p(x) q(x)q(a)a/x p(a)p(x) a/xnil 所以，g是f的邏輯結(jié)論 同理可求得(3)、(4)和(5)，其求解過程略。 3.15 設(shè)已知：(1) 如果x是y的父親，y是z的父親，則x是z的祖父；(2) 每個(gè)人都有一個(gè)父親。使用歸結(jié)演繹推理證明：對(duì)于某人

8、u，一定存在一個(gè)人v，v是u的祖父。 解：先定義謂詞 f(x,y)：x是y的父親 gf(x,z)：x是z的祖父 p(x)：x是一個(gè)人 再用謂詞把問題描述出來： 已知f1：(x) (y) (z)( f(x,y)f(y,z)gf(x,z) f2：(y)(p(x)f(x,y) 求證結(jié)論g：(u) (v)( p(u)gf(v,u) 然后再將f1，f2和g化成子句集： f(x,y)f(y,z)gf(x,z) p(r)f(s,r) p(u) gf(v,u) 對(duì)上述擴(kuò)充的子句集，其歸結(jié)推理過程如下：f(x,y)f(y,z)gf(x,z)gf(v,u)f(x,y)f(y,z)p(r)f(s,r)f(y,z)p

9、(y)p(r)f(s,r)p(y)p(z)p(y)p(u)nil x/v,z/ux/s,y/ry/s,z/r y/z y/u 由于導(dǎo)出了空子句，故結(jié)論得證。3.16 假設(shè)張被盜，公安局派出5個(gè)人去調(diào)查。案情分析時(shí)，貞察員a說：“趙與錢中至少有一個(gè)人作案”，貞察員b說：“錢與孫中至少有一個(gè)人作案”，貞察員c說：“孫與李中至少有一個(gè)人作案”，貞察員d說：“趙與孫中至少有一個(gè)人與此案無關(guān)”，貞察員e說：“錢與李中至少有一個(gè)人與此案無關(guān)”。如果這5個(gè)偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰是盜竊犯。解：(1) 先定義謂詞和常量設(shè)c(x)表示x作案，z表示趙，q表示錢，s表示孫，l表示李(2) 將已

10、知事實(shí)用謂詞公式表示出來趙與錢中至少有一個(gè)人作案：c(z)c(q)錢與孫中至少有一個(gè)人作案：c(q)c(s)孫與李中至少有一個(gè)人作案：c(s)c(l)趙與孫中至少有一個(gè)人與此案無關(guān)： (c (z)c(s)，即 c (z) c(s)錢與李中至少有一個(gè)人與此案無關(guān)： (c (q)c(l)，即 c (q) c(l)(3) 將所要求的問題用謂詞公式表示出來，并與其否定取析取。設(shè)作案者為u，則要求的結(jié)論是c(u)。將其與其否)取析取，得： c(u) c(u)(4) 對(duì)上述擴(kuò)充的子句集，按歸結(jié)原理進(jìn)行歸結(jié)，其修改的證明樹如下：c(z)c(q)c (z) c(s)c(q)c(s)c(q)c(s)c(q)c(

11、u)c(u)c(q) q/u 因此，錢是盜竊犯。實(shí)際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出：c(s)c(l)c (q) c(l)c(s)c(q)c(q)c(s)c(s)c(u)c(u)c(s)c (q) c(l)c(s)c(l)c(q)c(s)c(s)c(q)c(u)c(u)c(s) s/u c(s) 因此，孫也是盜竊犯。3.18 設(shè)有子句集： p(x)q(a, b), p(a)q(a, b), q(a, f(a), p(x)q(x, b)分別用各種歸結(jié)策略求出其歸結(jié)式。解：支持集策略不可用，原因是沒有指明哪個(gè)子句是由目標(biāo)公式的否定化簡(jiǎn)來的。刪除策略不可用，原因是子句集中沒有沒有重言

12、式和具有包孕關(guān)系的子句。單文字子句策略的歸結(jié)過程如下：q(a, f(a)p(x)q(a, b) b/f(a)p(x)q(x, b)p(a)q(a, f(a)q(a, b) a/x b/f(a)q(a, b)用線性輸入策略（同時(shí)滿足祖先過濾策略）的歸結(jié)過程如下：p(a)q(a, b)p(x)q(a, b)p(x)q(x, b)p(a) a/xa/xq(a, f(a)q(a,b) b/f(a)nil 3.19 設(shè)已知：(1) 能閱讀的人是識(shí)字的；(2) 海豚不識(shí)字；(3) 有些海豚是很聰明的。請(qǐng)用歸結(jié)演繹推理證明：有些很聰明的人并不識(shí)字。解：第一步，先定義謂詞， 設(shè)r(x)表示x是能閱讀的；k(y

13、)表示y是識(shí)字的；w(z) 表示z是很聰明的；第二步，將已知事實(shí)和目標(biāo)用謂詞公式表示出來能閱讀的人是識(shí)字的：(x)(r(x)k(x)海豚不識(shí)字：(y)(k (y)有些海豚是很聰明的：(z) w(z)有些很聰明的人并不識(shí)字：(x)( w(z)k(x) 第三步，將上述已知事實(shí)和目標(biāo)的否定化成子句集： r(x)k(x)k (y)w(z)w(z)k(x) 第四步，用歸結(jié)演繹推理進(jìn)行證明w(z)w(z)k(x)w(z)k(z)nil3.20 對(duì)子句集： pq, qr, rw, rp, wq, qr 用線性輸入策略是否可證明該子句集的不可滿足性？ 解：用線性輸入策略不能證明子句集pq, qr, rw, r

14、p, wq, qr 的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過程。3.21 對(duì)線性輸入策略和單文字子句策略分別給出一個(gè)反例，以說明它們是不完備的。3.22 分別說明正向、逆向、雙向與/或形演繹推理的基本思想。3.23 設(shè)已知事實(shí)為 (pq)r) (s(tu) f規(guī)則為 s(xy)z試用正向演繹推理推出所有可能的子目標(biāo)。解：先給出已知事實(shí)的與/或樹，再利用f規(guī)則進(jìn)行推理，其規(guī)則演繹系統(tǒng)如下圖所示。由該圖可以直接寫出所有可能的目標(biāo)子句如下： pqpqpqyrtu rxzryz 所有子目標(biāo)utzyxrqp所有目標(biāo)utzyxrqpyxzxysuttus所有目標(biāo)utzyxrqp

15、所有目標(biāo)yzutxprqyxxyf規(guī)則zxyxyzssutqptuqp已知事實(shí)已知事實(shí)tusr(pq)turs(pq) (s(tu)(pq)r) (s(tu)(pq)r)(pq)r) (s(tu)(pq)r) (s(tu)3.24 設(shè)有如下一段知識(shí)：“張、王和李都屬于高山協(xié)會(huì)。該協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)動(dòng)員，就是登山運(yùn)動(dòng)員，其中不喜歡雨的運(yùn)動(dòng)員是登山運(yùn)動(dòng)員，不喜歡雪的運(yùn)動(dòng)員不是滑雪運(yùn)動(dòng)員。王不喜歡張所喜歡的一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪?！痹囉弥^詞公式集合表示這段知識(shí)，這些謂詞公式要適合一個(gè)逆向的基于規(guī)則的演繹系統(tǒng)。試說明這樣一個(gè)系統(tǒng)怎樣才能回答問題：“高山俱樂部中有沒有一

16、個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員，但不是一個(gè)滑雪運(yùn)動(dòng)員？”解：(1) 先定義謂詞a(x) 表示x是高山協(xié)會(huì)會(huì)員s(x) 表示x是滑雪運(yùn)動(dòng)員c(x) 表示x是登山運(yùn)動(dòng)員l(x,y) 表示x 喜歡y (2) 將問題用謂詞表示出來“張、王和李都屬于高山協(xié)會(huì)a(zhang)a(wang)a(li)高山協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)動(dòng)員，就是登山運(yùn)動(dòng)員(x)(a(x)s(x)c(x)高山協(xié)會(huì)中不喜歡雨的運(yùn)動(dòng)員是登山運(yùn)動(dòng)員(x)(l(x, rain)c(x)高山協(xié)會(huì)中不喜歡雪的運(yùn)動(dòng)員不是滑雪運(yùn)動(dòng)員(x)(l(x, snow) s(x)王不喜歡張所喜歡的一切東西(y)( l(zhang, y) l(wang ,y) 王

17、喜歡張所不喜歡的一切東西(y)( l(zhang, y)l(wang, y)張喜歡雨和雪l(zhang , rain)l(zhang , snow)(3) 將問題要求的答案用謂詞表示出來高山俱樂部中有沒有一個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員，但不是一個(gè)滑雪運(yùn)動(dòng)員？ (x)( a(x)c(x) s(x) (4) 為了進(jìn)行推理，把問題劃分為已知事實(shí)和規(guī)則兩大部分。假設(shè)，劃分如下：已知事實(shí)：a(zhang)a(wang)a(li)l(zhang , rain)l(zhang , snow)規(guī)則：(x)(a(x)s(x)c(x)(x)(l(x, rain)c(x)(x)(l(x, snow) s(x)(y)( l(zhang, y) l(wang ,y)(y)( l(zhang, y)l(wang, y) (5) 把已知事實(shí)、規(guī)則和目標(biāo)化成推理所需要的形式事實(shí)已經(jīng)是文字的合取形式：f1: a(zhang)a(wang)a(li)f2: l (zhang , rain)l(zhang , snow)將規(guī)則轉(zhuǎn)化為后件為單文字的形式：r1: a(x)s(x)c(x)r2: l(x, rain)c(x)r3: l(x, snow) s(x)r4: l(zhang, y) l(wang ,y)r5: l(zhang, y)l(wang