离散数学集合.ppt

集合的基本概念和运算,第三章,3.1 集合的基本概念,一、集合：,一些,可确定的可分辨,的事物构成的整体。用大写字母,A,B,C,标记。,如：(1)26个英文字母的集合；,(,2)坐标平面上所有点的集合。,规定：(,i),元素之间彼此相异；,(,ii),没有次序关系。,组成一个集合的每一个特定的事物，叫做集合的元素，用小写字母,a,b,c,标记。,常用集合记号：,N,：,自然数集(包括0)；,Z,：,代表整数集；,Q,：,有理数集；,R,：,实数集；,C,：,复数集；,：空集(不含任何元素)；,U,：,全集,二、常用集合,三、集合的表示方法：,(1),列举法,：,A,=,a,b,c,d,可以看出,a,A,，,但,e,A,(2),描述法：,用谓词概括该集合中元素的属性，,即：,A,=,x,|,P,(,x,),如：,A,=,x,|,x,Z,3,x,6,两个集合间的关系,(1),子集：,如果,B,中每个元素都是,A,中元素，则,B,A,。,(2),相等集：,如果,A,B,且,B,A,，,则,A,=,B,。,符号化：,B,A,(,x,)(,x,B,x,A,)，,显然：(,i),S,S,，(ii),对任意集合,A,，,A,。,符号化：,A,=,B,A,B,B,A,四、集合之间的关系,(3),真子集：,如果,B,A,且,B,A,，,则,B,A。,(4),幂 集：,集合,A,的全体子集构成的集合，记作,P,(,A,)。,符号化：,P,(,A,)=,B,|,B,A,，,n,元集,A,的幂集,P(,A,),中含2,n,个元素。,例,3.1,计算以下幂集,(1),P,(,),(2),P,(,),(3),P,(1,2,3),解：,(1),P,(,)=,(,为什么不是?),(2),P,(,)=,(3),P,(1,2,3)=,方法：先写,子集；再写含一个元素的子集；再写含二个元素的子集；,1,2,3,1,2,3,3.2 集合的基本运算,并：,A,B,=,x,|,x,A,x,B,交：,A,B,=,x,|,x,A,x,B,，,若,A,B,=，,则称,A,与,B,不交,相对补：,A,B,=,x,|,x,A,x,B,绝对补：,A,对全集,U,的相对补集，记作：,A,或,对称差：,A,B,=(,A,B,),(,B,A,)=(,A,B,)(,A,B,),一、几种常见的运算,集合运算的直观表示,：文氏图,画法,：(1)用大矩形表示全集,U；,(,2)用一些圆圈(矩形内)表示不同的集合及其关系；,(3)用阴影线表示运算结果。,二、文氏图,如：,A,B,A,B,A,B,A,B,三、集合算律：,(,1),幂等律,A,A,=,A,A,A,=,A,(,2),结合律,(,A,B,),C,=,A,(,B,C,),(,3),交换律,A,B,=,B,A,A,B,=,B,A,(,4),分配律,A,(,B,C,)=(,A,B,),(,A,C,),(,A,B,),C,=,A,(,B,C,),A,(,B,C,)=(,A,B,)(,A,C,),(,9),吸收律,A,(,A,B,)=,A,(,7),排中律,A,=,U,(,8),矛盾律,A,=,A,(,A,B,)=,A,(,5),同一律,A,=,A,A,U,=,A,(,6),零 律,A,U,=,U,A,=,(,10),德.摩根律,A,(,B,C,)=(,A,B,),(,A,C,),A,(,B,C,)=(,A,B,),(A,C),(,11),互补律,A,=U,(,排中律,),=,U,(,德 摩根律,),=,(,德 摩根律,),(,12),双重否定律,A,=,(,矛盾律,),常用运算性质,(,1),A,B,A,A,B,B,(,2),A,A,B,B,A,B,(,3),A,B,A,(,5),A,B,=,B,A,B,A,B,=,A,A,B,=,(,证明包含关系的各种方法),(,4),(,补变交),(,7)(,A,B,),C,=,A,(,B,C,),(,8),A,=,A,(,9),A,A,=,(,6),A,B,=,B,A,(,10),A,B,=,A,C,B,=,C,(,消去律,),例,3.2,化简(,A,B,C,),(,A,B,),(,A,(,B,C,),A,),解题思想：,解：,因为,A,B,A,B,C,A,A,(,B,C,),所以(,A,B,C,),(,A,B,)=,A,B,(,A,(,B,C,),A,=,A,所以原式是：(,A,B),A,=,B,A,利用算律和运算性质,四、应用,3.3 集合中元素的计数,容斥原理：,对任意两个有限集,A,和,B,，,有,|,A,B,|=|,A,|+|,B,|,|,A,B,|,|,|：,集合的基数(元素个数),一、集合计数的基本原理,证明：,A,B,=,B,(,A,B,),且,B,(,A,B,)=,又,A,=(,A,B,),(,A,B,),且,(,A,B,),(,A,B,)=,从而|,A,B,|=|,B,|+|,A,B,|,|,A,|=|,A,B,|+|,A,B,|,即|,A,B,|=|,B,|+|,A,|,|,A,B,|,|,A,B,C,|,|,A,|,|,B,|,|,C,|,|,A,B,|,|,A,C,|,|,B,C,|,|,A,B,C,|,推 广,例,3.,3,某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球，而6个会打网球的人都会打另外一种球(指篮球和排球)，求不会打这三种球的人数？,二、实例,=|,A,|+|,B,|+|,C,|,|,A,B,|,|,A,C,|,|,B,C,|+,|,A,B,C,|,先求：,=12+6+146 5+2|,A,B,|=23,|,A,B,|,解：,用,A,、,B,、,C,分别表示会打排球、网球、篮球的学生集合，则有：,|,A,|=12，,|,A,C,|=6，,|,B,|=6，,|,U,|=25,|,C,|=14，,|,B,C,|=5，,|,A,B,C,|=2,|,A,B,C,|,又因为6个会打网球的人都会打另外一种球，,=6,(5 2)=3,例,3.4,一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试中有21人得5分。如果两次考试中都没得5分的有17人，那么在两次考试都得5分的有多少人？,解：,设,A,、,B,、,分别表示第一和第二次考试中得5分学生的集合，那么有,又因为|,A,B,|=|,A,|+|,B,|,|,A,B,|,所以|,A,B,|=|,A,|+|,B,|,|,A,B,|,=26+21,33=14,知,=33,小结与学习要求,熟练掌握空集，子集，幂集，并，交，补，差等概念，善于应用各种运算的性质，要特别掌握好容斥原理在集合计数中的应用。,