《离散数学》考试题库及答案
- 格式：pdf
- 大小：1.31 MB
- 文档页数：25
《离散数学》考试题库及答案
、填空 20% （每小题2分）
1. 设 A = {xl（xeN）且（*5）},B = {xlx£E+且xv7}
（N;自然数集，曰正偶 数）则 。
2.
A, B, C
表示三个集合，文图中阴影部分的集合表达式为
3. 设P, Q的真值为0, R, S的真值为1,则
「（P v （Q r （R
A「P））） T （R v「S）的真
值=
4. 公式成逐）3人&）八户的主合取范式为
5. 若解释I的论域D仅包含一个元素，则在I下真值为
6. 设A={1, 2, 3. 4}, A上关系图为
则R2 =
7. 设A=（a, b, c, d},其上偏序关系R的哈斯图为
9.设A={a, b, c, d} , A上二元运算如下: 那么代数系统VA, *＞的幺元是
,有逆元的元素为 ,它们的
逆元分别为 C
10.下图所示的偏序集中，是格的为 ，
二、选择20% （每小题2分）
I. 下列是頁命题的有（
2、 下列集合中相等的有（ ）
A. ｛4, 3｝^中；B. ｛①，3, 4｝； C. ｛4,中，3, 3｝； D. ｛3, 4｝。
3、 设A=｛1, 2, 3｝,则A上的二元关系有（）个。
A. 23； B. 32 ； C. 23x3.
D. 32气
4、 设R, S是集合A上的关系，则下列说法正确的是（ ）
A. 若R. S是自反的，则R°S是自反的；
B. 若R, S是反自反的，则R°S是反自反的；
C. 若R, S是对称的，则RoS是对称的；
D. 若R, S是传递的，则R°S是传递的。
5、设A=｛1, 2, 3. 4｝, P （A） （A的蓦集）上规定二元系如下 中£｛｛中｝,中｝ D. ｛①隹｛｛中｝｝ R = {< s,t >1 s,t e p(A)
A (I 51=1 /1)则 p(A)/
R=( )
A. A ： B. P(A) : C. ({{!}}, {{1, 2}}, {{1, 2, 3}}, {{1, 2, 3. 4}}}；
D. ({①}, {2}, {2, 3}, {{2, 3, 4}}, {A}}0
6、设A={小，{lb (1, 3}, (1, 2, 3}}则A上包含关系“W”的哈斯图为(
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4
度结点。
A. 1； B. 2； C. 3； D. 4。
三、证明26%
7、下列函数是双射的为（
A. f:I^E, f(x) = 2x ； B. JN — NxN, f (n) =
C. f:R_I, f(x) = [xl ； D. f:LN,f(x)
（注：I—整数集，E一偶数集，N—自然数集,
R—实数集）
）条。
9、下图中既不是Eular图, 也不是Hamilton图的图是（ 1、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当
< a, b> 和va, c>在 R 中有v.b, c>在 R 中。(8 分)
2、 f和g都是群
群。其中c」引'EG]且/'(x) = g(x)} (8分)
3、 G=
四、 逻辑推演16%
用CP规则证明下题(每小题8分)
I A
VB->C
AD,Q
VE
TF
=
A->F
2、S(P(x)->。(同)n SP(x) t SQ⑴
五、 计算18%
1、设集合 A={a, b, c. d}上的关系 R={va,b>,vb,a>,vb,c>,vc,d>}用矩阵运算
求出R的传递闭包t(R)。 (9分)
2、如下图所示的赋权图表示某七个城市七'％'…'、及预先算出它们之间的一些直接通
信线路造价，试给出一个设计方案，使得各城市之间能够通信而11总造价最小。 (9分)
5^ 1； 6^ {, <1,.3>, <2,2>, <2,4> }； 7、{
匕；8、e<
图，则 2-2)
由此证明彼得森图(Peterson)图是非平面图。(11分)
试卷一答案：
一、填空20% (每小题2分)
1、 {0, 1, 2, 3,4,6}； 2、 (B©C)-A. 3、
1; 4、(^
VS
V/?)
A(->P
V-,S
V/?)
；
9、a : a,b,c,d : a, d , c , d : 10、c;
二、选择20% （每小题2分）
题目 1 2 3 4 5 6 7 8 9 10
答案 C D B、C C A D C A D B A
三、证明26%
1、证:
Pa,b,ccX 若
R 对称性知
vb，a>,vc,a> eR,由
R 传递性得 vb,c>cR
“ u ” 若 v a,b >
GR < a,c >
G R 有 < b,c >
G R 任意 a,b c X , 因
va,a>eR 若 va,b>eR「.
R 是对祢的。
若 va,b>cR < b,c > e R 则 vb,a>€R/\
即R是传递的。
f(.a) = g(a),f(b) = g(b)
f(b-i) = /-i(Z>), g(b-i) = g-i(b) :. f(b-t) = f-i(b) = g-i(b) = g(b-i)
••• f(a ★ H)= /(«)*/-' (b) = g(o) * g(“ ) = gjb-i)
••fb-EC ..<(：,★> 是 vG], ★ >的子群。
3、证:
2e = ^ d（F）>rk
r<^_
①设G有r个面，则 ' ，即 *。而 2、证
v-e+r=2故
