离散数学考研试题及答案

离散数学考研试题及答案

单项选择题（每题2分，共10题）1.下列哪个是命题公式（）A.x+1=2B.今天天气真好！C.3是偶数D.请坐好！2.集合A={1,2,3}，其幂集元素个数为（）A.3B.6C.8D.93.关系R是自反的，当且仅当（）A.恒等关系包含于RB.R包含于恒等关系C.R对称D.R传递4.无向图G有5个顶点，度数分别为2,3,3,4,4，则边数为（）A.7B.8C.9D.105.下列哪个不是联结词（）A.∧B.→C.≠D.¬6.整数集Z上的模3同余关系是（）A.等价关系B.偏序关系C.全序关系D.以上都不是7.完全图K₄的边数是（）A.4B.5C.6D.88.命题“若2+2=4，则3是奇数”的真值为（）A.真B.假C.不确定D.以上都不对9.集合A={a,b}到集合B={1,2}的函数个数为（）A.2B.4C.8D.1610.一棵树有5个叶子结点，3个2度结点，其余是3度结点，3度结点有（）个A.1B.2C.3D.4多项选择题（每题2分，共10题）1.以下哪些是命题（）A.5能被2整除B.明年国庆节是晴天C.x>3D.地球外有生命2.集合运算包括（）A.并B.交C.补D.对称差3.关系的性质有（）A.自反性B.反自反性C.对称性D.反对称性4.下列哪些是图的基本要素（）A.顶点B.边C.度数D.回路5.以下哪些是逻辑联结词（）A.与非B.或非C.异或D.条件否定6.偏序关系具有的性质（）A.自反性B.反对称性C.传递性D.对称性7.图的连通性包括（）A.连通图B.强连通图C.单向连通图D.弱连通图8.能构成格的代数系统有（）A.集合的幂集关于包含关系B.正整数集关于整除关系C.实数集关于小于等于关系D.整数集关于模5同余关系9.下列哪些是命题逻辑的推理规则（）A.前提引入规则B.结论引入规则C.置换规则D.假言推理规则10.集合A={1,2,3}上的等价关系有（）A.{<1,1>,<2,2>,<3,3>}B.{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>}C.{<1,1>,<2,2>,<3,3>,<1,3>,<3,1>}D.{<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}判断题（每题2分，共10题）1.（p∧q）→r与（p→r）∧（q→r）等价。（）2.空集是任何集合的子集。（）3.若关系R对称且传递，则一定自反。（）4.简单图中顶点度数之和等于边数的两倍。（）5.命题公式（p∨¬p）是永真式。（）6.偏序集中一定存在最大元。（）7.无向图中，连通分支数为1时是连通图。（）8.集合A上的恒等关系是等价关系。（）9.一个函数若既是单射又是满射，则是双射。（）10.树是无回路的连通图。（）简答题（每题5分，共4题）1.简述命题公式的赋值。答：给命题公式中的每个命题变元指定一个真值（0或1），称为对命题公式的一个赋值，不同赋值可使公式有不同真值。2.说明集合的包含关系与子集的联系。答：若集合A的所有元素都是集合B的元素，称A包含于B或A是B的子集。包含关系用于描述集合间这种元素归属关系，A是B子集体现A与B的包含关系。3.简述图的邻接矩阵定义。答：对于有n个顶点的图G，其邻接矩阵A是n×n矩阵，若顶点vᵢ到vⱼ有边，则A[i][j]=1（无向图时A[j][i]也为1），否则A[i][j]=0。4.简述偏序集极大元的概念。答：在偏序集<A,≤>中，若元素a∈A，不存在x∈A使得a<x，则称a为偏序集的极大元，即没有比它更大的元素（在偏序关系意义下）。讨论题（每题5分，共4题）1.讨论命题逻辑和谓词逻辑的区别与联系。答：区别：命题逻辑研究简单命题及其复合命题间关系，不涉及命题内部结构；谓词逻辑深入到命题内部分析其主谓结构。联系：命题逻辑是谓词逻辑基础，谓词逻辑包含命题逻辑内容，两者共同为逻辑推理提供工具。2.探讨关系的闭包运算及其作用。答：关系的闭包运算是在原有关系基础上添加最少元素使其满足特定性质（自反、对称、传递）。作用是在不改变太多原有关系的情况下，让关系具有所需性质，便于研究和处理与关系相关问题，如在图论、数据库关系模型等方面有应用。3.分析图论中连通性的重要性及应用场景。答：连通性很重要，反映图中顶点间能否相互到达。在通信网络中，确保节点连通保证信息传递；交通规划里，道路连通性影响交通效率；社交网络中，判断用户间能否建立联系等都依赖连通性。4.谈谈离散数学在计算机科学中的应用领域。答：在算法设计中分析算法复杂度；数据结构里定义和操作数据对象关系；数据库管理中处理数据间联系；人工智能领域用于知识表示和推理；计算机网络研究网络拓扑结构等，离散数学为计算机科学提供重要理论基础和工具。答案单项选择题1.C2.C3.A4.A5.C6.A7.C8.A9.B10.A多项选择题1.ABD2.