发布时间 : 星期一 文章离散数学答案（尹宝林版）第二章习题解答更新完毕开始阅读3b8762726ad97f192279168884868762caaebba9
?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)}。