謂詞邏輯習題課答案

1、謂詞邏輯習題課1.將下列命題符號化（1）在湖南高校學習的學生，未必都是湖南籍的學生H(x)：x是在湖南高校學習的學生; S(x)：x是湖南籍的學生x(H(x)S(x)（2）對于每一個實數(shù)x，存在一個更大的實數(shù)yR(x)：x是實數(shù)； G(x,y):x比y大 x(R(x)y (R(y)G(y,x)（3）存在實數(shù)x，y和z，使得x與y之和大于x與z之積 f(x,y)=x+y; g(x,y)=xy xyz(R(x)R(y)R(z)G(f(x,y), g(x,z)（4）某些汽車比所有的火車都慢，但至少有一列火車比每輛汽車快 C(x)：x是汽車；H(x)：x是火車；S(x,y): x比y慢 x(C(x)y

2、(H(y)S(x,y)z(H(z)y(C(y) S(y,z)（5）對任何整數(shù)x和y，xy且yx是x=y的充要條件I(x)：x是整數(shù)；E(x,y)：x=y；G(x,y)：xyxy(I(x)I(y)(G(x,y)G(y,x) E(x,y)（6）若m是奇數(shù)，則 2m 不是奇數(shù) O(x)：x是奇數(shù)； f(x,y)= xy O(m) O(f(2,m) （7）那位戴眼鏡的用功的大學生在看這本大而厚的巨著 A(x):x是戴眼鏡的,B(x):x是用功的,C(x):x是大學生,D(x):x是大的,E(x):x是厚的，F(xiàn)(x):x是巨著, G(x,y):x在看y,a:那位，b:這本 A(a)B(a)C(a)D(b

3、)E(b)F(b)G(a,b)（8）每個自然數(shù)都有唯一的后繼數(shù) N(x)：x是自然數(shù)； L(x,y)：x是y的后繼數(shù) x(N(x)(y (N(y)L(y,x) z (N(z)L(z,x) E(y,z)（9）沒有一個自然數(shù)使數(shù)1是它的后繼數(shù) x (N(x) L(1,x) （10）每個不等于1的自然數(shù)都有唯一的一個數(shù)是它的直接先行者 S(x,y)： x是y的先行者 x(N(x) E(x,1)!y (N(y)S(y,x)z (N(z)S(y,z)L(z,x)2.變元的約束（1）對下列謂詞公式中的約束變元換名x(P(x)(R(x)Q(x) xR(x)zS(x,z) y(P(y)(R(y)Q(y) tR

4、(t)uS(x,u) （2）對下列謂詞公式中的自由變元代入(yA(x,y)xB(x,z) xzC(x,y,z) (yA(u,y)xB(x,v) xzC(x,w,z) 3.討論在給定解釋下謂詞公式的真值（1）x(PQ(x)R(a)D=-2,3,6 , P:21,Q(x):x3, R(x):x5,a:5x(PQ(x)R(a)(PxQ(x)R(a)(P(Q(-2)Q(3)Q(6)R(5)(T(T T F )F(TF)FFF F（2）xy(P(x)Q(x,y)D= 1,2，P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F真值為F4.判斷下列公式是不是永

5、真式，并加以說明（1）(xP(x) xQ(x) x(P(x) Q(x)解：不是永真式，取解釋如下 D= 1,2 P(1) P(2) Q(1) Q(2) F T F T在該解釋下xP(x) 為T，xQ(x)為F，所以xP(x) xQ(x)為F；而(P(1) Q(1)為T， (P(2) Q(2)為T，所以x(P(x) Q(x)為T；綜上該公式不是永真式（2） x y(P(x) Q(y) (xP(x) y Q(y)解：是永真式。證明：法1，形式證明法2，量詞作用域的收縮與擴張公式5.用形式推理證明：（1）xP(x)xQ(x) x (P(x)Q(x)(1) x (P(x)Q(x)P(假設)(2) x(

6、P(x)Q(x)T(1)E(3) (P(c)Q(c)ES(2)(4) P(c)Q(c)T(3)E(5) P(c) T(4)I(6) xP(x)EG(5)(7) x P(x) T(6)E(8) xP(x)xQ(x) P(9) xQ(x) T(7)(8)I(10) Q(c)US(9)(11) Q(c)T(4)I(12) Q(c) Q(c)T(10)(11)I（2）xF(x)y(G(y)H(y), xM(x)yG(y) x(F(x)M(x)yH(y)(1) x(F(x)M(x)P(附加)(2) xF(x)y(G(y)H(y)P(3) xM(x)yG(y) P(4) xF(x)xM(x) T(1)I(

7、5) xF(x) T(4)I(6) y(G(y)H(y)T(2)(5)I(7) xM(x)T(4)I(8) yG(y) T(3)(7)I(9) G(c) ES(8)(10) G(c)H(c)US(6)(11) H(c)T(9)(10)I(12) yH(y)EG(11)(13) x(F(x)M(x)yH(y)CP（3）任何人如果他喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行設 A(x):x是人, B(x):x是喜歡步行, C(x):x喜歡乘汽車，D(x):x喜歡騎自行車x(A(x)(B(x) C(x),x(A(x)(C(x)D(x),

8、x(A(x) D(x) x(A(x) B(x) x(A(x) D(x) P A(a) D(a) ES A(a) T I D(a) T I x(A(x)(B(x) C(x) P A(a)(B(a) C(a) US B(a) C(a) T I x(A(x)(C(x)D(x) P A(a)(C(a)D(a) US C(a)D(a) T I C(a) T I B(a) T I A(a) B(a) T I x(A(x) B(x) EG （4）每個大學生不是文科生就是理工科生，有的大學生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學生，他就是文科生設 A(x):x是大學生, B(x):x是文科生, C(x):x是理工科生，D(x):x是優(yōu)等生, a:小張x(A(x)( B(x)C(x), x(A(x)D(x) C(a)D(a) A(a)B(a)x(A(x)( B(x)C(x), x(A(x)D(x)