北京科技大学 –学 离散试题.doc

北京科技大学 2007 2008学年 第 I 学期 离散数学 试卷（A）院(系) 班级 学号 姓名 试卷卷面成绩占课程考核成绩70平时 成绩占30%课程考核成绩题号一二三四五六七八小计得分装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊得 分一、判断正误（共30分，每小题1.5分）1. 树是无环连通简单图。 ( )2. 命题具有确定的真假值。 ( )3. p®q和Øpq命题等价。 ( )4. 有向图中结点入度之和等于出度之和。 ( )5. 设R和S是非空集合A上的等价关系，则也是A上的等价关系。 ( )6. 若A为矛盾式，则A的主析取范式为1。 ( )7. 量词的约束顺序对公式真假值无影响。 ( )8. 自然数集是无限集中最小的集合。 ( )9. 质数阶群必是循环群。 ( )10. 若r(R)=R，则R一定是自反的。 ( )11. 若f为函数，则(f-1)-1=f。 ( )12. 群中有幺元，零元。 ( )13. 若无向图中有两对结点的度数为奇数，则存在欧拉路。 ( )14. 任意一棵树至少有两片树叶。 ( )15. ( )16. 设是群G到群H的同态映射，若G是交换群，则H也是交换群。 ( )17. 设V<Z, +, ·>，其中 + 和·分别代表普通加法和乘法，则集合S-1, 0, 1可以构成V的子代数。 ( )18. 偶数阶群必含2阶元。 ( )19. 任何一个循环群必定是阿贝尔群。 ( )20. Æ, Æ Æ=Æ, Æ ( )得 分二、填空题（共30分，每个空格2分）1. 已知集合A =Æ，1，2，则A的幂集合P（A）= 。2. 设集合A= a, b, c, d，A上的关系R= < a , a >， <a , c>，<b, d>，则关系R2= 。3. 设集合A = 0, 1, 2, 3, 4, 5，A上的关系R = <0, 0>，<1, 1>，<1, 2>，<1, 3>，<2, 1>，<2, 2>，<2, 3>，<3, 1>，<3, 2>，<3, 3>，<4, 4>，<4, 5>，<5, 4>，<5, 5>，则R在A上构成的等价类是_ 。4. 设集合A = a, b, c, d, e，A上半序关系R的哈斯图如图1所示，则A的极小元为_ 。图15. 已知命题公式G = Ø（P®Q）ÙR，则G的主析取范式是_ 。6. 设D：a , b，将表达式"x$ y (x, y)中的量词消除后，与之等价的命题公式是 。7. 设G是完全二叉树，G有15个点，其中有8个叶点，则G的分枝点数是 。8. 对下图（图2）中树的点图2中序遍历的次序是 。9. 设有限集A, B，|A| = m, |B| = n, 则笛卡儿积 A´B 的子集个数有 _个.10. 设X= x | xÎR, x ¹0,1, 在X上如下定义6个函数：f1(x) = x， f2(x) =1/x, f3(x) = 1-x, f4(x) = 1/(1-x), f5(x) = (x-1)/x, f6(x) = x/(x-1), 则G = f1, f2, f3, f4, f5, f6关于函数合成运算构成群. 则子群 f1, f2 的所有的右陪集是_.11. 设G是由K1, K2, K3 3个连通分支组成的平面图，则G共有 个面。12. 设GS4为4元对称群，则<(1432)>= .13. 设S=，则下列集合S，P(S)，N，N×N×N，P(N)，R，R×R装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊中基数为的有： 。14. 一个班70个学生，在第一次考试中有36人得5分，在第二次考试中有29人得5分，如果两次考试中都没有得5分的有26人，那么两次考试都得5分的有 人。15. 的前束范式是 。得 分三、在自然推理系统F中构造下面推理的证明（8分）前提：，结论： 得 分四、试证：一个有限非交换群至少含有6个元（8分）得 分五、设A=a,b,c，求出A上所有的等价关系。（10分）得 分六、对下图（图3）所示无向带权图G求一棵最小生成树T，并计算出T的权W(T)。（6分）装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊图3得 分七、设为单射函数，为在下的像。证明也是单射的。（4分）得 分八、求当连通平面图的每个面至少有5条边围成时，边数与结点数所满足的关系式（4分）一、判断正误（共30分，每小题1.5分）1. 2. 3 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.二、填空题（共30分，每个空格2分）a) ，1，2，1，2，1，2，Ab) <a，a>，<a，c>c) M1 0，M2 1，2，3，M3 4，5d) c，de) PØQR或m5f) （F（a，a）F（a，b）（F（b，a）F（b，b）或（F（a，a）F（b，a）（F（a，b）F（b，b）g) 7h) DBKHLEAFICGMJNi)j) f1, f2，f1, f2f3 = f3, f5, f1, f2f4 = f4, f6.k) 2个l) (1234), (13)(24), (1432), (1)m) N，N×N×Nn) 21人o)三、证明（8分）在自然推理系统F中构造下面推理的证明前提：，结论：证明：(1) 附加前提引入(2) (1) EI （1分）(3) (2)化简(4) (2)化简(5) 前提引入(6) (3)EG （1分）(7) (5)(6)假言推理 （1分）(8) 前提引入(9) (4)EG （1分）(10) (8) (9)假言推理 （1分）(11) (10)EI （1分）(12) (7)UI （1分）(13) (11) (12) 假言推理 （1分）(14) (13)EG四、试证：一个有限非交换群至少含有6个元（8分）证明：由拉格朗日定理的推论知，1，2，3，5阶群都是循环群，从而是可交换的。（4分）若G为4阶群，除单位元e外，G的元素的阶或为2或为4。只有两种可能。(1) G中存在一个阶为4的元素a。此时必有G=<a>，是由a生成的循环群，由上一步的讨论知G是可交换的。（2分）(2) 若G中不存在阶为4的元素，由拉格朗日定理的推论知，除e外，G的所有元素的阶为2。设G=e,a,b,c。则。由于，（反之有a或b等于e），且，所以必有。同理，。也是可交换的。（2分）故非交换群至少有6个元素。五、设A=a,b,c，求出A上所有的等价关系。（10分）解 先求出A上有多少个不同的分划。分成一个分划块的分划 分成两个分划块的分划 、分成三个分划块的分划 因此，A上有5个不同的分划（5分），记与分划 相对应的等价关系为（5分）六、对下图所示无向带权图G求一棵最小生成树T，并计算出T的权W(T)。（6分）解：按Kruskal算法，细心的寻找在最小生成树中的边，所得最小生成树如下图所示（4分），W(T)31。（2分）七、设为单射函数，为在下的像。证明也是单射的。（4分）证明：假设，且。（1分）不妨设存在，因此且，于是，（2分）从而。（1分）八、求当连通平面图的每个面至少有5条边围成时，边数与结点数所满足的关系式（4分）解：设平面图G有n个结点，m条边和r个面，则欧拉公式为：nm+r2。（1分）因图中每个面至少有5条边围成，所以有，即，（2分）代入欧拉公式化简后得： （1分）即为所求。 离散数学 试卷 第 10 页 共 10 页