离散数学考试题及答案

离散数学考试题及答案

一、单项选择题（每题2分，共10题）1.下列哪个是命题？（）A.x+3>5B.请关上门C.2是偶数D.明天会下雨吗2.集合A={1,2,3}，其幂集P(A)的元素个数是（）A.3B.6C.8D.93.设R是集合A上的关系，若R是自反的，则（）A.∀a∈A，(a,a)∈RB.∃a∈A，(a,a)∈RC.∀a,b∈A，若(a,b)∈R则(b,a)∈RD.∀a,b,c∈A，若(a,b)∈R且(b,c)∈R则(a,c)∈R4.命题公式¬(p→q)的主析取范式是（）A.p∧¬qB.¬p∧qC.p∨¬qD.¬p∨q5.一个无向图G有10条边，4个3度顶点，其余顶点度数均为2，则G的顶点数为（）A.8B.9C.10D.116.整数集Z上的模3同余关系是（）A.等价关系B.偏序关系C.函数关系D.以上都不是7.下列哪个图是欧拉图（）A.有5个顶点，每个顶点度数为3B.有6个顶点，每个顶点度数为4C.有7个顶点，每个顶点度数为5D.有8个顶点，每个顶点度数为68.设A={a,b,c}，B={1,2}，从A到B的函数个数是（）A.6B.8C.9D.129.谓词公式∀x(P(x)→∃yQ(y))中，变元x是（）A.自由变元B.约束变元C.既是自由变元又是约束变元D.既不是自由变元也不是约束变元10.一棵树有5个树叶，3个2度顶点，其余顶点度数为3，则树的顶点数为（）A.8B.9C.10D.11二、多项选择题（每题2分，共10题）1.以下哪些是命题公式（）A.pB.p→qC.(p∧q)∨rD.p+q2.集合A={1,2,3,4}，下列哪些是A的划分（）A.{{1},{2},{3},{4}}B.{{1,2},{3,4}}C.{{1,2,3},{4}}D.{{1},{2,3,4}}3.关系R具有传递性，以下哪些情况成立（）A.若(a,b)∈R且(b,c)∈R则(a,c)∈RB.若(a,a)∈R则(a,a)∈RC.若(a,b)∈R且(a,c)∈R则(b,c)∈RD.若(a,b)∉R且(b,c)∉R则(a,c)∉R4.以下哪些图是平面图（）A.完全图K4B.完全二分图K2,3C.完全图K5D.完全二分图K3,35.下列哪些是逻辑等价式（）A.p→q⇔¬p∨qB.p∧(q∨r)⇔(p∧q)∨(p∧r)C.¬(p∧q)⇔¬p∨¬qD.p∨(q∧r)⇔(p∨q)∧(p∨r)6.设A={a,b}，则A上的二元关系有（）A.空关系B.恒等关系C.全域关系D.关系{(a,b)}7.下列哪些关于树的说法正确（）A.树是连通无回路的图B.树的边数等于顶点数减1C.任意两个顶点之间有且仅有一条路径D.树中一定有度数为1的顶点8.谓词逻辑中，以下哪些说法正确（）A.∀x(A(x)∧B(x))⇔∀xA(x)∧∀xB(x)B.∃x(A(x)∨B(x))⇔∃xA(x)∨∃xB(x)C.∀x(A(x)→B(x))⇔∃xA(x)→∀xB(x)D.∃x(A(x)→B(x))⇔∀xA(x)→∃xB(x)9.集合运算中，正确的有（）A.A∪(B∩C)=(A∪B)∩(A∪C)B.A-(B∪C)=(A-B)∩(A-C)C.A∩(B∪C)=(A∩B)∪(A∩C)D.A∪(B-C)=(A∪B)-(A∪C)10.以下哪些图是哈密顿图（）A.完全图Kn（n≥3）B.完全二分图Kn,n（n≥2）C.有n个顶点，边数大于(n-1)(n-2)/2的简单图D.所有连通图三、判断题（每题2分，共10题）1.命题“2+3=5且4是奇数”是真命题。（）2.集合A上的恒等关系是等价关系。（）3.若关系R是对称的且传递的，则R一定是自反的。（）4.命题公式p→(q→p)是重言式。（）5.一个无向图中，所有顶点度数之和等于边数的两倍。（）6.函数f:A→B，若对于任意x1,x2∈A，x1≠x2时有f(x1)≠f(x2)，则f是满射。（）7.任何一个连通图都存在生成树。（）8.谓词公式∀xP(x)∨∃x¬P(x)是永真式。（）9.集合A和B，若A⊆B且B⊆A，则A=B。（）10.完全图K5是平面图。（）四、简答题（每题5分，共4题）1.简述集合的三种表示方法。答案：列举法，如{1,2,3}；描述法，如{x|x是偶数}；文氏图法，用图形直观表示集合关系。2.什么是关系的自反闭包？答案：设R是集合A上的关系，自反闭包r(R)是包含R的最小自反关系。通过在R中添加所有(a,a)（a∈A）得到。3.简述命题公式的真值表。答案：将命题公式中各命题变元的所有可能取值组合列出，按公式运算规则计算出对应公式的真值，形成的表格就是真值表，可判断公式类型。4.简述图的连通分量的概念。答案：无向图G的极大连通子图称为G的连通分量。一个图可能有多个连通分量，每个连通分量都是一个连通的子图。五、讨论题（每题5分，共4题）1.讨论等价关系与集合划分的联系。答案：集合A上的等价关系R可诱导出A的一个划分，划分块是等价类；反之，A的一个划分也能确定A上的一个等价关系，即元素在同一划分块中则具有等价关系。二者相互确定。2.讨论命题逻辑和谓词逻辑的区别与联系。答案：区别：命题逻辑以原子命题为基本单位，不分析内部结构；谓词逻辑深入到原子命题内部。联系：命题逻辑是谓词逻辑的基础，谓词逻辑包含命题逻辑，许多命题逻辑规则在谓词逻辑中仍适用。3.讨论图论中哈密顿图和欧拉图的判定方法及实际应用。答案：欧拉图判定：无向图所有顶点度数为偶数；哈密顿图判定较复杂，如满