《离散数学集合的基本运算.ppt》由会员分享，可在线阅读，更多相关《离散数学集合的基本运算.ppt（32页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、3.2集合的基本运算集合的基本运算集合的交、并、差、补、对称差集合的交、并、差、补、对称差集合相等的证明集合相等的证明并集并集union定义：设定义：设A，B是两个集合，所有属是两个集合，所有属于于A或属于或属于B的元素组成的集合，称为集合的元素组成的集合，称为集合A与与B的并集，记作的并集，记作A B;A A B=xB=x x x A A x x BB。ABE交集交集intersection定义：定义：A，B是两个集合，即属于是两个集合，即属于A，又属于又属于B，称为集合，称为集合A与与B的交集，记为的交集，记为A B。即。即A B=x x A x BEAB广义的并集广义的并集集集合合的的并
2、并(union)：集集合合A和和B的的并并A B定定义义为为：A B=x|x A或或者者x B，集集合合的的并并可可推推广广到到多多个个集集合合，设设A1,A2,An都都是是集集合，它们的并定义为：合，它们的并定义为：A1 A2 An=x|存在某个存在某个i，使得，使得x Ai广义的交集广义的交集集集合合的的交交(intersection)：集集合合A和和B的的并并A B定定义义为为：A B=x|x A而而且且x B，集集合合的的交交也也可可推推广广到到多多个个集集合合，设设A1,A2,An都都是是集集合合，它它们的交定义为：们的交定义为：A1A2An=x|对所有的对所有的i，都有，都有x A
3、i集合的交并例题集合的交并例题1例如：集合例如：集合A=x-2x2，x R，B=x 0 x4,x R求求AB，AB。解：解：AB=x-2x2或或0 x4,x R=x-2x4,x RAB=x-2x2且且0 x4,x R =x =x 0 x0 x2,x2,x R R 0 1234-1-2-3集合的交并例题集合的交并例题2设设A为奇数集合，为奇数集合，B为偶数集合，求为偶数集合，求AB和和AB。解：解：AB=x x是偶数或是偶数或x是奇数是奇数=Z AB=x AB=x x x既是偶数又是奇数既是偶数又是奇数=集合的交并例题集合的交并例题3设设A1=1，2，3，A2=2，1，3，A3=3，1，2，求求
4、A1A2，A1A3，A2A3。解：三个集合均有两个元素，其中一个元素是解：三个集合均有两个元素，其中一个元素是数。另一元素是两个数组成的集合，三个集合没数。另一元素是两个数组成的集合，三个集合没有相同元素，有相同元素，A1A2=A2A3=A3A1=不相交不相交如如AB=AB=称称A A，B B不相交。不相交。集合的差集合的差设设A，B是两集合，属于是两集合，属于A而不属于而不属于B的元的元素全体称为素全体称为A与与B的差集，记作的差集，记作A-B，即即A-B=xA-B=x x x AxAx BB。EAB补集补集(complement set)集合集合A的补集，记为的补集，记为A A，是那些不属
5、于集合，是那些不属于集合A的的元素所构成的集合，元素所构成的集合，即即A=x|x A。通常来说，是在存在一个全集通常来说，是在存在一个全集U的情况下讨论集的情况下讨论集合的补集。全集合的补集。全集U是所讨论的问题域中所有元素是所讨论的问题域中所有元素所构成的集合。所构成的集合。显然，显然，A=E-A。AE可知：可知：x Ax A xA求求证证A-B=AA-B=AB B 证明证明A-B=x|xA-B=x|x A-BA-B =x =x x x A Ax x BB =x =x x x A Ax xBB =A =AB B当当A A，B B不相交时，不相交时，A-B=AA-B=A，B-A=B B-A=B
6、 EAB对称差对称差定义：设定义：设A，B是两集合，集合（是两集合，集合（A-B）（B-A）称为集合）称为集合A，B的对称差，记作的对称差，记作A B。即即A B=x x A且且x B x B且且x A=x(x x AAx B)(x BBx A)A B=(A B)-(A B)EAB对称差举例对称差举例例例1、A=a,b,eB=a,c,d解：解：B-A=c,d A-B=b,eB-A=c,d A-B=b,e，A A B=c,d,b,eB=c,d,b,e例例2、A=x x-2,x R,E=x x2求求 A，A A。解：解：A=xx-2=x-2x2，x RA-A=AA A=(A-A)A=(A-A)(A
7、-A)=(A-A)=集合运算性质（运算律）集合运算性质（运算律）1、交换律交换律AB=BA，AB=BA2、结合律结合律（A AB B）C=AC=A（B BC C）（AB）C=A（BC）3、分配律分配律A（BC）=（AB）（AC）A（BC）=（AB）（AC)4、幂等律、幂等律AA=A，AA=A5、同一律、同一律A=A,AE=A9、德摩根律德摩根律（AB）=A B6、零一律、零一律A=，AE=E（AB）=A B7、补余律、补余律A A=，A A=E10、双重否定律、双重否定律（A）=A8、吸收律、吸收律A（AB）=A注：注：A-B=A BA（AB）=A集合相等的证明的方法集合相等的证明的方法一、利
8、用集合的定义证明；一、利用集合的定义证明；二、利用集合等式证明；（常用）二、利用集合等式证明；（常用）三、利用谓词公式证明；三、利用谓词公式证明；四、用集合成员表。（略）四、用集合成员表。（略）证明：证明：A A（B BC C）=（A AB B）（A AC C）(1)x A(B C),分两种情况分两种情况(a)如如x Ax A B且且x A Cx(A B)(A C)(b)如如x A,则则x B Cx B且且x Cx A B且且x A C x(A B)(A C)任何情况下均有任何情况下均有x(A B)(A C)A(B C)(A B)(A C)证明：证明：A A（B BC C）=（A AB B）（
9、A AC C）(续续)(2)x(A B)(A C)x A B且且x A C分两种情况分两种情况(a)若若x A,则则x A(B C)(b)若若x A，由由x A,x A Bx B,由由x A,x A Cx C x B Cx A(B C)任何情况均有任何情况均有x A(B C)(A B)(A C)A(B C)(1)(2)(1)(2)合并为合并为 A A（B B C C）=（A A B B）（A A C C）求证：求证：A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)证明：证明：x x(A-B)(A-C)(A-B)(A-C)，则则x x(A-B)(A-B)x x(A-C)(A-
10、C)（x x A)(xA)(x B)B)(x x A)(xA)(x C)C)（x x A)(xA)(x B)B)(x(x C)C)（x x A)A)(x x B)B)(x x C)C)（x x A)A)(x x B Bx x C)C)(x x A)A)(x x B BC)C)x x A-(BC)A-(BC)从而，从而，A-(BC)=(A-B)(A-C)A-(BC)=(A-B)(A-C)利用谓词公式证明求证：求证：A-A-(BC)=(A-B)(A-C)(BC)=(A-B)(A-C)证明：证明：(A-B)(A-C)(A-B)(A-C)x|xx|x(A-B)(A-C)(A-B)(A-C)=x|x =
11、x|x(A-B)(A-B)x x(A-C)(A-C)=x|=x|x x A(xA(x B)B)(x(x A)(xA)(x C)C)=x|(=x|(x x A)(xA)(x B)B)(x(x C)C)=x|(=x|(x x A)A)(x x B)B)(x x C)C)=x|=x|（x x A)A)(x x B Bxx C)C)=x|(=x|(x x A)A)(x x B BC)C)=x|=x|x x A-(BC)A-(BC)=(A-B)(A-C)=(A-B)(A-C)利用集合等式证明求证：A-(BC)=(A-B)(A-C)(A-B)(A-C)(A-B)(A-C)ABACABAC =ABC =AB
12、C =A(BC)=A(BC)=A-(BC)=A-(BC)证证明吸收律明吸收律A A（A A B B）=A=A证明：证明：A（A B）=（A）（A B）=A（B）=A =A =A已知已知A B=A C,A B=A C,求证求证B=C证明证明:B=B(A B)(吸收律吸收律)=B(A C)(等量代入等量代入)=(B A)(B C)(分配律分配律)=(A C)(B C)(等量代入等量代入)=(A B)C(分配律分配律)=(A C)C(等量代入等量代入)=C(吸收律吸收律)说明说明:A B=A CB=CA B=A CB=C 两种推理均是不成立的。两种推理均是不成立的。课堂练习用三种方法求证：用三种方法
13、求证：(B-A)(B-A)A=BAA=BA集合的化简集合的化简化化简简(A B C)(A B)-(A(B-C)A)证明证明:原集合原集合=(A B)-A(吸收律吸收律)=(A B)A=(AA)(BA)(分配律分配律)=(BA)(互补律互补律)=B =BA (A (同一律同一律)集合包含的性质 A A E E如果如果A A B B C C，则，则A A C CA A B B A A ABABA A B B AB=B AB=B A A B=A B=A B B AA集合包含的证明集合包含的证明方法：方法：一、包含的定义；一、包含的定义；x x A A，最后，最后x x B B；二、二、利用已知等式和
14、包含性质利用已知等式和包含性质A B B AB=B AB=B AB=A AB=A A-B=A-B=B A例题：证明：例题：证明：A A，B B是集合，是集合，A A B B P P（A A）P(BP(B）u P(A)u A,A Bu B,u P（B）从而从而P(A)P(B)x x A Axx A Axx P(A),P(A),P(A)P(A)P(B)P(B)xx P(B)P(B)x x B BAA B B。另外另外 A A P(A),P(A),P(A)P(A)P(B)P(B)AA P(B)P(B)AA B B。例题：证明：如果例题：证明：如果A A B B，那么，那么 B B A A证明：证明：
15、B A=(BA)=A从而从而 B A求证：如果A B，则P(A)P(B)证明：证明：(使用定义：使用定义：x x 左，最后左，最后x x 右右)x x P(A)P(A)，则，则x x A A，又由已知又由已知A A B B，所以，所以x x B B 从而从而x x P(B)P(B)。P(A)P(A)P(B)P(B)例题例题设设F表示一年级大学生的集合，表示一年级大学生的集合，S表示二年级大学生的集合，表示二年级大学生的集合，R表示计算机系学生的结合，表示计算机系学生的结合，M表示数学系学生的集合，表示数学系学生的集合，T表示选表示选修离散数学的学生的集合，修离散数学的学生的集合，L表示爱好文学
16、的学生的集合，表示爱好文学的学生的集合，P表示表示爱好体育的学生的集合。则下列句子所对应的集合表达式为：爱好体育的学生的集合。则下列句子所对应的集合表达式为：1）所有计算机系二年级的学）所有计算机系二年级的学生都选修离散数学。生都选修离散数学。RS T2）数学系的学生或者爱好文）数学系的学生或者爱好文学或者爱好体育运动。学或者爱好体育运动。M LP3）数学系一年级的学生都没）数学系一年级的学生都没有选修离散数学。有选修离散数学。4）只有一、二年级的学生才爱）只有一、二年级的学生才爱好体育运动。好体育运动。5）除去数学系和计算机系二年）除去数学系和计算机系二年级的学生外都不选离散数学。级的学生外都不选离散数学。只有数学系和计算机系二只有数学系和计算机系二年级的学生才选离散数学。年级的学生才选离散数学。T(MR)S