第六章集合代数

6.1集合的基本概念方程x2-1=0的实数解集合,1和-1是该集合的元素;26个英文字母的集合,a,b,…,z是该集合的元素;坐标平面上所有点的集合;0,0,0,1,1,1是该集合的元素;常用的集合名称:N:自然数集合(本课程中认为0也是自然数)Z:整数集合Q:有理数集合R:实数集合C:复数集合集合(Set)是一些个体汇集在一起所组成整体.通常把整体中的个体称为集合的元素或成员.例如:集合是不能精确定义的基本概念。集合有三种表示方法:列元素法、谓词表示法和图示法.列元素法:列出集合中的所有元素,各元素之间用逗号隔开,并把它们用花括号括起来.例如A={a,b,c,…,z}Z={0,±1,±2,…}谓词表示法:用谓词来概括集合中元素的属性.例如:B={x|xR且x2-1=0}集合B表示方程x2-1=0的实数解集.许多集合可用两种方法来表示,如:B={-1,1}.有些集合不能用列元素法表示,如:实数集合,不能列举出所有集合中的所有元素.图示法:用一个圆来表示,圆中的点表示集合中的元素.6.1集合的基本概念集合的元素是彼此不同的.若同一个元素在集合中多次出现,则只认为其是一个元素;如:{1,1,2,2,3}={1,2,3}集合的元素是无序的,如:{3,1,2}={1,2,3}本书规定:集合的元素都是集合.6.1集合的基本概念元素(Element)和集合之间的隶属关系:“属于”或“不属于”.“属于”关系记作,“不属于”记作.例如:A={a,{b,c},d,{{d}}}.aA,{b,c}A,dA,{{d}}A,bA,{d}A.b和{d}是A元素的元素.为了体系的严谨性,规定:对任何集合A,都有:AA.A={a,{b,c},d,{{d}}}的树形图表示.a{b,c}Ad{{d}}bc{d}d6.1集合的基本概念如果B不被A包含,则记作BA.包含的符号化表示为BAx(xBxA)例如: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.AB6.1集合的基本概念：等值的：蕴涵式定义6.2设A和B为集合,如果AB且BA,则称A与B相等,记作:A=B.若A与B不相等,则记作:AB.相等的符号化表示为A=BAB∧BAx(xAxB)∧x(xBxA)定义6.3设A和B为集合,如果BA且BA,则称B是A的真子集(ProperSubset),记作BA.若B不是A的真子集,则记为:BA.真子集的符号化表示为:BABA∧BA例如:NZQRC,但,NN.6.1集合的基本概念定义6.4不含任何元素的集合叫做空集,记作:.空集可以符号化表示为:={x|xx}.例如:{x|xR∧x2+1=0}是方程x2+1=0的实数解集,因为该方程无实数解,所以,其解集是空集.定理6.1空集是一切集合的子集.任给一个集合A,由子集的定义可知:Ax(xxA)由于蕴涵式(xxA)的前件为假而使其成为真命题,所以,A.6.1集合的基本概念证假设:存在空集1和2.由定理6.1可知:12,21.由集合相等的定义可知:1=2.推论空集是惟一的.证例6.1A={1,2,3},将A的子集分类:假设有一个含有n个元素的集合A（n元集）,若集合A1是其子集且|A1|=m,则称子集A1为集合A的m元子集.对任给一个n元集合A,如何求出它的全部子集?0元子集,即空集,只有一个:;1元子集,即单元集:{1},{2},{3};2元子集:{1,2},{1,3},{2,3};3元子集:{1,2,3}.由上面的例子,我们不难归纳出:对n元集合A,有:0元子集有Cn0个1元子集有Cn1个…m元子集有Cnm个…n元子集有Cnn个子集总数为Cn0+Cn1+…+Cnn=2n个定义集合A中元素的个数n为集合的势(Cardinality),记为|A|.6.1集合的基本概念全集是有相对性的,不同的问题有不同的全集,即使是同一个问题也可以取不同的全集.例如:在研究平面上直线的相互关系时,可把整个平面上所有点的集合看作全集,也可把整个空间上所有点的集合看作全集.一般地说,全集取得小一些,问题的描述和处理会简单些.幂集的符号化表示为:P(A)={x|xA}.对于集合A={1,2,3},有:P(A)={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.不难看出,若A是n元集,则P(A)有2n个元素.定义6.6在某具体问题中,若所涉及的集合都是某个集合的子集,则称该集合为全集(UniversalSet),记作E.定义6.5设A为集合,把A的全体子集构成的集合叫做A的幂集(PowerSet),记作P(A),PA,2A.6.1集合的基本概念集合的基本运算有并(Union),交(Intersection)和相对补(RelativeComplement).定义6.7设A和B为集合,A与B的并集A∪B,交集A∩B,B对A的相对补集A-B分别定义如下:A∪B={x|xA∨xB}A∩B={x|xA∧xB}A-B={x|xA∧xB}由定义可知:A∪B是由A或B的元素构成,A∩B由A和B的公共元素构成,A-B由属于A,但不属于B的元素构成.例如:A={a,b,c},B={a},C={b,d},则:A∪B={a,b,c}A∩B={a}A-B={b,c}B-A=,B∩C=若两个集合的交集为,则称这两个集合是不相交的.如:B和C是不相交的.6.2集合的运算n个集合的并和交:无穷多个集合的并和交:∪i=1..∞Ai=A1∪A2∪…∩i=1..∞Ai=A1∩A2∩…∪i=1..nAi=A1∪A2∪…∪An={x|xA1∨…∨xAn)∩i=1..nAi=A1∩A2∩…∩An={x|xA1∧…∧xAn)6.2集合的运算例如A={a,b,c},B={b,d},则:AB={a,c,d}对称差运算的另一种定义是AB=(A∪B)-(B∩A)在给定全集E以后,AE,A的绝对补集~A定义如下:集合的对称差集(SymmetricDifference)和绝对补集(AbsoluteComplement).定义6.9~A=E–A={x|xE∧xA}因为E是全集,xE是真命题,所以,~A可以定义为~A={x|xA}.例如:E={a,b,c,d},A={a,b,c},则,~A={d}.定义6.8设A和B为集合,A与B的对称差集AB定义为:AB=(A-B)∪(B-A)6.2集合的运算6.2集合的运算以上定义的并和交运算称为初级并和初级交.下面考虑推广的并和交运算,即广义并和广义交.定义6.10设A为集合,A的元素的元素构成的集合称为A的广义并,记为∪A.符号化表示为:∪A={x|z(zA∧xz)}根据广义并的定义不难得到:若A={A1,A2,…,An},则∪A=A1∪A2∪…∪An类似地可以定义集合的广义交.例6.4设A={{a,b,c},{a,c,d},{a,e,f}}B={{a}}C={a,{c,d}}则∪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)}定义6.11中,特别强调A是非空集合;对于空集可以进行广义并,即:∪=;空集不可进行广义交,因为∩不是集合;在集合论中是没有意义的;若A={A1,A2,…,An},则∩A=A1∩A2∩…∩An.6.2集合的运算称广义并,广义交,幂集,绝对补运算为一类运算,并,交,相对补和对称差运算为二类运算.下面的集合公式都是合理的公式:∩A-∪B,∪P(A),~P(A)∪∪B,~(A∪B)一类运算优先于二类运算一类运算之间由右向左顺序进行二类运算之间由括号决定先后顺序6.2集合的运算例6.5设A={{a},{a,b}},计算∪∪A,∩∩A,∪∩A,∩∪A.解∪A={a,b}∩A={a}∪∪A=a∪b∩∩A=a∩∪A=a∩b∪∩A=a6.2集合的运算例6.5（续）设A={{a},{a,b}},计算∩∪A∪(∪∪A-∪∩A)（练习）.解∪A={a,b}∩A={a}∪∪A=a∪b∩∩A=a∩∪A=a∩b∪∩A=a∩∪A∪(∪∪A-∪∩A)=(a∩b)∪((a∪b)-a)=(a∩b)∪(b-a)=b所以∪∪A=a∪b,∩∩A=a,∩∪A∪(∪∪A-∪∩A)=b.6.2集合的运算课后作业(1)习题六第5,6,8,9,11,14题（4小题（含）以上的题做奇数小题；否则全做。）（第96-98页）.EEBEB文氏图(VennDiagrams)EABA∩B=AA∩B=AEABA-BEABA∪BEABA∩BEA~AAABB(A∩B)-CAC6.3有穷集的计数有穷集的计数使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的。然后将已知集合的元素数填入表示该集合的区域内通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。例6.2对24名人员掌握外语情况的调查.其统计结果如下:解令A,B,C和D分别表示会英、法、德、日语的人的集合.设同时会三种语言的有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-2DACB会英、日、德、法分别为:13,5,10和9人;同时会英语和日语的有2人;会英、德和法语中任两种语言的都是4人.已知会日语的人既不懂法语也不懂德语,分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数.6.3有穷集的计数41BAC例6.3求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整除}|A|=int(1000/5)=200|B|=int(1000/6)=166|C|=int(1000/8)=125|A∩B|=int(1000/lcm(5,6))=33|A∩C|=int(1000/lcm(5,8))=25|B∩C|=int(1000/lcm(6,8))=41|A∩B∩C|=int(1000/lcm(5,6,8))=81000-(200+100+33+67)=600171502581333320016612516733672510059+A∩B∩C6.3有穷集的计数定理6.2(包含排斥原理)设S为有穷集,P1,P2,…,Pm是m个性质.S中的任何元素x或者具有性质Pi,或者不具有性质Pi(i=1..m),两种情况必居其一.令Ai表示S中具有性质Pi的元素构成的子集,则S中不具有性质P1,P2,…,Pm的元素数为:||21mAAA6.3有穷集的计数||)1(||||||||21111mmmkjik