资源描述
离散数学,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,
展开阅读全文