离散数学期末复习题套

1、离散数学期末考试题(A)一、填空题(每小题3分，共15分)1.设，则，.2.集合，其上可定义( )个封闭的1元运算，( )个封闭的2元运算，( )个封闭的3元运算.3.命题公式的对偶式为( ).4.所有6的因数组成的集合为( ).5.不同构的5阶根树有( )棵.二、单选题(每小题3分，共15分)1.设A, B是集合，若，则(A)B = Æ (B) A = Æ (C)Æ (D)2.谓词公式中量词的辖域为(A) (B)(C) (D)和3.任意6阶群的子群的阶一定不为(A)4 (B)6 (C)2 (D)34.设是正整数，则有限布尔代数的元素个数为(A)2n (B)4n

2、(C) (D)5.对于下列序列，可构成简单无向图的度数序列为(A)3, 3, 4, 4, 5 (B)0, 1, 3, 3, 3 (C)1, 1, 2, 2, 3 (D)1, 1, 2, 2, 2三、判断题(每小题3分，共15分): 正确打“”，错误打“×”.1. 设，则是满射. ( )2. 5男5女圆桌交替就座的方式有2880种. ( )3. 设是格，对于，若且，则. ( )4. 任何树都至少2片树叶. ( )5. 无向图有生成树的充要条件是为连通图. ( )四、(10分)设和是集合，证明，并举例说明上式中不能将改为 = .五、(15分)设N是自然数集合，定义N上的关系如下：是偶数，

3、1.证明是N上的等价关系.2.求出N关于等价关系的所有等价类.3.试求出一个N到N的函数，使得.六、(10分)在实数集合R中证明下列推理的有效性:因为R中存在自然数，而所有自然数是整数，所以R中存在整数.七、(10分)设R是实数集合，令，定义上的运算如下:对于任意，证明是非Abel群.八、(10分)若简单平面图的节点数且边数，则是连通图，试证明之.离散数学期末考试题(B)一、填空题(每小题3分，共15分)1.设Æ，则Æ = ( )，Æ = ( )，中的元素个数( ).2.设集合A中有3个元素，则A上的二元关系有( )个，其中有( )个是A到A的函数.3.谓词公式中

4、量词的辖域为( ), 量词的辖域为( ).4.设，对于其上的整除关系“|”，元素( )不存在补元.5.当( )时，阶完全无向图是平面图，当为( )时，是欧拉图.二、单选题(每小题3分，共15分)1.设是集合A上的偏序关系，是的逆关系，则是A上的(A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立2.由2个命题变元和组成的不等值的命题公式的个数有(A)2 (B)4 (C)8 (D)163.设是素数且是正整数，则任意有限域的元素个数为(A) (B) (C) (D)4.设R是实数集合，是其上的小于等于关系，则(R, )是(A)有界格 (B)分配格 (C)有补格 (D)布尔格5.3阶

5、完全无向图的不同构的生成子图有(A)2 (B)3 (C)4 (D)5三、判断题(每小题3分，共15分): 正确打“”，错误打“×”.1.若一个元素既存在左逆元，又存在右逆元，则. ( )2.命题联结词不满足结合律. ( )3.在Z8 = 0，1，2，3，4，5，6，7中，2关于“×8”的逆元为4. ( )4.整环不一定是域. ( )5.任何平面图的面数. ( )四、(10分)设且，若是单射，证明是单射，并举例说明不一定是单射.五、(15分)设,上的关系,1.画出的关系图.2.判断所具有的性质.3.求出的关系矩阵.六、(10分)利用真值表求命题公式的主析取范式和主合取范式.七

6、、(10分) 边数的简单平面图，必存在节点使得.八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数.离散数学期末考试题(C)一、填空题(每小题3分，共15分)1. 若，则( )，A到B的2元关系共有( )个，A上的2元关系共有( )个.2. 设A = 1, 2, 3, f = (1,1), (2,1), (3, 1), g = (1, 1), (2, 3), (3, 2)和h = (1, 3), (2, 1), (3, 1)，则( )是单射，( )是满射，( )是双射.3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号).(1)；(2)；(3)；(4)；

7、(5).4. 设D24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).5. 设G是(7, 15)简单平面图，则G一定是( )图，且其每个面恰由( )条边围成，G的面数为( ).二、单选题(每小题3分，共15分)1. 设A, B, C是集合，则下述论断正确的是( ).(A)若A Í B， B Î C，则A Î C. (B)若A Í B， B Î C，则A Í C.(C)若A Î B， B Í C，则A Î C. (D)若A Î B， B &#

8、205; C，则A Í C. 2. 设R Í A ´ A，S Í A ´ A，则下述结论正确的是( ).(A)若R和S是自反的，则R Ç S是自反的.(B)若R和S是对称的，则是对称的.(C)若R和S是反对称的，则是反对称的.(D)若R和S是传递的，则R È S是传递的.3.在谓词逻辑中，下列各式中不正确的是( ).(A) (B)(C)(D)4. 域与整环的关系为( ).(A)整环是域 (B)域是整环 (C)整环不是域 (D) 域不是整环5.设G是(n, m)图，且G中每个节点的度数不是k就是k + 1，则G中度数为k的节点

9、个数为( ).(A). (B)n(n + 1). (C)nk. (D).三、判断题(每小题3分，共15分): 正确打“”，错误打“×”.1.设f: Z ® Z，则是单射. ( )2.设是群G1到群G2的同态映射，若G1是Abel群，则G2是Abel群. ( )3.设是格，对于，若且，则. ( )4.元素个数相同的有限布尔代数都是同构的. ( )5.设G是n (n ³ 11)阶简单图，则G或是非平面图. ( )四、(15分)设A和B是集合，使下列各式(1)； (2)；(3)成立的充要条件是什么，并给出理由.五、(10分) 设S是实数集合R上的关系，其定义如下R且是是

10、整数，证明: S是R上的等价关系.六、(10分) 求谓词公式的前束范式.七、(10分) 若n个人，每个人恰有3个朋友，则n必为偶数，试证明之.八、(10分) 利用生成函数求解递归关系.离散数学期末考试题(D)一、填空题(每小题3分，共15分)1. 设|A| = 5, |B| = 2, 则可定义A到B的函数( )个，其中有( )单射，( )个满射.2. 令G(x): x是金子，F(x): x是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ).3. 设X是非空集合，则X的幂集P(X)关于集合的È运算的单位元是( )，零元是( )，P(X)关于集合的Ç运算的单位

11、元是( ).4. 不同构的5阶无向树有( )棵.5. 对于n阶完全无向图Kn, 当n为( )时是Euler图，当n ³ ( )时是Hamilton图，当n ( )时是平面图.二、单选题(每小题3分，共15分)1. 幂集P(P(P(Æ) 为( )(A)Æ, Æ, Æ. (B)Æ, Æ, Æ, Æ. (C) Æ, Æ, Æ, Æ, Æ (D) Æ, Æ, Æ.2. 设R是集合A上的偏序关系，则是( ).(A)偏序关系 (B)等价关

12、系 (C)相容关系 (D)以上答案都不对3. 下列( )组命题公式是不等值的.(A)与. (B) 与.(C)与. (D)与.4.下列代数结构(G, *)中，( )是群.(A)G = 0, 1, 3, 5, “*”是模7加法. (B) G = Q, “*”是数的乘法.(C)G = Z, “*”是数的减法. (D) G = 1, 3, 4, 5, 9, “*”是模11乘法.5.4阶完全无向图中含3条边的不同构的生成子图有(A)3 (B)4 (C)5 (D)2三、判断题(每小题3分，共15分): 正确打“”，错误打“×”.1.函数的复合运算“”满足结合律. ( )2. 是最小功能完备联结词

13、集合. ( )3. 实数集R关于数的乘法运算“×”阿贝尔群. ( )4. 任意有限域的元素个数为2n. ( )5. 设G是n(n为奇数)简单图，则G与中度数为奇数的节点个数相同. ( )四、(10分)设A和B是集合，使成立的充要条件是什么，并给出理由.五、(10分) 设R和S是集合A上的对称关系，证明对称的充要条件是.六、(15分)分别利用(1)等值演算法和(2)真值表求命题公式的主析取范式和主合取范式.七、(10分) 设G是(n, m)无向图，若，证明G中必存在圈.八、(10分) 在初始条件f(1) = c下，求解递归关系，其中b，c为常数且，k为正整数.离散数学期末考试题(E)一

14、、填空题(每小题3分，共15分)1.设A = 2, 3, 4, a, B = 1, 3, 4, a, 则3( )A，a( )B，a( )B.2. 设A = 1, 2, 3, 4, 5上的关系R = (1, 2), (3, 4), (2, 2), S = (4, 2), (2, 5), (3, 1), (1, 3), 则 , , .3. gcd(36, 48) = ( )，lcm(36, 48) = ( ).4.任意有限布尔代数均与集合代数( )同构，其元素个数为( ).5. 不同构的5阶无向树有( )棵，不同构的5阶根树有( )棵.二、单选题(每小题3分，共15分)1. 在有理数集合Q上定义运

15、算“*”如下：对于任意x, y Î Q， = x + y xy，则Q关于*的单位元是( ).(A)x. (B)y. (C)1. (D)0. 2. 设A = 1, 2, 3, 下图分别给出了A上的两个关系R和S，则 是( )关系.GR112233GS(A)自反. (B)对称. (C)传递. (D)等价.3.令T(x): x是火车，B(x): x是汽车，F(x, y): x比y快，则“某些汽车比所有的火车慢”符号化为( ).(A).(B).(C).(D).4. 整数集合Z关于数的加法“+”和数的乘法“×”构成的代数结构(Z, +, ×)是( ).(A)域 (B)域和整

16、环 (C)整环 (D) 有零因子环5.设G是简单图，是G的补图，若，则称G为自补图. 5阶不同构的自补图个数为( ).(A)0. (B)1. (C)2. (D)3.三、判断题(每小题3分，共15分): 正确打“”，错误打“×”.1. Æ, Æ Ï P(P(Æ). ( )2. 非空1元及2元联结词集合的个数为29-1. ( )3. 群可分为Abel群和非Abel群. ( )4. 元素个数相同的有限域都是同构的. ( )5. 设G是简单图，则G或是连通图. ( )四、(15分) 设, 若是单射，证明f是单射，并举例说明g不一定是单射.五、(10分)

17、 设A = a, b, c, d上的关系R = (a, b), (b, d), (c, c), (a, c), 画出R的关系图，并求出R的自反闭包r(R)、对称闭包s(R)和传递闭包t(R).六、(10分)用CP规则证明下列推理.七、(10分) 求谓词公式的前束范式. 八、(10分)任意6个人中，一定有3个人彼此认识或有3个人彼此不认识.离散数学期末考试题(F)一、填空题(每小题3分，共15分)1. 设A = 1, 2, 3, 1, 2, 3, B = 2, 2,3, 1 , 则A B = , B A = , A Å B = .2. 实数集合R关于加法运算“+”的单位元为( ), 关

18、于乘法运算“×”的单位元为( ), 关于乘法运算“×”的零元为( ).3. 令Z(x): x是整数，O(x): x是奇数，则“不是所有整数都是奇数”符号化为( ).4. 有限域的元素个数为( ), 其中( )且( ). 5. 设G是(7, 15)简单平面图，则G一定 ( )连通图，其每个面恰由( )条边围成，G的面数为( ).二、单选题(每小题3分，共15分)1. 函数的复合运算“”满足( )(A)交换律. (B)结合律. (C)幂等律. (D)消去律.2. 设集合A中有4个元素，则A上的等价关系共有( )个.(A)13 (B)14 (C)15 (D)163.下列代数结构(G, *)中，( )是群.(A