离散数学课件 第三章 集合论

第三章集合论3.1集合3.2集合的运算和性质3.3集合中元素的计数3.4应用集合的概念集合的表示幂集

3.1集合第3章集合

集合的概念定义3.1

集合（Set）论是现代数学中最重要的基础之一，它是不能精确定义的概念。一般地，把具有共同性质的一些东西汇集成一个整体，就形成一个集合。例如：(1)自然数的全体。(2)某个图书馆的藏书。(3)教室里的学生。集合通常用大写英文字母来标记，如实数集合、复数集合、整数集合、自然数集合与有理数集合等。集合中的每一个对象称为元素（Element），通常用小写英文字母表示，如a,b,c,...

集合的表示集合完全由其包含的元素确定，可用多种方法表示。1.列举法列举法即将集中的全部元素或部分元素但能看出其他元素规律的方法，亦称枚举法。一般来说，当一个集合仅含有限个元素或元素之间有明显关系时，采用列举法。例如，20以内的素数集合A={2，3，5，7，11、13、17、19}全体自然数集合={0，1，2，3，…，}

集合的表示2．描述法描述法是刻画集合中元素所具有的某种特性来表示集合的方法，任何元素属于或不属于集合，看该元素是否具有规定的性质，亦称谓词表示法。集合，其中，代表元素，表示具有性质P，或是表示由使为真的全体构成。例如，其元素是其元素是描述法具有抽象性的特点，是一种隐式表示法。

集合的表示3.文氏图法文氏图（Venndiagram）是以英国数学家韦恩（JohnVenn）的名字命名的，他在1881年介绍了这种图的使用，用它表示集合之间的关系或运算。它是一种非常直观的图示集合工具。但是文氏图只起示意作用，不能用以代替证明方法，用文氏图表示集合的方法如下

集合的表示3.文氏图法首先画一个大矩形表示全集E，其次在矩形内画一些圆(或任何其他的适当的闭曲线)用圆的内部表示集合。在一般情况下，如果不特殊说明，这些表示集合的圆应该是彼此相交的。如果已知某两个集合是不交的，则表示它们的圆彼此相离。通常在图中画有阴影的域表示新组成的集合。图3.1是一些文氏图的实例。图3.1文氏图实例

定义3.1

设

和

是任意两个集合，如果

中的每个元素都是

中的元素，则称

是

的子集合，简称子集(Subset)，这时也称

被

包含，或

包含

，

记作或

。

如果

不被

包含，则记作

由定义知

是

的子集，即

，如果

，则

例如集合间的关系

集合间的关系定义3.2

如果

且

，则称

是

的真子集（ProperSubset），也称

真包含于

，或

真包含

，记作

或

。称为真包含关系(ProperlyInclusionRelation)如果A不是B的真子集，则记作A⊆B。A是B的真子集，即A⊆B且∃x∈B，但x∉A。换句话说，∀x，如果x∈A，则x∈B，且存在x∈B但x∉A。例如N⊂Z⊂Q⊂R。

集合间的关系证明：A⊆B∧B⊆A⇔∀x(x∈A→x∈B)∧∀x(x∈B→x∈A)⇔∀x((x∈A→x∈B)∧(x∈B→x∈A))⇔∀x(x∈A↔x∈B)⇔A=B该定理是证明两个集合相等的基本思路和依据。

集合间的关系例3.1

设A、B、C是任意集合，若A⊆B，B⊆C，试证明A⊆C。证明：由A⊆B知，对∀x∈A，则有∀x∈B。又由B⊆C，有∀x∈C，所以有A⊆C。

集合间的关系3.1.4几个特殊集合1.空集定义3.3

不含任何元素的集合叫作空集（EmptySet），记作∅。注意：∅≠{∅}。∅中不含任何元素，而{∅}中含有一个元素∅。∅是客观存在的，是唯一的，而且是一切集合的子集。例如：A={x|x∈R，且x²+1=0}就是一个空集。

集合间的关系2.全集定义3.4

在一个具体问题中，如果涉及的集合都是某个集合的子集，则称这个集合为全集。全集是相对唯一的，与具体问题有关，所研究的问题不同，所取的全集也不同。例如，在研究实数问题时，把实数集R取作全集；在研究有理数时，把全体有理数Q取作全集；在研究人类时，把全体人类取作全集。

集合间的关系2.幂集定义3.5设A是任意集合，由A的所有子集所组成的集合，称为集合A的幂集（PowerSet），记为P(A)或2^A。P(A)={B|B⊆A}。这种以集合为元素的集合称为集族（FamilyofSet）。显然，幂集是一个集族。

集合间的关系例3.2：求下列集合的幂集(1)∅(2){∅}(3){1,2,3}(4){1,{2,3}}解：P(∅)={∅}P({∅})={∅,{∅}}P({1,2,3})={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}P({1,{2,3}})={∅,{1},{{2,3}},{1,{2,3}}}

集合间的关系定理3.3如果有限集合A有n个元素，则其幂集有2ⁿ个元素。证明：A的所有由k个元素组成的子集数为从n个元素中取k个元素的组合，即另外，空集是任何集合的子集，所以其幂集总数M可表示为

集合间的关系令x=y=1，则有即有限集合A的幂集元素个数是2ⁿ。一个有限集合幂集元素个数与其子集个数相等。

集合间的关系为有效表示有限集幂集中元素，我们引进二进制编码即P(A)={A_i|i∈J}，J={i|i是二进制数，且00…0≤i≤11…1}。如对集合S={a,b,c}，其幂集A=P(S)，A₀₀₁={a}，A₀₁₁={b,c}，A₁₀₀={a,b}。

集合间的关系定理3.4

设A、B为任意两个集合，A⊆B当且仅当P(A)⊆P(B)。证明必要性：对∀x∈P(A)，有x⊆A，由于A⊆B，所以x⊆B，即有x∈P(B)，即P(A)⊆P(B)成立。证明充分性。假设A⊆B不成立，则至少有一元素a∈A，但a∉B。对集合{a}，有{a}∈P(A)但{a}∉P(B)，这与假设矛盾，所以有A⊆B。

3.2集合的运算和性质第3章集合论

集合的并和交集合的差和补集合运算的性质

集合的并和交定义3.6A和B是任意两集合，则(1)A和B的并是由A和B中所有元素组成的集合,记为A∪B，A∪B={x|x∈A或x∈B}(2)A和B的交是由A和B共有元素组成的集合,记为A∩B，A∩B={x|x∈A且x∈B}集合的并和交可推广到多个集体的并和交，即，集合的并和交可推广到多个集体的并和交，即，也可以推广到可数无穷个集合的并和交，即

集合的差和补定义3.7设A和B为任意集合，(1)A与B的差是由属于A而不属于B的元素组成的集合,记为A−B,也称为B对A的相对补A−B={x|x∈A且x∉B}(2)A与B的对称差是由属于A而不属于B或属于B而不属于A的元素组成的集合，记为A⊕BA⊕B=(A−B)∪(B−A)(3)设E为全集，且A⊆E，则称对E的相对补集为A的绝对补集，记作¬A，即¬A=E−A={x|x∈E且x∉A}={x|x∉A}

集合的差和补例3.3设E={a,b,c,d,e}为全集，A{a,b,c,d},B={d,e,f}分别求A−B,B−A，A的绝对补，A和B的对称差。解A−B={a,b,c}，B−A={f,e}，¬A={e,f}A⊕B=(A−B)∪(B−A)={a,b,c,f,e}A与B对称差的等价定义是A⊕B=(A∪B)−(A∩B)用文氏图可以形象地描述集合间的关系和有关运算。如图3.2所示，分别表示集合的补、交、并、差和对称差运算。图3.2集合的补、交、并、差和对称差运算示意图

集合运算的性质根据集合运算的定义，很容易得到集合运算的一些运算定律，这些定律与实数集合上的定义的运算定律类似，如下：定理3.5设E为全集，A,B,C为任意集合，则集合运算满足以下定律交换律A∩B=B∩A，A∪B=B∪A，A⊕B=B⊕A结合律(A∪B)∪C=A∪(B∪C)，(A∩B)∩C=A∩(B∩C)(A⊕B)⊕C=A⊕(B⊕C)分配律A∪(B∩C)=(A∪B)∩(A∪C)，A∩(B∪C)=(A∩B)∪(A∩C)等幂律A∩A=A，A∪A=A吸收律A∩(A∪B)=A，A∪(A∩B)=A

集合运算的性质排中律A∪¬A=E，A∩¬A=∅零律A∪E=E，A∩∅=∅同一律A∪∅=A，A∩E=A矛盾律A∩¬A=∅德摩根律

¬(A∪B)=¬A∩¬B，¬(A∩B)=¬A∪¬B双重否定律

¬(¬A)=A

集合运算的性质例3.4证明¬(A∪B)=¬A∩¬B证明对任意的xx∈¬(A∪B)⇔x∉(A∪B)⇔x∉A∧x∉B⇔x∈¬A∧x∈¬B⇔x∈¬A∩¬B

集合运算的性质例3.5证明A−(B∪C)=(A−B)∩(A−C)证明对任意的xx∈A−(B∪C)⇔x∈A∧x∉(B∪C)⇔x∈A∧(x∉B∧x∉C)⇔(x∈A∧x∉B)∧(x∈A∧x∉C)⇔x∈(A−B)∧x∈(A−C)⇔x∈(A−B)∩(A−C)类似地，可证其他两个等式，留给读者自证。除了以上定律外，还有一些关于集合运算性质的重要结论，

集合运算的性质A∩B⊆A，A∩B⊆BA⊆A∪B，B⊆A∪BA−B=A∩¬BA−B⊆AA⊕B=A⊕C⇒B=CA⊕A=A

集合运算的性质例3.6证明，对任意集合A,B，有(A−B)∩(B−A)=∅证明(A−B)∩(B−A)⇔(A∩¬B)∩(B∩¬A)⇔A∩¬B∩B∩¬A⇔(A∩¬A)∩(B∩¬B)⇔∅∩∅⇔∅

第三章集合论3.1集合3.2集合的运算和性质3.3集合中元素的计数3.4应用集合元素的个数容斥原理

3.3集合中的元素计数第3章集合

集合元素的个数集合元素的个数

计数问题在计算机科学中具有十分重要的地位。集合的运算在计数问题中有很好的应用。对一些简单集合的计数问题，可利用集合的交、并、差运算来解决。集合A中的元素个数被称为集合A的基数，对含有n个元素的有限集合，称其基数是n，记作：基数是表示集合中所含元素多少的量，也可记作A等于n。如果一个集合的基数是有限的，则称该集合为有限集；如果一个集合的基数是无限的，则称该集合为无限集。显然，空集的基数为0。

集合的表示定义3.8设A为集合，若存在自然数n使得CardA=n，则称A为有限集，否则称A为无限集。例如：{1,2,3}是有限集，而N、R、Z、Q、C都是无限集。因无限集的基数比较复杂，这里仅讨论有限集的基数问题。根据集合的运算，下面的式子显然成立：

集合的表示例3.7有96名程序员，其中51名熟悉Python语言，67名熟悉C语言，32名同时熟悉这两种语言。有多少人对这两种语言都不熟悉？解：设A、B分别表示熟悉Python语言和C语言的程序员的集合，则该问题可以用文氏图来表示，如图3.3所示。图3.3例3.7文氏图

集合的表示将熟悉两种语言的对应人数32填到

的区域内，则有从而得到所以,共有10人对两种语言都不熟悉。

集合的表示例3.8解：设只会英语、法语、德语的人数分别为x，y，z。会3种语言的人数为h根据题意，构造文氏图如图3.4所示，从而得到如下方程:图3.4例3.8文氏图

集合的表示解得所以，只会一种语言的人数是12人，会三语言的人数1人。

定义3.3.2容斥原理用文氏图来解决一些简单集合的计数问题非常方便。上面的例子中，首先计算所有元素的个数，然后减去（排斥掉）不符合条件的元素的个数。这实际上就是容斥原理（thePrincipleofInclusion-Exclusion）的基本思想，即先包含，后排斥。集合间的关系

集合间的关系定理3.6

设S为有限集合，P₁,P₂,…,P是n条性质，Aᵢ表示S中具有性质Pᵢ的元素构成的集合，则

集合间的关系证明：1）用数学归纳法该定理是证明两个集合相等的基本思路和依据。显然，当n=2时，成立，因为这把只属于A₁或只属于A₂的元素只计一次，而把既属于A₁又属于A₂的元素计了两次。

集合间的关系设

证明：由A⊆B知，对∀x∈A，则有∀x∈B。又由B⊆C，有∀x∈C，所以有A⊆C。有

集合间的关系因此有

所以（1）成立。（2）因为

所以有

集合间的关系此定理中（1）计数了S中至少具有一条性质的元素数，而（2）则计数了S中不具有任一性质的元素数。有了容斥原理，例3.7中所求的元素数为

集合间的关系定义3.9

设某班有100名学生，其中有68人英语成绩为优，有45人数学成绩为优，有23人英语和数学成绩均为优。问两门课程都不为优的学生有多少名？解：设分别表示英语成绩为优和数学成绩为优的集合，则有由包含排斥原理得所以

集合间的关系定义3.10

求1到500之间能被，2，3，5任何一个整除的整数个数。解：设A、B、C分别表示1到500之间能被2、3、5整除的整数集合，则有A中元素个数=⌊500÷2⌋=250B中元素个数=⌊500÷3⌋=166C中元素个数=⌊500÷5⌋=100

集合间的关系A∩B中元素个数=⌊500÷(2×3)⌋=83A∩C中元素个数=⌊500÷(2×5)⌋=50B∩C中元素个数=⌊500÷(3×5)⌋=33A∩B∩C中元素个数=⌊500÷(2×3×5)⌋=10则可得到：A∪B∪C的元素个数=A+B+C−A∩B−A∩C−B∩C+A∩B∩C=250+166+100−83−50−33+10=360

集合间的关系其中⌊x⌋表示小于或等于x的最大整数。即在1到500之间有360个整数可被2、3、5任一个整除。例3.11求1到1000之间不能被3或5，也不能被7整除的整数个数。解：设A、B、C分别表示1到1000之间能被3、5、7整除的整数集合，则有A中元素个数=⌊1000÷3⌋=333B中元素个数=⌊1000÷5⌋=200C中元素个数=⌊1000÷7⌋=142

集合间的关系A∩B中元素个数=⌊1000÷(3×5)⌋=66A∩C中元素个数=⌊1000÷(3×7)⌋=47B∩C中元素个数=⌊1000÷(5×7)⌋=28A∩B∩C中元素个数=⌊1000÷(3×5×7)⌋=9所以，既不能被3，5整除，也不能被7整数的整数有457个。例子3.12：求欧拉函数的值。欧拉函数ψ是数论中的一个重要函数，在密码学中有着重要作用。设n是正整数，ψ(n)表示{0,1,2,…,n−1}中与n互素的数的个数。例如，ψ(14)=6，因为与14互素的数有1、3、5、9、11、13。这里约定ψ(1)=1。下面用容斥原理给出欧拉函数的计算公式。

集合间的关系例如，ψ(14)=6，因为与14互素的数有1、3、5、9、11、13。这里约定ψ(1)=1。下面用容斥原理给出欧拉函数的计算公式。给定正整数n，若

为n的素因子分解式，令则有下面计算上述右边的各项。

集合间的关系由容斥原理

集合间的关系例如：即小于15且与15互素的正整数有8个，即1，2，4，7，8，11，13，14。即小于30且与30互素的正整数有8个，即1，7，11，13，17，19，23，29。

第三章集合论3.1集合3.2集合的运算和性质3.3集合中元素的计数3.4应用这里，我们介绍一种利用全集元素的一个任意排序存放元素以表示集合的方法。这种表示法使我们很容易计算集合的组合，也便于进行集体的交、并、补、差运算。设全集U是有限集。首先为U的元素任意规定一个顺序，例如m₁,m₂,…,m。于是可以用长度为n的1/0位串表示U的子集