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

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