解 (1) 不成立。取解释I如下。
DI?{a,b}， PI(a)?0， PI(b)?1， QI(a)?1， QI(b)?0
则I(?x(P(x)?Q(x)))?0且I(?xP(x)??xQ(x))?1。 (2) 不成立。取解释I如下。
DI?{a,b}， PI(a)?0， PI(b)?1， QI(a)?1， QI(b)?0
则I(?x(P(x)?Q(x)))?0且I(?xP(x)??xQ(x))?1。 (3) 不成立。取解释I和I中赋值v下。
DI?{a,b}， PI(a)?0， PI(b)?1， v(x)?b
则I(?xP(x))(v)?0且I(P(x))(v)?1。
(4) 成立。任取解释I和I中赋值v，因为x不是?xP(x)中的自由变元，所以对于每个
d?DI，I(?xP(x))(v[x/d])?I(?xP(x))(v)。
I(?x?xP(x))(v)?1
当且仅当对于每个d?DI，I(?xP(x))(v[x/d])?1 当且仅当I(?xP(x))(v)?1
(5) 不成立。取解释I如下。
DI?{a,b}， PI(a)?0， PI(b)?1， QI(a)?1， QI(b)?0
则I(?x(P(x)??yQ(y)))?0且I(?xP(x)??yQ(y))?1。 (6) 不成立。取解释I如下。
DI?{a,b}， PI(a)?1， PI(b)?0， QI(a)?QI(b)?1
则I(?x(P(x)??yQ(y)))?0且I(?xP(x)??yQ(y))?1。 15.设A,B是任意公式，证明以下等值式。 (1) ?xA??yAy，其中y在A中不出现。 (2) ?x(A?B)??xA??xB
(3) ?x?y(A?B)??xA??yB，其中x不是B的自由变元，y不是A的自由变元。 (4) ?x?y(A?B)??xA??yB，其中x不是B的自由变元，y不是A的自由变元。
x
(5) ?x?y(A?B)??xA??yB，其中x不是B的自由变元，y不是A的自由变元。 (6) ?x?yA??y?xA
xx证明 (1) ?xA???x?A???y?Ay??yAy
(2) ?x(A?B)??x(?A?B)??x?A??xB???xA??xB??xA??xB (3) ?x?y(A?B)??x(A??yB)??xA??yB (4) ?x?y(A?B)??x(A??yB)??xA??yB (5) ?x?y(A?B)??x(A??yB)??xA??yB (6) 任取解释I和I中赋值v，
I(?x?yA)(v)?0
当且仅当有d?DI使得I(?yA)(v[x/d])?0 当且仅当有d,c?DI使得I(A)(v[x/d][y/c])?0 当且仅当有d,c?DI使得I(A)(v[y/c][x/d])?0 当且仅当有c?DI使得I(?xA)(v[y/c])?0
当且仅当I(?y?xA)(v)?0
16.判断以下逻辑推论关系是否成立，并说明理由。 (1) ?x(P(x)?Q(x))|??xP(x)??xQ(x) (2) ?xP(x)??xQ(x)|??x(P(x)?Q(x)) (3) ?x(P(x)??xQ(x))|??x(P(x)?Q(x)) (4) ?x(P(x)??xQ(x))|??x(P(x)?Q(x)) (5) ?x(P(x)?Q(x)),?xP(x)|??xQ(x) (6) ?x?yP(x,y)|??xP(x,x) 解 (1) 不成立。取解释I如下。
DI?{a,b}， PI(a)?0， PI(b)?1， QI(a)?1，则
I(?x(P(x)?Q(x)))?1且
I(?xP(x)??xQ(x))?0
QI(b)?0
。这表 明
?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)}。