《离散数学集合的基本概念和运算.ppt》由会员分享，可在线阅读，更多相关《离散数学集合的基本概念和运算.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第3章 集合的概念,集合的概念,集合是数学中最重要的概念，集合理论是数学中最重要的理论。 十九世纪七十年代，威尔斯特拉斯、戴德金、康托尔等人深入研究实数理论，建立起极限论的基本定理，不仅为微积分建立起严格的理论基础，也导致了集合论的诞生。 集合论分朴素集合论和公理化集合论。 集合论被广泛应用在计算机科学中，如数据结构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、CAD 等。,第 3 章 集合的概念与运算,一、什么是集合？ 只能给予直观的描述。所谓集合（Set），就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的一个整体。 组成集合的各个对象，称为
2、这个集合的元素（Element）或成员（Member）。 通常，用大写字母A，B，C，表示集合，用小写字母a，b，c，表示元素。 集合与元素之间的关系“属于”关系 aA aB,3.1 集合的基本概念,二、集合的表示 列举法 将集合中的元素一一列举出来，或者列出足够多的元素以反映集合中成员的特征，并用花括号将元素括起来，其表示形如： A=a1，a2，an A=a1，a2，a3, 列举法必须把元素的全体尽列出来，不能遗漏任何一个，并且集合中的元素没有顺序之分且不重复。,3.1 集合的基本概念,谓词表示法 用一个谓词来描述集合中元素具有的共同性质。 表示形式如A=x|P(x) 意义是： 集合A 由且
3、仅由满足性质P 的那些对象所组成，也就是说aA 当且仅当a 满足性质P。,3.1 集合的基本概念,练习,2,3,5,7,11,13,17,19 -3,-1,1,3,2x|xZ且x100 2n|nN且n10,3.1 集合的基本概念,集合与元素,元素与集合的关系：隶属关系 属于，不属于 实例 A= x | xRx2-1=0 , A=-1,1 1A, 2A 注意：对于任何集合A和元素x(可以是集合)， xA和 xA 两者成立其一，且仅成立其一.,隶属关系的层次结构,例 3.1 A= a, b,c, d, d b,cA bA dA dA dA,包含（子集） A B x (xA xB) 不包含 A B
4、x (xA xB) 相等 A = B A B B A 不相等 A B 真包含 A B A B A B 不真包含 A B 思考： 和 的定义 注意 和 是不同层次的问题,一、集合之间的关系,例1 A=a, b, c, d, B=a, e, x, y, z, C=a, x 则 C B，C A，B A， A B,3.1 集合的基本概念,集合的包含关系具有如下几条性质：,对任意集合A，A； 自反性：AA 反对称性：若AB且BA，则AB 传递性：若AB且BC，则A C 若|A|n，则A有2n个子集,3.1 集合的基本概念,空集与全集,空集 不含任何元素的集合 实例 x | x2+1=0 xR 就是空集
5、定理 空集是任何集合的子集 A x (xxA) T 推论 空集是惟一的. 证 假设存在1和2，则12 且12，因此 1=2 全集 在一个具体问题中，如果所涉及的集合都是某个 集合的子集，则称这个集合为全集，记作E 全集具有相对性 在给定问题中，全集包含任何集合，即A (AE ),三、幂集（PowerSet） 定义1.2.2 给定集合A，以A的所有子集为元素的集合称为A的幂集，记作P(A)。 例3 A=，B=，a，a P（A） P（B），a，a，a，a，a，a，a，a,3.1 集合的基本概念,集合的基数 设A 为任一集合，用|A|(或#A)表示A中不同元素的个数，称为集合A的基数，有： 若|A|
6、=0，则称A 为空集合（Empty Set），记为； 若|A|为某自然数，则称A 为有限集合（Finite Set）； 若|A|为无穷，则称A 为无限集合（Infinite Set）,3.1 集合的基本概念,:,:a1,a2 ,an,:a1, a2,a1, a3 ,:a1, a2 , , an,证明 设A= a1, a2 , , an,从n个元素中选 取m个元素的方法有 种，所以A的子集 个数为,注：设A是有限集，则 .,3.1 集合的基本概念,练习1 设A=a,b,c,a,a,b，试指出下列论断是否正确？ (1)aA ( ) (8)bA ( ) (2)aA ( ) (9)a,bA ( ) (
7、3)aA ( ) (10)a,bA ( ) (4)A ( ) (11)cA ( ) (5)A ( ) (12)cA ( ) (6)bA ( ) (13)cA ( ) (7)bA ( ) (14)a,b,cA ( ),3.1 集合的基本概念,练习2 列出集合A=1,2的全部子集。 解 因为是任何集合的子集，所以是A的子集。由A中任意一个元素所组成的集合是A的子集，所以1和2是A的子集。由A中任意两个元素所组成的集合是A的子集，所以1,2是A的子集。因为A中只有两个元素，故A再没有其他的子集。 由上可知，A有四个子集：，1，2，1,2。,典型习题,练习3 设有集合A,B,C和D, 下述论断是否正确
8、？说明理由。 （1）若AB,BC,则AC 解 正确。因为BC，所以集合B的每一个元素也是集合C的元素，由AB知A是B的一个元素，因此A也是C的一个元素，故AC。 （2）若AB,BC,则AC 解 错误。举反例如下：设A=a，B=a,b，C=a,b,c，显然AB，BC，但A不是C的子集。因为aA，但aC。,典型习题,例1.3.1 设A=a,b,c, B=c,d,f , C=b,e,则,A,B,定义3.7 A、B是任意集合，由属于A或属于B的所有元素组成的集合称为A与B的并集，记作 。即,显然：,3.2集合的基本运算,例1.3.2 设A=a,b,c,d, B=d,f,a, C=e,f,g,则,显然：,定义3.7 设有A、B是任意两个集合，属于A同时又属于B的所有元素组成的集合称为A与B的交集，记作 。即,3.2集合的基本运算,定义3.7 设A、B是任意两个集合，所有属于A而不属于B的元素组成的集合，称为B对A的相对补集，记作A-B。即,例1.3.3 设A=a,b,c,d, B=d,f,a, C=e,f,g,重要性质：,3.2集合的基本运算,定义3.8 E为全集，A为E的子集，E-A称为A的绝对补集，记作 。即,3.2集合的基本运算,例如 设U=1，2，3，4，10， A=2，4，6，8，10,则,又例如 设U=I（I是整数集），,则,3.2集合的基本运算,