《计算机数学基础》(一)――离散数学期末复习参考
R＝{<1,2>,<3,1>} S={<1,2>,<2,1>,<3,3>} 求R S，写出它的矩阵MR S．
(2) 求布尔表达式E(a,b,c) (a b c) b c的对偶式，并求当a,b,c取值0,0,1时，E(a,b,c)以及其对偶式的真值。
15. 指出谓词公式 x(F(x) G(x,z) P(x)) xH(x,y) S(x)中 x和 x的辖域，
16. 已知带权图G，如图3所示．试求图G的 最小生成树，并计算该生成树的权．
17. 设简单连通无向图G有12条边，G中有1度
结点2个，2度结点2个，4度结点3个，其余结点度 数不超过3．求G中至少有多少个结点．试作一个满足 该条件的简单无向图． 图3
五、证明题
18. 证明如果R和S是非空集合A上的等价关系，则R S也是A上的等价关系． 19. 设R*是非0实数集，在R*上定义集合S为
S {
a 0
0 *
a,b R} b
证明 (S，*)是代数系统，满足结合律，交换律，存在单位元，S的每个元素有逆元。其中*是矩阵的乘法运算． 五、自我练习题解答
一、单项选择题
1. B 2. C 3. A 4. A 5. D 二、填空题
6. 1 7. x(N(x) Z(x)) x(Z(x) N(x)) 8. 0 9. m=n ． 10. 结点vi的出度和结点vj的入度 三、化简解答题
11. . 命题公式的真值表
12. ((A B C) (A C))－((C (C－B) ～A)
＝(A C)－（C ～A）(两次用吸收律) =((A C) (～C A)
=(A ～C) (C ～C) A (A C) =(A ～C) A=A
13. (1) P Q ( R P)
(P Q) (R P) (P Q) ( P R)
不惟一.
(2) x(P Q(x)) R(f(a))
=((P Q(0)) (P Q(4))) R(f(4))
=(1 0) (1 1) 0 0
四、计算解答题
14. (1) R S= {<1,2>,<3,1>} {<1,2>,<2,1>,<3,3>}={ 1,1 , 3,2 }