《计算机数学基础》(一)――离散数学期末复习参考
M
R S
1 0 0
001
0
0 0
(2) E(0,0,1) (0 0 1) 0 1 (1 1) 0 1 1
E(a,b,c) (a b c) b c
的对偶式为(a b c) b c，
其真值是(0 0 1) 0 1 1 0 1 0
15. x的辖域为：F(x) G(x，z) P(x) x的辖域为：H(x，y) x既是约束变元，也是自由变元，约束出现4次，自由出现1次．y是自由变元，自由出现1次．. z是自由变元，自由出现1次．
x y(Q(f(x),y))) xP(x)
( yQ(f(2),y)) ( yQ(f(3),y)) P(2) P(3))
(Q(3,2) Q(3,3)) (Q(2,2) Q(2,3)) 0 1
(0 1) (0 1) 1 1
16. 做法如下：
①选边1； ②选边2；
③选边3； ④选边5； ⑤选边7
最小生成树为{1,2,3,5,7}．如图4 中粗线所示．
权数为18． 图4 17. 设图G有x个结点，有握手定理
2 1+2 2+3 4＋3 （x 2 2 3） 12 2
3x 24 21 18 27 x 9
图G至少有9个结点． 图５ 满足条件的图如图5所示． 五、证明题
18. ① x A, x,x R, x,x S x,x R S，所以R S有自反性； ② x,y A,因为R，S是对称的，
x,y R S x,y R x,y S
R,S对称的
y,x R y,x S
y,x R S
所以，R S是对称的．
③ x,y,z A，因为R，S是传递的，
x,y R S y,z R S
x,y R x,y S y,z R y,z S x,y R y,z R x,y S y,z S
R,S传递
x,z R x,z S x,z R S 所以，R S是传递的． 总之，R S是等价关系.
19. 首先证*在S上封闭．任取S中的元素
a 0
0 ,b
x 0
0 * ，其中a,b,x,y R． y