《CH3集合的基本概念和运算》由会员分享，可在线阅读，更多相关《CH3集合的基本概念和运算（59页珍藏版）》请在金锄头文库上搜索。
1、离散数学CH3 集合的基本概念和运算集合论简介康托(Georg Cantor，1845-1918)是集合 论的创始人，为数学引入了集合和无限 两个新事物。集合论是数学中许多分支的基础，是整 个大厦的基础，是许多计算机科学理论 不可或缺的工具。从历史上来看，1900 年之前的数学几乎没有集合论的容身之 地。当时的学术论文，文摘杂志上，集 合论都被作为哲学的一部分。集合不仅可以用来表示数及其运算，更可 以用于非数值信息的表示和处理，如数据 的删除、排序、插入、数据间的关系描述 。第3章 集合的基本概念和运算集合是数学、计算机科学以及其他科学 的最基础的知识之一 本章学习：集合的基本概念和基本运算1
2、集合的基本概念2集合的基本运算3集合中元素的计数 3.1集合的基本概念康托关于集合的描述：集合是一些确定的、不同的事物的总 体，这些事物人们可以意识到，并且能判断一个给定的事物是 否属于这个总体。集合是由某些相互区别的事物汇集在一起组成的整体。例 (1) 所有偶数构成一个集合。 (2) 所有在20世纪80年代出生的人构成一个集合。 (3) 亚洲的国家的全体构成一个集合。 (4) 方程x2-1=0的全体实数解集合。 (5) 26个英文字母的集合。 (6) 计算机内存的全体单元的集合。3.1集合的基本概念集合是不能精确定义的、基本的数学概念一般认为一个集合指的是一些可确定、可分 辨的事物构成的整体
3、对于给定的集合和事物，应该可以断定这个特定 的事物是否属于这个集合 如果属于，就称它为这个集合的元素集合的符号表示 集合通常用大写英文 字母表示。元素通常用小写字母 表示。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，55，4，3
4、都是同一个集合集合的表示方法列举法（穷举法）：把一个集合中的所有或者 部分元素列举在花括号当中，元素之间用逗号 隔开。例如：A=0, 1, , 100A= 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是自然数, x100x|x5+x4+x3+x+1=0B=x|x Z 3x6一般说来，集合的元素可以是任何类型的事物一个集合也可以作为另一个集合的元素 例如，集合 A= a, b,c
5、, d, d aA, b,cA, dA, d A b,c, d本身也是集合但，b A, d Ab是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由以上定义可以
6、知道，两个集合相等的充分 必要条件是它们具有相同的元素例如，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)右边的蕴涵式
7、中，因前件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个
8、： a,b,c 2元子集，有C32个：a,b,a,c,b,c 3元子集，有C33个：a,b,cA的子集共有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且
9、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|xAxBA B
10、 =x|xAxBAB=x|xAx BA 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 AA B=3= B AB C= AB=1，4BA=2CA=当两个集合的交集是空集时，称它们是不相交 的。 交运算和并运算的扩展 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,20,1 1,2 1,3= 1
11、定义 (绝对补集):设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,3A与B的对称差也可等价地定义为AB=（A B）（A B）这时，对于上例，有AB=0,1,2,32=0,1,3课堂练习P72 3.1 集合的算律任何代数运算都遵从一定的算律（恒等式 ），集合运算也不例外下面列出的是集合运算的主要算律，其中 的A，B，C表
12、示任意的集合，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 = AAE = A 零律 AE = EA = 排中律 AA = E 矛盾律 AA= 吸收律 A（AB）=AA（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有
13、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其次在矩形内画一些圆或任何其它的适合的闭曲 线，用圆的内部表示集合通常在图中画有阴影的区域表示新组成的集合在一般情况下，如果不作特殊的说明，这些表 示集合的圆应该是彼此相交的如果已知某两个集合是不交的，则表示它们的 圆彼此相离例:
