《离散数学——有限集与无限集》由会员分享，可在线阅读，更多相关《离散数学——有限集与无限集（41页珍藏版）》请在金锄头文库上搜索。
1、薯_第四章有限集与无限集5zmuggggg心8圆,001$4.1有限集与无限集基本概念问题:L,2,3,.小与2,4,6,.哪个集合的元素更多?口因为L,2,3,.22,4,6,.,所以L,2,3,.里的个数多于2,4,6,.的个数。口因为两个集合可用水数ffaj=:2n表示,而f(n)=2n是一一对应函数,所以L,2,3,.和2,4,6,.两个集合的个数一样多。结论:无限集合无法用确切的个数来描述,有限集合的一些特征也不能任意推广到无限集合中去。$4.1有限集与无限集基本概念定义4.1一个集合S与集合N,=0,1,2.(n-1)如果存在一一对应函数fNu_*S,则称S是有限的,并称其有基数n
2、;如果S不是有限的则称其为无限的。定义4.2如果存在一一对应函数f:S一S,使得f(S)一S,即f(S)是S的真子集,|则8是无限的,否则8是有限的。说明:要证明一个集合是无限集,只需证明集合和它的它的真子集间存在一一对应关系。如:2n是n的真子集。$4.1有限集与无限集基本概念例4.1一个有n个不同元素所组成的集合,它就是基数为n的有限集。例4.2自然数集N是无限集。例4.3实数集R是无限集。邑4l有限集与无限集基本概念囤E分析:VXeN,找到一一对应的函数f(g),且ylyzf(CxjsvVmeNjcN证明:设函数f:N一N“定义为f(XJ=2X,显然f是一对一的,而且有f(N)CN,所以
3、N是无限的。_姜84.1有限集与无限集基本概念_囤实数集R是无限的。_分析:YVXE耶,找到一一对应的凶数f(g),丁yly=fcO,yxeRCR证薯$4.2有限集定义有限集的基数定义4.3有限集S的元素个数称为S的基数,记为ISI。例:设A=a,b,c,町,则IAl=4842有限集定如果A,B是分离的有限集合,则有iIAUBIEIAI+IBI如果A,B是任意的有限集合,则有NPBHIAIIB-A0张万对任意三个有限集合A,B,C,则有IAUBUCEIAIHIBIHICL|AnBl-IAnCL-IBnCI+IlAnBnC|惧$4.2有限集设有n个有限集合Sl,Sz,.S,则有|SIUS,U.5,丨=二|S|2、ss1+万,|Surlajhise1s诉Eksn+一芒“fSaeef8u|喜$4.2有限集例4.4假定有120个学生,其中100个学生至少要学德、法、英三种语言的一种,还假定65人学法语,45人学德语,42人学英语;20人学法语和德语,25人学法语和英语,15人学德语和英语。请问同时学三种语言的有多少人?仅学一种语言的各有多少人?解:(1)设A、B、C分别表示学法语、德语和英语的学生的集合,由题意和定理4.5有:IAUBUCIzIAHIBHICLH|AnBHIAnCH|BnC|+IAnBnC1100=65+45+42-20-25-15+|AnBnC|所以|AIBnC-8
