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

第二章 谓词逻辑

习题与解答

1. 将下列命题符号化：

(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。令

T(x):x是火车， C(x):x是汽车， F(x,y):x比y跑得快。

“所有的火车都比某些汽车快”可以符号化为?x(T(x)??y(C(y)?F(x,y)))。 (2) 取论域为所有物质的集合。令

M(x):x是金属， L(x):x是液体， D(x,y):x可以溶解在y中。

“任何金属都可以溶解在某种液体中” 可以符号化为?x(M(x)??y(L(y)?D(x,y)))。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为

?x(M(x)??y(L(y)?D(x,y)))。

(4) 取论域为所有事物的集合。令

M(x):x是人， J(x):x是职业， L(x,y):x喜欢y。

“每个人都有自己喜欢的职业” 可以符号化为?x(M(x)??y(J(y)?L(x,y))) (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为

?x(J(x)??y(M(y)?L(y,x)))。

2. 取论域为正整数集，用函数?（加法），?（乘法）和谓词?，?将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。

(4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下：

D(x,y):x能被y整除，D(x,y)可表示为?v(v?y?x)。 J(x):x是奇数，J(x)可表示为??v(v?2?x)。 E(x):x是偶数，E(x)可表示为?v(v?2?x)。

P(x):x是素数，P(x)可表示为?(x?1)??u(?v(v?u?x)?u?1?u?x)。

(1) “没有既是奇数，又是偶数的正整数”可表示为??x(J(x)?E(x))， 并可进一步符号化为??x(??v(v?2?x)??v(v?2?x))。 (2) “任何两个正整数都有最小公倍数”可表示为

?x?y?z(D(z,x)?D(z,y)??u(D(u,x)?D(u,y)?z?u?z?u))，

并可进一步符号化为

?x?y?z(?v(v?x?z)??v(v?y?z)??u(?v(v?x?u)??v(v?y?u)?z?u?z?u))(3) “没有最大的素数”可表示为??x(P(x)??y(P(y)?y?x?y?x))， 并可进一步符号化为

??x(?(x?1)??u(?v(v?u?x)?u?1?u?x)

??y(?(y?1)??u(?v(v?u?y)?u?1?u?y)?y?x?y?x))(4) “并非所有的素数都不是偶数”可表示为??x(P(x)??E(x))，并可进一步符号化为

??x(?(x?1)??u(?v(v?u?x)?u?1?u?x)???v(v?2?x))

3. 取论域为实数集合，用函数?，－（减法）和谓词?，?将下列命题符号化： (1) 没有最大的实数。

(2) 任何两个不同的实数之间必有另一实数。 (3) 函数f(x)在点a处连续。 (4) 函数f(x)恰有一个根。 (5) 函数f(x)是严格单调递增函数。

解 (1) “没有最大的实数”符号化为??x?y(y?x?y?x)。

(2)“ 任何两个不同的实数之间必有另一实数”符号化为?x?y(x?y??z(x?z?z?y))。 (3) “函数f(x)在点a处连续”的定义是：

任给??0，总可以找到??0，使得只要|x?a|??就有|f(x)?f(a)|??。 “函数f(x)在点a处连续”符号化为

??(0?????(0????x(a???x?x?a???f(a)???f(x)?f(x)?f(a)??)))

(4) “函数f(x)恰有一个根”符号化为?x(f(x)?0??y(f(y)?0?y?x))。 (5) “函数f(x)是严格单调递增函数”符号化为?x?y(x?y?f(x)?f(y))。 4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。 (1) ?x(P(y,x)?P(x,a)) (2) ?xP(x)??zQ(x,y)

(3) ?x(P(x)?R(x))??xP(x)?Q(x) (4) ?y(P(f(x,y),x)??xP(z,g(x,y))) (5) ?x(P(x)?Q(x)??xR(x))?R(x)

解 (1) 变元 x 在?x(P(y,x)?P(x,a))中三次出现都是约束出现，?x 的唯一出现的辖域是 P(y, x) ? P(x, a)。

(2) 变元 x 在?xP(x)??zQ(x,y)中的头两次出现是约束出现，第三次出现是自由出现。变元 y 在?xP(x)??zQ(x,y)中的唯一出现是自由出现。变元 z 在

?xP(x)??zQ(x,y)中的唯一出现是约束出现。?x 的唯一出现的辖域是 P(x)，?z 的唯

一出现的辖域是Q(x, y)。

(3) 变元 x 在?x(P(x)?R(x))??xP(x)?Q(x)中的头五次出现是约束出现，第六次出现是自由出现。?x 的第一次出现的辖域是P(x) ? R(x)，第二次出现的辖域是P(x)。 (4) 变元 x 在?y(P(f(x,y),x)??xP(z,g(x,y)))中的头两次出现是自由出现，后两次出现是约束出现。?x 的唯一出现的辖域是 P(z, g(x, y))， ?y 的唯一出现的辖域是 P(f(x, y), x) ? ?xP(z, g(x, y))。

(5) 变元 x 在?x(P(x)?Q(x)??xR(x))?R(x)中的头五次出现是约束出现，第六次出现是自由出现。?x 的唯一出现的辖域是P(x) ? Q(x) ? ?xR(x)，?x 的唯一出现的辖域是R(x)。 5. 归纳证明：若t，t?是项，则tt?也是项。 证明 ① 若t是x，则tt?是t?，tt?是项。

② 若t是不同于x的变元y，则tt?仍是y，tt?是项。 ③ 若t是常元a，则tt?仍是a，tt?是项。

④若t是f(t1,?,tn)，则tt?是f((t1)tx?,?,(tn)tx?)，由归纳假设知(t1)tx?,?,(tn)tx?都是项，

xxxxxxxx

所以tt?是项。

6. 归纳证明：若t是项，A是公式，则At也是公式。

证明 ① 若A是P(t1,?,tn)，则At是P((t1)tx,?,(tn)tx)，由上题知(t1)tx,?,(tn)tx都是项，所以At是公式。

② 若A是?B，则At是?Bt，由归纳假设知Bt是公式，所以At是公式。

③ 若A是B?C，则At是Btx?Ctx，由归纳假设知Bt和Ct都是公式，所以At是公式。

④ 若A是?xB，则At仍是A，At是公式。

⑤ 若A是?yB，其中y是不同于x的变元，则At是?yBtx，由归纳假设知Bt是公式，所以At是公式。

7. 给定解释I和I中赋值v如下：

xxxxxxxxxxxxxxxxxDI?{1,2}，aI?1，bI?2，fI(1)?2，fI(2)?1

PI(1,1)?PI(1,2)?1，PI(2,1)?PI(2,2)?0，v(x)?1，v(y)?1

计算下列公式在解释I和赋值I中v下的真值。 (1) P(a,f(x))?P(x,f(b))?P(f(y),x) (2) ?x?yP(y,x)

(3) ?x?y(P(x,y)?P(f(x),f(y))) 解 (1) (2)

I(P(a,f(x))?P(x,f(b))?P(f(y),x))(v)

?PI(aI,fI(v(x)))?PI(v(x),fI(bI))?PI(fI(v(y)),v(x)) ?PI(1,fI(1))?PI(1,fI(2))?PI(fI(1),1) ?PI(1,2)?PI(1,1)?PI(2,1)?1?1?0?0

I(?x?yP(y,x))(v)

?I(?yP(y,x))(v[x/1])?I(?yP(y,x))(v[x/2]) ?(I(P(y,x))(v[x/1][y/1])?I(P(y,x))(v[x/1][y/2]))

?(I(P(y,x))(v[x/2][y/1])?I(P(y,x))(v[x/2][y/2]))

?(PI(1,1)?PI(2,1))?(PI(1,2)?PI(2,2))

?(1?0)?(1?0)?1

v) (3) I(?x?y(P(x,y)?P(f(x),f(y))))(?(PI(1,1)?PI(fI(1),fI(1)))?(PI(1,2)?PI(fI(1),fI(2))) ?(PI(2,1)?PI(fI(2),fI(1)))?(PI(2,2)?PI(fI(2),fI(2)))

?(PI(1,1)?PI(2,2))?(PI(1,2)?PI(2,1))?(PI(2,1)?PI(1,2))?(PI(2,2)?PI(1,1))?(1?0)?(1?0)?(0?1)?(0?1)?0?0?1?1?0

7. 给定解释I如下：

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

判断I是不是以下语句的模型。 (1) ?x?yP(x,y) (2) ?x?yP(x,y) (3) ?x?yP(x,y) (4) ?x?y?P(x,y)

(5) ?x?y(P(x,y)?P(y,x)) (6) ?xP(x,x)

解 (1) I(?x?yP(x,y))

?(PI(a,a)?PI(a,b))?(PI(b,a)?PI(b,b))?(1?0)?(0?1)?1

(2) I(?x?yP(x,y))

?PI(a,a)?PI(a,b)?PI(b,a)?PI(b,b)?1?0?0?1?0

(3) I(?x?yP(x,y))

?(PI(a,a)?PI(a,b))?(PI(b,a)?PI(b,b))?(1?0)?(0?1)?0

(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)

解 (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)}。

本文来源：https://www.bwwdw.com/article/lrl6.html