复旦大学计算机科学与工程系吴永辉离散数学集合论经典习题省公共课一等奖全国赛课获奖课件.pptx
《复旦大学计算机科学与工程系吴永辉离散数学集合论经典习题省公共课一等奖全国赛课获奖课件.pptx》由会员分享,可在线阅读,更多相关《复旦大学计算机科学与工程系吴永辉离散数学集合论经典习题省公共课一等奖全国赛课获奖课件.pptx(126页珍藏版)》请在咨信网上搜索。
1、集合论习题解析集合论习题解析经典习题与考研习题经典习题与考研习题经典习题经典习题一、集合基础一、集合基础二、二元关系二、二元关系三、函数三、函数四、概念综合练习四、概念综合练习考研习题考研习题 北京大学、中科院计算所、中科院软件所、中北京大学、中科院计算所、中科院软件所、中科院自动化所、北京师范大学、中科院成都计算科院自动化所、北京师范大学、中科院成都计算所、上海交通大学、西安交通大学、西南交通大所、上海交通大学、西安交通大学、西南交通大学、北京航空航天大学、复旦大学等学、北京航空航天大学、复旦大学等第1页一、集合基础一、集合基础1.1 与1.2 集合运算1.3 幂集第2页1.1 与与 1 设
2、A,B,C是任意3个集合,假如AB,B C,则AC可能吗?AC常真吗?举例说明。第3页AC可能A=1,B=1,C=1,1AC不常真A=1,B=1,C=1第4页2 设A,B是任意2个集合,A B与 AB同时成立,这可能吗?第5页可能A=1,B=1,1.第6页3 设A,B,C是集合,判断以下命题真假,假如为真,给出证实;假如为假,给出反例:1)AB,BC AC;2)AB,BC AC;3)AB,BC AC;4)AB,BC AC;5)aA,AB aB.第7页1)假A=1,B=2,C=2 2)假A=1,B=2,C=13)假A=1,B=1,C=1,1第8页4)假A=1,B=1,1,C=1,25)真子集定义
3、第9页4 4 设设A,B,CA,B,C是是U U子集,判断以下命题真假,假如子集,判断以下命题真假,假如为真,给出证实;假如为假,给出反例:为真,给出证实;假如为假,给出反例:1)1)A A B BA AB=BB=B;2)2)A A B BA AB=AB=A;3)3)A A B BA AB=AB=A;4)4)A A B BA AB=B;B=B;5)5)A A B BA A(B-A)=B(B-A)=B;6)6)B B A A(A-B)(A-B)B=AB=A;第10页1)假,A=B时不成立/*与与不一样不一样*/分析:I)ABAB=B:因为BAB;对于任意xAB,假如xA,因为AB,所以xB,则对
4、任意xAB,xB成立。所以AB=B。II)A=B AB=B,但AB不成立。第11页2)假,A=1,B=1,2,不成立;3)假,A=B时不成立;4)假,A=1,B=1,2,不成立;5)假,A=B时不成立6)假,A=1,2,B=1,不成立;第12页1.2 集合运算集合运算5 设A,B,C是任意3个集合,(1)AB=AC,则B=C吗?(2)AB=AC,则B=C吗?(3)AB=AC且AB=AC,则B=C吗?第13页(1 1)假)假A=1,2,B=1,C=2A=1,2,B=1,C=2(2 2)假)假A=1,B=1,2,C=1,3A=1,B=1,2,C=1,3(3 3)真)真/*/*基本法、反证法证实基本
5、法、反证法证实基本法、反证法证实基本法、反证法证实*/*/设设x x B B,假设,假设x x C C。因为。因为x x B B,所以,所以x x A AB B;因为;因为A AB=AB=AC C,所以,所以x x A AC C;因为;因为x x C C,所以所以x x A A;又因为;又因为x x B B,所以,所以x x A AB B;因为;因为A AB=AB=AC C ,所以,所以x x A AC C;则;则x x C C,这与,这与x x C C矛盾。所以矛盾。所以B=CB=C。第14页6 设A,B是任意2个集合,(1)若A-B=B,则A与B有何关系?(2)若A-B=B-A,则A与B有
6、何关系?(3)若AB=AB,则A与B有何关系?(4)若AB=A,则A与B有何关系?/*用文氏图辅助*/第15页证实:(1)由A-B=B,可得出A=B=。第16页(2)由A-B=B-A,可导出A=B。第17页(3)A=B第18页(4)B=第19页7 给出以下命题成立充分必要条件(1)(A-B)(A-C)=A(2)(A-B)(A-C)=(3)(A-B)(A-C)=(4)(A-B)(A-C)=/*等式推导*/第20页解:(1)1):设(A-B)(A-C)=A,对任意x,xA,则xA-B 或 xA-C;则有第21页2):设ABC=,对任意x,xA,则xB或xC,则有第22页 对任意x,x(A-B)(A
7、-C),则xA-B或 xA-C,则有第23页(2)(A-B)(A-C)=(A-B)=或(A-C)=AB而且ACABC所以,充要条件为ABC。第24页(3)1)设(A-B)(A-C)=,对任意x,xA,x(A-B)而且x(A-C);所以xB-A或xC-A;则有xB或xC;得xBC。所以ABC。2)ABC AB或AC;所以A-B=或A-C=。得(A-B)(A-C)=。从而,(A-B)(A-C)=ABC。第25页(4)(A-B)(A-C)=(A-B)-(A-C)(A-C)-(A-B)=(A-B)(A-C)而且(A-C)(A-B)(A-B)=(A-C)第26页1.3 幂集幂集7 设A,B是任意2个集合
8、,证实:(1)ABP(A)P(B)(2)P(A)P(B)A B(3)P(A)=P(B)A=B第27页/*利用基本法证实集合包含关系*/证实:(1)对任意xP(A),有xA,又因为AB,所以xB,即xP(B);所以P(A)P(B)。(2)/*证实方法同(1);*/对任意xA,则xP(A),又因为P(A)P(B),所以x P(B),即xB;所以A B。(3)由(1)和(2)证实导出。第28页二、二元关系二、二元关系1 设R是集合A上关系(1)R是自反,则RR是自反;(2)R是对称,则RR是对称;(3)R是反自反和传递,则R是反对称;第29页/*证实思想:依据定义给出性质证实*/证实:(1)证实思想
9、与(2)和(3)相同(2)设(a,b)RR,则存在c,(a,c)R,(c,b)R;因为R是对称,所以(b,c)R,(c,a)R;所以(b,a)RR。则RR是对称。(3)假设(a,b)R,(b,a)R。因为R是传递,所以(a,a)R,(b,b)R;因为R是反自反,所以造成矛盾。第30页2 设R是A上关系,若R是自反和传递,则RR=R。其逆命题也成立吗?证实思想:证实RR=R,1)证实RRR;2)证实RRR:第31页证实:证实:1 1)证实)证实R R R R R R:设设(a,b)(a,b)R R R R,存在,存在c c A,A,使得使得(a,c)(a,c)R,(c,R,(c,b)b)R R,
10、因为,因为R R是传递,所以是传递,所以(a,b)(a,b)R R;则;则R R R R R R;2 2)证实证实R R R R R R:设设(a,b)(a,b)R R,R R是自反,是自反,(b,b)(b,b)R R,所以,所以(a,(a,b)b)R R R R;则;则R R R R R R。所以所以R R R=RR=R。第32页自反不成立传递成立第33页特殊关系特殊关系3 设S=1,2,3,4,并设A=SS,在A上定义关系R为:(a,b)R(c,d)当且仅当a+b=c+d。(1)证实R是等价关系;(2)计算出A/R。第34页(1)证实:/*依据等价关系定义证实依据等价关系定义证实*/1)/
11、*证实证实R是自反;是自反;*/对于任意(a,b)SS,因为a+b=a+b,所以(a,b)R(a,b),即R是自反。2)/*证实证实R是对称;是对称;*/假如(a,b)R(c,d),则a+b=c+d,那么有c+d=a+b;所以(c,d)R(a,b),即R是对称。3)/*证实证实R是传递;是传递;*/假如(a,b)R(c,d),(c,d)R(e,f),则a+b=c+d,c+d=e+f;所以a+b=e+f,得(a,b)R(e,f),即R是传递。第35页(2)假如(a,b)R(c,d),则a+b=c+d,所以依据和数来划分。第36页4 设R,S是A上等价关系,证实:RS是A上等价关系RS=SR。第3
12、7页证实思想:1)RS是A上等价关系RS=SR;证实(i)RSSR;(ii)SR RS;2)RS=SR RS是A上等价关系;证实RS是(i)自反;(ii)对称;(iii)传递;第38页证实:1)RS是A上等价关系RS=SR:假如(a,b)RS,因为RS是对称,所以(b,a)RS,所以存在cA,使得(b,c)R,(c,a)S;因为R和S是对称,所以(c,b)R,(a,c)S;则(a,b)SR;同理,SR RS;第39页2)RS=SR RS是A上等价关系:/*证实RS是自反、对称比较轻易*/第40页传递性证实:传递性证实:对任意对任意a,b,ca,b,c A A,假如,假如(a,b)(a,b)R
13、R S,(b,c)S,(b,c)R R S S,因为因为R R S=SS=S R R,则有,则有(b,c)(b,c)S S R R,即存在,即存在e,fe,f A A,使,使(a,e)(a,e)R R,(e,b)(e,b)S S,(b,f)(b,f)S S,(f,c)(f,c)R R。因为因为S S是传递,是传递,(e,b)(e,b)S S,(b,f)(b,f)S S,所以,所以(e,f)(e,f)S S;因为;因为(a,e)(a,e)R R,所以,所以(a,f)(a,f)R R S S;R R S S是对称,是对称,则则(f,a)(f,a)R R S S;因为;因为R R是对称,是对称,(f
14、,c)(f,c)R R,则,则(c,(c,f)f)R R。因为因为(f,a)(f,a)R R S S,则存在,则存在g g A A,使得,使得(f,g)(f,g)R R,(g,a)(g,a)S S;因为;因为R R是传递,由是传递,由(c,f)(c,f)R R,(f,g)(f,g)R R,则则(c,g)(c,g)R R;因为;因为(c,g)(c,g)R R,(g,a)(g,a)S S,所以,所以(c,(c,a)a)R R S S。因为已经证实,。因为已经证实,R R S S是对称,所以是对称,所以(a,(a,c)c)R R S S。第41页函数函数12 设f:XY是函数,A,B是X子集,证实:
15、(1)f(AB)f(A)f(B)(2)f(AB)=f(A)f(B)(3)f(A)-f(B)f(A-B)第42页/*基本法证实*/证实:(1)对任意yf(AB),存在x,x AB,使得y=f(x)。因为xA,所以yf(A);因为x B,所以yf(B)。所以yf(A)f(B)。则f(AB)f(A)f(B)。第43页13 设R是A上一个二元关系,S=(a,b)|a,bA而且对于某个cA,有(a,c)R且(c,b)R。证实:若R是A上等价关系,则S是A上等价关系。/*证实是S自反、对称和传递*/第44页四、概念综合练习四、概念综合练习一、选择题(北京理工大学考研)1 以下集合运算中()对满足分配律。A
16、)B)C)D)第45页2 A、B是集合,P(A)、P(B)为其幂集,且AB=,则P(A)P(B)=()A)B)C)D),第46页3 A、B是集合,以下各式除()之外,均与AB等价。A)ABBB)AB=BC)AB=AD)ABB2第47页4 R是集合A上自反关系,则()A)R RB)RR RC)RR-1=IAD)R R-1=IA第48页5 集合A中有n个元素,则A上共有()个既对称又反对称关系。A)0B)2nC)n2D)2n第49页6 R是可传递二元关系,则在RR-1,RR-1,R-R-1,R-1-R中,有()个一定是可传递。A)1B)2C)3D)4第50页7 函数f:RR,其中R为实数集合,以下
17、四个命题中()为真。A)f(x)=5是内射B)f(x)=5是满射C)f(x)=5是双射D)A),B),C)都不真第51页8 集合A到B共有64个不一样函数,则B中元素不可能是()个。A)4B)8C)16D)64第52页二、选择题(北京理工大学1999)1 已知AB=1,2,3,AC=2,3,4,若2B,则 。A)1CB)2CC)3CD)4C第53页2 对任何二元关系R,在RR-1,RR-1,RR-1,RR-1中有 个一定是对称关系。A)1B)2C)3D)4第54页3 R=(1,4),(2,3),(3,1),(4,3),则 t(R)。A)(1,1)B)(1,2)C)(1,3)D)(1,4)第55
18、页集合论集合论考研习题考研习题考研习题一、集合基础二、二元关系三、函数第56页一、集合基础一、集合基础1.1 集合运算容斥原理1.2 集合运算证实1.3 幂集1.4 相类似练习题目第57页1.1 集合运算集合运算容斥原理容斥原理中国科学院自动化所中国科学院自动化所1997120个学生参加考试,考试有A、B和C3道题,考试结果以下:12个学生3道题都做对了,20个学生做对A和B,16个学生做对A和C,28个学生做对B和C,做对A有48个学生,做对B 有56个学生,有16个学生一道也没有做对。试求做对了C学生有多少个?直接使用容斥原理第58页解:设做对A题学生集合为PA,做对B题学生集合为PB,做
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 复旦大学 计算机科学 工程系 吴永辉 离散数学 集合论 经典 习题 公共课 一等奖 全国 获奖 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【a199****6536】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【a199****6536】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。