离散数学考卷题目和答案呈现

离散数学考卷题目和答案呈现考试时间：______分钟总分：______分姓名：______一、选择题：本大题共5小题，每小题3分，共15分。在每小题给出的四个选项中，只有一项是符合题目要求的，请将正确选项前的字母填在题后的括号内。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,4,5}(D){2,3,4,5}2.命题公式(p∧¬q)∨(¬p∧q)是？(A)重言式(B)可满足式但非重言式(C)矛盾式(D)无法判断3.设R是集合A上的一对一函数，且R的定义域为A，则R的值域最多有多少个元素？(A)1(B)|A|(C)2|A|(D)|A|^24.下列哪个关系是集合A上的等价关系？(A)R={(a,b)|a<b,a,b∈A}(B)R={(a,b)|a≡b(mod3),a,b∈A}(C)R={(a,b)|a=b^2,a,b∈A}(D)R={(a,b)|a+b是偶数,a,b∈A}5.一个无向图G有6个顶点，每个顶点的度数均为3，则该图最少有多少条边？(A)6(B)9(C)12(D)18二、填空题：本大题共5小题，每小题3分，共15分。请将答案填写在题后的横线上。6.若集合A有5个元素，集合B有4个元素，则从A到B的函数共有________个。7.关系R={(1,2),(2,3),(3,4),(4,1)}的传递闭包R*包含的有序对为________。8.设n是正整数，则C(n,0)+C(n,1)+...+C(n,n)=________。9.一个有向图G有4个顶点，其中顶点a的出度为2，入度为1；顶点b的出度为1，入度为1；顶点c的出度为0，入度为2；顶点d的出度为1，入度为0。则该图共有________条边。10.完全二叉树有7个叶节点，则该二叉树共有________个顶点。三、计算题：本大题共3小题，每小题8分，共24分。11.已知集合A={x|x是小于10的正偶数}，B={x|x是小于10的质数}，C={x|x是小于10的合数}。请计算(A-B)∩(B∪C)。12.设集合A={a,b,c}，关系R定义在A上，R={(a,a),(a,b),(b,c),(c,b)}。请判断R是否是A上的偏序关系？如果是，请写出A上的哈斯图（用文氏图或类似方式表示即可，无需画出具体图形，只需列出顶点和关系）。13.计算组合数C(10,6)，并用组合公式解释其含义（例如“从10个不同元素中取出6个元素的组合数”）。四、证明题：本大题共2小题，每小题10分，共20分。14.使用数学归纳法证明：对于任意正整数n，有1+3+5+...+(2n-1)=n^2。15.设A是一个非空集合，R是A上的关系。如果R是自反的且对称的，证明R是等价关系。试卷答案一、选择题1.(B)2.(A)3.(B)4.(B)5.(A)二、填空题6.4^57.{(1,2),(2,3),(3,4),(4,1),(1,3),(2,4),(3,1),(4,2)}8.2^n9.410.15三、计算题11.{4}12.不是偏序关系。（或：是偏序关系，哈斯图顶点为{a,b,c}，关系为{(a,a),(a,b),(b,c),(c,b)}，注意(b,c)和(c,b)同时存在，这违反了反对称性，故不是偏序关系）13.C(10,6)=10!/(6!*4!)=210。含义：从10个不同元素中取出6个元素组成一个组合的方式有210种。四、证明题14.证明：(1)基础步骤：当n=1时，左边=1，右边=1^2=1。等式成立。(2)归纳假设：假设当n=k(k≥1)时，等式成立，即1+3+5+...+(2k-1)=k^2。(3)归纳步骤：需要证明当n=k+1时等式也成立。左边=1+3+5+...+(2k-1)+(2(k+1)-1)=k^2+2k+1(根据归纳假设)=(k+1)^2右边=(k+1)^2左边=右边。因此，由数学归纳法原理，等式对于所有正整数n成立。15.证明：需要证明R是自反的、对称的、传递的。(1)自反性：对任意a∈A，根据R的自反性定义，(a,a)∈R。因此R是自反的。(2)对称性：对任意a,b∈A，如果(a,b)∈R，根据R的对称性定义，(b,a)∈R。因此R是对称的。(3)传递性：需要证明对任意a,b,c∈A，如果(a,b)∈R且(b,c)∈R，则(a,c)∈R。因为R是自反的，所以(b,b)∈R。因为R是对称的，由(b,c)∈R可得(c,b)∈R。因为R是对称的，由(b,b)∈R可得(b,a)∈R。因为R是对称的，由(c,b)∈R可得(b,c)∈R。因为R是对称的，由(b,a)∈R可得(a,b)∈R。因为R是对称的，由(b,c)∈R可得(c,b)∈R。因为R是对称的，由(b,a)∈R可得(a,b)∈R。因为R是对称的，由(a,b)∈R可得(b,a)∈R。因为R是对称的，由(b,c)∈R可得(c,b)∈R。因为R是对称的，由(a,b)∈R可得(b,a)∈R。因为R是对称的，由(b,c)∈R可得(c,b)∈R。因为R是自反的，所以(a,a)∈R。因为R是对称的，由(a,a)∈R可得(a,a)∈R。