离散数学本科课程试题及答案

离散数学本科课程试题及答案考试时间：______分钟总分：______分姓名：______一、单项选择题（每题2分，共20分。在每小题的四个选项中，只有一个是正确的，请将正确选项的字母填在题后的括号内）1.设集合A={1,2,3},B={2,3,4},C={3,4,5}，则(A∪B)∩C=?(A){1,2,3,4}(B){3}(C){1,2,3,4,5}(D){2,3,4}2.下列哪个语句是命题？(A)今天天气真好！(B)x+y=5(C)请你安静一点。(D)2是偶数且3是奇数。3.设命题p:今天下雨，q:我会去图书馆。用逻辑连接词“∧”(与)连接p和q，得到的复合命题是？(A)今天下雨或我会去图书馆。(B)如果今天下雨，那么我会去图书馆。(C)今天下雨且我会去图书馆。(D)今天不下雨或我会去图书馆。4.命题公式(p∨q)→¬p是？(A)重言式(B)可满足式但不是重言式(C)矛盾式(D)无法判断5.设集合A有5个元素，集合B有3个元素，则从A到B的不同函数个数是？(A)15(B)3^5(C)5^3(D)86.下列哪个图是欧拉图？(A)(B)(C)(D)7.完全二部图K_3,3是？(A)连通图(B)欧拉图(C)哈密顿图(D)既是欧拉图也是哈密顿图8.设集合A={a,b,c}，A上的关系R={(a,a),(a,b),(b,c)}，则关系R不是？(A)自反关系(B)反自反关系(C)传递关系(D)以上都不是9.下列哪个是等价关系？(A)整数集上的“大于”关系(B)集合A上的恒等关系(C)实数集上的“不等于”关系(D)整数集上的“整除”关系10.下列哪个数是可判定的？(A)判断一个给定的图是否是哈密顿图(B)判断一个给定的命题公式是否是重言式(C)判断一个给定的数是否是素数(D)判断一个给定的图是否是平面图二、多项选择题（每题3分，共15分。在每小题的五个选项中，有多个是正确的，请将所有正确选项的字母填在题后的括号内，多选、错选、漏选均不得分）1.设集合A={1,2},B={2,3,4},C={3,4}，则下列哪个式子是真的？(A)A⊆(B∪C)(B)A⊆B(C)A⊆C(D)A⊆(B∩C)(E)A∩B={2}2.下列哪些是命题公式？(A)p∨q(B)p→q∧r(C)p∨(q→r)(D)(p∧q)∨¬r(E)(∧p)q3.设集合A={1,2,3}，A上的关系R={(1,1),(1,2),(2,3)}，则关系R具有哪些性质？(A)自反性(B)反自反性(C)传递性(D)对称性(E)antisymmetry4.下列哪些是图论中的基本概念？(A)顶点(B)边(C)链(D)回路(E)颜色5.下列哪些数是无穷集？(A)自然数集(B)整数集(C)有理数集(D)实数集(E)素数集三、判断题（每题1分，共10分。请将“正确”或“错误”填在题后的括号内）1.空集是任何集合的子集。（）2.命题公式p∧q与p∨q的真值表相同。（）3.如果一个函数是双射，那么它的逆函数也存在。（）4.任何欧拉图都存在欧拉回路。（）5.无向图G是树，当且仅当G是连通且无环的图。（）6.关系矩阵是对称矩阵，当且仅当该关系是对称关系。（）7.等价关系一定是自反的、对称的、传递的。（）8.可判定问题是可以在有限步骤内确定解是否存在的问题。（）9.哈密顿图是存在经过所有顶点恰好一次的回路。（）10.对一个图进行着色是指用不同颜色给图的顶点着色，使得相邻顶点颜色不同。（）四、计算题（每题5分，共20分）1.化简命题公式：(p∨q)∧(¬p∨r)∧(q∨¬r)。2.设集合A={1,2,3,4},B={a,b}，构造一个从A到B的满射函数。3.给定有向图G如下（请自行绘制该图，顶点为a,b,c,d，边为：<u>a,b</u>,<u>b,c</u>,<u>c,a</u>,<u>a,d</u>），判断G是否有欧拉路径，如果有，请给出一条。4.设集合A={1,2,3}，A上的关系R={(1,1),(1,2),(2,3),(3,1)}，写出关系R的矩阵表示。五、证明题（每题10分，共30分）1.证明：命题公式(p→q)→p是重言式。2.证明：如果一个图是哈密顿图，那么它也是连通图。3.证明：集合A上的恒等关系R={(x,x)|x∈A}是等价关系。试卷答案一、单项选择题1.(B)2.(D)3.(C)4.(A)5.(B)6.(C)*(注：此处需根据实际图示判断，假设(C)为连通无奇数度顶点的图)*7.(C)*(注：此处需根据实际图示判断，假设(C)为连通且每个顶点度数为偶数的图)*8.(A)9.(B)10.(B)二、多项选择题1.(B,D,E)2.(A,B,C,D)3.(B,C,E)4.(A,B,C,D)5.(A,B,C,D)三、判断题1.正确2.错误3.正确4.正确5.正确6.正确7.正确8.正确9.正确10.正确四、计算题1.解析思路：利用逻辑等价式进行化简。可以使用分配律、德摩根律、结合律、交换律等。答案：r2.解析思路：构造函数需保证B的每个元素都是函数值的像。例如：f(1)=a,f(2)=a,f(3)=b,f(4)=b。答案：例如f(1)=a,f(2)=a,f(3)=b,f(4)=b。3.解析思路：判断欧拉路径需检查奇数度顶点个数。本题奇数度顶点为b(度2),d(度1)。存在欧拉路径，路径可从度数为1的顶点d开始，经过边<a,d>,<d,b>,<b,c>,<c,a>。答案：存在欧拉路径，例如：d,b,c,a。4.解析思路：关系矩阵的主对角线元素应为1（自反性），非对角线元素为0或1。根据关系定义填充。答案：[[1,1,0],[0,0,1],[1,0,0]]五、证明题1.解析思路：构造真值表，计算命题公式在所有可能真值组合下的真值，验证其是否恒为真。证明：真值表如下：|p|q|p→q|(p→q)→p|||||-||T|T|T|T||T|F|F|T||F|T|T|F||F|F|T|T|由于最后一列全为T，故(p→q)→p是重言式。2.解析思路：利用哈密顿图的定义，即存在经过所有顶点恰好一次的回路。证明该回路存在，则图必然连通。证明：设G是哈密顿图，存在哈密顿回路H。H包含G的所有顶点。对于G中任意两个顶点u和v，它们都属于H。H是一条连通所有顶点的简单回路，故u和v之间存在路径。因此，G是连通图。3.解析思路：分别验证自反性、对称性、传递性。证明：(1)自反性：对于任意x∈A，(x,x)∈A。因为R包含所有形如