杭州师范大学钱江学院2012 —2013 学年第二学期期末试卷
_ 班《 离散数学 》（A ）卷
命题教师_田正平_
一、判断题（对的打∨，错的打?；每空2分，共20分）
1、 “若43>，则地球比太阳大。” 是假命题。（ ）
2、 如果命题公式A 是重言式，那么命题公式A 是可满足式。（ ）
3、 有限偏序集),(≤X 必定存在极小元。（ ）
4、 A B A B ?→?∧?)(。（ ）
5、 无向图),(E V G =的每一个顶点的度数2
)(V v d ≥，则图G 是哈密顿图。（ ）
6、 对称关系一定不是反对称关系。（ ）
7、 设集合},,{c b a X =上的关系R 的关系矩阵是???
?
?
??=000101110R M ，则关系R 是传
递关系。（ ）
8、 在复数集合C 上关系}),{(2
2
2
2
d c b a di c bi a R +=+++=是等价关系。（ ）
9、集合},{b a A =到集合}3,2,1{=B 共有6个不同的关系。（ ） 10、没有回路的图是树。（ ）
二、填空题（每空4分，共20分）
1、欧拉图),(E V G =。
2、将命题：“我今天出差，除非我病倒。”符号化。
3、全序关系),(≤X 。
4、轮图n W 的色数=)(5W χ。
5、在无圈图),(E V G 中，3-=V E ，则图),(E V G 的联通分支数=)(G ω。
三、选择题（每题4分，共20分）
1、下面命题公式中，矛盾式是（ ）
（A ）)(Q P P ∨→ (B)P P P ?→?→)(
(C) )()(R Q Q P P ∧?∧→?∨ (D) )()(Q P Q P ???→?
2、设集合}10,6,4,3,2{=X 上的关系R 是整除关系，则关系R （ ） （A ）有最大元，有最小元 (B)有最大元，无最小元
(C) 无最大元，有最小元 (D) 无最大元，无最小元
3、下图（ ）
（A ）有欧拉通路，有哈密顿回路 (B)有欧拉回路，无哈密顿通路
(C) 无欧拉通路，无哈密顿回路 (D) 无欧拉回路，有哈密顿通路
4、设*
R 是非零实数集，下面关系中是等价关系的是（ ）
（A ）}0),{(>+y x y x (B) }0),{(<+y x y x
(C) }0),{(>xy y x (D) }0),{( （1）)}3,3(),3,1(),2,1(),1,1{(1=R （2）)}3,3(),2,2(),1,2(),2,1(),1,1{(2=R （3）)}3,2(),3,1(),2,1(),1,1{(3=R （4）?=4R （5）A A R ?=5 中同时是对称关系和传递关系的是（ ） （A ）431,,R R R (B) 542,,R R R (C ) 532,,R R R (D) 321,,R R R 四、计算题（每题4分，共20分） 1、 设集合}6,4,3,2{=X 上的关系R 是整除关系, 写出关系R 的邻接矩阵。 解：关系R 的邻接矩阵是： 2、集合},,,,{e d c b a X =上的关系)},(),,(),,(),,{(e d d b c b b a R =，求关系R 的传递闭包)(R t 。 3、在复数集C 上定义关系}),{(d b di c bi a R =++=，给出这个等价类的几何说明。 4、写出图G 的一个哈密顿回路。 5、设集合}20,6,4,3,2{=X 上的关系R 是整除关系, 写出偏序关系R 的极大元、极小元。 五、证明题（每题10分，共20分） 1、 证明：面为正方形的正多面体是唯一的。 2、 证明：有限全序集),( X 必有最大元存在。
相关主题
文本预览