abdce
A．abcde B．edcba C．bdeca D．badce
得分 阅卷人 二、填空题（每题3分，共24分）
1、含3个命题变项的命题公式的主合取范式为
M0?M3?M4?M6?M7,
则它的主析取范式为 。(表示成m?m的形势)
2、〈Z4，?〉模4加群， 则3是 阶元，3?3= ，3的逆元是 。 3、设V=
?123456??是集合A={1，2，3，4,5,6}上的一个置换，则把它表示成?31546?不相交的轮换的积是 。
4、已知n阶无向简单图G有m条边，则G的补图有 条边。 5、一个有向图是强连通的充分必要条件是 。 7、已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m， 则m= .
8、在下图中从A点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。
A5B1726E8C34D
得分 阅卷人 三、计算题（每题9分，共 36分）
1、已知命题公式(?p?q)?(?q?p)，
(1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。
2、R1={<1,2>,<1,3>,<2,3>}, R2={<2,2>,<2,3>,<3,4>},求：
(1)R1?R2 （２）R1 (３) 求R2?R1
３、设为一个偏序集，其中，A={1，2，3，4，6，9，12，24},R是A上的整除关系。 （1）画R出的哈斯图； （2）求A的极大元和极小元； （3）求B={4,6}的上确界和下确界。
４、画一棵带权为1，1，1，3，3，5，8的最优二叉树T，并计算它的权W（T）。
得分 阅卷人 四、证明题（共 20分）
1、（7分）前提： p?(q?s),q,p??r
结论: r?s
2、（7分）A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)}, R={<(a,b),(c,d)>| (a,b),(c,d)?A且a+b=c+d }. (1)证明：R是A上的等价关系． (2)给出R确定的对A的划分(分类).
3、（6分）设?G,??是群, S?{x|x?G且对于?y?G,x?y?y?x}, 证明S是G的子群.
《离散数学》试题九
一、选择题（每小题2分，共20分）
1．一个命题公式或一阶逻辑公式的（ ）是不惟一的。 A．主析取范式 B．主合取范式 C．前束范式 D．对偶式 2．下列四个公式正确的是
①?x(A(x)?B(x))??xA(x)??xB(x) ②?x(A(x)?B(x))??xA(x)??xB(x) ③?x(A(x)?B(x))??xA(x)??xB(x) ④?xA(x)??xB(x)??x(A(x)?B(x)) A.①③ B.①④ C.③④ D.②④
3．设集合A={a，b，c，d，e}，偏序关系R的哈斯图下图所示，则元素的关系不正确的是（ ）。
?1ecabdg fA．c?d B．a?e C．a?c D．d?e 4．已知A,B是集合│A│=15，│B│=10，│A∪B│=20，则│A∩B│=（ ）
A．10 B．5 C．20 D．13
5．X={a，b，c，d，e}，Y={1，2，3，4}，f从X到Y的映射，其中f(a)=2, f(b)=4,f(c)=1,f(d)=3,f(e)=4,则f是（ ）
A.双射 B. 满射 C. 单射 D. 不是单射也不是满射 6．设A,B,C是三个非空集合,则( )是正确的.
A.A?B?A?C?B?C B.A?B?A?C?B?C C.A?B?A?C?B?C D. A?B?A?C?B?C 7．在下图所示的哈斯图中的偏序集不是格的是（ ）
8．下图中,（ ）是欧拉图。
A B C D
9.关于无向树的描述,不正确的是( ). A. 无向树是连通图、没有回路,每个边都是桥；
B. 无向树是连通图、边数比顶点数少１,任意两个顶点的路径是惟一的； C. 无向树是连通图、没有回路,每个顶点都是割点； D. 无向树是连通图、没有回路，每条边都是割边。 10.关于含有n片树叶的最优二叉树描述,不正确的是( ). A. 含有n片树叶的最优二叉树每个分支点都有两个孩子；
B. 含有n片树叶的最优二叉树分支点的个数是n-1；
C. W(T)等于个分支点的权重（构造最优二叉树时产生）之和； D. 在权重一定的前提下，含有n片树叶的最优二叉树是惟一的。 二、计算题（每小题10分，共40分） 1.(1)求((p?q)?r)?p的主析取范式； (2)根据主析取范式直接写出主合取范式； (3)根据主析取范式直接写出真值表。
2.设集合A={a，b，c，d}，A上的关系R={,,
(3) tr(R)中再添加一些元素后得D(R)，若使D(R)是等价关系，则tr(R)中再添哪些元
素后得D(R)? 3.(1)下图的最下生成树；
(2)求该图的点连通度和边连通度； (3)求A到B的最短路径的长度。 A
B 4.(10分)对于下有向图,
(1) 写出度序列和出度序列；
(2) 写出邻接矩阵A，第一行元素之和的含义是什么？ (3) 求A,据此说明从A到A的长度为4的回路用多少？
4ADB三、证明题（每小题10分，共40分） 1.利用推理规则证明。
前提：?xP(x)??xQ(x)
C
结论：?x(P(x)?Q(x))
2. 设A是正整数集合，在A?A上定义二元关系R如下：
??x,y?,?u,v???R当且仅当xv?yu,证明：R为等价关系。
3. 设R为实数集，+为普通加法，?为普通乘法，
x*y=x+y+x?y
证明:
4.设f1，f2都是一从代数系统到代数系统
卷号：十 离散数学
本题得分 一、
选择题（选择正确答案，并将其代号写在题干后面的括号里，本
题共6小题,每小题3分，共18分)
1 下列语句中 哪个是真命题？ （） (A) 我正在说谎。 (B) 请讲普通话。
(C) 如果1＋2＝5，那么雪是黑的。 (D) 如果1+2=3,那么雪是黑的。
2 集合A?{1,2,???,10}上的关系R?{(x,y)|x?y?10,x?A,y?A},则R的性质为：（ ） (A) 自反的 (B)对称的 (C) 传递的、对称的 (D) 反自反的、传递的 3下面集合( )关于减法运算是封闭的。
(A) N (B) {x|x是质数}； (C) {2x?1|x?I}； (D) {2x|x?I}。
4设G1??{0,1,2},??，G2??{0,1},*?，其中?表示模3加法，*表示模2加法，则积代数G1?G2的单位元是（ ）。
(A)<0,0>； (B) <0,1>； (C) <1,0>； (D) <1,1> 5 下列偏序集中能构成格的是 （ ）。
6 图G和G?的结点和边分别存在一一对应关系是G和G?同构的 ( ) 。 (A) 必要条件 (B) 充分条件 (C) 充要条件 (D) 既不充分也不必要条件