[精品]离散数学练习试题2

离散数学练习试题2 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括 号内。错选、多选或未选均无分。 1. A. C. 2. 下列为两个命题变元P, Q的小项是 PAQA1P 〕PAQ 下列语句中是真命题的是（） B. D. 1PVQ 1PVPVQ A. 我正在说谎 B. 严禁吸烟 C. 如果123,那么雪是黑的 D.如果1 25,那么雪是黑的 3. A. C. 设P我们划船，Q我们跑步。命题“我们不能既划船又跑步”符号化为（ 1PA1Q 1 （P 分Q） B. D. IpvIq ]IpvIq 4. A. 命题公式（PA （PfQ）） fQ是（ 矛盾式 B. 蕴含式 C. 5. 重言式 命题公式］（PAQ） -R的成真指派是（ D. 等价式 A. 000, 001, 110, B. 001, 011, 101, 110, 111 C. D. 6. 全体指派 在公式V x F x, y日 y G x, y 无 中变元X是（ A. 自山变元 B. 约束变元 C. 既是自由变元，又是约束变元 D. 既不是自由变元，又不是约束变元 7.集合 A{1, 2,10}上的关系 R{x,ylxy10,xWA,yWA},则 R 的性质是（ 自反的B.对称的 A. C. 传递的、对称的 D.反自反的、传递的 若R和S是集合A上的两个关系，则下述结论正确的是（ A. 若R和S是自反的，则RCS是自反的 B. 若R和S是对称的，则R。S是对称的 C. 若R和S是反对称的，则RoS是反对称的 D.若R和S是传递的，则RUS是传递的 9. R{1, 4, 2, 3, 3, 1, 4, 3}, 则下列不是t （R）中元素的是（ A. 1, 1 B. 1, 2 C・ vl, 3 D. 1, 4 10.设 A{{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是（ C. {{4, 5}}uA D. 0GA 11在自然数集N上，下列运算是可结合的是 A. a * ba-2b B. a*bmin{d, b} C. a * b-a-b D. ab\a-b\ 12.在代数系统中，整环和域的关系是 A.整环一定是域 B.域不一定是整环 C.域一定是整环 D.域一定不是整环 下列所示的哈斯图所对应的偏序集中能构成格的是 13. A. 14. A. C. 15. 设G为有兀个结点的简单图，则有 A Gn B. D. AGn 具有4个结点的非同构的无向树的数目是 A G0 AGn B. D. A. 2 C. 4 二、填空题本大题共10小题，每小题2分，共20分 请在每小题的空格中填上正确答案。错填、不填均无分。 16. V兀Vy P 兀，y UQ .y, z A 3xP .x, y中 Vx 的辖域为, 3x 的辖域为o 17. 两个重言式的析取是式，一个重言式与一个矛盾式的析取是式。 18. 设N是自然数集合，/和g是N到N的函数，且f n 2nl, g n n2,那么复合 函数/y n go/* n o 19. 设复合函数g。/■是从A到C的函数，如果g。/■是满射，那么必是满射，如果 g。/是入射，那么必是入射。 20. 设 A{1, 2}, B{2, 3},则 A-A, A-B。 21. 设S是非空有限集，代数系统vP S, U中，其中P S为集合S的帚集，则P S 对U运算的单位元是,零元是o 22. 在立6＞中，2的阶是。 23. 设＜人，W＞是格，其中A{1, 2, 3, 4, 6, 8, 12, 24}, W为整除关系，则3的补元 是O 24. 在下图中，结点巾的度数是o 0 10 1 则 deg「V, 25. 设图 DvV, E, V{“，v2, *3, v4},若 D 的邻接矩阵 A } J J 10 0 1 , 从 Vt.至1J V4长度为 2 的路有条。 三、计算题本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题 8分，共30分 26. 已知 A{{0}, {0, 1}}, B{{0, 1}, {1}},计算 AUB, AB, A 的幕集 P A。 27. 构造命题公式PAQ -P VR的真值表。 下图给出了一个有向图。1求出它的邻接矩阵A； 2求出A, 29. 求下列公式的主合取范式和主析取范式PV ]P- QV ]Q-R 30. 设A{1, 2, 3, 4, 6, 8, 12, 24}, R为A上的整除关系，试画＜A, R＞的哈斯图, 并求A中的最大元、最小元、极大元、极小元。 四、证明题本大题共3小题，第31、32小题各6分，第33小题8分，共20分 31. 在整数集Z上定义aob a b-2m,beZ,证明＜Z,。＞是一个群。 32. R是集合A上自反和传递的关系，试证明RoRR0 33. 证明边e是图G的一条割边，当且仅当图G中不存在包含边e的简单回路。