离散数学答案（尹宝林版）第二章习题解答

?x(P(x)?Q(x))|?/?xP(x)??xQ(x)。

(2) 不成立。取解释I如下。

DI?{a,b}， PI(a)?0， PI(b)?1， QI(a)?1， QI(b)?0

则

I(?xP(x)??xQ(x))?1且

I(?x(P(x)?Q(x)))?0。这表明

?xP(x)??xQ(x)|?/?x(P(x)?Q(x))。

(3) 不成立。取解释I如下。

DI?{a,b}， PI(a)?PI(b)?0， QI(a)?1， QI(b)?0

则

I(?x(P(x)??xQ(x)))?1且

I(?x(P(x)?Q(x)))?0。这表明

?x(P(x)??xQ(x))|?/?x(P(x)?Q(x))。

(4) 若解释I使得I(?x(P(x)?Q(x)))?0，则有d?DI使得PI(d)?QI(d)?0，

PI(d)?1且QI(d)?0，I(?xQ(x))?0，I(?x(P(x)??xQ(x)))?0。这表明

?x(P(x)??xQ(x))|??x(P(x)?Q(x))。

(5) 不成立。取解释I如下。

DI?{a,b}， PI(a)?1， PI(b)?0， QI(a)?QI(b)?0

则

I(?x(P(x)?Q(x)))?I(?xP(x))?1且

I(?xQ(x))?0，这表明

?x(P(x)?Q(x)),?xP(x)|?/?xQ(x)。

(6) 不成立。取解释I如下。

DI?{a,b}， PI(a,b)?1， PI(a,a)?PI(b,a)?PI(b,b)?0

则I(?x?yP(x,y))?1，但I(?xP(x,x))?0。所以?x?yP(x,y)|?/?xP(x,x)。 17.设A,B是任意公式，证明以下结论。 (1) ?x(A?B)|??xA??xB (2) ?x(A?B),?xA|??xB

y(3) ?xAx|??x?yA，其中x对于A中的y是可代入的。

(4) ?xA??xB|??x(A?B)

证明 (1) 若解释I和I中赋值v使得I(?x(A?B))(v)?1，则有d?DI使得

I(A?B)(v[x/d])?1，

I(A)(v[x/d])?I(B)(v[x/d])?1，

I(?xA)(v)?1且

I(?xB)(v)?1，I(?xA??xB)(v)?1。这表明?x(A?B)|??xA??xB。

(2) 若解释I和I中赋值v使得I(?x(A?B))(v)?I(?xA)(v)?1，则对于每个d?DI，

I(A?B)(v[x/d])?I(A)(v[x/d])?1，I(B)(v[x/d])?1，I(?xB)(v)?1。这表明?x(A?B),?xA|??xB。

yy(3) 若解释I和I中赋值v使得I(?xAx)(v)?1，则有d?DI使得I(Ax)(v[x/y])?1，y因为I(Ax)(v[x/d])?I(A)(v[x/d][y/I(x)(v[x/d])])?I(A)(v[x/d][y/d])，所以

I(A)(v[x/d][y/d])?1，I(?yA)(v[x/d])?1，I(?x?yA)(v)?1。这表明

y?xAx|??x?yA。

(4) 若解释I和I中赋值v使得I(?x(A?B))(v)?0，则对于每个d?DI，

I(A?B)(v[x/d])?0，I(A)(v[x/d])?1且I(B)(v[x/d])?0，因此I(?xA)(v)?1且I(?xB)(v)?0，I(?xA??xB)(v)?0。所以?xA??xB|??x(A?B)。

18.设变元x既不是公式B中的自由变元，也不是公式集?中任何公式的自由变元，A是公式。若??{A}|?B，则??{?xA}|?B。

证明 设解释I和I中赋值v满足??{?xA}，则I(?xA)(v)?1，有d?DI使得

I(A)(v[x/d])?1。因为x不是公式集?中任何公式的自由变元，所以I和v[x/d]也满足?，

I和v[x/d]满足??{A}。又因为??{A}|?B，所以I(B)(v[x/d])?1，因为x不是B

中的自由变元，因此I(B)(v)?1。这表明??{?xA}|?B。

19. 设?是公式集合，A是公式，则?|?A当且仅当??{?A}不可满足。

证明 设??{?A}可满足，解释I和I中赋值v满足??{?A}，则I和v满足?且

I(A)(v)?0，所以?|?/A。

设?|?/A，则有解释I和I中赋值v满足?且I(A)(v)?0，所以I和v满足??{?A}。因此，??{?A}可满足。

20.判断以下公式集合是否可满足，并说明理由。 (1) {?P(t)|t是项}?{?xP(x)}

(2) {?x?P(x,x),?x?y?z(P(x,y)?P(y,z)?P(x,z)),?x?yP(x,y)} 解 (1) 可满足。取解释I和I中赋值v如下。

DI?{1,2}， PI(1)?0， PI(2)?1，

对每个常元a，aI?1；

对每个n元函数符号f，fI(x1,?,xn)?1； 对每个变元x，v(x)?1。

可归纳证明：对每个项t，I(t)(v)?1。

I和v满足{?P(t)|t是项}?{?xP(x)}。

(2) 可满足。取解释I和I中赋值v如下。

DI为自然数集， PI(x,y)?1 当且仅当 x?y

则I和v满足{?x?P(x,x),?x?y?z(P(x,y)?P(y,z)?P(x,z)),?x?yP(x,y)}。