离散数学及其应用02-集合论课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《离散数学及其应用02-集合论课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 及其 应用 02 集合论 课件
- 资源描述:
-
1、第2篇集合论集合论 集合论是现代各科数学的基础,它是德国数学家康托(Geog Cantor,18451918)于1874年创立的 1900年前后出现了各种悖论,使集合的发展一度陷入僵滞的局面。19041908年,策墨罗(Zermelo)列出了第一个集合论的公理系统,它的公理,使数学哲学中产生的一些矛盾基本上得到了统一,在此基础上以后就逐渐形成了公理化集合论和抽象集合论,使该学科成为在数学中发展最为迅速的一个分支。集合论在计算机科学中也具有十分广泛的应用,计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证,成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通
2、用语言,一切必要的数据结构都可以利用集合这个原始数据结构而构造出来,计算机科学家或许也可以利用这种方法。第第 3 章章 集合与关系集合与关系 3.1 集合的概念和表示法集合的概念和表示法 3.2 集合的运算集合的运算 3.3 集合的计数集合的计数 3.4序偶与笛卡尔积序偶与笛卡尔积 3.5 关系及其表示关系及其表示第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法 一般地说,把具有共同性质的或满足一定条件的事物汇集成一个整体,就形成一个集合集合。例如:教室内的桌椅、图书馆的藏书、自然数的全体、直线上的所有点等,均分别构成一个集合,而同学、高等学校、每个自然数、直线
3、上的点等分别是所对应集合的元素。通常用大写英文字母表示集合的名称,用小写英文字母表示组成集合的“事物”,即元素。若元素a属于集合A,记作aA,也称集合A包含a,或a在A之中,或a是A的成员;若元素a属于集合的元素,记作aA,也称集合A不包含a,或a不在A之中,或a不是A的成员。若一个集合包含的元素个数是有限的,则称该集合为有限集有限集,否则称为无限集无限集。第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法 集合的方法通常有两种:列举法和描述法。列举法是指将集合中所有元素都列举出来,或者列出足够多的元素以反映集合中成员的特征,并把它们写在大括号里。例如:Aa,b,
4、c,d,B课桌,灯泡,自然数,老虎,C1,2,3,,D=a,a2,a3,。从方法的定义中可以看出,列举法必须把元素的全体尽列出来,不能遗漏任何一个,并且集合中的元素没有顺序之分且不重复。而描述法是指利用一项规则,概括集合中元素的属性,以便决定某一事物是否属于该集合。如果我们用谓词P(x)表示一个集合中的元素x所具有的属性,则任一集合可表示为x|P(x),其中竖线“|”前写的是元素的一般表示,右边写出元素应满足(具有)的属性。含义为该集合中的元素x具有属性P。设集合Ax|P(x),如果P(a)为真,则a A,否则aA。例如:第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念
5、和表示法 本书中用如下专用字母表示常见的集合:N自然数的集合(包含0);Nm 小于m的自然数集合,即0,1,n-1;I(或Z)整数的集合;I+(或Z+)正整数的集合;I_(或Z_)负整数的集合;R实数的集合;R+正实数的集合;R_负实数的集合;Q有理数的集合;C复数的集合。第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法 集合间的关系集合间的关系 定义定义3.1.1设A,B为任意两个集合,则有:(1)对于每个a A皆有a B,那么称A为B的子集或B包含A,也称B为A的母集,记作AB或BA。即:ABx(xA xB)可等价地表示成:ABx(xBxA)。(2)若AB且
6、AB,则称A为B的真子集或B真包含A,记作AB或BA。即:ABx(xA xB)x(xBxA)(3)若AB且BA,则称A和B相等,记作A=B;否则,称A和B不相等,并记作AB。即:A=B(AB)(BA)第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法例题例题3.1.1设N为自然数集合,Q为一切有理数组成的集合。R为全体实数集合,C为全体复数集合,则 NQRC,1N,1,1.2,9.9Q,2,R。也有NQRC,1N,1,1.2,9.9Q,a,ba,b,c,d。注意符号“”和“”在概念上的区别,“”表示元素与集合间的“属于”关系,“”表示集合间的“包含”关系。集合间的
7、包含关系“”具有下述性质:定理定理3.1.1 设A,B是任意的集合,则(1)AA,称为自反性;(2)若AB且BC,则AC,称传递性;证明:证明:(1)由集合间包含关系的定义直接得证。(2)对任意xA,由AB可知,一定有xA,又由BC可知,一定有xC,因此AC。第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法 定义定义3.1.2 不包含任何元素的集合是空集(Empty Set),记作。即=x|P(x)P(x),P(x)是任意谓词。定理定理3.1.2 对于任意一个集合A,有A。且空集是惟一的。定义定义3.1.3 在一定范围内,如果所有集合均为某一集合的子集,则称该集
8、合为全集全集,记作E(或U)。对于任一xA,因AE,故xE,即x(xE)恒真,故 E x|P(x)P(x),P(x)是任意谓词。定义定义3.1.4给定集合A,由集合A的所有子集为元素组成的集合,称为集合A的幂集。记为P(A)(或记为2A)。即 P(A)X|X A。定义定义3.1.5 设A为任一集合,用|A|表示A含有不同元素的个数,也称为集合A的基数。定理定理3.1.3 如果有限集A的基数An,则其幂集P(A)有个元素,即|P(A)|=2n。第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法 定理定理3.1.4 设A,B任意两个集合,则有(1)P(A);(2)AP
9、(A);(3)若AB,则P(A)P(B)。证明证明 (1)和(2)由定理3.1和定义3.1.4直接推出。(3)若xP(A),则xA,又AB,所以xB,因此,xP(B),从而知P(A)P(B)。第第 3 章章 集合与关系集合与关系3.2 集合的运算集合的运算 定义定义3.2.1 集合的几种主要的基本运算。设A,B是集合,并集(Union):AB称为集合A与B的并集并集,由A和B的所有元素所组成,定义为AB=x xA xB;称为集合的并运算并运算。交集(Intersection):AB称为集合A与B的交集交集,由所有同属于A和B的元素所组成,定义为AB=x xA xB;称为集合的交交运算运算。差集
10、(Difference):B-A称为B与A的差集差集,或称为A关于B的相对补相对补集集,由所有属于A而不属于B的元素所组成,定义为B-A=x xB xA。补集(Complement):称为A关于全集U的相对补集,或称为A的绝绝对补集对补集,简称为A的补集补集,由由U中不属于A的所有元素所组成,定义为=x|xU xA。对称差(Symmetric Difference):称为集合A与B的对称差对称差或布尔和布尔和,由除A和B中共同元素外其它的A和B中元素所组成,定义为=(A-B)(B-A)=(AB)-(AB)。第第 3 章章 集合与关系集合与关系3.2 集合的运算集合的运算 集合运算的文氏图表示集
11、合运算的文氏图表示 B A AB ABAABA集合AU图3-1 五种基本集合运算的文氏图第第 3 章章 集合与关系集合与关系3.2 集合的运算集合的运算 交换律交换律 AB=BA,AB=BA;结合律结合律 (AB)C=A(BC),(AB)C=A(BC);分配律分配律 A(BC)=(AB)(AC),A(BC)=(AB)(AC);幂等律幂等律 AA=A,AA=A;同一律同一律 A=A,AU=A;零零 律律 AU=U,A=;互补律互补律 A=U,A=;双重否定律双重否定律 =A;吸收律吸收律 A(AB)=A,A(AB)=A;德德摩根律摩根律 ,。BABABABA第第 3 章章 集合与关系集合与关系3
12、.3有限集合中元素的计有限集合中元素的计 集合的运算,可用于有限集中元素的计数问题。我们记A为有限集合A所含元素的个数,通常有两种方法文氏图法和容斥原理法来进行集合运算的计数。3.3.1文氏图法文氏图法(1)A1A2|A1|+|A2|(2)A1A2 min(|A1|,|A2|)(3)A1 A2|A1|-|A2|(4)A1 A2=|A1|+|A2|-2A1A2 第第 3 章章 集合与关系集合与关系3.3有限集合中元素的计有限集合中元素的计 容斥原理法容斥原理法 容斥原理也称包含与排斥原理或逐步淘汰原则,它也是“多退少补”计数思想的应用。定理定理3.3.1 设A,B为有限集合,其元素个数分别为|A
13、|,|B|则AB=|A|+|B|-AB 定理定理3.3.2 S中不具有性质P1,P2,Pm的元素个数为 =+(-1)m(|A1A2Am|)。|21mAAAmiijijji 11 i j m1 i j k m|S|A|AA|AAA|第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 序偶序偶 定义定义3.4.1 由两个元素x,y(允许x=y)按给定次序排成的二元组合称为一个有序对有序对或序偶序偶(Ordered pair),记作,其中称x是有序对的第一元素第一元素,y是有序对的第二元素第二元素。例如,上、下;左、右;34;张华高于李明;中国地处亚洲;平面上点的坐标等。这些实
14、例可分别用序偶表示:;等。从这里可看出序偶是用来刻画两个对象之间的关系。序偶可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。在集合中a,bb,a,但对序偶。定义定义3.4.2 两个序偶相等,当且仅当 xu,yv。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 例例3.4.1 设=,求x,y。解解 由定义3.4.2可列出如下方程组:2xy10 x3y5求解得x=5,y=0。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 序偶的概念可以推广到有序三元组的情况。三元组是一个序偶,其第一元素本身也是一个序偶,可形式化表示为,z
15、。由序偶相等的定义,可以知道,z,w,当且仅当,zw,即xu,yv,zw。今后约定三元组可记作。应该注意的是:当xy时,。同理四元组被定义为一个序偶,其第一元素为三元组,故四元组有形式为,w且 ,w,s 当且仅当(xp)(yq)(zr)(ws)依此类推,n元组可写为,xn且 ,xn,yn当且仅当 (x1=y1)(x2=y2)(xn-1yn-1)(xnyn)一般地,n元组可简写为,第i个元素xi称作n元组的第i个坐标。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 定义定义3.4.3 设A,B是任意集合,以A中元素作第一元素,B中元素作第二元素生成的所有有序对的集合称为
16、A,B的笛卡笛卡尔积尔积(Descartes Product),记作AB。即AB=xA yB。由定义,两集合的笛卡尔积仍是集合,所以可应用集合的运算,如并、交、差、补。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积例例3.4.2 设集合A=x,y,z,B=0,1,C=u,v,求AB,BA,AA,ABC,(AB)C,A(BC),(AB)(BA)。解解 AB=,BA=,AA=,ABC=,(AB)C=,u,v,u,v,u,v,u,v,u,v,u,v=,A(BC)=x,x,x,x,y,y,y,y,z,z,z,z,第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与
17、笛卡尔积 由笛卡尔积的定义可得:1对于任意集合A,约定A=,A=。2笛卡尔积运算是不可交换的,当A,B,AB时ABBA。3笛卡尔积运算是不可结合的,因为(AB)C=,zxA,y B,z C是三元组的集合。A(BC)=x,x A,y B,z C是二元组的集合。定理定理3.4.1设A,B,C是三个集合,则有(1)A(BC)=(AB)(AC)(2)A(BC)=(AB)(AC)(3)(BC)A=(BA)(CA)(4)(BC)A=(BA)(CA)第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积定理定理3.4.2对于任意集合A,B,C,若C,则(1)AB的充分必要条件是ACBC,(
18、2)AB的充分必要条件是CACB。证明证明(1)充分性:设对任意的x A,因为C,任取y C,则 AC,又因为AC BC,因此 B C,从而x B,故AB;必要性:对任意的 AC,则x A且y C,因为AB,所以x B,因此,故ACBC。(2)的证明留给读者。在证明过程中C的条件在证明必要性时可减弱,因而ABACBC。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 定理定理3.4.3 设A、B、C、D为四个非空集合,则 AB CD的充要条件为AC,BD。定义定义3.4.4 定义A1A2An=(A1A2An-1)An,称为集合A1,A2,An的叉积。特别地,当A1=A2
19、=An=A时,简记A1A2An为An。定理定理3.4.3 若A、B都是有限集,|A|=m,|B|=n,则AB 也是有限集,且|AB|=mn。证明:证明:根据笛卡尔积的定义,A的一个元素要产生n个序对,A的m 个元素就共要产生mn个序对。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 关系的定义关系的定义 定义定义3.5.1 设A,B为集合,AB的任何子集R称为从集合从集合A到到集合集合B的二元关系的二元关系,简称为关系关系(Relation)。并称A为关系R的前域前域,B为关系R的后域后域。对于二元关系R,若R,常记作xRy;若R,则记作xy。特别当A=B时称R为集合集合
20、A上的二元关系上的二元关系。例例3.5.1 A=0,1,B=x,y,z,则R1=,R2=AB,R3=等都是从A到B的二元关系,R4=和R3同时也是A上的二元关系。A为整数集合,R=|x能整除y,x,yA为A上的整除关系。R为实数集合,=|xy,x,yR为R上的大于关系。例例3.5.2设A=2,3,4,B=2,3,4,5,6,A到B的关系R定义为:对于aA,bB,R当且仅当a|b(a|b即a整除b),则R=,R 第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.3 设A=1,2,3,4,定义A上的关系R为R=|a,bA,(ab)/2=k,kI 则 R=,通常称R为A
21、上的模2同余关系,也可等价地表示为R=|a,bA,a b(mod 2)对于集合A,今后常用到的三个特殊关系:空关系空关系(Empty Relation):由于AA,所以是A上的关系,称其为A上的空关系;全(域)关系全(域)关系(Total Relation):由AAAA,所以AA是 A上的关系,称其为A上的全域关系,记作EA,即EA=aA,bA;恒等关系恒等关系(Identity Relation):A=aA,称其为A上的恒等关系。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.4 设A=x,y,z,则(1)EA=,是A上的全关系,EA=AA=9。(2)A=,是
22、A上的恒等关系,A=A=3。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 定义定义3.5.2 关系R中所有有序对的第一元素的集合称为关系R的定义域定义域(Domain),记作domR,第二元素的集合称为关系R的值域值域(Range),记作ranR。称fldR=domRranR为R的域域(field)。即 domR=x|xAy(yBR),ranR=y|yBx(xAR)显然R是从A到B的关系,有domRA,ranRB,fldRAB。关系的定义域与值域可用图3-5表示。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示定定理理 3.5.1 设 R 和 S 是
23、从集合 X 到集合 Y 的两个关系,则 RS,RS,S,R-S 仍是从 X 到 Y 的关系。证证明明 因为 RXY,SXY,所以 RSXY,RSXY;因为S=XY-SXY,所以 R-S=RSXY。故 RS,RS,S,R-S 是从 X 到 Y 的关系。推推论论 设 R 和 S 是从集合 X 到集合 Y 的两个关系,(1)x(RS)yxRyxSy;(2)x(RS)yxRyxSy(3)x(S)yxS y;(4)x(R-S)yxRyxS y。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 关系的表示关系的表示1集合表示法集合表示法关系是一种集合,因而集合的表示方法,诸如列举法、描
24、述法都能用于关系的表示,上面几例给出了这两方法的应用。关系又是一种特殊的集合,因而它又有区别于通常集合的表示方法,对有限集合间的二元关系R除了可以用序偶集合的形式表达以外,还可用矩阵和图形表示,以便引入线性代数和图论的知识来讨论。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 关系的表示关系的表示2矩阵表示法矩阵表示法 设有限集合X=x1,x2,xn,Y=y1,y2,ym,其中m1,n1,R为集合X到集合Y的关系,则R的关系矩阵为MR=rijnm,其中ijijij1,x,yRri 1,2,n,j 1,2,m0,x,yR若()若如果R是有限集合X上的二元关系或X和Y含有相同
25、数量的有限个元素,则MR是方阵。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.6 若A=a1,a2,a3,a4,a5,B=b1,b2,b3,R=,,写出关系矩阵MR。解解:R101011M100010010第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.7设A=1,2,3,4,写出集合A上大于关系“”的关系矩阵。解解:=,,故00001000M11001110第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 3关系图表示法关系图表示法 有限集合的二元关系也可用图形来表示。设集合X=x1,x2,xn到集合Y=y
展开阅读全文