北京科技大学– 离散试题

1、北京科技大学 2007 2008学年 第 i 学期 离散数学 试卷（a）院(系) 班级 学号 姓名 试卷卷面成绩占课程考核成绩70平时 成绩占30%课程考核成绩题号一二三四五六七八小计得分装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊得 分一、判断正误（共30分，每小题1.5分）1. 树是无环连通简单图。 ( )2. 命题具有确定的真假值。 ( )3. pq和pq命题等价。 ( )4. 有向图中结点入度之和等于出度之和。 ( )5. 设r和s是非空集合a上的等价关系，则也是a上的等价关系。 ( )6. 若a为矛盾式，则a的主析取范式为1。 ( )7

2、. 量词的约束顺序对公式真假值无影响。 ( )8. 自然数集是无限集中最小的集合。 ( )9. 质数阶群必是循环群。 ( )10. 若r(r)=r，则r一定是自反的。 ( )11. 若f为函数，则(f-1)-1=f。 ( )12. 群中有幺元，零元。 ( )13. 若无向图中有两对结点的度数为奇数，则存在欧拉路。 ( )14. 任意一棵树至少有两片树叶。 ( )15. ( )16. 设是群g到群h的同态映射，若g是交换群，则h也是交换群。 ( )17. 设v，其中 + 和分别代表普通加法和乘法，则集合s-1, 0, 1可以构成v的子代数。 ( )18. 偶数阶群必含2阶元。 ( )19. 任何

3、一个循环群必定是阿贝尔群。 ( )20. , =, ( )得 分二、填空题（共30分，每个空格2分）1. 已知集合a =，1，2，则a的幂集合p（a）= 。2. 设集合a= a, b, c, d，a上的关系r= ， ，则关系r2= 。3. 设集合a = 0, 1, 2, 3, 4, 5，a上的关系r = ，则r在a上构成的等价类是_ 。4. 设集合a = a, b, c, d, e，a上半序关系r的哈斯图如图1所示，则a的极小元为_ 。图15. 已知命题公式g = （pq）r，则g的主析取范式是_ 。6. 设d：a , b，将表达式x$ y (x, y)中的量词消除后，与之等价的命题公式是 。

4、7. 设g是完全二叉树，g有15个点，其中有8个叶点，则g的分枝点数是 。8. 对下图（图2）中树的点图2中序遍历的次序是 。9. 设有限集a, b，|a| = m, |b| = n, 则笛卡儿积 ab 的子集个数有 _个.10. 设x= x | xr, 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. 设

5、g是由k1, k2, k3 3个连通分支组成的平面图，则g共有 个面。12. 设gs4为4元对称群，则= .13. 设s=，则下列集合s，p(s)，n，nnn，p(n)，r，rr装 订 线 内 不 得 答 题自 觉 遵 守 考 试 规 则，诚 信 考 试，绝 不 作 弊中基数为的有： 。14. 一个班70个学生，在第一次考试中有36人得5分，在第二次考试中有29人得5分，如果两次考试中都没有得5分的有26人，那么两次考试都得5分的有 人。15. 的前束范式是 。得 分三、在自然推理系统f中构造下面推理的证明（8分）前提：，结论： 得 分四、试证：一个有限非交换群至少含有6个元（8分）得 分五、

6、设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分）

7、a) ，1，2，1，2，1，2，ab) ，c) m1 0，m2 1，2，3，m3 4，5d) c，de) pqr或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，nnnn) 21人o)三、证明（8分）在自然推理系统f中构造下面推理的证明前提：，结论：证明：(1) 附加前提引入(2) (1) ei （1分）(

8、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生成的循环

9、群，由上一步的讨论知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分