2022年《离散数学》试题及答案解析.docx

名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版一、填空题1 设集合 A,B,其中 A1,2,3, B= 1,2, 就 A - B _; A - B _ . 2. 设有限集合 A, |A| = n, 就 | A× A| = _.3. 设集合 A = a, b, B = 1, 2, 就从 A 到 B的全部映射是 _ _, 其中双射的是 _. 4. 已知命题公式GPQR,就 G的主析取范式是_ _. 6 设 A、 B为两个集合 , A= 1,2,4, B = 3,4, 就从 A B_; A B _;A B _ . 7. 设 R是集合 A 上的等价关系, 就 R所具有的关系的三个特性是_, _, _. 8. 设命题公式GPQ R ,就使公式G为真的说明有 _ ,_, _. 9. 设集合 A1,2,3,4, A上的关系 R1= 1,4,2,3,3,2, R2= 2,1,3,2,4,3, 就 R1.R2 = _,R R1 2 =_. 2.R1 =_, 10. 设有限集 A, B,|A| = m, |B| = n, 就| | A B| = _. 11 设 A,B,R 是三个集合,其中 R是实数集, A = x | -1x1, x R, B = x | 0x < 2, x R, 就 A-B = _ , B-A = _ , AB = _ , . 13. 设集合 A2, 3, 4, 5, 6 ,R是 A 上的整除,就 R以集合形式 列举法 记为 _ _ . 14. 设一阶规律公式G = xPxxQx ,就 G的前束范式是 _ _. 16. 设谓词的定义域为 a, b, 将表达式xRx xSx 中量词排除,写成与之对应的命题公式是_. 17. 设集合 A1, 2, 3, 4,A 上的二元关系R1,1,1,2,2,3, S1,3,2,3,3,2；就 RS专业资料学习参考细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页,共 8 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版_, R 2_. 二、挑选题1设集合 A=2,a,3,4,B = a,3,4,1,E为全集,就以下命题正确选项 ；2A2A BaA CaB E Da,1,3,4B. 设集合A=1,2,3,A上的关系R1,1,2,2,2,3,3,2,3,3,就R 不具备 . A 自反性 B 传递性 C 对称性 D 反对称性3 设半序集 A, 关系 的哈斯图如下所示,如 A 的子集 B = 2,3,4,5, 就元素 6 为 B 的 ；A 下界 B 上界 C 最小上界 D 以上答案都不对 6 4 以下语句中, 是命题；5 A 请把门关上 B 地球外的星球上也有人 3 4 Cx + 5 > 6 D 下午有会吗？2 5 设 I 是如下一个说明：Da,b, P a , a Pa, b Pb, a Pb, b 1 1 0 1 0就在说明 I 下取真值为 1 的公式是 . A x yPx,y B x yPx,y C xPx,x D x yPx,y. 6. 如供挑选答案中的数值表示一个简洁图中各个顶点的度,能画出图的是 . A1,2,2,3,4,5 B1,2,3,4,5,5 C1,1,1,2,3 D2,3,3,4,5,6. 7. 设 G、H是一阶规律公式,P是一个谓词, G xPx, HxPx, 就一阶规律公式GH是 . A 恒真的 B 恒假的 C 可满意的 D 前束范式 . 8 设命题公式 GP Q,HP Q P,就 G与 H的关系是 ；AG H BH G CG H D 以上都不是 . 9 设 A, B 为集合,当 时 ABB. AA B BA B CB A DA B. 10 设集合 A = 1,2,3,4, A上的关系 R 1,1,2,3,2,4,3,4, 就 R具有 ；A 自反性 B 传递性 C 对称性 D 以上答案都不对11 以下关于集合的表示中正确的为 ；Aa a,b,c Ba a,b,c C a,b,c Da,b a,b,c 12 命题 xGx 取真值 1 的充分必要条件是 . A 对任意 x,Gx 都取真值 1. B有一个 x0,使 Gx0 取真值 1. C 有某些 x,使 Gx0 取真值 1. D以上答案都不对. 13. 设 G是连通平面图,有5 个顶点, 6 个面,就 G的边数是 . A 9条 B 5条0 C 6条 D 11条. . 111115. 设图 G的相邻矩阵为10100,就 G的顶点数与边数分别为11011A4, 5 B5, 6 1010110110C4, 10 D5, 8. 三、运算证明题专业资料学习参考细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 8 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版1. 设集合 A1, 2, 3, 4, 6, 8, 9, 12,R为整除关系；1 画出半序集 A,R 的哈斯图；2 写出 A的子集 B = 3,6,9,12的上界,下界,最小上界,最大下界；3 写出 A的最大元,最小元,极大元,微小元；2.设集合 A1, 2, 3, 4,A 上的关系 R x,y | x, yA 且 x y, 求1 画出 R的关系图；2 写出 R的关系矩阵 . 3. 设 R是实数集合, , 是 R上的三个映射,x = x+3, x = 2x, x x/4,试求复合映射 ., . , . , ., . . . 4. 设 I 是如下一个说明：D = 2, 3, a b f 2 f 3 P2, 2 P2, 3 P3, 2 P3, 3 3 2 3 2 0 0 1 1 试求 1 P a, f a P b, f b; 2 x y P y, x. 5. 设集合 A1, 2, 4, 6, 8, 12, R为 A 上整除关系；1 画出半序集 A,R 的哈斯图；2 写出 A的最大元,最小元,极大元,微小元；3 写出 A的子集 B = 4, 6, 8, 12 的上界,下界,最小上界,最大下界 . 6. 设命题公式 G = PQQ PR, 求 G的主析取范式；7. 9 分 设一阶规律公式：G = xP x yQ y xR x ,把 G化成前束范式 . 9. 设 R是集合 A = a, b, c, d. R是 A 上的二元关系 , R = a,b, b,a, b,c, c,d, 1 求出 rR, sR, tR；2 画出 rR, sR, tR 的关系图 . 11. 通过求主析取范式判定以下命题公式是否等价：1 G = P QPQR PR 2 H = P QR Q13. 设 R和 S 是集合 A a, b, c, d 上的关系,其中S a, b, b, c, b, d, d, d. 1 试写出 R和 S 的关系矩阵；2 运算 R. S, R S, R1, S1. R 1. 四、证明题参考答案一、填空题1. 3; 3,1,3,2,3,1,2,3. 专业资料学习参考R a, a, a, c, b, c, c, d, 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页,共 8 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版2.2n .3= a,1, b,2, 4= a,2, b,1; 3.1= a,1, b,1, 2= a,2, b,2,3, 4.R; x | 0 x1, xR. 4.PQR.5.12, 3. 6.4, 1, 2, 3, 4, 1, 2. 7.自反性；对称性；传递性.8.1, 0, 0, 1, 0, 1, 1, 1, 0.9.1,3,2,2,3,1; 2,4,3,3,4,2; 2,2,3,3.10. 2 m n.11. x | -1x < 0, xR; x | 1 < x < 2, x12. 12; 6.13. 2, 2,2, 4,2, 6,3, 3,3, 6,4, 4,5, 5,6, 6.14.xPx Qx.15. 21.16. Ra Rb Sa Sb.17. 1, 3,2, 2; 1, 1,1, 2,1, 3. 二、挑选题1. C. 2. D. 3. B. 4. B. 5. D. 6. C. 7. C. 8. A. 9. D. 10. B. 11. B. 13. A. 14. A. 15. D 三、运算证明题1. 84126391 212 B 无上界,也无最小上界；下界 1, 3; 最大下界是 3. 3 A 无最大元,最小元是 1,极大元 8, 12, 90+; 微小元是 1. 2. R = 1,1,2,1,2,2,3,1,3,2,3,3,4,1,4,2,4,3,4,4. 1 14专业资料学习参考细心整理归纳 精选学习资料 23 第 4 页,共 8 页 - - - - - - - - - - - - - - - - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版10001 1 0 02 M R1 1 1 01 1 1 13. 1 . x x+3 2x+32x+3. 2 . x x+3 x+3+3 x+6, 3 . x x+3 x/4+3, 4 . x x/4 2x/4 = x/2,5 . . . . . +32x/4+3 x/2+3. 4. 1 P a, f a P b, f b = P3, f 3P2, f 2 = P3, 2P2, 3 = 1 0 = 0. 2 x y P y, x = x P 2, x P 3, x = P 2, 2P 3, 2 P 2, 3P 3, 3 = 0 1 0 1 = 1 1 = 1. 5. 1 812元,最小元1,极大元 8, 12; 微小元是 1. 4622 无 最 大3 B无上1界,无最小上界；下界1, 2; 最大下界 2. 6. G = PQQPR = PQQPR 专业资料学习参考细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,共 8 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版= P QQPR = P QQPQR = P Q RPQRPQRPQRP QR PQR = P Q RPQRPQRPQR PQR = m3m4m5m6m7 = 3, 4, 5, 6, 7. 7. G = xP x yQ y xRx = xP x yQ y xR x = xP x yQ y xR x = x P x y Q y zR z = x y z P x Q y R z 9. 1 rRR IAa,b, b,a, b,c, c,d, a,a, b,b, c,c, d,d, sR RR1 a,b, b,a, b,c, c,b c,d, d,c, c,dtR RR 2R 3R 4a,a, a,b, a,c, a,d, b,a, b,b, b,c, b,d, ；2 关系图 : adadatRcdbcbcbrRsR11. GPQPQR PQR PQRPQR m6 m7m3 3, 6, 7 H = P Q R Q PR PQQR PQR PQRPQR PQRPQR P QR PQR PQRPQR m6 m3m7 3, 6, 7 专业资料学习参考细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页,共 8 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版G,H 的主析取范式相同,所以G = H. MS0100101013. 1MR0010001100010000000000012 R.S a, b, c, d, RS a, a, a, b, a, c, b, c, b, d, c, d, d, d, R1 a, a, c, a, c, b, d, c,S1. R1 b, a, d, c. 四 证明题2. 设 A,B 为任意集合,证明：A-B-C = A-BC. 3. 此题 10 分 利用形式演绎法证明： AB, CB, C D蕴涵 AD；4. 此题 10 分A, B 为两个任意集合,求证：AAB = A BB . 1. 利用形式演绎法证明： PQ, RS, PR 蕴涵 QS；1. 证明： PQ, RS, PR 蕴涵 QS1 P R P 2 RP Q1 3 P Q P 4 RQ Q23 5 QR Q4 6 R S P 7 QS Q56 8 Q S Q7 2. 证明： A-B-C = A BC = ABC = ABC = A-B C 3. 证明： AB, CB, C D蕴涵 AD 1 A D附加 2 AB P 专业资料学习参考细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页,共 8 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -WORD 整理版4.3 B Q12 4 CB P 5 B C Q4 6 C Q35 7 C D P 8 D Q67 9 A D D18 所以 A B, CB, C D蕴涵 AD. 证明： AAB = AAB AAB AAA B AB AB AB 而 A BB = A B B = A BB B = A B= AB 所以： AAB = A BB. 专业资料学习参考细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页,共 8 页 - - - - - - - - -