离散数学-六的.ppt

主要内容l集合的基本概念 属于、包含 幂集、空集 文氏图等l集合的运算l有穷集的计数l集合恒等式 集合运算的算律、恒等式的证明方法 第二部分 集合论第六章 集合代数1.6.1 集合的基本概念1.集合定义 集合没有精确的数学定义 理解：由离散个体构成的整体称为集合，称这些个体为集 合的元素 常见的数集：N,Z,Q,R,C 等分别表示自然数、整数、有 理数、实数、复数集合2.集合表示法 列元素法-列出集合的所有元素，所有元素之间用逗号隔开，并把它们用花括号括起来 谓词表示法-用谓词来概括集合中元素的性质 实例：列元素法 自然数集合 N=0,1,2,3,谓词表示法 S=x|x R x2 1=0 2.元素与集合1.集合的元素具有的性质 无序性：元素列出的顺序无关 相异性：集合的每个元素只计 数一次 确定性：对任何元素和集合都 能确定这个元素是否 为该集合的元素 任意性：集合的元素也可以是 集合2元素与集合的关系 隶属关系：或者 3集合的树型层次结构例如：集合A=a,b,c,d,d规定：A A3.集合与集合集合与集合之间的关系：,=,定义6.1 设A，B为集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B，记作B A。如果B不被A包含，则记作B A。符号化表示为：B A x(x B x A)B A x(x B x A)例如N Z Q R C，但Z N。显然对任何集合A都有A A。定义6.2 设A，B为集合，如果A B且B A，则称A与B相等，记作AB。如果A与B不相等，则记作AB。符号化表示为：A=B A B B A定义6.3 设A，B为集合，如果B A且BA，则称B是A的真子集，记作B A。如果B不是A的真子集，则记作B A。符号化表示为：B A B A B A 例如N Z Q R C，但N N。注意：和 是不同层次的问题，如A=a,a和a4.空集、全集和幂集定义6.4 空集 ：不含有任何元素的集合符号化表示为：=x|x x 实例：x|x R x2+1=0 定理6.1 空集是任何集合的子集。证 对于任意集合A，A x(xx A)1(恒真命题)推论 是惟一的 证明：假设存在空集1 和 2 ，由定理6.1有：1 2 和 2 1 根据集合相等的定义，有1=2 所以得出结论：是惟一的。5.空集、全集和幂集 含有n个元素的集合简称n元集，它的含有m（mn）个元素的子集叫做它的m元子集。任给一个n元集，怎样求出它的全部子集呢？例6.1 A1,2,3，将A的子集分类：解：0元子集，也就是空集，只有一个：；1元子集，即单元集：1，2，3；2元子集：1,2，1,3，2,3；3元子集：1,2,3。6.空集、全集和幂集 定义6.5 幂集：设A为集合，把A的全部子集构成的集合叫做A的幂集，记作P(A)(或PA，2A)。符号化表示为：P(A)=x|x A 实例：P()=,P()=,计数：如果|A|=n，则|P(A)|=2n.定义6.6 全集 E：包含了所有集合的集合 全集具有相对性：与问题有关，不存在绝对的全集7.6.2 集合的运算初级运算集合的基本运算有并，交，相对补和对称差 定义6.7 设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集AB分别定义如下：并 A B=x|x A x B 交 A B=x|x A x B 相对补 A B=x|x A x B例如：A=a,b,c，B=a，C=b,dA B=a,b,c,A B=a,A B=b,c,B-A=,B C=若两个集合的交集为，则称这两个集合是不交的8.6.2 集合的运算定义6.8 设A，B为集合，A与B的对称差集A B定义为：对称差 A B=(A B)(B A)另一种定义是：A B=(A B)(A B)例如：A=a,b,c，B=b,d,A B=a,c,d定义6.9 在给定全集E以后，A E，A的绝对补集A定义如下：绝对补 A=E A=x|xEx A=x|x A 例如：Ea，b，c，d，Aa，b，c，则Ad。9.文氏图集合运算的表示ABABABABAEA BA BABA BA10.几点说明l并和交运算可以推广到有穷个集合上，即A1 A2 An=x|xA1 xA2 xAn A1 A2 An=x|xA1 xA2 xAnl A B A B=l A B=A B=A11.广义运算1.集合的广义并与广义交 定义6.10 设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为 广义并 A=x|z(z A x z)定义6.11 设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为 广义交 A=x|z(z A x z)例6.2 设Aa,b,c,a,c,d,a,e,fBaCa,c,d则Aa,b,c,d,e,f,Ba，Cac,d Aa，Ba，Cac,d 12.广义运算1.集合的广义并与广义交 定义6.10 设A为集合，A的元素的元素构成的集合称为A的广义并，记为A。符号化表示为 广义并 A=x|z(z A x z)定义6.11 设A为非空集合，A的所有元素的公共元素构成的集合称为A的广义交，记为A。符号化表示为 广义交 A=x|z(z A x z)练习:A=1,1,2,1,2,3,B=a,C=a解:A=1,2,3,A=1 B=a，B=a C=a，C=a13.关于广义运算的说明2.广义运算的性质 (1)=，无意义 (2)单元集x的广义并和广义交都等于x (3)广义运算减少集合的层次（括弧减少一层）(4)广义运算的计算：一般情况下可以转变成初级运算 A=A1,A2,An=A1 A2 An A=A1,A2,An=A1 A2 An 3.引入广义运算的意义 可以表示无数个集合的并、交运算，例如 x|x R=R 这里的 R 代表实数集合.14.运算的优先权规定 一 类运算：广义并，广义交，幂集，绝对补 运算 运算由右向左顺序进行(右结合)二 类运算：并 ，交 ，相对补 ，对称差 优先顺序由括号确定混合运算：一类运算优先于二类运算。例 A=a,a,b，计算A(AA).解：A(AA)=a,b(a,ba)=(a b)(a b)a)=(a b)(b a)=b15.例6.5 设Aa,a,b 计算A，A和A(AA)。解:Aa,bAaAabAaAabAaA(AA)(ab)(ab)a)(ab)(ba)b所以Aab，Aa，A(AA)b。16.作业书本97页第8题 的 第（4）小题第9题 的 第（1）、（3）、（5）三个小题书本98页第18题 的 第（1）、（3）两个小题17.有穷集合元素的计数1.文氏图法2.包含排斥原理定理6.2 设集合S上定义了n条性质，其中具有第 i 条性质的元素构成子集Ai,那么集合中不具有任何性质的元素数为 推论 S中至少具有一条性质的元素数为18.实例例6.5 求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(200+100+33+67)=60019.实例方法二|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(200+166+125)+(33+25+41)8=600 20.6.3 集合恒等式下面的恒等式给出了集合运算的主要算律，其中A，B，C代表任意集合。幂等律 AAA AAA 结合律 (AB)CA(BC)(AB)CA(BC)交换律 ABBA ABBA 分配律 A(BC)(AB)(AC)A(BC)(AB)(AC)同一律 AA AEA零律 AEE A 排中律 AAE 矛盾律 AA吸收律 A(AB)A A(AB)A 德摩根律 A(BC)(AB)(AC)A(BC)(AB)(AC)(BC)=BC (BC)=BC E E双重否定律 (A)A 21.除了以上算律以外，还有一些关于集合运算性质的重要结果。例如：AB A，AB B (6.24)A AB，B AB (6.25)AB A (6.26)ABAB (6.27)ABB A B ABA AB (6.28)A BB A (6.29)(A B)CA (B C)(6.30)A A (6.31)A A (6.32)A BA C BC (6.33)22.书本88页例6.5 设Aa,a,b 计算A，A和A(AA)。解:Aa,bAaAabAaAabAaA(AA)(ab)(ab)a)(ab)(ba)b所以Aab，Aa，A(AA)b。23.6.4 集合恒等式（P92）集合算律1只涉及一个运算的算律：交换律、结合律、幂等律 交换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=A24.集合算律 2涉及两个不同运算的算律：分配律、吸收律 与 与 分配A(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)=A25.集合算律3涉及补运算的算律：德摩根律，双重否定律 德摩根律A(B C)=(A B)(A C)A(B C)=(A B)(A C)(B C)=BC(B C)=BC双重否定律A=A26.集合算律4涉及全集和空集的算律：补元律、零律、同一律、否定律E补元律AA=AA=E零律A=A E=E同一律A=AA E=A否定律=E E=27.集合证明题证明方法：命题演算法、等式置换法命题演算证明法的书写规范(以下的X和Y代表集合公式)(1)证X Y 任取x，x X x Y(2)证X=Y 方法一 分别证明 X Y 和 Y X 都为真。方法二 任取x，x X x Y注意：在使用方法二的格式时，必须保证每步推理都是充分必要的（等值）28.集合等式的证明方法一：命题演算法例1 证明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.例2 证明(6.27)A B=AB证 任取x,x A B x A x B x A xB x AB 因此得 A B=AB29.等式置换法方法二：等式置换法例3 假设交换律、分配律、同一律、零律已经成立，证明吸 收律 A(A B)=A.证 A(A B)=(A E)(A B)（同一律）=A(E B)（分配律）=A(B E)（交换律）=A E （零律）=A （同一律）30.包含等价条件的证明例4 证明(6.28)A B A B=B A B=A A B=证明思路：l确定问题中含有的命题：本题含有命题,l确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论l确定证明顺序：，l按照顺序依次完成每个证明（证明集合相等或者包含）31.证明证明A B A B=B A B=A A B=证 显然B A B，下面证明A B B.任取x，x A B x A x B x B x B x B 因此有A B B.综合上述得证.A B=A(A B)=A(由知A B=B，将A B代入B，并结合吸收律得证)32.证明A B A B=B A B=A A B=A B=A B=(A B)B=A(B B)=A=假设A B不成立，那么 x(x A x B)x A B A B与条件矛盾.因此，结论A B成立。证明33.式（6.28）在化简集合公式中的应用例 6.14 化简(ABC)(AB)(A(BC)A)解：由于 AB ABC，A A(BC)因此有：(ABC)(AB)(A(BC)A)=(AB)A （由式子（6.28）=(AB)A （由式子（6.27）=(AA)(BA)（分配律）=(BA)（矛盾律）=(BA)（交换律）=BA （同一律）=B A （由式子（6.27）34.对称差运算算律 式（6.33）的证明例 6.15 已知A B=A C，证明B=C证已知A B=A C，所以有 A(A B)=A(A C)(A A)B=(A A)C （由式子（6.30）B=C （由式子（6.32）B =C （由式子（6.29）B=C （由式子（6.31）35.练习题练习：证明下列集合恒等式（1）（A B）C=（A C）B证明：左边=（A B）C =（A B）C （由式子（6.27）=（A C）B （交换律和结合律）=（A C）B （由式子（6.27）=右边（2）（A B）A）=A证明：左边=（A B）A）=（A B）A）（德摩根律）=（A B）A （德摩根律）=A （吸收律）=右边36.第六章 练习作业书本第100页 第32题的第（1）小题 第33题的第（1）小题 第50题37.第六章 总结主要内容l集合的两种表示法l集合与元素之间的隶属关系、集合之间的包含关系的区别与联系l特殊集合：空集、全集、幂集l文氏图及有穷集合的计数l集合的,等运算以及广义,运算l集合运算的算律及其应用38.第六章 习题课主要内容l集合的两种表示法l集合与元素之间的隶属关系、集合之间的包含关系的区别与联系l特殊集合：空集、全集、幂集l文氏图及有穷集合的计数l集合的,等运算以及广义,运算l集合运算的算律及其应用39.基本要求l熟练掌握集合的两种表示法l能够判别元素是否属于给定的集合l能够判别两个集合之间是否存在包含、相等、真包含等关系l熟练掌握集合的基本运算（普通运算和广义运算）l掌握证明集合等式或者包含关系的基本方法40.练习1 1判断下列命题是否为真(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)为真，其余为假.41.方法分析(1)判断元素a与集合A的隶属关系是否成立基本方法：把 a 作为整体检查它在A中是否出现，注意这里的 a 可 能是集合表达式.(2)判断A B的四种方法l若A,B是用枚举方式定义的，依次检查A的每个元素是否在B中出现.l若A,B是谓词法定义的，且A,B中元素性质分别为P和Q,那么“若P则Q”意味 A B，“P当且仅当Q”意味=l通过集合运算判断A B，即A B=B,A B=A,A B=三个等式中有一个为真.l通过文氏图判断集合的包含（注意这里是判断，而不是证明42.练习22设 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 S143.解答解(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)X S3=意味着 X是S3的子集，因此 X=S3或 S5.(5)由于S3是S1的子集，因此这样的X不存在.44.练习33.判断以下命题的真假，并说明理由.（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.45.解题思路l先将等式化简或恒等变形.l查找集合运算的相关的算律，如果与算律相符，结果为真.l注意以下两个重要的充要条件 A B=A A B=A B=A B A B=B A B=A 如果与条件相符，则命题为真.l如果不符合算律，也不符合上述条件，可以用文氏图表示集合，看看命题是否成立.如果成立，再给出证明.l试着举出反例，证明命题为假.46.解答解(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 的子集 47.练习44证明 A B=A C A B=A C B=C解题思路l分析命题：含有3 3个命题：A B=A C,A B=A C,B=C l证明要求 前提：命题和 结论：命题 l证明方法：恒等式代入 反证法 利用已知等式通过运算得到新的等式48.解答方法一：恒等变形法 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，也与已知矛盾.49.解答方法三：利用已知等式通过运算得到新的等式.由已知等式和可以得到 (A B)(A B)=(A C)(A C)即 A B=A C 从而有 A(A B)=A(A C)根据结合律得 (A A)B=(A A)C 由于A A=,化简上式得B=C.50.练习55设A,B为集合，试确定下列各式成立的充分必要条件：(1)A B=B(2)A B=B A(3)A B=A B(4)A B=A51.分析解题思路:求解集合等式成立的充分必要条件可能用到集合的算律、不同集合之间的包含关系、以及文氏图等.具体求解过程说明如下：(1)化简给定的集合等式 (2)求解方法如下：l利用已知的算律或者充分必要条件进行判断l先求必要条件，然后验证充分性l利用文氏图的直观性找出相关的条件，再利用集合论的证明方法加以验证 52.解答解(1)A B=B A=B=.求解过程如下：由A B=B得 (AB)B=B B 化简得B=.再将这个结果代入原来的等式得A=.从而得到必要条件A=B=.再验证充分性.如果A=B=成立，则A 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.53.解答(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=.54.