人工智能第3章參考答案

1、第 3章 確定性推理部分參考答案判斷下列公式是否為可合一，若可合一，則求出其最一般合一。(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)解： 可合一，其最一般和一為=a/x, b/y。 可合一，其最一般和一為=y/f(x), b/z。 可合一，其最一般和一為：c= f(b)/y, b/x。(4) 不可合一。(5) 可合一，其最一般和一為：c = y/x。把下列謂詞公式化成子句集：(1) (x)(y)(

2、P(x, y)A Q(x,y)(2) (x)(y)(P(x, y戸 Q(x,y)(3) (x)(y)(P(x, y)V (Q(x,y尸 R(x,y)(4) ( x) ( y) ( z)(P(x, y戸 Q(x, y)V R(x, z)P(x, y)A Q(x, y)已經(jīng)是合解： 由于(x)(y)(P(x, y)A Q(x, y)已經(jīng)是Skolem標(biāo)準(zhǔn)型，且取范式，所以可直接消去全稱量詞、合取詞，得 P(x, y), Q(x, y)再進行變元換名得子句集：S= P(x, y), Q(u, v)(2) 對謂詞公式(x)(y)(P(x, y尸Q(x, y),先消去連接詞“宀”得:(x)(y)(P(x

3、, y)V Q(x, y)此公式已為 Skolem 標(biāo)準(zhǔn)型。再消去全稱量詞得子句集：S=P(x, yV) Q(x, y)J”得:(3) 對謂詞公式(x)( y)(P(x, y)V (Q(x, y尸R(x, y),先消去連接詞(x)( y)(P(x, y)V (Q(x, y)V R(x, y)此公式已為前束范式。再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x)(P(x, f(x)V Q(x, f(x)V R(x, f(x)此公式已為 Skolem 標(biāo)準(zhǔn)型。最后消去全稱量詞得子句集：S=P(x, f(x)V) Q(x, f(x)V R(x, f(x)J”得:(4) 對謂詞(x) ( y

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

5、x)V Q(x) , P(y)V R(y), P(a), S(a), S(V R(z)(5) P(x)V Q(f(x),a) , P(h(y)V Q(f(h(y), a) V P(z)(6) P(x)V Q(x)V R(x) , P(y)V R(y), Q(a), R(b) 解：(1)不可滿足，其歸結(jié)過程為：PV QQNIL(2) 不可滿足，其歸結(jié)過程為:(3) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4) 不可滿足，其歸結(jié)過程略(5) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6) 不可滿足，其歸結(jié)過程略對下列各題分別證明 G是否為F1,F2,nF勺邏輯結(jié)論:(1) F: ( x)(

6、y)(P(x, y)G: (y)( x)(P(x, y)(2) F: ( x)(P(x)A (Q(a)V Q(b)G: ( x) (P(x)A Q(x)(3) F: ( x)( y)(P(f(x)A (Q(f(y)G： P(f(a)A P(y)A Q(y)(4) Fi: (x)(P(x尸(y)(Q(y尸L)F2: ( x) (P(x)A (y)(R(y戸 L)G： ( x)(R(x戸Q(x)(5) Fi: (x)(P(x尸(Q(x)A R(x)F2: ( x) (P(x)A S(x)G: ( x) (S(x)A R(x)解：(1)先將F和G化成子句集：S=P(a,b), P(x,b)再對S進行

7、歸結(jié)：所以，G是F的邏輯結(jié)論(2) 先將F和G化成子句集由 F 得：S=P(x), (Q(a)V Q(b)由于 G 為：(x) (P(x)A Q(x),即卩(x) ( P(x)V Q(x),可得：S2= P(x)V Q(x)因此，擴充的子句集為：S= P(x) (Q(a) V Q(b),P(x)V Q(x)再對S進行歸結(jié)：所以，G是F的邏輯結(jié)論同理可求得(3)、(4)和(5),其求解過程略。設(shè)已知：(1) 如果x是y的父親，y是z的父親，貝U x是z的祖父；(2) 每個人都有一個父親。使用歸結(jié)演繹推理證明：對于某人u, 定存在一個人v, v是u的祖父。解：先定義謂詞F(x,y)： x是y的父親

8、GF(x,z) x是z的祖父P(x)： x是一個人再用謂詞把問題描述出來：已知 F1： ( x) ( y) (z)( F(x,y)A F(y,z)嚴(yán)GF(x,z)F2： ( y)(P(x尸F(xiàn)(x,y)求證結(jié)論 G： ( u) ( v)( P(u尸GF(v,u)然后再將F1, F2和G化成子句集： F(x,y)V F(y,z)V GF(x,z) P(r)V F(s,r) P(u) GF(v,u)對上述擴充的子句集，其歸結(jié)推理過程如下：由于導(dǎo)出了空子句，故結(jié)論得證。假設(shè)張被盜，公安局派出 5個人去調(diào)查。案情分析時，貞察員 A說：“趙與錢中至少有 一個人作案”，貞察員B說：“錢與孫中至少有一個人作案

9、”，貞察員C說：“孫與李中至少有一 個人作案”，貞察員D說：“趙與孫中至少有一個人與此案無關(guān)”，貞察員E說：“錢與李中至少 有一個人與此案無關(guān)”。如果這5個偵察員的話都是可信的，使用歸結(jié)演繹推理求出誰是盜竊犯。解：(1)先定義謂詞和常量設(shè)C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李(2) 將已知事實用謂詞公式表示出來趙與錢中至少有一個人作案：C(Z)V C(Q)錢與孫中至少有一個人作案：C(Q)V C(S)孫與李中至少有一個人作案：C(S)V C(L)趙與孫中至少有一個人與此案無關(guān)：(C (Z)A C(S)即C (Z)V C(S)錢與李中至少有一個人與此案無關(guān)：(C (Q)人C(

10、L),即C (Q)V C(L)(3) 將所要求的問題用謂詞公式表示出來，并與其否定取析取。設(shè)作案者為u,則要求的結(jié)論是C(u)o將其與其否)取析取，得：C(u) V C(u)(4) 對上述擴充的子句集，按歸結(jié)原理進行歸結(jié)，其修改的證明樹如下：因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出:因此，孫也是盜竊犯。設(shè)有子句集：P(x)V Q(a, b), P(a)VQ(a, b), Q(a, f(a), P(x)V Q(x, b)分別用各種歸結(jié)策略求出其歸結(jié)式。解：支持集策略不可用，原因是沒有指明哪個子句是由目標(biāo)公式的否定化簡來的。 刪除策略不可用，原因是子句集中沒有沒有重言

11、式和具有包孕關(guān)系的子句。 單文字子句策略的歸結(jié)過程如下：用線性輸入策略(同時滿足祖先過濾策略)的歸結(jié)過程如下:設(shè)已知：(1) 能閱讀的人是識字的；(2) 海豚不識字；(3) 有些海豚是很聰明的。請用歸結(jié)演繹推理證明：有些很聰明的人并不識字。 解：第一步，先定義謂詞， 設(shè)R(x)表示x是能閱讀的；K(y)表示y是識字的；W(z)表示z是很聰明的；第二步，將已知事實和目標(biāo)用謂詞公式表示出來能閱讀的人是識字的：(x)(R(x)嚴(yán)K(x) 海豚不識字：(y)(K (y)有些海豚是很聰明的：(z) W(z)有些很聰明的人并不識字：(x)( W(z)A K(x) 第三步，將上述已知事實和目標(biāo)的否定化成子句

12、集：R(x)V K(x)K (y)W(z)W(z) V K(x)第四步，用歸結(jié)演繹推理進行證明對子句集：PV Q, QV R, R W,RV P W V Q,QVR 用線性輸入策略是否可證明該子句集的不可滿足性解：用線性輸入策略不能證明子句集PV Q, QV R, RV W, RV P, WV Q, QV R 的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過程。對線性輸入策略和單文字子句策略分別給出一個反例，以說明它們是不完備的。分別說明正向、逆向、雙向與/或形演繹推理的基本思想。設(shè)已知事實為(PV Q)A R) V (SA (TV U)F規(guī)則為St (XA Y)V Z試用

13、正向演繹推理推出所有可能的子目標(biāo)。解：先給出已知事實的與/或樹，再利用F規(guī)則進行推理，其規(guī)則演繹系統(tǒng)如下圖所示。 由該圖可以直接寫出所有可能的目標(biāo)子句如下：PV QVTVUPV QVXVZPV QV YVZRV TV URV XV ZRV YV Z設(shè)有如下一段知識：“張、王和李都屬于高山協(xié)會。該協(xié)會的每個成員不是滑雪運動員，就是登山運動員，其 中不喜歡雨的運動員是登山運動員，不喜歡雪的運動員不是滑雪運動員。王不喜歡張所喜歡的 一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪。 ”試用謂詞公式集合表示這段知識，這些謂詞公式要適合一個逆向的基于規(guī)則的演繹系統(tǒng)。 試說明這樣一個系統(tǒng)怎樣才能回答問題

14、：“高山俱樂部中有沒有一個成員，他是一個登山運動員，但不是一個滑雪運動員”解：(1)先定義謂詞A(x)表示x是高山協(xié)會會員S(x)表示x是滑雪運動員C(x)表示x是登山運動員L(x,y)表示x 喜歡 y(2)將問題用謂詞表示出來“張、王和李都屬于高山協(xié)會A(Zhang)人 A(Wang)人 A(Li) 高山協(xié)會的每個成員不是滑雪運動員，就是登山運動員(x)(A(x)A S(xH C(x) 高山協(xié)會中不喜歡雨的運動員是登山運動員(x)(L(x, Ra in戸 C(x) 高山協(xié)會中不喜歡雪的運動員不是滑雪運動員(x)(L(x, SnowR S(x) 王不喜歡張所喜歡的一切東西(y)( L(Zhan

15、g, y)R L(Wang ,y)王喜歡張所不喜歡的一切東西(y)( L(Zhang, y)RL(Wang, y)張喜歡雨和雪L(Zhang , RainA) L(Zhang , Snow)(3) 將問題要求的答案用謂詞表示出來 高山俱樂部中有沒有一個成員，他是一個登山運動員，但不是一個滑雪運動員( x)( A(x)R C(x)A S(x)(4) 為了進行推理，把問題劃分為已知事實和規(guī)則兩大部分。假設(shè)，劃分如下： 已知事實：A(Zhang)A A(Wang)A A(Li)L(Zhang , RainA) L(Zhang , Snow) 規(guī)則：(x)(A(x)A S(x)R C(x)(x)(L(

16、x, Rain)RC(x)(x)(L(x, Snow)R S(x)(y)( L(Zhang, y)R L(Wang ,y)(y)( L(Zhang, y)RL(Wang, y)(5) 把已知事實、規(guī)則和目標(biāo)化成推理所需要的形式 事實已經(jīng)是文字的合取形式：f1: A(Zhang)A A(Wang)A A(Li) f2: L (Zhang , RainA) L(Zhang , Snow) 將規(guī)則轉(zhuǎn)化為后件為單文字的形式：r1: A(x)A S(x)R C(x)r2: L(x, RainR) C(x)r3: L(x, Snow)R S(x)r4: L(Zhang, y)R L(Wang ,y)r5: L(Zhang, y)R L(Wang , y) 將目標(biāo)公式轉(zhuǎn)換為與 / 或形式A(x)V (C(x)A S(x