第六章--集合代数-离散数学及其应用课件.ppt

《第六章--集合代数-离散数学及其应用课件.ppt》由会员分享，可在线阅读，更多相关《第六章--集合代数-离散数学及其应用课件.ppt（44页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1主要内容主要内容l集合的基本概念集合的基本概念属于、包含属于、包含幂集、空集幂集、空集l集合的基本运算集合的基本运算并、交、补、差等并、交、补、差等l集合恒等式集合恒等式集合运算的算律、恒等式的证明方法集合运算的算律、恒等式的证明方法第二部分第二部分 集合论集合论第六章第六章 集合代数集合代数26.1集合的基本概念集合的基本概念1.集合定义集合定义集合没有精确的数学定义集合没有精确的数学定义理解：由离散个体构成的整体称为理解：由离散个体构成的整体称为集合集合，称这些个体为集，称这些个体为集合的合的元素元素常见的数集：常见的数集：N,Z,Q,R,C等分别表示自然数、整数、有等分别表示自然数、整

2、数、有理数、实数、复数集合理数、实数、复数集合2.集合表示法集合表示法枚举法枚举法-通过列出全体元素来表示集合通过列出全体元素来表示集合谓词表示法谓词表示法-通过谓词概括集合元素的性质通过谓词概括集合元素的性质实例：实例：枚举法枚举法自然数集合自然数集合N=0,1,2,3,谓词法谓词法S=x|x是实数，是实数，x2 1=03元素与集合元素与集合1.集合的元素具有的性质集合的元素具有的性质无序性：元素列出的顺序无关无序性：元素列出的顺序无关相异性：集合的每个元素只计相异性：集合的每个元素只计数一次数一次确定性：对任何元素和集合都确定性：对任何元素和集合都能确定这个元素是否能确定这个元素是否为该集

3、合的元素为该集合的元素任意性：集合的元素也可以是任意性：集合的元素也可以是集合集合2元素与集合的关系元素与集合的关系隶属关系：隶属关系：或者或者 3集合的树型层次结构集合的树型层次结构A=a,b,b,d d A,a A4集合与集合集合与集合集合与集合之间的关系：集合与集合之间的关系：,=,定义定义6.1 A B x(x A x B)定义定义6.2 A=BA B B A定义定义6.3 A BA B A B A B x(x A x B)思考：思考：和和 的定义的定义注意注意 和和 是不同层次的问题是不同层次的问题66.2 集合的运算集合的运算初级运算初级运算集合的基本运算有集合的基本运算有定义定义

4、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 Al并和交运算可以推广到有穷个集合上，即并和交运算可以推广到有穷个集合上，即A1 A2 An=x|x A1 x A2 x AnA1 A2 An=x|x A1 x A2 x An7广义运算广义运算1.集合的广义并与广义交集合的广义并与广义交定义定义6.10广义并广义并 A=x|z(z A x z)定义定义6.11广义交广义交 A=x|z(z A x z)实例实例 1,1,2,1,2,3=1,2,3 1,1

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

6、代表实数集合代表实数集合.10文氏图文氏图ABABABABABA BA BABA BA6.3有穷集合元素的计数有穷集合元素的计数11方法一：文氏图方法一：文氏图例例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(200+100+33+67)

7、=60013实例实例方法二方法二|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欧拉函数（续）欧拉函数（续）与与60互素的正整数有互素的正整数有16个：个：1,7,11,13,17,19,23,29,31,37,41,43,47

8、,49,53,59.15实例：实例：错位排列计数错位排列计数例例4错位排列：错位排列：排列排列i1i2in，满足，满足ij j,j=1,2,n.错位排列数错位排列数S为为1,2,n排列的集合，排列的集合，Pi是是i 处在排列处在排列第第i 位的性质，位的性质，Ai是是S中具有性质中具有性质Pi的排列的集合，的排列的集合，i=1,2,n.|S|=n!，|Ai|=(n 1)!i=1,2,n|Ai Aj|=(n 2)!1 ij n|A1 A2 An|=0!=11618集合算律集合算律2涉及两个不同运算的算律：涉及两个不同运算的算律：分配律、吸收律分配律、吸收律 与与 与与 分配分配A(B C)=(A

9、 B)(A C)A(B C)=(A B)(A C)A(B C)=(A B)(A C)吸收吸收A(A B)=AA(A B)=A19集合算律集合算律3涉及补运算的算律：涉及补运算的算律：DM律律，双重否定律双重否定律 D.M律律A(B C)=(A B)(A C)A(B C)=(A B)(A C)(B C)=BC(B C)=BC双重否定双重否定A=A20集合算律集合算律4涉及全集和空集的算律：涉及全集和空集的算律：补元律补元律、零律零律、同一律同一律、否定律否定律E补元律、排中律补元律、排中律AA=AA=E零律零律A=A E=E同一律同一律A=AA E=A否定律否定律=E E=21集合证明题集合证明

10、题证明方法：命题演算法、等式置换法证明方法：命题演算法、等式置换法命题演算证明法的书写规范命题演算证明法的书写规范(以下的以下的X和和Y代表集合公式代表集合公式)(1)证证X Y任取任取x，x X x Y(2)证证X=Y方法一方法一分别证明分别证明X Y 和和Y X方法二方法二任取任取x，x X x Y注意：在使用方法二的格式时，必须保证每步推理都是充注意：在使用方法二的格式时，必须保证每步推理都是充分必要的分必要的22集合等式的证明集合等式的证明方法一：命题演算法方法一：命题演算法例例5证明证明A(A B)=A（吸收律）（吸收律）证证任取任取x,x A(A B)x A x A B x A(x

11、 A x B)x A因此得因此得A(A B)=A.例例6证明证明A B=AB证证任取任取x,x A Bx A x B x A xB x AB因此得因此得A B=AB24包含等价条件的证明包含等价条件的证明例例8证明证明A B AB=B A B=A A B=证明思路：证明思路：l确定问题中含有的命题：本题含有命题确定问题中含有的命题：本题含有命题,l确定命题间的关系（哪些命题是已知条件、哪些命题是要确定命题间的关系（哪些命题是已知条件、哪些命题是要证明的结论）：本题中每个命题都可以作为已知条件，每证明的结论）：本题中每个命题都可以作为已知条件，每个命题都是要证明的结论个命题都是要证明的结论l确定

12、证明顺序：确定证明顺序：，l按照顺序依次完成每个证明（证明集合相等或者包含）按照顺序依次完成每个证明（证明集合相等或者包含）25证明证明证明证明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=A(A B)A=A B(由由知知A B=B，将，将A B用用B代入代入)26假设假设A B,即即 x A B，那么知道，那么知道x A且且x B.而而 x B x A B从而与从而与A B=A矛盾矛盾.假设假设A B不成立，那么不成立，那么 x(

13、x A x B)x A B A B与条件与条件矛盾矛盾.证明证明28基本要求基本要求l熟练掌握集合的两种表示法熟练掌握集合的两种表示法l能够判别元素是否属于给定的集合能够判别元素是否属于给定的集合l能够判别两个集合之间是否存在包含、相等、真包含等关能够判别两个集合之间是否存在包含、相等、真包含等关系系l熟练掌握集合的基本运算（普通运算和广义运算）熟练掌握集合的基本运算（普通运算和广义运算）l掌握有穷集合的计数方法和包含排斥原理掌握有穷集合的计数方法和包含排斥原理l掌握证明集合等式或者包含关系的基本方法掌握证明集合等式或者包含关系的基本方法29练习练习11判断下列命题是否为真判断下列命题是否为真

14、(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)为真，其余为假为真，其余为假.31练习练习22设设 S1=1,2,8,9，S2=2,4,6,8S3=1,3,5,7,9S4=3,4,5S5=3,5确定在以下条件下确定在以下条件下X是否与是否与S1,S5中某个集合相等？如中某个集合相等？如果是，又与哪个集合相等？果是，又与哪个集合相等？（1）若）若X S5=（2）若）若X S4但但X S2=（3）若）若X S1且且X S3（4）若）若X S3=（5）

15、若）若X S3且且X S132解答解答解解(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不存在不存在.练习练习33.一个班一个班50个学生，在第一次考试中有

16、个学生，在第一次考试中有26人得人得5分，在第二分，在第二次考试中有次考试中有21人得人得5分分.如果两次考试中都没有得如果两次考试中都没有得5分的有分的有17人，那么两次考试都得人，那么两次考试都得5分的有多少人？分的有多少人？求解求解方法一：文氏图填图法方法一：文氏图填图法第一次得第一次得5分学生：集合分学生：集合A第二次得第二次得5分学生：集合分学生：集合B全班学生：全集全班学生：全集E(26 x)+x+(21 x)+17=50 x=14.33AB26 x21 xx17文氏图文氏图求解求解方法二：使用包含排斥原理方法二：使用包含排斥原理.A、B和全集和全集E设定同上设定同上.那么有那么有

17、|E|=50,|A|=26,|B|=21根据包含排斥原理有根据包含排斥原理有代入得：代入得：3435练习练习44.判断以下命题的真假，并说明理由判断以下命题的真假，并说明理由.（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.36解题思路解题思路l先将等式化简或恒等变形先将等式化简或恒等变形.l查找集合运算的相关的算律，如果与算律相符，结果为真查找集合运算的相关的算律，如果与算律相符，结果为真.l注意以下两个重要的充要条件注意以下两个重要的充要条件 A B=AA B=A B=A BA

18、 B=BA B=A如果与条件相符，则命题为真如果与条件相符，则命题为真.l如果不符合算律，也不符合上述条件，可以用文氏图表示如果不符合算律，也不符合上述条件，可以用文氏图表示集合，看看命题是否成立集合，看看命题是否成立.如果成立，再给出证明如果成立，再给出证明.l试着举出反例，证明命题为假试着举出反例，证明命题为假.37解答解答解解(1)B=是是A B=A的充分条件，但不是必要条件的充分条件，但不是必要条件.当当B不空不空但但是与是与A不交时也有不交时也有A B=A.(2)这是这是DM律，命题为真律，命题为真.(3)不符合算律，反例如下：不符合算律，反例如下：A=1，A A=，但是，但是A.(

19、4)命题不为真命题不为真.A B=B的充分必要条件是的充分必要条件是B A，不是，不是A=E.(5)命题为真，因为命题为真，因为x 既是既是A 的元素，也是的元素，也是A 的子集的子集38练习练习55证明证明A B=A C A B=A CB=C解题思路解题思路l分析命题：含有分析命题：含有3 3个命题：个命题：A B=A C,A B=A C,B=Cl证明要求证明要求前提：命题前提：命题和和结论：命题结论：命题l证明方法：证明方法：恒等式代入恒等式代入反证法反证法利用已知等式通过运算得到新的等式利用已知等式通过运算得到新的等式39解答解答方法一：恒等变形法方法一：恒等变形法 B=B(B A)=B

20、(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，也与已知矛盾，也与已知矛盾.40解答解答方法三：利用已知等式通过运算得到新的等式方法三：利用已知等式通过运算得到新的等式.由已知等式由已知等式和和可以得到可以得到(A B)(A B)=(A

21、C)(A C)即即A B=A C从而有从而有 A(A B)=A(A C)根据结合律得根据结合律得(A A)B=(A A)C由于由于A A=,化简上式得化简上式得B=C.41练习练习66设设A,B为集合，试确定下列各式成立的充分必要条件：为集合，试确定下列各式成立的充分必要条件：(1)A B=B(2)A B=B A(3)A B=A B(4)A B=A42分析分析解题思路解题思路:求解集合等式成立的充分必要条件可能用到集合的算律、不求解集合等式成立的充分必要条件可能用到集合的算律、不同集合之间的包含关系、以及文氏图等同集合之间的包含关系、以及文氏图等.具体求解过程说明具体求解过程说明如下：如下：(

22、1)化简给定的集合等式化简给定的集合等式(2)求解方法如下：求解方法如下：l利用已知的算律或者充分必要条件进行判断利用已知的算律或者充分必要条件进行判断l先求必要条件，然后验证充分性先求必要条件，然后验证充分性l利用文氏图的直观性找出相关的条件，再利用集合论利用文氏图的直观性找出相关的条件，再利用集合论的证明方法加以验证的证明方法加以验证43解答解答解解(1)A B=B A=B=.求解过程如下：求解过程如下：由由A B=B得得(AB)B=B B化简得化简得B=.再将这个结果代入原来的等式得再将这个结果代入原来的等式得A=.从从而得到必要条件而得到必要条件A=B=.再验证充分性再验证充分性.如果

23、如果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.44解答解答(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=.