离散数学第六章 集合-集合的基本运算.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第六章 集合,6.1,集合的基本概念,6.2,集合的基本运算,6.3,全集和集合的补,6.4,自然数与自然数集,6.5,包含与排斥原理,并运算：,AB,定义：设,A,和,B,是两个集合,则,存在一个集合，它的元素是所有的或者属于集合,A,，或者属于集合,B,的元素组成，称这个集合为集合,A,与集合,B,的并集。记为,A,B,，即,AB=,x,x,A,或,xB,AB,交运算、差运算,存在一个集合，它的元素是所有的既属于集合,A,，又属于集合,B,的元素组成，称这个集合为集合,A,与集合,B,的交集。记为,AB,，即,AB=x,xA,且,xB,AB,交运算、差运算,存在一个集合，它的元素是所有的属于集合,A,，但不属于集合,B,的元素组成，称这个集合为集合,A,与集合,B,的差。记为,AB,，即,AB=x,xA,且,xB,AB,集合运算性质,定理：设,A,、,B,、,C,是三个任意集合，则：,幂等律,A,A=A,AA=A,交换律,AB=BA,AB=BA,结合律,A,（,BC,）,=,（,AB,）,C,A,（,BC,）,=,（,AB,）,C,分配律,A,（,BC,）,=,（,AB,）,（,AC,）,A,（,BC,）,=,（,AB,）,（,AC,）,证明：,A,（,BC,）,=,（,AB,）（,AC,）,对于任意的,x,，若,x A(BC),，则,x A,，或,xBC,。,当,x A,，则,x AB,且,x AC,，所以,x(AB)(AC),；,当,xBC,，则,xB,且,xC,，就有,x AB,且,x AC,，,所以,x(AB)(AC),。,故,A(BC),(AB)(AC),反过来，若,x(AB)(AC),，则,x AB,且,x AC,由,x AB,得,xA,或,xB,；（,1,）,由,x AC,得,xA,或,xC,。（,2,）,于是，当,xA,，有,x A(BC),；,当,x,A,，由,(1),和,(2),，,xB,且,xC,，有,xBC,，所以,x A(BC),。,故,(AB)(AC),A(BC),综上知，,A,（,BC,）,=,（,AB,）,（,AC,）。,对称差,定义,2,：,A,B,是两个集合，存在一个集合，它的元素是所有的或者属于,A,不属于,B,，或者属于,B,不属于,A,，称它为集合,A,和集合,B,的对称差，记为,A,B,，即：,A,B=,x,xA,且,xB,或,xB,且,xA,A,B,由定义，不难知：,AB=(A,B),(BA),AA=,A=A,命题,(p65),AB=(AB)(A,B),证明：对于任何一个,x,若,x,AB,，则,x,A,B,或,xB,A,。,若,xA,B,，则有,xA,且,x,B,，,从而有,x AB,且,x AB,，所以,x(AB)(AB),；,若,xB,A,，则有,xB,且,xA,，,从而有,x AB,且,x AB,，所以,x(AB)(AB),；因此,AB,(AB)(AB),对于任何一个,x,，若,x(AB)(AB),，,则有,x AB,且,x AB,。,若,xA,又,x AB,所以,xB,从而有,xA,B,故,xAB,；,若,xB,又,x AB,所以,xA,从而有,xB,A,故,x AB,；,因此，,(AB)(AB)AB,综上所得，,AB=(AB)(AB),。,例：,（,A,B,）,C=A,（,B C,）,设,x,（,A B,）,C,于是有,（,1,）,x A B,，且,xC,，即有,xA,且,xB,且,xC,或,xB,且,xA,且,xC,；,或（,2,）,xC,且,x A B,即有,xC,且,x A,且,x B,，,或,xC,且,xA,且,xB,。,设,x A,（,B C,）,于是有,（,1,）,x A,，且,x B C,，即有,x A,且,xB,且,xC,，,或,xA,且,x B,且,x C,；,或（,2,）,x B C,且,x A,即有,xB,且,x C,且,xA,，,或,xC,且,xB,且,xA,。,由上不难看出：,（,A B,）,C=A,（,B C,）,A,B,C,例,1,(p66),(A-B),(A-C)=A,在何条件下成立？,解：,根据分析当且仅当,A,(B,C)=,时,等式成立。,首先，假若,(A-B)(A-C)=A,要证明,A(BC)=,。,用反证法。,若,ABC,则,x,ABC,所以,xA,，,xB,，,xC,。,由,xA,，,xB,有,x A-B,又由,xA,，,xC,有,x A-C,所以有,x (A-B)(A-C)=A,。,矛盾说明,ABC=,。,分析：,A,的元素,a,既是,B,的元素、也是,C,的元素，则等式不成立。,再证，若,A(BC)=,则,(A-B)(A-C)=A,成立。,对于任意的,x,(A,-B)(A-C),则有,xA,-B,或,xA,-C,即有,x A,且,xB,或,xA,且,xC,于是有,xA,所以,(A-B)(A-C),A,。,对于任意的,xA,若,xB,，则有,xA,-B,进而,x(A,-B)(A-C),；,若,xB,则,xA,B,，由于,A(BC)=,则,xC,即有,xA,-C,进而,x(A,-B)(A-C),；,所以有,A,(A-B)(A-C),。,综合得到,(A-B)(A-C)=A,成立。,例,2,(p66),已知,A,B=AC,，证明,B=C,。,证明：因为,AB=AC,所以,A(AB)=A(AC),从而有,（,AA,）,B=,（,AA,）,C,即,B=,C,故,B=C,有限并、有限交,设,P,i,(1,ik),是,k,个任意集合,把,P,1,P,2,P,k,简记为,把,P,1,P,2,P,k,简记为,推论,(p67),设,A,P,i,(1,ik),是,k+1,个集合,则,（分配率对有限并、有限交都成立。）,可数并、可数交,设,P,i,(,i,N,),是任意集合,性质：,设,A,P,i,(,i,N,),是任意集合,广义并、广义交,设,H,是一个集合，我们称它为下标集，对于,H,中的每一个元素,g,，,A,g,表示一个集合。,广义并、广义交,设,D,是一个集合簇，也可以认为是一个以集合为元素的集合。我们要求,D,不是空集合。我们令：,在,D=,A,g,g,H,的情形下,有,例,3,(p67),设,S,a,=x,0,x0,记,则,幂集,定义,3,：,A,是一个集合，存在一个集合，它是由,A,的所有子集为元素构成的集合，,称它为集合,A,的幂集合，,记为,(A),，也记为,2,A,。,例,设,A=0,1,，则,(A)=,0,1,0,1,设,B=,a,b,c,，则,(B)=,a,b,c,a,b,a,c,b,c,a,b,c,第六章 集合,6.1,集合的基本概念,6.2,集合的基本运算,6.3,全集和集合的补,6.4,自然数与自然数集,6.5,包含与排斥原理,