(4) I(?x?y?P(x,y))
??PI(a,a)??PI(a,b)??PI(b,a)??PI(b,b)?0?1?1?0?1
(5) I(?x?y(P(x,y)?P(y,x)))
?(PI(a,a)?PI(a,a))?(PI(a,b)?PI(b,a)) ?(PI(b,a)?PI(a,b))?(PI(b,b)?PI(b,b))
?(1?1)?(0?0)?(0?0)?(1?1)?1
(6) I(?xP(x,x))?PI(a,a)?PI(b,b)?1?1?1
9. 写出一个语句A，使得A有模型，并且A的每个模型的论域至少有三个元素。 解 语句A为?x?P(x,x)?P(a,b)?P(b,c)?P(c,a)。给定解释I?如下。
DI?为自然数集合， PI?(x,y)?1当且仅当x?y， aI??1，bI??2，cI??3
则I?是A的模型，A有模型。
任取满足语句A的解释I，则PI(aI,bI)?PI(bI,cI)?PI(cI,aI)?1，又因为
I(?x?P(x,x))?1，所以aI，bI，cI是论域DI中三个不同元素，论域DI中至少有三个
元素。
10. 写出一个语句A，使得A有模型，并且A的每个模型的论域有无穷多个元素。 解 语句A为?x?P(x,x)??x?y(P(x,y)?P(y,z)?P(x,z))??x?yP(x,y)。给定解释I?如下。
DI?为自然数集合， PI?(x,y)?1当且仅当x?y
则I?是A的模型，A有模型。
任取满足语句A的解释I，取d1?DI，因为I(?x?yP(x,y))?1，所以有d2?DI使得
PI(d1,d2)?1，又因为I(?x?P(x,x))?1，故d1?d2。因为I(?x?yP(x,y))?1，所以
有d3?DI使得PI(d2,d3)?1，又因为I(?x?P(x,x))?1，故d3?d2。因为
I(?x?y(P(x,y)?P(y,z)?P(x,z)))?1，所以PI(d1,d3)?1，故d3?d1。因此，d1，
d2，d3是论域中的三个不同元素。这个过程可以不断进行下去，得到d1,d2,d3,?因此，
论域 DI 中必然有无穷多个元素。
11. 判断以下公式是不是永真式、永假式、可满足式，并说明理由。
(1) ?xP(x)??xQ(x)??x(P(x)?Q(x)) (2) ?xP(x)??xQ(x)??x(P(x)?Q(x)) (3) ?x(P(x)?Q(x))??xP(x)??xQ(x) (4) ?xP(x,x)??x?yP(x,y)
(5) (?xP(x)??xQ(x))??x(P(x)?Q(x)) (6) (?xP(x)??xQ(x))??x(P(x)?Q(x)) (7) ?x(P(x)?Q(x))?(?xP(x)??xQ(x))
解 (1) ?xP(x)??xQ(x)??x(P(x)?Q(x))是永真式。若解释I
使得
I(?xP(x)??xQ(x))?1，则I(?xP(x))?1或I(?xQ(x))?1。
① 若I(?xP(x))?1，则存在d?DI使得PI(d)?1，PI(d)?QI(d)?1。 ② 若I(?xQ(x))?1，则存在d?DI使得QI(d)?1，PI(d)?QI(d)?1。 因此，I(?x(P(x)?Q(x)))?1。
(2) ?xP(x)??xQ(x)??x(P(x)?Q(x))是非永真的可满足式。给定解释I如下。
DI?{d}， PI(d)?1， QI(d)?1
则I(?xP(x)??xQ(x)??x(P(x)?Q(x)))?1。 给定解释I?如下。
DI??{a,b}，PI?(a)?1，PI?(b)?0，QI?(a)?0，QI?(b)?1
则I?(?xP(x)??xQ(x)??x(P(x)?Q(x)))?0。
(3) ?x(P(x)?Q(x))??xP(x)??xQ(x)是非永真的可满足式。给定解释I如下。
DI?{d}， PI(d)?1， QI(d)?1
则I(?x(P(x)?Q(x))??xP(x)??xQ(x))?1。 给定解释I?如下。
DI??{a,b}，PI?(a)?1，PI?(b)?0，QI?(a)?0，QI?(b)?1
则I?(?x(P(x)?Q(x))??xP(x)??xQ(x))?0。
(4) ?xP(x,x)??x?yP(x,y)是非永真的可满足式。给定解释I如下。
DI?{d}， PI(d,d)?1
则I(?xP(x,x)??x?yP(x,y))?1。 给定解释I?如下。
DI??{a,b}，PI?(a,a)?PI?(b,b)?1，PI?(a,b)?PI?(b,a)?0
则I?(?xP(x,x)??x?yP(x,y))?0。
(5) (?xP(x)??xQ(x))??x(P(x)?Q(x))是非永真的可满足式。给定解释I如下。
DI?{d}， PI(d)?1， QI(d)?1
则I((?xP(x)??xQ(x))??x(P(x)?Q(x)))?1。 给定解释I?如下。
DI??{a,b}，PI?(a)?1，PI?(b)?0，QI?(a)?0，QI?(b)?1
则I?((?xP(x)??xQ(x))??x(P(x)?Q(x)))?0。
(6) (?xP(x)??xQ(x))??x(P(x)?Q(x))是永真式。若解释
I
使得
I(?x(P(x)?Q(x)))?0，则存在d?DI使得PI(d)?QI(d)?0，因此PI(d)?1且
QI(d)?0，I(?xP(x))?1且I(?xQ(x))?0，I((?xP(x)??xQ(x)))?0。
(7) ?x(P(x)?Q(x))?(?xP(x)??xQ(x))是永真式。若解释
I
使得
I((?xP(x)??xQ(x)))?0，则I(?xP(x))?1且I(?xQ(x))?0。存在d?DI使得
PI(d)?1，又因为I(?xQ(x))?0，所以QI(d)?0，PI(d)?QI(d)?0。因此，
I(?x(P(x)?Q(x)))?0。
12.设A,B是任意公式，证明以下公式是永真式。 (1) Atx??xA,其中项t对于A中的x是可代入的。 (2) ??xA??x?A (3) ??xA??x?A
(4) ?x(A?B)??xA??xB (5) ?xA??xB??x(A?B)
(6) ?x(A?B)?(A??xB)，其中x不是A的自由变元。
解 (1) 任取解释I和I中赋值v，若I(Atx)(v)?1,则I(Atx)(v)?I(A)(v[x/I(t)(v)])?1，所以I(?xA)(v)?1。这表明Atx??xA是永真式。 (2) 任取解释I和I中赋值v，
I(??xA)(v)?1 当且仅当 I(?xA)(v)?0
当且仅当 存在d?DI使得I(A)(v[x/d])?0 当且仅当 存在d?DI使得I(?A)(v[x/d])?1 当且仅当 I(?x?A)(v)?1
这表明??xA??x?A是永真式。 (3) 任取解释I和I中赋值v，
I(??xA)(v)?0 当且仅当 I(?xA)(v)?1
当且仅当 存在d?DI使得I(A)(v[x/d])?1 当且仅当 存在d?DI使得I(?A)(v[x/d])?0 当且仅当 I(?x?A)(v)?0
这表明??xA??x?A是永真式。
()?1，则存在d?DI使得(4) 任取解释I和I中赋值v，若I(?x(A?B))vI(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是永真式。 ()?0，则存在d?DI使得(5) 任取解释I和I中赋值v，若I(?x(A?B))v
I(A?B)(v[x/d])?0，I(A)(v[x/d])?I(B)(v[x/d])?0，I(?xA??xB)(v)?0。
这表明?xA??xB??x(A?B)是永真式。
(6) 任取解释I和I中赋值v，若I(?x(A?B))(v)?I(A)(v)?1，则对于每个d?DI，
I(A?B)(v[x/d])?1，因为x不是A的自由变元，所以I(A)(v[x/d])?I(A)(v)?1，
因此I(B)(v[x/d])?1，I(?xB)(v)?1。这表明?x(A?B)?(A??xB)是永真式。 13.设A1是公式A的闭包，A2是?x1??xnA，其中Var(A)?{x1,?,xn}。证明： (1) A是永真式当且仅当A1是永真式； (2) A是可满足式当且仅当A2是可满足式。
证明 (1) （?）首先证明：若A是永真式，则?xA是永真式。设A是永真式。任取解释I和I中赋值v，任取d?DI，因为v[x/d]也是I中赋值，所以I(A)(v[x/d])?1，
I(?xA)(v)?1。?xA是永真式。若A是永真式，则?xnA是永真式，… ，?x1??xnA是
永真式。
（?）因为?x1??xnA?A是永真式，所以若?x1??xnA是永真式，则A是永真式。 (2) （?）因为A??x1??xnA是永真式，所以若解释I和I中赋值v满足A，则I和v满足?x1??xnA。
（?）若解释I和I中赋值v满足?x1??xnA，则有d1,?,dn?DI使得
I(A)(v[x1/d1,?,xn/dn])?1，I和I中赋值v[x1/d1,?,xn/dn]满足A。
14.判断以下等值式是否成立，并说明理由。 (1) ?x(P(x)?Q(x))??xP(x)??xQ(x) (2) ?x(P(x)?Q(x))??xP(x)??xQ(x) (3) ?xP(x)?P(x) (4) ?x?xP(x)??xP(x)
(5) ?x(P(x)??yQ(y))??xP(x)??yQ(y) (6) ?x(P(x)??yQ(y))??xP(x)??yQ(y)