2013年4月考试离散数学第3次作业.doc

2013年4月考试离散数学第三次作业一、填空题（本大题共30分，共 15 小题，每小题 2 分）1. 一公式为 ______ 之充分必要条件是其合取范式之每一合取项中均必同时包含一命题变元及其否定2. 对于前提：S→ùQ, SúR, ùR, ùP?Q，其有效结论为 ______ 。3. 集合M={a,b,c,d}，集合N={1,2},则M到N的不同的函数关系有 ______ 个。4. 设p,q的真值为0；r,s的真值为1，求命题公式 （rs)(pq)的真值 ______ 。5. 下图的邻接矩阵A= ______ 。6. 设A={a,b,c},A上的二元关系R={a,b,b,c}，则r(R)= ______ ；s(R)= ______ 。 7. 求命题公式的主合取范式 ______ 。8. 在代数系统A,*中，A={a}，*是A上的二元运算，则该代数系统的单位元是 ______ ,零元是 ______ 。9. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度结点，该图有 ______ 个顶点。 10. 有5个结点的完全图的总边数为 ______ 。11. 设个体域D={1,2}，命题xy(x+y=3)的真值为 ______ 。12. 一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为。 ______ 13. 求命题公式的主析取范式 ______ 。14. 设A={1,2},B={α，β，γ}，则AoB= ______ 。15. 设Z是整数集，+是整数加法运算，则是群，其幺元是 ______ 。二、作图题（本大题共10分，共 2 小题，每小题 5 分）1. 设A={a,b,c},P(A)是A的幂集，R为A上的包含关系，试给出的哈斯图，并给出子集{{b,c},{a,c},{c}}的极大元、极小元、最大元、最小元。2. 某城市拟在六个区之间架设有限电话网，其网点间的距离如下有权矩阵，请绘出有权图，给出架设线路的最优方案，并计算线路的长度。三、计算题（本大题共20分，共 4 小题，每小题 5 分）1. 一棵树中，度数为2的结点有2个，度数为3的结点有3个，。。。度数为k的结点有k个，其余的是度数为1的结点，求度数为1的结点的个数。2. 判定下图是否能够一笔画，若不能，请说明为什么，若能，请标出路径。3. 证明： ( )(C(x)→W(x) ? R(x)) ? ( ? x)(C(x) ? Q(x)) T ( ? x)(Q(x) ? R(x)) 4. 对200名大学一年级的学生进行调查的结果是：其中67人学数学，人学物理，95人学生物，26人既学数学又学生物，28人既学数学又学物理，27人既学物理又学生物，50人这三门课都不学。50人这三门课都不学。 求出三门课都学的学生数四、简答题（本大题共8分，共 1 小题，每小题 8 分）判定下列代数系统是否为群，请说明原因。 （1）R,+，其中R为实数集，+为普通加法； （2）I,，其中I为整数集，为普通乘法 五、分析题（本大题共8分，共 1 小题，每小题 8 分）求出下图的最小生成树，并计算出权。 六、证明题（本大题共24分，共 3 小题，每小题 8 分）1. 如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。2. 设A={1,2,3…9}，在A×A上定义关系R：如果a+d=b+c,则R. (1)证明R是等价关系. (2)求[＜3，6]R (即＜3，6的等价类) 3. 设f1,f2 都是从代数系统到代数系统的同态。设g是从A到B的一个映射，使得对任意a∈A，都有g(a)= f1 (a)* f2 (a)答案：一、填空题（30分，共 15 题，每小题 2 分）1. 参考答案：永真式解题方案：评分标准：答案正确得满分，错误不得分2. 参考答案：P解题方案：评分标准：3. 参考答案：16解题方案：评分标准：4. 参考答案：0解题方案：评分标准：5. 参考答案：解题方案：评分标准：6. 参考答案：{,,,,},s(R)={,,,} 解题方案：评分标准：7. 参考答案：解题方案：评分标准：8. 参考答案：a,a 解题方案：评分标准：9. 参考答案：4解题方案：评分标准：10. 参考答案：10解题方案：评分标准：11. 参考答案：1解题方案：评分标