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

《离散数学第六章 集合 集合的基本运算ppt课件.ppt》由会员分享，可在线阅读，更多相关《离散数学第六章 集合 集合的基本运算ppt课件.ppt（20页珍藏版）》请在三一办公上搜索。

1、第六章 集合,6.1 集合的基本概念6.2 集合的基本运算6.3 全集和集合的补 6.4 自然数与自然数集6.5 包含与排斥原理,并运算：AB,定义：设A和B是两个集合,则, 存在一个集合，它的元素是所有的或者属于集合A，或者属于集合B的元素组成，称这个集合为集合A与集合B的并集。记为AB ，即 AB=x xA或xB,交运算、差运算,存在一个集合，它的元素是所有的既属于集合A，又属于集合B的元素组成，称这个集合为集合A与集合B的交集。记为AB ，即 AB=x xA且xB,交运算、差运算,存在一个集合，它的元素是所有的属于集合A，但不属于集合B的元素组成，称这个集合为集合A与集合B的差。记为AB

2、 ，即 AB=x xA且xB,集合运算性质,定理：设A、B、C是三个任意集合，则：,幂等律 AA=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 A

3、C 由x AB 得xA 或xB； （1）由x AC 得xA 或xC 。 （2）于是，当xA，有x A(BC)；当xA，由(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的对称差，记为AB，即： AB=xxA且xB,或xB且xA,由定义，不难知：AB = (AB)(BA)AA = A = A,命题 (p65) AB = (AB)(AB),证明：对于任何一个x,若xAB，则xAB或xBA

4、。 若xAB，则有xA且xB ， 从而有x AB且x AB ，所以x (AB)(AB) ；若xBA，则有xB且xA ，从而有x AB且x AB ，所以x (AB)(AB) ；因此, AB (AB)(AB) 对于任何一个x，若x (AB)(AB) ，则有x AB且x AB。若xA,又x AB, 所以xB,从而有xAB,故xAB； 若xB,又x AB, 所以xA,从而有xBA,故x AB； 因此， (AB)(AB) AB综上所得， AB = (AB)(AB) 。,例：（A B） C = A （B C）,例1 (p66) (A-B)(A-C)=A在何条件下成立？,解： 根据分析当且仅当 A(BC)=

5、时,等式成立。 首先，假若(A-B)(A-C)=A, 要证明A(BC)=。 用反证法。 若ABC, 则xABC, 所以 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)

6、； 若xB, 则xAB，由于A(BC)=, 则 xC, 即有xA-C, 进而x(A-B)(A-C)； 所以有A(A-B)(A-C) 。综合得到 (A-B)(A-C)=A成立。,例2 (p66) 已知AB=AC，证明B=C。,证明：因为 AB=AC 所以 A(AB)= A(AC ) 从而有 （AA）B =（ AA）C 即 B=C 故 B=C,有限并、有限交,设Pi (1ik)是k个任意集合,把P1P2Pk简记为,把P1P2Pk简记为,推论 (p67),设A, Pi (1ik)是k+1个集合, 则,（分配率对有限并、有限交都成立。）,可数并、可数交,设Pi (iN)是任意集合,性质：设A,Pi (

7、iN)是任意集合,广义并、广义交,设H是一个集合，我们称它为下标集，对于H中的每一个元素g， Ag表示一个集合。,广义并、广义交,设D是一个集合簇，也可以认为是一个以集合为元素的集合。我们要求D不是空集合。我们令：,在 D=AggH的情形下 , 有,例3 (p67),设 Sa=x0 xa ，其中a是一个正实数。,令 R+ =xR x0记则,幂集,定义3： A是一个集合，存在一个集合，它是由A的所有子集为元素构成的集合， 称它为集合A的幂集合， 记为(A) ，也记为2A 。,例 设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 包含与排斥原理,