离散数学第六章-集合-集合的基本运算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 x A或或x BAB交运算、差运算交运算、差运算存在一个集合，它的元素是所有的既属于集存在一

2、个集合，它的元素是所有的既属于集合合A，又属于集合，又属于集合B的元素组成，称这个集合的元素组成，称这个集合为集合为集合A与集合与集合B的交集。记为的交集。记为AB ，即，即 AB=x x A且且x BAB交运算、差运算交运算、差运算存在一个集合，它的元素是所有的属于集合存在一个集合，它的元素是所有的属于集合A，但不属于集合，但不属于集合B的元素组成，称这个集合的元素组成，称这个集合为集合为集合A与集合与集合B的差。记为的差。记为AB ，即，即 AB=x x A且且x BAB集合运算性质 定理：设定理：设A、B、C是三个任意集合，则：是三个任意集合，则： 幂等律幂等律 AA=A AA=A 交换

3、律交换律 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，或，或x BC 。当当x A，则，则x AB 且且x AC，所以，所以 x (AB)(AC) ；当当x BC，则，则x B 且且x C，就有，就有x AB, 且且x AC，所以所以 x (AB)(AC) 。 故故 A(BC)(AB)(AC) 反过来，若反过来，若x (AB)(AC)，则，则 x AB, 且且x AC 由由x A

4、B 得得x A 或或x B； （1）由由x AC 得得x A 或或x C 。 （2）于是，当于是，当x A，有，有x A(BC)；当当xA，由，由(1)和和(2)， x B 且且x C，有，有x BC ，所以，所以x A(BC)。故故 (AB)(AC) A(BC)综上知，综上知， A（BC）=（AB）（AC）。）。对称差 定义定义2：A,B是两个集合，存在一个集合，它的是两个集合，存在一个集合，它的元素是所有的或者属于元素是所有的或者属于A不属于不属于B，或者属，或者属于于B不属于不属于A，称它为集合，称它为集合A和集合和集合B的对的对称差，记为称差，记为A B，即：，即： A B=xx A且

5、x B,或x B且x AAB由定义，不难知：由定义，不难知：A B = (AB)(BA)A A = A = A命题 (p65) A B = (AB)(AB) 证明：对于任何一个证明：对于任何一个x,若若xA B，则，则xAB或或x BA。 若若x AB，则有，则有x A且且xB ， 从而有从而有x AB且且x AB ，所以，所以x (AB)(AB) ；若若x BA，则有，则有x B且且x A ，从而有从而有x AB且且x AB ，所以，所以x (AB)(AB) ；因此因此, A B (AB)(AB) 对于任何一个对于任何一个x，若，若x (AB)(AB) ，则有则有x AB且且x AB。若若x

6、 A,又又x AB, 所以所以x B,从而有从而有x AB,故故x A B； 若若x B,又又x AB, 所以所以x A,从而有从而有x BA,故故x A B； 因此，因此， (AB)(AB) A B综上所得，综上所得， A B = (AB)(AB) 。例：（A B） C = A （B C） 设设 x （A B） C, 于是有于是有（1） x A B，且，且x C，即，即有有 x A且且x B 且且x C, 或或x B且且x A 且且x C；或（或（2）x C 且且x A B , 即即有有 x C且且x A 且且x B， 或或x C且且x A 且且x B。设设 x A （B C）, 于是有于是

7、有（1）x A ，且，且x B C，即，即有有 x A且且x B 且且x C， 或或x A且且x B 且且x C；或（或（2）x B C 且且x A , 即即有有 x B且且x C 且且x A， 或或x C且且x B 且且x A。由上不难看出：由上不难看出：（A B） C = A （B C） ABC例1 (p66) (A-B)(A-C)=A在何条件下成立？在何条件下成立？ 解：解： 根据分析当且仅当根据分析当且仅当 A(BC)=时时,等式成立。等式成立。 首先，假若首先，假若(A-B)(A-C)=A, 要证明要证明A(BC)=。 用反证法。用反证法。 若若ABC, 则则xABC, 所以所以 x

8、 A， x B ， x C 。 由由x A，x B, 有有 x A-B, 又由又由x A，x C, 有有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), 则有则有x A-B或或x A-C, 即有即有x A且且x B,或或x A且且x C,于是有于是有x A, 所以所以 (A-B)(A-C)A。对于任意的对于任意的x A, 若若x B，则

9、有，则有x A-B, 进而进而x (A-B)(A-C)； 若若x B, 则则x AB，由于，由于A(BC)=, 则则 x C, 即有即有x A-C, 进而进而x (A-B)(A-C)； 所以有所以有A(A-B)(A-C) 。综合得到综合得到 (A-B)(A-C)=A成立。成立。例2 (p66) 已知已知A B=A C，证明，证明B=C。 证明：因为证明：因为 A B=A C 所以所以 A (A B)= A (A C ) 从而有从而有 （A A） B =（ A A） C 即即 B= C 故故 B=C有限并、有限交设Pi (1ik)是k个任意集合,ikiP111iikiPxkiixP，存在一个ik

10、iP111iikiPxkiixP，对于所有的u 把把P P1 1P2Pk简记简记为为u 把把P P1 1P2Pk简记为简记为推论 (p67)设A, Pi (1ik)是k+1个集合, 则)(11ikiikiPAPA)(11ikiikiPAPA（分配率对有限并、有限交都成立。）（分配率对有限并、有限交都成立。）可数并、可数交设设Pi (iN)是任意集合是任意集合, 1,1iiiPxiNiixP，存在一个1,1iiiPxiNiixP，对于所有的)(11iiiiPAPA)(11iiiiPAPA性质：性质：设设A,Pi (i N)是任意集合是任意集合, 广义并、广义交 ggHgAxHgxA，存在一个gg

11、HgAxHgxA，对于所有的设设H是一个集合，我们称它为下标集，对于是一个集合，我们称它为下标集，对于H中的每一个中的每一个元素元素g， Ag表示一个集合。表示一个集合。广义并、广义交 设设D是一个集合簇，也可以认为是一个以集合为元素的集是一个集合簇，也可以认为是一个以集合为元素的集合。我们要求合。我们要求D不是空集合。我们令：不是空集合。我们令：SxDSxSDs，存在一个SxDSxSDs，对于所有的在在 D=Agg H的情形下 , 有有gHgDsAS gHgDsAS 例3 (p67)设设 Sa=x0 x0记记则则RaSDa0 xRxSSaRaDs0aRaDsSS幂集 定义定义3： A是一个集合，存在一个集合，它是由是一个集合，存在一个集合，它是由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 包含与排斥原理包含与排斥原理