集合的基本概念和运算.ppt

Click to edit Master text styles,Second level,Third level,Fourth level,Click to edit Master title style,集合的基本概念和运算,主要内容,集合的基本概念,集,合、相等、,(,真,),包含、子集、空集、全集、幂集,集合运算,交、并、,(,相对和绝对,),补、对称差,文氏图,有穷集计数问题,集合恒等式,集合的基本概念,集合,(Set),是不能精确定义的基本概念。,所谓集合，是指我们无意中或思想中将一些确定的、彼此完全不同的客体的总和而考虑为一个整体。这些客体叫做该集合的元素。,(,康托,),直观地说，把一些事物汇集到一起组成一个整体就叫,集合,，而这些事物就是这个集合的,元素,或,成员,。,例如：,方程,x,2,1,0,的实数解集合：,26,个英文字母的集合；,坐标平面上所有点的集合；,集合通常用大写的英文字母来标记。,常见的数的集合,N,自然数集合,Z,整数集合,Q,有理数集合,R,实数集合,C,复数集合,集合的表示方法,表示一个集合的方法主要有两种：,列元素法,和,谓词表示法,。,列元素法,是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。,A,a,，,b,，,c,，,，,z,Z,0,，,1,，,2,，,C,桌子,灯泡,老虎,自然数,谓词表示法,是用谓词来概括集合中元素的属性。,B,x|x,R,x,2,1,0,许多集合可以用两种方法来表示，如,B,也可以写成,-1,，,1,。但是有些集合不可以用列元素法表示，如实数集合。,集合的元素,集合的元素是彼此不同的，如果同一个元素在集合中多次出现应该认为是一个元素。,例如：,1,，,1,，,2,，,2,，,3,1,，,2,，,3,集合的元素是无序的。,例如：,1,，,2,，,3,3,，,1,，,2,元素和集合之间的关系,元素和集合之间的关系是隶属关系，即,属于,或,不属于,，属于记作,，不属于记作,。,例如：,A,a,，,b,，,c,，,d,，,d,a,A,，,b,，,c,A,，,d,A,，,d,A,，,bA,，,d,A,。,b,和,d,是,A,的元素的元素。,可以用一种树形图表示集合与元素的隶属关系。集合作为结点，它的元素作为其儿子。,说明,隶属关系可以看作是处在不同层次上的集合之间的关系。,规定：对任何集合,A,都有,A,A,。,A,a,b,c,d,d,b,c,d,d,子集,定义,6.1,设,A,，,B,为集合，如果,B,中的每个元素都是,A,中的元素，则称,B,是,A,的子集合，简称,子集,。这时也称,B,被,A,包含,，或,A,包含,B,，,记作,B,A,。,包含的符号化表示为,B,A,x(xBxA),如果,B,不被,A,包含，则记作,B A,。,例如：,N,Z,Q,R,C,，但,Z N,。,显然对任何集合,A,都有,A,A,。,隶属和包含的说明,隶属关系和包含关系都是两个集合之间的关系，对于某些集合可以同时成立这两种关系。（,本书的系统中把集合中的元素也看做（同一层次的）集合,）,例如,A,a,，,a,和,a,既有,a,A,，,又有,a,A,。,前者把它们看成是不同层次上的两个集合，,后者把它们看成是同一层次上的两个集合。,集合相等,定义,6.2,设,A,，,B,为集合，如果,A,B,且,B,A,，,则称,A,与,B,相等,，记作,A,B,。,相等的符号化表示为：,A,B,A,B,B,A,如果,A,与,B,不相等，则记作,A,B,。,真子集,定义,6.3,设,A,，,B,为集合，如果,B,A,且,BA,，,则称,B,是,A,的,真子集,，记作,B,A,。,真子集的符号化表示为,B,A,B,A BA,如果,B,不是,A,的真子集，则记作,B,A,。,例如：,N,N,空集,定义,6.4,不含任何元素的集合叫做,空集,，记作,。,空集的符号化表示为：,x|xx,。,例如,:x|xRx,2,+1=0,是方程,x,2,+1=0,的实数解集，因为该方程无实数解，所以是空集。,空集的性质,推论 空集是唯一的。,证明：假设存在空集,1,和,2,，由上述定理有,1,2,，,2,1,。,根据集合相等的定义，有,1,2,。,定理,空集是一切集合的子集。,证明,：,任给集合,A,，,由子集定义有,A,x(x,xA),右边的蕴涵式因前件假而为真命题，,所以,A,也为真。,n,元集,含有,n,个元素的集合简称,n,元集,，它的含有,m(mn),个元素的子集叫做它的,m,元子集,。,例,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,元子集有 个。子集总数为,定义,设,A,为集合，把,A,的全部子集构成的集合叫做,A,的,幂集,，记作,P(A)(,或,PA,2,A,),。,幂集的符号化表示为,P(A),x|x,A,若,A,是,n,元集，则,P(A),有,2,n,个元素。,全集,定义,在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为,全集,，记作,E,。,说明,全集是有相对性的，不同的问题有不同的全集，即使是同一个问题也可以取不同的全集。,例如，在研究平面上直线的相互关系时，可以把整个平面,(,平面上所有点的集合,),取作全集，也可以把整个空间,(,空间上所有点的集合,),取作全集。,一般地说，全集取得小一些，问题的描述和处理会简单些。,集合的运算,定义,6.7,设,A,，,B,为集合，,A,与,B,的,并集,AB,，,交集AB,，,B,对,A,的,相对补集,A,B,分别定义如下：,AB,x|xAxB,AB,x|xAxB,A,B,x|xAx,B,举例,设,A,a,，,b,，,c,，,B,a,，,C,b,，,d,则有,A,B,a,，,b,，,c,，,A,B,a,，,A,B,b,，,c,，,B,A,，,B,C,说明,如果两个集合的交集为,，则称这两个集合是不相交的。例如,B,和,C,是不相交的。,n,个集合的并和交,两个集合的并和交运算可以推广成,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,1A,2,A,n,A,1,A,2,A,n,两个集合的并和交运算可以推广到无穷多个集合的情况：,A,1,A,2,A,1,A,2,对称差集,定义,设,A,，,B,为集合，,A,与,B,的,对称差集,A,B,定义为：,A,B,(A,B)(B,A),对称差运算的另一种定义是,A,B,(AB),(AB),例如,:A,a,，,b,，,c,，,B,b,，,d,，,则,A,B,a,，,c,，,d,绝对补集,定义,A,E,A,x|xEx,A,因为,E,是全集，,xE,是真命题，所以,A,可以定义为：,A,x|x,A,例如,:E,a,，,b,，,c,，,d,，,A,a,，,b,，,c,A,d,文氏图,集合之间的关系和运算可以用,文氏图,给予形象的描述。,文氏图的构造方法如下：,画一个大矩形表示全集,E(,有时为简单起见可将全集省略,),。,在矩形内画一些圆,(,或任何其它的适当的闭曲线,),，用圆的内部表示集合。,不同的圆代表不同的集合。如果没有关于集合不交的说明，任何两个圆彼此相交。,图中阴影的区域表示新组成的集合。,可以用实心点代表集合中的元素。,文氏图的实例,有穷集的计数问题,使用文氏图可以很方便地解决,有穷集的计数问题,。,首先根据已知条件把对应的文氏图画出来。,一般地说，每一条性质决定一个集合。,有多少条性质，就有多少个集合。,如果没有特殊说明，任何两个集合都画成相交的,然后将已知集合的元素数填入表示该集合的区域内。,通常从,n,个集合的交集填起，,根据计算的结果将数字逐步填入所有的空白区域。,如果交集的数字是未知的，可以设为,x,。,根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。,例,对,24,名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为,13,，,5,，,10,和,9,人，其中同时会英语和日语的有,2,人，会英、德和法语中任两种语言的都是,4,人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言,(,英、德、法、日,),的人数和会三种语言的人数。,解：令,A,，,B,，,C,，,D,分别表示会英、法、德、日语的人的集合。根据题意画出文氏图。设同时会三种语言的有,x,人，只会英、法或德语一种语言的分别为,y,1,，,y,2,和,y,3,人。将,x,和,y,1,，,y,2,，,y,3,填入图中相应的区域，然后依次填入其它区域的人数。,4-x,4-x,4-x,x,y,2,y,1,y,3,2,5-2,英,13,法,9,德,10,日,5,y,1,+2(4-x)+x+213,y,2,+2(4-x)+x9,y,3,+2(4-x)+x10,y,1,+y,2,+y,3,+3(4-x)+x24-5,包含排斥原理,定理,设,S,为有穷集，,P,1,P,2,P,m,是,m,个性质。,S,中的任何元素,x,或者具有性质,P,i,，,或者不具有性质,P,i,(i=1,2,m),两种情况必居其一。令,A,i,表示,S,中具有性质,P,k,的元素构成的子集，则,S,中不具有性质,P,1,P,2,P,m,的元素为,推论,S,中至少具有一条性质的元素数为,例,求,1,到,1000,之间,(,包含,1,和,1000,在内,),既不能被,5,和,6,，也不能被,8,整除的数有多少个。,解答,设,S,x|x,Z,1,x,1000,A,x|x,S,x,可被,5,整除,B,x|x,S,x,可被,6,整除,C,x|x,S,x,可被,8,整除,|T|,表示有穷集,T,中的元素数,x,表示小于等于,x,的最大整数,l,cm(x,1,x,2x,n,),表示,x,1,x,2,x,n,的最小公倍数,|A|,1000/5,200,|B|,1000/6,166,|C|,1000/8,125,|A,B|,1000/,l,cm(5,6),33,|A,C|,1000/,l,cm(5,8),25,|B,C|,1000/,l,cm(6,8),41,|A,B,C|,1000/,l,cm(5,6,8),8,将这些数字依次填入文氏图，得到,根据包含排斥原理，所求不能被,5,，,6,和,8,整除的数应为,由文氏图也可得知，不能被,5,，,6,和,8,整除的数有,1000,(200+100,33,67),600,个。,集合恒等式,下面的恒等式给出了集合运算的主要算律，其中,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)(AC)(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),集合运算性质的一些重要结果,AB,A,，,AB,B(6.24),A,AB,，,B,AB(6.25),A,B,A(6.26),A,B,A,B (6.27),AB,B,A,B,AB,A,A,B,(6.28),A,B,B,A(6.29),(A,B),C,A,(B,C)(6.30),A,A (6.31),A,A,(6.32),A,B,A,C,B,C (6.33),对偶原理,对偶式,：一个集合表达式，如果只含有、,、,、,E,、,、,，,那么同时把与互换，把,与,E,互换，把,与互换,，得到式子称为原式的对偶式。,对偶原理,：对偶式同真假。或者说，集合恒等式的对偶式还是恒等式。,集合恒等式的证明方法,逻辑演算法,利用,逻辑等值式,和,推理规则,集合演算法,利用,集合恒等式,和,已知结论,逻辑演算法的格式,题目：,A,B,证明：,x,，,xA,xB,所以,A,B,或证,A,B,B,A,题目：,A,B,证明：,x,，,xA,xB,所以,A,B,集合演算法的格式,题目：,A,B,证明：,A,B,所以,A,B,题目：,A,B,证明：,A,B,所以,A,B,例,证明,A,(B,C),(A,B),(AC),证明 对任意的,x,，,有,x,A,(B,C),x,A,x,B,C,x,A,(x,B,x,C),x,A,(,x,B,x,C),x,A,(,x,B,x,C),(x,A,x,B),(x,A,x,C),x,A,B,x,A,C,x,(A,B),(A,C),所以,A,(B,C),(A,B),(A,C),例,证明,A,E,A,证明 对任意的,x,，,有,x,AE,x,A,x,E,x,A(,因为,x,E,是恒真命题,),所以,A,E,A,例,证明,A,B,A,B,证明 对于任意的,x,，,有,xA,B,xA x,B,xA x,B,xA,B,所以,A,B,A,B,。,说明,等式,6.27,把相对补运算转换成交运算，这在证明有关相对补的恒等式中是很有用的。,例,证明,(A,B)B,AB,证明,(A,B)B,(A,B)B,(AB)(,BB),(AB)E,AB,例,证明,AB,B,A,B,AB,A,A,B,说明,上式给出了,A,B,的另外三种等价的定义，这不仅为证明两个集合之间的包含关系提供了新方法，同时也可以用于集合公式的化简。,证明思路,AB,B,A,B,AB,A,A,B,AB,B,证明,AB,B,A,B,对于任意的,x,，,有,xA,xAxB,xAB,xB(,因为,AB,B),所以,A,B,。,证明,A,B,AB,A,显然有,AB,A,，,下面证,A,AB,。,对于任意的,x,，,有,xAxAxA,xAxB(,因为,A,B),xAB,所以,A,AB,由,集合相等,的定义有,AB,A,。,证明,AB,A,A,B,A,B,A,B,(AB),B(,因为,AB,A),A(B,B),A,证明,A,B,AB,B,。,由,例,6.10,(A,B)B,AB,及,A,B,有,AB,B(A,B),B,B,例,化简,(ABC)(AB),(A(B,C)A),解答 因为,AB,ABC,，,A,A(B,C),，,从而，,(,AB,C),(AB),(,A(,B,C),A,),(AB),A,B,A,例,已知,A,B,A,C,，,证明,B,C,。,证明,已知,A,B,A,C,，,所以有,A,(A,B),A,(A,C),(A,A),B,(A,A),C(,由式,6.30),B,C,(,由式,6.32),B,C,(,由式,6.29),B,C,(,由式,6.31),作业,P.75-76,3.13(2)(4),3.14(3),3.18,典型题,判断元素与集合的隶属关系以及集合之间的包含关系,集合的基本运算题,有关集合运算性质的分析题,集合相等或者包含的证明题,有穷集合的计数问题,典型例题一,判断下列命题是否为真,(1)x,x,(2)x x,(3)x x,x,(4)x x,x,(5)x x,x,(6)x xx,(7),若,xA,，,AP(B),，,则,xP(B),答案,(1),真,(2),假,(3),真,(4),真,(5),真,(6),真,(7),假,典型例题一的分析,判断元素,a,与集合,A,的隶属关系是否成立的基本方法：把,a,作为一个整体，检查它在,A,中是否出现，注意这里的,a,可能是集合表达式。,判断集合包含,A,B,一般可以使用以下四种方法：,若,A,、,B,是用枚举方式定义的，依次检查,A,的每个元素是否在,B,中出现。,若,A,、,B,是用谓词法定义的，且,A,、,B,中元素性质分别为,P,和,Q,，,那么“如果,P,则,Q”,意味着,AB,，“,P,当且仅当,Q”,意味着,A,B,。,通过集合运算判断,AB,，即,AB,B,，,AB,A,，,A,B,3,个等式中有一个为真，则,AB,。,可以通过文氏图判断集合的包含（不是证明）,。,判断以下命题的真假,(1)A(B,C),(AB),(AC),(2)(A,B)(B,A),(3)A,(BC),(A,B)C,(4),(A,B),(B,A),(5),(AB)A,(6)(AB)(B,A)A,(7)AB,A B,答案,(1),真,(2),真,(3),假,(4),假,(5),假,(6),假,(7),假,