CH3集合的基本概念和运算.ppt

离散数学,CH3集合的基本概念和运算,集合论简介,康托(GeorgCantor，1845-1918)是集合论的创始人，为数学引入了集合和无限两个新事物。集合论是数学中许多分支的基础，是整个大厦的基础，是许多计算机科学理论不可或缺的工具。从历史上来看，1900年之前的数学几乎没有集合论的容身之地。当时的学术论文，文摘杂志上，集合论都被作为哲学的一部分。集合不仅可以用来表示数及其运算，更可以用于非数值信息的表示和处理，如数据的删除、排序、插入、数据间的关系描述。,第3章集合的基本概念和运算,集合是数学、计算机科学以及其他科学的最基础的知识之一本章学习：集合的基本概念和基本运算1集合的基本概念2集合的基本运算3集合中元素的计数,3.1集合的基本概念,康托关于集合的描述：集合是一些确定的、不同的事物的总体，这些事物人们可以意识到，并且能判断一个给定的事物是否属于这个总体。集合是由某些相互区别的事物汇集在一起组成的整体。例(1)所有偶数构成一个集合。(2)所有在20世纪80年代出生的人构成一个集合。(3)亚洲的国家的全体构成一个集合。(4)方程x2-1=0的全体实数解集合。(5)26个英文字母的集合。(6)计算机内存的全体单元的集合。,3.1集合的基本概念,集合是不能精确定义的、基本的数学概念一般认为一个集合指的是一些可确定、可分辨的事物构成的整体对于给定的集合和事物，应该可以断定这个特定的事物是否属于这个集合如果属于，就称它为这个集合的元素,集合的符号表示,集合通常用大写英文字母表示。元素通常用小写字母表示。a是集合A的元素，记作aA，否则记为aA。,集合的特点,一个集合的元素有如下特点：(1)互异性；(2)无序性；(3)确定性,在集合论中，规定元素之间是彼此相异的，并且是没有次序关系的例如:集合3，4，5，3，4，4，4，55，4，3都是同一个集合,集合的表示方法,列举法（穷举法）：把一个集合中的所有或者部分元素列举在花括号当中，元素之间用逗号隔开。例如：A=0,1,100A=a，b，c，d其中a是A的元素，记作aA同样有bA，cA，dA但e不是A的元素，可记作eA,集合的表示方法,描述法（谓词表示法）：用一个谓词公式P(x)表示x具有性质P，用x|P(x)表示所有具有性质P的事物组成的集合例如：x|x-2|1,x是实数x|x是自然数,x100x|x5+x4+x3+x+1=0B=x|xZ3x6,一般说来，集合的元素可以是任何类型的事物一个集合也可以作为另一个集合的元素例如，集合A=a,b,c,d,daA,b,cA,dA,dAb,c,d本身也是集合但，bA,dAb是A的元素b,c中的元素，不是A的元素,集合间的关系,定义（包含关系）设A，B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集合，或简称子集。这时也称B被A包含，或A包含B。记作：BA。包含的符号化表示为：BAx(xBxA)例：令A=0，1，2，B=0，1,C=1，2则有BA，CA，AA对任何集合S都有SS,定义（相等关系）设A，B为集合，如果BA且AB，则A与B相等，记作A=B，符号化表示为A=BABBA如果A和B不相等，则记作AB由以上定义可以知道，两个集合相等的充分必要条件是它们具有相同的元素例如，A=x|x是小于等于3的素数B=x|x|x=2x=3则A=B,定义（真子集）设A，B为集合，如果BA且BA，则称B是A的真子集，记作BA例如，0，1是0，1，2的真子集但1，3和0，1，2都不是0，1，2的真子集,空集:不含任何元素的集合叫做空集，记作。空集可以符号化表示为:=x|xx=x|P(x)P(x)空集是客观存在的，例如:A=x|xRx2+1=0是方程x2+1=0的实数解集。因为该方程没有实数解，所以A=,集合的简单性质:定理3.1空集是一切集合的子集。证明:任给集合A，由子集定义有Ax(xxA)右边的蕴涵式中，因前件x为假，所以整个蕴涵式对一切x为真。推论空集是唯一的。证明:假设存在空集1和2，由定理3.1，有12和21，根据集合相等的定义得1=2。,例3.1确定下列命题是否为真。（1）；（2）；（3）；（4）。解:（1），（3），（4）为真，（2）为假。注意和的区别：不含任何元素；含唯一一个元素。,集合的其他一些概念:含有n个元素的集合简称n元集，它的含有m个（mn）元素的子集称作它的m元子集。下面说明求一个n元集的全部子集的方法,例3.2A=a,b,c,求A的全部子集。解:将A的子集从小到大分类：0元子集，即空集，只有1个：1元子集，即单元集或单集，有C31个：a,b,c2元子集，有C32个：a,b,a,c,b,c3元子集，有C33个：a,b,cA的子集共有8个,一般来说，对于n元集A，它的m(0mn)元子集有Cnm个。所以不同的子集总数为:Cn0+Cn1+Cnn=2n定义（幂集）设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)，或PA，或2A。符号化表示为:P(A)=x|xA若A有n个元素，则P(A)有2n个元素例，设A=a,b,c，则P(A)=,a,b,c，a,b,a,c,b,c,a,b,c,练习,判断下列表达式是否成立：xx,xx,xx,xx,xx,xx,x,x,是否存在集合A,B满足AB且AB下列集合是否为某集合的幂集？(1);(2)a,;(3),a;(4),a,a,定义（全集）在一个具体问题中，如果所涉及的集合都是某个集合的子集。则称这个集合为全集，记作E（或U）全集是个相对性的概念。由于所研究的问题不同，所取的全集也不同例如，研究平面解析几何的问题时把整个坐标平面取作全集，研究整数的问题时，把整数集取作全集,3.2集合的基本运算,给定集合A和B，可以通过集合的并，交，相对补，绝对补，以及对称差等运算产生新的集合,定义（并、交、相对补）设A，B为集合，A与B的并集AB，交集AB，B对A的相对补集A-B分别定义如下：AB=x|xAxBAB=x|xAxBAB=x|xAxBAB由A或B中的元素构成AB由A和B中的公共元素构成AB由属于A但不属于B中的元素构成,例:A=1，3，4，B=2，3，C=4则有AB=1，2，3，4=BAAB=3=BABC=AB=1，4BA=2CA=当两个集合的交集是空集时，称它们是不相交的。,交运算和并运算的扩展n个集合A1，A2，An的并集和交集定义如下:A1A2An=x|xA1xA2xAn简记为:i=1nAiA1A2An=x|xA1xA2xAn简记为:i=1nAi,例如，0,11,20,1,1,2=0,1,2,0,1,1,20,11,21,3=1,定义(绝对补集):设E为全集，AE，则称A对E的相对补集为A的绝对补集，记作A，即：A=EA=x|xExA例:E=0,1,2,3,A=0,1,2,B=0,1,2,3,C=则A=3，B=，C=E,定义（对称差）设A，B为集合，则A与B的对称差是:AB=(AB)(BA)例:A=0,1,2,B=2,3则AB=0,13=0,1,3,A与B的对称差也可等价地定义为AB=（AB）（AB）这时，对于上例，有AB=0,1,2,32=0,1,3,课堂练习,P723.1,集合的算律,任何代数运算都遵从一定的算律（恒等式），集合运算也不例外下面列出的是集合运算的主要算律，其中的A，B，C表示任意的集合，E是全集,幂等律AA=AAA=A结合律（AB)C=A（BC）(AB)C=A（BC）交换律AB=BAAB=BA分配律A（BC）=（AB）（AC）A（BC）=（AB）（AC）同一律A=AAE=A零律AE=EA=,排中律AA=E矛盾律AA=吸收律A（AB）=AA（AB）=A双重否定律（A）=A德.摩根律AB）=AB（AB）=AB=EE=A-（BC）=（A-B）（A-C）A-（BC）=（A-B）（A-C）,恒等式及集合相等的证明方法,之一证明的基本思想是：欲证P=Q，即证：PQQP也就是要证明对任意的x有xPxQ,例:证明A-（BC）=（A-B）（A-C）即证对x,xA-(BC)x(A-B)(A-C)证：xA-(BC)xAxBCxA(xBC)xA(xBxC)xA(xBxC)xAxBxC(xAxB)(xAxC)xA-BxA-Cx(A-B)(A-C)A-(BC)=(A-B)(A-C),恒等式及集合相等的证明方法,之二：利用已知算律证明例:证明（AB）B=AB证:（AB）B=（AB）B=（AB）（BB）=（AB）E=AB,除以上所给的算律以外，还有一些关于集合运算性质的重要结果ABA,ABBAAB,BABA-BAAB=BABAB=AA-B=A-B=ABA-B=A-(AB),文氏图,集合之间的相互关系和有关的运算可以用文氏图给予形象的描述文氏图的构造方法如下:首先画一个大矩形表示全集E其次在矩形内画一些圆或任何其它的适合的闭曲线，用圆的内部表示集合通常在图中画有阴影的区域表示新组成的集合在一般情况下，如果不作特殊的说明，这些表示集合的圆应该是彼此相交的如果已知某两个集合是不交的，则表示它们的圆彼此相离,例:用文氏图表示下面集合(1)A(BC)(2)(AB)-C,集合中元素的计数,集合A=1，2，n，它含有n个元素，这个集合的基数是n，记作cardA=n或|A|=n显然空集的基数是0，即|=0定义设A为集合，若存在自然数n，使得cardA=|A|=n，则称A为有穷集，否则就称A为无穷集。例有100名程序员，其中47名熟悉C语言，35名熟悉C+语言，23名熟悉这两种语言。问有多少人对这两种语言都不熟悉？常用方法：文氏图、容斥原理,使用文氏图解决有穷集的计数问题1.首先根据已知条件把对应的文氏图画出一般地说，每一条性质决定一个集合，有多少条性质，就有多少个集合如果没有特殊的说明，任何两个集合都是相交的2.然后将已知集合的基数填入表示该集合的区域内通常是从几个集合的交集填起接着根据计算的结果将数字逐步填入其它空白区域内直到所有区域部填好为止,例:有100名程序员，其中47名熟悉FORTRAN语言，35名熟悉PASCAL语言，23名熟悉这两种语言。问有多少人对这两种语言不熟悉？,例：用文氏图解决下列问题：某学校足球队38人，篮球队15人，棒球队20人，三个队总人数58人，其中，3人同时参加了3个队，问同时参加两个队者共有几人？,3,求x+y+z+3,58=38-x-y-3+15-x-z-3+20-y-z-3+x+y+z+3求得：x+y+z=9,0,所以同时参加两个队的人有12个,练习:对24名科技人员进行掌握外语情况的调查,其统计资料如下:所有人员起码会一门外语。会英、日、德和法语的人数分别为13、5、10和9人。其中同时会英语和日语的有2人。同时会英语和法语，或者同时会英语和德语，或者同时会德语和法语两种语言的各有4人。会日语的人既不懂法语也不懂德语。求：只会英语、法语、德语和日语的分别有几人？同时会英语、法语、德语的有几人？,0,0,0,X=1,例:一个班里有50个学生，在第一次考试中有26人得5分，在第二次考试中有21人得5分。如果两次考试中都没得5分的有17人，那么两次考试都得5分的有多少人？,X=14,包含排斥原理的简单形式,设S是有穷集，P1和P2分别表示两种性质，对于S中的任何一个元素x，只能处于以下4种情况之一：(1)只具有性质P1；(2)只具有性质P2；(3)同时具有两种性质；(4)两种性质都没有。设A1和A2分别表示S中具有性质P1和P2的元素的集合，则|A1A2|=|S|-(|A1|+|A2|)+|A1A2|推论：|A1A2|=(|A1|+|A2|)-|A1A2|,包含排斥原理,定理3.2设S为有穷集，P1,P2,Pm是m个性质。S中的任何元素x或者具有性质Pi，或者不具有性质Pi(i=1,2,m),两种情况必居其一。令Ai表示S中具有性质Pi的元素构成的子集，则S中不具有性质P1,P2,Pm的元素为,推论,S中至少具有一条性质的元素数为,例3.10,求1到1000之间(包含1和1000在内)既不能被5和6，也不能被8整除的数有多少个。解：设Sx|xZ1x1000Ax|xSx可被5整除Bx|xSx可被6整除Cx|xSx可被8整除|T|表示有穷集T中的元素数x表示小于等于x的最大整数lcm(x1,x2,xn)表示x1,x2,xn的最小公倍数,例3.10,|A|1000/5200|B|1000/6166|C|1000/8125|AB|1000/lcm(5,6)33|AC|1000/lcm(5,8)25|BC|1000/lcm(6,8)41|ABC|1000/lcm(5,6,8)8,例3.10,根据包含排斥原理，所求不能被5，6和8整除的数应为,容斥原理实例2,某学院选课情况如下：260人选C语言，208人选编译原理，160人选人工智能，76人选C语言和编译原理，48人选C语言和人工智能，62人选编译原理和人工智能，全部3门课均选的有30人，3门课均没选的有150人(1)该学院共有多少人？(2)有多少学生选C语言和编译原理，但不选人工智能？(3