离散数学课件 3.1集合和3.2节 集合的运算和性质

第三章集合论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)