离散数学2017秋综合练习题.doc

《离散数学2017秋综合练习题.doc》由会员分享，可在线阅读，更多相关《离散数学2017秋综合练习题.doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流离散数学2017秋综合练习题.精品文档.离散数学综合练习题 一、判断下列命题是否正确如果正确，在题后括号内填“/”；否则，填“” （1）空集是任何集合的真子集 （ ）（2）是空集 （ ）（3） （ ） （4）如果，则或 （ ） （5）设集合，则 （6）设集合，则是到的关系 （ ）（7）关系的复合运算满足交换律 （ ）（8）设为集合 上的等价关系, 则也是集合 上的等价关系 （9）设是集合上的等价关系, 则当时， ( ) （10）设为集合 上的等价关系, 则（11）集合A上的任一运算对A是封闭的 （ ） （12）设A是集合，则是可结合的 （ ）

2、 （13）设是群如果对于任意，有则是阿贝尔群 （ ） （14）设a是群的元素，记则是的子群 （ ） （15）是格 （ ） （16）设a，b是格的任意两个元素，则 （17）设是布尔代数，则是格 （ ） （18）设集合，则是格 （ ）（19）设是布尔代数，则对任意，有 （20）设是布尔代数，则对任意，都有，使得（21）n阶完全图的任意两个不同结点的距离都为1. （ ）（22）在有向图中，结点到结点的有向短程即为到的有向短程 （ ） （23）强连通有向图一定是单向连通的 （ ） （24）不论无向图或有向图，初级回路一定是简单回路 （ ） （25）设图G是连通的，则任意指定G的各边方向后所得的有向图是

3、弱连通的 （ ） （26）设A是某个无向图的邻接矩阵，则(是的转置矩阵) （ ）（27）设有向图D的可达矩阵为则是单向连通的 （ ） （28）有生成树的无向图是连通的 （ ） （29）由r棵树组成的森林的结点数n与边数m有下列关系：m=n-r. （ ）（30）如果有向图D仅有一个结点的入度为0，其余结点的入度都为1，则D是有向树 （ ）（31）“如果872，则三角形有四条边”是命题 （ ） （32）设都是命题公式，则也是命题公式 （ ） （33）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下） （ ）（34）逻辑结论是正确结论 （ ）（35）设都是谓词公式，则

4、也是谓词公式 （ ）（36）设都是谓词公式，则是永真式 （ ） （37）设都是命题公式，则也是命题公式 （ ） （38）命题公式的真值分别为0，1，则的真值为0（以上是在对所包含的命题变元的某个赋值下） （ ） （39）设是个体域中某个元素，则其中都是谓词 （ ） （40） （ ）二、填空题（1）设有个元素，则集合的幂集中有 个元素。（2）设，则= .（3）设集合中元素的个数分别为，且，则集合中元素的个数 . （4）设集合，则中元素的个数为 .(5)设为集合 上的二元关系, 则 . (6)集合上的二元关系为传递的充分必要条件是 (7)设：称为母亲，：称为父亲，则： , (8)设为自然数的集合，

5、“”为自然数的小于等于关系，的子集，则的下确界为 ，下确界为 , (9)设10人集合赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李惠芝，李莉上的同姓关系为，则等价类赵= ，钱= ， (10)设 , 是 上的包含于关系，,则有 (11)设为非空有限集，代数系统中，对运算的单位元为 ，零元为 . (12)循环群的生成元为 . (13)循环群的所有子群为 . (14)代数系统中（其中为整数集合，+为普通加法），对任意的，其 . (15)在整数集合上定义运算为，则的单位元为 . (16)设,在代数系统中，的单位元为 ，可逆元为 . (17)设是群，则对于任意的，方程 和 有唯一解。 (18

6、)设是群，对任意，如果，则 . (19)设是群，为单位元，若元素满足，则 . (20)在整数集合上定义运算为，则的单位元为 . (21)设为树，中有4度，3度，2度分支点各1个，问中有 片树叶。 (22)为了从（n，m）连通无向图得到一棵生成树，必须删除G的 条边 (23)设树T中有7片树叶，3个3度结点，其余都是4度结点，问T中有 个4度结点。 (24)无环有向图的关联矩阵的所有元素之和为 (25)n阶完全图的任意两个不同结点的距离都为 (26)图为阶无向完全图，则共有 条边。 (27)设为图，则图中结点度数的总和为 。 (28)设图有6结点，若各结点的度数分别为：1，4，4，3，5，5，则

7、共有 条边。 (29)无向图是由棵树组成的森林，至少要添加 条边才能使成为一棵树。 (30)在任何图中，奇数结点必为 个。 (31)设 天气很冷，老王还是来了，则命题“虽然天气很冷, 但老王还是来了”符号化为 . (32)设天下雨， 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 . (33)设经一事, 长一智，则命题“不经一事, 不长一智”符号化为 . (34)设的真值为0，的真值为1，则命题公式的真值为 . (35)设的真值为0，的真值为1，则命题公式的真值为 . (36)由个命题变项可以组成 个不等值的命题公式。 (37)设个体域，公式在上消去量词后应为 . (38)

8、设是自然数，是奇数，是偶数，则命题“任何自然数不是奇数就是偶数” 符号化为 . (39)设是素数，是偶数，则命题“2既是偶数又是素数”符号化为 . (40)设是金子，是发光的，则命题“金子是发光的, 但发光的不一定是金子”符号化为 .三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设为实数集合，下列集合中哪一个不是空集 （ ）A. B C. D. （2）设为集合，若，则一定有 （ ）A. B C. D. （3）下列各式中不正确的是 （ ）A. B C. D. （4）设，则下列各式中错误的是 （ ）A. B C. D. （5）设，则为 （ ）A

9、. B C. D. （6）设，则的恒等关系为 （ ）A. B C. D. （7）集合上的二元关系，则的性质为 （ ）A. 自反的； B对称的； C. 反对称的； D. 反自反的.（8）设上的二元关系如下，则具有传递性的为 （ ）A. B C. D. （9）设为集合上的等价关系，对任意，其等价类为 （ ）A. 空集； B非空集； C. 是否为空集不能确定； D. .（10）映射的复合运算满足 （ ）A. 交换律 B结合律 C. 幂等律 D. 分配律（11）在整数集上，下列哪种运算是可结合的 （ ）A. B C. D. （12）设集合，下面定义的哪种运算关于集合不是封闭的A. B C. ，即的最大

10、公约数D. ，即的最小公倍数（13）下列哪个集关于减法运算是封闭的 （ ）A. （自然数集）； B；C. ； D. .（14）设是有理数集，在定义运算为，则的单位元为 （ ）A. ； B； C. 1； D. 0（15）下列代数系统中，哪一个不构成群 （ ）A. 是模11乘法；B. 是模3加法；C. 普通加法；D. 普通乘法.（16）循环群 的生成元为1和2，它们的周期为 （ ）A. 5 B6 C. 3 D. 9（17）循环群 的所有子群为 （ ）A. B C. 和 D. （18）循环群的所有生成元为 （ ）A. 1，0 B-1，2 C. 1，2 D. 1，-1（19）有限布尔代数的元素个数必定

11、等于 （ ）A. ； B； C. ； D. .（20）在下面偏序集的哈斯图中，哪一个是格 （ ）A B C D（21）仅由孤立点组成的图称为 （ ）A. 零图； B平凡图； C. 完全图； D. 多重图.（22）仅由一个孤立点组成的图称为 （ ）A. 零图； B平凡图； C.多重图； D. 子图.（23）在任何图中必有偶数个 （ ）A. 度数为偶数的结点； B度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.（24）设为有个结点的无向完全图，则的边数为 （ ）A. B C. D. （25）图和的结点和边分别存在一一对应关系是（同构）的 （ ）A. 充分条件； B必要条件；C

12、. 充分必要条件； D. 既不充分也不必要条件.（26）给定下列序列，哪一个可构成无向简单图的结点度数序列 （ ）A. BC. D. （27）在有个结点的连通图中，其边数 （ ）A. 最多条； B至少条；C. 最多条； D. 至少条.（28）是无向图的关联矩阵，是中的孤立点，则A. 对应的一行元素全为0； B对应的一行元素全为1；C. 对应的一列元素全为0； D. 对应的一列元素全为1.（29）任何无向图中结点间的连通关系是 （ ）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.（30）有向图，其中，则有向图是 （ ）A. 强连通图； B单向

13、连通图；C. 弱连通图； D. 不连通图.（31）下面哪个联结词不可交换 （ ）A. ； B； C.； D. .（32）命题公式是 （ ）A. 矛盾式； B非永真式的可满足式；C. 重言式； D. 等价式.（33）下列哪一组命题公式是等值的 （ ）A. ，； B，；C. ，； D. ，（34）下面哪一个命题是假命题 （ ）A. 如果2是偶数，那么一个公式的析取范式唯一；B如果2是偶数，那么一个公式的析取范式不唯一；C. 如果2是奇数，那么一个公式的析取范式唯一；D. 如果2是奇数，那么一个公式的析取范式不唯一.（35）设论域为整数集，下列公式中哪个值为真 （ ）A. ； B. ；C. ； D.

14、 .（36）设谓词是奇数，是偶数，谓词公式在哪个论域中是可满足的 （ ）A. 自然数； B整数； C. 实数； D. 以上均不成立.（37）命题“没有不犯错误的人”符号化为(设是人,犯错误) （ ）A. ； B.；C. ； D.（38）设个体域，公式在上消去量词后应为 （ ）A. ； B. ；C. ； D. .（39）在谓词演算中，下列各式中，哪一个是正确的 （ ）A.； B.；C.； D.（40）“学习有如逆水行舟，不进则退”。设学习如逆水行舟，学习进步，学习退步。则命题符号化为 （ ）A. ； B； C. ； D. .四、解答题1. 设 上的关系试 （1）写出的关系矩阵； （2）验证是上的

15、等价关系； （3）求出的各元素的等价类。2. 设，上的整除关系，画出的哈斯图。3. 设集合 , 是上的整除关系,画出的哈斯图；4. 设集合, 是上的整除关系，试求：（1） 集合的最大元，最小元（2） 子集和的上界、下界、上确界和下确界。5. 在下面的无向图中，回答下列问题（1）写出之间的所有初级通路； （2）写出之间的所有短程，并求； （3）判断无向图是否为欧拉图并说明理由。6. 下列各图是否为欧拉图，是否为哈密尔顿图？为什么？(1) (2)7. 下列图形中最少需添加几条边才能成为欧拉图 a a b e b d c d c （1） （2）8. 有向图如下图所示(1) 求的邻接矩阵；(2) 求中

16、长度为4的通路数和回路数，并找出中从到长度为4的所有通路。(3) 是哪类连通图？9. 设有向图，其邻接矩阵为(1) 画出有向图；(2) 中长度为4的通路有多少条？其中有多少条为回路？(3) 是那类连通图？10. 设连通图如下图所示，求它的一棵生成树a b c e f答案不唯一。五、构造下列推理的证明 1. 证明 2. 证明 3. 证明 4. 证明 5. 构造下列推理的证明：每个学术委员会的成员都是专家并且是大学生，有些成员是青年人，所以有些成员是青年专家。6.“有些病人相信所有的医生，病人都不相信骗子，所以医生都不是骗子。”在一阶逻辑中证明以上推理是正确的。六、证明题1. 设为集合上的等价关系

17、, 试证也是集合上的等价关系。2. 设为无向连通图中任意两个顶点，证明：若，则存在顶点，使得3. 证明下面四个矩阵关于矩阵乘法运算构成群。4. 设 是一个群，试证 是交换群 当且仅当对任意的 ,有 5. 设是群的元素，记，证明是的子群6. 设是一个群，取定，定义证明是一个群。离散数学综合练习题答案一、 判断下列命题是否正确（1）错误； （2）错误； （3）正确； （4）错误； （5）错误；（6）正确； （7）错误； （8）正确； （9）正确； （10）错误；（11）正确；（12）正确；（13）正确；（14）正确；（15）正确；（16）正确；（17）正确；（18）正确；（19）正确；（20）正确

18、；（21）正确；（22）错误；（23）正确；（24）正确；（25）正确；（26）正确；（27）正确；（28）正确；（29）正确；（30）错误；（31）正确；（32）错误；（33）错误；（34）错误；（35）错误；（36）正确；（37）正确；（38）正确；（39）错误；（40）错误.二、 填空题（1）； （2）； （3）3； （4）40； (5)(6) ； (7)称为外祖父； (8)5，9； (9)赵= 赵茵，赵萍，钱= 钱小滨，钱浩，钱钰，孙= 孙丽春，李= 李靖华，李秀娟，李惠芝，李莉.(10)(11) ； (12) 1和2；(13)，；(14) ； (15) 2； (16) 1，1； (1

19、7) ，； (18) ；(19) ； (20) 0； (21) 5； (22) m-n1； (23) 1； (24) 0； (25) 1；(26) ； (27) ； (28) 11； (29) ； (30) 偶数；(31) ； (32) ； (33) ； (34) 0； (35) 0；(36) ； (37)； (38) ；(39) ； (40) .三、 选择题（1） A； （2） C； （3） C； （4） B； （5） B；（6） A； （7） B； （8） D； （9） B； （10）B；（11）B； （12）D； （13）B； （14）D； （15）D；（16）C； （17）C； （18

20、）D； （19）C； （20）A；（21）A； （22）B； （23）B； （24）C； （25）B；（26）B； （27）B； （28）A； （29）B； （30）C；（31）B； （32）C； （33）B； （34）A； （35）A；（36）D； （37）D； （38）B； （39）B； （40）B.四、 解答题1. 解 （1）的关系矩阵为（2）从的关系矩阵可知：是自反的和对称的。又由于所以是传递的。 因为是自反的、对称的和传递的，所以是上的等价关系。（3） ，2. 解： 248 12 4 62 33. 解： 32 24 16 12 8 6 2 34. 解：由于是上的整除关系，所以是上的偏

21、序关系，的哈斯图为 4 6 2 3 5 1（1）集合的最大元：无，最小元：1（2）子集上界下界上确界下确界无1无161615. 解：（1）之间的所有初级通路共有7条，分别为（2）之间的长度最短的通路只有1条，即，因而它是之间唯一的短程，（3）由于无向图中有两个奇度顶点，所以无向图没有欧拉图回路，因而不是欧拉图。6. 解：图（1）中各顶点的度数为由于图（1）中各顶点的度数均为偶数，所以图（1）为欧拉图。 回路为经过图（1）中每个结点一次且仅一次的回路，所以回路为哈密尔顿回路，因此图（1）是哈密尔顿图。图（2）中各顶点的度数为由于图（2）中有两个奇度顶点，所以图（2）存在欧拉图通路，但是没有欧拉图

22、回路，因此图（2）不是欧拉图。 回路为经过图（2）中每个结点一次且仅一次的回路，所以回路为哈密尔顿回路，因此图（2）是哈密尔顿图。7. 解 由于(1)只有两个奇度结点，b,e. 因此，要由(1)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加一条边才能使(1)为欧拉图。由于(2)有 4个奇度结点，因此，要由(2)得到一个欧拉图，必须使它们的度数都为偶数。最少需添加两条边才能使(2)为欧拉图。例如，可在(1)中添加边(b,e), 在(2)中添加边(a,b),(c,d) a a b e b d c d c（1） （2）8. 解：(1) 求的邻接矩阵(2) 中长度为4的通路数为，其中对角元素之和

23、为3，中长度为4的回路有3条。由于中，所以中到长度为4的通路有4条。即，其中为简单通路。(3) 由于由可知道是单向连通图。9. 解：(1) 有向图为(2) 由于中长度为4的通路数为32。因对角元素之和为0，故中无长度为4的回路。(4) 从图可得的可达矩阵为从可知是强连通的。10. 解： a b c e f五、 构造下列推理的证明1. 证明： 前提引入； 前提引入； 析取三段论； 前提引入； 置换； 析取三段论。2. 证明 前提引入； 前提引入； 拒取式； 前提引入； 假言推理； 前提引入； 拒取式； 前提引入； 析取三段论。3. 证明 前提引入； 前提引入； 析取三段论； 前提引入； 假言推理

24、； 前提引入； 假言推理。4. 证明： 前提引入； EI； 化简； 前提引入； UI； 假言推理； 化简； 化简； 合取引入(10) EG 5. 解：设是学术委员会的成员，是专家，是大学生，是青年人。前提 结论证明： 前提引入； EI； 前提引入； UI； 化简； 假言推理； 化简； 化简； 合取引入(10) EG 6. 解：记是病人，是医生，是骗子， 相信。则上述推理符号化为前提：结论：证明： 前提引入； 存在量词消去规则； 化简规则； 前提引入； 全称量词消去规则； 假言推理规则； 全称量词消去规则； 置换； 化简规则； （10） 全称量词消去规则； （11） （10）假言三段论规则；（1

25、2） （11）全称量词引入规则；六、 证明题1. 证明：由于是自反的，所以对任意, 因而，即是自反的。 若，则,由于是对称的，所以, 从而，即是对称的。 若，则 ,由于是传递的，所以, 从而，即是传递的。 由于是自反的、对称的和传递的，所以是等价关系。2. 证明：由于的连通性，之间必存在短程，则，取为上除外的任意一点，都有之间的短程为，之间的短程为.否则，若之间存在比短的短程，则比短，这与为之间的短程矛盾。同理可证：为之间的短程。因而等于的长度加上的长度，而的长度加上的长度为的长度 ，即为，所以.3. 证明：令为由上述四个矩阵组成的集合，是矩阵乘法运算，容易验证上述四个矩阵关于矩阵乘法运算是封闭的。(1)由矩阵乘法运算知识知，是可结合的；(2)任取矩阵，由于所以矩阵是运算的单位