离散第1讲集合的概念、交并补差幂集.ppt

《离散第1讲集合的概念、交并补差幂集.ppt》由会员分享，可在线阅读，更多相关《离散第1讲集合的概念、交并补差幂集.ppt（37页珍藏版）》请在三一办公上搜索。

1、,计算机专业基础课程,授课人：梁妍,离散数学的特点与学习要求,特点 离散性 抽象性 逻辑性 有难度要求 预习复习独立完成作业,PowerPoint Template_Sub,集合的概念与表示,集合运算,集合的归纳定义,PowerPoint Template_Sub,集合论是一门研究数学基础的学科，产生于16世纪末德国数学家康托（Georg Cantor,18451918）通过集合的直观定义开创了朴素集合论，被公认为集合理论的创始人1902年英国数学家罗素（Russell,18721970）证明朴素集合论导致悖论，随后为弥补这一缺陷出现了各种公理化集合论体系集合不仅可以表示数及其运算，更可以用于

2、非数值信息及离散结构的表示和处理。集合论的原理和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中,集合的概念、表示与基本运算,Page 1 to 7,离散数学第1讲,-6-,第一讲 集合的概念、表示与基本运算,内容提要,基础知识集合、元素的概念怎样表示一个集合（列举、描述）空集、全集、有限集、无限集外延性公理集合相等、子集、若干定理集合的基本运算并、交、差、补幂集运算,-7-,第一讲 集合的概念、表示与基本运算,何为集合？何为元素？,集合(sets)：指确定的、互相区别的、作整体识别的一些事物（对象）的全体。简称集。集合中的对象称为集合的元素(members)，或称为元、成员。

3、当某一个对象a 是集合A的成员时，就说“a属于A”，记成aA，当a 不是集合A的成员时，就说“a不属于A”，记成aA。对于任何对象a和任何集合A，a要么属于A，要么不属于A，二者必居其一。,-8-,第一讲 集合的概念、表示与基本运算,集合举例,师范大学全体学生师范大学所有班级 全体正整数1，2，3，4，偶质数的全体09计算机1班和他们本学期选修的所有课程所有长得像张三的人 中国所有著名导演方程x2-2 x+1=0 的根 方程x2+x+1=0 的根,-9-,第一讲 集合的概念、表示与基本运算,集合与元素,集合中的元素可以是任何具体或抽象的个体，也可以是集合A=1，2，1，2 集合与其成员是两个截

4、然不同的概念1 1 a a 通常用大写字母A,B,C表示集合，用小写字母a,b,c表示集合的元素（并非绝对）,-10-,第一讲 集合的概念、表示与基本运算,集合的表示方法,列举法（枚举法）a,b,c,秦始皇，汉武帝1,2,3,4,2,4,6,8,1,2,4,7,11,描述法 A=x|P(x)（A中的元素均满足性质P，而A以外的元素一个也不满足性质P）x A P(x)x|x是整数且x0、x|x2-2 x+1=0 x|x出生于大连、x|x是0到1区间的实数,-11-,第一讲 集合的概念、表示与基本运算,集合的表示方法,归纳法（以后介绍）文氏图（常用于表示集合之间的关系）,-12-,第一讲 集合的概

5、念、表示与基本运算,常用集合及其表示,0,1=x|x=0 或 x=1自然数集合（或非负整数的集合）N=0,1,2,3,整数集合I=,-2,-1,0,1,2,正整数集合I+=1,2,3,=x|x I 且 x 0,-13-,第一讲 集合的概念、表示与基本运算,常用集合及其表示,偶数集合E=,-4,-2,0,2,4,=x|x是偶数=x|x I 且 2|x 前n个自然数的集合Nn=0，1，2，,n-1=x|x N 且 x n,-14-,第一讲 集合的概念、表示与基本运算,常用集合及其表示,P：全体素数的集合Q：全体有理数的集合Q：全体正有理数的集合R：全体实数的集合 R：全体正实数的集合C：全体复数的

6、集合,-15-,第一讲 集合的概念、表示与基本运算,空集、有限集和无限集,定义1.1：没有任何元素的集合称为空集，记为，=。由全体对象组成的集合称为全集，记为U。定义1.2：只含有限多个元素的集合称为有限集；不是有限集的集合称为无限集。空集是有限集有限集合A中元素的个数称为A的基数(cardinality)，记为|A|空集的基数是0，即|=0,-16-,第一讲 集合的概念、表示与基本运算,空集、有限集和无限集举例,x|x=0 或 x=1自然数集合N正整数集合A=1，2，1，2 师范大学全体学生方程x2+x+1=0 的根,-17-,第一讲 集合的概念、表示与基本运算,外延性公理（extensio

7、nality axiom）,外延性公理：两个集合相等当且仅当这两个集合具有完全相同的成员。即对任意的集合A和B：A=B 当且仅当对任意元素x，x属于A则一定有x属于B；反之，x属于B也一定有x属于A。也就是说，集合A中的所有元素均是集合B中的元素，反之，B中的所有元素均是A中的元素例1.4 0,1=1,0=0,1,0=x|x(x2-2x+1)=0外延性公理事实上刻画了集合元素的无序性、相异性及集合表示形式的不唯一性,-18-,第一讲 集合的概念、表示与基本运算,子集合(subsets),定义1.3：设A，B为集合，若A中每一个元素都同时是B的元素，则称A是B的子集。即对于任意元素x，当x属于A

8、时一定有x属于B。表示为AB，读成A包含于B，或B包含A。任意集合A均是自己的子集，即：AA 若要说明A不是B的子集，只须在A中找到某一个元素x，使得xB即可 定义1.4：设A、B为集合，当AB且AB时，称A为B的真子集，记成AB。读做A真包含于B，或B真包含A,-19-,第一讲 集合的概念、表示与基本运算,包含关系 vs.隶属关系,包含集合与集合之间的关系1,2 1,2,3,41,2 1,2,3,4 a a隶属元素与集合之间的关系1 1,2,3,45 1,2,3,4a a,-20-,第一讲 集合的概念、表示与基本运算,关于子集的若干定理,定理1.1：对任何集合A，B，A=B当且仅当AB且BA

9、。对任何集合A，AA定理1.3：对于任何集合A，B，C，若AB，BC，则AC。证明：设x为A中任一元素，因为AB，所以xB；又因为BC，所以xC 这就是说，A中所有元素均属于C，所以有AC。,-21-,第一讲 集合的概念、表示与基本运算,关于子集的若干定理,定理1.2，1.4：对任意集合A，AU，A定理1.5：空集是唯一的证明：假设1,2都是空集，根据定理3，应该有 1 2 且2 1，从而由定理1知1=2。,-22-,第一讲 集合的概念、表示与基本运算,关于子集的若干定理,定理1.6：设A为一个有限集，且|A|=n，则A的子集个数为2n证明：集合A的子集最多有n个元素，最少有0个元素。0个元素

10、的子集共有C(n,0)个；1个元素的子集共有C(n,1)个；n个元素的子集共有C(n,n)个.因此，集合A共有子集C(n,0)+C(n,1)+C(n,n)=2n个。,-23-,第一讲 集合的概念、表示与基本运算,集合的运算,集合运算以集合作为运算对象，运算结果仍为集合的运算算术运算：3+5=8 46=24集合运算：1,22,3=2 1,22,3=1,2,3 有哪些集合运算交、并、差、补求幂运算广义并、交求笛卡尔积运算,-24-,第一讲 集合的概念、表示与基本运算,集合的并运算union（）,定义1.5：(1)设 A、B为任意集合，则由A、B的所有元素合在一起所组成的集合称为A与B的并集，记成A

11、B。即：AB=x|xA或xB x AB xA或xB例1.6U=0,1,2,9A=2,4,B=4,5,6,7,C=0,8,9,D=1,2,3AB，AC，CD，BD,-25-,第一讲 集合的概念、表示与基本运算,集合的交运算intersection（）,定义1.5：(2)设 A、B为任意集合，则由A、B的公共元素所组成的集合称为A与B的交集，记成AB。即：AB=x|xA并且xB x AB xA并且xB例1.6U=0,1,2,9A=2,4,B=4,5,6,7,C=0,8,9,D=1,2,3AB，AC，CD，BD,-26-,第一讲 集合的概念、表示与基本运算,集合的差运算difference（）,定义

12、1.5：(3)设 A、B为任意集合，则由在A中而不在B中的元素所组成的集合称为A对B的差，记成AB。即：A B=x|xA且xB x A B xA并且x B 例1.6U=0,1,2,9A=2,4,B=4,5,6,7,C=0,8,9,D=1,2,3AB，AC，CD，BD,-27-,第一讲 集合的概念、表示与基本运算,集合的补运算 complement（）,定义1.5：(4)设U为全集，A为任意集合，则所有在全集U中但不属于A的元素所组成的集合称为A的补集，记成A。即：A=x|xU且xA x A x A例1.6U=0,1,2,9A=2,4,B=4,5,6,7,C=0,8,9,D=1,2,3A，B，C

13、，D,-28-,第一讲 集合的概念、表示与基本运算,文氏图表示的集合并、交、差、补运算,A,AB,AB,AB,(AB)C,-29-,第一讲 集合的概念、表示与基本运算,关于并、交、差、补运算的一些直观结论,AA=A，A=A，AU=UAA=A，A=，AU=AA A=，A=A，A U=，A=A=U A，=U，U=，A=A AA=，AA=UA AB，B AB，AB A，AB B A B A若A B，则AB=B，AB=A，A B=若AB=，则A B=A,-30-,第一讲 集合的概念、表示与基本运算,关于交换律和结合律,交换律2+3=3+2，ab=baAB=BA，AB=BA一般而言，A B B A结合律

14、2+(3+5)=(2+3)+5，a(bc)=(ab)cA(BC)=(AB)CA(BC)=(AB)C一般而言，A(B C)(A B)C,-31-,第一讲 集合的概念、表示与基本运算,关于分配律和吸收率,分配律a(b+c)=ab+acA(BC)=(AB)(AC)A(BC)=(AB)(AC)A(BC)=(AB)(AC)一般而言，A(BC)(AB)(AC)吸收律A(AB)=AA(AB)=A,-32-,第一讲 集合的概念、表示与基本运算,关于并、交、差、补运算的几个定理,定理1.6：A(BC)=(A B)(A C)A(BC)=(A B)(A C)定理1.8：(AB)=AB(AB)=ABA B=AB证明

15、A(BC)=(A B)(A C)对任意x，x A(BC)x A 且x BC x A 且(xB或者xC)(xA且xB)或者(xA且xC)xA B或者xA C x(A B)(A C),-33-,第一讲 集合的概念、表示与基本运算,关于并、交、差、补运算的几个定理,定理1.10：A B，A B=，AB=B，AB=A 四命题等价定理1.11：对任意集合A、B，若它们满足1)AB=U2)AB=那么B=A证明：B=B=B(AA)=(BA)(BA)=U(BA)=(AA)(BA)=(AB)A=A=A第二种证法：相互包含,-34-,第一讲 集合的概念、表示与基本运算,集合幂运算,定义1.6：我们把集合A的所有子

16、集组成的集合称为A的幂集（power set），记成(A)，即(A)=x|xA例：A=2,4,B=4,5,6,7,C=(A),(B),(C),-35-,第一讲 集合的概念、表示与基本运算,幂集的性质,定理1.12：设A、B为任意集合，AB 当且仅当(A)(B)证明：先证必要性。假设AB，X是(A)中任一元素，则根据(A)定义，X A。由于AB，所以X B，从而X(B)。因此(A)(B)。再证充分性。假设(A)(B)，x是集合A中任一元素，则x A，根据(A)定义，x(A)。因为(A)(B)，所以x(B)，从而x B，进一步x B。因此AB。,-36-,第一讲 集合的概念、表示与基本运算,集合恒等式的证明方法,集合恒等式的证明大体上可以分为以下几种情况：根据外延公理利用自然语言叙述或等价式推演 利用已经得到证明的恒等式进行代换 利用前面的性质把恒等式的左边和右边都化成只含、三种运算的式子，看右边是否等于左边可以利用文氏图进行集合恒等式的验证,-37-,第一讲 集合的概念、表示与基本运算,本讲小结,主要内容集合和元素的概念集合的表示方法外延公理、子集合集合的并、交、差、补运算及相关性质集合幂运算作业P6.7、8P15.6（1）（2）、7、8,