集合运算论文开题报告

关于集合运算的应用收稿日期:2008-01-08作者简介:邓凤茹(1969-),讲师,河北廊坊人,从事基础教育教学工作。1简介集合论的运算集合论是最近发现的数学理论,在1871年集合论的创始人德国大数学家康.托尔给出集合的第一定义,使“集合”成为数学基本概念之一,它也是整个数学大厦的基础,虽然集合论很“年轻”,但是它能够论证数学各个分支的统一性,例如代数式和几何式效果是相等的。下面简单介绍集合的概念和运算。集合的概念集合是指具有某种特定性质的事物的总体。组成这个集合的事物称为集合的元素;根据集合元素的个数集合分为有限集和无限集,同一性质的集合可以定义运算,集合的运算有三种:并、交、差。集合的运算设A、B是两个集合,由所有属于A或者属于B的元素组成的集合,称为A与B的并集,简称并(或和),记作A∪B,即A∪B={x|x∈A或x∈B}由所有既属于A又属于B的元素组成的集合,称为A与B的交集,简称交(或积),记作A∩B,即A∩B={x|x∈A且x∈B}由所有既属于A而不属于B的元素组成的集合,称为A与B的差集,简称差,记作A-B,即A-B={x|x∈A且x|B}以上定义可推广到无限多个集合的运算2在概率统计学中的应用1)概率的定义设(Ω,F)是可测空间,对每一个集合A∈F,有一实数与之对应,记为P(A),如果它满足下面三个条件:(1)对每一个集合A∈F,有0≤P(A)≤1;(2)对必然事件Ω,有P(Ω)=1;(3)对任意集合Ai∈F(i=1,2,…n),Ai∩Aj=Φ(i≠j),恒有P(∪ni=1A i)=6ni=1p(A i)(1)则称实值函数P为(Ω,F)上的概率,P(A)就称为事件A的概率2)当A i∩A j≠Φ(i≠j),(i,j=1,2…,n)时,公式一变成一般式即P(∪ni=1A i)=6ni=1p(A i)-6ni=16j>iP(A i∩A j)+6ni=16j>i6k>jP(A i∩A j∩A k)-…+(-1)n-1P(A 1∩A 2∩…∩A n)(2)由De Morgan定理(对偶律或摩根律)可得下述概率公式:P(∩ni=1A i)=P(∪ni=1A i)=P(Ω-∪ni=1A i)即P(∩ni=1A i)=1-[6ni=1p(A i)-6ni=16j>iP(A i∩A j)+6ni=16j>i6k>jP(A i∩A j∩A k)-…+(-1)n-1P(A 1∩A 2∩…∩A n)](3)注意:三个公式的适用条件当n=2时,为最简单的形式即P(A∪B)=P(A)+P(B)-P(A∩B)当A∩B=Φ时,P(A∪B)=P(A)+P(B)(可加性)3在组合数学中的应用1)集合中元素个数:设A为有限集合,A中元素个数为r,则称r为A的元素个数,记作:|A|=r2)推导一般公式|A∪B|=|A|+|B|-|A∩B|(当A∩B=Φ时,|A∪B|=|A|+|B|)|A∪B∪C|=|A|+|B|+|C|-[|A∩B|+|A∩C|+|B∩C|]+|A∩B∩C|推广到一般形式:∪ni=1A i=6ni=1|A i|-6ni=16j>i|A i∩A j|+6ni=16j>i6k>j|A i∩A j∩A k|-…+(-1)n-1|A 1∩A2∩…∩An|(4)由De Morgan定理(对偶律或摩根律)可得下述公式∩ni=1A i=∪ni=1A i=I-∪ni=1A i(I为全集,|I|=m)即∩ni=1A i=m-6ni=1|A i|-6ni=16j>i|A i∩A j|+6ni=16j>i6k>j|A i∩A j∩A k|-…+(-1)n-1|A 1∩A 2∩…∩A n|(5)公式(4)与公式(5)就是容斥原理3)推广容斥原理(1)|A∩B|=|A-(A∩B)|=|A|-|A∩B|同理|B∩A|=|B-(A∩B)|=|B|-|A∩B|即|A∩B|+|B∩A|=|A|+|B|-2|A∩B|(2)|A∩B∩C|=|A∩(B∪C)|=|A∩[I-(B∩C)]|=|A-[(A∩B)U(A∩C)]|=|A|-(|A∩B|+|A∩C|)+|A∩B∩C|同理可得:|A∩B∩C|=|B|-(|A∩B|+|B∩C|)+|A∩B∩C||A∩B∩C|=|C|-(|A∩C|+|B∩C|)+|A∩B∩C|即|A∩B∩C|+|A∩B∩C|+|A∩B∩C|=|A|+|B|+|C|-2(|A∩C|+|B∩C|+|B∩C|)+3|A∩B∩C|(3)推广到一般情况|A 1∩A 2∩A 3∩…∩A n|+|A 1∩A 2∩A 3∩…∩A n|+…|A1∩A2∩A3∩…∩An|=6ni=1|A i|-26ni=16j>i|A i∩A j|+3 6ni=16j>i6k>j|A i∩A j∩A k|-…+n|A 1∩A 2∩…∩A n|令α(m)=6|Ai1∩Ai2∩…∩Aim|,β(1)=6|A i1∩Ai2∩…∩Ain|则上式可表示为:β(1)=C11α(1)-C11+1α(2)+C21+2α(3)-…+C1nα(n)同理可推广:β(m)=Cmmα(m)-Cmm+1α(m+1)+Cmm+2α(m+2)-…+(-1)n-m Cmnα(n)(6)公式(6)为广义的容斥原理(证明略)4应用案例一个学校只有3门课程:数学,物理,化学。已知修这三门课的学生分别有170,130,120人;同时修数学、物理两门课的学生有45人;同时修数学、化学两门课的学生有20人;同时修物理、化学两门课的学生有22人;同时修三门课的学生有3人。问在该校众人抽一名,问他是只参加数学课程的概率是多少?解:设A为修数学课的学生集合;B为修数学课的学生集合;C为修数学课的学生集合;则有:|A|=170;|B|=130;|C|=120;|A∩B|=45;|A∩C|=20;|C∩B|=22|A∩B∩C|=3学校共有学生人数:|A∪B∪C|=|A|+|B|+|C|-[|A∩B|+|A∩C|+|B∩C|]+|A∩B∩C|=170+130+120-(45+20+22)+3=336(人)只参加数学课程的人数:|A∩B∩C|=|A|-(|A∩B|+|A∩C|)+|A∩B∩C|=170-(45+20)+3=108则在该校众人抽一名,只参加数学课程的概率为:P(A∩B∩C)=|A∩B∩C||A∪B∪C|=108336≈(下转第39页)(上接第32页)5结语通过对集合运算在《概率统计》与《组合数学》两门课程中应用的讨论,我们可以归纳为函数式的应用问题,如果把求概率和求集合中元素的个数抽象成为函数,把对应法则统一看作f,x,y为变量,“+”表示“加”或“或”的含义“;3”表示“乘”或“与”,“x”表示“差”或“非”,则该函数满足下列性质:(1)f(x+y)=f(x)+f(y)-f(x y)(2)将上式推广到有限个元素中去为:f(6ni=1x i)=6ni=1f(x i)-6ni=16j>if(x i x j)+6ni=16j>i6k>if(x i x j x k)-…+(-1)n-1 f(x 1 x 2…x n)(3)由De Morgan定理可知下述等式(A常数)f(6ni=1x i)=A-[6ni=1f(x i)-6ni=16j>if(x i x j)+6ni=16j>i6k>if(x i x j x k)-…+(-1)n-1 f(x 1 x 2…x n)]注“:3”号可以省略不写,“∏”表示连乘号以上等式还可以推广到无穷多个变量的函数等式中去,并且该函数也可以应用于其它领域当中。参考文献:[1]卢开澄.组合数学[M].北京:清华大学出版社,2003.[2]梁之舜.概率论及数理统计[M].北京:高等教育出版社,2005.[3]同济大学应用数学系.高等数学[M].北京:高等教育出版社,2005.