《2022年电大_离散数学形成性考核作业集合 .pdf》由会员分享，可在线阅读，更多相关《2022年电大_离散数学形成性考核作业集合 .pdf（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 / 14 离散数学形成性考核作业（一）集合论部分分校 _ 学号_ 姓名 _ 分数 _ 本课程形成性考核作业共4 次，内容由中央电大确定、统一布置。本次形考作业是第一次作业，大家要认真及时地完成集合论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第 1 章集合及其运算1用列举法表示“大于2 而小于等于9 的整数”集合2用描述法表示“小于5 的非负整数集合”集合 3写出集合B=1, 2, 3 的全部子集 4求集合 A=,的幂集 5设集合 A= a , a ，命题： a P(A)是否正确，说明理由 6设ABC , , , , , , , ,1 2 313 52 4 6求 (1)AB (2
2、)ABC (3)C- A (4)AB7化简集合表示式：(AB )B) - AB8设 A, B, C 是三个任意集合，试证：A- (BC ) = (A-B ) - C9填写集合 4,9 9,10,4之间的关系10设集合 A = 2, a, 3, 4 ，那么下列命题中错误的是（） AaAB a, 4, 3AC aA DA11设 B = a, 3, 4, 2 ，那么下列命题中错误的是（）A aB B2, a, 3, 4BC aBDB第 2 章关系与函数 1设集合 A = a, b，B = 1, 2, 3 ，C = 3, 4 ，求 A(BC)，(AB)(AC ) ，并验证 A(BC ) = (AB)(
3、AC )2对任意三个集合A, B 和 C，若 ABAC，是否一定有BC？为什么？精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 14 页2 / 14 3对任意三个集合A, B 和 C，试证 若 AB = AC，且 A，则 B = C4写出从集合A = a，b，c 到集合 B = 1 的所有二元关系5设集合 A = 1 ，2，3，4，5，6 ，R 是 A 上的二元关系， R =a , ba , bA , 且 a +b = 6 写出 R 的集合表示式6设 R 从集合 A = a，b，c，d 到 B = 1 ，2，3的二元关系，写出关系R =
4、a , 1，a , 3，b , 2，c , 2，c , 3 的关系矩阵，并画出关系图7设集合 A= a , b , c , d，A 上的二元关系R =a , b，b , d，c , c，c , d ，S =a , c，b , d，d , b，d , d 求 RS，RS，R-S，（RS）， RS8设集合 A=1 , 2 ，B = a , b , c，C = , ，R 是从 A 到 B 的二元关系， S是从 B 到 C的二元关系，且R = ， ，S= ， ，用关系矩阵求出复合关系R S精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 14 页
5、3 / 14 9设集合 A=1 , 2 , 3 , 4 上的二元关系R = 1 , 1，1 , 3，2 , 2，3 , 1，3 , 3，3 , 4，4 , 3，4 , 4 ，判断 R具有哪几种性质？ 10设集合 A= a , b , c , d 上的二元关系R = a , a，a , b，b , b，c , d ，求 r (R)， s (R)，t (R)11设集合 A = a, b, c, d，R，S是 A 上的二元关系，且R = , , , , , , , S = , , , , , , , , 试画出 R和 S的关系图，并判断它们是否为等价关系，若是等价关系，则求出A 中各元素的等价类及商
6、集12图 1.1 所示两个偏序集A，R 的哈斯图，试分别写出集合A和偏序关系R的集合表达式d b a e c f g (1) b g d c e f a (2) 图 1.1题 12 哈斯图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 14 页4 / 14 13画出各偏序集A，1的哈斯图，并指出集合A的最大元、最小元、极大元和极小元其中：A= a , b , c , d , e ，1 = a , b，a , c，a , d，a , e，b , e,c , e，d , eIA；14下列函数中，哪些是满射的？那些是单射的？那些是双射的？ (
7、1) f1 ：RR，f (a) = a3 + 1； (2) f4 ：N0 , 1 ，f (a) = 为偶数为奇数aa,1,0 15设集合 A= 1, 2 ，B = a, b, c ，则 B A= 16设集合A = 1 ，2，3，4，A 上的二元关系R =1 , 2，1 , 4，2 , 4，3 , 3 ，S =1 , 4，2 , 3，2 , 4，3 , 2 ，则关系（）= 1 , 4，2 , 4 ARS BRS CR - S DS - R 17设集合A=1 , 2 , 3 , 4 上的二元关系R = 1 , 1，2 , 3，2 , 4，3 , 4，则 R 具有（） A自反性 B传递性 C对称性
8、D反自反性 18设集合 A= a , b , c , d , e 上的偏序关系的哈斯图如图 1.2 所示则 A 的极大元为，极小元为 19设 R为实数集，函数f：RR，f (a) = -a2 +2a- 1，则 f 是（） A单射而非满射 B满射而非单射 C双射 D既不是单射也不是满射离散数学形成性考核作业（二）图论部分本课程形成性考核作业共4 次，内容由中央电大确定、统一布置。本次形考作业是第二次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第 3 章图的基本概念与性质1计算出下图2.1的结点数与边数，并说明其满足握手定理图 2.1 习题 1 的图b c
9、a e d 图 1.2题 18 哈斯图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 14 页5 / 14 2试分别画出下列图2.2(a)、(b)、(c)的补图图 2.2 习题 2 的图3找出下图2.3 中的路、通路与圈图 2.3 习题 3 的图4设 G 为无向图， |G|=9，且 G 每个结点的度数为5 或 6，试证明 G 中至少有 5 个 6 度结点或至少有6个 5 度结点5设有向图D=如图 2.4 所示，图 2.4 习题 5 的图试问图中是否存在长度分别为3, 4, 5, 6 的回路，如存在，试找出6若无向图G 有 10条边， 3
10、 度与 4 度结点均 2 个，其余结点的度数均小于3，试问 G 中至少有几个结点？若无向图G 中有 6 条边， 3 度与 5 度结点均有一个，其余结点的度数均是2，试问 G 中有几个结点 ? 7试求图 2.5中有向图的强分图，单侧分图和弱分图图 2.5 习题 7 的图8试说明图2.6 中 G1和 G2同构G2G1图 2.6 习题 8 的图9试求图 2.7中的邻接矩阵与可达矩阵精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 14 页6 / 14 图 2.7 习题 9 的图10有 n 个结点的无向完全图的边数为11图中度数为奇数的结点为数个
11、12已知图G的邻接矩阵为，则 G 有（）A5 点， 8 边 B6 点， 7 边C5 点， 7边 D6 点， 8 边第 4 章 几种特殊图1试分别构造满足下列条件的无向欧拉图（1）有偶数个结点，奇数条边（2）有偶数个结点，偶数条边（3）有奇数个结点，偶数条边（4）有奇数个结点，奇数条边2分别构造满足下列条件的四个汉密尔顿图（1）偶数个结点，奇数条边（2）有偶数个结点，偶数条边（3）有奇数个结点，偶数条边（4）有奇数个结点，奇数条边3试画出一个没有一条欧拉回路，但有一条汉密尔顿回路的图4如图 2.8 是否为欧拉图？试说明理由图 2.8 判断是否为欧拉图 5如图 2.9是否为汉密尔顿图？试说明理由图
12、 2.9 判断是否为汉密尔顿图6试分别说明图4.3（a）、（ b）与（ c）是否为平面图图 2.10 判断是否为平面图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 14 页7 / 14 7试分别求出图2.11（a）、（ b）与（ c）的每个图的面的次数图 2.11 求面的次数 8试利用韦尔奇 鲍威尔算法分别对图2.12（a）、（ b）与（ c）着色图 2.12 图的着色9若 G 是一个汉密尔顿图，则G 一定是 ( )A欧拉图 B平面图 C连通图10设 G是有 n 个结点 m条边的连通平面图，且有k个面，则 k 等于 ( )Am- n+
13、2 Bn- m- 2 Cn+m- 2 Dm+n+2 11无向连通图G 是欧拉图的充分必要条件是_12设 G是具有 n个结点的简单图，若在G 中每一对结点度数之和大于等于_，则在 G 中存在一条汉密尔顿路13现有一个具有k个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_条边第 5 章树及其应用1试指出图2.13 中那些是树，那些是森林，并说明理由图 2.13 习题 1 的图2试画出图2.14 中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补图 2.14 习题 2 的图3试画出如图2.15 的完全图 K5 的所有不同构的生成树图 2.15 习题 3 的图4试求出图2.16 中
14、的最小生成树及其权值精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 14 页8 / 14 图 2.16 习题 4 的图 5给定一组权值为1，2，2，3，6，7，9，12，是求出相应的一个最优树 6无向树 T 有 7 片树叶 , 3个 3 度结点 ,其余的都是4 度结点，则T 有（）个 4 度结点？ A1 B2 C3 D4 7无向树 T 有 3 个 3 度结点 ,2 个 4 度结点 ,其余的都是树叶，则T 有（）片树叶？ A3 B7 C9 D11 8无向树 T 有 1 个 2 度结点 ,3 个 3 度结点 ,4 个 4度结点 ,1个 5
15、度结点 ,其余的都是树叶，则T 有（）片树叶？ A12 B14 C16 D20 9无向树 T 有 9 片树叶 ,5 个 3 度结点 ,其余的都是4 度结点，则 T 有几个 4 度结点？ A0 B1 C2 D3 离散数学形成性考核作业（三）集合论与图论综合练习本课程形成性考核作业共4 次，内容由中央电大确定、统一布置。本次形考作业是第三次作业，大家要认真及时地完成图论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。一、单项选择题1若集合 A2 ，a， a ，4 ，则下列表述正确的是( )Aa， a A B a A C2A DA 2设 B = 2, 3, 4, 2 ，那么下列命题中错误的是（
16、）A2B B2, 2, 3, 4B C2B D2, 2B3若集合 A= a，b，1，2 ，B=1 ，2 ，则（） AB A，且 BA BB A，但 B A CB A，但 B A DB A，且 B A 4设集合 A = 1, a ，则 P(A) = ( ) A1, a B ,1, a C,1, a, 1, a D 1, a, 1, a 5设集合 A = 1 ，2，3，4，5，6 上的二元关系R =a , ba , bA , 且 a +b = 8 ，则 R 具有的性质为（）A自反的 B对称的C对称和传递的 D反自反和传递的6设集合A = 1 ，2，3，4，5 ，B = 1 ，2，3，R 从 A 到
17、 B 的二元关系，R =a , baA，bB且1ba 则 R具有的性质为（）A自反的 B对称的 C传递的 D反自反的 7设集合 A=1 , 2 , 3 , 4 上的二元关系R = 1 , 1，2 , 2，2 , 3，4 , 4 ，S = 1 , 1，2 , 2，2 , 3，3 , 2，4 , 4，则 S是 R的（）闭包 A自反 B传递 C对称 D以上都不对8非空集合A 上的二元关系R，满足 ( )，则称 R 是等价关系A自反性，对称性和传递性 B反自反性，对称性和传递性C反自反性，反对称性和传递性 D自反性，反对称性和传递性9设集合 A= a, b ，则 A 上的二元关系R=， 是 A上的 (
18、 )关系精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 14 页9 / 14 A是等价关系但不是偏序关系 B是偏序关系但不是等价关系C既是等价关系又是偏序关系 D不是等价关系也不是偏序关系 10设集合 A = 1 , 2 , 3 , 4 , 5 上的偏序关系的哈斯图如右图所示,若 A的子集 B = 3 , 4 , 5 ，则元素 3 为 B的（） A下界 B最大下界 C最小上界 D以上答案都不对 11设函数 f：R R，f (a) = 2a+ 1；g：R R，g(a) = a 2则（）有反函数 Ag f Bf g Cf Dg12设图 G
19、的邻接矩阵为0101010010000011100000100则 G 的边数为 ( )A5 B6 C3 D4 13下列数组中，能构成无向图的度数列的数组是( ) A(1, 1, 2, 3) B(1, 2, 3, 4, 5) C(2, 2, 2, 2) D (1, 3, 3) 14设图 G，则下列结论成立的是 ( )Adeg(V)=2 E Bdeg(V)= E CEvVv2)deg( DEvVv)deg(15有向完全图D，则图 D 的边数是 ( )AE ( E 1)/2 B V ( V 1)/2 CE ( E 1) D V ( V 1) 16给定无向图G 如右图所示，下面给出的结点集子集中，不是
20、点割集的为（） A b, d B d Ca, c D g, e 17设 G 是连通平面图，有v个结点， e 条边， r 个面，则 r = ( )Aev2 Bv e2 Cev2 Dev2 18无向图G存在欧拉通路，当且仅当( )AG 中所有结点的度数全为偶数 BG 中至多有两个奇数度结点CG 连通且所有结点的度数全为偶数 DG 连通且至多有两个奇数度结点19设 G 是有 n 个结点， m条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树A1mn Bmn C1mn D1nm 20已知一棵无向树T 中有 8 个结点， 4 度， 3度， 2 度的分支点各一个，T 的树叶数为A8 B5 C
21、4 D 3 二、填空题 1设集合AB , , , , 1 2 31 2，则 AB=，AB=，AB=，P(A)-P(B )=2设 A, B 为任意集合，命题A B的条件是3设集合 A 有 n 个元素，那么A 的幂集合 P(A)的元素个数为 4设集合 A = 1 ，2，3，4，5，6 ，A 上的二元关系AbabaR,且1ba ，则 R 的集合表示式为5设集合A = 1 ，2，3，4，5 ，B = 1 ，2，3，R 从 A 到 B 的二元关系， R =a , baA，bB 且 2a + b4 则 R的集合表示式为6设集合 A=0,1,2, B=0,2,4, R是 A到 B 的二元关系，,BAyxBy
22、AxyxR且且则 R的关系矩阵MR7设集合 A=1, 2, 3, 4 ，B=6, 8, 12 ，A 到 B 的二元关系R,2,ByAxxyyx24135a g b d f c e 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 14 页10 / 14 那么 R1 8设集合 A= a,b,c，A 上的二元关系R=, ，S=, 则(R S)1=9设集合 A=a,b,c， A 上的二元关系R=, , , ，则二元关系R具有的性质是 10设集合 A = 1 , 2 , 3 , 4 上的等价关系R = 1 , 2，2 , 1，3 , 4，4 ,
23、3IA那么 A中各元素的等价类为11设 A，B 为有限集，且m，n,那末 A与 B间存在双射，当且仅当12设集合A=1, 2, B= a, b ，那么集合A 到 B 的双射函数是13已知图G中有 1 个 1度结点， 2 个 2 度结点， 3 个 3 度结点， 4 个 4 度结点，则G 的边数是 14设给定图G(如由图所示 )，则图 G 的点割集是15设 G=是具有 n 个结点的简单图，若在G 中每一对结点度数之和大于等于，则在G 中存在一条汉密尔顿路16设无向图G是哈密顿图，则V 的任意非空子集V1，都有V117设有向图D 为欧拉图，则图D 中每个结点的入度18设完全图Kn有 n 个结点 (n
24、2) ，m条边，当时， Kn中存在欧拉回路19图 G（如右图所示）带权图中最小生成树的权是20连通无向图G有 6个顶点 9 条边，从G 中删去条边才有可能得到G 的一棵生成树T三、判断说明题1设 A、B、C 为任意的三个集合，如果AB=AC，判断结论B=C 是否成立？并说明理由2如果 R1和 R2是 A上的自反关系，判断结论：“ R-11、R1R2、R1R2是自反的 ” 是否成立？并说明理由3设 R，S是集合 A上传递的关系，判断R S是否具有传递性，并说明理由4若偏序集 的哈斯图如右图所示，则集合 A的最小元为1，最大元不存在5若偏序集，R 的哈斯图如右图所示，则集合 A的极大元为a，f；最
25、大元不存在6图 G(如右图 )能否一笔画出？说明理由若能画出，请写出一条通路或回路7判断下图的树是否同构？说明理由8给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由v1v2v3v5v4dbacefghn图 Ga b c d e f g 图 G2图 G1ab fced 1 8 4 6 9 5 2 7 7 a c b e d f (a) (b) (c) 6 8 7 9 2 2 1 2 3 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 14 页11 / 14 9判别图 G(如下图所示 )是不是平面图，并说明
26、理由 10在有 6 个结点， 12条边的简单平面连通图中，每个面有几条边围成？为什么？四、计算题1设4,2,5, 2, 1,4, 1,5,4,3, 2, 1CBAE，求：（1）(A B)C；（ 2）P(A)P(C)；（ 3）A B2设集合 Aa, b, c ，B= b, d, e ，求（1）BA；（ 2）AB；（ 3）AB；（ 4）BA3设 A=1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 ，R 是 A 上的整除关系， B=2, 4, 6 （1）写出关系R 的表示式；（2）画出关系R 的哈斯图；（3）求出集合B 的最大元、最小元 4设集合 A a, b, c, d
27、 上的二元关系R 的关系图如右图所示（1）写出 R 的表达式；（2）写出 R 的关系矩阵；（3）求出 R2 5设A=0 ，1，2，3，4 ，R=|x A，yA 且 x+y0 ，S=|xA，yA 且 x+y=3 ，试求R，S，R S，R-1，S-1，r(R)，s(R)，t(R)，r(S)，s(S)，t(S)6设图 GV，E ，其中 Va1, a2, a3, a4, a5, Ea1, a2， a2, a4， a3, a1， a4, a5， a5, a2（1）试给出 G 的图形表示；（2）求 G 的邻接矩阵；（3）判断图 D 是强连通图、单侧连通图还是弱连通图？7设图 G=，V= v1，v2，v3，
28、v4，v5 ，E= ( v1,v2)，(v1,v3)，(v2,v3)，(v2,v4)，(v3,v4)，(v3,v5)，(v4,v5) （1）试给出 G 的图形表示；（2）写出其邻接矩阵；（3）求出每个结点的度数（4）画出图 G 的补图的图形8图 G=，其中 V= a, b, c, d, e, f ，E= ( a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (d, e), (d, f), (e, f) ，对应边的权值依次为5，2，1，2，6，1，9，3 及 8（1）画出 G 的图形；（2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值
29、9已知带权图G 如右图所示试（1）求图 G 的最小生成树；（2）计算该生成树的权值10设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树；（2）计算它们的权值五、证明题 1试证明集合等式：A (B C)=(AB) (AC) 2证明对任意集合A，B，C，有CABACBA)( 3设 R 是集合 A 上的对称关系和传递关系，试证明：若对任意aA，存在 b A，使得 R，则 R是等价关系 4若非空集合A 上的二元关系R和 S是偏序关系，试证明：SR也是 A 上的偏序关系 5若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的6设 G 是连通简单平面
30、图，则它一定有一个度数不超过5 的结点（提示：用反证法） 7设连通图G 有 k 个奇数度的结点，证明在图G 中至少要添加2k条边才能使其成为欧拉图 8证明任何非平凡树至少有2 片树叶adbcv1v2v3v6v5v451063478921精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 14 页12 / 14 离散数学形成性考核作业（四）数理逻辑部分本课程形成性考核作业共4 次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第 6 章 命题逻辑1判
31、断下列语句是否为命题，若是命题请指出是简单命题还是复合命题（1）8 能被 4 整除（2）今天温度高吗？（3）今天天气真好呀！（4）6 是整数当且仅当四边形有4条边（5）地球是行星（6）小王是学生，但小李是工人（7）除非下雨，否则他不会去（8）如果他不来，那么会议就不能准时开始2翻译成命题公式（1）他不会做此事（2）他去旅游，仅当他有时间（3）小王或小李都会解这个题（4）如果你来，他就不回去（5）没有人去看展览（6）他们都是学生（7）他没有去看电影，而是去观看了体育比赛（8）如果下雨，那么他就会带伞3设 P，Q 的真值为 1；R，S的真值为 0，求命题公式 (PQ)RS Q 的真值4试证明如下逻
32、辑公式（1） （A B）（ BC）C（AC）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 14 页13 / 14 （2） (PQ)(QR) RP 5试求下列命题公式的主析取范式，主合取范式（1） （P(QR)）( PQ) （2） ( PQ)Q 6利用求公式的范式的方法，判断下列公式是否永真或永假（2）（ PQ）R7试证明 CD，( CD) H，H(AB)，(A B) ( RS) 蕴含 RS8设 P：昨天天晴， Q：前天下雨，则命题“ 昨天天晴，但前天下雨” 可符号化为（） APQ BPQ CPQ DQ P9可以确定下述推理的步骤（）
33、是正确的A（ 1） PQP （2） P T（1）IB（ 1） P QP （2） QT（1）IC（ 1） PQP（2） PT（1）ID（ 1） PQP（2） PT（1）I第 7 章 谓词逻辑将下列命题翻译成谓词公式(1) 有人能做这件事，但不是所有人都能做。(2) 每个人都不会来。(3) 没有人能做这件事。(4) 所有的整数都是实数。(5) 有些人能去，但不是所有人都能去。(6) 如果每人都这样做，那么就没有什么事做不了。(7) 没有什么非做不可的事。(8) 不是每个人都愿意做这件事。(9) 所有人都需要不断地努力学习，争取进步。精选学习资料 - - - - - - - - - 名师归纳总结 -
34、 - - - - - -第 13 页，共 14 页14 / 14 (10) 如果 x 大于 y，那么 x+4 大于 y+1。2设谓词 A(x)：x是偶数， B(x)：x 是奇数， x的取值为 1 至 10之间的正整数，试求出下列谓词公式的值（1）（ x）A（x）（x）B（x）（2）（ x）（ A（x）B（x）3试证明下列公式（1）（ x） A（x）（ x）A（x）（2）（ x）（ P（x） R（x）（ x）P（x）（x）R（x）（3）（ x）A（x） B（x）（ A（x）B）4试证明（x）（P（x）R（x） ,（x）R（x）可逻辑推出（x）P（x）5设 A（x）： x是人， B（x）： x犯错
35、误，则命题“ 没有不犯错误的人” 可符号化为（） A(x)(A(x)B(x) B( x)(A(x) B(x) C(x)(A(x)B(x) D( x)(A( x） B( x）6可以确定下述谓词推理的步骤（）是正确的A （1） （x）P（x）P （2） P（a） US（1）（3） （ x）P（x）ES（2）B （1） （ x）P（x）P （2） P（a）ES（1）（3） （x）P（x）US（2）C （1） P（a）P（2） （x）P（x）US（1）D （1） P（a）P（2） （a）P（a）US（1）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 14 页