电大_离散数学形成性考核作业集合

1、离散数学形成性考核作业（一）集合论部分分校_ 学号_ 姓名_ 分数_本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第一次作业，大家要认真及时地完成集合论部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第1章 集合及其运算1用列举法表示 “大于2而小于等于9的整数” 集合2用描述法表示 “小于5的非负整数集合” 集合 3写出集合B=1, 2, 3 的全部子集 4求集合A=的幂集 5设集合A=a , a ，命题：a P(A) 是否正确，说明理由 6设求 (1) (2) (3)C - A (4) 7化简集合表示式：(AB )B) - AB 8设A, B, C是三个任意

2、集合，试证： A - (BC ) = (A - B ) - C 9填写集合4, 9 9, 10, 4之间的关系 10设集合A = 2, a, 3, 4，那么下列命题中错误的是（ ） AaA B a, 4, 3A CaA DA 11设B = a, 3, 4, 2，那么下列命题中错误的是（ ） AaB B2, a, 3, 4B CaB DB第2章 关系与函数 1设集合A = a, b，B = 1, 2, 3，C = 3, 4，求 A(BC)，(AB)(AC ) ，并验证A(BC ) = (AB)(AC ) 2对任意三个集合A, B和C，若ABAC，是否一定有BC？为什么？ 3对任意三个集合A, B

3、和C，试证 若AB = AC，且A，则B = C 4写出从集合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 =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，（R

4、S），RS 8设集合A=1 , 2 ，B = a , b , c，C =a , b，R是从A到B的二元关系，S是从B到C的二元关系，且R = ， S= ，用关系矩阵求出复合关系RS 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 = , , , ,

5、, , , S = , , , , , , , , 试画出R和S的关系图，并判断它们是否为等价关系，若是等价关系，则求出A中各元素的等价类及商集 12图1.1所示两个偏序集A，R 的哈斯图，试分别写出集合A和偏序关系R的集合表达式dbaecfg(1)bgdcefa(2)图1.1 题12哈斯图 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下列函数中，哪些是满射的？那些是单射的？那些是双射的？ (1) f1 ：R R，

6、f (a) = a3 + 1； (2) f4 ：N 0 , 1，f (a) = 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具有（ ）bcaed图1.2 题18哈斯图 A自反性 B传递性 C对称性 D反自反性 18设集合A= a

7、 , 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的图2试分别画出下列图2.2(a)、(b)、(c)的补图图2

8、.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度与4度结点均2个，其余结点的度数均小于3，试问G中至少有几个结点？若无向图G中有6条边，3度与5度结点均有一个，其余结点的度数均是2，试问G中有几个结点?7试求图2.5中有向图的强分图，单侧分图和弱分图图2.5 习题7的图8试说明图2.6中G1和G2同构图2.6 习题8的图9试求图

9、2.7中的邻接矩阵与可达矩阵图2.7 习题9的图10有n个结点的无向完全图的边数为 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是否为欧

10、拉图？试说明理由图2.8 判断是否为欧拉图 5如图2.9是否为汉密尔顿图？试说明理由图2.9 判断是否为汉密尔顿图6试分别说明图4.3（a）、（b）与（c）是否为平面图图2.10 判断是否为平面图 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+2 Bn-m-2 Cn+m-2 Dm+n+211无向连通图 G 是欧拉图的充分必要条件

11、是_12设G是具有n个结点的简单图，若在G中每一对结点度数之和大于等于_，则在G中存在一条汉密尔顿路13现有一个具有个奇数度结点的图，若要使图中有一条欧拉回路，最少要向图中添加_条边第5章 树及其应用1试指出图2.13中那些是树，那些是森林，并说明理由图2.13 习题1的图2试画出图2.14中的一个生成树，并说明其中的树枝、弦，以及对应生成树的补 图2.14 习题2的图3试画出如图2.15的完全图K5 的所有不同构的生成树 图2.15 习题3的图4试求出图2.16中的最小生成树及其权值 图2.16 习题4的图 5给定一组权值为1，2，2，3，6，7，9，12，是求出相应的一个最优树 6无向树T

12、有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度结点,其余的都是树叶，则T有（ ）片树叶？ A12 B14 C16 D20 9无向树T有9片树叶,5个3度结点,其余的都是4度结点，则T有几个4度结点？ A0 B1 C2 D3 离散数学形成性考核作业（三）集合论与图论综合练习本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第三次作业，大家要认真及时地完成图论部

13、分的形考作业，字迹工整，抄写题目，解答题有解答过程。一、单项选择题1若集合A2，a， a ，4，则下列表述正确的是( )Aa， a A B a A C2A DA 2设B = 2, 3, 4, 2，那么下列命题中错误的是（ ） A2B B2, 2, 3, 4B C2B D2, 2B3若集合A=a，b， 1，2 ，B= 1，2，则（ ） AB A，且BA BB A，但BA CB A，但BA DB A，且BA 4设集合A = 1, a ，则P(A) = ( ) A1, a B,1, a C,1, a, 1, a D1, a, 1, a 5设集合A = 1，2，3，4，5，6 上的二元关系R =a ,

14、 ba , bA , 且a +b = 8，则R具有的性质为（ ）A自反的 B对称的C对称和传递的 D反自反和传递的6设集合A = 1，2，3，4，5 ，B = 1，2，3，R从A到B的二元关系，R =a , baA，bB且则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自反性，对称性和传递性

15、 B反自反性，对称性和传递性C反自反性，反对称性和传递性 D自反性，反对称性和传递性9设集合A=a, b，则A上的二元关系R=，是A上的( )关系A是等价关系但不是偏序关系 B是偏序关系但不是等价关系24135C既是等价关系又是偏序关系 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则（ ）有反函数 Agf Bfg Cf Dg 12设图

16、G的邻接矩阵为则G的边数为( )A5 B6 C3 D413下列数组中，能构成无向图的度数列的数组是( ) A(1, 1, 2, 3) B(1, 2, 3, 4, 5) C(2, 2, 2, 2) D(1, 3, 3) 14设图G，则下列结论成立的是 ( )Adeg(V)=2E Bdeg(V)=E C D15有向完全图D， 则图D的边数是( )AE(E1)/2 BV(V1)/2agbdfce CE(E1) DV(V1) 16给定无向图G如右图所示，下面给出的结点集子集中，不是点割集的为（ ） Ab, d Bd Ca, c Dg, e 17设G是连通平面图，有v个结点，e条边，r个面，则r= (

17、)Aev2 Bve2 Cev2 Dev218无向图G存在欧拉通路，当且仅当( )AG中所有结点的度数全为偶数 BG中至多有两个奇数度结点CG连通且所有结点的度数全为偶数 DG连通且至多有两个奇数度结点19设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树A B C D 20已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 A8 B5 C4 D 3二、填空题 1设集合，则AB= ，AB= ，A B= ，P(A)-P(B )= 2设A, B为任意集合，命题A-B=的条件是 3设集合A有n个元素，那么A的幂集合P(A)的元素个数为 4设集合A

18、= 1，2，3，4，5，6 ，A上的二元关系且，则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的二元关系，则R的关系矩阵MR7设集合A=1, 2, 3, 4 ，B=6, 8, 12， A到B的二元关系R那么R1 8设集合A=a,b,c，A上的二元关系R=,，S=,则(RS)1=9设集合A=a,b,c，A上的二元关系R=, , , ，则二元关系R具有的性质是 10设集合A = 1 , 2 , 3 , 4 上的等价关系R = 1 ,

19、 2，2 , 1，3 , 4，4 , 3IA那么A中各元素的等价类为 11设A，B为有限集，且|A|=m，|B|=n,那末A与B间存在双射，当且仅当 12设集合A=1, 2,B=a, b，那么集合A到B的双射函数是 a b f ce d图G 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中每个结点的入度 687922123

20、18设完全图K有n个结点(n2)，m条边，当 时，K中存在欧拉回路19图G（如右图所示）带权图中最小生成树的权是 20连通无向图G有6个顶点9条边，从G中删去 条边才有可能得到G的一棵生成树T三、判断说明题1设A、B、C为任意的三个集合，如果AB=AC，判断结论B=C 是否成立？并说明理由1oo84695277 2如果R1和R2是A上的自反关系，判断结论：“R-11、R1R2、R1R2是自反的” 是否成立？并说明理由 3设R，S是集合A上传递的关系，判断R S是否具有传递性，并说明理由 4若偏序集的哈斯图如右图所示，则acbedf集合A的最小元为1，最大元不存在5若偏序集的哈斯图如右图所示，则

21、 集合A的极大元为a，f；最大元不存在v1v2v3v5v4dbacefghn图G6图G(如右图)能否一笔画出？说明理由若能画出，请写出一条通路或回路 7判断下图的树是否同构？说明理由 (a)(b)(c)8给定两个图G1，G2（如下图所示），试判断它们是否为欧拉图、哈密顿图？并说明理由abcdefg图G2图G1 v1v2v3v6v5v4 9判别图G(如下图所示)是不是平面图，并说明理由 10在有6个结点，12条边的简单平面连通图中，每个面有几条边围成？为什么？四、计算题1设，求：（1）(AB)C； （2）P(A)P(C)； （3）AB2设集合Aa, b, c，B=b, d, e，求（1）BA；

22、（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的最大元、最小元adbc 4设集合Aa, b, c, d上的二元关系R的关系图如右图所示（1）写出R的表达式；（2）写出R的关系矩阵； （3）求出R2 5设A=0，1，2，3，4，R=|xA，yA且x+y0，S=|xA，yA且x+y=3，试求R，S，RS，R-1，S-1，r(R)，s(R)，t(R)，r(S)，s(S)，t(S)6设图G=，其中V=a1, a2, a3,

23、 a4, a5,E=，（1）试给出G的图形表示； （2）求G的邻接矩阵；（3）判断图D是强连通图、单侧连通图还是弱连通图？7设图G=，V= v1，v2，v3，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) ，对应边的权

24、值依次为5，2，1，2，6，1，9，3及8（1）画出G的图形；（2）写出G的邻接矩阵；51063478921（3）求出G权最小的生成树及其权值 9已知带权图G如右图所示试（1）求图G的最小生成树；（2）计算该生成树的权值10设有一组权为2,3,5,7,11,13,17,19,23,29,31,试（1）画出相应的最优二叉树；（2）计算它们的权值 五、证明题 1试证明集合等式：A (BC)=(AB) (AC) 2证明对任意集合A，B，C，有 3设R是集合A上的对称关系和传递关系，试证明：若对任意aA，存在bA，使得R，则R是等价关系 4若非空集合A上的二元关系R和S是偏序关系，试证明：也是A上的偏

25、序关系 5若无向图G中只有两个奇数度结点，则这两个结点一定是连通的 6设G是连通简单平面图，则它一定有一个度数不超过5的结点（提示：用反证法） 7设连通图G有k个奇数度的结点，证明在图G中至少要添加条边才能使其成为欧拉图 8证明任何非平凡树至少有2片树叶离散数学形成性考核作业（四）数理逻辑部分本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。第6章 命题逻辑1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题（1）8能被4整除（2）今天温度高吗？（3）今天天气真好呀！（

26、4）6是整数当且仅当四边形有4条边（5）地球是行星（6）小王是学生，但小李是工人（7）除非下雨，否则他不会去（8）如果他不来，那么会议就不能准时开始2翻译成命题公式（1）他不会做此事（2）他去旅游，仅当他有时间（3）小王或小李都会解这个题（4）如果你来，他就不回去（5）没有人去看展览（6）他们都是学生（7）他没有去看电影，而是去观看了体育比赛（8）如果下雨，那么他就会带伞3设P，Q的真值为1；R，S的真值为0，求命题公式(PQ)RSQ的真值4试证明如下逻辑公式（1） （AB）（BC）C （AC）（2） (PQ)(QR)R P5试求下列命题公式的主析取范式，主合取范式（1） （P(QR)）(PQ)（2） (PQ)Q6利用求公式的范式的方法，判断下列公式是否永真或永假 （2）（PQ）R7试证明CD，( CD)