第二部分 集合论 第六章 集合代数 主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式

Presentation on theme: "第二部分 集合论 第六章 集合代数 主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式"— Presentation transcript:

1 第二部分 集合论 第六章 集合代数 主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式
第二部分 集合论 第六章 集合代数 主要内容 集合的基本概念 属于、包含 幂集、空集 文氏图等 集合的基本运算 并、交、补、差等 集合恒等式 集合运算的算律、恒等式的证明方法

2 6.1 集合的基本概念 1. 集合定义 集合没有精确的数学定义 理解：由离散个体构成的整体称为集合，称这些个体为集 合的元素
6.1 集合的基本概念 1. 集合定义 集合没有精确的数学定义 理解：由离散个体构成的整体称为集合，称这些个体为集 合的元素 常见的数集：N, Z, Q, R, C 等分别表示自然数、整数、有 理数、实数、复数集合 2. 集合表示法 枚举法----通过列出全体元素来表示集合 谓词表示法----通过谓词概括集合元素的性质 实例： 枚举法 自然数集合 N={0,1,2,3,…} 谓词法 S={ x | x是实数，x21=0}

3 元素与集合 1. 集合的元素具有的性质 无序性：元素列出的顺序无关 相异性：集合的每个元素只计 数一次 确定性：对任何元素和集合都
1. 集合的元素具有的性质 无序性：元素列出的顺序无关 相异性：集合的每个元素只计 数一次 确定性：对任何元素和集合都 能确定这个元素是否 为该集合的元素 任意性：集合的元素也可以是 集合 2．元素与集合的关系 隶属关系：或者 3．集合的树型层次结构 d A , a A

4 集合与集合 集合与集合之间的关系：, =, ⊈, , ,  定义6.1 A  B  x ( xA  xB )
定义 A = B  A  B  B  A 定义 A  B  A  B  A  B A ⊈ B  x ( xA  xB ) 注意  和  是不同层次的问题

5 空集、全集和幂集 1．定义6.4 空集  ：不含有任何元素的集合 实例： { x | xR  x2+1=0 }
1．定义6.4 空集  ：不含有任何元素的集合 实例： { x | xR  x2+1=0 } 定理6.1 空集是任何集合的子集。 证 对于任意集合A， A  x (xxA) T (恒真命题) 推论 是惟一的 2. 定义6.5 幂集：P(A)={ x | x  A } 实例：P()={}, P({})={,{}} 计数：如果 |A|=n，则 |P(A)|=2n. 3. 定义6.6 全集 E：包含了所有集合的集合 全集具有相对性：与问题有关，不存在绝对的全集

6 6.2 集合的运算 初级运算 集合的基本运算有 定义6.7 并 AB = {x | xA  xB}
6.2 集合的运算 初级运算 集合的基本运算有 定义6.7 并 AB = {x | xA  xB} 交 AB = {x | xA  xB} 相对补 AB = {x | xA  xB} 定义6.8 对称差 AB = (AB)(BA) 定义6.9 绝对补 A = EA

7 文氏图 集合运算的表示 A B A B A B AB A–B AB B A A B AB ~A

8 几点说明 并和交运算可以推广到有穷个集合上，即 A  B  AB =  AB =   AB = A
A1  A2  …  An = { x | xA1 xA2  … xAn} A1  A2  …  An = { x | xA1  xA2  …  xAn} A  B  AB =  AB =   AB = A

9 广义运算 1. 集合的广义并与广义交 定义6.10 广义并 A = { x | z ( zA  xz )}
实例 {{1}, {1,2}, {1,2,3}}={1,2,3} {{1}, {1,2}, {1,2,3}}={1} {{a}}={a}， {{a}}={a} {a}=a， {a}=a

10 关于广义运算的说明 2. 广义运算的性质 (1) =，无意义 (2) 单元集{x}的广义并和广义交都等于x
2. 广义运算的性质 (1) =，无意义 (2) 单元集{x}的广义并和广义交都等于x (3) 广义运算减少集合的层次（括弧减少一层） (4) 广义运算的计算：一般情况下可以转变成初级运算 {A1, A2, … , An}=A1A2…An {A1, A2, … , An}=A1A2…An 3. 引入广义运算的意义 可以表示无数个集合的并、交运算，例如 {{x} | xR}=R 这里的 R 代表实数集合.

11 运算的优先权规定 1 类运算：初级运算, , , ， 优先顺序由括号确定 2 类运算：广义运算和运算， 运算由右向左进行
混合运算：2 类运算优先于1 类运算 例1 A={{a},{a,b}}，计算A(AA). 解： A(AA) = {a,b}({a,b}{a}) = (ab)((ab)a) = (ab)(ba) = b

12 有穷集合元素的计数 1. 文氏图法 2. 包含排斥原理 定理6.2 设集合S上定义了n条性质，其中具有第 i 条性质的
元素构成子集Ai, 那么集合中不具有任何性质的元素数为 推论 S中至少具有一条性质的元素数为

13 实例 例2 求1到1000之间（包含1和1000在内）既不能被5和6整 除，也不能被8整除的数有多少个？ 解 方法一：文氏图 定义以下集合：
例2 求1到1000之间（包含1和1000在内）既不能被5和6整 除，也不能被8整除的数有多少个？ 解 方法一：文氏图 定义以下集合： S={ x | xZ  1x1000} A={ x | xS  x可被5整除} B={ x | xS  x可被6整除} C={ x | xS  x可被8整除} 画出文氏图，然后填入相应的数字，解得 N=1000－( ) =600

14 实例 方法二 |S| = 1000 |A|=1000/5=200, |B|=1000/6=166, |C|=1000/8=125
|AB| = 1000/lcm(5,6) = 1000/33 = 33 |AC| = 1000/lcm(5,8) = 1000/40 = 25 |BC| = 1000/lcm(6,8) = 1000/24 = 41 |ABC| = 1000/lcm(5,6,8) = 1000/120 = 8 = 1000( )+( )8 = 600

15 6.3 集合恒等式 集合算律 1．只涉及一个运算的算律： 交换律、结合律、幂等律    交换 AB=BA AB=BA
6.3 集合恒等式 集合算律 1．只涉及一个运算的算律： 交换律、结合律、幂等律    交换 AB=BA AB=BA AB=BA 结合 (AB)C =A(BC) (AB)C= A(BC) (AB)C =A(BC) 幂等 AA=A AA=A

16 集合算律 2．涉及两个不同运算的算律： 分配律、吸收律 与 与 分配 A(BC)= (AB)(AC) A(BC)=
A(AB)=A A(AB)=A

17 集合算律 3．涉及补运算的算律： DM律，双重否定律   D.M律 A(BC)=(AB)(AC)
(BC)=BC (BC)=BC 双重否定 A=A

18 集合算律 4．涉及全集和空集的算律： 补元律、零律、同一律、否定律  E 补元律 AA= AA=E 零律 A= AE=E

19 集合证明题 证明方法：命题演算法、等式置换法 命题演算证明法的书写规范 (以下的X和Y代表集合公式) (1) 证XY
任取x， xX  …  xY (2) 证X=Y 方法一 分别证明 XY 和 YX 方法二 任取x，xX  …  xY 注意：在使用方法二的格式时，必须保证每步推理都是充 分必要的

20 集合等式的证明 方法一：命题演算法 例3 证明A(AB) = A （吸收律） 证 任取x, xA(AB)  xAxAB
 xA(xAxB)  xA 因此得 A(AB) = A. 例4 证明 AB = AB 证 任取x, x AB  xAxB  xAxB  xAB 因此得 AB = AB

21 等式代入法 方法二：等式置换法 例5 假设交换律、分配律、同一律、零律已经成立，证明吸 收律. 证 A(AB)
例5 假设交换律、分配律、同一律、零律已经成立，证明吸 收律. 证 A(AB) = (AE)(AB) （同一律） = A(EB) （分配律） = A(BE) （交换律） = AE （零律） = A （同一律）

22 包含等价条件的证明 例6 证明AB  AB=B  AB=A  AB= ① ② ③ ④ 证明思路：
① ② ③ ④ 证明思路： 确定问题中含有的命题：本题含有命题 ①, ②, ③, ④ 确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论 确定证明顺序：①②，②③，③④，④① 按照顺序依次完成每个证明（证明集合相等或者包含）

23 证明 证明AB  AB=B  AB=A  AB= ① ② ③ ④ 证 ①② 显然BAB，下面证明ABB. 任取x，
① ② ③ ④ 证 ①② 显然BAB，下面证明ABB. 任取x， xAB  xAxB  xBxB  xB 因此有ABB. 综合上述②得证. ②③ A=A(AB)  A=AB (由②知AB=B，将AB用B代入)

24 证明 ③④ 假设AB, 即xAB，那么知道xA且xB. 而 xB  xAB 从而与AB=A矛盾. ④①
x(xAxB)  xAB  AB 与条件④矛盾.

25 第六章 习题课 主要内容 集合的两种表示法 集合与元素之间的隶属关系、集合之间的包含关系的区别与联系 特殊集合：空集、全集、幂集
文氏图及有穷集合的计数 集合的, , , , 等运算以及广义, 运算 集合运算的算律及其应用

26 基本要求 熟练掌握集合的两种表示法 能够判别元素是否属于给定的集合 能够判别两个集合之间是否存在包含、相等、真包含等关系
熟练掌握集合的基本运算（普通运算和广义运算） 掌握证明集合等式或者包含关系的基本方法

27 练习1 1．判断下列命题是否为真 (1)  (2)  (3) {} (4) {}
(1)  (2)  (3) {} (4) {} (5) { a, b }  { a, b, c, {a, b, c}} (6) { a, b } { a, b, c, {a, b}} (7) { a, b}  { a, b, {{a, b}}} (8) { a, b} { a, b, {{a,b}}} 解 (1)、(3)、(4)、(5)、(6)、(7)为真，其余为假.

28 方法分析 (1) 判断元素a与集合A的隶属关系是否成立基本方法： 把 a 作为整体检查它在A中是否出现，注意这里的 a 可 能是集合表达式.
(2) 判断AB的四种方法 若A,B是用枚举方式定义的，依次检查A的每个元素是否在B中出现. 若A,B是谓词法定义的，且A, B中元素性质分别为P和Q, 那么“若P则Q”意味 AB，“P当且仅当Q”意味Ａ=Ｂ． 通过集合运算判断AB，即AB = B, AB = A, AB = 三个等式中有一个为真. 通过文氏图判断集合的包含（注意这里是判断，而不是证明

29 练习2 2．设 S1={1, 2, … , 8, 9}， S2={2, 4, 6, 8} S3={1, 3, 5, 7, 9} S4={3, 4, 5} S5={3, 5} 确定在以下条件下X是否与S1,…,S5中某个集合相等？如果是，又与哪个集合相等？ （1）若 XS5= （2）若 XS4但 XS2= （3）若 XS1且 X ⊈S3 （4）若 XS3= （5）若 XS3 且 X ⊈ S1

30 解答 解 (1) 和S5不交的子集不含有3和5，因此 X=S2. (2) S4的子集只能是S4和S5. 由于与S2不交，不能含有偶数，
(3) S1, S2, S3, S4和S5都是S1的子集，不包含在S3的子集含有 偶数，因此 X=S1, S2或S4. (4) XS3=意味着 X是S3的子集，因此 X=S3或 S5. (5) 由于S3是S1的子集，因此这样的X不存在.

31 练习3 3. 判断以下命题的真假，并说明理由. （1）AB = A  B= （2）A(BC) = (AB)(AC)
（3）AA = A （4）如果AB = B，则A = E. （5）A = {x}x，则 xA且x  A.

32 解题思路 先将等式化简或恒等变形. 查找集合运算的相关的算律，如果与算律相符，结果为真. 注意以下两个重要的充要条件
AB = A  AB =  AB =   AB  AB = B  AB = A 如果与条件相符，则命题为真. 如果不符合算律，也不符合上述条件，可以用文氏图表示集合，看看命题是否成立.如果成立，再给出证明. 试着举出反例，证明命题为假.

33 解答 解 (1) B=是AB=A的充分条件，但不是必要条件. 当B不空但 是与A不交时也有AB=A. (2) 这是DM律，命题为真.
(3) 不符合算律，反例如下： A={1}，AA=，但是A. (4) 命题不为真. AB=B的充分必要条件是 BA，不是A=E. (5) 命题为真，因为 x 既是 A 的元素，也是 A 的子集

34 练习4 证明要求 证明方法： 4．证明 AB = AC  AB = AC  B = C 解题思路 分析命题：含有3个命题：
① ② ③ 证明要求 前提：命题①和② 结论：命题③ 证明方法： 恒等式代入 反证法 利用已知等式通过运算得到新的等式

35 解答 方法一：恒等变形法 B = B(BA) = B(AB) = B(AC) = (BA)(BC)
= (AC)(BC) = (AB)C = (AC)C = C 方法二：反证法. 假设 B  C，则存在 x (xB且xC), 或存在 x (xC且xB). 不妨设为前者. 若x属于A，则x属于AB 但x不属于AC，与已知矛盾； 若x不属于A，则x属于AB但x不属于AC，也与已知矛盾.

36 解答 方法三：利用已知等式通过运算得到新的等式. 由已知等式①和②可以得到 (AB) (AB) = (AC) (AC) 即
从而有 A(AB) =A(AC) 根据结合律得 (AA)B = (AA) C 由于AA = , 化简上式得B = C.

37 练习5 5．设A,B为集合，试确定下列各式成立的充分必要条件： (1) AB=B (2) AB=BA (3) AB=AB

38 分析 解题思路: 求解集合等式成立的充分必要条件可能用到集合的算律、不同集合之间的包含关系、以及文氏图等. 具体求解过程说明如下：
(1) 化简给定的集合等式 (2) 求解方法如下： 利用已知的算律或者充分必要条件进行判断 先求必要条件，然后验证充分性 利用文氏图的直观性找出相关的条件，再利用集合论的证明方法加以验证

39 解答 解 (1) AB=B  A=B=. 求解过程如下： 由AB=B得 (AB)B = BB
(2) AB=BA  A=B. 求解过程如下： 充分性是显然的，下面验证必要性. 由AB=BA得 (AB)A=(BA)A 从而有A=AB, 即AB. 同理可证BA.

40 解答 (3) AB=AB  A=B. 求解过程如下： 充分性是显然的，下面验证必要性. 由AB=AB得
A(AB) = A(AB) 化简得A =AB，从而有AB. 类似可以证明BA. (4) AB=A  B=. 求解过程如下： 充分性是显然的，下面验证必要性. 由AB = A得 A(AB) = AA 根据结合律有 (AA)B = AA 即 B = , 就是B = .