[精品]离散数学练习试题2
离散数学练习试题2 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括 号内。错选、多选或未选均无分。 1. A. C. 2. 下列为两个命题变元P, Q的小项是 PAQA1P 〕PAQ 下列语句中是真命题的是() B. D. 1PVQ 1PVPVQ A. 我正在说谎 B. 严禁吸烟 C. 如果1+2=3,那么雪是黑的 D.如果1 +2=5,那么雪是黑的 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={lx+y=10,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={, , , }, 则下列不是t (R)中元素的是( A. B. C・ vl, 3> D. 10.设 A={{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( C. {{4, 5}}uA D. 0GA 11•在自然数集N上,下列运算是可结合的是() A. a * b=a-2b B. a*b=min{d, b} C. a * b=-a-b D. a^b=\a-b\ 12.在代数系统中,整环和域的关系是( ) A.整环一定是域 B.域不一定是整环 C.域一定是整环 D.域一定不是整环 下列所示的哈斯图所对应的偏序集中能构成格的是( ) 13. A. 14. ) A. C. 15. 设G为有兀个结点的简单图,则有( A (G)n 具有4个结点的非同构的无向树的数目是( A (G)0 A(G)^n 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) =2n+l, 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. 设图 D=vV, 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, A@B, 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上自反和传递的关系,试证明:RoR=R0 33. 证明:边e是图G的一条割边,当且仅当图G中不存在包含边e的简单回路。