第六章集合代数精选文档.ppt

《第六章集合代数精选文档.ppt》由会员分享，可在线阅读，更多相关《第六章集合代数精选文档.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章集合代数第六章集合代数本讲稿第一页，共四十五页 6.1 集合的基本概念方程方程x2-1=0的实数解集合的实数解集合,1和和-1是该集合的元素是该集合的元素;26个英文字母的集合个英文字母的集合,a,b,z是该集合的元素是该集合的元素;坐标平面上所有点的集合坐标平面上所有点的集合;,是该集合的元素是该集合的元素;常用的集合名称:集合(Set)是一些个体汇集在一起所组成整体.通常把整体中的个体称为集合的元素或成员.例如:集合是不能精确定义的基本概念。本讲稿第二页，共四十五页集合有三种表示方法:列元素法、谓词表示法和图示法.列元素法列元素法:列出集合中的所有元素列出集合中的所有元素,各元素之间

2、用逗号隔开各元素之间用逗号隔开,并把它们并把它们用花括号括起来用花括号括起来.例如例如 A=a,b,c,z Z=0,1,2,谓词表示法谓词表示法:用谓词来概括集合中元素的属性用谓词来概括集合中元素的属性.例如例如:B=x|x R 且且 x2-1=0 集合集合B表示方程表示方程x2-1=0的实数解集的实数解集.许多集合可用两种方法来表示许多集合可用两种方法来表示,如如:B=-1,1.有些集合不能用列元素法表示有些集合不能用列元素法表示,如如:实数集合实数集合,不能列举出所不能列举出所有集合中的所有元素有集合中的所有元素.图示法图示法:用一个圆来表示用一个圆来表示,圆中的点表示集合中的元素圆中的点

3、表示集合中的元素.6.1 集合的基本概念本讲稿第三页，共四十五页集合的元素是彼此不同的.u若同一个元素在集合中多次出现若同一个元素在集合中多次出现,则只认为其是一个元素则只认为其是一个元素;如如:1,1,2,2,3 =1,2,3 u集合的元素是无序的集合的元素是无序的,如如:3,1,2 =1,2,3 本书规定:集合的元素都是集合.6.1 集合的基本概念本讲稿第四页，共四十五页元素(Element)和集合之间的隶属关系:“属于”或“不属于”.“属于”关系记作,“不属于”记作.例如:A=a,b,c,d,d .a A,b,c A,dA,d A,bA,d A.b和 d 是A元素的元素.为了体系的严谨性

4、,规定:对任何集合A,都有:AA.A=a,b,c,d,d 的树形图表示.a b,c Ad d bc d d 6.1 集合的基本概念本讲稿第五页，共四十五页如果B不被A包含,则记作B A.包含的符号化表示为B A x(xB xA)例如:N Z Q R C,但,Z N.显然,对任何集合A,都有:A A.包含关系表示集合之间的关系;隶属关系表示元素和集合之间的关系,但也可表示某些集合之间关系.如:a a,a ,a a,a 定义6.1 设A和B为集合,若B中的每个元素都是A的元素,则称B是A的子集合,简称子集(Subset),也可称B被A包含,或A包含B,记作B A.AB 6.1 集合的基本概念本讲稿

5、第六页，共四十五页定义6.2 设A和B为集合,如果A B且B A,则称A与B相等,记作:A=B.若A与B不相等,则记作:A B.相等的符号化表示为 A=B ABBA x(xA xB)x(xB xA)定义6.3 设A和B为集合,如果B A且B A,则称B是A的真子集(Proper Subset),记作B A.若B不是A的真子集,则记为:B A.真子集的符号化表示为:B A B AB A例如:N Z Q R C,但,NN.6.1 集合的基本概念本讲稿第七页，共四十五页定义6.4 不含任何元素的集合叫做空集,记作:.空集可以符号化表示为:=x|x x.例如:x|xRx2+1=0 是方程x2+1=0的

6、实数解集,因为该方程无实数解,所以,其解集是空集.定理6.1 空集是一切集合的子集.任给一个集合A,由子集的定义可知:A x(x xA)由于蕴涵式(x xA)的前件为假而使其成为真命题,所以,A.6.1 集合的基本概念证假设:存在空集1和2.由定理6.1可知:1 2,2 1.由集合相等的定义可知:1=2.推论 空集是惟一的.证本讲稿第八页，共四十五页例6.1 A=1,2,3,将A的子集分类:假设有一个含有n个元素的集合A（n元集）,若集合A1是其子集且|A1|=m,则称子集A1为集合A的m元子集.对任给一个n元集合A,如何求出它的全部子集?0元子集,即空集,只有一个:;1元子集,即单元集:1,

7、2,3;2元子集:1,2,1,3,2,3;3元子集:1,2,3.由上面的例子,我们不难归纳出:对n元集合A,有:定义 集合A中元素的个数n为集合的势(Cardinality),记为|A|.6.1 集合的基本概念本讲稿第九页，共四十五页全集是有相对性的,不同的问题有不同的全集,即使是同一个问题也可以取不同的全集.例如:在研究平面上直线的相互关系时,可把整个平面上所有点的集合看作全集,也可把整个空间上所有点的集合看作全集.一般地说,全集取得小一些,问题的描述和处理会简单些.幂集的符号化表示为幂集的符号化表示为:P(A)=x|x A.对于集合对于集合A=1,2,3,有有:P(A)=,1,2,3,1,

8、2,1,3,2,3,1,2,3.不难看出不难看出,若若A是是n元集元集,则则P(A)有有2n个元素个元素.定义定义6.6 在某具体问题中在某具体问题中,若所涉及的集合都是某个集合的子集若所涉及的集合都是某个集合的子集,则称该集合为全集则称该集合为全集(Universal Set),记作记作E.定义6.5 设A为集合,把A的全体子集构成的集合叫做A的幂集(Power Set),记作P(A),PA,2A.6.1 集合的基本概念本讲稿第十页，共四十五页集合的基本运算有并(Union),交(Intersection)和相对补(Relative Complement).定义6.7 设A和B为集合,A与B

9、的并集AB,交集AB,B对A的相对补集A-B分别定义如下:AB=x|x Ax B AB=x|x Ax B A-B=x|x Ax B 由定义可知由定义可知:AB是由是由A或或B的元素构成的元素构成,AB由由A和和B的公共元素构成的公共元素构成,A-B由属于由属于A,但不属于但不属于B的元素构成的元素构成.例如例如:A=a,b,c,B=a,C=b,d,则则:AB=a,b,c AB=a A-B=b,c B-A=,BC=6.2 集合的运算本讲稿第十一页，共四十五页n个集合的并和交:无穷多个集合的并和交:i=1.Ai=A1A2i=1.Ai=A1A2i=1.nAi=A1A2An=x|xA1xAn)i=1.

10、nAi=A1A2An=x|xA1xAn)6.2 集合的运算本讲稿第十二页，共四十五页例如 A=a,b,c,B=b,d,则:AB=a,c,d 对称差运算的另一种定义是A B=(AB)-(BA)在给定全集E以后,A E,A的绝对补集A定义如下:集合的对称差集(Symmetric Difference)和绝对补集(Absolute Complement).定义6.9 A=E A=x|xEx A因为 E是全集,xE是真命题,所以,A可以定义为A=x|x A.例如:E=a,b,c,d,A=a,b,c,则,A=d.定义6.8 设A和B为集合,A与B的对称差集AB定义为:A B=(A-B)(B-A)6.2

11、集合的运算本讲稿第十三页，共四十五页 6.2 集合的运算 以上定义的并和交运算称为初级并和初以上定义的并和交运算称为初级并和初级交级交.下面考虑推广的并和交运算下面考虑推广的并和交运算,即广义并和即广义并和广义交广义交.本讲稿第十四页，共四十五页定义定义6.10 设设A为集合为集合,A的的元素的元素元素的元素构成的集合称为构成的集合称为A的广义并的广义并,记为记为A.符号化表示为符号化表示为:A=x|z(z Ax z)根据广义并的定义不难得到:若A=A1,A2,An,则A=A1A2An类似地可以定义集合的广义交.例例6.4 设设A=a,b,c,a,c,d,a,e,f B=a C=a,c,d 则

12、则A=a,b,c,d,e,f B=a C=a c,d =6.2 集合的运算本讲稿第十五页，共四十五页例例6.4:A=a,b,c,a,c,d,a,e,f B=a C=a,c,d 有有:A=a,B=a,C=a c,d 定义定义6.11 设设A为非空集合为非空集合,A的的所有元素所有元素的公共元素所构成的集的公共元素所构成的集合称为合称为A的广义交的广义交,记为记为A.符号化表示为符号化表示为A=x|z(z A x z)n定义6.11中,特别强调A是非空集合;n对于空集可以进行广义并,即:=;n空集不可进行广义交,因为不是集合;在集合论中是没有意义的;n若A=A1,A2,An,则A=A1A2An.6

13、.2 集合的运算本讲稿第十六页，共四十五页称称广义并广义并,广义交广义交,幂集幂集,绝对补绝对补运算为一类运算运算为一类运算,并并,交交,相对补和对称差相对补和对称差运算为二类运算运算为二类运算.下面的集合公式都是合理的公式下面的集合公式都是合理的公式:A-B,P(A),P(A)B,(AB)一类运算优先于二类运算一类运算优先于二类运算一类运算之间一类运算之间由右向左由右向左顺序进行顺序进行二类运算之间由二类运算之间由括号括号决定先后顺序决定先后顺序 6.2 集合的运算本讲稿第十七页，共四十五页例例6.5 设设 A=a,a,b ,计算计算A,A,A,A.解解A=a,b A=a A=ab A=aA

14、=abA=a 6.2 集合的运算本讲稿第十八页，共四十五页例例6.5（续）（续）设设 A=a,a,b ,计算计算 A(A-A)（练习练习）.解解A=a,b A=a A=abA=aA=abA=aA(A-A)=(ab)(ab)-a)=(ab)(b-a)=b所以所以 A=ab,A=a,A(A-A)=b.6.2 集合的运算本讲稿第十九页，共四十五页课后作业课后作业(1)习题六习题六 第第5,6,8,9,11,14题题 （4小题（含）以上的题做奇数小题；小题（含）以上的题做奇数小题；否则全做。否则全做。）（第（第96-98页）页）.本讲稿第二十页，共四十五页EEBEB文氏图(Venn Diagrams)

15、EABAB=AAB=AEABA-BEABABEABABEAAAA BB(AB)-CAC 6.3 有穷集的计数本讲稿第二十一页，共四十五页有穷集的计数n使用文氏图可以很方便地解决使用文氏图可以很方便地解决有穷集有穷集的计数问题。的计数问题。n首先根据已知条件把对应的文氏图画出来首先根据已知条件把对应的文氏图画出来 一般地说，每一条性质决定一个集合。有多少条性质，就有一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相多少个集合。如果没有特殊说明，任何两个集合都画成相交的。交的。n然后将已知集合的元素数填入表示该集合的区域内然后将已知集合的元素数填

16、入表示该集合的区域内 通常从通常从n个集合的交集填起，根据计算的结果将数字逐步个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以填入所有的空白区域。如果交集的数字是未知的，可以设为设为x。根据题目中的条件，列出一次方程或方程组，就。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。可以求得所需要的结果。本讲稿第二十二页，共四十五页例例6.2 对对24名人员掌握外语情况的调查名人员掌握外语情况的调查.其统计结果如下其统计结果如下:解解 令令A,B,C和和D分别表示会英、法、德、日语的人的集合分别表示会英、法、德、日语的人的集合.设同时会三种语

17、言的有设同时会三种语言的有x人人,只会英、法或德语一种语言的分别为只会英、法或德语一种语言的分别为y1,y2和和y3.画出的图如右图画出的图如右图.列出下面方程组列出下面方程组:y1+2(4-x)+x+2=13y2+2(4-x)+x=9y3+2(4-x)+x=10y1+y2+y3+3(4-x)+x=19解得解得:x=1,y1=4,y2=3,y3=3.y224-xy1x4-x4-xy35-2DACBu会英、日、德、法分别为会英、日、德、法分别为:13,5,10和和9人人;u同时会英语和日语的有同时会英语和日语的有2人人;u会英、德和法语中任两种语言的都是会英、德和法语中任两种语言的都是4人人.已

18、知会日语的人既不懂法语也不懂德语已知会日语的人既不懂法语也不懂德语,分别求只会一种语分别求只会一种语言言(英、德、法、日英、德、法、日)的人数和会三种语言的人数的人数和会三种语言的人数.6.3 有穷集的计数本讲稿第二十三页，共四十五页41BAC例例6.3 求求1到到1000之间之间(包含包含1和和1000在内在内),既不能被既不能被5和和6,也不能也不能被被8整除的数有多少个整除的数有多少个.解解 设设S=x|x Z1 x 1000 A=x|x Sx可被可被5整除整除 B=x|x Sx可被可被6整除整除 C=x|x Sx可被可被8整除整除|A|=int(1000/5)=200|B|=int(1

19、000/6)=166|C|=int(1000/8)=125|AB|=int(1000/lcm(5,6)=33|AC|=int(1000/lcm(5,8)=25|BC|=int(1000/lcm(6,8)=41|ABC|=int(1000/lcm(5,6,8)=81000-(200+100+33+67)=600171502581333320016612516733672510059+ABC 6.3 有穷集的计数本讲稿第二十四页，共四十五页定理定理6.2(包含排斥原理包含排斥原理)设设S为有穷集为有穷集,P1,P2,Pm是是m个个性质性质.S中的任何元素中的任何元素x或者具有性质或者具有性质Pi,

20、或者不具有性或者不具有性质质Pi(i=1.m),两种情况必居其一两种情况必居其一.令令Ai表示表示S中具有性质中具有性质Pi的元素构成的子集的元素构成的子集,则则S中不具有性中不具有性质质P1,P2,Pm的元素数为的元素数为:6.3 有穷集的计数本讲稿第二十五页，共四十五页推论推论 S中至少具有一条性质的元素数为中至少具有一条性质的元素数为根据包含排斥原理根据包含排斥原理,例例6.3中所求的元素数为中所求的元素数为:|ABC|=|S|-(|A|+|B|+|C|)+(|AB|+|AC|+|BC|)-|ABC|=1000-(200+166+125)+(33+25+41)-8=600 6.3 有穷集

21、的计数本讲稿第二十六页，共四十五页欧拉函数欧拉函数n欧拉函数欧拉函数是数论中的一个重要函数是数论中的一个重要函数,设设n n是正整数是正整数,(n)(n)表示表示0,1,n-10,1,n-1中与中与n n互素的数的个数互素的数的个数.例例如如(12)=4,(12)=4,因为与因为与1212互素的数有互素的数有1,5,7,11.1,5,7,11.这里认这里认为为(1)=1.(1)=1.利用利用包含排斥原理包含排斥原理给出欧拉函数的计给出欧拉函数的计算公式算公式.n分析分析 (1)因式分解！因式分解！(2)包含包含排斥原理。排斥原理。本讲稿第二十七页，共四十五页欧拉函数（续）欧拉函数（续）n(1)

22、因式分解因式分解 给定正整数给定正整数n,n的因式分解式为的因式分解式为,令令 则有则有n(2)包含排斥原理包含排斥原理 首先计算首先计算 由包含排斥原理得由包含排斥原理得 本讲稿第二十八页，共四十五页幂等率幂等率 Idempotent Laws AA=A(6.1)AA=A(6.2)结合律结合律 Associative Laws (AB)C=A(BC)(6.3)(AB)C=A(BC)(6.4)交换律交换律 Commutative Laws AB=BA(6.5)AB=BA(6.6)分配律分配律 Distributive Laws A(BC)=(AB)(AC)(6.7)A(BC)=(AB)(AC)

23、(6.8)6.4 集合恒等式本讲稿第二十九页，共四十五页同一率同一率 Identity Laws A =A(6.9)AE=A(6.10)零率零率 more Identity laws AE=E(6.11)A =(6.12)排中率排中率 Complementation laws AA=E(6.13)AA=(6.14)6.4 集合恒等式本讲稿第三十页，共四十五页吸收率吸收率 Absorption laws A(AB)=A(6.15)A(AB)=A(6.16)德摩根律德摩根律 De Morgan laws A-(BC)=(A-B)(A-C)(6.17)A-(BC)=(A-B)(A-C)(6.18)(

24、BC)=BC(6.19)(BC)=BC(6.20)=E(6.21)E=(6.22)双重否定率双重否定率 Double Complementation (A)=A(6.23)6.4 集合恒等式本讲稿第三十一页，共四十五页6.4 集合恒等式例例6.6 证明证明:A-(BC)=(A-B)(A-C)(式式6.17)n分析（证明思路）分析（证明思路）（1）定义（集合的基本概念）；）定义（集合的基本概念）；（2）命题逻辑中的等值演算命题逻辑中的等值演算。或者或者（3）根据前面的定理）根据前面的定理(集合恒等式集合恒等式)直接推导。直接推导。本讲稿第三十二页，共四十五页例6.8 证明:A-(BC)=(A-B

25、)(A-C)(式6.17)证证 对任意对任意x,x A-(BC)xAx BC xA(xBxC)xA(xBxC)xAx Bx C(xAx B)(xAx C)xA-BxA-C x(A-B)(A-C)所以所以,A-(BC)=(A-B)(A-C)6.4 集合恒等式本讲稿第三十三页，共四十五页例例6.9 证明式证明式6.10,即即:AE=A.证证 对任意对任意x,x AE x Ax E x A(因为因为x E是恒真命题是恒真命题),所以所以,AE=A.以上证明的基本思想是:设P和Q为集合公式,欲证:P=Q,即证 P QQ P为真.n要证对于任意的x有:xP xQ和xQ xP成立.n对于某些恒等式,可将这

26、两个方向的推理合到一起,就是xP xQ 6.4 集合恒等式本讲稿第三十四页，共四十五页证证 A(AB)=(AE)(AB)(6.10)=A(EB)(6.8)=A(BE)(6.5)=AE(6.11)=A(6.10)例例6.10 假设已知等式假设已知等式6.1-6.14,试证等式试证等式6.15:A(AB)=A.6.4 集合恒等式本讲稿第三十五页，共四十五页 6.4 集合恒等式n（练习练习）证明证明:A-(BC)=(A-B)(A-C)(式式6.18)本讲稿第三十六页，共四十五页还有一些关于集合运算性质的重要结果还有一些关于集合运算性质的重要结果.AB A,AB B(6.24)A AB,B AB(6.

27、25)A-B A(6.26)A-B=AB(6.27)AB=B A B AB=A A-B=(6.28)A B=B A(6.29)(A B)C=A (B C)(6.30)A =A(6.31)A A=(6.32)A B=A C B=C(6.33)6.4 集合恒等式本讲稿第三十七页，共四十五页例例6.11 证明等式证明等式6.27,即即A-B=AB.证证 对于任意的对于任意的x,xA-B xAxB xAxB xAB所以所以,A-B=AB.等式等式6.27把相对补运算转换成交运算把相对补运算转换成交运算.6.4 集合恒等式本讲稿第三十八页，共四十五页例例6.12 证明证明:(A-B)B=AB.证证(A-

28、B)B=(AB)B=(AB)(BB)=(AB)E=AB 6.4 集合恒等式本讲稿第三十九页，共四十五页例例6.13 证明命题证明命题6.28是真命题是真命题:AB=B A B AB=A A-B=.证证 1).证证 AB=B A B 对于任意的对于任意的x,x A x Ax B x AB x B(因为因为AB=B)所以所以,A B.2).证证 A B AB=A 显然有显然有AB A,下面证下面证:A AB.对于任意的对于任意的x,x A x Ax A x Ax B(因为因为A B)x AB 由集合相等的定义有由集合相等的定义有:AB=A.3).证证:AB=A A-B=A-B=AB=(AB)B(因

29、为因为AB=A)=A(BB)=A =4).证证:A-B=AB=B 由例由例6.12及及A-B=,有有:AB=B(A-B)=B =B 6.4 集合恒等式本讲稿第四十页，共四十五页 6.4 集合恒等式AB=B A B AB=A A-B=(6.28)n上式给出了上式给出了A B 的四种等价形式的四种等价形式n用途用途（1）证明两个集合之间的包含关系；）证明两个集合之间的包含关系；（2）用于集合公式的化简。）用于集合公式的化简。本讲稿第四十一页，共四十五页例例6.14 化简化简(ABC)(AB)-(A(B-C)A)解解 因为因为AB ABC,A A(B-C),由式由式6.28:(ABC)(AB)-(A

30、(B-C)A)=(AB)-A=B-A式式6.296.33是关于对称差运算的算律是关于对称差运算的算律;前四条可通过对称差的定义加以证明前四条可通过对称差的定义加以证明;最后一条叫做消去律最后一条叫做消去律.6.4 集合恒等式本讲稿第四十二页，共四十五页证证 已知已知A B=A C,所以所以,有有:A(A B)=A(A C)(6.30)(A A)B=(A A)C(6.32)B=C(6.29)B=C(6.31)例例6.15 已知已知A B=A C,证明证明:B=C.6.4 集合恒等式本讲稿第四十三页，共四十五页课后作业课后作业(1)习题六习题六 第第19,21,28,32,45题题（4小题（含）以上的题做奇数小题；否小题（含）以上的题做奇数小题；否则全做。则全做。）（第（第99-101页）页）.本讲稿第四十四页，共四十五页谢谢 谢谢!本讲稿第四十五页，共四十五页