第2-1章 集合及其运算.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,2,篇集合与关系,第,2-1,章 集合及其运算,第,2-2,章 二元关系,第,2-3,章 函数,第,2-1,章 集合及其运算,2-1-1,集合的概念 及其表示,2-1-2,集合的基本运算,2-1-3,集合中元素的计数,2-1-1,集合的概念及其表示,一集合的概念,一些事物汇集到一起组成一个整体就叫,集合,，,而这些事物就是这个集合的,元素,或,成员,。,例如：方程,x,2,1,0,的实数解集合；,26,个英文字母的集合；坐标平面上所有点的集合；,集合通常用大写英文字母来表示，,元素用小写字母表示,实数集合,R,，,复数集合,C,等。,自然数集合,N,，,整数集合,Z,，,有理数集合,Q,，,集合的表示方法有两种：列举法和谓词法。,例如,:A=a,，,b,，,c,，,，,z,Z=0,，,1,，,2,，,列举法,（穷举法）,x|xRx,2,10,谓词法,(,叙述法,),描述集合中元素的属性,x|P(x),使,P(x),成立的所有元素的集合,例如：方程,x,2,1,0,的实数解。,集合的元素是彼此不同的（无重复性）,集合的元素是无序的。,1，2，33，1，2,1，1，2，2，31，2，3,|A|,表示,A,中元素个数,树形图来表示隶属关系，该图分层构成，每个层上的结点都表示一个集合，它的儿子就是它的元素。,元素和集合之间的关系,隶属关系,属于,或,不属于,，属于记作，不属于记作,例如,:,A,a,，,b,，,c,，,d,，,d,aA，b，cA，dA，dA，,b,A，d,A,规定：对任何集合,A,都有,A,A,。,规定集合的元素都是集合。,定义,1.2,包含关系,设,A,，,B,为集合，如果,A,中的每个元素都是,B,中,的元素，则称,A,是,B,的子集合，或,A,包含于,B,，,或,B,包含,A,，,记作,A,B,，或,B,A,。,如果,A,不被,B,包含，则记作,A B,。,例如,N Z Q R C,，但,Z N,。,对任何集合,A,都有,A,A,。,A,B,x(,xAxB,),集合间的包含关系,“,”,的性质,1,、自反性,2,、传递性,(A,B),(B,C),(A,C),二集合之间的关系,定义,1.1,相等关系,当且仅当两个集合所有元素都相同，记做,A=B,；,不相等记做,A,B,例如：,1,，,2,，,4=1,，,4,，,2=1,，,2,，,2,，,4,1,，,2,，,4,1,，,2,，,4,A=B,(,A,B,),(,B,A,),由包含关系，可见,定理,1.1,外延性原理,证明集合相等的方法：互为子集,定义,1.3,真包含,设,A,，,B,为集合，如果,A,中每个元素都属于,B,，而,B,中至少有一个元素不属于,A,，,则称,A,是,B,的真子集。,记作,A,B,。,A,B,x(,xAxB,),x(,xB,x,A,),A,B,(,A,B,),(,A,B,),例如,N Z Q R C,，但,N N,。,三特殊的集合,定义,1.4,空集,不含任何元素的集合叫做,空集,，记作 。,例如：方程,x,2,+1,0,的实根的集合。,定理,1.2,对任一集合,A,，,定义,1.5,全集,在一定范围内，如果所有集合均为某一集合的,子集，则称该集合为,全集,，记做,E,。,定义,1.6,幂集,给定集合,A,，,由集合,A,的所有子集为元素组成,的集合，称为集合,A,的,幂集,，记做,P(A)(,或,2,A,),。,P(A)=X|X,A,例1.5 A=0，1，2，求P(A),定理,1.3,设,A=a,1,，,a,2,，,，,a,n,，则,|P(A)|=2,n,四集合的数码表示,计算机中表示集合,及其幂集（数码表示法）,设集合,A,2,=x,1,，,x,2,对集合中元素标定次序，,x,1,是第一个元素，,x,2,是第二个元素,P(,A,2,)=，,x,1,，,x,2,，,x,1,，x,2,S,00,S,10,S,01,S,11,P(,A,2,)=S,i,|,i,J,J,=00,01,10,11,将,J,中二进制转成十进制数,J,=0,1,2,3,P(A,2,)=S,i,|,i,J,J,=,i,|,i,是两位二进制数且,i,=0,1,2,3,扩展到,n,个元素情况,P(,A,n,)=S,i,|,i,J,J,=,i,|,i,是,n,位二进制数 且,0,i,2,n,-1,例,：,A,6,=x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,写出,S,7,和,S,12,代表的两个子集,7=000111,12=001100,S,7,=x,4,，x,5,，x,6,S,12,=x,3,，x,4,2-1-2,集合的基本运算（,5,种）,并,、交,、相对补,、绝对补,、对称差,一、并运算,定义,2.1,设,A,、,B,是任意两个集合，所有属于,A,或者,属于,B,的元素组成的集合，称为,A,与,B,的并集。,记做,A,B,A,B=x|(xA,),(,xB,),例,2.2,设,A,B,，,C,D,，,则,AC,BD,二、交运算,定义,2.2,设,A,、,B,是任意两个集合，由,A,和,B,的公共,元素组成的集合，称为,A,与,B,的交集。,记做,A,B,A,B=x|(xA,),(,xB,),例,2.5,设,A,是能被,5,整除的整数集合，,B,是能被,8,整,除的整数集合。,A,B,是能被,40,整除的整数集合。,定理,2.1,设,A,、,B,、,C,为任意三个集合，则,(1),幂等律,AA=A AA=A,(2),交换律,AB=BA AB=BA,(3),结合律,(AB)C=A(B C),(4),同一律,A,=A AE=A,(5),零律,A,E,=E A,=,(6)A,AB，B,AB,(AB)C=A(BC),(7)AB=B A,B,(6)AB,A，AB,B,(7)AB=A A,B,三、交运算和并运算之间的联系,定理,2.3,分配律,(1),交运算对并运算的分配律,(2),并运算对交运算的分配律,A,(B C)=(A,B)(A,C),A(B,C)=(AB),(AC),定理,2.4,吸收律,(1)A,(AB)=A,(2)A(A,B)=A,四、集合的补运算,定义,2.3,设,A,、,B,是任意两个集合，由属于,A,而不,属于,B,的一切元素构成的集合，称为,A,与,B,的差运算,（又称,B,对,A,补运算）。,记做,A-B,A,-,B=x|(xA,),(,x,B,),若,A=E,，,对任意集合,B,关于,E,的补集,E,B,，,称为,B,的绝对补集，,B,例6 设A=1，2，3，4，5，B=1，2，4，7,AB=,3，5,例,7,设,A,是素数集合，,B,是奇数集合，,AB=,2,定理,2.5,设,A,、,B,、,C,为任意三个集合，则,(9),若,A,B,，,当且仅当,五、集合的对称差运算,定义,2.4,设,A,、,B,是任意两个集合，由“属于,A,而不,属于,B”,或“属于,B,而不属于,A”,的一切元素构成的,集合，称为,A,与,B,的对称差。,记做,A,B,A,B=(A,B),(B,A),=x|(xA)(xB),A,B=(A,B),(A,B),例6 设A=1，2，3，4，5，B=1，2，4，5，7,A,B=,3，7,定理,2.6,设,A,、,B,、,C,为任意三个集合，则,(1)A,B=B,A,(2)A,=A,(3)A,A=,文氏图表示集合关系及运算,例,证明,(A,B)B,AB,证,:,(A,B)B,(AB)B,(AB)(,BB),(AB)E,AB,化简,(ABC)(AB),(A(B,C)A),解：,(ABC)(AB),(A(B,C)A),B,A,(AB),A,2-1-3,集合中元素的计数,一、两个基本原理,加法原理,：若一个事件以,m,种方式出现,(,这些方式,构成集合,A),，,另一个事件以,n,种事件出现,(,这些方,式构成集合,B),，,这两个事件完成一件即能达到目,的，则达到目的的方式数为,m+n,。,例,3.1,假设从城市,A,到城市,B,有铁路两条，公路三,条，航线一条，则从城市,A,到城市,B,有,条。,乘法原理,：若一个事件以,m,种方式出现,(,这些方式,构成集合,A),，,另一个事件以,n,种事件出现,(,这些方,式构成集合,B),，,这两个事件同时完成才能达到目,的，则达到目的的方式数为,mn,。,例,3.2,一位学生想从图书馆借,离散数学,和,C,语言,各一本，书架上有,3,种不同作者的离散,数学书，有,2,种不同作者的,C,语言书，那么这位学,生共有,种不同的选法。,二、排列、组合,从,n,个元素的集合中每次取,m,个的排列和组合的,计算公式分别为,排列和组合的最基本恒等式有：,例,3.3,将英文单词“,Computer”,的字母全部取出进,行全排列，其中,C,不在第一位，,r,不在末位，问共有,多少种不同的排法？,解：“,Computer”,的字母的全排列数有,其中,C,排在第一位的排法有,7,！种；,r,排在末位的排法有,7,！种。,设为集合,E,设为集合,A,设为集合,B,|E|=8!，|A|=7!，|B|=7!,AB=|A|+|B|,A,B,|A,B|=6!,AB=7!+7!,6!,E AB=8!7!7!+6!,=30960,A,B,E,A,B,E,E AB,例,3.4,将,1,，,2,，,3,三个数字排成,2,行,3,列的矩阵，,要求同行和同列上都没有相同的数字，问这样的,数字矩阵有多少？,解：先排矩阵的第一行共有 种排法,如果不管题目要求，第二行也有 种排法,可知，由这,3,个数字排成同行没有相同数字的矩阵,共有,36,种,(,乘法原理,),。,题目要求同列也没有相同数字,设同列中有相同数字的矩阵分为几种情况：,有一列数字相同其他两列数字不同；,有两列数字相同,(,三列数字相同,),；,同行同列上都没有相同数字的矩阵有,36-18-6=12,种,一般地，从,n,个元素的集合中抽群,m,个元素，允许,重复的排列数为：,n,m,。,可以设想有,m,个位子，每个位子都可以放,n,个元素,中的任一个，允许重复，,例,3.5,求电子计算机中的,6,位二进制数。,例,3.6,考试时有,25,个正确或错误的问题，学生也,可能不作答，问有多少种不同的考试结果。,重复组合数问题,从,1,，,2,，,3,种每次取出两个（允许重复抽取）的,组合按自然数顺序写出来（枚举）：,11，12，13，22，23，33,现将各种组合分别加上,01,，就得到,12，13，14，23，24，34,组合,(2),恰好是从,1,，,2,，,3,，,4,中任取两个不重复元素的组合,(,自然数顺序,),情况,组合,(1),组合,(2),组合,(1),组合,(2),+01,01,一一对应的关系,所以，从三个互异元素中任取两个的重复组合数,可转化为从四个互异元素中任取两个不重复,的元素的组合数 来计算。,推广到一般情况，从,n,个互异元素中任取,m,个,的重复组合数 可转换为从,n+m-1,个互异,元素中任取,m,个不重复元素的组合数。,考虑从,1,，,2,，,3,，,，,n,任取,m,个允许重复的元素,每一组合，将其元素分别加上,0,，,1,，,2,，,，,m-1,，,即变成从,1,，,2,，,3,，,，,n,，,n+1,，,，,n+m-1,任取,m,个不重复元素的组合。,例,3.7,求成自然序的四位数码的个数,解：四位数码是从,0,1,2,3,4,5,6,7,8,9,中选四个,数字组成，数字可以重复，属于重复组合数问题。,相当于从十个互异元素中选四个允许重复的组合。,环状排列问题,例,3.8 8,位朋友围圆桌而坐，若座位不编号有多少,种坐法？座位编号又有多少种坐法？,1,8,7,6,5,4,3,2,12345678,2,1,8,7,6,5,4,3,23456781,8,7,6,5,4,3,2,1,81234567,8,种,1,2,3,4,5,6,8,18765432,7,8!/8=7!,座位不编号,3,2,1,8,7,6,5,4,34567812,若座位编号，属于,全排列,问题,8!=40320,例,3.9 5,颗红珠，,3,颗白珠，穿在一个项链上，有,多少种方法？,分析：环状排列问题，,解：若,8,颗珠子互异，则有,7,！种串法,但,5,颗红珠相同；,3,颗白珠也相同,三、容斥原理,集合的基数,设集合,A=a,1,a,2,a,n,，,含有,n,个元素，称集合,基数为,n,记做,CardA,=n,也可记作,|A|=n,。,称,A,为有穷集，否则称为无穷集,空集的基数为,0,定理,3.1,容斥原理,设,A,，,B,为有限集合，则,|AB|=|A|+|B|,|AB|,定理,3.2,设,A,，,B,为有限集合，则,|A,B|=|A|+|B|,2,|AB|,例,3.10,假设,10,名青年中有,5,名是工人，,7,名是学生,其中既是工人又是学生的有,3,名，问既不是工人又,不是学生的有几名？,E,A,B,A=,工人,B=,学生,|AB|=3,|A|=5,|B|=7,要求的部分为,E,AB,|AB|=|A|+|B|AB|,=5+7-3=9,|EAB|=109=1,定理,3.3,（容斥原理）,设,A,为有穷集,P,1,，,P,2,，,，,P,m,是,m,个不同的性质，,令,A,i,表示,A,中具有性质,P,i,的元素构成的子集，,i,=1,2,，,m,，,A,i,A,j,(,i,j,),表示,A,中同时具有性质,P,i,和,P,j,的元素组成的子集，,A,i,A,j,A,k,(,i,j,k,),表示,A,中,同时具有性质,P,i,、,P,j,和,P,k,的元素组成的子集，,A,中至少具有一条性质的元素数为,A,中不具有性质,P,1,，,P,2,，,P,m,的元素数为,例,3.11,求不超过,1000,的自然数中能被,2,或,3,或,5,整除的数的个数？,解：设,A=1,2,，,1000,，,研究对象的集合,(,全集,),在,A,上定义性质,P,1,P,2,P,3,，,分别表示能被,2,、,3,、,5,整除，设,A,1,，,A,2,，,A,3,分别表示具有性质,P,1,P,2,P,3,的集合。,所求部分为,|,A,1,A,2,A,3,|,|,A,1,|=500,|,A,2,|=333,|,A,3,|=200,|,A,1,A,2,A,3,|=|,A,1,|+|A,2,|+|,A,3,|,|,A,1,A,2,|,|,A,1,A,3,|,|,A,2,A,3,|+|,A,1,A,2,A,3,|,|,A,1,A,2,|=166|,A,1,A,3,|=100|,A,2,A,3,|=66|,A,1,A,2,A,3,|=33,|,A,1,A,2,A,3,|=500+333+200,166,100,66,+33=734,例,3.12,某汽车工厂装配了三十辆汽车，可供选择,的设备是收录机，空调器，防盗器，三十辆汽车中,有,15,辆汽车装有收录机，,8,辆装有空调器，,8,辆装有,防盗器，三种设备都具有的汽车有,3,辆，问这三种,设备都没有的汽车有几辆？,解：设,A,，,B,，,C,分别表示具有收录机，空调器，,防盗器的汽车集合，,依题意，要求的汽车集合为,已知，,|A|=15,，,|B|=8,，,|C|=8,，,|A,B,C|=3,错位排列,的计数问题。,有,n,个人在参加晚会时寄存了自己的帽子，可是保,管人忘记放寄存号，当每个人领取帽子时，他只能,随机选择一顶帽子交给寄存人。问在,n!,种领取帽子,的方式中，有多少种方式使得每个人都没有领到自,己的帽子？如果将这些人与他们的帽子分别标号为,1,，,2,，,，,n,。设,j,领到的帽子标号为,i,j,，,j=1,2,，,n,，,那么这些人领到的帽子可以用排列,i,1,i,2,i,n,来表示，其中每个人都没有领到自己的,帽子的排列,i,1,i,2,i,n,满足,i,j,j,j=1,2,，,n,。,称这种排列为错位排列，错位排列数记做,D,n,，,证明：,证明：设,S,为,1,2,，,的排列的集合，,P,i,是,i,处在,排列中的第,i,位性质，,A,i,是,S,中具有性质,P,i,的排列,的集合，,i=1,2,，,n,。,错位排列数,D,n,就是,S,中不,具有以上任何一条性质的排列数。,隶属关系和包含关系都是两个集合之间的关系，对,于某些集合可以同时成立这两种关系。,例如,A,a,，,a,和,a,既有,aA,，,又有,a A,。,前者把它们看成是不同层次上的两个集合，后者把,它们看成是同一层次上的两个集合，都是正确的。,定义,6.2,设,A,，,B,为集合，如果,A B,且,B A,，,则称,A,与,B,相等,，记作,A,B,。,如果,A,与,B,不相等，则记作,AB,。,AB A BB A,相等的符号化表示为,定义,6.3,设,A,，,B,为集合，如果,B A,且,BA,，,则称,B,是,A,的,真子集,，记作,B A,。,如果,B,不是,A,的真子集，则记作,B A,。,真子集的符号化表示为,B A B ABA,例如,N,Z,Q,R,C,，但,N,N,。,定义,6.4,不含任何元素的集合叫做,空集,，记作 。,空集可以符号化表示为 ,x|xx,。,例如,x|xRx,2,+1=0,是方程,x,2,+1=0,的实数解集，,因为该方程无实数解，所以是空集。,定理,6.1,空集是一切集合的子集。,证,：任何集合,A,，,由子集定义有,A x(x xA),右边的蕴涵式因前件假而为真命题，所以,A,也为真。,推论,空集是唯一的。,证,：假设存在空集,1,和,2,，由定理,6.1,有,1,2,，,2,1,。根据集合相等的定义，有,1,2,。,含有,n,个元素的集合简称,n,元集,，它的含有,m(mn),个,元素的子集叫做它的,m,元子集,。,任给一个,n,元集，怎样求出它的全部子集呢？,例,6.1,A,1,2,3,，将,A,的子集分类：,解,:0,元子集，也就是空集，只有一个：；,1,元子集，即,单元集,：,1,，,2,，,3,；,2,元子集：,1,2,，,1,3,，,2,3,；,3,元子集：,1,2,3,。,一般地说，对于,n,元集,A,，,它的,0,元子集有 个，,1,元子集有 个，,，,m,元子集有 个，,，,n,元子集,有 个。,子集总数为,+,2,n,个。,定义,6.5,设,A,为集合，把,A,的全部子集构成的集合叫做,A,的,幂集,，记作,P(A)(,或,P,A,，,2,A,),。,幂集的符号化表示为,P(A),x|x A,例,6.1,中的集合,A,有,P(A),，,1,，,2,，,3,，,1,，,2,，,1,，,3,，,2,，,3,，,1,，,2,，,3,若,A,是,n,元集，则,P(A),有,2,n,个元素,定义,6.6,在一个具体问题中，如果所涉及的集合都是某,个集合的子集，则称这个集合为,全集,，记作,E,。,全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。,例如在研究平面上直线的相互关系时，可以把整个平面,(,平面上所有点的集合,),取作全集，也可以把整个空间,(,空间上所有点的集合,),取作全集。,一般地说，全集取得小一些，问题的描述和处理会简单些。,6.2,集合的运算,一集合的基本运算,集合的基本运算有并，交，相对补和对称差。,定义,6.7,设,A,，,B,为集合，,A,与,B,的,并集,AB,，,交集,AB,，,B,对,A,的,相对补集,A,B,分别定义如下：,ABx|xAxB ABx|xAxB,ABx|xAx B,A,或,B,中的元素构成,A,和,B,中的公共元素构成,属于,A,但不属于,B,的元素构成,a，b，c,a,b，c,例如,A,a,，,b,，,c,，,B,a,，,C,b,，,d,AB,AB,AB,BA,BC,如果两个集合的交集为 ，则称这两个集合是,不相交,的。,两个集合的并和交运算可以推广成,n,个集合的并和交：,A,1,A,2,A,n,x|xA,1,xA,2,xA,n,A,1,A,2,A,n,x|xA,1,xA,2,xA,n,A,1,A,2,A,n,A,1,A,2,A,n,AB A,并和交运算还可以推广到无穷多个集合的情况：,A,1,A,2,A,1,A,2,定义,6.8,设,A,，,B,为集合，,A,与,B,的,对称差集,A B,定义为：,A B(AB)(BA),例如,A,a,，,b,，,c,，,B,b,，,d,A Ba，c，d。,对称差运算的另一种定义是,A B(AB)(AB),在给定全集,E,以后，,A E,，,A,的,绝对补集,A,定义如下：,定义,6.9,A,E,A,x|xEx A,因为,E,是全集，,xE,是真命题，所以,A,可以定义为 ,A,x|x A,例如,E,a,，,b,，,c,，,d,，,A,a,，,b,，,c,Ad。,集合之间的关系和运算可以用,文氏图,(Venn Diagram),给予形象的描述。,文氏图的构造方法如下：,首先画一个大矩形表示全集,E(,有时为简单起见可,将全集省略,),，其次在矩形内画一些圆,(,或任何其它的,适当的闭曲线,),，用圆的内部表示集合。不同的圆代,表不同的集合。如果没有关于集合不交的说明，任何,两个圆彼此相交。图中阴影的区域表示新组成的集合,图,6.2,就是一些文氏图的实例。,三广义交和广义并,以上定义的,并,和,交,运算称为初级并和初级交。,下面考虑推广的并和交运算，即广义并和广义交。,定义,6.10,设,A,为集合，,A,的元素的元素构成的集合,称为,A,的,广义并,，记为,A,。,符号化表示为,A,x|z(zAxz),。,例6.4,设,Aa,b,c,a,c,d,a,e,f,BaCa,c,d,则,A,B,C,a,b,c,d,e,f,a,ac,d,根据广义并定义不难证明，若,A,A,1,A,2,A,n,，,则 ,A,A,1,A,2,A,n,。,类似地可以定义集合的广义交。,定义,6.11,设,A,为非空集合，,A,的所有元素的公共元素,构成的集合称为,A,的,广义交,，记为,A,。,符号化表示为,A,x|z(zAxz),Aa，Ba，Cac，d,和广义并类似，若,A,A,1,A,2,A,n,，,则,A,A,1,A,2,A,n,为了使得集合表达式更为简洁，我们对,集合运算的,优先顺序,做如下规定：称,广义并,，,广义交,，,幂集,，,绝对补,运算为,一类运算,，,并,，,交,，,相对补,，,对称差,运算为,二类运算,。,一类运算优先于二类运算。一类运算之间由右向左顺序进行。二类运算之间由括号决定先后顺序。,下面的集合公式：,A,B,，,P(A),，,P(A)B,，,(AB),都是合理的公式。,例,6.5,设,A,a,a,b,计算,A,，,A,和,A(A,A),。,解:,Aa,b Aa,A,ab A,a,A,ab,A,a,A(A,A),(ab)(ab)a),(ab)(ba),b,使用文氏图可以很方便地解决,有穷集合的计数问题,。,首先根据已知条件把对应的文氏图画出来。一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。,通常从,n,个集合的交集填起,，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为,x,。,根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。,6.3,有穷集的计数,例,6.2,对,24,名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为,13,，,5,，,10,和,9,人，其中同时会英语和日语的有,2,人，会英、德和法语中任两种语言的都是,4,人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言,(,英、德、法、日,),的人数和会三种语言的人数。,解,令,A,，,B,，,C,，,D,分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图,6.3,所示。设同时会三种语言的有,x,人，只会英、法或德语一种语言的分别为,y,1,，,y,2,和,y,3,人。将,x,和,y,1,，,y,2,，,y,3,填入图中相应的区域，然后依次填入其它区域的人数。,A,，,B,，,C,，,D,分别表示会英、法、德、日语的人的集合,根据已知条件列出方程组,如下：,解得,x,1,，,y,1,4,，,y,2,2,，,y,3,3,。,英,13,法,9,德,10,日,5,例,6.2,求,1,到,1000,之间（包含,1,和,1000,在内）既不能被,5,和,6,，也不能被,8,整除的数有多少个。,解：设,S,x|x,Z 1x1000,A,x|x,Z,x,可被,5,整除,B,x|x,Z,x,可被,6,整除,C,x|x,Z,x,可被,8,整除,用,|T|,表示有穷集，表示小于等于,x,的最大整数，,lcm(x,1,x,2,x,n,),表示,x,1,x,2,x,n,的最小公倍数，则有,|A|=200,|B|=166,|A,B|=33,|C|=125,|A,C|=25,|B,C|=41,|A,B,C|=8,将这些数字依次填入文史图，,得到图,6.4,，由图可知，,不能被,5,，,6,，,8,整除的数有,1000,（,200,100,33,67,）,600,A,B,C,150,100,67,25,17,33,8,定理,6.2,（包容排斥原理）设,S,为有穷集，,P,1,，,P,2,，,P,m,是,m,个性质，,S,中任何元素,x,或者具有性质,P,i,（,i=1,2,，,m,）,两种情况必居一种。令,A,i,表示,S,中具有性质,P,i,的元素构成的子集，则,S,中不具,有性质,P,1,，,P,2,，,P,m,的元素数为,=1000-(200+166+125)+(33+25+41)-8=600,推论,S,中至少具有一条性质的元素数为,例,6.7,错位排列,的计数问题。,有,n,个人在参加晚会时寄存了自己的帽子，可是保,管人忘记放寄存号，当每个人领取帽子时，他只能,随机选择一顶帽子交给寄存人。问在,n!,种领取帽子,的方式中，有多少种方式使得每个人都没有领到自,己的帽子？如果将这些人与他们的帽子分别标号为,1,，,2,，,，,n,。设,j,领到的帽子标号为,i,j,，,j=1,2,，,n,，,那么这些人领到的帽子可以用排列,i,1,i,2,i,n,来表示，其中每个人都没有领到自己的,帽子的排列,i,1,i,2,i,n,满足,i,j,j,j=1,2,，,n,。,称这种排列为错位排列，错位排列数记做,D,n,，,证明：,证明：设,S,为,1,2,，,的排列的集合，,P,i,是,i,处在,排列中的第,i,位性质，,A,i,是,S,中具有性质,P,i,的排列,的集合，,i=1,2,，,n,。,错位排列数,D,n,就是,S,中不,具有以上任何一条性质的排列数。,6.4,集合恒等式,一基本集合恒等式,下面的恒等式给出了集合运算的主要算律，其中,A,，,B,，,C,代表任意集合。,幂等律,AA,A,(6.1),AA,A,(6.2),结合律,(AB)C,A(BC),(6.3)(AB)C,A(BC),(6.4),交换律,AB,BA,(6.5)AB,BA,(6.6),分配律,A(BC),(AB)(AC),(6.7),A(BC),(AB)(AC),(6.8),同一律,A,A,(6.9),AE,A,(6.10),零律,AE,E,(6.11),A,(6.12),排中律,A,A,E,(6.13),矛盾律,A,A,(6.14),吸收律,A(AB),A,(6.15)A(AB),A,(6.16),德摩根律,A,(BC),(A,B)(A,C),(6.17)A,(BC),(A,B)(A,C),(6.18),(BC)=,B,C,(6.19),(BC)=,B,C,(6.20),E,(6.21),E,(6.22),双重否定律,(,A),A,(6.23),例,6.6,证明式,(6.17)A,(BC),(A,B)(A,C),集合证明中经常大量用到命题逻辑的等值式，在叙述中,采用半形式化的方法，其中 表示当且仅当,证明：对任意的,x,x A(BC),x A,(x B x C),x A,x (BC),x A,x B x C,(x A,x B)(x A x C),x(A B)x(A C),以上证明的基本思想是：,设，为集合公式，欲证，即证,P QQ P,为真。,也就是要证对于任意的,x,有,xP xQ,和,xQ xP,成立,对于某些恒等式可以将这两个方向的推理合到一起，,就是,xP xQ,不难看出，集合运算的规律和命题演算的某些规律,是一致的。所以命题演算的方法是证明集合恒等式,的基本方法。,例,6.8,假设已知等式,6.1,6.14,，试证等式,6.15,即,A,（,AB,）,A,证明：,A,（,AB,）（,AE,）（,AB,）,A,（,EB,）,AE,A,证明集合恒等式的另一种方法是利用已知的恒等式来,代入。,二证明技巧,证明技巧一,除了以上算律以外，还有一些关于集合运算性质,的重要结果。,AB A,，,AB B,(6.24),A AB,，,B AB,(6.25),A,B A,(6.26),A,B,A,B,(6.27),例,6.9,证明等式,6.27,，即,A,B,A,B,。,证,:,对于任意的,x,，,xAB xAx B,xAx,B,xA,B,所以,A,B,A,B,。,把相对补运算转换成交运算，这在证明有关相对补,的恒等式中是很有用的。,A-B=A B AB=B AB=A。,证明：,过程如下,A-B=A B AB=B AB=A A-B=。,假设,A B,A B,xA,x B,xA-B,与,A-B=,矛盾,显然,B AB,反之，任取,x,，,xAB,xAxB,xBxB,（A B）,xB,因此,AB B,。,显然,AB A,，,任取,x,，,xA,AB=B AB=A,xAB,xB,xA,xB,xA,B,A AB,因此,假设存在,xA-B,，,xAx B,xAB x B,假设,A-B,AB=A A-B=,xA,xB x B,出现矛盾,例,6.10,证明,(A,B)B,AB,证,:,(A,B)B,(AB)B,(AB)(,BB),(AB)E,AB,例,6.12,化简,(ABC)(AB),(A(B,C)A),解：,(ABC)(AB),(A(B,C)A),(AB),A,B,A,例,6.13,已知,A B,A C,，,证明,B,C,证明：,已知,A B,A C,，,所以有,主要内容,1.,集合，相等，（真）包含，子集，空集，全集，幂集,2.,交，并，（相对和绝对）补，对称差，广义交，广义并,3.,文氏图，有穷集计数问题,4.,集合恒等式（等幂律，交换律，结合律，分配律，,德,摩根律，吸收律，零律，同一律，排中律，,矛盾律，余补律，双重否定律，补交转换律等）,学习要求,熟练掌握集合的子集、相等、空集、全集、幂集等概,念及其符号化表示,2.,熟练掌握集合的交、并、（相对和绝对）补、对称差、,广义交、广义并的定义及其性质,3.,掌握集合的文氏图的画法及利用文氏图解决有限集的,计数问题的方法,4.,牢记基本的集合恒等式（等幂律、交换律、结合律、,分配律、德,摩根律、收律、零律、同一律、排中律、,矛盾律、余补律、双重否定律、补交转换律）,5.,准确地用逻辑演算或利用已知的集合恒等式或包含式,证明新的等式或包含式,1.,证明,A-B=A AB=,。,xAB,xA,x,B,xA-B,x,B,（,因为,A-B=A,）,xA,x,B,x,B,出现矛盾,证明：必要性。,A-B=A AB=,假设,AB,充分性。,AB=A-B=A,A-B=(A-B),（,A,B,）（,AB,）,A,（,B,B,）,AEA,A-B=A,A=B=,A=B,A=B,3.,设,A,B,为集合，试确定下列各式成立的充分必要条件：,（1）A-B=B,（2）A-B=B-A,（3）AB=AB,（4）A B=A,B=,(A-B)B=,ABB,BB,B=,A B=A,A (A B)=A A,B=,4.,判断下列命题是否为真。,（,1,）,为真,为假,（,2,）,为真,为假,（,3,）,;,为假,为真,（,4,）,;,为真,为假,（5）xx,x-x;,为真,为假,（6）x x,x-x.,为真,为假,5.,设,F,表示一年级大学生的集合，,S,表示二年级大学生的集合，,M,表示数学专业学生的集合，,R,表示计算机专业学生的集合，,T,表示听离散数学课学生的集合，,G,表示星期一晚上参加音乐会的学生的集合，,H,表示星期一晚上很迟才睡觉的学生的集合。问下列各句子所对应的集合表达式分别是什么？请从备选的答案中挑出来。,(1),所有计算机专业二年级的学生在学离散数学课。,(2),这些且只有这些学离散数学课的学生或者星期一晚上,去听音乐会的学生在星期一晚上很迟才睡觉。,(3),听离散数学课的学生都没参加星期一晚上的音乐会。,SR T,H=GT,TG=,(4),这个音乐会只有大学一、二年级的学生参加。,(5),除去数学专业和计算机专业以外的二年级学生都去参,加了音乐会。,G FS,S-(RM)G,备选答案：,T GH GH T SR T,HGT TG FS G,G FS S-(RM)G G S-(RM),