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

离散数学,CH3 集合的基本概念和运算,集合论简介,康托(Georg Cantor，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，5 5，4，3 都是同一个集合,集合的表示方法,列举法（穷举法）：把一个集合中的所有或者部分元素列举在花括号当中，元素之间用逗号隔开。 例如： A=0, 1, , 100 A= a，b，c，d 其中a是A的元素，记作aA 同样有bA，cA，dA 但e不是A的元素，可记作e A,集合的表示方法,描述法（谓词表示法）：用一个谓词公式P(x)表示x具有性质P，用x|P(x)表示所有具有性质P的事物组成的集合 例如： x| |x-2| 1, x是实数 x|x是自然数, x100 x|x5+x4+x3+x+1=0 B=x|x Z 3x6,一般说来，集合的元素可以是任何类型的事物 一个集合也可以作为另一个集合的元素 例如，集合 A= a, b,c, d, d aA, b,cA, dA, d A b,c, d本身也是集合 但，b A, d A b是A的元素b,c中的元素，不是A的元素,集合间的关系,定义（包含关系）设A，B为集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集合，或简称子集。这时也称B被A包含，或A包含B。记作： B A。 包含的符号化表示为： B A x(x Bx A) 例：令A=0，1，2，B=0，1 ,C=1，2 则有B A，C A，A A 对任何集合S都有S S,定义（相等关系）设A，B为集合，如果B A且A B，则A与B相等，记作A=B， 符号化表示为A=BA BB A 如果A和B不相等，则记作AB 由以上定义可以知道，两个集合相等的充分必要条件是它们具有相同的元素 例如， A=x|x是小于等于3的素数 B=x|x|x=2x=3 则A=B,定义（真子集）设A，B为集合，如果B A且BA，则称B是A的真子集，记作B A 例如，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，由子集定义有 A x(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.2 A=a,b,c,求A的全部子集。 解: 将A的子集从小到大分类： 0元子集，即空集，只有1个： 1元子集，即单元集或单集，有C31个： a,b,c 2元子集，有C32个：a,b,a,c,b,c 3元子集，有C33个：a,b,c A的子集共有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分别定义如下： A B=x|xAxB A B =x|xAxB AB=x|xAx B A B由A或B中的元素构成 A B由A和B中的公共元素构成 AB 由属于A但不属于B中的元素构成,例: A=1，3，4，B=2，3，C=4 则有 A B=1，2，3，4= B A A B=3= B A B C= AB=1，4 BA=2 CA= 当两个集合的交集是空集时，称它们是不相交的。,交运算和并运算的扩展 n个集合A1，A2，An的并集和交集定义如下: A1A2 An=x|xA1xA2xAn 简记为: i=1nAi A1A2 An=x|xA1xA2xAn 简记为: i=1nAi,例如， 0,1 1,2 0,1,1,2 =0,1,2,0,1,1,2 0,1 1,2 1,3= 1,定义 (绝对补集):设E为全集，A E，则称A对E的相对补集为A的绝对补集，记作A，即： A=EA = x|xEx A 例: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=（A B）（A B） 这时，对于上例，有 AB=0,1,2,32=0,1,3,课堂练习,P72 3.1,集合的算律,任何代数运算都遵从一定的算律（恒等式），集合运算也不例外 下面列出的是集合运算的主要算律，其中的A，B，C表示任意的集合，E是全集,幂等律 AA=A AA=A 结合律 （AB)C = A（BC） (AB)C = A（BC） 交换律 AB=BA AB=BA 分配律 A（BC）=（AB）（AC） A（BC）=（AB）（AC） 同一律 A = A AE = A 零律 AE = E A = ,排中律 AA = E 矛盾律 AA= 吸收律 A（AB）=A A（AB）=A 双重否定律 （A）=A 德.摩根律 AB）= A B （AB）= A B =E E= A-（BC）=（A-B）（A-C） A-（BC）=（A-B）（A-C）,恒等式及集合相等的证明方法,之一 证明的基本思想是： 欲证P=Q，即证： P QQ P 也就是要证明对任意的x有 xP xQ,例:证明 A-（BC）=（A-B）（A-C） 即证对 x, xA-(BC) x(A- B)(A-C) 证：xA-(BC) xAx BC xA(x BC) xA(x Bx C) xA(x Bx C) xA x B x C (xAx B ) (xAx C) xA-B xA-C x(A- B) (A-C) A-(BC)=(A-B)(A-C),恒等式及集合相等的证明方法,之二： 利用已知算律证明 例: 证明（AB）B = AB 证: （AB） B =（AB）B =（AB）（BB） =（AB）E = AB,除以上所给的算律以外，还有一些关于集合运算性质的重要结果 ABA,ABB AAB,BAB A-BA AB=B AB AB=A A-B= A-B=A B A-B=A-(A B),文氏图,集合之间的相互关系和有关的运算可以用文氏图给予形象的描述 文氏图的构造方法如下: 首先画一个大矩形表示全集E 其次在矩形内画一些圆或任何其它的适合的闭曲线，用圆的内部表示集合 通常在图中画有阴影的区域表示新组成的集合 在一般情况下，如果不作特殊的说明，这些表示集合的圆应该是彼此相交的 如果已知某两个集合是不交的，则表示它们的圆彼此相离,例:用文氏图表示下面集合 (1) A(BC) (2) (A B)-C,集合中元素的计数,集合A=1，2，n，它含有n个元素， 这个集合的基数是n，记作 card A = n 或 |A|=n 显然空集的基数是0，即|=0 定义 设A为集合，若存在自然数n，使得card A=|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|xZ1x1000 A x|xSx可被5整除 B x|xSx可被6整除 C x|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) 有多少学生选C语言和人工智能，但不选编译原理？(4) 有多少学生选人工智能和编译原理，但不选C语言？(5) 有多少学生选C语言，而不选其他两门课？(6) 有多少学生选编译原理，而不选其他两门课？(7) 有多少学生选人工智能，而不选其他两门课？,容斥原理实例3,某班学生150人，数学考试成绩90以上的有80人，语文考试成绩90以上的有75人，两门课程均在90以上的有50人，问(1) 只有一门课程在90以上的学生有多少人？(2) 两门课程均不在90以上的学生有多少人？,作业,P75 3.11 4、5 3.12 5、6 3.13 2、3 3.14 3.15 2、3 3.18 3.19,Q & A,59,