《离散数学作业题》由会员分享,可在线阅读,更多相关《离散数学作业题(4页珍藏版)》请在金锄头文库上搜索。
1、离散数学作业题第2章 集合、关系与映射P133 习题三:7、9、11、171. AB,AB能否同时成立,说明原因 求集合Aa,a的幂集 2. 证明:若BC,则P(B) P(C)3. 如果AB=AC,是否有B=C? 如果AB=AC,是否有B=C? 4. 试求1到10000之间不能被4,5或6整除的整数个数.5. 列出所有从A=a,b,c到B=s的关系,并指出集合A上的恒等关系和从A到B的全域关系.6. 给出A上的关系及其关系图和矩阵表示.|0x-y3 A=0,1,2,3,47. 已知S=a,b. R =x,y|x,yAxyA为集合族(S).试写出关系R.8. 已知: A=a,b,c, R=a,b
2、,a,c,b,c该关系具有什么性质? (自反,反自反,对称,反对称,传递性)9. 设A=a,b,c,R=a,b,a,c 计算:r(R),sr(R),tr(R),str(R).10. 设A是含有4个元素的集合,试求: (1)在A上可以定义多少种对称关系? (2)在A上可以定义多少种既是自反的,又是对称的关系?(3)在A上可以定义多少种既不是自反的,也不是反自反的二元关系?11. 设集合A=0,1,2,3,4. R=|x+y=4,x,yA ,S=|y-x=1,x,yA. 试求:RS,RR,(RS)R,R(SR).12. 证明:R是A上的传递关系RRR.13. A=1,2,3,4,5,R=|x,yA
3、x-y可被2整除,试问R是否是A上的等价关系?如果是,求出R的各等价类.14. A=1,2,3,4,5,A上的划分=1,2,3,4,5,给出由所诱导出的A上的等价关系R的集合表达式.15. 试给出一个单射但非满射的函数.(对某一集合而言)16. 设f:NNN,f(n)=,则: (1)说明f是否为单射和满射,并说明理由. (2) f的反函数是否存在?并说明理由. (3)求ranf. 17. 已知如果从无限集合A到集合B存在单射f,则B也是无限集合。设X是无限集合,集合Y,证明:X与Y的笛卡儿积XY是无限集合。 第六章 代数结构P247 习题六:4(1)(3)、6、16、211. 以下集合和运算是
4、否构成代数系统?如果构成,说明该系统是否满足结合律、交换律?求出该运算的幺元、零元和所有可逆元素的逆元.1) P(B)关于对称差运算,其中P(B)为幂集. 2) A=a,b,c,*运算如下表所示:2. 设集合A=a,b,那么(1)在A上可以定义多少不同的二元运算?(2)在A上可以定义多少不同的具有交换律的二元运算?3. 设A=1,2,B是A上的等价关系的集合.1) 列出B的元素. 2) 给出代数系统V=的运算表.3) 求出V的幺元、零元和所有可逆元素的逆元. 4) 说明V是否为半群、独异点和群? 4. 设A=a,b,c,构造A上的二元运算*,使得a*b=c,c*b=b,且*运算满足幂等律、交换
5、律.1) 给出关于*运算的一个运算表.2) *运算是否满足结合律,为什么?5. 设是一个代数系统。*是R上的一个二元运算,使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+ab(和+为数集上的乘法和加法). 证明:: 是独异点.6. 如果是半群,且*是可交换的. 证明:如果S中有元素a,b,使得a*a=a和b*b=b,则(a*b)*(a*b)=a*b.7. 设是一个群,则a,b,cS。 试证明: 群G中具有消去律,即成立: 如果ab=ac ,ba=ca 那么b=c.8. 设是群,aG . 现定义一种新的二元运算:xy=x*a*y,x,yG . 证明:也是群 . 9. 试写出模6加法群
6、的每个子群及其相应的左陪集. 10. 设A=1,2,5,10,11,22,55,110.1) A关于整除关系是否构成偏序集?2) 如果构成偏序集合,画出其对应的哈斯图.3) 如果构成偏序集,该偏序集合构成哪种格? (分配格、有界格、有补格、布尔格).第七题 图论1. 是否存在7阶无向简单图G,其度序列为1、3、3、4、6、6、7.给出相应证明.2. 求下图的补图.(无答案)3. 1)试画一个具有5个顶点的自补图2) 是否存在具有6个顶点的自补图,试说明理由。4. 设图G为n(n2且为奇数)阶无向简单图,证明:G与G的补图中奇度顶点个数相等.5. 无向图G中只有2个奇度顶点u和v,u与v是否一定连通.给出说明或证明。6. 图G如下图所示:1) 写出上图的一个生成子图.(不唯一)2) (G),(G),(G). 7. 在什么条件下无向完全图Kn为欧拉图? 8. 证明:有割边的图不是欧拉图.9. 证明:有割边的图不是哈密尔顿图.10. 树T有2个4度顶点,3个3度顶点,其余顶点全为树叶,问T有几片树叶?11. 给出全部互不同构的4阶简单无向图的平面图形。 12. 如果G是平面图, 有n个顶点、m条边、f个面,G有k个连通分支。试利用欧拉公式证明::n-m+f=k+1.