第六章第六章集合代数集合代数厦门大学数学科学学院金贤安6.16.1集合的基本概念集合的基本概念集合是不能精确定义的基本概念。直观的说,把一些事物汇集到一起组成一个整体,就叫做集合,而这些事物就是这个集合的元素或成员。例:教室内的桌椅、图书馆的藏书、全国的高等学校、自然数的全体、直线上的点、26个英文字母等等。元素元素集合内的对象称为元素集合通常用大写英文字母标记。例如,N代表自然数集合(包括0),Z代表整数集合,Q代表有理数集合,R代表实数集合,C代表复数集合。集合的表示集合的表示列举法:A={a,b,c,d}描述法:B={X∣P(x)}P(x)是谓词,概括集合中元素属性B={x∣x∈Z∧3<X≤6}即B={4,5,6}元素a属于集合A,记作a∈A。元素a不属于集合A,记作a∉A(元素无次序、不重复)集合的特征¾确定性¾互异性{1,2,3,2,4}={1,2,3,4}¾无序性{4,2,1,3}={1,2,3,4}A1{2,3}{{4}}23{4}4本书规定:1、集合元素都是集合。2、对于任何集合A,都有A∉A。根据规定1,元素和集合的隶属关系可以看作处于不同层次的集合之间的关系。下面我们考虑同一层次上的集合之间的关系。同一层次集合之间的关系同一层次集合之间的关系定义6.1设A,B是集合,如果B中的每个元素都是A中的元素,则称B是A的子集合,简称子集。这时也称B被A包含,或A包含B。记作B⊆A。若集合A不包含集合B,可表示成包含的符号化表示为B⊆AÙ∀x(x∈B→x∈A)对任何集合都有S,都有S⊆S。从属关系与包含关系从属关系与包含关系从属关系:集合S的元素a与集合S本身之间的关系,从属关系a∈S包含关系:集合A与集合B之间的关系包含关系A⊆B集合相等集合相等定义6.2设A,B为集合,如果A⊆B且B⊆A,则称A与B相等,记作A=B,符号化表示为A=BÙA⊆B∧B⊆A如果A和B不相等,则记作A≠B。实实例例判断A=B?1.2.{1,2,4}和{1,2,2,4}3.{1,2,4}和{1,4,2}4.{{1,2},4}和{1,4,2}5.{1,3,5,…}和{x|x是正奇数}真子集真子集定义6.3设A,B为集合,如果B⊆A且B≠A,则称B是A的真子集。记作B⊂A。真子集的符号化表示为:B⊂AÙA≠B∧B⊆A如果B不是A的真子集,记作B⊄A判断:{0,1}、{1,3}、{0,1,2}是{0,1,2}的真子集吗?空集空集定义6.4不含任何元素的集合叫做空集,记作∅。空集可以符号化表示为∅Ù{x|x≠x}空集是客观存在的,例如,是方程的实数解集,因为该方程没有实数解,所以A=∅。空集是一切集合的子集空集是一切集合的子集定理6.1空集是一切集合的子集.证明:对于任何集合A,有子集定义有∅⊆AÙ∀x(x∈∅→x∈A)右边的蕴涵式为真,所以∅⊆A也为真。空集是唯一的空集是唯一的推论空集是唯一的。证明假设存在空集∅1和∅2,∅1⊆∅2和∅2⊆∅1根据集合相等的定义得∅1=∅2确定下列命题是否为真确定下列命题是否为真(1),(3),(4)为真,(2)为假.幂集幂集定义6.5给定集合A,由集合A的所有子集为元素组成的集合,称为集合A的幂集,记作P(A)。设A={a,b,c},则P(A)={∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}若A是n元集,则P(A)有2n个元素。实实例例全全集集定义6.6在一个具体问题中,如果所涉及的集合都是某个集合的子集,则称这个集合为全集,记作E(或U)3.23.2集合的基本运算集合的基本运算定义6.7设A与B为集合,A与B的并集∪,交集∩,B对A的相对补集-分别定义如下:A∪B={x|(x∈A)∨(x∈B)}A∩B={X|(X∈A)∧(X∈B)}A-B={X|(X∈A)∧(X∉B)}当两个集合的交集是空集时,称它们是不交的。nn个集合的并集和交集个集合的并集和交集表示法表示法绝对补集绝对补集定义6.8设E为全集,A⊆E,则称A对E的相对补集为A的绝对补集,记作~A,即~A=E-A={x⎜x∈E∧x∉A}.~A={x⎜x∉A}.例:E={0,1,2,3},A={0,1,2},B={0,1,2,3},C=∅,则~A={3},~B=∅,~C=E.对称差对称差定义6.9A与B的对称差是A⊕B=(A∪B)-(A∩B)=(A-B)∪(B-A)例:A={0,1,2},B={2,3},则有A⊕B={0,1}∪{3}={0,1,3}或A⊕B={0,1,2,3}-{2}={0,1,3}文氏图(文氏图(JohnVennJohnVenn))ABEABEA∩B=∅A∪BABEABEA⊂BA∩B文氏图文氏图((johnVennjohnVenn))AEA-BA⊕B~AABEC(A∩B)-C定义6.10设R为集合,R的元素的元素构成的集合称为R的广义并,记作∪R,符号化表示为:∪R={x|∃z(z∈R∧x∈z)}例如:设A={{1,2,3},{1,3,4},{1,4,5}},B={{0}},C={1,{2,3}},则∪A={1,2,3,4,5},∪B={0}和∪C=1∪{2,3}。不难证明:若R={A1,A2,…,An},则∪R=A1∪A2∪…∪An特别强调:∪φ=φ定义6.11设R为非空集合,R的所有元素的公共元素构成的集合称为R的广义交,记作∩R,符号化表示为:∩R={x|∀z(z∈R→x∈z)}例如:设A={{1,2,3},{1,3,4},{1,4,5}},B={{0}},C={1,{2,3}}则∩A={1},∩B={0}和∩C=1∩{2,3}。不难证明:若R={A1,A2,…,An},则∩R=A1∩A2∩…∩An特别强调:φ不可以进行广义交运算。集合运算的优先级:称广义并、广义交、幂集和绝对补运算为一类运算,并、交、相对补和对称差为二类运算。z一类运算优先于二类运算。z一类运算由右向左顺序运算。z二类运算之间由括号决定先后顺序。6.36.3集合恒等式集合恒等式幂等律结合律算算律律交换律A∪B=B∪AA∩B=B∩A分配律A∩(B∪C)=(A∩B)∪(A∩C)A∪(B∩C)=(A∪B)∩(A∪C)算算律律同一律零律算算律律排中律矛盾律吸收律算算律律德·摩根律双重否定律恒等式证明的两种思路:(1)设A1、A2为集合公式,欲证A1=A2,只须证A1⊆A2∧A2⊆A1为真。也即证∀x∈A1⇒x∈A2和∀x∈A2⇒x∈A1或∀x有x∈A1Ùx∈A2(2)利用已知的恒等式代入通过演算证明。总体上还是多采用命题逻辑中的等值式,但在叙述上采用半形式化的方法。例6.6证明A-(B∪C)=(A-B)∩(A-C).证明:对于∀xx∈A-(B∪C)Ùx∈A∧x∉(B∪C)Ùx∈A∧⎤(x∈B∨x∈C)Ùx∈A∧(⎤x∈B∧⎤x∈C)Ùx∈A∧(x∉B∧x∉C)Ùx∈A∧x∉B∧x∉CÙ(x∈A∧x∉B)∧(x∈A∧x∉C)Ùx∈A-B∧x∈A-CÙx∈(A-B)∩(A-C)练1:证明A-B=A∩~B.证明:对于∀xx∈A-BÙx∈A∧x∉BÙx∈A∧x∈~BÙx∈A∩~B∴A-B=A∩~B注意:此公式提供了一种将相对补运算转换为交运算的重要方法!练2:证明A⊆BÙP(A)⊆P(B).证明:先证“⇒”对于∀xx∈P(A)⇒x⊆A⇒x⊆B⇒x∈P(B)∴P(A)⊆P(B)再证“=”对于∀xx∈A⇒{x}⊆A⇒{x}∈P(A)⇒{x}∈P(B)⇒{x}⊆B⇒x∈B∴A⊆B例6.8利用代入已知恒等式证明A∪(A∩B)=A.证明:A∪(A∩B)=(A∩E)∪(A∩B)=A∩(E∪B)=A∩E=A∴A∪(A∩B)=A练习:证明(A一B)∪B=A∪B证明(A—B)∪B=(A∩~B)∪B=(A∪B)∩(~B∪B)=(A∪B)∩E=A∪B集合运算性质集合运算性质例6.13已知A⊕B=A⊕C,证明B=C证明A⊕B=A⊕C所以A⊕(A⊕B)=A⊕(A⊕C),(A⊕A)⊕B=(A⊕A)⊕C,(结合律)∅⊕B=∅⊕C,所以B=C。6.46.4有限集合元素的计数有限集合元素的计数本节主要讲容斥原理。容斥原理是一种计数的方法,它在许多领域广泛的应用。4.1引入4.2容斥原理的一般形式4.3几个例子4.4三个练习4.14.1引入引入例有100名程序员,其中47名熟悉FORTRAN语言,35名熟悉PASCAl语言,23名熟悉这两种语言。问有多少人对这两种语言都不熟悉?解设A,B分别表示熟悉FORTRAN和PASCAL语言的程序员的集合100AB23473541题解题解|A∪B|=|A|+|B|-|A∩B|=47+35-23=59,|~(A∪B)|=100-59=4⒈所以,两种语言都不熟悉的有41人。设集合A是一有限集,我们用|A|表示集合A所含有的元素的个数。设S是一个有限集,A1和A2是S的子集,如下图所示。SA1A2A1A2A3S类似地我们有4.24.2容斥原理的一般形式容斥原理的一般形式定理:设S是一有限集,P1,P2,…,Pm是m个性质,令Ai表示S中所有具有性质Pi的元素构成的集合。则S中不具有性质P1,P2,…,Pm的元素的数目为思考:试用数学归纳法通过集合运算的方法给出定理1的一个证明。下面我们用组合方法证明定理1。证明只需证明,对S中的任何元素x,它对等式两边的计数的贡献都相同。(贡献是组合数学中常用的一个词。简单的说,若x∈A,则x对|A|的贡献为1,否则贡献就为0)现将S中的元素根据其恰好具有性质的个数进行分类,然后我们证明对每类中的任何一元素都证明它对等式两边的计数的贡献都相同。设x不具有性质P1,P2,…,Pm,那么x∉Ai,i=1,2,…m。则它对等式左边计数的贡献为1,对等式右边的计数的贡献也是1。根据牛顿二项式定理不难得到上面式子的结果是0.而由于x具有n个性质,它对等式左边的贡献也为0。4.34.3几个例子几个例子例1:求1-1000之间(包括1和1000)不能被5,也不能被6,还不能被8整除的整数有多少个?例2:某学校有12位教师,已知有8位老师可以教数学,6位可教物理,5位可教化学.其中有5位教师既教数学又教物理.4位老师兼教数学和化学,3位老师兼教物理和化学,3位老师兼教这三门课.1.求不教任何课的老师有几位?2.只教一门课的老师有几位?3.正好教其中两门课的老师有几位?例3:4个x,3个y,2个z的全排列中,求不出现xxxx,yyy,zz图象的排列。解:设出现xxxx的排列的集合记为A1,则|A1|=6!/(3!2!)=60;设出现yyy的排列的集合记为A2,则|A2|=7!/(4!2!)=105;设出现zz的排列的集合记为A3,则|A3|=8!/(4!3!)=280;全排列的个数为:9!/(4!3!2!)=1260;所以要求的排列数为1260-(60+105+280)+(12+20+30)-6=871.同理|A1∩A2|=4!/2!=12;|A1∩A3|=5!/3!=20;|A2∩A3|=6!/4!=30;|A1∩A2∩A3|=3!=6;4.44.4三个练习三个练习练习1:求由a,b,c,d构成的n位符号串中,a,b,c,d都至少出现一次的符号串的数目。练习2:求a,b,c,d,e,f六个字母的全排列中不允许出现ace,也不允许出现df图象的排列数。练习3:设某班有8位学生排成一队出去散步,第二天再列队时,同学们都不希望他前面同学与前一天的相同,问有多少种排法?