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的元素，记作aA，否则记为aA集合的特点,一个集合的元素有如下特点： (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的元素，记作a∈A同样有b∈A，c∈A，d∈A但e不是A的元素，可记作e A,集合的表示方法,描述法（谓词表示法）：用一个谓词公式P(x)表示x具有性质P，用{x|P(x)}表示所有具有性质P的事物组成的集合例如：{x| |x-2| ≤1, x是实数}{x|x是自然数, x≤100} {x|x5+x4+x3+x+1=0}B={x|x ∈ Z  3

这时也称B被A包含，或A包含B记作：B  A 包含的符号化表示为：B  A x(x∈ Bx∈ 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=BA  BB  A 如果A和B不相等，则记作A≠B 由以上定义可以知道，两个集合相等的充分必要条件是它们具有相同的元素 例如，A={x|x是小于等于3的素数}B={x|x|x=2∨x=3}则A=B,,定义（真子集）设A，B为集合，如果B  A且B≠A，则称B是A的真子集，记作B  A 例如，{0，1}是{0，1，2}的真子集但{1，3}和{0，1，2}都不是{0，1，2}的真子集,空集:不含任何元素的集合叫做空集，记作空集可以符号化表示为:={x|x≠x}Ø={x|P(x)∧﹁P(x)}空集是客观存在的，例如:A={x|x∈R∧x2+1=0}是方程x2+1=0的实数解集因为该方程没有实数解，所以A=,集合的简单性质: 定理3.1 空集是一切集合的子集。

证明: 任给集合A，由子集定义有⊆A  x(x∈x∈A)右边的蕴涵式中，因前件x∈为假，所以整个蕴涵式对一切x为真推论 空集是唯一的 证明: 假设存在空集1和2，由定理3.1，有1⊆2和2⊆1，根据集合相等的定义得1=2例3.1 确定下列命题是否为真1）⊆；（2）∈；（3）⊆{}；（4）∈{} 解: （1），（3），（4）为真，（2）为假注意和{}的区别：不含任何元素； {}含唯一一个元素集合的其他一些概念 :含有n个元素的集合简称n元集，它的含有m个（m≤n）元素的子集称作它的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(0≤m≤n)元子集有Cnm个所以不同的子集总数为:Cn0+Cn1+…+Cnn=2n定义（幂集）设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)，或PA，或2A。

符号化表示为:P(A)={x|x⊆A} 若A有n个元素，则P(A)有2n个元素 例，设A={a,b,c}，则 P(A)={,{a},{b},{c}，{a,b},{a,c},{ b,c},{ a,b,c }},练习,判断下列表达式是否成立： x{x}, {x}{x}, {x}{x}, x{{x}}, {x}{{x}}, {x}{{x}}, Ø{x}, Ø{x}, 是否存在集合A, B满足AB且AB 下列集合是否为某集合的幂集？ (1) Ø; (2) {a, Ø}; (3) {Ø, {a}}; (4) {Ø, {a}, {Ø,a}},,,定义（全集）在一个具体问题中，如果所涉及的集合都是某个集合的子集则称这个集合为全集，记作E（或U） 全集是个相对性的概念由于所研究的问题不同，所取的全集也不同 例如，研究平面解析几何的问题时把整个坐标平面取作全集，研究整数的问题时，把整数集取作全集,3.2集合的基本运算,给定集合A和B，可以通过集合的并∪，交∩ ，相对补—，绝对补~，以及对称差⊕等运算产生新的集合,定义（并、交、相对补）设A，B为集合，A与B的并集A∪B，交集A∩B，B对A的相对补集A-B分别定义如下：A∪ B={x|x∈A∨x∈B}A∩ B ={x|x∈A∧x∈B}A－B={x|x∈A∧x B} A∪ B由A或B中的元素构成 A∩ B由A和B中的公共元素构成 A－B 由属于A但不属于B中的元素构成,例: A={1，3，4}，B={2，3}，C={4}则有A ∪ B={1，2，3，4}= B ∪ AA ∩ B={3}= B ∩ AB ∩ C= A—B={1，4}B—A={2}C—A=当两个集合的交集是空集时，称它们是不相交的。

交运算和并运算的扩展 n个集合A1，A2，…，An的并集和交集定义如下: A1∪A2∪ …∪An={x|x∈A1∨x∈A2∨…∨x∈An} 简记为: ∪ i=1nAi A1∩A2∩…∩ An={x|x∈A1∧x∈A2∧…∧x∈An} 简记为: ∩ 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=E－A = {x|x∈E∧x  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的对称差是:A⊕B = (A－B)∪(B－A) 例:A={0,1,2},B={2,3} 则A⊕B={0,1}∪{3}={0,1,3},,A与B的对称差也可等价地定义为A⊕B=（A∪ B）－（A∩ B） 这时，对于上例，有A⊕B={0,1,2,3}－{2}={0,1,3},课堂练习,P72 3.1,集合的算律,任何代数运算都遵从一定的算律（恒等式），集合运算也不例外 下面列出的是集合运算的主要算律，其中的A，B，C表示任意的集合，E是全集,幂等律 A∪A=A A∩A=A 结合律 （A∪B)∪C = A∪（B∪C）(A∩B)∩C = A∩（B∩C） 交换律 A∪B=B∪A A∩B=B∩A 分配律 A∪（B∩C）=（A∪B）∩（A∪C） A∩（B∪C）=（A∩B）∪（A∩C） 同一律 A∪ = AA∩E = A 零律 A∪E = EA∩ = ,排中律 A∪~A = E 矛盾律 A∩~A= 吸收律 A∪（A∩B）=AA∩（A∪B）=A 双重否定律 ~（~A）=A德.摩根律 ~ A∪B）= ~ A∩ ~ B ~ （A∩B）= ~ A∪ ~ B~ =E~ E=A-（B∪C）=（A-B）∩（A-C） A-（B∩C）=（A-B）∪（A-C）,恒等式及集合相等的证明方法,之一 证明的基本思想是：欲证P=Q，即证：P  Q∧Q  P也就是要证明对任意的x有x∈P  x∈Q,例:证明 A-（B∪C）=（A-B）∩（A-C） 即证对 x, x∈A-(B∪C)  x∈(A- B)∩(A-C) 证：x∈A-(B∪C) x∈A∧x ∉ B∪C x∈A∧﹁(x ∈B∪C) x∈A∧﹁(x ∈B∨x ∈C) x∈A∧(﹁x ∈B∧﹁x ∈C) x∈A∧ x ∉ B ∧ x ∉ C (x∈A∧x ∉ B )∧ (x∈A∧x ∉ C) x∈A-B ∧ x∈A-C x∈(A- B) ∩(A-C) ∴ A-(B∪C)=(A-B)∩(A-C),恒等式及集合相等的证明方法,之二：利用已知算律证明例: 证明（A－B）∪B = A∪B证:（A－B）∪ B =（A∩~B）∪B=（A∪B）∩（~B∪B）=（A∪B）∩E= A∪B,除以上所给的算律以外，还有一些关于集合运算性质的重要结果 A∩B⊆A,A∩B⊆B A⊆A∪B,B⊆A∪B A-B⊆A A∪B=B  A⊆B  A∩B=A  A-B= A-B=A ∩ ~ B A-B=A-(A ∩ B),文氏图,集合之间的相互关系和有关的运算可以用文氏图给予形象的描述 文氏图的构造方法如下: 首先画一个大矩形表示全集E 其次在矩形内画一些圆或任何其它的适合的闭曲线，用圆的内部表示集合 通常在图中画有阴影的区域表示新组成的集合 在一般情况下，如果不作特殊的说明，这些表示集合的圆应该是彼此相交的 如果已知某两个集合是不交的，则表示它们的圆彼此相离,例:用文氏图表示下面集合 (1) ~ A∪(B∩C) (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名熟悉这两种语言问有多少人对这两种语言都不熟悉？ 常用方法：文氏图、容斥原理,。