离散数学2007-2008A卷..doc

北京科技大学 2007 –2008学年 第 I 学期 离散数学 试卷（A） 院(系) 班级 学号 姓名 试卷卷面成绩 占课程考核成绩70 平时 成绩占30% 课程考核成绩 题号 一 二 三 四 五 六 七 八 小计 得分 得 分 一、判断正误（共30分，每小题1.5分） 树是无环连通图。p?q和?p∨q命题等价。中结点入度之和等于出度之和。也是A上的等价关系。 ( ) 若A为矛盾式，则A的主析取范式为1 ( ) 量词的约束顺序对公式真假值无影响。 ( ) 自然数集是无限集中最小的集合。 ( ) 质数阶群必是循环群。 ( ) 若r(R)=R，则R一定是自反的。 ( ) 若f为函数，则(f-1)-1=f。 ( ) 群中有幺元，零元。 ( ) 若无向图中有两对结点的度数为奇数，则存在欧拉路。 ( ) 任意一棵树至少有两片树叶。 ( ) ( ) 设是群G到群H的同态映射，若G是交换群，则H也是交换群。 ( ) 设V＝Z, +, ·，其中 + 和·分别代表普通加法和乘法，则集合S＝{-1, 0, 1}可以构成V的子代数。 ( ) 偶数阶群必含2阶元。 ( ) 任何一个循环群必定是阿贝尔群。 ( ) {?, {?}} – ?={?, {?}} ( ) 得 分 二、填空题（共30分，每个空格2分） 已知集合A ={?，1，2}，则A幂集合（A）=。 设集合A= {a, b, c, d}，A上的关系R= { a , a ，a , c，b, d}，则关系R2=。 设集合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上构成的等价类是_。 设集合A = {a, b, c, d, e}，A上半序关系R的哈斯图如图所示，则A的极小元为_。 图1 已知命题公式G = ?（P?Q）ùR，则G的主析取范式是__。 设D：{a , b}，将表达式x$ y (x, y)中的量词消除后，与之等价的命题公式是。 设G是完全二叉树，G有15个点，其中有8个叶点，则G的分枝点数是。 对下图（图）中树的点 图2 中序遍历的次序是。 设有限集A, B，|A| = m, |B| = n, 则笛卡儿积 A?B 的子集个数有 __________________个. 设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?