离散数学试卷及答案(24).doc

离散数学试卷(24)

一、填空题：）
1．设，，请在下列每对集合中填入适当的符号：。
（1）,(2)。
2．设，N为自然数集，若，则是
射的，若，则是射的。
3．设图G=<V，E>中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，
则G中有条边，根据。
4．两个重言式的析取是，一个重言式和一个矛盾式的合取是。
5．设个体域为自然数集，命题“不存在最大自然数”符号化为。
6．设S为非空有限集，代数系统中幺元为，零元为。
7．设P、Q为两个命题，其De-Morden律可表示为。
8．当时，群只能有阶非平凡子群，不能有阶子群，平凡子群为。
二、单项选择题：（每小题1分，本大题共15分）
1．设，下面哪个命题为假（）。
A、；B、；
C、；D、。
2．设，则B－A是（）。
A、；B、；C、；D、。
3．下图描述的偏序集中，子集的上界为（）。
A、；B、；
C、；D、。

4．设和都是X上的双射函数，则为（）。
A、；B、；C、；D、。
5．下面集合（）关于减法运算是封闭的。
A、N；B、；C、；D、。
6．具有如下定义的代数系统，（）不构成群。
A、，*是模11乘；B、，*是模11乘；
C、（有理数集），*是普通加法；D、（有理数集），*是普通乘法。
7．设，*为普通乘法。则代数系统的幺元为（）。
A、不存在；B、；C、；D、。
8．下面集合（）关于整除关系构成格。
A、{2，3，6，12，24，36}；B、{1，2，3，4，6，8，12}；
C、{1，2，3，5，6，15，30}；D、{3，6，9，12}。
9．设，
，则有向图
是（）。
A、强连通的；B、单侧连通的；C、弱连通的；D、不连通的。
10．下面那一个图可一笔画出（）。

11．在任何图中必定有偶数个（）。
A、度数为偶数的结点；B、入度为奇数的结点；
C、度数为奇数的结点；D、出度为奇数的结点。
12．含有3个命题变元的具有不同真值的命题公式的个数为（）。

A、；B、；C、；D、。
13．下列集合中哪个是最小联结词集（）。
A、；B、；C、；D、。
14．下面哪个命题公式是重言式（）。
A、；B、；
C、；D、。
15．在谓词演算中，下列各式哪个是正确的（）。
A、；B、；
C、；D、。
三、判断改正题：（每小题2分，本大题共20分）
1．设，，则。（其中为（A））()
2．设，，则
。（）
3．集合A上的恒等关系是一个双射函数。（）
4．设Q为有理数集，Q上运算*定义为，则是半群。（）
5．阶数为偶数的有限群中，周期为2的元素的个数一定为偶数。（）
6．在完全二元树中，若有片叶子，则边的总数。（）
7．能一笔画出的图不一定是欧拉图。（）
8．设P，Q是两个命题，当且仅当P，Q的真值均为T时，的值为T。（）
9．命题公式是重言式。（）
10．设命题“所有的研究生都读过大学”符号化为：。（）
四、简答题：（25分）
1．设，A上的关系，求出
。

2．集合上的偏序关系为整除关系。设，，试画出的哈斯图，并求A，B，C的最大元素、极大元素、下界、上确界。

3．图给出的赋权图表示五个城市
及对应两城镇间公路的长度。试给出一个最优化的设计
方案使得各城市间能够有公路连通。

4．已知，为模7乘法。试说明是否构成群？是否为循环群？若是，生成元是什么？

5．给定命题公式，试给出相应的二元树。

五、证明题：（25分）
1．如果集合A上的关系R和S是反自反的、对称的和传递的，证明：是A上的等价关系。

2．用推理规则证明是
的有效结论。

3．若有n个人，每个人都恰有三个朋友，则n必为偶数。

4．设G是（11，m）图，证明G或其补图是非平面图。

一、填空题
1．（1），（2）。2．双射，满射。3．14，。
4．重言式，矛盾式。5．，6．，S。
7．；
。
8．2，4；3，5，6，7；。

二、单项选择题
题号123456789101112131415答案ACBCBDBCCACCABA
三、判断改正题
1．×。
2．×

3．√。4．√。5．×阶数为偶数的有限群中周期为2的元素个数一定为奇数。
6．×完全二叉树中，边数。7．√。
8．×当且仅当P，Q的真值相同时，的真值为T。9．√。
10．×。

四、简答案题
1．解，
，
，
，
。
2．解：的哈斯图为

集合最大元极大元下界上确界A无24，36无无B12126，2，312C66无6
3．解此问题的最优设计方案即要求该图的最小生成树，
由破圈法或避圈法得最小生成树为：
其权数为1+1+3+4=9。

4．解：既构成群，又构成循环群，其生成元为3，5。因为：的运算表为：

1234561123456224613533625144415263553164266543211）由运算表知，封闭；