离散数学课件：3-2 集合的基本概念与运算

1、只有一、二年级的学生才爱好体育运动只有一、二年级的学生才爱好体育运动A: 一年级大学生的集合一年级大学生的集合 B：二年级大学生的集合：二年级大学生的集合C：计算机学院学生的集合：计算机学院学生的集合 D：数学学院学生的集合：数学学院学生的集合E：选修离散数学的学生集合：选修离散数学的学生集合F：爱好文学学生的集合：爱好文学学生的集合 G：爱好体育运动学生的集合：爱好体育运动学生的集合E (D C ) B C B E(D A) E =D F G G A B 除去除去数学学院和计算机学院二数学学院和计算机学院二年级学生外年级学生外都都不选修不选修离散数学离散数学写出下列句子对应集合表达式 所有所

2、有计算机学院二计算机学院二年级学生都选修离散数学年级学生都选修离散数学数学学院一数学学院一年级的学生都没有选修离散数学年级的学生都没有选修离散数学数学学院学生数学学院学生或爱好文学或爱好体育运动或爱好文学或爱好体育运动第3章 集合的基本概念和运算3.1 集合的基本概念3.2 集合的基本运算3.3 集合中元素的计数3.2 集合的基本运算n集合的基本运算n并并 A B = x | x A x B n交交 A B = x | x A x B n相对补相对补 A B = x | x A x B n绝对补绝对补 A = E A = x | x A （A的绝对补集是的绝对补集是 A 对对 E 的相对补集）

3、的相对补集）n对称差对称差 A B文氏图表示文氏图表示集合的并和交运算的性质n满足交换律nA B= B A A B = B An满足幂等律nA A = A A A = An满足对的分配律、 对的分配律nA (B C) = (A B) (A C)nA (B C) = (A B) (A C)nA =A A = 对于n个集合A1，A2.An的并集和交集为: 121niniAAAA |()()ixi xAn个集合的并和交12 |nx xAxAxA 121niniAAAA12 |nx xAxAxA |()()ixi xAn设A,B为集合，B对A的相对补集AB定义为：n重要结论： 集合相对补与绝对补的关系

4、将相对补集与绝对补集联系在一起 n设A，B为集合，则A与B的对称差是集合的对称差运算 A B = (A-B) ( B-A)= (A B) (B A) 其文氏图如下：其文氏图如下： A B =(A B) (A B)集合对称差运算的性质n满足交换律满足交换律nA B = B An满足结合律满足结合律n(A B) C = A (B C )nA = A A A = nA B = A C B = C 交换交换A B=B AA B=B AA B=B A结合结合(A B) C=A (B C)(A B) C=A (B C)(A B) C=A (B C)幂等幂等A A=AA A=A 与与 与与 分配分配 A (

5、B C)=(A B) (A C)A (B C)=(A B) (A C)A (B C)=(A B) (A C)吸收吸收A (A B)=AA (A B)=A集合运算的算律吸收律的前提：吸收律的前提： 、 可交换可交换集合运算的算律（续） D.M 律律A (B C)=(A B) (A C)A (B C)=(A B) (A C) (B C)= BC (B C)= BC双重否定双重否定A=AE补元律补元律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定否定=E E=例题n例例3.5 证明证明 : (A-B) B=A B证证: (A-B) B = (A B) B = (A B) (B

6、B) = A BAB=A B例3.4 证明式3.17n证明：证明：A(B C)(A B) ( AC)n证证: 对对 x， x (A(B C) = x A x (B C) = x A (x B x C) = x A ( x B x C) = x A (x B x C) = (x A x B) (x A x C) = x (AB) x (AC) = x (AB) (AC) 所以所以 A(B C)(AB) (AC)A-B=x|x A x B集合包含的证明方法n证明证明 X Yn命题演算法命题演算法n包含传递法包含传递法n等价条件法等价条件法n反证法反证法n并交运算法并交运算法以上的以上的 X, Y

7、代表集合公式代表集合公式任取任取 x ， x X x Y命题演算法证 X Yn证证: (1) A B P(A) P(B) 任取任取x, x P(A) x A x B x P(B) (2) P(A) P(B) A B 任取任取x x A x A x P(A) x P(B) x B x B 例例1 证明证明 A B P(A) P(B)X Yx (x Xx Y)包含传递法证 X Y找到集合找到集合T 满足满足 X T 且且 T Y，从而有，从而有X Y例例2 A B A B证证 因为因为 A B A 而而 A A B 所以所以 A B A B 利用包含的等价条件证 X Y A-BABABBABA (

8、1) 证证 (A B) C=C A C A C =C B C B C =C (A B) C = A (B C) = A C =C(A B) C=C A B C (2) 证证 (A B) C= A B A C A C = A B C B C = B (A B) C = (A C) (B C) = A B(A B) C=A BA B C例例3 A C B C A B C 反证法证 X Y欲证欲证X Y, 假设命题不成立，必存在假设命题不成立，必存在 x 使得使得 x X 且且 x Y. 然后推出矛盾然后推出矛盾. 例例4 证明证明 A C B C A B C证证: 假设假设 A B C 不成立，则

9、不成立，则 A B C x (x A B x C) x (x A x B) x C) x (x A x C) (x B x C) x ( x A x C) x (x B x C) A C B C （与前提矛盾）（与前提矛盾）Q P P Q A B x(x A x B)利用已知包含式并交运算证 X Y例例5 证明证明 A C B C A C B C A B证证: 上述两条件分别两边上述两条件分别两边求并，得求并，得 (A C) (A C) (B C) (B C) (A C) (A C) (B C) (B C) A (C C) B (C C) A E B E A B由已知包含式通过运算产生新的包含

10、式由已知包含式通过运算产生新的包含式 (X Y)(SW ) (X S) (Y W ) (X Y)(SW ) (X S) (Y W )集合相等的证明方法n证明证明 X=Yn命题演算法命题演算法n等式替换法等式替换法n反证法反证法n运算法运算法以上的以上的 X, Y 代表集合公式代表集合公式 例例6 证明证明 A (A B)=A （吸收律）（吸收律） 证证 任取任取x, x A (A B) x A x (A B) x A (x A x B) x A 命题演算法证明X=Y任取任取 x ， x X x Y x Y x X 或者或者 x X x Y X (X Y)XX Y Y XA=B x(x Ax B

11、)等式替换证明X=Y例例7 证明证明A (A B)=A （吸收律）（吸收律）证证 ( (假设假设分配律、同一律、零律分配律、同一律、零律成立成立) ) A (A B) =(A E) (A B) 同一律同一律 =A (E B) 分配律分配律 =A E 零律零律 =A 同一律同一律不断进行代入化简，最终得到两边相等不断进行代入化简，最终得到两边相等反证法证明X=Y例例8 证明证明 A B A B =证证: 假设假设 A B ，即，即 x (x A x B) x ( x A x B) x (x A x B) A B 与条件与条件 A B 矛盾矛盾. 所以所以， 结论正确。结论正确。假设假设 X=Y

12、不成立，则存在不成立，则存在 x 使得使得 x X且且x Y，或者或者存在存在 x 使得使得 x Y且且x X，然后推出矛盾，然后推出矛盾. A Bx(x A x B)集合运算法证明X=Y例例9 证明证明 A C=B C A C=B C A=B证证: 由第二个条件减第一个条件由第二个条件减第一个条件得得 (A C)-(A C)=(B C)-(B C) 从而有从而有 A C=B C (A C) C =(B C) C A (C C) =B (C C) A = B A=B由已知等式通过运算产生新的等式由已知等式通过运算产生新的等式 (X=Y)(Z=W) X Z=Y W, X Z=Y W, X-Z=Y-W例题n例例3.6 化简化简 : (A B C) (A B) (A (BC ) A)证证: 因为：因为： (A B C) (A B) = (A B) (A (BC ) A = A 所以，原式所以，原式= (A B) A = (A B) A = B A = B A 例：对于任意集合A、B和C，给出 (A-B) (A-C)=