《离散-ch6(my)》由会员分享，可在线阅读，更多相关《离散-ch6(my)（37页珍藏版）》请在金锄头文库上搜索。
1、主要内容 l集合的基本概念属于、包含幂集、空集文氏图等l集合的基本运算并、交、补、差等l集合恒等式集合运算的算律、恒等式的证明方法 第二部分 集合论第六章 集合代数16.1 集合的基本概念1. 集合定义集合没有精确的数学定义理解：由离散个体构成的整体称为集合，称这些 个体为集 合的元素常见的数集：N, Z, Q, R, C 等分别表示自然数、 整数、有 理数、实数、复数集合2. 集合表示法枚举法-通过列出全体元素来表示集合谓词表示法-通过谓词概括集合元素的性质实例：枚举法 自然数集合 N=0,1,2,3,谓词法 S= x | x是实数，x21=0 2元素与集合1. 集合的元素具有的性质无序性：
2、元素列出的顺序无关相异性：集合的每个元素只计数一次确定性：对任何元素和集合都能确定这个元素是否为该集合的元素任意性：集合的元素也可以是集合2元素与集合的关系隶属关系：或者3集合的树型层次结构d A , a A3集合与集合集合与集合之间的关系：, =, , , , 定义6.1 A B x ( xA xB ) 定义6.2 A = B A B B A 定义6.3 A B A B A B A B x ( xA xB ) 思考： 和 的定义 注意 和 是不同层次的问题4空集、全集和幂集1定义6.4 空集 ：不含有任何元素的集合实例： x | xR x2+1=0 定理6.1 空集是任何集合的子集。证 对于
3、任意集合A，A x (xxA) T (恒真命题) 推论 是惟一的3. 定义6.6 全集 E：包含了所有集合的集合全集具有相对性：与问题有关，不存在绝对的 全集2. 定义6.5 幂集：P(A)= x | x A 实例：P()=, P()=,计数：如果 |A|=n，则 |P(A)|=2n.56.2 集合的运算初级运算 集合的基本运算有 定义6.7 并 AB = x | xA xB交 AB = x | xA xB相对补 AB = x | xA xB 定义6.8 对称差 AB = (AB)(BA) 定义6.9 绝对补 A = EA 6文氏图集合运算的表示ABABABABABABABABABA7几点说明
4、l并和交运算可以推广到有穷个集合上，即 A1 A2 An = x | xA1 xA2 xAn A1 A2 An = x | xA1 xA2 xAnl A B AB = l AB = AB = A8广义运算1. 集合的广义并与广义交 定义6.10 广义并 A = x | z ( zA xz )广义交 A= x | z ( zA xz ) 实例1, 1,2, 1,2,3=1,2,31, 1,2, 1,2,3=1a=a， a=aa=a， a=a9关于广义运算的说明2. 广义运算的性质(1) =，无意义 (2) 单元集x的广义并和广义交都等于x (3) 广义运算减少集合的层次（括弧减少一层）(4) 广
5、义运算的计算：一般情况下可以转变成初级 运算A1, A2, , An=A1A2AnA1, A2, , An=A1A2An 3. 引入广义运算的意义可以表示无数个集合的并、交运算，例如x | xR=R这里的 R 代表实数集合. 10运算的优先权规定1 类运算：初级运算, , , ，优先顺序由括号确定 2 类运算：广义运算和运算，运算由右向左进行 混合运算：2 类运算优先于1 类运算例1 A=a,a,b，计算A(AA). 解： A(AA) = a,b(a,ba)= (ab)(ab)a)= (ab)(ba) = b116.3 集合恒等式集合算律 1只涉及一个运算的算律：交换律、结合律、幂等律交换AB
6、=BAAB=BAAB=BA 结合(AB)C =A(BC)(AB)C= A(BC)(AB)C =A(BC) 幂等AA=AAA=A12集合算律2涉及两个不同运算的算律：分配律、吸收律 与与分配A(BC)= (AB)(AC) A(BC)= (AB)(AC)A(BC) =(AB)(AC)吸收A(AB)=A A(AB)=A13集合算律3涉及补运算的算律：DM律，双重否定律 D.M律A(BC)=(AB)(AC ) A(BC)=(AB)(AC )(BC)=BC (BC)=BC双重否定A=A14集合算律4涉及全集和空集的算律：补元律、零律、同一律、否定律E补元律AA=AA=E 零律A=AE=E 同一律A=AA
7、E=A 否定=EE=15集合证明题证明方法：命题演算法、等式置换法命题演算证明法的书写规范 (以下的X和Y代表集合 公式) (1) 证XY任取x， xX xY (2) 证X=Y方法一 分别证明 XY 和 YX方法二 任取x，xX xY注意：在使用方法二的格式时，必须保证每步推理 都是充 分必要的16集合等式的证明方法一：命题演算法 例3 证明A(AB) = A （吸收律）证 任取x,xA(AB) xAxAB xA(xAxB) xA 因此得 A(AB) = A.例4 证明 AB = AB 证 任取x,x AB xAxB xAxB xAB 因此得 AB = AB17等式代入法方法二：等式置换法 例
8、5 假设交换律、分配律、同一律、零律已经成立 ，证明吸收律. 证 A(AB) = (AE)(AB) （同一律）= A(EB) （分配律） = A(BE) （交换律）= AE （零律）= A （同一律）18包含等价条件的证明例6 证明AB AB=B AB=A AB= 证明思路： l确定问题中含有的命题：本题含有命题 , , , l确定命题间的关系（哪些命题是已知条件、哪些命 题是要证明的结论）：本题中每个命题都可以作为已 知条件，每个命题都是要证明的结论 l确定证明顺序：， l按照顺序依次完成每个证明（证明集合相等或者包 含） 19证明证明AB AB=B AB=A AB= 证 显然BAB，下面证
9、明ABB. 任取x， xAB xAxB xBxB xB因此有ABB. 综合上述得证. A=A(AB) A=AB (由知AB=B，将 AB用B代入) 20 假设AB, 即xAB，那么知道xA且xB. 而xB xAB 从而与AB=A矛盾. 假设AB不成立，那么x(xAxB) xAB AB 与条件矛盾. 证明21第六章 习题课主要内容 l集合的两种表示法 l集合与元素之间的隶属关系、集合之间的包含关系 的区别与联系 l特殊集合：空集、全集、幂集 l文氏图及有穷集合的计数 l集合的, , , , 等运算以及广义, 运算l集合运算的算律及其应用22基本要求l熟练掌握集合的两种表示法 l能够判别元素是否属
10、于给定的集合 l能够判别两个集合之间是否存在包含、相等、真包 含等关系 l熟练掌握集合的基本运算（普通运算和广义运算） l掌握证明集合等式或者包含关系的基本方法23练习11判断下列命题是否为真(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)为真，其余为假.24方法分析(1) 判断元素a与集合A的隶属关系是否成立基本方 法：把 a 作为整体检查它在A中是否出现，注意这里 的 a 可能是集合表达
11、式. (2) 判断AB的四种方法 l若A,B是用枚举方式定义的，依次检查A的每个元 素是否在B中出现. l若A,B是谓词法定义的，且A, B中元素性质分别为P 和Q, 那么“若P则Q”意味 AB，“P当且仅当Q”意味 = l通过集合运算判断AB，即AB = B, AB = A, AB = 三个等式中有一个为真.l通过文氏图判断集合的包含（注意这里是判断，而 不是证明25练习22设S1=1, 2, , 8, 9， S2=2, 4, 6, 8S3=1, 3, 5, 7, 9 S4=3, 4, 5S5=3, 5确定在以下条件下X是否与S1,S5中某个集合相 等？如果是，又与哪个集合相等？（1）若 X
12、S5=（2）若 XS4但 XS2=（3）若 XS1且 X S3（4）若 XS3=（5）若 XS3 且 X S126解答解 (1) 和S5不交的子集不含有3和5，因此 X=S2. (2) S4的子集只能是S4和S5. 由于与S2不交，不能含有 偶数，因此 X=S5. (3) S1, S2, S3, S4和S5都是S1的子集，不包含在S3的子 集含有偶数，因此 X=S1, S2或S4. (4) XS3=意味着 X是S3的子集，因此 X=S3或 S5. (5) 由于S3是S1的子集，因此这样的X不存在.27练习33. 判断以下命题的真假，并说明理由. （1）AB = A B=（2）A(BC) = (AB)(AC)（3）AA = A（4）如果AB = B，则A = E. （5）A = xx，则 xA且x A. 28解题思路l先将等式化简或恒等变形.l查找集合运算的相关的算律，如果与算律相符，结 果为真.l注意以下两个重要的充要条件AB = A AB = AB = AB AB = B AB = A 如果与条件相符，则命题为真.l如果不符合算律，也不符合上述条件，可以用文氏 图表示集合，看看命题是否成立.如果成立，再给出 证明. l试着举出反例，证
