发布时间 : 星期一 文章离散数学答案（尹宝林版）第二章习题解答更新完毕开始阅读3b8762726ad97f192279168884868762caaebba9
?(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