《离散数学》集合的基本概念和运算

资源描述

《《离散数学》集合的基本概念和运算》由会员分享，可在线阅读，更多相关《《离散数学》集合的基本概念和运算（51页珍藏版）》请在金锄头文库上搜索。

1、第3章集合的概念集合的概念集合是数学中最重要的概念，集合理论是数学中最重要的理论。十九世纪七十年代，威尔斯特拉斯、戴德金、康托尔等人深入研究实数理论，建立起极限论的基本定理，不仅为微积分建立起严格的理论基础，也导致了集合论的诞生。集合论分朴素集合论和公理化集合论。集合论被广泛应用在计算机科学中，如数据结构、操作系统、数据库、知识库、编译原理、形式语言、程序设计、人工智能、信息检索、CAD 等。第第3 3章章集集合合的的概概念念与与运运算算一、什么是集合？-只能给予直观的描述。所谓集合（Set ），就是把人们直观的或想象中的某些确定的能够区分的对象汇合在一起组成的

2、一个整体。-组成集合的各个对象，称为这个集合的元素（Element）或成员（Member）。通常，用大写字母A，B，C，表示集合，用小写字母a，b，c，表示元素。集合与元素之间的关系“属于”关系- aA aB3.1 集合的基本概念二、集合的表示列举法-将集合中的元素一一列举出来，或者列出足够多的元素以反映集合中成员的特征，并用花括号将元素括起来，其表示形如：A=a1，a2，an A=a1，a2，a3, -列举法必须把元素的全体尽列出来，不能遗漏任何一个，并且集合中的元素没有顺序之分且不重复。3.1 集合的基本概念谓词表示法-用一个谓词来描述集合中元

4、 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 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 B3.1 集合的基本概念集

5、合的包含关系具有如下几条性质：对任意集合A，A；自反性：AA反对称性：若AB且BA，则AB传递性：若AB且BC，则A C若|A|n，则A有2n个子集3.1 集合的基本概念空集与全集空集不含任何元素的集合实例 x | x2+1=0xR 就是空集定理空集是任何集合的子集A x (xxA) T 推论空集是惟一的. 证假设存在1和2，则12 且12，因此 1=2 全集在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E全集具有相对性在给定问题中，全集包含任何集合，即A (AE )三、幂集（PowerSet）定义1.2.2 给定集合A，以A的

6、所有子集为元素的集合称为A的幂集，记作P(A)。例3 A=，B=，a，aP（A）P（B），a，a，，a，a，a，a， a，a3.1 集合的基本概念集合的基数设A 为任一集合，用|A|(或#A)表示A中不同元素的个数，称为集合A的基数，有：若|A|=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 ,

7、, an,从n个元素中选取m个元素的方法有种，所以A的子集个数为注：设A是有限集，则 .3.1 集合的基本概念练习1 设A=a,b,c,a,a,b，试指出下列论断是否正确？(1)aA ( ) (8)bA ( )(2)aA ( ) (9)a,bA ( )(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中任

8、意一个元素所组成的集合是A的子集，所以1和2是A的子集。由A中任意两个元素所组成的集合是A的子集，所以1,2是A的子集。因为A中只有两个元素，故A再没有其他的子集。由上可知，A有四个子集：，1， 2，1,2。典型习题练习3 设有集合A,B,C和D, 下述论断是否正确？说明理由。（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 。典

9、型习题例1.3.1 设A=a,b,c, B=c,d,f , C=b,e则 AB定义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则显然： AB定义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

10、, B=d,f,a, C=e,f,g 则B-A= f , C-A= e ,f , g =C BA重要性质：3.2 集合的基本运算A定义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 集合的基本运算定义1.4.1 A、B为任意两个集合，所有属于A而不属于B或属于B而不属于A的元素组成的集合，称为A与B的对称差对称差，记作。即AB3.2 集合的基本运算关于运算的说说明运算顺序：和幂集优先，其他由括

11、号确定并和交运算可以推广到有穷个集合上，即A1A2An= x | xA1xA2xAn A1A2An= x | xA1xA2xAn某些重要结果 ABAAB AB=（后面证明）AB= AB=A只有一、二年级的学生才爱好体育运动F:一年级大学生的集合 S：二年级大学生的集合R：计算机系学生的集合 M：数学系学生的集合T：选修离散数学的学生的集合L：爱好文学学生的集合 P：爱好体育运动学生的集合T(MR)SRS T(MF)T=MLPPFSS(MR)P除去数学和计算机系二年级学生外都不选修离散数学例所有计算机系二年级学生都选修离散数学数学系一年级的学生都没有选修离散数学数学系学生或爱好文学或爱好体育运

12、动例分别对条件(1)到(5)，确定 X 集合与下述那些集合相等。 S1 = 1, 2, , 8, 9 , S2= 2, 4, 6, 8 , S3= 1, 3, 5, 7, 9 , S4 = 3, 4, 5 , S5= 3, 5 (1) 若 XS5=, 则 X(2) 若 XS4, XS2=, 则 X(3) 若 XS1，X S3, 则 X(4) 若 XS3=, 则 X(5) 若 XS3，X S1, 则 X= S2= S5= S1, S2, S4= S3, S5与 S1, . , S5 都不等3.2 集合的基本运算一、集合运算的十条定律一、集合运算的十条定律对于全集合E的任意子集A、B

13、、C，有：交换律结合律分配律恒等律3.2 集合的基本运算互补律否定律幂等律零一律吸收律德摩根律对偶原理：把一个等式中的中的，E和的分别别代以，和E后得到另一等式3.2 集合的基本运算二、对称差运算的性质：二、对称差运算的性质： AA= A =A A E=A BB A3.2 集合的基本运算三、集合包含的证明方法证明 XY-命题演算法-包含传递法-等价条件法-反证法-并交运算法3.2 集合的基本运算3.1.命题演算法证 XY任取 x ，xX xY证明：AB P(A)P(B)任取xxP(A) xA xB xP(B)任取xxA xA xP(A) xP(B) xB xB 3.2.包含传递法证 XY找到集合T 满足 XT 且 TY，从而有XY。例4 AB AB 证 AB A A AB所以 AB AB3.3.利用包含的等价条件证 XY例5 ACBC ABC 证 AC AC=C BC BC=C (AB)C=A(BC)=A

展开阅读全文