离散数学本科模拟试题及答案

离散数学本科模拟试题及答案考试时间：______分钟总分：______分姓名：______一、单项选择题（每题2分，共20分。下列每小题给出的四个选项中，只有一项是符合题目要求的。请将正确选项的字母填在题后的括号内。）1.设集合A={1,2,3,4}，B={2,4,6,8}，C={3,4,5,6}，则(A∩B)∪C=?(A){1,2,3,4,5,6}(B){3,4,5,6}(C){1,5,6}(D){2,4,6}2.下列语句中，哪个是命题？(A)今天天气真好！(B)x+y=5(C)请你安静一点。(D)2是偶数且3是奇数。3.设命题p:今天下雨，q:我出门不带伞。则命题“如果今天不下雨，那么我出门不带伞”可以表示为？(A)p∧¬q(B)p→¬q(C)¬p→q(D)¬p∧q4.判断下列推理是否有效：前提1:所有程序员都懂C++。前提2:李明是程序员。结论:李明懂C++。(A)有效(B)无效5.设集合A和B的基数分别为|A|=5，|B|=4，则A×B的基数|A×B|为？(A)9(B)20(C)8(D)16.下列关系图中，哪个图定义了一个函数？(A)O→A(B)O→A,B;P→B(C)O→A,B;P→C(D)O→A;O→B;P→C7.设R是集合A={1,2,3}上的关系，R={(1,2),(2,3)}。则关系R的传递闭包R*是？(A){(1,2),(2,3)}(B){(1,2),(2,3),(1,3)}(C){(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}(D){(1,3)}8.设G是一个具有n个顶点的无向简单图，其边数m=n(n-1)/2，则G是？(A)完全图(B)树(C)二分图(D)图9.下列哪个图是欧拉图？(A)只有0个奇度顶点的连通图(B)只有2个奇度顶点的连通图(C)任何顶点的度数都大于等于4的连通图(D)存在割点的连通图10.计算组合数C(10,6)的值？(A)210(B)84(C)462(D)15二、多项选择题（每题3分，共15分。下列每小题给出的四个选项中，至少有两项是符合题目要求的。请将正确选项的字母填在题后的括号内。多选、错选、少选均不得分。）1.下列哪个集合运算满足交换律？(A)并集(∪)(B)交集(∩)(C)补集(')(D)差集(-)2.下列逻辑等价式中，哪个是正确的？(A)¬(p∧q)↔¬p∧¬q(B)p∨¬p↔True(C)(p→q)↔¬p∨q(D)(p∧q)→r↔p→(q→r)3.设R是集合A上的关系。下列哪个条件是R为等价关系？(A)自反性：对于所有a∈A，(a,a)∈R(B)对称性：对于所有a,b∈A，如果(a,b)∈R，则(b,a)∈R(C)传递性：对于所有a,b,c∈A，如果(a,b)∈R且(b,c)∈R，则(a,c)∈R(D)反对称性：对于所有a,b∈A，如果(a,b)∈R且(b,a)∈R，则a=b4.下列关于树的说法中，哪些是正确的？(A)树是连通且无环的图(B)树的任意两个顶点之间都有唯一的路径相连(C)树的顶点数n和边数m满足m=n-1(D)树至少有两个叶子顶点（假设顶点数大于等于2）5.在以下关于图论问题的描述中，哪些是NP完全问题？(A)判断一个无向图是否是二分图(B)判断一个有向图是否是强连通的(C)判断一个无向图是否包含哈密顿回路(D)判断一个有向图是否包含哈密顿路径三、判断题（每题1分，共10分。请将“正确”或“错误”填在题后的括号内。）1.如果一个集合包含n个元素，则它的所有子集共有2^n个。（）2.命题公式(p∨q)∧(¬p∨r)是重言式。（）3.关系R={(a,b)|a<b}在集合A={1,2,3}上是偏序关系。（）4.任何包含n个顶点的连通无向简单图，其边数至少为n-1。（）5.如果一个图是欧拉图，那么它一定是连通的。（）6.组合数C(n,k)表示从n个不同元素中取出k个元素的排列数。（）7.哈密顿回路是经过图中所有顶点恰好一次的简单回路。（）8.任何命题公式都至少有一个成真赋值和一个成假赋值（假设公式中至少有一个命题变元）。（）9.一个群G的单位元是唯一的。（）10.空集是任何集合的子集。（）四、计算题（每题8分，共32分。）1.设集合A={a,b,c},B={1,2}。计算A×(B∪C)，其中C={x,y}。2.写出命题公式p∧(q∨¬r)的主析取范式。3.设集合A={1,2,3,4}上的关系R={(1,2),(2,3),(3,4),(4,1),(1,4)}。判断R是否是等价关系？如果是，写出所有等价类；如果不是，说明理由。4.设G是一个具有6个顶点的无向简单图，其每个顶点的度数均为3。G至少有多少条边？G一定连通吗？请说明理由。五、证明题（每题10分，共20分。）1.证明：对于任意集合A，有A⊆A∪B。2.证明：命题公式(p→q)∨(q→p)是重言式。试卷答案一、单项选择题1.(A)解析：A∩B={2,4}，(A∩B)∪C={2,4}∪{3,4,5,6}={1,2,3,4,5,6}。2.(D)解析：选项D是一个具有明确真假的陈述句。选项A是感叹句，B是包含变量的命题，C是祈使句。3.(B)解析：“今天不下雨”是¬p，“我出门不带伞”是¬q。原命题“如果今天不下雨，那么我出门不带伞”是¬p→¬q。根据逻辑等价式，¬p→¬q↔p→q。4.(A)解析：推理形式为∀x(P(x)→Q(x)),P(a)⊢Q(a)。这是有效的直接推理形式。5.(B)解析：根据笛卡尔积定义，|A×B|=|A|×|B|=5×4=20。6.(C)解析：定义函数要求对于定义域中的每一个元素，必须有唯一的一个值与之对应。选项C中，O有两个输出（A和B），不满足唯一性。7.(B)解析：R*是包含R且最小的传递关系。需要添加(1,3)使其满足传递性：(1,3)∈R*当且仅当((1,2)∈R∧(2,3)∈R)∨(1,3)∈R。因为(1,2)∈R且(2,3)∈R，所以(1,3)∈R*。R*={(1,2),(2,3),(1,3)}。8.(A)解析：边数m=n(n-1)/2是完全图K_n的特征。当n=4时，m=4(4-1)/2=6。题目描述符合完全图K_4。9.(A)解析：根据欧拉定理，一个无向连通图是欧拉图当且仅当所有顶点的度数都是偶数。选项A满足此条件。10.(A)解析：C(10,6)=C(10,4)=10!/(4!*6!)=(10*9*8*7)/(4*3*2*1)=210。二、多项选择题1.(A),(B)解析：并集和交集满足交换律：A∪B=B∪A，A∩B=B∩A。补集不满足：A'≠B'（例如A={1},B={2}）。差集不满足：A-B≠B-A。2.(B),(C),(D)解析：A错误，¬(p∧q)↔¬p∨¬q（德摩根律）。B正确。C正确，这是蕴含式的定义。D正确，这是蕴含式蕴涵律的一种形式。3.(A),(B),(C)解析：等价关系必须满足自反性、对称性和传递性。反身性是每个元素都与自身相关。对称性是关系是双向的。传递性是关系链可以传递。反身性不是群的定义要求。4.(A),(B),(C)解析：树是定义明确的无环连通图，所以A正确。连通性保证任意顶点间路径存在，所以B正确。边数等于顶点数减一(m=n-1)是树的基本性质，所以C正确。D错误，树可以只有一个顶点（此时无边），或者有两个顶点（一条边），此时只有一个叶子顶点。5.(C),(D)解析：判断无向图是否包含哈密顿回路和判断有向图是否包含哈密顿路径都是经典的NP完全问题。判断无向图是否是二分图是P问题。判断有向图是否是强连通是P问题。三、判断题1.正确解析：集合A的子集数量等于2的A的基数次方，即2^n。2.正确解析：公式(p∨q)∧(¬p∨r)的真值表如下：p|q|r|¬p|¬p∨r|p∨q|(¬p∨r)∧(p∨q)|||-|||--T|T|T|F|T|T|TT|T|F|F|T|T|TT|F|T|F|T|T|TT|F|F|F|F|T|FF|T|T|T|T|T|TF|T|F|T|T|T|TF|F|T|T|T|F|FF|F|F|T|T|F|F所有行最后一列都为T，故为重言式。3.正确解析：检查自反性：(a,a)不在R中，但根据定义a<a不成立，所以自反性不满足。检查其他性质也不需要，因为不满足自反性，故不是偏序关系。（修正：原题意可能是指a≤b定义为a<b，此时关系是严格偏序，满足传递性但通常不满足自反性。如果题目意图是标准偏序关系“≤”，则(1,1),(2,2),(3,3)不在R中。假设题目意图是a≤b定义为a<b，则R={(1,2),(2,3),(3,4),(4,1),(1,4)}。此时：反自反性：没有a<a，满足。反对称性：存在(a,b)和(b,a)同时成立的情况，如(4,1)和(1,4)，且a≠b，不满足。传递性：存在(a,b)和(b,c)但无(a,c)，如(4,1)和(1,4)，但无(4,4)，不满足。所以不是偏序关系。如果题目意图是标准偏序关系“≤”，则R中缺少(1,1),(2,2),(3,3),(4,4)。此时：反自反性：满足。反对称性：满足。传递性：不满足，例如(4,1)和(1,4)存在，但无(4,4)，且(4,1)和(1,3)存在，但无(4,3)。所以也不是偏序关系。考虑到判断题通常考察基础定义，且关系定义可能略有歧义，若按a≤b定义为a<b，则R={(1,2),(2,3),(3,4),(4,1),(1,4)}，不满足传递性，错误。若按a≤b定义为a=b或a<b，则R中缺少(1,1),(2,2),(3,3),(4,4)，错误。此题表述可能存在问题。假设题目意图是R={(a,b)|a≤b}，则A={1,2,3,4}，R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}，此时R是偏序关系。题目原表述R={(1,2),(2,3),(3,4),(4,1),(1,4)}不构成偏序关系。此题作为“正确”答案存在问题。为符合答案格式，此处标记为“错误”可能更符合严谨性，但按指令标记“正确”并指出其问题。错误解析：见上方分析，关系R={(1,2),(2,3),(3,4),(4,1),(1,4)}不是偏序关系。它不满足反自反性（例如(1,1)不在R中），不满足反对称性（例如(4,1)和(1,4)都在R中且4≠1），也不满足传递性（例如(4,1)和(1,4)在R中，但(4,4)不在R中）。因此该关系不是偏序关系。4.正确解析：一个具有n个顶点的连通图至少需要n-1条边才能保持连通（例如，可以构造一个树）。如果少于n-1条边，根据极小连通图性质，移除任何一条边都会使其不连通。5.正确解析：欧拉图定义要求存在一条经过所有边恰好一次的闭回路。这意味着图必须连通。如果图不连通，则无法从某一部分到达另一部分，无法完成遍历所有边。6.错误解析：组合数C(n,k)表示从n个不同元素中取出k个元素，组成一个无序的集合的个数。排列数P(n,k)表示从n个不同元素中取出k个元素，组成一个有序的序列的个数。7.正确解析：这是哈密顿回路的标准定义。它要求经过每个顶点恰好一次，并且起点和终点相同，形成一个回路。8.正确解析：对于一个n变量的命题公式，其有2^n个不同的赋值组合。对于每个赋值组合，公式都有一个真值（True或False）。如果公式至少有一个变元，那么存在至少一种赋值使公式为True（例如全为False时，p为False，¬p为True，p∨¬p为True），也存在至少一种赋值使公式为False（例如全为True时，p为True，¬p为False，p∨¬p为True，但如果公式是p→¬p，则全为True时为False；更一般的，如果公式包含至少一个变元，总存在赋值使其为False，例如p为True,¬p为False时，p∨¬p为True；如果公式是p，赋值为p=False，则公式为False）。对于只有一个命题变元p的公式，当p=True时p为True；当p=False时¬p为True，p∨¬p为True。所以总有一个赋值为True，一个为False（当p=True时，¬p=False，p∨¬p=True；当p=False时，¬p=True，p∨¬p=True）。对于更复杂或只有一个变元的简单公式，如p,¬p,p∧q,p∨¬p，确实只有一个赋值使得公式为假。更严谨地说，对于任何非永假式（至少有一个赋值使之为真）的命题公式，都存在至少一个赋值使其为假。对于永假式（所有赋值都为假），则不存在赋值使其为真（但存在赋值使其为假）。题目说“至少有一个成真赋值和一个成假赋值”，对于至少有一个变元的公式，成假赋值一定存在（除非是永真式，但永真式没有成假赋值，与题意矛盾）。对于只有一个变元的永真式p，没有成假赋值。对于只有一个变元的永假式¬p，没有成真赋值。因此该陈述对“公式中至少有一个命题变元”的公式成立，对单个永真/永假式不成立。考虑到判断题通常考察普遍情况，且永真/永假式相对少见，此题表述可能存在不严谨之处。但若题目隐含“非永假式”，则该陈述正确。错误解析：见上方分析，该陈述对所有至少有一个变元的命题公式成立，但存在单个永真式（如p）没有成假赋值，单个永假式（如¬p）没有成真赋值。因此该陈述整体上不正确。9.正确解析：群的定义中包含一个二元运算*，满足封闭性、结合律、存在单位元e，以及存在每个元素的逆元a^(-1)。单位元e的性质是对于群中的任意元素a，有e*a=a*e=a。因为群中乘法运算是封闭的，所以e*a和a*e必须也是群中的元素。由于它们都等于a，这表明群中的单位元是唯一的。10.正确解析：空集∅是任何集合A的子集。根据子集定义，如果A中的所有元素都属于B，则A⊆B。对于空集，它没有元素，因此“所有元素都属于B”这个条件对于空集总是成立的（因为没有元素可以违反这个条件）。所以∅⊆A对任何集合A都成立。四、计算题1.解：B∪C={1,2}∪{x,y}={1,2,x,y}。A×(B∪C)=A×{1,2,x,y}={(a,1),(a,2),(a,x),(a,y),(b,1),(b,2),(b,x),(b,y),(c,1),(c,2),(c,x),(c,y)}。2.解：公式p∧(q∨¬r)的真值表如下：p|q|r|¬r|q∨¬r|p∧(q∨¬r)|||-||--T|T|T|F|T|TT|T|F|T|T|TT|F|T|F|F|FT|F|F|T|T|TF|T|T|F|T|FF|T|F|T|T|FF|F|T|F|F|FF|F|F|T|T|F主析取范式是包含所有使公式为真的赋值对应的极小项的析取（或）。极小项：pqr,pqr',pq'r',p'qr'主析取范式：pqr∨pqr'∨pq'r'∨p'qr'3.解：判断R是否是等价关系：-自反性：检查(a,a)∈R对所有a∈A。只有(1,1),(2,2),(3,3),(4,4)不在R中，所以R不是自反的。-对称性：检查如果(a,b)∈R，则(b,a)∈R。例如(1,4)∈R，但(4,1)∉R。所以R不是对称的。-传递性：检查如果(a,b)∈R且(b,c)∈R，则(a,c)∈R。例如(1,2)∈R且(2,3)∈R，但(1,3)∉R。所以R不是传递的。因为R不满足自反性、对称性和传递性中的任何一个，所以R不是等价关系。结论：R不是等价关系。4.解：设G是具有n=6个顶点，每个顶点度数d=3的无向简单图。-根据握手定理（HandshakingLemma），图的所有顶点度数之和等于边数的2倍。即Σv∈Vdeg(v)=2m。-由于每个顶点度数为3，且共有n=6个顶点，所以Σv∈Vdeg(v)=6*3=18。-因此，18=2m，解得m=9。-G至少有多少条边？对于n=6的图，最小边数是0（空图），但度数都为3的图不能是空图。一个n=6度数都为3的图至少