人工智能確定性推理部分參考答案

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

2、(y)(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)解： 由于(x)(y)(P(x, y)A Q(x, y)已經(jīng)是 Skolem 標(biāo)準(zhǔn)型，且合取范式，所以可直接消去全稱量詞、合取詞，得 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)，先消去連接詞“宀”得:(x)( y)(?P(x, y)Q

3、V(x, y)此公式已為 Skolem 標(biāo)準(zhǔn)型。再消去全稱量詞得子句集：S=?P(x, y)QV(x, y)(3) 對(duì)謂詞公式(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)(4) 對(duì)謂詞(x) ( y) ( z)(P(

4、x, y)Q(x, y) V R(x, z),先消去連接詞P(x, y)A Q(x, y)已經(jīng)是J”得:J”得:整理文檔( x) ( y) ( z)(?P(x, y) Q(xV,y)V R(x, z)再消去存在量詞，即用Skolem 函數(shù) f(x)替換 y 得：( x) ( y) (?P(x, y) Q(xV,y)V R(x, f(x,y)此公式已為 Skolem 標(biāo)準(zhǔn)型。最后消去全稱量詞得子句集：S= ?P(x, y)Qx,y) V R(x, f(x,y)3 判斷下列子句集中哪些是不可滿足的：(1)?P V Q, ?Q, P, ?P(2) P V Q , ?PV Q, PV ?Q, ?P V

5、 ?Q (3) P(y) V Q(y) , ?P(f(x)V(a)(4)?P(x) VQ(x) , ?P(y) VR(y), P(a), S(a), ?S(z)V ?R(z)(5)?P(x) VQ(f(x),a) , ?P(h(y)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é)過(guò)程為：?PVQ?QNIL(2)不可滿足，其歸結(jié)過(guò)程為:(3) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4) 不可滿足，其歸結(jié)過(guò)程略(5) 不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6) 不可滿

6、足，其歸結(jié)過(guò)程略4 對(duì)下列各題分別證明 G 是否為 F1F2,F 的邏輯結(jié)論:(1)F: (x)( y)(P(x, y)G:(y)( x)(P(x, y)F: (x)(P(x)A (Q(a) V Q(b)G:(x) (P(x)A Q(x)F: (x)( y)(P(f(x) A (Q(f(y)整理文檔G: P(f(a)A P(y)A Q(y)F1：( x)(P(x)f (y)(Q(y)L(x.y)F2：(x) (P(x) A (y)(R(y) L(x.y)G:(x)(R(x)fQ(x)F1：(X)(P(X)T(Q(x) A R(x)F2：( x) (P(x) A S(x)整理文檔G: ( x)

7、(S(x)人 R(x)解：(1)先將 F 和？ G 化成子句集:S=P(a,b), ? P(x,b)再對(duì) S 進(jìn)行歸結(jié)：所以，G 是 F 的邏輯結(jié)論(2)先將 F 和？ G 化成子句集由 F 得：Si=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)因此，擴(kuò)充的子句集為：S= P(x) , (Q(a)V Q(b), ? P(x) V? Q(x)再對(duì) S 進(jìn)行歸結(jié)：所以，G 是 F 的邏輯結(jié)論 同理可求得(3)、(4)和(5),其求解過(guò)程略。5 設(shè)已知:(1) 如果 x 是

8、 y 的父親，y 是 z 的父親，則 x 是 z 的祖父；(2) 每個(gè)人都有一個(gè)父親。使用歸結(jié)演繹推理證明：對(duì)于某人U, 定存在一個(gè)人V, v 是 U 的祖父。解：先定義謂詞F(x,y)： x 是 y 的父親GF(x,z): x 是 z 的祖父P(x)： x 是一個(gè)人再用謂詞把問(wèn)題描述出來(lái)：整理文檔已知 F1： ( x) ( y) (z)( F(x,y)A F(y,z)GF(x,z)F2 : (y)(P(x)f F(x,y)求證結(jié)論 G : ( u) ( v)( P(u)TGF(v,u)然后再將 F1, F2 和？ G 化成子句集：1？F(x,y)V? F(y,z)V GF(x,z)2？P(r

9、)V F(s,r)3P(u)4?GF(v,u)對(duì)上述擴(kuò)充的子句集，其歸結(jié)推理過(guò)程如下:由于導(dǎo)出了空子句，故結(jié)論得證。6 假設(shè)張被盜，公安局派出5 個(gè)人去調(diào)查。案情分析時(shí)，貞察員A 說(shuō)：“趙與錢中至少有一個(gè)人作案”，貞察員 B 說(shuō)：“錢與孫中至少有一個(gè)人作案”，貞察員 C 說(shuō)：“孫與李中 至少有一個(gè)人作案”，貞察員 D 說(shuō)：“趙與孫中至少有一個(gè)人與此案無(wú)關(guān)”，貞察員 E 說(shuō)：“錢與李中至少有一個(gè)人與此案無(wú)關(guān)”。如果這 5 個(gè)偵察員的話都是可信的，使用歸結(jié)演繹推理 求出誰(shuí)是盜竊犯。解：(1)先定義謂詞和常量設(shè) C(x)表示 x 作案，Z 表示趙，Q 表示錢，S 表示孫，L 表示李(2) 將已知事實(shí)

10、用謂詞公式表示出來(lái)趙與錢中至少有一個(gè)人作案：C(Z) V C(Q)錢與孫中至少有一個(gè)人作案：C(Q) V C(S)孫與李中至少有一個(gè)人作案：C(S)V C(L)趙與孫中至少有一個(gè)人與此案無(wú)關(guān)：？(C (C)S),用卩？C (Z) V ?C(S)錢與李中至少有一個(gè)人與此案無(wú)關(guān)：？ (C (Q)L) ,/W ?C (Q) V ?C(L)(3) 將所要求的問(wèn)題用謂詞公式表示出來(lái)，并與其否定取析取。設(shè)作案者為 u,則要求的結(jié)論是 C(u)。將其與其否)取析取，得：? C(u) V C(u)整理文檔(4) 對(duì)上述擴(kuò)充的子句集，按歸結(jié)原理進(jìn)行歸結(jié)，其修改的證明樹(shù)如下：整理文檔因此，錢是盜竊犯。實(shí)際上，本案

11、的盜竊犯不止一人。根據(jù)歸結(jié)原理還可以得出:因此，孫也是盜竊犯。7 設(shè)有子句集：P(x) V Q(a, b), P(a)VQ(a, b), Q(a, f(a), P(x) V Q(x, b)分別用各種歸結(jié)策略求出其歸結(jié)式。解：支持集策略不可用，原因是沒(méi)有指明哪個(gè)子句是由目標(biāo)公式的否定化簡(jiǎn)來(lái)的。 刪除策略不可用，原因是子句集中沒(méi)有沒(méi)有重言式和具有包孕關(guān)系的子句。 單文字子句策略的歸結(jié)過(guò)程如下：Q(a, b)整理文檔用線性輸入策略(同時(shí)滿足祖先過(guò)濾策略)的歸結(jié)過(guò)程如下:8 設(shè)已知：(1) 能閱讀的人是識(shí)字的；(2) 海豚不識(shí)字；(3) 有些海豚是很聰明的。請(qǐng)用歸結(jié)演繹推理證明：有些很聰明的人并不識(shí)字

12、。解：第一步，先定義謂詞， 設(shè) R(x)表示 x 是能閱讀的；K(y)表示 y 是識(shí)字的；W(z)表示 z 是很聰明的；第二步，將已知事實(shí)和目標(biāo)用謂詞公式表示出來(lái)能閱讀的人是識(shí)字的：(X)(R(X)TK(x) 海豚不識(shí)字：(y)(?K (y)有些海豚是很聰明的：(z) W(z) 有些很聰明的人并不識(shí)字：(X)( W(z)A? K(X)第三步，將上述已知事實(shí)和目標(biāo)的否定化成子句集：? R(X) V K(X)?K(y)W(z)? W(z) V K(X)第四步，用歸結(jié)演繹推理進(jìn)行證明NIL9 對(duì)子句集：P V Q, Q V R, RV W, RV P,WVQ, Q V R 用線性輸入策略是否可證明該

13、子句集的不可滿足性？解：用線性輸入策略不能證明子句集P V Q, Q V R, RV W,RVP, WV Q, QV R 的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過(guò)程。整理文檔10 設(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)。試說(shuō)明這樣一個(gè)系統(tǒng)怎樣才能回答問(wèn)題：“高山俱樂(lè)部中有沒(méi)有一個(gè)成員，他是一個(gè)

14、登山運(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) 將問(wèn)題用謂詞表示出來(lái) “張、王和李都屬于高山協(xié)會(huì)A(Zhang) A A(Wang) A A(Li) 高山協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)動(dòng)員，就是登山運(yùn)動(dòng)員(x)(A(x) A ?S(x) (x) 高山協(xié)會(huì)中不喜歡雨的運(yùn)動(dòng)員是登山運(yùn)動(dòng)員(x)(?L(x, Rai n)C(x)高山協(xié)會(huì)中不喜歡雪的運(yùn)動(dòng)員不是滑雪運(yùn)動(dòng)員(x)(?L(x, Snow)-S?x)王不喜歡張所喜歡的一切東西(y)( L(Zhang,

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

16、(?L(x, Rai n) C(x)(x)(?L(x, Snow)-S?x)(y) ( L(Zhang, y)- ? L(Wang ,y)(y)(? L( Zha ng, y)- L(Wa ng, y)(5) 把已知事實(shí)、規(guī)則和目標(biāo)化成推理所需要的形式事實(shí)已經(jīng)是文字的合取形式：fi: A(Zhang) A A(Wang) A A(Li)f2： L (Zhang , Rain) A L(Zhang , Snow)將規(guī)則轉(zhuǎn)化為后件為單文字的形式：A： A(x) A ?S(x) (x)a: ?L(x, Rai n)C整理文檔3： ?L(x, Snow) ?x)4： L(Zha ng, y) ? L(Wa ng ,y)5： ? L( Zhang, y) L(Wang , y)將目標(biāo)公式轉(zhuǎn)換為與/或形式? A(x)