人工智能參考答案

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

2、)(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)VR(x,z)P(x,y)AQ(x,y)已經(jīng)是合解：(1)由于(x)(y)(P(x,y)AQ(x,y)已經(jīng)是Skolem標(biāo)準(zhǔn)型，且取范式，所以可直接消去全稱量詞、合取詞，得P(x,y),Q(x,y)再進(jìn)行變元換名得子句集：S=P(x,y),Q(u,v)(2)對謂詞公式(x)(y)(P(x,y盧Q(x,y),先消去連接詞一得:(x)(y)(P(x,y)VQ(x,y)此公式已為Skolem標(biāo)準(zhǔn)型。再消去全稱量詞得子句集：S=P(x,yyQ(x,y)一得:(3

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

4、(x,y)VQ(x,y)VR(x,f(x,y)此公式已為Skolem標(biāo)準(zhǔn)型。最后消去全稱量詞得子句集：S=P(x,yyQ(x,y)VR(x,f(x,y)3-13判斷下列子句集中哪些是不可滿足的：(1) PVQ,Q,PP(2) PVQ,PVQ,PVQ,PVQ(3) P(y)VQ(y),P(f(x)VR(a)(4) P(x)VQ(x),P(y)VR(y),P(a),S(a),S(Z)R(z)(5) P(x)VQ(f(x),a),P(h(y)VQ(f(h(y),a)VP(z)(6) P(x)VQ(x)VR(x),P(y)VR(y),Q(a),R(b)解：(1)不可滿足，其歸結(jié)過程為：PVQQNIL(

5、2)不可滿足，其歸結(jié)過程為:(3)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(4)不可滿足，其歸結(jié)過程略(5)不是不可滿足的，原因是不能由它導(dǎo)出空子句。(6)不可滿足，其歸結(jié)過程略對下列各題分別證明G是否為Fi,F2,nF勺邏輯結(jié)論:(1) F:(x)(y)(P(x,y)G:(y)(x)(P(x,y)(2) F:(x)(P(x)A(Q(a)VQ(b)G:(x)(P(x)AQ(x)(3) F:(x)(y)(P(f(x)A(Q(f(y)G：P(f(a)AP(y)AQ(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)

6、 Fi：(x)(P(x尸(Q(x)AR(x)F2：(x)(P(x)AS(x)G：(x)(S(x八R(x)解：(1)先將F和G化成子句集：S=P(a,b),P(x,b)再對S進(jìn)行歸結(jié)：所以，G是F的邏輯結(jié)論(2)先將F和G化成子句集由F得：Si=P(x),(Q(a)VQ(b)由于G為：(x)(P(x)AQ(x),即(x)(P(x)VQ(x),可得：S2=P(x)VQ(x)因此，擴(kuò)充的子句集為：S=P(x)(Q(a)VQ(b),P(x)VQ(x)再對S進(jìn)行歸結(jié)：所以，G是F的邏輯結(jié)論同理可求得(3)、(4)和(5),其求解過程略。設(shè)已知：(1)如果x是y的父親，y是z的父親，則x是z的祖父；(2)

7、每個(gè)人都有一個(gè)父親。使用歸結(jié)演繹推理證明：對于某人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)VF(y,z)VGF(x,z)P(r)VF(s,r)P(u)GF(v,u)對上述擴(kuò)充的子句集，其歸結(jié)推理過程如下：由于導(dǎo)出了空子句，故結(jié)論得證。假設(shè)張被盜，公安局派出5個(gè)人去調(diào)查。案情分析時(shí)，貞察員A說：“

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

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

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

11、x)K(y)W(z)W(z)VK(x)第四步，用歸結(jié)演繹推理進(jìn)行證明對子句集：PVQ,QVR,R/W,RVPWVQ,QVR用線性輸入策略是否可證明該子句集的不可滿足性解：用線性輸入策略不能證明子句集PVQ,QVR,RVW,RVP,WVQ,QVR的不可滿足性。原因是按線性輸入策略，不存在從該子句集到空子句地歸結(jié)過程。對線性輸入策略和單文字子句策略分別給出一個(gè)反例，以說明它們是不完備的。分別說明正向、逆向、雙向與/或形演繹推理的基本思想。設(shè)已知事實(shí)為(PVQ)AR)V(SA(TVU)F規(guī)則為Sf(XAY)VZ試用正向演繹推理推出所有可能的子目標(biāo)。解：先給出已知事實(shí)的與/或樹，再利用F規(guī)則進(jìn)行推理，

12、其規(guī)則演繹系統(tǒng)如下圖所示。由該圖可以直接寫出所有可能的目標(biāo)子句如下：PVQVTVUPVQVXVZPVQVYVZRVTVURVXVZRVYVZ設(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)員。王不喜歡張所喜歡的一切東西，而喜歡張所不喜歡的一切東西。張喜歡雨和雪?！痹囉弥^詞公式集合表示這段知識，這些謂詞公式要適合一個(gè)逆向的基于規(guī)則的演繹系統(tǒng)。試說明這樣一個(gè)系統(tǒng)怎樣才能回答問題：“高山俱樂部中有沒有一個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員，但不是一個(gè)滑雪運(yùn)動(dòng)員”解：(1)先定義謂詞A(x)表示x是高山協(xié)

13、會(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)AA(Wang)AA(Li)高山協(xié)會(huì)的每個(gè)成員不是滑雪運(yùn)動(dòng)員，就是登山運(yùn)動(dòng)員(x)(A(x)AS(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)王喜歡張所不喜歡的一切東西(y)(L(Zhang,y戶L(Wang,y)張喜歡雨和雪L(Zhang,Rain八L(Zhan

14、g,Snow)(3)將問題要求的答案用謂詞表示出來高山俱樂部中有沒有一個(gè)成員，他是一個(gè)登山運(yùn)動(dòng)員，但不是一個(gè)滑雪運(yùn)動(dòng)員(x)(A(x)-C(x)AS(x)(4)為了進(jìn)行推理，把問題劃分為已知事實(shí)和規(guī)則兩大部分。假設(shè)，劃分如下:已知事實(shí)：A(Zhang)AA(Wang)AA(Li)L(Zhang,Rain八L(Zhang,Snow)規(guī)則：(x)(A(x)AS(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)是文字的合取形式：fi:A(Zhang)AA(Wang)AA(Li)f2：L(Zhang,Rain)L(Zhang,Snow)將規(guī)則轉(zhuǎn)化為后件為單文字的形式：門：A(x)AS(x戶C(x)L(x,Rain戶C(x)L(x,Snow戶S(x)":L(Zhang,y戶L(Wang,y)L(Zhang,y戶L(Wang,y)將目標(biāo)公式轉(zhuǎn)換為與/或形式A(x)V(C(x