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

完整word版)离散数学试卷及答案(2)
一、填空 20% （每小题2分）
1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为
；“虽然你努力了，但还是失败了”的翻译为
。
2、论域D={1，2}，指定谓词P
P (1,1)
P (1,2)
P (2,1)
P (2,2)
T
T
F
F
则公式真值为 。
2、 设S={a1 ，a2 ，…，a8}，Bi是S的子集，则由B31所表达的子集是
。
3、 设A={2，3，4，5，6}上的二元关系，则R=
（列举法）。
R的关系矩阵MR=

。
5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R= ；A上既是对称的又是反对称的关系R= 。
*
a b c
a
b
c
a b c
b b c
c c b
6、设代数系统，其中A={a，b，c},

则幺元是 ；是否有幂等 性 ；是否有对称性 。
7、4阶群必是 群或 群。
8、下面偏序格是分配格的是 。

9、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是
。
10、公式 的根树表示为

。
二、选择 20% （每小题2分）
1、在下述公式中是重言式为（ ）
A．；B．；
C．； D． 。
2、命题公式 中极小项的个数为（ ），成真赋值的个数为（ ）。
A．0； B．1； C．2； D．3 。
3、设，则 有（ ）个元素。
A．3； B．6； C．7； D．8 。
4、 设，定义上的等价关系
则由 R产 生的上一个划分共有（ ）个分块。
A．4； B．5； C．6； D．9 。
5、设，S上关系R的关系图为

则R具有（ ）性质。
A．自反性、对称性、传递性； B．反自反性、反对称性；
C．反自反性、反对称性、传递性； D．自反性 。
6、设 为普通加法和乘法，则（ ）是域。
A． B．
C． D．= N 。

7、下面偏序集（ ）能构成格。

8、在如下的有向图中，从V1到V4长度为3 的道路有（ ）条。

A．1； B．2； C．3； D．4 。
9、在如下各图中（ ）欧拉图。
10、设R是实数集合，“”为普通乘法，则代数系统 是（ ）。
A．群； B．独异点； C．半群 。
三、证明 46%
1、 设R是A上一个二元关系，
试证明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分）

2、 用逻辑推理证明：
所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（11分）

3、 若是从A到B的函数，定义一个函数 对任意有，证明：若f是A到B的满射，则g是从B到 的单射。（10分）

4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分）

5、 设G是具有n个结点的无向简单图，其边数，则G是Hamilton图（8分）
四、计算 14%
1、 设是一个群，这里+6是模6加法，Z6={[0 ]，[1]，[2]，[3]，[4]，[5]}，试求出的所有子群及其相应左陪集。（7分）

2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分）

一、 填空 20%（每小题2分）
1、； 2、T 3、 4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>}； 5、R={<1,2>,<1,3>,<2,1>}；R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein四元群；循环群 8、 B 9、；图中无奇度结点且连通 10 、

二、 选择 20%（每小题 2分）
题目
1
2
3
4
5
6
7
8
9
10
答案
B、D
D；D
D
B
D
A
B
B
B
B、C

三、 证明 46%
1、（9分）
（1） S自反的
，由R自反，，
（2） S对称的

（3） S传递的

由（1）、（2）、（3）得；S是等价关系。
2、11分
证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华
上述句子符号化为：
前提：、 结论： ……3分
① P
② P
③ US②
④ T①I
⑤ T③④I
⑥ T①I
⑦ T⑤⑥I
⑧ EG⑦ ……11分
３、１0分
证明 ：

。
48分
证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G1、G2 ，使得u和v分别属于G1和G2，于是G1和G2中各含有1个奇数度结点，这与图论基本定理矛盾，因而u，v一定连通。
5、8分
证明： 证G中任何两结点之和不小于n。
反证法：若存在两结点u，v 不相邻且,令，则G-V1是具有n-2个结点的简单图，它的边数,可得，这与G1=G-V1为n-2个结点为简单图的题设矛盾，因而G中任何两个相邻的结点度数和不少于n。
所以G为Hamilton图.

四、 计算 14%
1、 7分
解：子群有<{[0]},+6>；<{[0],[3]},+6>；<{[0],[2],[4]},+6>；<{Z6},+6>
{[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]}
{[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]}
{[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]}
Z6的左陪集：Z6 。

2、 7分

第 8 页 共 8 页