第六章集合代数ppt课件.ppt

6.1 集合的基本概念,方程x2 - 1 = 0的实数解集合, 1和-1是该集合的元素;26个英文字母的集合, a, b, , z是该集合的元素;坐标平面上所有点的集合;, , 是该集合的元素;,常用的集合名称:,N: 自然数集合(本课程中认为0也是自然数)Z: 整数集合Q: 有理数集合R: 实数集合C: 复数集合,集合(Set)是一些个体汇集在一起所组成整体.通常把整体中的个体称为集合的元素或成员.例如:,集合是不能精确定义的基本概念。,集合有三种表示方法:列元素法、谓词表示法和图示法.,列元素法:列出集合中的所有元素, 各元素之间用逗号隔开, 并把它们用花括号括起来.,例如 A = a, b, c, , z Z = 0, 1, 2, ,谓词表示法: 用谓词来概括集合中元素的属性.,例如:B = x | x R 且 x2 - 1 = 0 集合B表示方程x2 - 1 = 0的实数解集.,许多集合可用两种方法来表示, 如: B = -1, 1 .有些集合不能用列元素法表示, 如: 实数集合, 不能列举出所有集合中的所有元素.,图示法:用一个圆来表示, 圆中的点表示集合中的元素.,6.1 集合的基本概念,集合的元素是彼此不同的.,若同一个元素在集合中多次出现, 则只认为其是一个元素;如: 1, 1, 2, 2, 3 = 1, 2, 3 ,集合的元素是无序的, 如: 3, 1, 2 = 1, 2, 3 ,本书规定: 集合的元素都是集合.,6.1 集合的基本概念,元素(Element)和集合之间的隶属关系: “属于”或“不属于”.“属于”关系记作, “不属于”记作.例如: A = a, b, c , d, d .aA, b, c A, dA, d A,bA, d A.b和 d 是A元素的元素.为了体系的严谨性, 规定: 对任何集合A, 都有: AA.,A = a, b, c , d, d 的树形图表示.,a, b, c ,A,d, d ,b,c, d ,d,6.1 集合的基本概念,如果B不被A包含, 则记作B A.包含的符号化表示为B A x(xB xA)例如: N Z Q R C, 但, Z N.显然, 对任何集合A, 都有: A A.包含关系表示集合之间的关系;隶属关系表示元素和集合之间的关系, 但也可表示某些集合之间关系. 如: a a, a , a a, a ,定义6.1 设A和B为集合, 若B中的每个元素都是A的元素, 则称B是A的子集合, 简称子集(Subset), 也可称B被A包含, 或A包含B, 记作B A.,A,B,6.1 集合的基本概念,：等值的：蕴涵式,定义6.2 设A和B为集合, 如果A B且B A, 则称A与B相等, 记作: A = B.,若A与B不相等, 则记作: A B.相等的符号化表示为 A=B ABBA x(xA xB)x(xB xA),定义6.3 设A和B为集合, 如果B A且B A, 则称B是A的真子集(Proper Subset), 记作B A.,若B不是A的真子集, 则记为: B A.真子集的符号化表示为: B A B AB A例如: N Z Q R C, 但, NN.,6.1 集合的基本概念,定义6.4 不含任何元素的集合叫做空集, 记作: .,空集可以符号化表示为: = x | x x .例如: x | xRx2+1=0 是方程x2+1=0的实数解集, 因为该方程无实数解, 所以, 其解集是空集.,定理6.1 空集是一切集合的子集.,任给一个集合A, 由子集的定义可知: A x(x xA)由于蕴涵式(x xA)的前件为假而使其成为真命题, 所以, A.,6.1 集合的基本概念,证,假设: 存在空集1和2.由定理6.1可知: 1 2, 2 1.由集合相等的定义可知: 1 = 2.,推论 空集是惟一的.,证,例6.1 A = 1, 2, 3 , 将A的子集分类:,假设有一个含有n个元素的集合A（n元集）, 若集合A1是其子集且|A1| = m, 则称子集A1为集合A的m元子集.对任给一个n元集合A, 如何求出它的全部子集?,0元子集, 即空集, 只有一个: ;1元子集, 即单元集: 1 , 2 , 3 ;2元子集: 1, 2 , 1, 3 , 2, 3 ;3元子集: 1, 2, 3 .,由上面的例子, 我们不难归纳出: 对n元集合A, 有:,0元子集有Cn0个1元子集有Cn1个m元子集有Cnm个n元子集有Cnn个子集总数为 Cn0 + Cn1 + + Cnn=2n个,定义 集合A中元素的个数n为集合的势(Cardinality), 记为|A|.,6.1 集合的基本概念,全集是有相对性的, 不同的问题有不同的全集, 即使是同一个问题也可以取不同的全集.例如:在研究平面上直线的相互关系时, 可把整个平面上所有点的集合看作全集, 也可把整个空间上所有点的集合看作全集.一般地说, 全集取得小一些, 问题的描述和处理会简单些.,幂集的符号化表示为: P(A) = x | x A .对于集合A = 1, 2, 3 , 有:P(A) = , 1, 2, 3, 1,2, 1,3, 2,3, 1,2,3 .不难看出, 若A是n元集, 则P(A)有2n个元素.,定义6.6 在某具体问题中, 若所涉及的集合都是某个集合的子集, 则称该集合为全集(Universal Set), 记作E.,定义6.5 设A为集合, 把A的全体子集构成的集合叫做A的幂集(Power Set), 记作P(A), PA, 2A.,6.1 集合的基本概念,集合的基本运算有并(Union), 交(Intersection)和相对补(Relative Complement).,定义6.7 设A和B为集合, A与B的并集AB, 交集AB, B对A的相对补集A-B分别定义如下:,AB = x | x Ax B AB = x | x Ax B A - B = x | x Ax B ,由定义可知: AB是由A或B的元素构成, AB由A和B的公共元素构成, A-B由属于A, 但不属于B的元素构成.例如: A = a, b, c , B = a , C = b, d , 则:AB = a, b, c AB = a A - B = b, c B - A = , BC = ,若两个集合的交集为, 则称这两个集合是不相交的.如: B和C是不相交的.,6.2 集合的运算,n个集合的并和交:,无穷多个集合的并和交:,i=1.Ai = A1A2i=1.Ai = A1A2,i=1.nAi = A1A2An = x | xA1xAn)i=1.nAi = A1A2An = x | xA1xAn),6.2 集合的运算,例如 A = a, b, c , B = b, d , 则: AB= a, c, d 对称差运算的另一种定义是A B = (AB) - (BA)在给定全集E以后, A E, A的绝对补集A定义如下:,集合的对称差集(Symmetric Difference)和绝对补集(Absolute Complement).,定义6.9 A = E A = x | xEx A,因为 E是全集, xE是真命题, 所以, A可以定义为A = x | x A .例如: E = a, b, c, d , A = a, b, c , 则, A = d .,定义6.8 设A和B为集合, A与B的对称差集AB定义为: A B = (A - B)(B - A),6.2 集合的运算,6.2 集合的运算,以上定义的并和交运算称为初级并和初级交. 下面考虑推广的并和交运算, 即广义并和广义交.,定义6.10 设A为集合, A的元素的元素构成的集合称为A的广义并, 记为A.符号化表示为:A = x | z(zAxz) ,根据广义并的定义不难得到: 若A = A1, A2, , An , 则A = A1A2An类似地可以定义集合的广义交.,例6.4 设A = a, b, c, a, c, d , a, e, f B = a C = a, c, d 则A = a, b, c, d, e, f B = a C = a c, d = ,6.2 集合的运算,例6.4:A = a, b, c, a, c, d , a, e, f B = a C = a, c, d 有:A = a , B = a , C = a c, d ,定义6.11 设A为非空集合, A的所有元素的公共元素所构成的集合称为A的广义交, 记为A.符号化表示为A = x | z(zA xz) ,定义6.11中, 特别强调A是非空集合;对于空集可以进行广义并, 即: = ;空集不可进行广义交, 因为不是集合;在集合论中是没有意义的;若A = A1, A2, , An , 则A = A1A2An.,6.2 集合的运算,称广义并, 广义交, 幂集, 绝对补运算为一类运算, 并, 交, 相对补和对称差运算为二类运算.,下面的集合公式都是合理的公式: A - B, P(A), P(A)B, (AB),一类运算优先于二类运算一类运算之间由右向左顺序进行二类运算之间由括号决定先后顺序,6.2 集合的运算,例6.5 设 A = a , a, b , 计算A, A, A, A.,解A = a, b A = a A = abA = aA = abA = a,6.2 集合的运算,例6.5（续） 设 A = a , a, b , 计算 A(A - A) （练习）.,解A = a, b A = a A = abA = aA = abA = aA(A - A)= (ab)(ab) - a)= (ab)(b - a)= b所以 A = ab, A = a, A(A - A) = b.,6.2 集合的运算,课后作业,(1) 习题六 第5, 6, 8, 9,11,14题 （4小题（含）以上的题做奇数小题；否则全做。） （第96-98页）.,文氏图 (Venn Diagrams),AB=,AB=A,A-B,AB,AB,A,AB,B,(AB)-C,6.3 有穷集的计数,有穷集的计数,使用文氏图可以很方便地解决有穷集的计数问题。首先根据已知条件把对应的文氏图画出来 一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的。然后将已知集合的元素数填入表示该集合的区域内 通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。如果交集的数字是未知的，可以设为x。根据题目中的条件，列出一次方程或方程组，就可以求得所需要的结果。,例6.2 对24名人员掌握外语情况的调查.其统计结果如下:,解 令A, B, C和D分别表示会英、法、德、日语的人的集合.,设同时会三种语言的有x人, 只会英、法或德语一种语言的分别为y1, y2和y3.画出的图如右图.列出下面方程组:y1 + 2(4-x) + x + 2 = 13y2 + 2(4-x) + x = 9y3 + 2(4-x) + x = 10y1 + y2 + y3 + 3(4-x) + x = 19解得: x = 1, y1 = 4, y2 = 3, y3 = 3.,y2,2,4-x,y1,x,4-x,4-x,y3,5-2,D,A,C,B,会英、日、德、法分别为: 13, 5, 10和9人;同时会英语和日语的有2人;会英、德和法语中任两种语言的都是4人.,已知会日语的人既不懂法语也不懂德语, 分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数.,6.3 有穷集的计数,41,例6.3 求1到1000之间(包含1和1000在内), 既不能被5和6, 也不能被8整除的数有多少个.,解 设,S = x | xZ1 x 1000 A = x | xSx可被5整除 B = x | xSx可被6整除 C = x | xSx可被8整除 ,|A| = int(1000/5) = 200|B| = int(1000/6) = 166|C| = int(1000/8) = 125|AB| = int(1000/lcm(5,6) = 33|AC| = int(1000/lcm(5,8) = 25|BC| = int(1000/lcm(6,8) = 41|ABC| = int(1000/lcm(5,6,8) = 81000-(200+100+33+67)=600,17,150,25,8,133,33,200,166,125,167,33,67,25,100,59+ABC,6.3 有穷集的计数,定理6.2(包含排斥原理) 设S为有穷集, P1, P2, , Pm是m个性质.S中的任何元素x或者具有性质Pi, 或者不具有性质Pi(i=1.m), 两种情况必居其一.令Ai表示S中具有性质Pi的元素构成的子集, 则S中不具有性质P1, P2, , Pm的元素数为:,6.3 有穷集的计数,推论 S中至少具有一条性质的元素数为,根据包含排斥原理, 例6.3中所求的元素数为:|ABC| = |S| - (|A|+|B|+|C|) + (|AB|+|AC|+|BC|) - |ABC| =1000-(200+166+125)+(33+25+41)-8 = 600,6.3 有穷集的计数,欧拉函数,欧拉函数是数论中的一个重要函数, 设n是正整数,(n)表示0,1,n-1中与n互素的数的个数. 例如(12)=4, 因为与12互素的数有1,5,7,11. 这里认为(1)=1. 利用包含排斥原理给出欧拉函数的计算公式.分析 (1) 因式分解！ (2) 包含排斥原理。,欧拉函数（续）,(1) 因式分解 给定正整数n, n的因式分解式为, 令 则有(2) 包含排斥原理 首先计算 由包含排斥原理得,幂等率 Idempotent Laws AA = A(6.1) AA = A(6.2)结合律 Associative Laws (AB)C = A(BC)(6.3) (AB)C = A(BC)(6.4)交换律 Commutative Laws AB = BA(6.5) AB = BA(6.6)分配律 Distributive Laws A(BC) = (AB)(AC)(6.7) A(BC) = (AB)(AC)(6.8),6.4 集合恒等式,同一率 Identity Laws A = A(6.9) AE = A(6.10)零率 more Identity laws AE = E(6.11) A = (6.12)排中率 Complementation laws AA = E(6.13) AA = (6.14),6.4 集合恒等式,吸收率 Absorption laws A(AB) = A(6.15) A(AB) = A(6.16)德摩根律 De Morgan laws A - (BC) = (A - B)(A - C)(6.17) A - (BC) = (A - B)(A - C)(6.18) (BC) = BC(6.19) (BC) = BC(6.20) = E(6.21) E = (6.22)双重否定率 Double Complementation (A) = A(6.23),6.4 集合恒等式,6.4 集合恒等式,例6.6 证明: A - (BC) = (A - B)(A - C) (式6.17)分析（证明思路）（1）定义（集合的基本概念）；（2）命题逻辑中的等值演算。或者（3）根据前面的定理(集合恒等式)直接推导。,例6.8 证明: A - (BC) = (A - B)(A - C) (式6.17),证 对任意x, x A - (BC) xAx BC xA(xBxC) xA(xBxC) xAxBx C (xAxB)(xAxC) xA - BxA - C x(A - B)(A - C)所以, A - (BC) = (A - B)(A - C),6.4 集合恒等式,例6.9 证明式6.10, 即: AE = A.证 对任意x, xAE xAxE xA(因为xE是恒真命题), 所以, AE = A.,以上证明的基本思想是: 设P和Q为集合公式, 欲证: P = Q, 即证 PQQP为真.,要证对于任意的x有: xP xQ和xQ xP成立.对于某些恒等式, 可将这两个方向的推理合到一起, 就是xP xQ,6.4 集合恒等式,证 A(AB)= (AE)(AB)(6.10)= A(EB)(6.8)= A(BE)(6.5)= AE(6.11)= A(6.10),例6.10 假设已知等式6.1-6.14, 试证等式6.15:A(AB) = A.,6.4 集合恒等式,6.4 集合恒等式,（练习）,证明: A - (BC) = (A - B)(A - C) (式6.18),还有一些关于集合运算性质的重要结果.,AB A, AB B(6.24)A AB, B AB(6.25)A - B A(6.26)A - B = AB(6.27)AB = B A B AB = A A-B = (6.28)A B = B A(6.29)(A B) C = A (B C)(6.30)A = A(6.31)A A = (6.32)A B = A C B = C(6.33),6.4 集合恒等式,例6.11 证明等式6.27, 即A - B = AB.,证 对于任意的x, xA - B xAxB xAxB xAB所以, A - B = AB.等式6.27把相对补运算转换成交运算.,6.4 集合恒等式,例6.12 证明: (A - B)B = AB.,证(A - B)B= (AB)B= (AB)(BB)= (AB)E= AB,6.4 集合恒等式,例6.13 证明命题6.28是真命题: AB = B A B AB = A A - B = .,证 1). 证 AB = B A B 对于任意的x, xA xAxB xAB xB(因为AB = B) 所以, A B. 2). 证 A B AB = A 显然有AB A, 下面证: A AB. 对于任意的x, xA xAxA xAxB (因为A B) xAB 由集合相等的定义有: AB = A. 3). 证: AB = A A - B = A - B = AB = (AB)B (因为AB = A)= A(BB) = A = 4). 证: A - B = AB = B 由例6.12及A - B= , 有: AB = B(A - B) = B =B,6.4 集合恒等式,6.4 集合恒等式,AB = B A B AB = A A-B = (6.28)上式给出了A B 的四种等价形式用途（1）证明两个集合之间的包含关系；（2）用于集合公式的化简。,例6.14 化简(ABC)(AB) - (A(B-C) A),解 因为AB ABC, A A(B - C), 由式6.28: (ABC)(AB) - (A(B - C)A)= (AB) - A= B - A,式6.296.33是关于对称差运算的算律;前四条可通过对称差的定义加以证明;最后一条叫做消去律.,6.4 集合恒等式,证 已知AB = AC, 所以, 有: A(AB) = A(AC)(6.30) (AA)B = (AA)C(6.32) B = C(6.29) B = C(6.31),例6.15 已知AB = AC, 证明: B = C.,6.4 集合恒等式,课后作业,(1) 习题六 第19,21,28,32,45题 （4小题（含）以上的题做奇数小题；否则全做。） （第99-101页）.,谢 谢 !,