集合的概念及其表.ppt

第一章 集 合 1. 集合的概念及其表示 2. 集合之间的关系 3. 集合的运算 4. 容斥原理 1 本章学习目标 通过本章的学习，应达到如下目标： 深入理解掌握集合的概念和不同的表示方法 ； 理解集合间的关系和特殊集合，包括幂集等 ； 熟练掌握集合的基本运算（交、并、补、差 、对称差等）；理解集合运算的规律和主要 证明方法； 了解集合的图形表示法，能够借助文氏图直 观表示复杂的集合； 2 1.1 集合论(set theory) 十九世纪数学最伟大成就之一 集合论体系 朴素(naive)集合论 公理(axiomatic)集合论（蔡梅罗罗(Zermelo ) ) 创始人康托(Cantor)Georg Ferdinand Philip Cantor 1845 1918 德国数学家, 集合论创始人。他在 这一领域的贡献包括实数集合不 可数性的发现。 3 什么是集合(set) 集合：是一种原始概念，不能精确定义 。一些具有某种特点的对象的整体就构 成集合，这些对象称为元素(element) 或成员(member)。 用大写英文字母A,B,C,表示集合 用小写英文字母a,b,c,表示元素 a A：表示a是A的元素，读作“a属于 A” a A：表示a不是A的元素，读作“a不属 于A” 4 什么是集合(set)（续） 例 ： (1) 偶素数集合2, 称为为单单元集。 (2) 二进进制的基数集合0, 1。 (3) 英文字母(大写和小写)的集合。 (4) C#语语言的基本字符构成一个字符集。 (5) 计计算机主存的全部存储单储单 元集合。 (6) 全体实实数的集合。 (7) 广工全体师师生的集合。 5 集合的性质1（外延 (extension) 公理 ） 1. 外延 (extension) 公理-两个集合A和B相 等的充分必要条件是它们们有相同的元素。 I：互异性: 一个集合的各元素是可以互相区 分开的, 即每一元素在一个集合中只出现现一 次。 II：无序性: 集合中元素排列次序无关紧紧要, 即集合表示形式的不唯一性。例：a, b = b, a III. 确定性：任一元素是否属于一个集合, 回 答是确定的。 6 集合的性质2（正则则 (regularity)公理 ） 3. 对对任何集合S, 有S S；只能说说 S S，不能说说 S=S。（正则则 (regularity) 公理的推论论） 从而规规定了集合S与 S的不同层层次性。 说说明： 1.集合与其成员员是两个截然不同的概念, 集合的 元素可以是任何具体或抽象事物, 包括别别的集合, 但 不能是本集合自身。 2.先有成员员后才形成集合, 所以一个正在形成中的集合 并不能作为为一个实实体充当本集合的成员员。 7 1.2 数的集合表示 N：自然数(natural numbers)集合， N=0,1,2,3, Z：整数(integers)集合， Z=0, 1, 2,=,-2,-1,0,1,2, Q：有理数(整数商Quotient : i/j, j 0) R：实数(Real numbers)集合 C：复数(complex numbers)集合 P：素数或质质数 (Prime)集合 8 1.3 集合的表示 列举法（枚举法） 描述法（特征法） 9 1.列举法(roster) 列出集合中的全体元素，元素之间用逗 号分开，然后用花括号括起来，例如 A=a,b,c,d,x,y,z B=0,1,2,3,4,5,6,7,8,9 集合中的元素不规定顺序。 C=2,1=1,2 集合中的元素各不相同。 C=2,1,1,2=2,1 10 用列举举法表示集合并不总总是可能的。 例如, 区间间0, 1中的所有实实数的集合就不能 用这这种方法给给出。 从计计算机的观观点看, 列举举法是一种“静态态”表 示法, 若把全部列举举的数据都存储储在计计算机 中, 那将占用大量的存储储空间间。 11 2.描述法(defining predicate) 也称作特征法。以某个小写英文字母表 示该集合中的任意一个元素，并指出 该类 元素的共同特征。 例 : 正奇数集合 Odd = m | m=2n + 1且 n N。 例 : 0, 1上的所有连续连续 函数所形成的集 合可记记成 : C0, 1 = f (x) | f (x)在0, 1上连续连续 。 12 描述法(defining predicate) 描述法也称作谓词法，性质描述法。 用谓词P(x)表示x具有性质P ，用x|P(x)表 示具有性质 P 的集合，例如 P1 (x): x是小写英文字母 A=x|P1 (x)=x| x是英文字母 =a,b,c,d,x,y,z P2 (x): x是十进制数字 B=x|P2(x)= x|x是十进制数字 =0,1,2,3,4,5,6,7,8,9 13 描述法（续） 两种表示法可以互相转化，例如 E=2,4,6,8, /列举法 =x|x0且x是偶数 /描述法 =x|x=2(k+1)，k为非负整数 =2(k+1) | k为非负整数 有些书在列举法中用:代替|, 例如 2(k+1): k为非负整数 14 1.4 集合之间的关系 子集、真子集（包含关系与相等关系） 空集、全集 幂集 15 子集：设设A和B是两个集合, 若A中的每一个元 素都是B的元素, 则则称A是B的子集(subset), 也称B包含(include)A, 记记作A B(或B A) 。 真子集：若A为为B的子集, 且A B, 则则称A为为B 的真子集(proper subset), 或称B真包含A, 记记作A B, B称为为A的超集(superset)。 集合的包含关系：子集与真子集 16 子集、真子集(举例) 设A=England国家足球队全体成员 B=England国家足球队前锋成员 C=欧文, 鲁尼 则有 B A, C B, C A 也有 B A, C B, C A 17 子集(举例) 设A=a,b,c,B=a,b,c,d,C=a,b,则 A B, C A, C B， C A B A C B a b c d e f g h ij 18 例 ：N Q R C。 例 ：台湾人都是中国人, 台湾人真包含于中国 人, 即 台湾人 中国人。 “ ”与“ ”“ ”的区别别: 符号“ ”表示元素与集合间间的隶属关系; 例： 1 N /* 1 N，正确与否？*/ “ ” “ ”是集合之间间的包含关系, “ ” “ ”的 两边边均是集合, 地位平等。 集合之间间可以没有任何关系。 真子集(举例) 19 包含关系的性质 设设A、B、C为为3个集合, 由定义义可知集 合的包含关系有如下性质质： (1) A A。 (自反性) (2) 若A B且B A, 则则A = B。(反对对称 性) (3) 若A B且B C, 则则A C。(传递传递 性) 20 “ ”传递性证明 若A B,且B C, 则A C 证明: 因为 A B ，所以对于任意属于A 的元素x，都有x B； 又因为B C，则x C； 任何属于A的元素都属于C。即： A C 21 “ ”传递性证明 若A B,且B C, 则A C 证明: 要证A C，即证A C并且A C 首先证明A C A B A B 并且 A B A B 同理 B C B C, 所以A C. 反证法证明A C 假设A=C, 则B C B A, 又A B, 故A=B, 此与A B矛盾, 所以A=C不成立，因而A C成立. 所以, A C. 22 相等关系定义义1：由外延公理, 集合A与 集合B的元素完全相同时时, A = B。 相等关系判定定理： 设设A和B是任意两 个集合, 若A B 且 B A, 则则称A与 B相等, 记记作 A = B。 集合的相等关系 23 集合的相等关系有如下性质质： (1) A = A。(自反性 ) (2) 若A = B, 则则B = A。(对对称 性) (3) 若A = B且B = C, 则则A = C。 (传递传递 性) 两个相等的集合并不意味着它们们是用同样样的 方式定义义的。 例 ：设设集合A是方程 x2 x = 0 的解的集合, A = x | x2 x = 0; x2 x = 0 的解为为0 和1 B = 0, 1; 则则 A = B。 24 空集(empty set) 空集:不包含任何元素的集合称为为空集 (empty set), 记记作 , 或 。 例 ：方程 x2 + 1 = 0 的实实根集合是空集 。 这说这说 明空集是客观观存在的。 空集的引入, 可以使许许多问题问题 的叙述得 到简简化。 下列命题题成立： ； 25 例1 ：判断下列命题题的真假: (1) (2) (3) (4) Solution ：(2)为为假; 其余均为为真。 例2： 列出 B = 和 C = 的全部(真)子集 。 Solution ： 且 ； B有两个子集: 和 ； B只有一个真子集 : 。 C, 所以C只有一个子集 , 没有真子 集。 例3:是否存在集合A和B, 使得 A B 且 A B。 Solution ：存在。例 A = a, B = a, a 。 26 （1） 空集是一切集合的子集。 （2） 空集是唯一的。 proof 若存在空集合 1和 2, 由（1）知 1 2 和 2 1, 根据集合相等的定义义 1 = 2。 对对于每个非空集合S, 至少有两个不同的子集, 即 S 和 S S。 我们们称 和S自身是S的平凡子集。 空集的性质 27 全集 全集: 如果限定所讨论的集合A都是某个集合 U的子集,则称集合U是全集。某些书上也记 作E。 全集是相对的, 视情况而定, 因此不唯一.全集 只包含与讨论讨论 有关的所有对对象, 并不一定包 含一切事物。 例：讨论(a,b)区间里的实数性质时, 可以选 U=(a,b), U=a,b), U=(a,b, U=a,b, U=(a,+ ),U=(- ,+ )等 28 幂集(power set) 幂集: 设A是集合，A的全体子集组成的集合, 称为A的幂集,记作P(A)，或者2A 。A称作 P(A)的指标集。 P(A)=x|x A 注意: x P(A) x A。也就是说，P(A)中的 每一个元素都是集合，这些集合中的元素全 部都只能来自集合A。 例：A=a,b, P(A)= ,a,b,a,b. 29 集合的基 基：也称作“势”。集合A中元素的个数 。 基数是有限数的集合称为有限集, 否则 称为无限(infinite)集。一般仅对 有限集 讨论 其基的值。 定理：设A是有限集，且|A|=n，则A的 幂集的基|P(A)|= 2n 。 例：A=a,b, P(A)= ,a,b,a,b. |A|=2，则|P(A)|=4 30 给给定一个有限集, 要保证证不重复和不遗遗漏地 写出它的全部子集, 办办法之一就是将子集按 基数由小到大地分类类, 相同基数类类的子集再 按字母数字顺顺序逐个地写出。 例:求出集合S = a, b, c的所有子集。n=3 Solution: 0元子集, 只有一个C30个: ; 1元子集, 有C31个: a, b, c； 2元子集, 有C32个: a, b, a, c, b, c； 3元子集, 有C33个: a, b, c 。 共有子集数: C30+C31+C32+C33= (1+1)3 = 23 = 8 31 子集与二进制数 通过建立子集与二进制数的关系，求 出集合的所有子集。 A=a1, a2, , an, |A|=n a1a2a3an 0/10/10/10/1 1011 0110 = a2, a3 A的子集与n位二进制数一一对应 = a1, a3 , an B101001 B011000 32 子集与二进制数（举例） 例：设设A = a, b, c, |A| = 3, P(A) = B0= B000 = , B1= B001 =c, B2= B010 =b, B3= B011 =b,c, B4= B100 =a , B5= B101 =a,c B6= B110 =a,b , B7= B111 = a,b,c abc子集 B000 B001c B010b B011b,c B100a B101a,c B110a,b B111a,b,c 33 若|A|=n，A的任一子集都可用n位二进进制 数中的某个数来表示;反之, 若给给出2n 1 中的任何一个值值, 就能够够确定A相应应的子 集。 我们们只用下标标来确定子集的各元素, 而 字母B则则是无关紧紧要的。 若使用十进进制数作为为子集的下标标, 则则转转 换为换为 A的基数位数的二进进制数后同样处样处 理。 34 例 : 设设S = a1, a2, ., a8, 由B17 和B31所表示的S 的子集各是什么? 应应如何表示子集a1, a8和a3, a8, a7? 解 S有28 = 256个不同的子集, 可表示为为B0, B1, B2, B3, , B255, 二进进制下标标有8位. B17 = B00010001 = a4, a8 B31 = B00011111 = a4, a5, a6, a7 , a8 a1, a8 = B10000001 = B129 a3, a8, a7 = B00100011 = B35。 35 空集的幂集举例 1. | |=