离散数学期末试卷及答案

离散数学期末试卷及答案

一、单项选择题（共10题）1.下列语句中，哪一个是命题？A.请把门关上！B.地球外的星球上也有人C.x+5>6D.下午有会吗？答案：B2.设集合A={1,2,3}，集合B={2,3,4}，则A∩B为？A.{1,2,3,4}B.{2,3}C.{1}D.{4}答案：B3.命题公式(¬P∨Q)∧(¬Q∨R)的主析取范式中含极小项的个数为？A.2B.3C.4D.5答案：C4.设R是集合A上的二元关系，若R是自反的、对称的和传递的，则R是？A.等价关系B.偏序关系C.全序关系D.拟序关系答案：A5.一个无向图G有12条边，若每个顶点的度数均为3，则G的顶点数为？A.4B.6C.8D.12答案：C6.设函数f:A→B，g:B→C，若g∘f是双射函数，则下列说法正确的是？A.f是单射，g是满射B.f是满射，g是单射C.f和g都是双射D.f和g都是单射答案：A7.下列哪个图是欧拉图？A.有4个度数为3的顶点的图B.存在割边的图C.无奇度顶点的连通图D.有5个顶点的完全图答案：C8.设集合A={a,b,c}，A上的二元关系R={<a,a>,<b,b>,<a,c>}，则R的对称闭包s(R)为？A.{<a,a>,<b,b>,<a,c>,<c,a>}B.{<a,a>,<b,b>,<a,c>}C.{<a,a>,<b,b>,<c,c>,<a,c>}D.{<a,a>,<b,b>,<c,c>,<a,c>,<c,a>}答案：A9.命题“所有的人都是要死的”符号化为（设F(x)：x是人，G(x)：x是要死的）？A.∀x(F(x)→G(x))B.∃x(F(x)∧G(x))C.∀x(F(x)∧G(x))D.∃x(F(x)→G(x))答案：A10.设A={1,2,3}，A上的关系R={<1,2>,<2,3>,<3,1>}，则R的传递闭包t(R)是？A.{<1,2>,<2,3>,<3,1>,<1,3>,<2,1>,<3,2>}B.{<1,2>,<2,3>,<3,1>}C.{<1,1>,<2,2>,<3,3>,<1,2>,<2,3>,<3,1>}D.{<1,2>,<2,3>,<3,1>,<1,3>}答案：A二、多项选择题（共10题）1.以下哪些是命题公式？A.P∧QB.¬(P∨Q)C.P→(Q∧R)D.P+Q答案：ABC2.设集合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}}答案：ABCD3.下列关于关系的性质说法正确的是？A.若关系R是自反的，则其关系矩阵主对角线元素全为1B.若关系R是对称的，则R的关系矩阵是对称矩阵C.若关系R是传递的，当<x,y>∈R且<y,z>∈R时，必有<x,z>∈RD.反对称关系一定不是对称关系答案：ABC4.以下哪些图是简单图？A.无平行边的图B.无环的图C.既有平行边又有环的图D.无平行边且无环的图答案：ABD5.设命题P：明天下雨，Q：我去图书馆，则以下哪些命题表示“如果明天下雨，我就不去图书馆”？A.P→¬QB.¬(P∧Q)C.¬P∨¬QD.Q→¬P答案：AC6.下列哪些集合运算满足结合律？A.并运算∪B.交运算∩C.差运算-D.对称差运算⊕答案：ABD7.对于一个有n个顶点的无向图G，以下哪些说法正确？A.若G是连通图，则边数至少为n-1B.若G是完全图，则边数为n(n-1)/2C.若G是树，则边数为nD.若G是欧拉图，则顶点度数均为偶数答案：ABD8.设函数f:A→B，下列哪些说法正确？A.若f是单射，则对于任意a1,a2∈A，当a1≠a2时，f(a1)≠f(a2)B.若f是满射，则对于任意b∈B，存在a∈A使得f(a)=bC.若f是双射，则f既是单射又是满射D.若f是双射，则存在逆函数f-1:B→A答案：ABCD9.下列哪些是合式公式的特点？A.单个命题变项是合式公式B.若A是合式公式，则¬A也是合式公式C.若A和B是合式公式，则A∧B、A∨B、A→B、A↔B都是合式公式D.合式公式中括号可以随意省略答案：ABC10.设集合A={a,b}，集合B={1,2}，则从A到B的函数有？A.f1={<a,1>,<b,1>}B.f2={<a,2>,<b,2>}C.f3={<a,1>,<b,2>}D.f4={<a,2>,<b,1>}答案：ABCD三、判断题（共10题）1.命题“2是偶数且3是奇数”是真命题。答案：对2.集合A={1,2,3}，集合B={3,4,5}，则A-B={1,2}。答案：对3.若关系R是对称的，且<x,y>∈R，则<y,x>∈R。答案：对4.一个无向图中，所有顶点的度数之和等于边数的两倍。答案：对5.命题公式P→Q和¬P∨Q是等价的。答案：对6.设集合A={a,b,c}，A上的关系R={<a,b>,<b,c>}，则R的自反闭包r(R)={<a,a>,<b,b>,<c,c>,<a,b>,<b,c>}。答案：对7.完全图K5是平面图。答案：错8.若函数f:A→B是单射，且|A|=|B|，则f是双射。答案：对9.“x>5”是一个命题。答案：错10.设集合A={1,2,3}，A上的关系R={<1,1>,<2,2>,<3,3>}，则R是等价关系。答案：对四、简答题（共4题）1.简述命题公式的等价定义。两个命题公式A和B等价，是指在任何一组命题变项的赋值下，A和B的真值都相同。可以通过真值表来判断两个命题公式是否等价，若对于所有可能的赋值，A和B的真值对应相同，则A⇔B。例如，P→Q和¬P∨Q，通过列出真值表，可发现它们在各种赋值下真值都一样，所以这两个命题公式等价。2.简述集合的三种基本运算并举例说明。集合的三种基本运算为并、交、差。并运算：A∪B是由所有属于A或者属于B的元素组成的集合。例如A={1,2}，B={2,3}，则A∪B={1,2,3}。交运算：A∩B是由所有既属于A又属于B的元素组成的集合，上述例子中A∩B={2}。差运算：A-B是由所有属于A但不属于B的元素组成的集合，所以A-B={1}。3.简述关系的传递闭包的定义及求法。关系R的传递闭包t(R)是包含R且具有传递性的最小关系。求法通常有两种，一种是利用关系矩阵，通过Warshall算法来计算。另一种是通过不断添加满足传递条件的有序对来得到。例如关系R={<a,b>,<b,c>}，由于<a,b>和<b,c>存在，根据传递性要添加<a,c>，则t(R)={<a,b>,<b,c>,<a,c>}。4.简述无向图连通性的概念。无向图G中，若对于任意两个顶点u和v，都存在一条从u到v的路径，则称无向图G是连通的。路径是由顶点和边交替构成的序列。如果一个无向图不是连通的，则它可以分成多个连通分支，每个连通分支都是一个连通的子图。例如一个图由两个互不相连的三角形组成，那么这个图就不是连通的，它有两个连通分支。五、讨论题（共4题）1.讨论命题逻辑在实际生活中的应用。命题逻辑在实际生活中有广泛应用。在电路设计中，可用命题逻辑表示电路的输入输出关系，通过逻辑运算设计出满足需求的电路。在决策制定方面，可将各种条件和决策结果用命题表示，进行逻辑推理以做出合理决策。例如在交通信号灯控制中，根据不同时段、不同方向的车流量等条件，利用命题逻辑规则决定信号灯的状态。在程序设计里，条件判断语句也常基于命题逻辑，确保程序按预定逻辑执行。2.讨论集合运算与逻辑运算之间的联系。集合运算和逻辑运算有紧密联系。集合的并运算类似于逻辑的或运算，集合A∪B中的元素，只要属于A或者属于B即可，这与逻辑中P∨Q，只要P为真或者Q为真结果就为真类似。集合的交运算类似逻辑的与运算，A∩B中的元素需同时属于A和B，如同逻辑中P∧Q需P和Q同时为真结果才为真。集合的补运算类似逻辑的非运算，集合A的补集是全集中不属于A的元素，逻辑中¬P是对P的否定。3.讨论关系的性质在数据库中的应用。在数据库中，关系的性质有重要应用。自反性可用于表示实体自身的一些属性关系，比如员工表中员工与自身的联系（如员工的自我评价等）。对称性可用于处理双向关系，例如朋友关系，若A是B的朋友，B也是A的朋友。传递性在处理层次关系或依赖关系时很有用，如在组织结构中，若A领导B，B领导C，那么A间接领导C。等价关系可用于数据分类和分组，将具有相同特征的