(20120831)第六章集合代数.ppt

,漳州师范学院计算机科学与工程系,第六章 集合代数,第六章 集合代数,集合的基本概念 集合的运算 有穷集的计数 集合恒等式 知 识 点：集合的概念与表示、集合的运算、包含排斥原 理 、集合恒等式 教学要求：深刻理解和掌握有关集合的基本概念和运算 教学重点：集合的基本概念和基本运算 学时: 2,6.1 集合的基本概念,集合: 把一些事物汇集到一起组成的整体称为集 合, 组成集合的那些事物称为该集合的元素 或成员. 集合一般有两种表示法: 列举法: 把属于集合的元素以某种方式列举出来, 写在花括号 里 例: 由四个数 -1, 2, 3, -4 构成的集合表示为-1, 2, 3,-4 描述法 把属于某个集合的元素所具有的特定性质P 描述出来, 写在花括号 里记为 x | P(x) 例: x | 3x+1 2 ,集合由其元素完全确定, 集合中的元素是不考虑次序的, 而且也应是互不相同的。,6.1 集合的基本概念,集合与元素之间的隶属关系 a是集合A的元素, 就称 a属于A, 记为 a A a不是集合A的元素, 就称 a不属于A, 记为a A 例: A= a , b,c , d , d 这里 aA, dA, d A , 但 b A 规定: A A 数集 用 N 表示自然数集, 用 Z 表示整数集, 用 Q 表示有理数集, 用 R 表示实数集, 用 C 表示复数集,6.1 集合的基本概念,集合间的包含与相等关系 定义6.1 设A, B为两个集合, 如果B的每一个元素都属 于A 则称B是A的子集, 记为B A 或 A B, 也称 A包含B。 如果B不被A包含, 则记作 B A 包含的符号化表示为 B A (x) ( xB x A ) 对任何集合A都有 A A 例如: N Z Q R C 隶属关系和包含关系都是两个集合之间的关系,对某些集合可以同时成立这两种关系 例如: A= a, a , 则 a A 并且 a A,6.1 集合的基本概念,定义 6.2 设A, B为两个集合, 若B A且 A B, 则称A与B相等, 记作 A = B 相等的符号化表示为 A B (B A) ( A B ) 定义 6.3 设A,B为集合,如果 B A 且BA 则称B为A的真子集或A真包含B, 记为B A 真子集的符号化表示为 A B (B A) ( A B ),6.1 集合的基本概念,定义 6.4 不含任何元素的集合称为空集, 记为 空集的符号化表示为 = x | xx 定理 6.1 空集是一切集合的子集 A (x) ( x x A ) 推论 空集是唯一的,6.1 集合的基本概念,至少有一个元素的集合称为非空集. 由无限多个元素构成的集合称为无限集. 由有限个元素构成的集合称为有限集. 含有n个元素的集合简称为n元集 n元集的含有m(mn)个元素的子集叫做它的m元子集 对n元集集A,它的0元子集有Cn0个, 1元子集有Cn0个, m元子集有Cnm个, n元子集有Cnn个 所以子集总数为 Cn0 + Cn0 + Cnn =2n,6.1 集合的基本概念,定义 6.5 设A为集合,把A的全体子集构成的集合 叫做A的幂集,记作P(A)或2A 例如: 设A=a, b, c, 则P(A)=,a,b,c,a,b,a,c,b,c,A 定义 6.6 在一个具体的问题中，如果所涉及的集合都是某个集合的子集,则称这个集合为全集,记作E。全集是相对的。,6.2 集合的运算,定义6.7 设A,B为集合,A与B的并,交,差(相对补) 运算定义如下: 并: A与B的并集记为AB , ABx|xAxB 交: A与B的交集, 记为AB ,ABx|xAxB 差: A与B的差集, 记为AB , A 与 B 的差称为B 关于A 的相对补. AB x|xAx B ,6.2 集合的运算,定义6.8 设A, B为集合, A与B 的对称差集 AB,定义为 A B = x | x AB x AB 定义6.9 给定全集E以后,设A是E的子集,A的绝 对补集A定义如下: A = EA= x|xE x A ,6.2 集合的运算,五种运算的文氏图,6.2 集合的运算,两个集合的并和交运算可以推广成n个集合的并和交： A1A2Anx|xA1xA2xAn A1A2Anx|xA1xA2xAn A1A2An A1A2An 并和交运算还可以推广到无穷多个集合的情况： A1A2 A1A2,6.2 集合的运算,定义6.10 设A为集合,A的元素的元素构成的集合 称为A的广义并 A的广义并记为A A的广义并符号化表示为 A= x | z ( zA xz ) = 例如: A= a,b,c,a,c,d,a,e,f , 则 A=a,b,c,d,e,f ,6.2 集合的运算,定义6.11 设A为非空集合,A的所有元素的公共元 素构成的集合称为A的广义交 A的广义交记为A A的广义交符号化表示为 A= x | z (zA x z) 在集合论中没有意义 , 不是集合 例如: A= a,b,c , a,c,d , a,e,f ,则 A=a,6.2 集合的运算,集合运算的优先次序 广义并,广义交,幂集,绝对补运算为一类运算 并,交,相对补,对称差运算为二类运算 一类运算优先于二类运算 一类运算之间由右向左顺序进行 二类运算之间由括号决定先后顺序,6.3 有穷集的计数,使用文氏图可以很方便地解决有穷集的计数问题。 首先根据已知条件把对应的文氏图画出来。 一般地说，每一条性质决定一个集合。有多少条性质，就有多少个集合。如果没有特殊说明，任何两个集合都画成相交的，然后将已知集合的元素数填入表示该集合的区域内。 通常从n个集合的交集填起，根据计算的结果将数字逐步填入所有的空白区域。 如果交集的数字是未知的，可以设为x。 根据题目中的条件，列出一次方程或方程组， 就可以求得所需要的结果。,6.3 有穷集的计数,例6.4 对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。,6.3 有穷集的计数,解: 令A，B，C，D分别表示会英、法、德、日语的人的集合。根据题意画出文氏图如图6.3所示。设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。 根据已知条件列出方程组如下： 解得x1，y14，y22，y33,6.3 有穷集的计数,定理6.2 (包含排斥原理) 设S为有穷集, P1,P2,Pn是n个性质.A中的任何元素x或者具有性质Pi或者不具有性质Pi,两种情况必居其一。 令Ai表示A中具有性质Pi的元素构成的子集,则A中不具有性质P1,P2,Pn的元素数为,6.4 集合恒等式,基本集合恒等式 , A,B,C代表任意集合 幂等律 AAA (6.1) AAA (6.2) 结合律 (AB)CA(BC) (6.3) (AB)CA(BC) (6.4) 交换律 ABBA (6.5) ABBA (6.6) 分配律 A(BC)(AB)(AC) (6.7) A(BC)(AB)(AC) (6.8),6.4 集合恒等式,同一律 AA (6.9) AEA (6.10) 零律 AEE (6.11) A (6.12) 排中律 AAE (6.13) 矛盾律 AA