离散数学试题十.doc

离散数学一、选择（每题3分，共24分） 1. 设为上关系，则具有性质（）。 A.自反性B.反自反性C.对称性D.传递性2. 下列运算正确的是（）。A．B. C．D．3. 下图中各顶点次数之和为18的是（）。 A. B．C．D．数的乘法在下列集合中不封闭的有（）。A．B．C. D．5. 设个体域为有理数集，则以下谓词公式中为假的是（）。 A. ?? B．C． D. 6.若无向图为树，其中，，则等价于以下叙述中的（ ） A．连通且B．连通且C．当且仅当连通D．当且仅当无回路7. 下列各式中，不正确的有（）。A． B． C． D． 8. 实数集关于下列二元运算结合律，交换律都满足的有（）。 A． B． C． D． 二、计算与证明题 1．（每小题4分 共20分） ，为上关系，关系矩阵为， (1) 画出关系图。　　(2) 求，。　　(3) 求，，。　　(4) 指出具有的性质。　　(5) 是偏序关系吗？能否画出哈斯图？ 2．（14分） 设是群，证明是阿贝尔群的充要条件是，对任意，都有。 3．（每小题5分 共15分） 已知命题公式， (1) 构造真值表。(2) 求主析取范式。(3) 求主合取范式。 4．（15分） 对图A，B，利用KRUSKAL算法求最小生成树 图 A 图 B 5．（每小题6分 共12分） 将下列语句翻译成谓词公式。 　　(1) 并非所有的人都聪明。(2) 某些汽车比所有的火车慢。? 测试题八参考答案 二、计算与证明题 1、，为上关系，关系矩阵为， (1) 画出关系图 　　(2) ={1,1,2,2,3,3,2,1,3,1}， ={1,1,2,2,3,3,1,2,1,3}。(3)={1,1,2,2,3,3,2,1,3,1}， ={1,1,2,2,3,3,2,1,1,2,3,1,1,3}， =={1,1,2,2,3,3,2,1,3,1}。　　 (4) 具有自反性、反对称性、传递性。　　 (5) 是偏序关系，哈斯图为： 2、 证明：是阿贝尔群的充要条件是，对，都有。 因为是阿贝尔群，所以任意，有a*b=b*a，所以，即必要条件 已知是群，故G中都有递元存在，又因为，所以， 即是阿贝尔群。 3、已知命题公式， (1) 构造真值表 p q r T T T F T? T? T? T? T T? F? F? T? T? T? T? T? F? T? F? T? F? T? F? T? F? F? F T F T F F T T T T F T F F T F T F F F F F F T T T T T T F F F T F T F F (2) 求主析取范式:(3) 主合取范式: 4 对图A，B，利用KRUSKAL算法求最小生成树 图 A 图 B 则图 A对应的最小生成树为： 图 B对应的最小生成树有5个为： 5、将下列语句翻译成谓词公式： 　　 (1) G(x):x是金子,H(x):x发光,则有： 或者 　　 (2) N(x):x自然数,I(x):x是整数，则有：