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

(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

。这表 明