计算机中的集合运算.ppt

,肥东圣泉中学初中部,信息组,计算机中的集合,计算机中的集合,第一节 集合的基本概念,1.1,个体与集合之间的关系,1.2,集合的表示法,1.3,集合与集合之间的关系,1.4,幂集,第二节 集合的基本运算,2.1,集合的补运算,2.2,集合的交运算和并运算,2.3,集合的宏运算,1.1,个体与集合之间的关系,什么是集合，关于集合的各种不同说法如下。,1.,莫斯科大学的那汤松教授说：,凡具有,某种特殊性质,的,对象,的,汇集,称之为集。,2.,复旦大学的陈建功教授说：,凡可供吾人思维的，不论它有形或无形，都叫做,物,。具有,某种条件,的物，称它们的,全部,谓之一集。,3.,南开大学的杨宗磐教授说：,集就是“,乌合,之,众,”。不考虑怎样“,乌合,”起来的，众,可以具体,，,可以抽象,。,4.,集合论之父,G.Cantor,（,1845-1918,）,说：,集是由,总括,某些,个体,成一个整体而成的。对于每个个体，只设其为,可思考对象，辨别它的异同,。个体之间并不需要有任何关系。,综上所述集合的概念有三要素,1.,个体（元素）,2.,个体的可辨认性,3.,集合（动词）,通常用小写拉丁字母表示集合中的个体：,a,、,b,、,c,、,d,通常用大写拉丁字母表示集合的名称：,A,、,B,、,C,、,D,个体与集合之间的关系称为属于关系。,对于某个个体,a,和某个集合,A,而言，,a,只有两种可能,1,）,a,属于,A,，,记为,a,A,，称,a,是,A,中的元素。,2,）,a,不属于,A,，,记为,a,A,，称,a,不是,A,中的元素。,判断个体,a,属于,A,还是不属于,A,，,必须使用个体的可辨认性，而且个体的可辨认性是无二义性的，即或者,a,属于,A,或者,a,不属于,A,，,二者居其一且只居其一。,关于个体的辨认有赖于各方面的公认的知识。,集合,（名词）,1.2,集合的表示法,文字表示法,用文字表示集合的元素，两端加上花括号。,在座的同学,高等数学中的积分公式,元素列举法,将集合中的元素逐一列出，两端加上花括号。,1,，,2,，,3,，,4,，,5,风，马，牛,2,，,4,，,6,，,8,，,10,，,谓词表示法,xp(x)p,表示,x,所满足的性质。,xx,2,=1,yy,是开区间,(a,b),上的连续函数,使,x,2,=1,的实数,1,，,-1 xx,2,=1,集合的特殊情况,不含任何元素的集合称为空集，记为,或,。,只含一个元素的集合称为单元素集，记为,a,。,含讨论问题所需全部元素的集合称为全集，记为,X,。,常用集合的字母表示：,自然数集、整数集、有理数集、实数集、复数集,分别用大写字母,N,、,Z,、,Q,、,R,、,C,表示,有时还用,Q,表示正有理数集，用,R,表示负实数集，等等,1.3,集合与集合之间的关系,定义,1,设,A,，,B,是两个集合,1,）若对于,A,中的每个元素,x,，,都有,x,属于,B,，,则称,A,包含,在,B,中，记,为,AB,。,同时称,A,是,B,的子集。,2,）若,A,中的每个元素都属于,B,，且,B,中的每个元素都属于,A,，,则称,A,等于,B,，,记为,A=B,。,子集的两种特殊情况（平凡子集）：,1,）空集是任一集合的子集。,2,）每个集合是它自己的子集。,集合与集合之间的关系称为包含关系。,真子集：,对于两个集合,A,与,B,，如果,A B,，并且,A B,，,就说集合,A,是集合,B,的真子集，记作,A B,（或,B A,）,空集是任何非空集合的真子集,全集,：,如果集体,S,含有所要研究各个集合的全部元素，,这个集合就可以看作一个,全集,，全集通常用表示,I,表示,补集：,一般地，设,S,中一个集合，,A,是,S,的一个子集（即,A S,），,由,S,中所有,不属于,A,的元素组成的集合，叫做,S,中子集,A,的补集（或余集），,记作,A,即,A,xx,S,，,且,x A,1.4,幂集,定义,2,设,A,是集合，,A,的所有子集组成的集合称为,A,的幂集，记为,2,A,。,2,A,=x,x A,定理,1,设集合,A,是有限集合，,A,=n,，,则,2,A,=2,A,。,定理,2,设,A,B,是两个集合。那么,A=B,当且仅当,2,A,=2,B,。,第二节 集合的基本运算,2.1,集合的补运算（一元运算）,定义,1,设,X,是集合，,A,是,X,的,子集。,A,=x xX xA,称,A,是,A,关于,X,的补集，称,为补,运算。,定理,1,设,X,是集合，,A,，,B,是,X,的子集。则,1,）,(A,)=A,；,2,）若,A,B,，则,B,A,；,3,）若,A=,B,，则,A,=,B,；,4,）,X,=,，,=X,。,2.2,集合的交运算和并运算,定义,2,设,A,，,B,是两个集合,1,）,A,B=xxAxB,，,称,A,B,为,A,与,B,的交集，称,为,集合交运算。,2,）,A,B=xxAxB,，,称,A,B,为,A,与,B,的并集，称,为集合并运算。,定理,2,设,X,是全集，,A,，,B,，,C,是,X,的三个子集合，则,1,）,A,A=A,，,AA=A,2,）,A,A=,，,AA=X,3,）,A,X=A,，,AX=X,4,）,A,=,，,A=A,5,）,A,B=BA,，,AB=BA,6,）,(,A,B)C=A(BC),(,A,B)C=A(BC),7,）,A,(B C)=(AB)(AC),A,(B C)=(AB)(AC),定理,3,设,A,，,B,，,C,为三个集合，则,1,）,A,AB,，,A,B,A,；,2,）,若,A,C,且,B,C,，,则,AB,C,；,3,）,若,C,A,且,C,B,，,则,C,A,B,。,定理,4,设,A,，,B,为两个集合，则下面三式等价。,1,）,A,B 2,）,AB=B 3),A,B=A,定理,5,设,A,，,B,为两个集合，则,1,）,(,AB)=,A,B,2,）,(,A,B)=AB,2.3,集合的宏运算,定义,3,设,A,B,是两个集合，,AB=,xxAxB,，,称,AB,为,A,和,B,的差集，称,为集合差运算。,由差运算、交运算、补运算的定义知,AB=,A,B,。,由于差运算可以由并、交、补运算线性表出，因此称差运算为宏运算。,定理,6,设,X,是全集，,A,B,C,是,X,的三个子集合，则,1)AB,A,；,2)AA=,；,3)XA=A,；,AX=,；,4)A,=A,；,A=,；,5)A,(BC)=(,A,B)(,A,C),；,6)A(BC)=(AB),(A,C),7),(AB)C=A(B,C),；,8)A(B,C),=(AB),(AC),；,9)A(B,C),=(AB),(AC),。,例：如图，,I,为全集，集合,M,，,N,满足：,M N,，那么图中红色阴影部分用集合表示，可表示为：,例：如果集合,M,满足,M 7,，,13,，,20,，,且,M,中至多含有一个奇数，,那么符合上述条件的集合,M,共有,_,个,6,个,分析：集合,M,满足两个条件：,是集合,7,，,13,，,20,的真子集；,其中至多含有一个奇数，即,M,的元素中或者没有奇数,或者仅有一个奇数还要注意空集 是符合条件的,由上得,M,可能是 ，,20,，,7,，,13,，,7,，,20,，,13,，,20,再见,