CH3集合的基本概念和运算.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。 符号代表的集合 N(N+)自然数(正整数)集 Z(Z+, Z-)整数(正整数,负整数)集 Q(Q+, Q-)有理数(正有理数,负有 理数)集 R(R+, R-)实数(正实数,负实数)集 C复数集 集合的特点 一个集合的元素有如下特点： (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 求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的最小公倍数