广工离散数学试卷及答案

广工离散数学试卷及答案一、单项选择题（每题2分，共20分）1.在集合{1,2,3}上，以下哪个关系是等价关系？A.R={(1,1),(2,2),(3,3),(1,2)}B.R={(1,1),(2,2),(3,3),(2,3)}C.R={(1,1),(2,2),(3,3),(1,3)}D.R={(1,1),(2,2),(3,3),(1,2),(2,1)}2.以下哪个命题是真命题？A.所有的偶数都是整数。B.所有的整数都是偶数。C.所有的实数都是复数。D.所有的复数都是实数。3.如果一个图是连通的，那么它至少有多少个顶点？A.1B.2C.3D.44.以下哪个逻辑表达式等价于P∧(Q∨R)？A.(P∧Q)∨(P∧R)B.(P∨Q)∧(P∨R)C.(P∧Q)∨RD.P∧(P∨Q)∧(P∨R)5.以下哪个命题是永真命题？A.P→(Q→P)B.P∧¬PC.P∨¬PD.P↔¬P6.在一个有向图中，如果存在从顶点A到顶点B的路径，那么称A可达B，以下哪个图是强连通的？A.只有一个顶点的图B.所有顶点都相互可达的图C.存在至少一个顶点不可达其他顶点的图D.存在至少两个顶点，其中一个顶点不可达另一个顶点的图7.以下哪个是图的生成树？A.包含图中所有顶点的子图B.包含图中所有边的子图C.包含图中所有顶点且无环的子图D.包含图中所有顶点和边的子图8.以下哪个逻辑表达式等价于(P→Q)∧(Q→R)？A.P→RB.¬P∨RC.¬Q∨RD.P∨R9.以下哪个是二元关系？A.一个集合与其自身的笛卡尔积B.两个不同集合的笛卡尔积C.一个集合与其子集的笛卡尔积D.两个不同集合的并集10.以下哪个命题是永假命题？A.P→(Q→P)B.P∧¬PC.P∨¬PD.P↔¬P二、填空题（每题3分，共30分）1.如果集合A={1,2,3}，集合B={3,4,5}，则A∩B=______。2.命题“若x>0，则x²>0”的逆否命题是______。3.在一个有n个顶点的完全图中，边的数量是______。4.逻辑表达式(P∨Q)∧¬P的等价表达式是______。5.如果一个图的顶点集是V，边集是E，则该图的邻接矩阵是一个______矩阵。6.命题“若x>0，则x²>0”的逆命题是______。7.在一个无向图中，如果存在环，则该图是______。8.逻辑表达式(P→Q)∧(Q→R)的等价表达式是______。9.如果集合A={1,2,3}，集合B={2,3,4}，则A∪B=______。10.在一个有向图中，如果存在从顶点A到顶点B的有向路径，则称A可达B，以下哪个图是强连通的？______。三、解答题（每题10分，共50分）1.给定集合A={1,2,3}，B={3,4,5}，请找出A和B的所有子集，并计算A∪B，A∩B，A-B，B-A。2.证明命题“若x>0，则x²>0”是真命题。3.给定一个有5个顶点的无向图，顶点集为V={v1,v2,v3,v4,v5}，边集为E={(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)}，请找出该图的生成树，并说明理由。4.给定逻辑表达式P∧(Q∨R)，请使用逻辑等价变换将其转换为(P∧Q)∨(P∧R)的形式。5.给定一个有向图，顶点集为V={A,B,C,D}，边集为E={(A,B),(B,C),(C,D),(D,A)}，请判断该图是否是强连通的，并说明理由。四、附加题（每题10分，共10分）1.给定一个无向图，顶点集为V={A,B,C,D,E}，边集为E={(A,B),(B,C),(C,D),(D,E),(E,A),(A,C),(B,D)}，请找出该图的所有生成树，并计算生成树的数量。答案：一、单项选择题1.D2.A3.B4.A5.C6.B7.C8.A9.A10.B二、填空题1.{3}2.若x²≤0，则x≤03.n(n-1)/24.Q5.n×n6.若x²>0，则x>07.连通8.P→R9.{1,2,3,4}10.所有顶点都相互可达的图三、解答题1.A的子集：∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}B的子集：∅,{3},{4},{5},{3,4},{3,5},{4,5},{3,4,5}A∪B={1,2,3,4,5}A∩B={3}A-B={1,2}B-A={4,5}2.证明：假设x>0，根据实数的性质，x²≥0。又因为x>0，所以x²>0。因此，若x>0，则x²>0是真命题。3.生成树：{(v1,v2),(v2,v3),(v3,v4),(v4,v5)}。理由：该子图包含所有顶点且无环，满足生成树的定义。4.证明：P∧(Q∨R)≡(P∧Q)∨(P∧R)。根据逻辑等价变换，我们可以将P∧(Q∨R)转换为(P∧Q)∨(P∧R)的形式。5.该图是强连通的。理由：在该有向图中，每个顶点都可达其他顶点，满足强连通图的定义。四、附加题1.生成树：{(A,B),(B,C),(C,D),(D,E),(E,