离散数学试卷及答案

考证素材 一、单项选择题(本大题共 15 小题，每题 1 分，共 15 分)在每题列出的四个选项中 只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图 G，如果它的全部结点的度数都是偶数，那么它具有一条() A.汉密尔顿回路B.欧拉回路 C.汉密尔顿通路D.初级回路 2.设 G 是连通简单平面图，G 中有 11 个顶点 5 个面，则 G 中的边是() A.10B.12C.16D.14 3.在布尔代数 L 中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是() A.b∧(a∨c) B.(a∧b)∨(a’ ∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设 i 是虚数， ·是复数乘法运算，则G=是群，以下是 G 的子群是() A.B.〈{-1},· 〉 C.〈{i},· 〉D.〈{-i},· 〉 5.设 Z 为整数集，A 为集合，A 的幂集为 P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，以下系统中是代数系统的有() A.〈Z，+，/〉B.〈Z，/〉 C.〈Z，-，/〉D.〈P(A)，∩〉 6.以下各代数系统中不含有零元素的是() A.〈Q，X〉Q 是全体有理数集，X 是数的乘法运算 B.〈Mn(R),X〉,Mn(R)是全体 n 阶实矩阵集合，X 是矩阵乘法运算 C.〈Z，〉 ，Z 是整数集，定义为 xxy=xy,x,y∈Z D.〈Z，+〉 ，Z 是整数集，+是数的加法运算 7.设 A={1,2,3}，A 上二元关系 R 的关系图如下： R 具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设 A={a,b,c}， A 上二元关系 R={ 〈a,a〉 ， 〈b,b〉 〈, a,c〉 }， 则关系 R 的对称闭包 S(R)是() A.R∪IAB.RC.R∪{〈c,a〉}D.R∩IA 9.设 X={a,b,c},Ix 是 X 上恒等关系，要使 Ix∪{〈a,b〉 ， 〈b,c〉 ， 〈c,a〉 ， 〈b,a〉}∪R 为 X 上的 等价关系，R 应取() A.｛ 〈c,a〉 ， 〈a,c〉 ｝B.{〈c,b〉 ， 〈b,a〉} C.{〈c,a〉 ， 〈b,a〉}D.{〈a,c〉 ， 〈c,b〉} 10.以下式子正确的选项是() A.∈B.C.{}D.{}∈ 11.设解释 R 如下：论域 D 为实数集，a=0,f(x,y)=x-y,A(x,y):x0}，X 是数的乘法运算，是一个群，则以下集 合关于数的乘法运算构成该群的子群的是〔〕 A．{R+中的有理数}B．{R+中的无理数} C．{R+中的自然数}D．{1，2，3} 13．设是环，则以下正确的选项是〔〕 A．是交换群B．是加法群 C．对 X 是可分配的D．X 对是可分配的 14．以下各图不是欧拉图的是〔〕 15．设 G 是连通平面图，G 中有 6 个顶点 8 条边，则 G 的面的数目是〔〕 A．2 个面B．3 个面 C．4 个面D．5 个面 第二局部第二局部非选择题〔共非选择题〔共 8585 分〕分〕 二、填空题〔本大题共二、填空题〔本大题共 1010 小题，每空小题，每空 1 1 分，共分，共 2020 分〕分〕 请在每题的空格中填上正确答案。错填、不填均无分。请在每题的空格中填上正确答案。错填、不填均无分。 16．一公式为之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元 及其否认；一公式为之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否认。 17．前束范式具有形式(Q1V1)(Q2V2)…(QnVn)A，其中 Qi(1≤i≤n)为，A 为的谓 词公式。 18．设论域是{a,b,c}，则(x)S(x)等价于命题公式；(x)S(x)等价于命题公式。 19．设 R 为 A 上的关系，则 R 的自反闭包 r(R)=，对称闭包 s(R)=。 20． 某集合 A 上的二元关系 R 具有对称性， 反对称性， 自反性和传递性， 此关系 R 是， 其关系矩阵是。 21．设是一个偏序集，如果 S 中的任意两个元素都有和，则称 S 关于≤ 构成一个格。 22．设 Z 是整数集，在 Z 上定义二元运算 X 为 aXb=a+b+a·b，其中+和·是数的加法和乘 法，则代数系统的幺元是，零元是。 23．如下平面图有 2 个面 R1和 R2，其中 deg(R1)=，deg(R2)=。 24．无向图 G 具有一条欧拉回路，当且仅当G 是，并且全部结点的度数都是。 25．在以下图中，结点 v2的度数是，结点 v5的度数是。 三、计算题〔本大题共三、计算题〔本大题共 6 6 小题，第小题，第 2626——2727 小题每题小题每题 4 4 分，第分，第 2828、、3030 小题每题小题每题 5 5 分，第分，第 2929、、 3131 小题每题小题每题 6 6 分，共分，共 3030 分〕分〕 26． 〔4 分〕求出从 A={1,2}到 B={x,y}的全部函数，并指出哪些是双射函数，哪些是满射函 考证素材 考证素材 数。 27． 〔4 分〕如果论域是集合{a,b,c}，试消去给定公式中的量词：(y)(x)(x  y  0)。 28． 〔5 分〕设 A={a,b,c }，P〔A〕是 A 的幂集，是集合对称差运算。已知是群。 在群 中，①找出其幺元。②找出任一元素的逆元。③求元素x 使满足 {a}x={b}。 29． 〔6 分〕用等值演算法求公式┐(p→q)  (p→┐q)的主合取范式 30． 〔5 分〕画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。 31． 〔6 分〕在偏序集中，其中 Z={1,2,3,4,6,8,12,14}，≤是 Z 中的整除关系，求集合 D={2,3,4,6}的极大元，极小元，最大元，最小元，最小上界和最大下界。 四、证明题〔本大题共四、证明题〔本大题共 3 3 小题，第小题，第 32~3332~33 小题每题小题每题 6 6 分，第分，第 3434 小题小题 8 8 分，共分，共 2020 分〕分〕 32． 〔6 分〕用等值演算法证明((q∧s)→r)∧(s→(p∨r))(s∧(p→q))→r 33． 〔6 分〕设 n 阶无向树 G=中有 m 条边，证明 m=n- 1。 34． 〔8 分〕设 P={Ø,{1},{1,2},{1,2,3}}，是集合 P 上的包含关系。 〔1〕证明：是偏序集。 〔2〕在〔1〕的根底上证明是全序集 五、应用题五、应用题(15(15 分〕分〕 35． 〔9 分〕在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果 没有人获得知识就没有人在学校读书。 〔个体域：全部人的集合〕 考证素材