《集合的基本概念(离散数学).ppt》由会员分享，可在线阅读，更多相关《集合的基本概念(离散数学).ppt（55页珍藏版）》请在三一办公上搜索。
1、离 散 数 学(I),离散数学(I),第一章 集合论基础第二章 命题逻辑第三章 一阶逻辑第四章 图与网络第五章 数论基础,第一章 集合论基础,1.1 集合的基本概念1.2 关 系 1.3 映 射,康托尔(Cantor),1.1 集合的基本概念,什么是集合(Set)？“所要讨论的一类对象的整体”；“具有同一性质单元的集体”通常，用大写的英文字母A,B,C,表示集合；,1、二十六个英文字母可以看成是一个集合；2、所有的自然数看成是一个集合；3、吉林大学计算机学院2001级的本科学生可以看成是一个集合；4、这间教室中的所有座位可以看成是一个集合。,例如:,集合的元素(member或element),
2、组成一个集合的那些对象或单元称为这个集合的元素。通常，用小写的英文字母a,b,c,表示集合中的元素,设A是一个集合，a是集合A中的元素，记以aA，读作a属于A；若a不是集合A中的元素，则记以aA，读作a不属于A。例如：A是正偶数集合，则2A，8A，36A；而 3A，9A，17A,属于(belong to),包含有限个元素的集合，称为有限集或有穷集(finite set)；包含无限个元素的集合，称为无限集或无穷集(infinite set)。例：所有英文字母组成的集合是有限集，整数集合是无限集。,有限集、无限集,约定，存在一个没有任何元素的集合，称为空集(empty set)，记为，有时也用来表
3、示。约定，所讨论的对象的全体称为全集(universal set)，记作E或U，我们所讨论的集合都是全集的子集。全集是相对的。,空集、全集,设A是有穷集合，A中元素的个数称为集合A的元素数，记为A。例如，设A是所有英文字母组成的集合，则A=26。特别，|=0,集合的元素数,列举法；将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，例如：V=a,e,i,o,u 或B=1,4,9,16,25,36。描述法；通过描述集合中元素的共同特征来表示集合，例如：V=x|x是元音字母，B=x|x=a2,a是自然数,集合的表示法,文氏图(Venn Diagram)用一个大的矩形表示全集，在矩形内
4、画一些圆或其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。例如：集合V=a,e,i,o,u，用文氏图表示如下:,E,V,a,u,确定性；互异性；无序性；多样性；,集合的特征,任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；例如：A=x|x是自然数，且x100B=x|x是年轻人C=x|x是秃子,确定性,集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。例如：集合A=a,b,c,c,b,d，实际上，应该是A=a,b,c,d,互异性,集合与其中的元素的顺序无关例如：集合a,b,c,d,e、d,c,e,a,b、e,c,d,b,a，都是表示同一个集合。,无序性,集
5、合中的元素可以是任意的对象，相互独立，不要求一定要具备明显的共同特征。例如：A=a,a,a,b,a,1A=1,a,*,-3,a,b,x|x是汽车,地球,多样性,设集合S=A|A是集合，且AA若SS，则S是集合S的元素，则根据S的定义，有S S，与假设矛盾；若SS，则S是不以自身为元素的集合，则根据S的定义，有SS，与假设矛盾；,罗素悖论(Russells paradox),当两个集合A和B的元素完全一样，即A，B实际上是同一个集合时，则称集合A，B相等，记以A=B。例：设A=x|x是偶数，且0 x10，B=2,4,6,8，则A=B。,【定义1】集合相等,设A，B是两个集合，若A的元素都是B的元
6、素，则称A是B的子集，也称B包含A，或A包含于B，记以A B，或B A。若AB，且AB，则称A是B的真子集(proper subset)，也称B真包含A，或A真包含于B，记以AB，或B A。,【定义2】子集(subset),设A=2,4,6,8，B=x|x是正偶数，C=x|x是整数,则有A B，B C，AC,并且A B，B C，A C。,例：,对任意集合A,有A A。空集是任意集合的子集，且空集是唯一的。对于任意两个集合A、B，A=B当且仅当AB且BA。,重要结论,是否存在集合A和B,使得AB 且A B？若存在，请举一例。设A=a，B=a,a,b,c，则有:AB 且A B 再例如：且,讨论：,
7、设A 是集合，A的所有子集为元素做成的集合称为A的幂集，记以(A)或 2A。(A)=S|S A例：A=a,b,c，则(A)=,a,b,c,a,b,a,c,b,c,a,b,c,【定义3】幂集(power set),若A为有穷集，|A|=n，则|2A|=Cn0+Cn1+Cnn=2n。x(A)当且仅当xA。设A、B是两个集合，AB当且仅当(A)(B)；,幂集的性质,设C是一个集合。若C的元素都是集合，则称C为集合族。若集合族C可表示为C=SddD，则称D为集合族C的标志（索引）集。,【定义4】集合族、标志集,显然，2A是一个集合族。设A1,A2,A3,是集合的序列，且两两之间互不相同，则集合A1,A
8、2,A3,是一个集合族，可表示为Ai|iN，其中,N是自然数集合，是该集合的标志集合。,设A，B是两个集合。所有属于A或者属于B的元素做成的集合，称为A和B的并集，记以AB。即AB=x|xA或xB例如，令A=a，b，c，d，B=c，d，e，f，于是AB=a，b，c，d，e，f。,【定义5】集合的并集(Union),并集的文氏图,A,B,AB,设A，B是两个集合。由属于A又属于B的元素组成的集合，称为A和B的交集，记以AB。即AB=x|xA且xB例如，令A=a，b，c，d，B=c，d，e，f，于是AB=c，d。,【定义6】集合的交集(Intersection),交集的文氏图,A,B,AB,设A1
9、，A2，An是n个集合，则，A1A2An，简记为A1A2An，简记为,并集和交集的推广,容斥原理(principle of inclusion-exclusion),容斥原理是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿。定理：设A、B是任意有限集合，有：|AB|=|A|+|B|-|AB|,设A1，A2，An是n个集合，则,容斥原理(principle of inclusion-exclusion),称为包含排斥原理，简称容斥原理。,设A，B是两个集合。由属于集合A而不属于集合B的所有元素组成的集合，称为A与B的差集，记以A-
10、B，或AB。即A-B=x|xA且xB例如，令A=a，b，c，d，B=c，d，e，f，于是A-B=a，b。,【定义7】集合的差集(Difference),差集的文氏图,A,B,A-B,E,设A是一个集合，全集E与A的差集称为A的余集或补集，记以A。即A=E-A例如，令E=a，b，c，d，e，f，A=b，c，于是A=a，d，e，f。特别，,【定义8】集合的补集(Complement),补集的文氏图,A,A的补集,E,设A，B是两个集合。则A与B的环和(对称差),记以AB,定义为AB=(A-B)(B-A)。A与B的对称差还有一个等价的定义，即AB=(AB)-(AB)。例：令A=a，b，c，d，B=c
11、，d，e，f，于是AB=a，b，e，f。,【定义9】集合的对称差,对称差的文氏图,A,B,AB,E,设A，B是两个集合，则A与B的环积定义为 A B=AB,【定义10】集合的环积,A,B,E,我们将(a1,a2,an)称为有序n元组，其中，a1是其第一个元素，a2是其第二个元素，an是其第n个元素。两个有序n元组(a1,a2,an)和(b1,b2,bn)相等当且仅当ai=bi,i=1,2,n,【定义11】有序n元组(ordered n-tuple),对于有序n元组，当n=2时，我们将其称作有序二元组，也称作有序对,或序偶。有序对的特点：若ab,则(a,b)(b,a)两个有序对(a,b)和(c,
12、d)相等当且仅当a=c，b=d,【定义12】有序对(ordered pairs),设A，B是两个集合，所有有序对(x,y)做成的集合(其中xA，yB)，称为A，B的直乘积(笛卡儿积)，记以AB。AB=(x，y)xA且yB。,【定义13】笛卡儿积(Cartesian product),设A1,A2,An是n个集合，由所有有序n元组(a1,a2,an)做成的集合(其中aiAi，i=1,2,n)，称为A1,A2,An的直乘积(笛卡儿积)，记以A1A2 An。A1A2 An=(a1,a2,an)aiAi，i=1,2,n。,【定义14】笛卡儿积的推广,设A=1,2，B=a,b,c,则AB=(1,a),(
13、1,b),(1,c),(2,a),(2,b),(2,c)；BA=(a,1),(a,2),(b,1),(b,2),(c,1),(c,2)；,例如：,|AB|=A B；对任意集合A，有A=，A=；直乘积运算不满足交换律，即ABBA；直乘积运算不满足结合律，即(AB)CA(BC),直乘积的性质,5.直乘积运算对并和交运算满足分配律，即:A(BC)=(AB)(AC)，(BC)A=(BA)(CA)，A(BC)=(AB)(AC)，(BC)A=(BA)(CA)；6.设A，B，C，D是集合，若AC且BD，则AB CD。,等幂律：AA=A，AA=A。交换律：AB=BA，AB=BA。结合律：(AB)C=A(BC)，(AB)C=A(BC)。分配律：A(BC)=(AB)(AC)，A(BC)=(AB)(AC)。吸收律：A(AB)=A，A(AB)=A。,对于任意集合A,B,C有如下算律：,互补律：摩根律：同一律：EA=A，A=A。零一律：A=，EA=E。双重否定律：,其它算律：,证明：任取，即aAB，亦即aA且aB，于是 且，故，所以任取，即 且，亦即aA且aB，于是aAB，故，所以从而，得证。,证明：,证明：,
