苏XI友无密码课件第3章集合的基本概念和运算.ppt

1、Chap.3 集合的基本概念和运算,集合论是研究集合一般性质的数学分支, 它作为一门独立学科诞生于19世纪, 创始人为乔治康托(George Cantor,1845-1918). 康托建立的集合论一般称为古典(或朴素)集合论. 集合论是全部现代数学的理论基础, 已深入到现代科学的各个方面, 集合的概念已成为表达各种严谨科学概念的必不可少的数学语言. 集合论的语言适应于描述和研究离散对象及其关系,所以它是计算机科学和技术的基础理论和表达工具. 集合论在程序语言、数据结构、开关理论、形式语言、关系数据库、编译原理、操作系统、人工智能、信息检索等领域都有着重要应用. 本课程主要介绍集合论的基础知识,

2、 属于古典集合论的范畴,2021/3/5,北京林业大学信息学院 苏喜友,1,1 集合的基本概念,集合是人们直观上或思想上能够明确区分的一些对象所构成的一个整体. 集合是在一定范围内所讨论的对象组成的整体. 集合是把一些事物汇集到一起组成的一个整体. Cantor称集合是“一些确定的、不同的东西的总体. 这些东西, 人们能够意识到, 并且能判断一个给定的东西是否属于这个总体.,2021/3/5,北京林业大学信息学院 苏喜友,2,集合中的事物、对象、客体称为集合的成员或元素. 集合用大写英文字母表示, 元素用小写英文字母表示. 集合与元素之间的关系是属于或不属于的关系. 如, 一元素a, 要么aS

3、, 要么aS,1 集合的基本概念,2021/3/5,北京林业大学信息学院 苏喜友,3,如果集合S中包含的元素个数是有限的, 则称S为有限(有穷)集合, 否则, 称为无限(无穷)集合. 称只有一个元素的集合为单元集, 称两个元素的集合为二元集, 一般地称有n个元素的集合为n元集,1 集合的基本概念,2021/3/5,北京林业大学信息学院 苏喜友,4,关于集合的定义需要注意: Note1 集合的元素是彼此不同的. 如, 1,1,2=1,2. Note2 集合的元素是无序的. 如, 1,2,3=3,1,2. Note3 集合的元素可以是任何类型的事物, 尤其可以是集合. 如, A=a,a,b,c,1

4、 集合的基本概念,2021/3/5,北京林业大学信息学院 苏喜友,5,集合的描述或表示通常有下述三种方法: (1)列举法(枚举法):列举集合中的所有元素来表示某个集合. 例如, A=a,b,c,d, N=0,1,2,3,. (2)谓词法(隐式法叙述法抽象法):用集合元素所 具有的共同性质来描述这个集合. 可以用非形式化的自然语言描述, 也可以用形式 化的谓词表示,1 集合的基本概念,2021/3/5,北京林业大学信息学院 苏喜友,6,例如, Z+=x|x是整数, 且x0. R=x|x是实数. B=x|xRx2-1=0. S=x|P(x), 其中, x具有性质P. (3)归纳法:由归纳法定义集合

5、中的元素. 例如, 设a0=1, a1=1, , ai+1=ai+ai-1(i1), 则 S=a0,a1,a2,a3,. 再例如, 命题公式的集合和谓词公式的集合都 是由归纳法定义的,1 集合的基本概念,2021/3/5,北京林业大学信息学院 苏喜友,7,一般说来, 任意的集合都可以用谓词法表示. 例如, A=a,e,i,o,u, A=x|x是英文中的元音字母. B=2,3,5,7, B=x|x是素数且x10. C=2,3,-5, C=x|x=2x=3x=-5. 由此可见, 谓词法是表示集合的基本方法,1 集合的基本概念,2021/3/5,北京林业大学信息学院 苏喜友,8,1 集合的基本概念,

6、Def.1 子集(Subset) 设A和B是两个集合, 如果A的每个元素都是B的元素, 则称A是B的子集, 也称A包含于B或B包含A. 记为AB或BA. 用谓词形式表示为: ABx(xAxB). 由定义, 任意一个集合都是其自身的子集, 即 AA,2021/3/5,北京林业大学信息学院 苏喜友,9,1 集合的基本概念,Def.2 相等 设A,B是集合, 如果AB且BA, 则称A和B相等. 记为AB. 若A和B不相等, 记为AB. 用谓词形式表示: AB(AB)(BA) x(xAxB)x(xBxA) x(xAxB,2021/3/5,北京林业大学信息学院 苏喜友,10,1 集合的基本概念,Def.

7、3 真子集(Real Subset) 设A,B为集合, 如果AB且AB, 则称A是B的真子集, 也称A真包含于B, 或B真包含A. 记为AB. 用谓词形式表示: AB(AB)(AB) x(xAxB)x(xBxA,2021/3/5,北京林业大学信息学院 苏喜友,11,1 集合的基本概念,Def.4 全集 由全体客体组成的集合称为全集.记为E或U. 全集具有相对性, 不同的问题有不同的全集, 既使同一个问题, 也可以有不同的全集. 一般说来, 全集取得小一些, 问题的描述和处理会简单些. Def.5 空集 不包含任何元素的集合称为空集或零集. 记为. 用谓词形式表示: x|P(x)P(x), 其中

8、, P(x)为任意的谓词,2021/3/5,北京林业大学信息学院 苏喜友,12,1 集合的基本概念,Theorem1 设A为一集合, 则有 A, AA, AE. 证明.Ax(xxA)1. AA, AE类似可证. Th.2 空集是唯一的. 证明.设空集不唯一, 不妨设和都是空集. 由Th.1, 得 ,. 由集合相等的定义, 得,2021/3/5,北京林业大学信息学院 苏喜友,13,1 集合的基本概念,Def.6 幂集(Power set) 设A为集合, A的所有子集组成的集合称为A的幂集. 记为P(A)或2A, 即 P(A)=x|xA. 例如, A=a,b,c, 则 P(A)=,a,b,c,a,

9、b,a,c,b,c,a,b,c. Def.7 基数(Cardinal Number) 集合中不同元素的数目称为集合的基数或势. 若基数是有限数, 则称该集合为有限(有穷)集, 否则称为无限(无穷)集. 有限集的基数记为|A|.如上例,|A|=3,|P(A)|=8,2021/3/5,北京林业大学信息学院 苏喜友,14,1 集合的基本概念,Th.3 (幂集的基数) 设A为有限集, 则P(A)的基数为|P(A)|=2|A|. 证明.设|A|=n, 即A中有n个不同元素. 从A中n个元素任意取i个元素组成A的子集, 共有 个. 故A的所有子集的个数为: 即,2021/3/5,北京林业大学信息学院 苏喜

10、友,15,1 集合的基本概念,Exp.1 判断下列命题是否为真. (1); (2); (3)aa; (4)aa; (5)aa; (6)aa; (7)a,ba,b,c,a,b; (8)a,ba,b,c,a,b,1,1,1,0,0,1,1,1,2021/3/5,北京林业大学信息学院 苏喜友,16,1 集合的基本概念,Exp.2 求下列集合的幂集. (1); (2); (3)a,a. 解.(1)P()=. (2)P()=,. (3)P(a,a)=,a,a,a,a,2021/3/5,北京林业大学信息学院 苏喜友,17,2 集合的运算,Def.1 集合的运算 (1)并 集合A与B的并记为AB, AB=x

11、|xAxB. (2)交 集合A与B的交记为AB, AB=x|xAxB. (3)相对补(集) 集合A与B的相对补记为A-B, A-B=x|xAxB. 也称A-B为A与B的差(集), B相对于A的补(集,2021/3/5,北京林业大学信息学院 苏喜友,18,2 集合的运算,4)绝对补(集) 设E为全集, AE, A的绝对补记为A(或A), A=E-A=x|xExA. (5)对称差(集) 集合A与B的对称差记为AB, AB=(A-B)(B-A) =x|(xAxB)(xBxA). 也称AB为A与B的环和,2021/3/5,北京林业大学信息学院 苏喜友,19,2 集合的运算,上述定义可以用文氏(John

12、 Venn)图描述如下,A,B,AB,AB,A,A-B,AB,A,A,B,A,B,A,B,由文氏图立得, A-B=AB, AB=(AB)-(AB,E,E,E,E,E,2021/3/5,北京林业大学信息学院 苏喜友,20,2 集合的运算,集合运算中优先于,-和, 后几种运算平级, 有括号先进行括号里的运算, 无括号按从左到右次序运算. Th.1 设E是全集, A,B,C是E的任意子集, 则下述等式成立. (1)交换律 AB=BA, AB=BA, AB=BA. (2)结合律 (AB)C=A(BC), (AB)C=A(BC), (AB)C=A(BC,2021/3/5,北京林业大学信息学院 苏喜友,2

13、1,2 集合的运算,3)分配律 A(BC)=(AB)(AC), A(BC)=(AB)(AC). (4)同一律 A=A, AE=A, A-=A, A=A. (5)零 律 A=, AE=E, A-A=, A-E=, AA=. (6)补余律 AA=E, 排中律 AA=. 矛盾律 (7)双否律 (A)=A,2021/3/5,北京林业大学信息学院 苏喜友,22,2 集合的运算,8)幂等律 AA=A, AA=A. (9)吸收律 A(AB)=A, A(AB)=A. (10)德摩根律 A-(BC)=(A-B)(A-C), A-(BC)=(A-B)(A-C), (BC)=BC, (BC)=BC, =E, E,2

14、021/3/5,北京林业大学信息学院 苏喜友,23,2 集合的运算,以上恒等式的证明主要用到命题演算的等值式. 基本思想是:欲证P=Q, 即证 PQQP, 也就是要证对任意的x有 xPxQxQxP 即 xPxQ. 一般, 要证明两个集合相等, 可以按照上述思路根据定义来证, 也可以根据已知的集合恒等式 证明,2021/3/5,北京林业大学信息学院 苏喜友,24,2 集合的运算,1.利用集合相等定义证明. Exp.1 AB=BA. 证明.对任意的x, xABxAxB xBxA xBA. 所以,x(xABxBA), 即 AB=BA,2021/3/5,北京林业大学信息学院 苏喜友,25,2 集合的运

15、算,Exp.2 证明:A-B=AB. 证.对任意x, xA-BxAxB xAxB xAB. 故 A-B=AB,2021/3/5,北京林业大学信息学院 苏喜友,26,2 集合的运算,Exp.3 证明 A-(BC)=(A-B)(A-C). 证.对任意的x, xA-(BC) xAxBC xA(xBC) xA(xBxC) xA(xB)(xC) xAxBxC xAxAxBxC (xAxB)(xAxC) xA-BxA-C x(A-B)(A-C). 故 A-(BC)=(A-B)(A-C,2021/3/5,北京林业大学信息学院 苏喜友,27,2 集合的运算,2.利用集合恒等式证明. Exp.4 证明 (AB)

16、(AB)=A. 证. (AB)(AB) =A(BB) =AE =A,2021/3/5,北京林业大学信息学院 苏喜友,28,2 集合的运算,Exp.5 已知AB=AC, 证明B=C. 证.因为 AB=AC, 所以 A(AB)=A(AC), (AA)B=(AA)C, B=C, 故 B=C,2021/3/5,北京林业大学信息学院 苏喜友,29,2 集合的运算,Exp.6 证明 (AB)-A=B-A. 证. (AB)-A =(AB)A =(AA)(BA) =(BA) =BA =B-A. 此外, 还有利用文氏图、用集合成员表和利用规定原理证明两集合相等等方法, 但都不很常用,2021/3/5,北京林业大

17、学信息学院 苏喜友,30,2 集合的运算,Exp.7 证明ACBCA-CB-CAB. 证.因为 ACBC A-CB-C 所以 (AC)(A-C)(BC)(B-C) (AC)(AC)(BC)(BC) A(CC)B(CC) AEBE 故 AB. 证明中利用了P1Q1P2Q2P1P2Q1Q2, 同时也有 P1Q1P2Q2P1P2Q1Q2,2021/3/5,北京林业大学信息学院 苏喜友,31,2 集合的运算,Th.2 设A和B是任意集合, 则以下四个命题等价： (1)AB; (2)AB=B; (3)AB=A; (4)A-B=. 证. (1)(2)(3)(4)(1,2021/3/5,北京林业大学信息学院

18、 苏喜友,32,2 集合的运算,1)AB(2)AB=B. 对任意x, xB, 则xAxB, 从而xAB, 故 BAB; 对任意x, xAB, 则xAxB, 由于AB, 所以总有xB, 故 ABB. 所以 AB=B,2021/3/5,北京林业大学信息学院 苏喜友,33,2 集合的运算,2)AB=B(3)AB=A. 因为 AB=B, 所以 AB=A(AB)=A. (3)AB=A(4)A-B=. A-B=AB=(AB)B=A(BB) =A=. (4)A-B=(1)AB. 任取xA, 若xB, 则xA-B, 与A-B=矛盾. 所以 xB, 故 AB,2021/3/5,北京林业大学信息学院 苏喜友,34

19、,2 集合的运算,Exp.8 在什么条件下等式(A-B)(A-C)=成立? 解. (A-B)(A-C)=A-(BC), 由Th.2知, A-(BC)=当且仅当ABC. 故(A-B)(A-C)=成立的充要条件是ABC,2021/3/5,北京林业大学信息学院 苏喜友,35,2 集合的运算,Exp.7 证明:ACBCA-CB-CAB. 证二. 因为 ACBC, A-CB-C, 所以 (AC)(BC)=AC, (A-C)(B-C)=A-C, ABC=AC, ABC=AC. 上述等式两边分别取并, 得 (ABC)(ABC)=(AC)(AC), (AB)(CC)=A(CC), (AB)E=AE, 即 AB=A, 故 AB,2021/3/5,北京林业大学信息学院 苏喜友,36,3 有穷集合的计数,Exp.1 对24名会外语的科技人员进行掌握外语情况的调查, 其统计结果如下:会英、日、德和法语的人分别为13、5、10和9人. 其中同时会英语和日语的有2人, 会英、德和法语中任两种语言的都是4人. 已知会日语的