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)解：(1)可合一，其最一般和一為：(T =a/x, b/y。(2) 可合一，其最一般和一為：(T =y/f(x), b/z 。可合一，其最一般和一為：d = f(b)/y, b/x 。(4) 不可合一。(5) 可合一，其最一般和一為：d = y/x 。把下列謂詞公式化成

2、子句集：(1) (x)(y)(P(x,y)AQ(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)解：(1)由于(x)(y)(P(x, y) A Q(x, y)已經是 Skolem 標準型，且 P(x, y) A Q(x, y)已經是合取范式，所以可直接消去全稱量詞、合取詞，得 P(x, y), Q(x, y)再進行變元換名得子句集：S= P(x, y), Q(u, v)(2) 對謂詞公式(x)(y)(P(x, y) -Q(x,

3、 y),先消去連接詞一得:(x)(y)( ? P(x, y) V Q(x, y)此公式已為Skolem 標準型。再消去全稱量詞得子句集：S=? P(x, y) VQ(x, y)(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 函數 f(x) 替換 y 得：(x)(P(x, f(x) V ? Q(x, f(x) V R(x, f(x)此公式已為Skolem 標準型。最后消去全稱量詞得子句集：S=P(x, f(x) V

4、? Q(x, f(x) V R(x, f(x)(4) 對謂詞(x) ( y) (z)(P(x, y)-Q(x, y) V R(x, z)，先消去連接詞”得:(1) ( y) (z)( ? P(x, y) V Q(x, y) V R(x, z)再消去存在量詞，即用Skolem 函數 f(x) 替換 y 得：(2) ( y) ( ? P(x, y) V Q(x, y) V R(x, f(x,y)此公式已為Skolem 標準型。最后消去全稱量詞得子句集：S=? P(x, y) VQ(x, y) V R(x, f(x,y)3-13 判斷下列子句集中哪些是不可滿足的：(3) ? PVQ, ? Q, P,

5、 ? P(4) P VQ , ? PV Q, P V? Q, ? PV ? Q P(y) V Q(y) , ? P(f(x) V R(a)(5) ? P(x) V Q(x) ,? P(y) V Ry), P(a), S(a),? S(z) V ? R(z)(6) ? P(x) VQ(f(x),a) ,? P(h(y) VQ(f(h(y), a ) V? P(z)(7) P(x) V Q(x) V R(x) ,? P(y) V R(y), ? Q(a), ? R(b)解：(1)不可滿足，其歸結過程為:(2)不可滿足，其歸結過程為:(3)不是不可滿足的，原因是不能由它導出空子句。(4)不可滿足，其

6、歸結過程略(5)不是不可滿足的，原因是不能由它導出空子句。(6)不可滿足，其歸結過程略對下列各題分別證明G是否為F1,F2,Fn的邏輯結論:(1) F： (x)(y)(P(x, y)G： (y)(x)(P(x, y)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)

7、A S(x)G: ( x) (S(x) A R(x)解：(1)先將F和？ G化成子句集：S=P(a,b),? P(x,b)再又S進行歸結:a/x所以，G是F的邏輯結論(2)先將F和？ G化成子句集由 F得：Si=P(x) , (Q(a) V Q(b)由于？ G為：？( x) (P(x) AQ(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進行歸結:Q(a) V Q(b)a/xNIL所以，G是F的邏輯結論同理可求得(3)、(4)和(5),其求解過

8、程略。設已知：(1)如果x是y的父親，y是z的父親，則x是z的祖父；(2)每個人都有一個父親。使用歸結演繹推理證明：對于某人u, 一定存在一個人v, v是u的祖父。解：先定義謂詞F(x,y) ： x是y的父親GF(x,z) : x是z的祖父P(x) ： x是一個人再用謂詞把問題描述出來：已知 F1: ( x) ( y) (z)( F(x,y) A F(y,z) 一GF(x,z)F2(y)(P(x)F(x,y)求證結論 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

9、) P(u)? GF(v,u)對上述擴充的子句集，其歸結推理過程如下：? F(x,y) 丫?0JfJJjFMx/v,z/u? F(x,y) ? Jp(r) V F(sx/s,y/r ? F(y,z)?J J?p V F(s? P(y) V ?y/s,z/r? p(yP(u)y/z3/NILy/u由于導出了空子句，故結論得證。假設張被盜，公安局派出 5個人去調查。案情分析時，貞察員 A說：“趙與錢中至少有 一個人作案”，貞察員B說：“錢與孫中至少有一個人作案”，貞察員C說：“孫與李中至少有一 個人作案”，貞察員D說：“趙與孫中至少有一個人與此案無關”，貞察員E說：“錢與李中至少有一個人與此案無關

10、”。如果這5個偵察員的話都是可信的，使用歸結演繹推理求出誰是盜竊犯。解：(1)先定義謂詞和常量設C(x)表小x作案，Z表小趙，Q表小錢，S表小孫，L表小李(2)將已知事實用謂詞公式表示出來趙與錢中至少有一個人作案：C(Z) V C(Q)錢與孫中至少有一個人作案：C(Q)V C(S)孫與李中至少有一個人作案：C(S) V C(L)趙與孫中至少有一個人與此案無關：？(C (Z) AC(S),即？ C (Z) V? C(S)錢與李中至少有一個人與此案無關：？(C (Q) A C(L)，即？ C (Q) V? C(L)(3)將所要求的問題用謂詞公式表示出來，并與其否定取析取。設作案者為u,則要求白結論

11、是 C(u)。將其與其否)取析取，得：? C(u) V C(u)(4)對上述擴充的子句集，按歸結原理進行歸結，其修改的證明樹如下：CC(Q) V ?VC(S)C(uVC(Q/uC(S)C(Q)C(Q) V C(S)C(Z) V C(Q)C(S) V ? C(Q IS/uC(S)因此，孫也是盜竊犯。設有子句集:P(x) V Q(a, b), P(a)Q(a, b),Q(a, f(a),P(x) V Q(x, b)分別用各種歸結策略求出其歸結式。解：支持集策略不可用，原因是沒有指明哪個子句是由目標公式的否定化簡來的。刪除策略不可用，原因是子句集中沒有沒有重言式和具有包孕關系的子句。單文字子句策略的

12、歸結過程如下:a/xb/f(a)Qa用線性輸入策略(同時滿足祖先過濾策略)的歸結過程如下:b/f(a)NIL設已知：(1)能閱讀的人是識字的；(2)海豚不識字；(3)有些海豚是很聰明的。請用歸結演繹推理證明：有些很聰明的人并不識字。解：第一步，先定義謂詞，設R(x)表示x是能閱讀的；K(y)表示y是識字的；W(z)表示z是很聰明的；第二步，將已知事實和目標用謂詞公式表示出來能閱讀的人是識字的：(x)(R(x) - K(x)海豚不識字：(y)( ? K (y)有些海豚是很聰明的：( z) W(z)有些很聰明的人并不識字：(x)( W(z) A?K(x)第三步，將上述已知事實和目標的否定化成子句集

13、：? R(x) V K(x)? k (y)W(z)? W(z) V K(x) 第四步，用歸結演繹推理進行證明? W(z) V K(x)_W億)KWxNIL對子句集：P VQ, QVR, R VW, RV P, W Q, QV R 用線性輸入策略是否可證明該子句集的不可滿足性解：用線性輸入策略不能證明子句集PVQ, QV R, R V W, RV P, W Q, QV R 的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結過程。對線性輸入策略和單文字子句策略分別給出一個反例，以說明它們是不完備的。 分別說明正向、逆向、雙向與/或形演繹推理的基本思想。設已知事實為(P VQ)A R

14、) V(SA(TVU)F 規則為S 一 (XAY)VZ試用正向演繹推理推出所有可能的子目標。解：先給出已知事實的與/或樹，再利用F規則進行推理，其規則演繹系統如下圖所示。由該圖可以直接寫出所有可能的目標子句如下：P V QV T V UPV QVX V ZPV QV YV ZRV TV URV XV ZRV YV Z知(P VQ)/R) V(S/(T VU)設有如下一段知識：“張、王和李都屬于高山協會。該協會的每個成員不是滑雪運動員，就是登山運動員，其 中不喜歡雨的運動員是登山運動員，不喜歡雪的運動員不是滑雪運動員。王不喜歡張所喜歡的 一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪。”試用

15、謂詞公式集合表示這段知識，這些謂詞公式要適合一個逆向的基于規則的演繹系統。試說明這樣一個系統怎樣才能回答問題：“高山俱樂部中有沒有一個成員，他是一個登山運動員，但不是一個滑雪運動員”解：(1)先定義謂詞A(x)表示x是高山協會會員S(x)表示x是滑雪運動員C(x)表示x是登山運動員L(x,y) 表示x 喜歡 y(2)將問題用謂詞表示出來“張、王和李都屬于高山協會A(Zhang) A A(Wang)A A(Li)高山協會的每個成員不是滑雪運動員，就是登山運動員(x)(A(x) A ? S(x) C(x)高山協會中不喜歡雨的運動員是登山運動員(x)( ? L(x, Rain) - C(x)高山協會

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

17、Wang)A A(Li)L(Zhang , Rain) A L(Zhang , Snow)規則：(x)(A(x) A? S(x)-C(x)(x)(? L(x, Rain) -C(x)(x)( ? L(x, Snow) f? S(x)(y)( L(Zhang, y) f ? L(Wang ,y)(y)( ? L(Zhang, y) fL(Wang, y)(5) 把已知事實、規則和目標化成推理所需要的形式事實已經是文字的合取形式:f i: A(Zhang) A A(Wang)A A(Li)f 2： L (Zhang , Rain) A L(Zhang , Snow)將規則轉化為后件為單文字的形式：ri： A(x) A? S(x) C(x)r2： ? L(x, Rain) 一 C(x)r3： ? L(x, Snow) 一？ S(x)r4： L(Zhang, y) 一？ L(Wang ,y)5： ?