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

《《离散数学》集合的基本概念和运算.ppt》由会员分享，可在线阅读，更多相关《《离散数学》集合的基本概念和运算.ppt（51页珍藏版）》请在三一办公上搜索。

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 由且仅由满足性质P 的那些对象所组成，也

3、就是说aA 当且仅当a 满足性质P。,3.1 集合的基本概念,练习,2,3,5,7,11,13,17,19-3,-1,1,3,2x|xZ且x1002n|nN且n10,3.1 集合的基本概念,集合与元素,元素与集合的关系：隶属关系 属于，不属于 实例 A=x|xRx2-1=0,A=-1,1 1A,2A注意：对于任何集合A和元素x(可以是集合)，xA和 xA 两者成立其一，且仅成立其一.,隶属关系的层次结构,例 3.1A=a,b,c,d,d b,cAbAdAdAdA,包含（子集）A B x(xA xB)不包含 A B x(xA xB)相等 A=B A B B A 不相等 A B 真包含 A B A

4、 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 就是空集定理 空集是任何集合的子集 A x(xxA)T 推论 空集是惟一的.证 假设存在1和2，则12 且12，因此 1=2全集 在一个

5、具体问题中，如果所涉及的集合都是某个 集合的子集，则称这个集合为全集，记作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|=0，则称A 为空集合（Empty Set），记为；若|A|为某自然数，则称A 为有限集合（Finite Set）；若|A|为无穷，则称A 为无限集

6、合（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()(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的全部

7、子集。解 因为是任何集合的子集，所以是A的子集。由A中任意一个元素所组成的集合是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的子集

8、。因为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集合的基本运算,例 设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。即,例 设A=a,b,c,d,B=d,f,a,C=e,f,g,重要性

9、质：,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集合的基本运算,定义1.4.1 A、B为任意两个集合，所有属于A而不属于B或属于B而不属于A的元素组成的集合，称为A与B的对称差，记作。即,3.2集合的基本运算,关于运算的说明,运算顺序：和幂集优先，其他由括号确定并和交运算可以推广到有穷个集合上，即 A1A2An=x|xA1xA2xAn A1A2An=x|xA1xA2xAn某些重要结果 ABA AB AB=（后面证明）

10、AB=AB=A,只有一、二年级的学生才爱好体育运动,F:一年级大学生的集合 S：二年级大学生的集合 R：计算机系学生的集合 M：数学系学生的集合 T：选修离散数学的学生的集合 L：爱好文学学生的集合 P：爱好体育运动学生的集合,T(MR)S,RS T,(MF)T=,MLP,PFS,S(MR)P,除去数学和计算机系二年级学生外都不选修离散数学,例,所有计算机系二年级学生都选修离散数学,数学系一年级的学生都没有选修离散数学,数学系学生或爱好文学或爱好体育运动,例,=S2,=S5,=S1,S2,S4,=S3,S5,与 S1,.,S5 都不等,3.2集合的基本运算,一、集合运算的十条定律,对于全集合E

11、的任意子集A、B、C，有：,交换律,结合律,分配律,恒等律,3.2集合的基本运算,互补律,否定律,幂等律,零一律,吸收律,德摩根律,对偶原理：把一个等式中的中的，E和的分别代以，和E后得到另一等式,3.2集合的基本运算,二、对称差运算的性质：,AA=A=A A E=A BB A,3.2集合的基本运算,三、集合包含的证明方法,证明 XY命题演算法包含传递法等价条件法反证法并交运算法,3.2集合的基本运算,3.1.命题演算法证 XY,任取 x，xX xY,证明：AB P(A)P(B)任取x xP(A)xA xB xP(B)任取x xA xA xP(A)xP(B)xB xB,3.2.包含传递法证 X

12、Y,找到集合T 满足 XT 且 TY，从而有XY。例4 AB AB证 AB A A AB 所以 AB AB,3.3.利用包含的等价条件证 XY,例5 ACBC ABC 证 AC AC=C BC BC=C(AB)C=A(BC)=AC=C(AB)C=C ABC 命题得证,3.4.反证法证 XY,欲证XY,假设命题不成立，必存在 x 使得 xX 且 xY.然后推出矛盾.例6 证明 AC BC ABC证 假设 AB C 不成立，则 x(xABxC)因此 xA 或 xB，且 xC 若 xA,则与 AC 矛盾；若 xB,则与 BC 矛盾.,3.5.利用已知包含式并交运算,由已知包含式通过运算产生新的包含式

13、 XY XZYZ,XZYZ 例7 证明 ACBC ACBC AB证 ACBC，AC BC 上式两边求并，得(AC)(AC)(BC)(BC)(AC)(AC)(BC)(BC)A(CC)B(CC)AE BE A B,四、集合相等的证明方法,证明 X=Y命题演算法等式代入法反证法运算法,例8 证明 A(AB)=A（吸收律）证 任取x,xA(AB)xA xAB xA(xA xB)xA,4.1 命题演算法证明X=Y,任取 x，xX xY xY xX 或者 xX xY,4.2.等式替换证明X=Y,例9 证明A(AB)=A（吸收律）证(假设交换律、分配律、同一律、零律成立)A(AB)=(AE)(AB)同一律=

14、A(EB)分配律=A(BE)交换律=AE 零律=A 同一律,不断进行代入化简，最终得到两边相等,3.2集合的基本运算,4.3.反证法证明X=Y,例10 证明以下等价条件 AB AB=B AB=A AB=(1)(2)(3)(4)证明顺序：(1)(2),(2)(3),(3)(4),(4)(1),假设 X=Y 不成立，则存在 x 使得 xX且xY，或者存在 x 使得 xY且xX，然后推出矛盾.,(1)(2)显然BAB，下面证明ABB.任取x，xAB xAxB xBxB xB因此有ABB.综合上述（2）得证.,(2)(3)A=A(AB)A=AB（将AB用B代入),3.2集合的基本运算,(3)(4)假设

15、AB,即xAB，那么xA且xB.而 xB xAB.从而与AB=A矛盾.,(4)(1)假设AB不成立，那么 x(xA xB)xAB AB与条件（4）矛盾.,4.4.集合运算法证明X=Y,例11 证明AC=BC AC=BC A=B证 由 AC=BC 和 AC=BC 得到(AC)-(AC)=(BC)-(BC)从而有 AC=BC A=B（消去律）因此 AC=BC(AC)C=(BC)C A(CC)=B(CC)A=B A=B,由已知等式通过运算产生新的等式 X=Y XZ=YZ,XZ=YZ，X-Z=Y-Z,3.2集合的基本运算,集合 A 的基数：集合A中的元素数，记作 cardA有穷集 A：cardA=|A

16、|=n，n为自然数.有穷集的实例：A=a,b,c,cardA=|A|=3；B=x|x2+1=0,xR,cardB=|B|=0 无穷集的实例：N,Z,Q,R,C 等,集合的基数与有穷集合,3.3集合的计数,包含排斥原理,定理 设 S 为有穷集，P1,P2,Pm 是 m 种性质，Ai 是 S 中具有性质 Pi 的元素构成的子集，i=1,2,m.则 S 中不具有性质 P1,P2,Pm 的元素数为,3.3集合的计数,S中至少具有一条性质的元素数为,推论,3.3集合的计数,解：S=x|xZ,1 x 1000,如下定义 S 的 3 个子集 A,B,C：A=x|xS,5|x，B=x|xS,6|x，C=x|x

17、S,8|x,例1 求1到1000之间（包含1和1000在内）既不能被 5 和6 整除，也不能被 8 整除的数有多少个？,应用,3.3集合的计数,对上述子集计数：|S|=1000,|A|=1000/5=200,|B|=1000/6=166，|C|=1000/8=125,|AB|=1000/30=33,|BC|=1000/40=25,|BC|=1000/24=41,|ABC|=1000/5,6,8的最小公倍数 1000/120=8,代入公式 N=1000(200+166+125)+(33+25+41)8=600,例1（续）,3.3集合的计数,文氏图法,求1到1000之间（包含1和1000在内）既不

18、能被 5 和6 整除，也不能被 8 整除的数有多少个？,|ABC|=1000/120=8,先填入相应区域。|AB|=33,|BC|=25,|BC|=41；再填入相应区域。,|A|=200,|B|=166，|C|=125,再填入相应区域。则|A B C|400从而结论为600,3.3集合的计数,例2 24名科技人员，每人至少会1门外语.英语：13；日语：5；德语：10；法语：9英日：2;英德：4；英法：4；法德：4会日语的不会法语、德语求：只会 1 种语言人数，会 3 种语言人数,x+2(4-x)+y1+2=13x+2(4-x)+y2=10 x+2(4-x)+y3=9x+3(4-x)+y1+y2

19、+y3=19x=1,y1=4,y2=3,y3=2,3.3集合的计数,关于集合运算的计数还有：|A1A2|A1|+|A2|A1A2|min(|A1|,|A2|)|A1-A2|A1|-|A2|A1A2|=|A1|+|A2|-2|A1A2|对包含排斥原理，重点有：|AB|A|+|B|AB|；|ABC|A|+|B|C|AB|AC|-|BC|+|A B C|特点：(1)n-1|A1 A2.An|,3.3集合的计数,例、在某工厂装配30辆汽车，可供选择的设备是收音机、空气调节器和对讲机。已知其中15辆汽车有收音机，8辆汽车有空气调节器，6辆汽车有对讲机，而其中3辆汽车这三样设备都有。请问至少有多少辆汽车没有提供任何设备？解 设A1、A2和A3分别表示配有收音机、空气调节器和对讲机的汽车集合。因此，|A1|=15,|A2|=8,|A3|=6 并且|A1A2A3|=3 故:,因为,得到,即至多有23辆汽车有一个或几个供选择的设备，因此至少有7辆汽车不提供任何可选择的设备。,3.3集合的计数,