《离散数学文档第三章.doc》由会员分享，可在线阅读，更多相关《离散数学文档第三章.doc（5页珍藏版）》请在三一文库上搜索。
1、第三章集合论集合论是现代数学的基础，是数学不可或缺的基本描述工具。可以这样讲，现代数学与离散数学的“大厦”是建立在集合论的基础之上的。集合论的研究起源于对数学的基础研究：对数学的对象、性质及其发生、发展的一般规律进行的科学研究。德国数学家康托尔从1874年始，发表了一系列集合论方面的著作，从而创立了集合论。在自然科学中，除了研究处于孤立的个体之外，更重要的是将一些相关的个体放在一起进行研究，这就直观地产生了引入集合这一概念的要求。随着计算机时代的到来，集合的元素已由传统的“数集”和“点集”拓展成包含文字、符号、图形、图表和声音等多媒体信息，构成了各种数据类型的集合。从而集合论在编译原理、开关理
2、论、信息检索、形式语言等各个领域得到了广泛的应用。3.1 集合一个集合是作为整体识别的、确定的、互相区别的一些事物的全体。严格地讲，这只是一种描述，不能算是集合的定义。类似于几何中的点、线、面等概念，在朴素集合论中，集合也是一种不加定义而直接引入的最基本的原始概念(一给出定义就要引入悖论)。而集合论中的其他概念，则都是从它出发给予了严格的定义。构成集合的每个事物称为这个集合的元素或成员。集合一般用大写字母表示，元素用小写字母表示。但这也不是绝对的，因为一个集合可以是另外一个集合的元素。例3.1.1英文字母的集合，C语言的基本字符集，全体实数，计算机内存单元集合。例3.1.21，2，32，1，3
3、3，1，2。例3.1.3常用集合：N，I(I，I)，P，Q(Q，Q)，R(R，R)，C。集合的表示：(1)枚举法；(2)性质描述法：Sx | P(x) ； (3)文氏图法：用于描述集合间的关系及其运算，其特点是直观、形象、信息量大且富有启发性。一般用矩形表示全集U，用圆表示U的子集A，B，C等等。集合中的事物称为集合的元素，通常用小写英文字母表示。如果x是集合S的一个元素，则称x属于S，记作xS；否则称x不属于S，记作xA。集合有三个重要的特性：互异性、无序性和确定性。例3.1.41N，0.5Q，3.0R，1N，Q。定义3.1.1 设A是任意集合，A中元素的个数称为A的基数或势，用|A|表示。
4、(1)基数为有限的集合称为有限集，否则称为无限集；(2)若A0，则称A为空集，记作或。否则称A是非空集合。例3.1.5N，I，Q，R，C都是无限集；大于3且小于1的整数集是空集，Hx | xR 且x2+x+1=0是空集；偶质数集是有限非空集。|=0，|0,1|=2，|=1，|N|=，|R|=。定义3.1.2 设A和B是两个集合。若A中的每个元素都是B的元素，则称A是B的子集或称B包含A、A包含于B，记作AB。若AB但AB，则称A为B的真子集，记作AB，B称为A的扩集或超集。空集是任何集合的子集(对任一集合A，有A)。对任一非空集合A，它至少有两个不同的子集和A，称它们为A的平凡子集。例3.1.
5、6NQRC。集合的包含关系有如下性质：(1)自反性：AA；(2)反对称性：AB，BAAB；(3)传递性：AB，BCAC。而集合的真包含关系则只有传递性：AB，BCAC。定义3.1.3 设 A和B是两个集合。若AB且BA，则称A与B相等，记为AB，否则称A与B不等，记为AB。例3.1.7Ax | x2-x=0 且xR，B0,1，则AB。例3.1.8判断下列命题的真假：，定义3.1.4 在一定范围内，若所有集合均为某一集合的子集，则称该集合为全集，记为U。3.2集合的运算3.2.1集合的运算定义3.2.1 设有集合A与B，则(1)称由A与B的公共元素组成的集合为A与B的交集，记作AB，即ABx |
6、 xA且xB。若AB，则称A与B不相交。(2)称由A与B的所有元素组成的集合为A与B的并集，记作AB，即ABx | xA 或xB。(3)称由属于A但不属于B的元素组成的集合为B对A的相对补集，记作AB，即ABx | xA且xB。特别地，若AU，则称UB为B的补集，记作。，。例3.2.1设A2，3，B1，5，8，C3，6，U1，10，求AB，CB，AB，BA，。定理3.2.1 (集合运算的性质)对全集U和任意集合A,B,C，有（1） AAB，BAB；ABA，ABB；（2） ABA；AB=A；（3） AC，BCABC；AB，ACABC；（4） AB。例3.2.2设A，B是任意集合，证明下列条件相互
7、等价：(1)AB；(2)ABB；(3)AAB。定义3.2.2 设A与B是集合，则称由属于A但不属于B的元素或属于B但不属于A的元素组成的集合为A与B的对称差，记作AB，即AB=x | (xA且xB)或(xB且xA)(AB)(BA)。例3.2.3设A2，3，B1，5，8，U1，10，求AB，BA，AA，A，UA。定义3.2.3 设A为一个集合，由A的所有子集作为元素组成的集合称为A的幂集，记为(A)(P(A)或2A)，即(A)SSA。例3.2.4()=，()=，(a)=，a；设A0，1，则(A)，0，1，0,1；设B=0,1,2，则(B)=,0,1,2,0,1,0,2,1,2,B。定理3.2.2
8、 设A和B都是集合，则(1)(A)，A(A)；A； (2)(A)(B)(AB)；(3)(AB)= (A)(B)；(4 )若A是有限集，则|(A)|=2A。3.2.1集合合恒等式关于集合的运算，有下列基本规律：交换律：ABBA，ABBA；结合律：(AB)CA(BC)，(AB)CA(BC)；分配律：(AB)C=(AC)(BC)，(AB)C(AC)(BC)；同一律：AAAUA;零一律：A，AUU；排中律：AU；矛盾律：A；等幂律：AAAAA；双否律：A；吸收律：AA；德摩根律：，；例3.2.5(1)设A，B，C都是集合，且ABAC，ABAC，则BC；(2)对任意集合A，B，证明：ABAB。3.3集合中元素的计数 容斥原理设A，B，C，(i=1,2,)都是有限集，则|AB|=|A+|B-|AB|;|ABC|=|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|;|=-+-+(-1)n-1。例3.3.1对100名大学生进行调查的结果是：34人爱下围棋，24人爱好美术，48人爱好音乐；13人既爱好围棋又爱好音乐，14人既爱好围棋又爱好美术，15人既爱好美术又爱好音乐；有25人没有任何一种爱好。问这三种爱好都有的大学生有多少个？例3.3.2求1到250间能被2，3，5，7其中任何一个整除的数的个数。5