人工智能教程習題及答案習題參考解答

第三章確定性推理方法習題參考解答3.1 練習題3TF的命題。什么是謂詞？什么是謂詞個體及個體域？函數(shù)與謂詞的區(qū)別是什么？謂詞邏輯和命題邏輯的關系如何？有何異同？什么是謂詞的項？什么是謂詞的階？請寫出謂詞的一般形式。D={1,2},試給出謂詞公式(x)(y)(P(x,y)Q(x,y))的所有解釋，并且對每一種解釋指出該謂詞公式的真值。對下列謂詞公式分別指出哪些是約束變元？哪些是自由變元？并指出各量詞的轄域。(1)(x)(P(x,y)(y)(Q(x,y)R(x,y)))⑵(z)(y)(P(z,y)Q(z,x))R(u,v)⑶(x)(~P(x,f(x))(z)(Q(x,z)~R(x,z)))(4)(z)((y)((t)(P(z,t)Q(y,t))R(z,y))5(z)(y)(P(z,y)(z)((y)(P(z,y)Q(z,y)(z)Q(z,y))))什么是謂詞公式的永真性、永假性、可滿足性、等價性及永真蘊含?什么是置換？什么是合一？什么是最一般的合一?

判斷以下公式對是否可合

P(x,y)一；若可合一，則求出最一般的合一:P(y,x)(1) P(a,b),(2) P(f(z),b),

P(y,f(a))P(x,f(a),f(b))⑶P(f(x),y),(4)P(f(y),y,x),(5)P(x,y),

P(y,x)SKOLEM范式的形式什么是子句？什么是子句集？請寫出求謂詞公式子句集的步驟謂詞公式與它的子句集等值嗎？在什么情況下它們才會等價？把下列謂詞公式分別化為相應的子句集：(1) (z)(y)(P(z,y)Q(z,y))(2) (x)(y)(P(x,y)Q(x,y))⑶(x)(y)(P(x,y)(Q(x,y)R(x,y)))(4) (x)(y)(z)(P(x,y)Q(x,y)R(x,z))(5)(x)(y)(z)(u)(v)(w)(P(x,y,z,u,v,w)(Q(x,y,z,u,v,w)?R(x,z,w)))判斷下列子句集中哪些是不可滿足的：S{?PQ,?Q,P,?P}S{PQ,?PQ,P?Q,?P?Q}(3)S{P(y)Q(y),?P(f(x))R(a)}(4)S{?P(x)Q(x)，?P(y)R(y),P(a),S(a),?S(z)?R(z)}(5)S{?P(x)?Q(y)?L(x,y),P(a),?R(z)L(a,z),R(b),Q(b)}(6)S{?P(x)Q(f(x),a),?P(h(y))Q(f(h(y)),a)?P(z)}(7)S{P(x)Q(x)R(x),~P(y)R(y),?Q(a),?R(b)}1.1S{P(x)Q(x)，?Q(y)R(y),?P(z)Q(z),?R(u)}HerbrandfHH域？什么是原子集？如何求子句集的原子集？HDIHI*呢？S={P(z)VQ(z),R(f(t))},SD={1,2}H域和原子集的定義：H={a,f(a),f(f(a)),…}A={P(a),Q(a),R(a),P(f(a)),Q(f(a)),R(f(a)),…}如果設I是D上的解釋，并作如下的設定1:f(1)f(2)P(1)P(2)Q(1)Q(2)R(1)R(2)22TFFTFT請構造H域上的一個解釋I*與I相對應，且使S|I*=TORobinson的歸結原理有何意義？其基本思想是什么？請寫出應用歸結原理進行定理證明的步驟。GFi,F2,…，F(xiàn)n的邏輯結論⑴Fi:(x)(y)P(x,y)G：(y)(x)P(x,y)⑵Fi:(x)(P(x)(Q(a)Q(b)))G：(x)(P(x)Q(x))⑶Fi:(x)(y)(P(f(x))Q(f(b)))G:P(f(a))P(y)Q(y)⑷Fi:(x)(P(x) (y)(Q(y)~L(x,y)))F2：(x)(P(x)(y)(R(y)L(x,y)))

(Q(x)R(x)))S(x))R(x))G：(x)(R(x)~Q(x))(6)Fl:(z)(A)F3:(z)(E(x)~B(z))G：(z)(E(z)C(z))

(y)(D(z,y)C(y)))證明：(y)(Q(y)(B(y)C(y)))(y)(Q(y)D(y))(y)(D(y)C(y))某單位招聘工作人員，張三、李四、王五三人應試，經(jīng)面試后單位有如下想法:(2)如果錄取李四，則一定錄取王五。三人中至少要錄取一人。求證：王五一定會被單位錄取。蓄錢。請寫出利用歸結原理求解問題答案的步驟。應用歸結原理求解下列問題：設張三、李四和王五三人中有人從不說真話，也有人從不說假話。某人向這三人分別提出同一個問題:誰是說假話者？張三答：“李四和王五都是說假話者”；李四答：“張三和王五都是說假話者"；王五答：“張三和李四中至少有一個說假話者”。求誰是說假話者，誰是說真話者？xyxy的老師。請問李偉的老師是誰？什么是完備的歸結控制策略？有哪些歸結控制策略是完備的？設已知：(1)能閱讀的人是識字的。(2)海豚不識字。(3)有些海豚是很聰明的。用輸入歸結策略證明：有些很聰明的人并不識字。用輸入歸結策略是否可證明下列子句集的不可滿足性？S={PVQ,QVR,RVW,?RV?P,?WV?Q,?QV?R}習題參考解答3.23.3 答：(略)3.4 答：(略)3.5 答：(略)3.6 答：(略)解：在謂詞公式(x)(y)(P(x,y)Q(x,y))中沒有包括個體常量和函數(shù)，所以，可以直接為謂詞指派真值。設：P(1,1)=T,P(1,2)=F,P(2,1)=T,P(2,2)=FQ(1,1)=T,Q(1,2)=F,Q(2,1)=T,Q(2,2)=F在這種解釋下，對某一個x(x=1或x=2)對所有的y(即y=1或y=2)都不能使P(x,y)的真值為T,所以，在此解釋下，P(x,y)的真值為F。同理，Q(x,y)的真值也為F。根據(jù)謂詞邏輯真值表可知：在該解釋下，上述謂詞公式的真值為To上述謂詞公式在D={1,2}上共有256種解釋，這里不再一一列出，讀者可自己列出其中的幾個，并求出其真值。解：P(x,y),Q(x,y)R(x,y)xQ(x,y),R(x,y)y是約束變元。P(x,y)y是自由變元。量詞xy的轄域是(Q(x,y)R(x,y))。z和y是約束變元。x,u,v是自由變元。z和yP(z,y)Q(z,x)。x和z均是約束變元。沒有自由變元。x的轄域是整個公式，zQ(x,z)~R(x,z)。z、y和t均是約束變元。沒有自由變元。z和y的轄域是整個公式，tP(z,t)Q(y,t)。(5)zy,z和一個y都可看成是另外的變量，因此，可作變元替換將公式變換為：(z)(y)(P(z,y)(z')((y1)(P(z',y')Q(z',y')(z'')Q(z'',y'))))z、y、z'、y'、z'五個變元。z和y的轄域是整個公式，z'y'的轄P(z',y')Q(z',y')(z'')Q(z'',y'),z'Q(z'',y')3.7答：(略)3.8答：(略)解：P(a,b)P(x,y)是可合一的。(T={a/x,b/y}P(f(z),b)P(x,y)是可合一的。b={f(z)/x,b/y}P(f(x),y)P(y,f(a))b={f(a)/y,a/x}P(f(y),y,x)P(x,f(a),f(b))是不可合一的。P(x,y)P(y,x)是可合一的。(T={y/x}或={x/y}答：范式就是標準型。謂詞演算中，一般有兩種范式，一種叫前束形范式，另一種叫斯克林(Skolem)范式。一個謂詞公式，如果它的所有量詞均非否定地出現(xiàn)在公式的最前面，且束形范式。它的一般形式是(QIX1)(Q2X2)…(Qxn)M(x1,x2,…，x)其中，Qi(i=1,2,…n)是存在量詞或全稱量詞，而母式M(xi,X2,…,x)不再含有量詞。從前束形范式中消去全部存在量詞所得到的公式稱為Skolem標準型，它的一般形式是(Xl)(X2)??(Xn)M(X1,X2，…,Xi)答：連接詞的謂詞公式叫做原子或原子公式。由子句構成的集合稱為子句集。求謂詞公式G的子句集的步驟如下：G中的蘊涵(-)和雙條件符號()，以?AVBA-B,以(AAB)V(?AA?B)替換AB。減少否定符號(?)的轄域，使否定符號“?”最多只作用到一個謂詞上。重新命名變元名，使所有的變元的名字均不同，并且自由變元及約束變元亦不同。消去存在量詞。這里分兩種情況，一種情況是存在量詞不出現(xiàn)在全稱量詞的轄域一種情況是，存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如，(X1)(X2)???(Xn)(y)P(X1,X2，…，Xi,y)yXIX2,…，xnSkolemf(x1,X2,…K)y即可將存在量詞y消去，得到：(X1)(X2)???(Xn)P(X1,X2，…，X,f(x1,X2,???,x))個部分。合取。消去全稱量詞。對變元進行更名，是不同子句中的變元不同名。(1) A,將各子句寫成子居積合的形式。3.12答：(略)解：因為(z)(y)(P(z,y)Q(z,y))Skolem標準型，P(z,y)Q(z,y)已是合取范式，以逗號代替，得子句集：S={P(z,y),Q(z,y)}首先將謂詞公式(x)(y)(P(x,y)Q(x,y))Skolem標準型：(x)(y)(~P(x,y)Q(x,y))消去全稱量詞，并將母式化為子句集S={P(x,y)Q(x,y)}首先將謂詞公式(x)(y)(P(x,y)(Q(x,y)R(x,y)))Skolem標準型：第一步：消去號(x)(y)(P(x,y)(~Q(x,y)R(x,y)))Skolemf(x)y(x)(P(x,f(x))~Q(x,f(x))R(x,f(x)))第三步：消去全稱量詞，并將母式化為子句集S={P(x,f(x))~Q(x,f(x))R(x,f(x))}首先將謂詞公式(x)(y)(z)(P(x,y)Q(x,y)R(x,z))Skolem標準型:第一步：消去號(x)(y)(z)(~P(x,y)Q(x,y)R(x,z))Skolemf(x,y)z(x)(y)(~P(x,y)Q(x,y)R(x,f(x,y)))第三步：消去全稱量詞，并將母式化為子句集S={~P(x,y)Q(x,y)R(x,f(x,y))}Skolem標準型：x,y,a,b(z)(u)(v)(w)(P(a,b,z,u,v,w)(Q(a,b,z,u,v,w)~R(a,z,w)))u,uzSkolemu=f(z)(z)(v)(w)(P(a,b,z,f億),v,w)(Q(a,b,z,f億),v,w)~R(a,z,w)))w,wz和vSkolemw=g(z,v)(z)(v)(P(a,b,z,f(z),v,g(z,v))(Q(a,b,z,f(z),v,g(z,v))~R(a,z,g(z,v))))第三步：消去全稱量詞，并將母式化為合取范式，再化為子句集S={P(a,b,z,f(z),v,g(z,v)),Q(a,b,z,f(z),v,g(z,v))~R(a,z,g(z,v))}解S{~PQ,~Q,P,~P}進行歸結推理?PQ?QP-PNIL3),4)歸結所以，該子句集是不可滿足的。同理，可以推知第(2)、(4)、(5)、(8)小題的子句集也是不可滿足的，因為它們都可以歸結出空子句。答：引入Herbrand理論的目的是為了簡化對謂詞公式不可滿足性的證明。對于一個謂詞公足性的判定仍然是困難的，因為要判斷子句集的不可滿足性就要對子句集中的每D的任意性以及解釋個數(shù)的無限性，這實際上是使謂詞公式在該特殊域上是不可滿足的，就能保證它在任一域上也是不可滿足的呢？HerbrandHerbrand域(H域)。只要對H域上的所有解釋進行判定，即可得知謂詞公式是否是不可滿足的。HHGS,HG或子句集SHerbrand域，簡稱H域。令H0是SSaD,規(guī)定H0={a}。令Hi+1=HiU{Sf(t1,…,t)的元素}其中f(t1,…用是出現(xiàn)于G中的任一函數(shù)符號，而t1,…，tn是Hi中的元素。i=0,1,2,…。答：下列集合稱為子句集S的原子集：A={所有形如P(ti,t2,…&的元素}Stl,t2,…，tn則是S的H答：如果子句集S的原子集為A,則對A中各元素的真假值的一個具體設定都是S的一個H解釋。用域DIHI*(1)S的H域和原子集ADI,HH域中有常量符號，可按Da設定某一值。HIA中各元素的取值。這樣，原子集A中的各個元素都得到了一個取值，它就是與D上的解釋I相對應的H域上的解釋I*。解：D={1,2},ID上的解釋，并作如下的設定f(1)f(2)P(1)P(2)Q(1)Q(2)R(1)R(2)22TFFTFT將以上各值代入S,有S|I=T?，F(xiàn)在要構造H域上的一個解釋I*與I相對應，且使SI*=T。依據(jù)DI之規(guī)定，對H域中的每個元素設定相應的值。在Ha,f(a),f(f(a)),…這時，由于aI中并未給出規(guī)定，所以我們要按Da1,21,2都是D的元素)。若a1,I,Hf(a)-f(1)-2f(f(a))-f(2)-2f(f(f(a)))f(2)2再依據(jù)HIAP(a)-P⑴fTQ(a)-Q(1)-FR(a)-R(1)-FP(f(a))-P(2)-FQ(f(a))-Q(2)-TR(f(a))-R(2)-T于是，便得到與D域上解釋I相對應的H域上的解釋I*i：I*i={P(a),?Q(a),?R(a),?P(f(a)),Q(f(a)),R(f(a)),…}同理，若將H中的元素a設成2,我們可以得到與I相對應的另一個H解釋I*2:I*2={?P(a),Q(a),R(a),?P(f(a)),Q(f(a)),R(f(a)),…}*2可以驗證S|I*i=T,S|I=TO解釋I*i、I*2便是所求的與D域上解釋I相對應的H域之解釋。*23.19答：(略)答：設要被證明的定理可用謂詞公式表示為形式A1AA2A…AAn->B,則應用歸結原理進行定理證明的步驟如下：B,并將否定后的公式?B與前提公式集組成如下形式的謂詞公式：G=A1AA2A…AAnA?BGSoS的不可滿足性，從而證明謂詞公式G這就說明對結論B的否定是錯誤的，推斷出定理的成立。解：1(1) F:(x)(y)P(x,y)1G:(y)(x)P(x,y)首先將F1和?G化為子句集1) P(a,b)2) ~P(x,b)然后利用歸結原理進行歸結3) NIL1)2)歸結，d={a/x}所以G是Fi的邏輯結論。(2)Fi和?GFi：(x)(P但(Q(a)Q(b))),由于Fi本身就是Skelom標準型，所以有Si={P(x),Q(a)Q(b)}?G=(x)(?P(x)?Q(x))所以，S2={-P(x)~Q(x)}下面進行歸結P(x)Q(a)Q(b)3) ~P(x)~Q(x)4) -Q(x)1),3)歸結5) Q(b)2),4)b={a/x}6) NIL4),5)歸結(r={b/x}所以G是Fi的邏輯結論。其余各題的證明留給讀者自己練習。證明：第一步：先對結論否定并與前提合并得謂詞公式GG=(y)(Q(y)-(B(y)AC(y)))A(y)(Q(y)AD(y))A?(y)(D(y)AC(y))第二步：將公式G化為子句集，可將G看作三項的合取，對每一項分別求子句集Gi：(y)(Q(y)-(B(y)AC(y)))=(y)(?Q(y)V(B(y)AC(y)))=(y)((?Q(y)VB(y))A(?Q(y)VC(y)))所以，Si={(?Q(y)VB(y)),?Q(y)VC(y)}。G2：(y)(Q(y)AD(y))。?B:?(y)(D(y)AC(y))=(y)(?D(y)V?C(y))所以，SB={?D(y)V?C(y)}。從而得公式G的子句集：S=SiUS2USB={(?Q(y)VB(y)),?Q(y)VC(y),Q(a),D(a),?D(y)V?C(y)}第三步：使用歸結原理，對子句集S進行歸結。Q(a)D(a)?D(y)V?C(y)(6)C(a)(2)與(3)歸結b={a/y}(7)?C(a)(4)與(5)歸結b={a/y}(8)NIL(6)與(7)歸結由此得出子句集S是不可滿足的，因而公式G也是不可滿足的，從而命題得證。證明：第一步：定義謂詞，并將待證明的問題的前提條件和邏輯結論用謂詞公式表示出來。)定義謂詞和常量：Matr(x)xZ表不'張三，L表不'李四，W表不'王五。)將前提及要證的問題表示成謂詞公式：Matr(Z)A~Matr(L)-Matr(W)Matr(L).Matr(W)Matr(Z)VMatr(L)VMatr(W)把要求證的問題否定，并用謂詞公式表示出來：d)?Matr(W)第二步：將上述公式化成子句集。?Matr(Z)VMatr(L)VMatr(W)?Matr(L)VMatr(W)Matr(Z)VMatr(L)VMatr(W)?Matr(W)第三步：利用歸結原理對上面的子句集中的子句進行歸結。Matr(L)VMatr(W)1)3)歸結Matr(W)2)5)歸結NIL4)6)歸結所以，王五一定會被錄取。證法一：定義謂詞：設：Save(x):表示x儲蓄錢；Interest(x)x獲得利息。將前提表示成謂詞公式：(x)(Save(x)Interest(x))把要求證的問題用謂詞公式表示出來：(y)(?Interest(y)~Save(y))第二步：將前提和要求證的問題之否定化成子句集。求前提子句集：(x)(Save(x)Interest(x))(x)(~Save(x)Interest(x))前提的子句集：S1={?Save(x)Interest(x)}求結論之否定子句集：~(y)(~Interest(y)~Save(y))~(y)(Interest(y)~Save(y))(y)(~Interest(y)Save(y))結論之否定子句集：S2={?Interest(y),Save(y)}第三步：利用歸結原理對上面的子句集中的子句進行歸結~Save(x)Interest(x)~Interest(y)⑶Save(y)(4)Save(y)(1),(2)歸結={x/y}(5)NIL(3),(4)歸結證畢。證法二：定義謂詞：設：Save(x,y)：表示x儲蓄y;Money(y):y是錢；Interest(y)y是利息；Obtain(x,y):x獲彳y。將前提表示成謂詞公式：(x)((y)(Money(y)Save(x,y))(u)(Interest(u)Obtain(x,u)))把要求證的問題用謂詞公式表示出來：(x)(~(u)(Interest(u)Obtain(x,u))~(y)(Money(y)Save(x,y)))第二步：將前提和要求證的問題之否定化成子句集。求前提子句集：(x)(~(y)(Money(y)Save(x,y))(u)(Interest(u)Obtain(x,u)))(x)((y)(~Money(y)~Save(x,y))(u)(Interest(u)Obtain(x,u)))設skolem函數(shù)為u=f(x),則:前提的子句集：S1={~Money(y)~Save(x,y)Interest(f(x)),~Money(y)~Save(x,y)Obtain(x,f(x))}求結論之否定子句集：~(x)(~(u)(Interest(u)Obtain(x,u))~(y)(Money(y)Save(x,y)))~(x)((u)(Interest(u)Obtain(x,u))~(y)(Money(y)Save(x,y)))(x)((u)(~Interest(u)~Obtain(x,u))(y)(Money(y)Save(x,y)))設skolem函數(shù)為y=g(x),則上式變?yōu)椋?x)(u)((~Interest(u)~Obtain(x,u))(Money(g(x))Save(x,g(x))))結論之否定子句集：S2={~Interest(u)~Obtain(x,u),Money(g(x)),Save(x,g(x))}第三步：利用歸結原理對上面的子句集中的子句進行歸結~Money(y)~Save(x,y)Interest(f(x))~Money(y)~Save(x,y)Obtain(x,f(x))~Interest(u)~Obtain(x,u)Money(g(x))Save(x,g(x)) ~Save(x,y)~Obtain(x,f(x))(6) ~Money(y) (1),(3)歸結{f(x)/u}~Money(y)~Save(x,y) (2),(6)歸結~Money(g(x))(5),(7) b={g(x)/y}NIL(4),(8)歸結證畢。答：利用歸結原理求取問題答案的步驟如下:把已知前提條件用謂詞公式表示出來，并化成相應的子句集，設該子句集的名字為S。SIANSWER構成析取式。謂詞ANSWER是一個專為求解問題而設置的謂詞，其變量必須與問題公式的變量完全一■致。ANSWERSi合并構SoSANSWER中的變元。ANSWER,ANSWER謂詞中。解：第一步：將已知條件用謂詞公式表示出來，并化成子句集，那么要先定義謂詞。定義謂詞和常量：設P(x)表小x說真tIfoZ表小張三，L表小李四，W表小王五。將已知事實用謂詞公式表示出來。若張三說的是真話，則有P(Z)f?P(L)A?P(W)若張三說的是假話，則有?P(Z)-P(L)VP(W)對李四和王五說的話做同樣的處理，可得：P(L)-?P(Z)A?P(W)?P(L)-P(Z)VP(W)P(W)-?P(Z)V?P(L)?P(W)-P(Z)AP(L)?P(Z)V?P(L)?P(Z)V?P(W)P(Z)VP(L)VP(W)?P(W)V?P(Z)V?P(L)P(W)VP(Z)第二步：把問題用謂詞公式表示出來，并將其否定與謂詞ANSWER作析取。設u是說真話者，則有：P(u)。將其否定與ANSWER作析取，得：G:?P(u)VANSWER(u)將上述公式G化為如下的子句，并將其合并到So?P(u)VANSWER(u)}第三步：應用歸結原理對上述子句集進行歸結?P(Z)VP(W)1)7)歸結10) P(W)6)9)歸結11) ANSWER(W)8)10)b={W/u}第四步：得到的歸結式ANSWER(W),答案即在其中，u=W,所以，求得王五是說真ANSWER(Z)和ANSWER(L)來,說明張三和李四不P(Z)或?P(L)作為要證明的結論，將它的否定之子句并入前面的子句集1)—7),并進行歸結推理，推出空子句，從而證明假設的正確性，即張三和李四是說假話者。解：第一步：定義謂詞，并將已知條件用謂詞公式表示出來，并化成子句集。 定義謂詞和常量：