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