【正文】 Default：male Age：Unit（Years）Telephone：Home Unit（Number）Mobile Unit（Number） 教師框架Frame Teachers AKOTeachersStudents Major：Unit（MajorName） Lectures：Unit（CourseName） Field：Unit（FieldName） Project ：Area（National，Provincial，Other） Default：Provincial Paper：Area（SCI，EI，Core，General） Default：Core 學生框架Frame Students AKO TeachersStudents Major：Unit（MajorName） Classes：Unit（ClassesName） Degree：Area（doctor，mastor, bachelor） Default：bachelor 第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) 可合一，其最一般和一為：σ={a/x, b/y}。(2) 可合一，其最一般和一為：σ={y/f(x), b/z}。(3) 可合一，其最一般和一為：σ={ f(b)/y, b/x}。(4) 不可合一。(5) 可合一，其最一般和一為：σ={ y/x}。 把下列謂詞公式化成子句集：(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))已經是Skolem標準型，且P(x, y)∧Q(x, y)已經是合取范式，所以可直接消去全稱量詞、合取詞，得 { P(x, y), Q(x, y)} 再進行變元換名得子句集： S={ P(x, y), Q(u, v)} (2) 對謂詞公式(x)(y)(P(x, y)→Q(x, y))，先消去連接詞“→”得：(x)(y)(172。P(x, y)∨Q(x, y))此公式已為Skolem標準型。 再消去全稱量詞得子句集： S={172。P(x, y)∨Q(x, y)} (3) 對謂詞公式(x)(y)(P(x, y)∨(Q(x, y)→R(x, y)))，先消去連接詞“→”得：(x)(y)(P(x, y)∨(172。Q(x, y)∨R(x, y)))此公式已為前束范式。再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x)(P(x, f(x))∨172。Q(x, f(x))∨R(x, f(x)))此公式已為Skolem標準型。 最后消去全稱量詞得子句集： S={P(x, f(x))∨172。Q(x, f(x))∨R(x, f(x))} (4) 對謂詞(x) (y) (z)(P(x, y)→Q(x, y)∨R(x, z))，先消去連接詞“→”得：(x) (y) (z)(172。P(x, y)∨Q(x, y)∨R(x, z))再消去存在量詞，即用Skolem函數(shù)f(x)替換y得：(x) (y) (172。P(x, y)∨Q(x, y)∨R(x, f(x,y)))此公式已為Skolem標準型。 最后消去全稱量詞得子句集：S={172。P(x, y)∨Q(x, y)∨R(x, f(x,y))}313 判斷下列子句集中哪些是不可滿足的：(1) {172。P∨Q, 172。Q, P, 172。P}(2) { P∨Q , 172。P∨Q, P∨172。Q, 172。P∨172。Q }(3) { P(y)∨Q(y) , 172。P(f(x))∨R(a)}(4) {172。P(x)∨Q(x) , 172。P(y)∨R(y), P(a), S(a), 172。S(z)∨172。R(z)}(5) {172。P(x)∨Q(f(x),a) , 172。P(h(y))∨Q(f(h(y)), a)∨172。P(z)}(6) {P(x)∨Q(x)∨R(x) , 172。P(y)∨R(y), 172。Q(a), 172。R(b)} 解：(1) 不可滿足，其歸結過程為：172。P∨Q172。Q172。PPNIL(2) 不可滿足，其歸結過程為：P∨Q172。P∨P∨172。Q172。P∨172。Q172。QNIL(3) 不是不可滿足的，原因是不能由它導出空子句。(4) 不可滿足，其歸結過程略(5) 不是不可滿足的，原因是不能由它導出空子句。(6) 不可滿足，其歸結過程略 對下列各題分別證明G是否為F1,F2,…,Fn的邏輯結論：(1) F: (x)(y)(P(x, y)G: (y)(x)(P(x, y)(2) F: (x)(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()))F2: (x) (P(x)∧(y)(R(y)→L()))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和172。G化成子句集： S={P(a,b), 172。P(x,b)} 再對S進行歸結：172。P(x,b)P(a,b)NIL {a/x} 所以，G是F的邏輯結論(2) 先將F和172。G化成子句集由F得：S1={P(x)，(Q(a)∨Q(b))}由于172。G為：172。 (x) (P(x)∧Q(x))，即 (x) (172。 P(x)∨172。 Q(x))，可得： S2={172。 P(x)∨172。 Q(x)}因此，擴充的子句集為：S={ P(x)，(Q(a)∨Q(b))，172。 P(x)∨172。 Q(x)} 再對S進行歸結：Q(a)∨Q(b)Q(a)172。 P(x)∨172。 Q(x)172。 P(a)P(x)NILQ(a)∨Q(b) {a/b}172。 P(x)∨172。 Q(x)Q(a){a/x}172。 P(a)P(x) {a/x}NIL 所以，G是F的邏輯結論 同理可求得(3)、(4)和(5)，其求解過程略。 設已知：(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)∧F(y,z))→GF(x,z)) F2：(y)(P(x)→F(x,y)) 求證結論G：(u) (v)( P(u)→GF(v,u)) 然后再將F1，F(xiàn)2和172。G化成子句集： ① 172。F(x,y)∨172。F(y,z)∨GF(x,z)② 172。P(r)∨F(s,r) ③ P(u) ④ 172。GF(v,u)) 對上述擴充的子句集，其歸結推理過程如下：172。F(x,y)∨172。F(y,z)∨GF(x,z)172。GF(v,u)172。F(x,y)∨172。F(y,z)172。P(r)∨F(s,r)172。F(y,z)∨172。P(y)172。P(r)∨F(s,r)172。P(y)∨172。P(z)172。P(y)P(u)NIL {x/v,z/u}{x/s,y/r}{y/s,z/r} {y/z} {y/u} 由于導出了空子句，故結論得證。 假設張被盜，公安局派出5個人去調查。案情分析時，貞察員A說：“趙與錢中至少有一個人作案”，貞察員B說：“錢與孫中至少有一個人作案”，貞察員C說：“孫與李中至少有一個人作案”，貞察員D說：“趙與孫中至少有一個人與此案無關”，貞察員E說：“錢與李中至少有一個人與此案無關”。如果這5個偵察員的話都是可信的，使用歸結演繹推理求出誰是盜竊犯。解：(1) 先定義謂詞和常量設C(x)表示x作案，Z表示趙，Q表示錢，S表示孫，L表示李(2) 將已知事實用謂詞公式表示出來趙與錢中至少有一個人作案：C(Z)∨C(Q)錢與孫中至少有一個人作案：C(Q)∨C(S)孫與李中至少有一個人作案：C(S)∨C(L)趙與孫中至少有一個人與此案無關：172。 (C (Z)∧C(S))，即 172。C (Z) ∨172。C(S)錢與李中至少有一個人與此案無關：172。 (C (Q)∧C(L))，即 172。C (Q) ∨172。C(L)(3) 將所要求的問題用謂詞公式表示出來，并與其否定取析取。設作案者為u，則要求的結論是C(u)。將其與其否)取析取，得：172。 C(u) ∨C(u)(4) 對上述擴充的子句集，按歸結原理進行歸結，其修改的證明樹如下：C(Z)∨C(Q)172。C (Z) ∨172。C(S)C(Q)∨172。C(S)C(Q)∨C(S)C(Q)172。C(u)∨C(u)C(Q) {Q/u} 因此，錢是盜竊犯。實際上，本案的盜竊犯不止一人。根據歸結原理還可以得出：C(S)∨C(L)172。C (Q) ∨172。C(L)C(S)∨172。C(Q)C(Q)∨C(S)C(S)172。C(u)∨C(u)C(S)172。C (Q) ∨172。C(L)C(S)∨C(L)C(Q)∨C(S)C(S)∨172。C(Q)172。C(u)∨C(u)C(S) {S/u} C(S) 因此，孫也是盜竊犯。 設有子句集： {P(x)∨Q(a, b), P(a)∨Q(a, b), Q(a, f(a)), P(x)∨Q(x, b)}分別用各種歸結策略求出其歸結式。解：支持集策略不可用，原因是沒有指明哪個子句是由目標公式的否定化簡來的。刪除策略不可用，原因是子句集中沒有沒有重言式和具有包孕關系的子句。單文字子句策略的歸結過程如下：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)用線性輸入策略（同時滿足祖先過濾策略）的歸結過程如下：P(a)∨Q(a, b)P(x)∨Q(a, b)P(x)∨Q(x, b)P(a) {a/x}{a/x}Q(a, f(a))Q(a,b) {b/f(a)}NIL 設已知：(1) 能閱讀的人是識字的；(2) 海豚不識字；(3) 有些海豚是很聰明的。請用歸結演繹推理證明：有些很聰明的人并不識字。解：第一步，先定義謂詞， 設R(x)表示x是能閱讀的；K(y)表示y是識字的；W(z) 表示z是很聰明的；第二步，將已知事實和目標用謂詞公式表示出來能閱讀的人是識字的：(x)(R(x))→K(x))海豚不識字：(y)(172。K (y))有些海豚是很聰明的：(z) W(z)有些很聰明的人并不識字：(x)( W(z)∧172。K(x)) 第三步，將上述已知事實和目標的否定化成子句集： 172。R(x))∨K(x)172。K (y)W(z)172。W(z)∨K(x)) 第四步，