离散数学(A)答案2015

离散数学试卷（A）卷，第1页，共5页杭州师范大学钱江学院2014—2015学年第二学期期末试卷_班《离散数学》（A）卷命题教师_田正平_一、判断题（对的打，错的打；每空2分，共20分）1、“若鸟不会飞，则地球比太阳大。”是假命题。（）2、qqpp)(。（）3、)()())()((xxBxxAxBxAx（）4、有限偏序集),(X必定存在最小元。（）5、对称关系不一定是反对称关系。（）6、设集合},,{cbaX上的关系R的关系矩阵是100111101RM，则关系R是等价关系。（）7、图G是n阶简单图，若对所有的1)(vdVv，则在G中有回路。（）8、在哈密顿图G中若顶点u和v不相邻，则必有nvdud)()(。（）9、平面图G是n阶简单连通图，它有e条边，则63ne。（）10、有n—1条边的n阶图是树。（）题目一二三四五总分分值2020202020100得分得分班级：学号：姓名：装订线离散数学试卷（A）卷，第2页，共5页二、填空题（每空4分，共20分）1、将命题：“每列火车都比某些汽车快。”符号化。设个体域为交通工具。P(x)：x是火车；Q(x)：x是汽车；R(x,y)：x比y快。则“每列火车都比某些汽车快。”可以符号化为：)),()()((yxRyQxPyx2、全序关系),(X。集合X上的自反，反对称和传递关系称为X上的偏序关系，如果对于X中的任意两个元素都是可以比较的，那么就称为全序关系。3、简单回路。图的一条回路，如果其中所有的边都不相同，那么就称为简单回路。4、超立方图nQ的色数)(nQ2。5、在简单图),(EVG中，3VE，则图),(EVG的联通分支数)(G3。三、选择题（每题4分，共20分）1、下面命题公式中，矛盾式是（C）（A）)(QPP(B)PPP)((C))()(RQQPP(D))()(QPQP2、设集合}12,10,6,4,3,2,1{X上的关系R是整除关系，则关系R（C）（A）有最大元，有最小元(B)有最大元，无最小元(C)无最大元，有最小元(D)无最大元，无最小元得分得分离散数学试卷（A）卷，第3页，共5页3、图G的邻接矩阵0110110010100100110110010A，则图G（C）（A）无欧拉通路，有哈密顿回路(B)有欧拉回路，无哈密顿通路(C)有欧拉通路，无哈密顿回路(D)无欧拉回路，有哈密顿通路4、设R是非零实数集，下面关系中是等价关系的是（C）（A）}0),{(yxyx(B)}0),{(yxyx(C)}0),{(xyyx(D)}0),{(xyyx5、和谓词公式))((BxAx等值的是（C）（A）BxxA)((B))(xxAB(C)BxxA)((D))(xxAB四、计算题（每题4分，共20分）1、化简命题公式))((pqpq。解：111)()()()())(())(())(())(())((qpqppqqppqpqpqpqpqpqpqpqpqpqpq2、集合},,,,{edcbaX上的关系)},(),,(),,(),,{(eddbcbbaR，求关系R的传递闭包)(Rt。得分离散数学试卷（A）卷，第4页，共5页解：5432)},{()},(),,(),,{(RReaRebdacaR所以：)},(),,(),,(),,(),,(),,(),,{),,{(,)(321eaebdacaeddbcbbaRRRRRtnn3、在复数集C上定义关系}),{(dbdicbiaR，给出这个等价类的几何说明。解：}|{][RxbixbiaR所以等价类是复平面上平行于实轴的直线。4、图G的邻接矩阵0110110010100100110110010A，求从顶点1v到顶点2v长度为3的不同通路的个数。解：06606600606006006606600603A所以顶点1v到顶点2v长度为3的不同通路的个数是6。5、设集合}20,6,4,3,2{X上的关系R是整除关系,写出偏序关系R的极大元、极小元。解：偏序关系R的极大元是6和20；极小元是2和3。离散数学试卷（A）卷，第5页，共5页五、证明题（每题10分，共20分）1、图G是简单图，若它的最小度数1)(kG。证明：图G有长度为k的基本通路。证明：因为G至少有k条边，所以有基本通路存在。由定理知基本通路的长度不大于n-1。设P是所有基本通路中长度最长的一条，u和v分别是基本通路的起点和终点。若P的长度不小于k,则问题已经解决。若P的长度小于k，因为kGvd)()(，从顶点v出发至少有k条边，而基本通路P上异于v的点仅有k-1个；在图G中还有另外一个点w和点v相邻接,这样我们得到一条新的基本通路P+{v,w},它比基本通路P还要长，这和P是所有基本通路中长度最长的一条这一事实相矛盾。所以G中最长的基本通路的长度一定不小于k。2、证明：有限全序集),(X必有最大元存在。证明：有限全序集),(X是偏序集，由定理知必有极大元存在，设为a。任意取Xx，因为),(X是全序集，所以ax和xa至少有一个成立。由a是极大元知xa是不可能成立的。这样由xa可得xa，即ax。所以a就是全序集),(X的最大元。得分