【文章內(nèi)容簡介】 (2,2)為T。所以在此解釋下，本題謂詞公式的真值為T。11. 對謂詞指派的真值為：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=T，Q(1,2)=F，Q(2,1)=F，Q(2,2)=T，在此解釋下，x=1時，P(1,1)174。Q(1,1)為T，P(1,2)174。Q(1,2)為F；x=2時，P(2,1)174。Q(2,1)為F，P(2,2)174。Q(2,2)為T。所以在此解釋下，本題謂詞公式的真值為F。12. 對謂詞指派的真值為：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=F，Q(1,2)=T，Q(2,1)=T，Q(2,2)=F，在此解釋下，x=1時，P(1,1)174。Q(1,1)為T，P(1,2)174。Q(1,2)為T；x=2時，P(2,1)174。Q(2,1)為T，P(2,2)174。Q(2,2)為T。所以在此解釋下，本題謂詞公式的真值為T。13. 對謂詞指派的真值為：P(1,1)=F，P(1,2)=T，P(2,1)=T，P(2,2)=F，Q(1,1)=F，Q(1,2)=T，Q(2,1)=F，Q(2,2)=T，在此解釋下，x=1時，P(1,1)174。Q(1,1)為T，P(1,2)174。Q(1,2)為T；x=2時，P(2,1)174。Q(2,1)為F，P(2,2)174。Q(2,2)為T。所以在此解釋下，本題謂詞公式的真值為T。14. 對謂詞指派的真值為：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=T，Q(1,2)=F，Q(2,1)=F，Q(2,2)=T，在此解釋下，x=1時，P(1,1)174。Q(1,1)為T，P(1,2)174。Q(1,2)為F；x=2時，P(2,1)174。Q(2,1)為T，P(2,2)174。Q(2,2)為T。所以在此解釋下，本題謂詞公式的真值為T。15. 對謂詞指派的真值為：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=F，Q(1,2)=T，Q(2,1)=T，Q(2,2)=F，在此解釋下，x=1時，P(1,1)174。Q(1,1)為T，P(1,2)174。Q(1,2)為T；x=2時，P(2,1)174。Q(2,1)為T，P(2,2)174。Q(2,2)為F。所以在此解釋下，本題謂詞公式的真值為F。16. 對謂詞指派的真值為：P(1,1)=F，P(1,2)=T，P(2,1)=F，P(2,2)=T，Q(1,1)=F，Q(1,2)=T，Q(2,1)=F，Q(2,2)=T，在此解釋下，x=1時，P(1,1)174。Q(1,1)為T，P(1,2)174。Q(1,2)為T；x=2時，P(2,1)174。Q(2,1)為T，P(2,2)174。Q(2,2)為T。所以在此解釋下，本題謂詞公式的真值為T。6. 對下列謂詞公式分別指出哪些是約束變元？哪些是自由變元？并指出各量詞的轄域。（1）(x)(P(x,y)218。($y)(Q(x,y)217。R(x,y)))解：(x)的轄域是(P(x,y)218。($y)(Q(x,y)217。R(x,y)))，x是受(x)約束的變元；($y)的轄域的(Q(x,y)217。R(x,y))，y是受($y)約束的變元；沒有自由變元。（2）($z)(y)(P(z,y) 218。Q(z,x)) 218。R(u,v)解：($z)的轄域是(y) (P(z,y) 218。Q(z,x))，z是受($z)約束的變元；(y)的轄域是(P(z,y) 218。Q(z,x))，y是受(y)約束的變元；u、v是自由變元。（3）(x)(~P(x,f(x)) 218。($z)(Q(x,z) 217。~R(x,z)))解：(x)的轄域是(~P(x,f(x)) 218。($z)(Q(x,z) 217。~R(x,z)))，x是受(x)約束的變元；($z)的轄域是(Q(x,z) 217。~R(x,z))，z是受($z)約束的變元；沒有自由變元。（4）(z)(($y)(($t)(P(z,t) 218。Q(y,t))217。R(z,y)))解：(z)的轄域是(($y)(($t)(P(z,t) 218。Q(y,t))217。R(z,y)))，z是受(z)約束的變元；($y)的轄域是(($t)(P(z,t) 218。Q(y,t))217。R(z,y))，y是受($y)約束的變元；($t)的轄域是(P(z,t) 218。Q(y,t))，t是受($t)約束的變元；沒有自由變元。（5）(z)($y)(P(z,y) 218。($z)((y)(P(z,y) 217。Q(z,y) 218。($z)(Q(z,y)))))解：(z)的轄域是($y) (P(z,y) 218。($z)((y)(P(z,y) 217。Q(z,y) 218。($z)(Q(z,y)))))，z是受(z)約束的變元；($y)的轄域是(P(z,y) 218。($z)((y)(P(z,y) 217。Q(z,y) 218。($z)(Q(z,y)))))，y是受($y)約束的變元；($z)的轄域是((y)(P(z,y) 217。Q(z,y) 218。($z)(Q(z,y))))，z是受($z)約束的變元；(y)的轄域是(P(z,y) 217。Q(z,y) 218。($z)(Q(z,y)))，y是受(y)約束的變元；($z)的轄域是(Q(z,y))，z是受($z)約束的變元；沒有自由變元。7. 什么是謂詞公式的永真性、永假性、可滿足性、等價性及永真蘊含？解：永真性：如果謂詞公式P，對個體域D上的任何一個解釋都取得真值T，則稱P在D上是永真的；如果P在每個非空個體域上均永真，則稱P永真。永假性：如果謂詞公式P，對個體域D上的任何一個解釋都取得真值F，則稱P在D上是永假的；如果P在每個非空個體域上均永假，則稱P永假?？蓾M足性：對于謂詞公式P，如果至少存在一個解釋使得公式P在此解釋下的真值為T，則稱公式P是可滿足的。等價性：若對共同的個體域D上的任何一個解釋，謂詞公式P與Q的取值都相同，則公式P和Q在域D上是等價的；如果D是任意個體域，則稱P和Q是等價的。永真蘊含：對于謂詞公式P和Q，如果P174。Q永真，則稱P永真蘊含Q。8. 謂詞的永假性和不可滿足性等價嗎？解：根據(jù)永假性和不可滿足性的定義可知，兩者是等價的。9. 什么是置換？什么是合一？什么是最一般的合一？解：置換是形如｛t1/x1，t2/x2，…，tn/xn｝的一個有限集。其中xi是變量，ti是不同于xi的項（常量，變量，函數(shù)），且xi185。xj（i185。j），i，j=1，2，…，n。設(shè)有公式集｛E1，E2，…，En｝和置換q，使E1q＝E2q＝…＝Enq，便稱E1，E2，…，En是可合一的，用稱q為合一置換。若E1，E2，…，En有合一置換s，且對E1，E2，…，En的任一置換q都存在一個置換l，使得q＝sl，則稱s是E1，E2，…，En的最一般合一置換。10. 寫出最一般合一置換的步驟。解：設(shè)E1，E2兩個謂詞公式，其最一般合一置換算法：（1） 令W=｛E1，E2｝。（2） 令k=0，Wk=W，sk=e；e是空置換，它表示不作置換。（3） 如果Wk只有一個表達(dá)式，則算法停止，sk就是所要求的mgu。（4） 找出Wk的不一致集Dk。（5） 若Dk中存在元素xk和tk，其中xk是變元，tk是項，且xk不在tk 中出現(xiàn)，則置： sk+1=sk{ tk/xk} Wk+1=Wk{ tk/xk} k=k+1　　然后轉(zhuǎn)（3）。（6） 算法終止，W的mgu不存在。11. 判斷以下公式對是否可合一；若可合一，則求出最一般的合一。（1）P(a,b)，　　P(x,y)解：依據(jù)算法：(1) 令W={P(a,b)，P(x,y)}。(2) 令s0=e，W0=W。(3) W0未合一。(4) 從左到右找不一致集，得D0={a，x}。(5) 取x0=x，t0=a，則 s1=s0{ t0/ x0}=s0{a/ x}={a/ x}W1= W0s1={P(a,b)，P(a,y)} (3’) W1未合一。 (4’) 從左到右找不一致集，得D1={b，y}。(5’) 取x1=y，t1=b，則 s2=s1{ t1/ x1}=s1{b/ y}={a/ x}{b/ y}={a/x，b/y}W2= W1s2={P(a,b)，P(a,b)} (3’’) W2已合一，因為其中包含相同的表達(dá)式，這時s2={a/x，b/y}即為所求的mgu。（2）P(f(z)),b)，　　P(y,x)解：依據(jù)算法：(1) 令W={P(f(z),b)，P(y,x)}。(2) 令s0=e，W0=W。(3) W0未合一。(4) 從左到右找不一致集，得D0={f(z)，y}。(5) 取x0=y，t0=f(z)，則 s1=s0{ t0/ x0}=s0{f(z)/ y}={f(z)/y}W1= W0s1={P(f(z),b)，P(f(z),x)} (3’) W1未合一。 (4’) 從左到右找不一致集，得D1={b，x}。(5’) 取x1=x，t1=b，則 s2=s1{ t1/ x1}=s1{b/ x}={ f(z)/ y}{ b/ x}={f(z)/y，b/x}W2= W1s2={P(f(z),b)，P(f(z),b)} (3’’) W2已合一，因為其中包含相同的表達(dá)式，這時s2={f(z)/y，b/x}即為所求的mgu。（3）P(f(x),y)，　　P(y,f(a))解：依據(jù)算法：(1) 令W={P(f(x),y)，P(y,f(a))}。(2) 令s0=e，W0=W。(3) W0未合一。(4) 從左到右找不一致集，得D0={f(x)，y}。(5) 取x0=y，t0=f(x)，則 s1=s0{ t0/ x0}=s0{f(x)/ y}={f(x)/y}W1= W0s1={P(f(x),f(x))，P(f(x),f(a))} (3’) W1未合一。 (4’) 從左到右找不一致集，得D1={y，f(a)}。(5’) 取x1=y，t1=f(a)，則 s2=s1{ t1/ x1}=s1{f(a)/ y}={ f(x)/ y}{ f(a)/ y}={f(x)/y}W2= W1s2={P(f(x),f(x))，P(f(x),f(a))} (6) 算法終止，W的mgu不存在。（4）P(f(y),y,x)，　　P(x,f(a),f(b))解：依據(jù)算法：(1) 令W={P(f(y),y,x)，P(x,f(a),f(b))}。(2) 令s0=e，W0=W。(3) W0未合一。(4) 從左到右找不一致集，得D0={f(y)，x}。(5) 取x0=x，t0=f(y)，則 s1=s0{ t0/ x0}=s0{f(y)/ x}={f(y)/x}W1= W0s1={P(f(y),y,f(y))，P(f(y),f(a),f(b))} (3’) W1未合一。 (4’) 從左