离散数学(B)答案 VIP免费

离散数学试卷（第1页，共5页）1杭州师范大学钱江学院2013—2014学年第二学期期末试卷_班_《离散数学》(B)卷命题教师_田正平_一、判断题（对的打，错的打；每空2分，共20分）1、“如果地球比太阳大，那么月球就比地球大。”是假命题。（）2、“‘请勿吸烟!’,不是命题。”是命题。（）3、命题)(pqp是重言式。（）4、设集合},,{cbaX上的关系R的关系矩阵是000100111RM，则关系R是传递关系。（）5、在复数集合C上关系}0),{(acdicbiaR是等价关系。（）6、有限偏序集),(X必定存最大元。（）7、集合},{baA到集合}3,2,1{B共有6个不同的关系。（）8、完全图nK的色数nKn)(。（）9、若图有欧拉通路，则图的所有顶点的度数都是偶数。（）10、连通偶图一定是哈密顿图。（）题目一二三四五总分分值2028202012100得分得分班级：学号：姓名：装订线离散数学试卷（第2页，共5页）2二、填空题（每空4分，共20分）1、哈密顿图),(EVG。解：包含),(EVG的每一个顶点的基本回路称为G的哈密顿回路。具有哈密顿回路的图称为哈密顿图。2、将命题：“我今天出差，除非我病倒。”符号化。解：设命题P：我今天出差，命题Q：我生病。则命题：“我今天出差，除非我病倒。”可以符号化为：QP。3、全序集),(X。解：设),(X是偏序集，且对X中任意两个元素yx,，关系xyyx,总有一个成立，则称),(X是全序集。4、轮图nW的色数4)(5W。5、设顶点v是图),(EVG的割点，则)()(GvG三、选择题（每题4分，共20分）1、下面命题公式中，重言式是（ABD）（A）)(QPP(B)PPP)((C))()(RQQPP(D))()(QPQP2、设集合}10,6,4,3,2{X上的关系R是整除关系，则关系R（D）（A）有最大元，有最小元(B)有最大元，无最小元(C)无最大元，有最小元(D)无最大元，无最小元3、下图（A）（A）有欧拉通路，有哈密顿回路(B)有欧拉回路，无哈密顿通路得分得分离散数学试卷（第3页，共5页）3(C)无欧拉通路，无哈密顿回路(D)无欧拉回路，有哈密顿通路v1v2v3v5v6e1e2e3e4e5e6e7e8e9e104、)()())()((xxBxxAxBxAx是（C）（A）永真式(B)矛盾式(C)可满足式(D)以上都不是5、集合A={1,2,3}上的五个关系（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）AAR5中同时是对称关系和传递关系的是（B）（A）431,,RRR(B)542,,RRR(C)532,,RRR(D)321,,RRR四、计算题（每题4分，共20分）1、设集合}6,4,3,2{X上的关系R是整除关系,写出关系R的关系矩阵。解：关系R的关系矩阵是：1000010010101101RM得分离散数学试卷（第4页，共5页）42、集合},,,,{edcbaX上的关系)},(),,(),,(),,{(eddbcbbaR，求关系R的传递闭包)(Rt。解：关系R的传递闭包)},(),,(),,(),,(),,(),,(),,(),,{()(ebeadacaeddbcbbaRt。3、在复数集C上定义关系}),{(dbdicbiaR，给出这个等价类的几何说明。解：等价类}{CxbixbiaR，是所有在直线by上的复数。4、设nX是有限集，求在X上的自反关系的个数。解：在X上的自反关系R可以写成SIRX这里S是幂集)(2XIXP的子集合。所以在X上不同的自反关系共有nn22个。5、设集合}20,6,4,3,2{X上的关系R是整除关系,写出偏序关系R的极大元、极小元。解：偏序关系R的极大元是6,20；极小元是2,3。五、证明题（每题6分，共12分）1、证明：非空有限偏序集必有极小元。证明：设),(X是偏序集。任取X中的一个元素1x，如果1x不是极小元，那么存在Xx2使得12xx；如果2x不是极小元，那么存在Xx3使得23xx；......，因为),(X是有限集，且,,,321xxx全不相等，而这个过程不可能无限重复。上面的过程有限次之后必能找到极小元。得分离散数学试卷（第5页，共5页）52、写出下列推理的逻辑证明：)()(xxAxxA。