《离散数学 第2版 教学课件 ppt 作者 王元元 离散第1讲》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第1讲（36页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,指挥自动化学院 计算机理论教研室 王 元 元,PowerPoint Template_Sub,集合的概念与表示,集合运算,集合的归纳定义,PowerPoint Template_Sub,集合论是一门研究数学基础的学科，产生于16世纪末 德国数学家康托（Georg Cantor, 18451918）通过集合的直观定义开创了朴素集合论，被公认为集合理论的创始人 1902年英国数学家罗素（Russell, 18721970 ）证明朴素集合论导致悖论，随后为弥补这一缺陷出现了各种公理化集合论体系 集合不仅可以表示数及其运算，更可以用于非数值信息及离散结构的表示和处理。集合论的原理
2、和方法作为数学基本技术广泛地应用于计算机科学的基础研究和实际应用中,集合的概念、表示与基本运算,Page 1 to 7,离散数学第1讲,-5-,第一讲 集合的概念、表示与基本运算,内容提要,基础知识 集合、元素的概念 怎样表示一个集合（列举、描述 ） 空集、全集、有限集、无限集 外延性公理 集合相等、子集、若干定理 集合的基本运算 并、交、差、补 幂集运算,-6-,第一讲 集合的概念、表示与基本运算,何为集合？何为元素？,集合(sets)：指确定的、互相区别的、作整体识别的一些事物（对象）的全体。简称集。 集合中的对象称为集合的元素(members)，或称为元、成员。 当某一个对象a 是集合A
3、的成员时，就说“a属于A”，记成aA，当a 不是集合A的成员时，就说“a不属于A”，记成aA 对于任何对象a和任何集合A，a要么属于A，要么不属于A，二者必居其一,-7-,第一讲 集合的概念、表示与基本运算,集合举例,理工大学全体学员 理工大学全体学员队 全体正整数1，2，3，4， 偶质数的全体 16队学员和他们本学期选修的所有课程 所有长得像张三的人 中国所有著名导演 方程x2 -2 x + 1 = 0 的根 方程x2 + x + 1 = 0 的根,-8-,第一讲 集合的概念、表示与基本运算,集合与元素,集合中的元素可以是任何具体或抽象的个体，也可以是集合 A = 1，2，1，2 集合与其成
4、员是两个截然不同的概念 1 1 a a 通常用大写字母A, B, C表示集合，用小写字母a, b, c表示集合的元素（并非绝对）,-9-,第一讲 集合的概念、表示与基本运算,集合的表示方法,列举法（枚举法） a, b, c、秦始皇，汉武帝 1, 2, 3, 4, 2, 4, 6, 8, 1, 2, 4, 7, 11, 0, 0.1, 0100072, 0.2345, 0.99999, 描述法 A = x | P(x)（A中的元素均满足P，而A以外的元素一个也不满足P） x | x是整数且x0、 x | x2 -2 x + 1 = 0 x | x出生于大连 、x | x是0到1区间的实数,-10
5、-,第一讲 集合的概念、表示与基本运算,集合的表示方法,归纳法（以后介绍） 文氏图（常用于表示集合之间的关系 ）,AB,1,-11-,第一讲 集合的概念、表示与基本运算,常用集合及其表示,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,-12-,第一讲 集合的概念、表示与基本运算,常用集合及其表示,偶数集合 E = , -4, -2, 0, 2, 4, = x | x是偶数 = x | x I 且 2|x 前n
6、个自然数的集合 Nn = 0，1，2，, n-1 = x | x N 且 x n ,-13-,第一讲 集合的概念、表示与基本运算,常用集合及其表示,P：全体素数的集合 Q：全体有理数的集合 Q：全体正有理数的集合 R：全体实数的集合 R ：全体正实数的集合 C：全体复数的集合,-14-,第一讲 集合的概念、表示与基本运算,空集、有限集和无限集,定义1：没有特定元素的集合称为空集，记为 ， = 。由全体对象组成的集合称为全集，记为U。 定义2：只含有限多个元素的集合称为有限集；不是有限集的集合称为无限集。 空集是有限集 有限集合A中元素的个数称为A的基数(cardinality)，记为|A| 空
7、集的基数是0，即| = 0,-15-,第一讲 集合的概念、表示与基本运算,空集、有限集和无限集举例,x | x=0 或 x=1 自然数集合N 正整数集合 A = 1，2，1，2 理工大学全体学员 方程x2 + x + 1 = 0 的根,-16-,第一讲 集合的概念、表示与基本运算,外延公理（extensionality axiom）,外延公理：两个集合相等当且仅当这两个集合具有完全相同的成员。 即对任意的集合A和B：A = B 当且仅当对任意元素x，x属于A则一定有x属于B，反之x属于B也一定有x属于A。也就是说，集合A中的所有元素均是集合B中的元素，反之，B中的所有元素均是A中的元素 0,
8、1 = 1, 0 = 0, 1, 0 = x | x(x2-2x+1)=0 外延公理事实上刻画了集合元素的无序性、相异性及集合表示形式的不唯一性,-17-,第一讲 集合的概念、表示与基本运算,子集合(subsets),定义3：设A，B为集合，若A中每一个元素都同时是B的元素，则称A是B的子集。即对于任意元素x，当x属于A时一定有x属于B。表示为AB，读成A包含于B，或B包含A。 任意集合A均是自己的子集，即：AA 若要说明A不是B的子集，只须在A中找到某一个元素x，使得xB即可 定义4：设A、B为集合，当AB且AB时，称A为B的真子集，记成AB。读做A真包含于B，或B真包含A,-18-,第一讲
9、 集合的概念、表示与基本运算,包含关系 vs. 隶属关系,包含集合与集合之间的关系 1,2 1, 2 , 3, 4 a a 隶属元素与集合之间的关系 1 1, 2 , 3, 4 5 1, 2 , 3, 4 a a,-19-,第一讲 集合的概念、表示与基本运算,关于子集的若干定理,定理1：对任何集合A，B，A=B当且仅当AB且BA 对任何集合A， AA 定理2：对于任何集合A，B，C，若AB，BC，则AC 证明：设x为A中任一元素， 因为AB，所以xB； 又因为BC，所以xC 这就是说，A中所有元素均属于C，所以有AC。,-20-,第一讲 集合的概念、表示与基本运算,关于子集的若干定理,定理3：
10、对任意集合A， AU， A 定理4：空集是唯一的 证明：假设1, 2都是空集，根据定理3，应该有1 2 且2 1 ，从而由定理1知1= 2 。,-21-,第一讲 集合的概念、表示与基本运算,关于子集的若干定理,定理5：设A为一个有限集，且|A|=n，则A的子集个数为2n 证明：集合A的子集最多有n个元素，最少有0个元素。 0元素的子集共有C(n,0)个； 1元素的子集共有C(n,1)个； n元素的子集共有C(n,n)个. 因此，集合A共有子集C(n,0)+ C(n,1)+ C(n,n)= 2n个。,-22-,第一讲 集合的概念、表示与基本运算,集合的运算,集合运算以集合作为运算对象，运算结果仍
11、为集合的运算 算术运算：3+5=8 46=24 集合运算：1, 22, 3=2 1, 22=1, 2 有哪些集合运算 交、并、差、补 求幂运算 广义并、交 求笛卡尔积运算,-23-,第一讲 集合的概念、表示与基本运算,集合的并运算union （）,定义5：设 A、B为任意集合，则由A、B的所有元素合在一起所组成的集合称为A与B的并集，记成AB。即：AB=x | xA或xB 举例 U=0, 1, 2, , 9 A=2, 4, B=4, 5, 6, 7, C=0, 8, 9, D=1, 2, 3 AB， AC， CD， BD,-24-,第一讲 集合的概念、表示与基本运算,集合的交运算interse
12、ction（）,定义6：设 A、B为任意集合，则由A、B的公共元素所组成的集合称为A与B的交集，记成AB。即：AB=x | xA并且xB 举例 U=0, 1, 2, , 9 A=2, 4, B=4, 5, 6, 7, C=0, 8, 9, D=1, 2, 3 AB， AC， CD， BD,-25-,第一讲 集合的概念、表示与基本运算,集合的差运算difference（）,定义7：设 A、B为任意集合，则由在A中而不在B中的元素所组成的集合称为A对B的差，记成AB。即：A B = x | xA且xB 举例 U=0, 1, 2, , 9 A=2, 4, B=4, 5, 6, 7, C=0, 8,
13、9, D=1, 2, 3 AB， AC， CD， BD,-26-,第一讲 集合的概念、表示与基本运算,集合的补运算 complement（）,定义8：设U为全集，A为任意集合，则所有在全集U中但不属于A的元素所组成的集合称为A的补集，记成A。即：A = x | xU且xA 举例 U=0, 1, 2, , 9 A=2, 4, B=4, 5, 6, 7, C=0, 8, 9, D=1, 2, 3 A ， B ， C ， D,-27-,第一讲 集合的概念、表示与基本运算,文氏图表示的集合并、交、差、补运算,A,AB,AB,AB,(AB) C,-28-,第一讲 集合的概念、表示与基本运算,关于并、交、
14、差、补运算的一些直观结论,AA = A，A = A，AU = U AA = A，A = ，AU = A A A = ，A = A，A U = ， A = A= U A，= U，U= ，A =A AA= ，AA= U A AB，B AB，AB A，AB B A B A 若A B，则AB = B，AB = A，A B = 若AB = ，则A B = A,-29-,第一讲 集合的概念、表示与基本运算,关于交换律和结合律,交换律 2+3 = 3+2，ab = ba AB = BA，AB = BA 一般而言，A B B A 结合律 2+(3+5) = (2+3)+5 ， a(bc) = (ab)c A(BC) = (AB) C A(BC) = (AB) C 一般而言， A (B C) (A B) C,-30-,第一讲 集合的概念、表示与基本运算,关于分配律和吸收率,分配律 a(b + c) = ab + ac A(BC) = (AB) (AC) A(BC) = (AB) (AC) A(BC) = (AB)(AC) 一般而言，A(BC) (AB)(AC) 吸收率 A(AB) = A A(AB) = A,-31-,第一讲 集合的概念、表示与基本运算,关于并、交、差、补运算的几个定理,定理6： A (BC) = (A B)(A C)
