《离散数学》期末考试题

《离散数学》期末考试题(A) 《离散数学》期末考试题(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)3 4.设 是正整数，则有限布尔代数的元素个数为 (A)2n (B)4n (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上的关系 如下： 是偶数， 1.证明 是N上的等价关系. 2.求出N关于等价关系 的所有等价类. 3.试求出一个N到N的函数 ，使得 . 六、(10分)在实数集合R中证明下列推理的有效性: 因为R中存在自然数，而所有自然数是整数，所以R中存在整数. 七、(10分)设R是实数集合，令 ，定义 上的运算如下: 对于任意 ， ，证明 是非Abel群. 八、(10分)若简单平面图 的节点数 且边数 ，则 是连通图，试证明之. 《离散数学》期末考试题(A)参考答案 一、1. ， ， , {{a, b}}, {{c}}, {{a, b}, {c}}}. 2. . 3. . 4.{-1，-2，-3，-6，1，2，3，6}. 5.9. 二、1(C); 2(B); 3(A); 4(C); 5(D). 三、1(×); 2(√); 3(×); 4(×); 5(√). 四、证 对于任意 ，有 且 ，于是 且 ，进而 ，因此 ，所以 . 例如取 ，这时 ，进而 ，而 ， 故 . 五、证 1.对于任意 N，由于 是偶数，于是 ，因此 是N上的自反关系. 对于任意 N，若 ，则 是偶数，即 是偶数，于是 ，因此 是N上的对称关系. 对于任意 N，若 且 ，则 是偶数且 是偶数，于是 是偶数，进而 ，因此 是N上的传递关系. 综上所述， 是N上的等价关系. 2. N关于等价关系 的所有等价类为 和 . 3.令 ，显然 . 六、证 令 是自然数， 是整数，则 前提: 结论: 构造性证明如下: (1) P (2) ES(1) (3) P (4) US(3) (5) T(2)(4)I (6) EG(5) 七、证 (1)对于任意 ，有 ，进而 ，于是 ，即“∙”是 上的代数(封闭)运算. (2)结合律 对于任意 ，一方面有 ， 另一方面有 ， 于是 . (3)单位元为(1, 0) 对于任意 ，由于 且 ，于是(1, 0)是单位元. (4)每元素均存在逆元 对于任意 ，因为 且 ，而 ， 所以， 中每元素均有逆元. (5)由于 且 ，即 ，因而“∙”不可交换. 综上所述， 是非Abel群. 八、证(反证) 设 是不连通的，则 有 个连通分支 . 对于任意 ，令 是 图. 若存在 使得 ，则另外6个节点所生成的子图恰15条边. 由于 是简单图， 的边数为15，即 中含 子图. 显然， 不是平面图，这与已知 是平面图矛盾. 若存在 使得 ，则另外5个节点所生成的子图恰14条边，这不可能，因为 的边数恰为10. 于是 , 因此对于每个连通分支有 ，进而 . 因为 ，所以 ，由此得出 ，与 矛盾. 故 是连通图. 《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设 }，则 = ( )， {} = ( )， 中的元素个数 ( ). 2.设集合A中有3个元素，则A上的二元关系有( )个，其中有( )个是A到A的函数. 3.谓词公式 中量词 的辖域为( ), 量词 的辖域为( ). 4.设 ，对于其上的整除关系“|”，元素( )不存在补元. 5.当 ( )时， 阶完全无向图 是平面图，当当 为( )时， 是欧拉图. 二、单选题(每小题3分，共15分) 1.设 是集合A上的偏序关系， 是 的逆关系，则 是A上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元 和 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设 是素数且 是正整数，则任意有限域的元素个数为 (A) (B) (C) (D) 4.设R是实数集合， 是其上的小于等于关系，则(R, )是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图 的不同构的生成子图有 (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分)利用真值表求命题公式 的主析取范式和主合取范式. 七、(10分) 边数 的简单平面图 ，必存在节点 使得 . 八、(10分) 有六个数字，其中三个1，两个2，一个3，求能组成四位数的个数. 《离散数学》期末考试题(B)参考答案 一、1. {{a, b}, a, b, }， {{a, b}, a, b}，16. 2. , 27. 3. , . 4. 2, 4, 6, 12. 5. ，奇数. 二、1(B); 2(D); 3(C); 4(B); 5(C). 三、1(×); 2(√); 3(×); 4(×); 5(×). 四、证 对于任意 ，若 ，则 ，即 . 由于 是单射，因此 ，于是 是单射. 例如取 ，令 ， ，这时 是单射，而 不是单射. 五、解 1. 的关系图 如下： 2.(1)由于 ，所以 不是自反的. (2)由于 ，所以 不是反自反的. (3)因为 ，而 ，因此 不是对称的. (4)因 ，于是 不是反对称的. (5)经计算知 ，进而 是传递的. 综上所述，所给 是传递的. 3. 的关系矩阵 . 六、解 命题公式 的真值表如下: p, q, r A 1, 1, 1 1 1 1 1, 1, 0 0 1 0 1, 0, 1 1 1 1 1, 0, 0 1 1 1 0, 1, 1 1 0 0 0, 1, 0 1 1 1 0, 0, 1 1 1 1 0, 0, 0 1 1 1 由表可知， 的主析取范式为 A的主合取范式为 . 七、证 不妨设 的阶数 ，否则结论是显然的. 根据推论1知， . 若 的任意节点 的度数均有 ，由握手定理知 . 于是 ，进而 . 因此 ，与已知矛盾. 所以必存在节点 使得 . 八、解 设满足要求的r位数的个数有ar种，r = 0，1，2，…，则排列计数生成函数 , 因而 . 《离散数学》期末考试题(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) ； (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 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的节点个数为( ). (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且是 是整数}， 证明: S是R上的等价关系. 六、(10分) 求谓词公式 的前束范式. 七、(10分) 若n个人，每个人恰有3个朋友，则n必为偶数，试证明之. 八、(10分) 利用生成函数求解递归关系 . 《离散数学》期末考试题(C)参考答案 一、1. . 2.g, g, g. 3.1,2,4. 4.8，不存在，不存在. 5.连通，3，10. 二、1(C); 2(A); 3(B); 4(A); 5(D). 三、1(√); 2(×); 3(×); 4(√); 5(√). 四、证 (1) 显然， . (2)可以证明： . ()当A = B时，A – B = 且B – A = , 于是 . ()假定 ，先证明 : 对于任意 ，若 ，则 ，进而 ，根据差运算定义知 ，与 矛盾. 所以 ，因此 . 同理可证 . 故A = B. (3)容易证明： . ()显然. ()(反证)若B ，则存在 . 分两种情况讨论：若 ，则 ，由于 ，于是 ，矛盾；若 ，则 且 , 进而 ，矛盾. 证毕. 五、证 1. 对于任意x R, 因为 是整数，所以(x, x) S，即S是R上的自反关系. 2. 对于任意x, y R, 若(x, y) S，则 是整数，而 也是整数，于是(y, x) S. 3. 对于任意x, y, z R, 若(x, y) S且(y, z) S，则 是整数且 是整数. 由于 是整数，由此得出(x, z) S. 综上所述，知S是R上的等价关系. 六、解 = = = = = = = = = . 七、证 用n个节点代表n个人，两个人是朋友则在相应的两个节点之间连一条无向边，于是得到一个n阶图, 其中每个节点的度数均为3. 由于每个节点度数为3, 根据握手定理知 , 其中m为G的边数. 于是n必为偶数. 证毕. 八、解 由数列a1，a2，…，an，…，构造组合计数生成函数 . 因为 ，于是 ， 因而 ， 故 .