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},φ}，则A的幂集有元素 ______ 个。
6. 设A={1,2,3}，B={x,y}，f：AB，则不同的函数个数为 ______ 个。 7. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点，该图有 ______ 个顶点。
8. 集合A={1,2}，B={a,b,c,d}，C={c,d,e}，则A*(B-C)为 ______ 。 9. 求命题公式的主析取范式 ______ 。 10. 命题公式P→Q∧R的对偶式为 ______
二、作图题（本大题共6分，共 1 小题，每小题 6 分）
根据下列条件如果能则画出一个欧拉图，如果不能则说明理由。 （1） 偶数个顶点，偶数条边 （2） 奇数个顶点，奇数条边 （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.
画出满足下列条件的图来
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)自反的 b)对称的 c)可传递的 d)反对称的。
4. 一棵数有两个结点度数为2，一个结点度数为3，三个结点度数为4，问有几个度数为1的结点？
答案：
一、填空题（40分，共 10 题，每小题 4 分） 1.
参考答案：
（1）P?Q (2) P??Q (3)P??Q 解题方案：
评分标准： 2.
参考答案：
恒等关系 恒等矩阵
解题方案：
评分标准：
答案正确得满分，错误不得分 3.
参考答案：
{＜1, α＞,＜1,β＞,＜1,γ＞ ,＜2,α＞,＜2,β＞，＜2,γ＞}
解题方案：
评分标准： 4.
参考答案： {2,3,φ} 解题方案：
评分标准： 5.
参考答案： 8
解题方案：
评分标准： 6.
参考答案： 8
解题方案：
评分标准： 7.
参考答案： 4
解题方案：
评分标准： 8.
参考答案：
{<1,a>,<1,b>,<2,a>,<2,b>} 解题方案：
评分标准： 9.
参考答案：
解题方案：
评分标准： 10.
参考答案： ?P∧(Q∨R) 解题方案：
评分标准：
二、作图题（6分，共 1 题，每小题 6 分） 0.
参考答案：
（1）、（2）均可画出。依次如下：
其中（3）（4）不能画出一个欧拉图，因此具有n个结点的连通图如果存在一条包含所有节点的回路，则该图至少有n条边。对于（3）（4）而言，则必然还有其余的边，使的图中存在奇数度结点，故它们没有欧拉回路，不能构成欧拉图。
解题方案：
评分标准：
三、计算题（30分，共 5 题，每小题 6 分） 1.
参考答案： 略
解题方案： 略
评分标准：
2.
参考答案：
可以一笔画（路径略） 解题方案：
评分标准： 3.
参考答案：
（1）哈斯图为：
（2）B的最大元为6，最小元为1，极大元为6，极小元为1. 为：6，12；上确界为6；下界为：1，下确界为1. 解题方案：
评分标准： 4.
参考答案：
解题方案：
评分标准：
3）B的上界（