1、 2014年 9月份考试离散数学第三次作业 一、填空题（本大题共 40 分，共 10 小题，每小题 4 分） 1. 设 P：我生病， Q：我去学校（ 1）命题 “ 我虽然生病但我仍去学校 ” 符号化为 _ 。（ 2）命题 “ 只有生病的时候，我才不去学校 ” 符号化为 _ 。（ 3）命题 “ 如果我生病，那么我不去学校 ” 符号化为 _ 。 2. 某集合 A上的二元关系 R具有对称性，反对称性，自反性和传递性，此关系R是 _ ，其关系矩阵是 _ 3. 设 A=1,2,B= ， ， ，则 AoB= _ 。 4. 设 A=2,3,2,3, ，则 A-2,3= _ 。 5. 设 A=1,2, ，则
2、A 的幂集有元素 _ 个。 6. 设 A=1,2,3， B=x,y， f： A B，则不同的函数个数为 _ 个。 7. 设无向图中有 6 条边， 3度与 5 度顶点各 1个，其余顶点都是 2 度结点，该图有 _ 个顶点。 8. 集合 A=1,2， B=a,b,c,d， C=c,d,e，则 A*(B-C)为 _ 。 9. 求命题公式 的主析取范式 _ 。 10. 命题公式 PQR 的对偶式为 _ 二、作图题（本大题共 6分，共 1 小题，每小题 6 分） 根据下列条件如果能则画出一个欧拉图，如果不能则说明理由。 （ 1） 偶数个顶点，偶数条边 （ 2） 奇数个顶点，奇数条边 （ 3） 偶数个顶点
3、，奇数条边 （ 4） 奇数个顶点，偶数条边 三、计算题（本大题共 30 分，共 5 小题，每小题 6 分） 1. 分别列出：广群、半群、独异点、群的概念 2. 判定下图是否能够一笔画，若不能，请说明为什么，若能，请标出路径。3. 设 S=1,2,3,4,6,12， D为 S上的整除关系， （ 1）试写出该关系并画出哈斯图； （ 2）设子集 B=2,3,6，试求 B的最大元、最小元、极大元和极小元； （ 3）试求 B 的上界、上确界、下界和下确界。 4. 所有的有理数是实数，某些有理数是整数，因此某些实数是整数。 1）请符号化该命题。 2）使用谓词演算的推理论证，证明结论成立。 5. 画出满足下
4、列条件的图来 a）画一个有一条欧拉回路和一条汉密尔顿回路的图。 b）画一个有一条欧拉回路，但没有一条汉密尔顿回路的图。 c）画一条没有一条欧拉回路，但有一条 汉密尔顿回路的图。 四、分析题（本大题共 24 分，共 4 小题，每小题 6 分） 1. 设 I 是整数集， ， =， 是 I 上的二元关系，分别表示小于、大于、等于、小于等于、大于等于，不等于。那么这些关系会满足什么性质？试填写下表： 2. 求出下图的最小生成树，并计算出权。 3. 分析集合 A=1， 2， 3上的下述 5个关系 (1)R=, (2) S=, (3) T=, (4) 空关系 (5) 全域关系 判断上述关系是否为 a)自反
5、的 b)对称的 c)可传递的 d)反对称的。 4. 一棵数有两个结点度数为 2，一个结点度数为 3，三个结点度数为 4，问有几个度数为 1的结点？ 答案： 一、填空题（ 40 分，共 10 题，每小题 4 分） 1. 参考答案： （ 1） PQ (2) P Q (3)PQ 解题方案： 评分标准： 2. 参考答案： 恒等关系 恒等矩阵 解题方案： 评分标准： 答案正确得满分，错误不得分 3. 参考答案： 1, , 1, , 1, , 2, , 2,， 2, 解题方案： 评分标准： 4. 参考答案： 2,3, 解题方案： 评分标准： 5. 参考答案： 8 解题方案： 评分标准： 6. 参考答案：
6、8 解题方案： 评分标准： 7. 参考答案： 4 解题方案： 评分标准： 8. 参考答案： , 解题方案： 评分标准： 9. 参考答案： 解题方案： 评分标准： 10. 参考答案： P (Q R) 解题方案： 评分标准： 二、作图题（ 6 分，共 1 题，每小题 6 分） 0. 参考答案： （ 1）、（ 2）均 可画出。依次如下： 其中（ 3）（ 4）不能画出一个欧拉图，因此具有 n 个结点的连通图如果存在一条包含所有节点的回路，则该图至少有 n条边。对于（ 3）（ 4）而言，则必然还有其余的边，使的图中存在奇数度结点，故它们没有欧拉回路，不能构成欧拉图。 解题方案： 评分标准： 三、计算题（
7、 30 分，共 5 题，每小题 6 分） 1. 参考答案： 略 解题方案： 略 评分标准： 2. 参考答案： 可以一笔画（路径略） 解题方案： 评分标准： 3. 参考答案： （ 1）哈斯图为： （ 2） B 的最大元为 6， 最小元为 1，极大元为 6，极小元为 1. （ 3） B的上界为： 6， 12；上确界为 6；下界为： 1，下确界为 1. 解题方案： 评分标准： 4. 参考答案： 解题方案： 评分标准： 5. 参考答案： 解题方案： 评分标准： 四、分析题（ 24 分，共 4 题，每小题 6 分） 1. 参考答案： 解题方案： 评分标准： 2. 参考答案： 权 =1+2+2+3+5=1
8、3 解题方案： 权 =1+2+2+3+5=13 评分标准： 7 3 3. 参考答案： （ 1）可传递的 （ 2）自反、对称、可传递的 （ 3）都不是 （ 4）自反、对称和传递的 （ 5）自反、对称、传递的 解题方案： （ 1）可传递的 （ 2）自反、对称、可传递的 （ 3）都不是 （ 4）自反、对称和传递的 （ 5）自反、对称、传递的 评分标准： 2 2 2 2 2 4. 参考答案： 设有 x个度数为 1 的结点。则结点总数为： 2+1+3+x=6+x; 树的边树 =结点数 -1，故该树中边数为： 5+x; 因为： 2e=Sdeg(vi) 故： 2(5+x)=2*2+1*3+3*4+x x=9 解题方案： 设有 x个度数为 1 的结点。则结点总数为： 2+1+3+x=6+x; 树的边树 =结点数 -1，故该树中边数为： 5+x; 因为： 2e=Sdeg(vi) 故： 2(5+x)=2*2+1*3+3*4+x x=9 评分标准： 3 3 4
