离散数学课后试题及答案

离散数学课后试题及答案

一、单项选择题（每题2分，共10题）1.设集合A={1,2,3}，A上的关系R={(1,1),(2,2),(1,2)}，则R是（）A.自反的B.对称的C.传递的D.反自反的2.命题公式¬(p→q)的主析取范式是（）A.p∧¬qB.¬p∧qC.p∨¬qD.¬p∨q3.若A、B为集合，|A|=3，|B|=2，则从A到B的函数个数为（）A.5B.6C.8D.94.无向图G有12条边，6个3度顶点，其余顶点度数均小于3，则G至少有（）个顶点A.8B.9C.10D.115.设集合A={a,b,c}，下列（）是A的一个划分A.{{a},{b},{c}}B.{{a,b},{b,c}}C.{{a},{b,c,d}}D.{{a,b},c}6.谓词公式∀x(P(x)→∃yQ(y))中量词∀x的辖域是（）A.P(x)B.P(x)→∃yQ(y)C.∃yQ(y)D.P(x)→Q(y)7.设R是实数集，定义运算为ab=a+b-ab，则23=（）A.-1B.1C.5D.68.一个连通平面图G有5个顶点，8条边，则其面数为（）A.4B.5C.6D.79.集合A={1,2,3,4}上的关系R={(1,2),(2,3),(3,4),(4,1)}，则R的传递闭包t(R)是（）A.RB.A×AC.{(1,3),(2,4),(3,1),(4,2)}D.以上都不对10.下列（）是命题A.x+3>5B.请把门关上C.2是偶数且3是奇数D.地球外的星球上也有人二、多项选择题（每题2分，共10题）1.以下哪些是命题公式（）A.p→(q∨r)B.¬(p∧q)C.p+qD.p¬q2.设集合A={1,2,3,4}，A上的关系R={(1,2),(2,3),(3,4),(4,1)}，则R具有（）性质A.自反性B.反自反性C.对称性D.反对称性E.传递性3.以下哪些是集合A={a,b}的幂集元素（）A.∅B.{a}C.{b}D.{a,b}4.下列关于图的说法正确的是（）A.完全图的边数为n(n-1)/2B.二部图一定是平面图C.连通图的生成树是唯一的D.欧拉图一定是连通图5.设群<G,>，下列说法正确的是（）A.群中单位元唯一B.群中每个元素都有逆元C.群运算满足结合律D.群一定是阿贝尔群6.以下哪些是谓词公式中的合式公式（）A.∀x(P(x)∧Q(x))B.∃x(P(x)→Q(x))C.P(x)∃xQ(x)D.∀xP(x)∨∃yQ(y)7.集合A到集合B的函数f：A→B，若满足（），则f是双射函数A.单射B.满射C.既是单射又是满射D.一一对应8.下列哪些是布尔代数的性质（）A.交换律B.分配律C.同一律D.补元律9.设A={1,2,3}，关系R={(1,1),(2,2),(3,3),(1,2),(2,1)}，则R是（）A.等价关系B.偏序关系C.自反关系D.对称关系10.以下哪些图是平面图（）A.树B.完全二部图K2,3C.完全图K5D.环图C4三、判断题（每题2分，共10题）1.命题“如果1+1=3，那么雪是黑的”是真命题。（）2.集合A上的恒等关系IA是等价关系。（）3.若函数f：A→B是单射，则|A|≤|B|。（）4.无向图G中存在欧拉回路当且仅当G中所有顶点度数均为偶数。（）5.命题公式(p→q)∧(q→r)→(p→r)是重言式。（）6.集合A={1,2,3}，B={4,5}，则A×B={(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)}。（）7.一个群<G,>中，若a,b∈G，则(ab)-1=a-1b-1。（）8.谓词公式∀xP(x)→∃xP(x)是永真式。（）9.偏序集的哈斯图中，元素之间的连线具有传递性。（）10.若图G是连通的，则其补图G一定不连通。（）四、简答题（每题5分，共4题）1.简述集合的三种表示方法。答案：列举法，如{1,2,3}；描述法，如{x|x是偶数}；文氏图法，用图形直观表示集合关系。2.简述什么是等价关系。答案：集合A上的关系R若满足自反性（∀a∈A，(a,a)∈R）、对称性（∀a,b∈A，若(a,b)∈R则(b,a)∈R）、传递性（∀a,b,c∈A，若(a,b)∈R且(b,c)∈R则(a,c)∈R），则R是等价关系。3.简述命题公式的主合取范式与主析取范式的关系。答案：主合取范式与主析取范式是互补的。对于一个命题公式，其主合取范式中极大项的下标与主析取范式中极小项的下标合起来恰好是所有可能的下标组合。4.简述树的定义及性质。答案：树是无回路的连通无向图。性质有：边数e=顶点数v-1；任意两个顶点之间有且仅有一条路径；删去任一边，图不再连通；增加任一边，图会出现回路。五、讨论题（每题5分，共4题）1.讨论集合运算与逻辑运算之间的联系。答案：集合运算中的交、并、补分别类似于逻辑运算中的合取、析取、否定。例如集合A与B的交，类似命题p与q的合取；集合的补运算类似命题的否定。通过这种联系，可借助逻辑运算理解集合运算，反之亦然。2.讨论在软件开发中，离散数学的图论知识有哪些应用场景。答案：在软件项目管理中，可用有向图表示任务依赖关系，通过关键路径法安排任务顺序；在数据库设计的E-R图绘制中，用图表示实体和关系；在网络拓扑结构设计方面，用图描述网络连接情况，利于分析和优化。3.讨论如何判断一个代数系统是否为群，并举例说明。答案：判断一个代数系统<G,>是否为群，需验证封闭性（∀a,b∈G，ab∈G）、结合律（∀a,b,c∈G，(ab)c=a(bc)）、有单位元（∃e∈G，∀a∈G，ae=ea=a）、每个元素有逆元（∀a∈G，∃a-1∈G，aa-1=a-1a=e）。例如整数集Z关于加法运算构成群。4.讨论谓词逻辑在人工智能知识表示中的作用。答案：谓词逻辑能精确表示复杂知识，通过定义谓词和量词描述对象性质、关系及数量。如“所有的鸟都会飞”可用谓词逻辑表示。它使知识形式化，便于计算机处理推理，利于人工智能系统进行知识存储、检索和利用。答案一、单项选择题1.C2.A3.D4.B5.A6.B7.A8.B