离散数学ch61集合论基本概念课件

离散数学第二部分集合论集合代数1集合论简介集合论是以集合为研究对象的一个数学分支

集合论是现代数学的基础集合是数学中最为基本的概念集合论的基本概念已渗透到数学的几乎一切领域可以说集合论已是整个现代数学的基础是自然科学及社会科学各领域的最普遍采用的描述工具是数学各分支所研究的对象2集合论简介集合论的诞生德国著名数学家康托尔于19世纪末创立的康托尔的不朽功绩“康托尔的不朽功绩在于他向无穷的冒险迈进”-----柯尔莫戈洛夫(前苏联数学家)数学与无穷潜无限思想和实无限思想无穷集元素的个数最终获得世界公认3集合论简介集合论在19

世纪末由德国数学家

G.

康托尔创立它的发展可分为两个阶段

：1908

年以前称为朴素集合论1908

年以后称为公理集合论集合论的两个阶段4集合论简介康托尔于

1874

年超越数集的局限

，首先建立起一般性的集合概念

。1878年，他引进了两个集合具有相等的“势”的概念。康托尔的重大成就在于对无穷集的研究，对数学的发展产生了深远的影响。朴素集合论1870年前后，康托尔关于无穷序列的研究导致集合论的系统发展。

5集合论简介公理化集合论的建立集合论最终获得了世界公认在1900年第二次国际数学大会上，著名数学家庞加莱就曾兴高采烈地宣布“……数学已被算术化了。今天，我们可以说绝对的严格已经达到了。”6集合论简介朴素集合论中包含着悖论。

第一个悖论是布拉利-福尔蒂的最大序数悖论。

1901年罗素发现了有名的罗素悖论。

1891年康托尔也发表了关于最大基数的悖论。

悖论的出现使人们对集合论产生了怀疑，甚至对整个数学推理的正确性也产生了疑问。数学史上的第三次危机这就动摇了数学的基础，触发了数学史上的第三次危机。

7集合论简介经过数学家们潜心研究，认识到悖论产生的原因在于康托尔原来的集合定义是不严格的。为了避免悖论，必须对集合的定义加以严格的限制。数学史上的第三次危机8集合论简介开始于1908年E.策梅罗所发表的一组公理，经过A.弗兰克尔的加工，这个系统称为策梅罗-弗兰克尔集合论（ZF），其中包括1904年策梅罗引入的选择公理。

另外一种系统是冯*诺伊曼-伯奈斯-哥德尔集合论。称

NBG

公理系统。

数学家们经过一番努力之后，终于放弃直接提出集合的定义

，而选择了公理化方法

，重新整理集合论。

集合论的现代公理化9集合论简介无论哪种公理系统，都使朴素集合论得到严格处理，避免悖论，保留一切有价值的东西，使集合论进入一个更新的发展阶段。

集合论的现代公理化10集合论简介本部分主要介绍朴素集合论的主要内容主要包括:（第6章）集合（第7章）二元关系（第8章）函数集合论的基本概念集合代数本部分主要内容介绍（第9章）集合的基数11集合论的基本概念集合与元素集合间的关系幂集12

集合与元素

1、集合的概念集合是一个不可精确定义的、最基本的数学概念。凡是具有某种特殊性质的客体的聚合，都可称为集合集合可以由各种类型的事物构成例如：

方程x2－1＝0的实数解集合；

26个英文字母的集合；

全体中国公民的集合；……

13

集合与元素

2、集合的标记集合通常用大写的英文字母来标记，例如:N:自然数集合(在离散数学中认为0也是自然数)I:整数集合Q:有理数集合R:实数集合C:复数集合……

14

集合与元素

3、元素属于给定集合的任何客体，称为该集合的成员或元素

元素：良定集合:符号表示:通常采用小写字母表示集合的元素依据某些规则，如果能明确地判定任何给定的客体是否是某个集合的成员，则称该集合为良定集合。

a

S:表示a属于S

a

S:表示a不属于S

例如:15

集合与元素

4、基数或势集合S中不同元素的数目,可称为集合S的基数或势，通常记作

#S或|S|。基数或势:有穷集合:无穷集合:基数无限的集合称为无穷集合

基数有限的集合称为有穷集合

1和m之间的正整数集合，包括有1和m，即{1,2...,m}0和m-1之间的非负整数集合,

即{0,1,2,...,m-1}

Im：Nm：A={a,b},例：则

A

=216

集合与元素

5、集合的表示方法

列举法:表示一个集合的方法有两种：是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。

例如:

有穷集合A={a，b，c，…，z}Z={0，±1，±2，…}无穷集合列举法和谓词表示法

17

集合与元素

5、集合的表示方法

谓词表示法:谓词表示法是用谓词来概括集合中元素的属性例如:

S由使P(x)为真的全体x构成。集合S={x

P(x)}表示:A={x

x=a∨x=b}A={a,b}A为偶数集合A={x

y(y

I∧x=2y)}I表示整数集方程x2－1＝0的实数解集

B＝{x|x∈R∧x2－1＝0}18

集合与元素

6、集合概念的一些问题(1)不能有矛盾性或者c

S，或者c

S对于给定的集合S和某个客体c,但是不能有c

S，同时c

S(2)相同的元素算一个元素,并且元素无次序都是同一个集合例如:{3、4、4、4、5},{5、3、4}集合{3、4、5}，19

集合与元素

(3)集合的元素可以是集合。(4)应把单元素集合与单元素区别开来。仅含一个元素的集合称为单元素集合。A={a,b,c,D}例：而D={a,b,c}，是一个集合例：{{1，0}}与{1，0}不同。{{1，0}}表示以{1，0}集合为元素的集合{1，0}表示包含”1”和”0”两个元素的集合6、集合概念的一些问题20“村里所有不自己理发的人都由我给他们理发，

集合与元素7、悖论一天，一个理发师挂出了一块招牌：于是有人问他：“您的头发由谁理呢？”理发师顿时哑口无言理发师悖论我也只给这些人理发。”分析:如果他给自己理发，那么他就属于自己给自己理发的那一类。但是，招牌上说明他不给这类理发，因此他不能自己理发。而招牌上说明他要给所有不自己理发的人理发，因此他应该自己理。21“村里所有不自己理发的人都由我给他们理发，

集合与元素7、悖论一天，一个理发师挂出了一块招牌：于是有人问他：“您的头发由谁理呢？”理发师顿时哑口无言理发师悖论我也只给这些人理发。”分析:不管做怎样的推论，理发师所说的话总是自相矛盾的。由此可见，这是一个著名的悖论，称为“罗素悖论”22

集合与元素罗素悖论罗素将集合分成两类，S={A|AA}即，S是由满足条件”AA”的那些A组成的一个新集合。那么，S是不是它自己的元素呢？即SS还是SS?一类是集合A本身是A的一个元素，即AA;另一类是集合A本身不是A的一个元素，即AA.现在构造一个集合S:7、悖论23

集合与元素如果SS，因为集合S由所有满足条件AA的集合A所组成，由SS，即知SS如果SS，因为集合S中任一元素A都有AA，由SS知S是S中的元素，所以SS罗素悖论7、悖论分析:从而产生矛盾24当且仅当A的每一个元素都是B的一个元素，

集合间的关系1、集合的相等否则，称集合A和B是不相等的，并记作A≠B。

给定两个集合A和B，定义:B的每一个元素也都是A的一个元素，A和B才是相等的，并记作A=B。

x(x

A

x

B)∧

x(x

B

x

A)用谓词逻辑表示为:

x(x

A

x

B)(a)A=B(b)A=B或者25

集合间的关系B={x

x=2∨x=3}A={x

x是小于等于3的素数}则A=B例1、集合的相等26

集合间的关系2、集合的包含

定义:设A和B是任意的集合。如果集合A的每一个元素，都是集合B的一个元素，则称A是B的子集。或说B包含A。或者A被包含于B中，记作A

B，或B

A。如果集合B不包含集合A，则把它表示成AB。用谓词逻辑表示为:

x(x

A

x

B)A

B27

集合间的关系B={a,b,c}A={a,b}则A

BBA2、集合的包含

例28

集合间的关系3、真包含

定义:设A和B是任意的集合。如果A是B的子集,且A≠B,则称A是B的真子集,记作A

B，或B

A。用谓词逻辑表示为:

x(x

A

x

B)∧

x(x

A∧x

B)A

B也称为B真包含A。29

集合间的关系B={a,b,c}A={a,b}则A

B例C={a,b,c}则C

B3、真包含

30

集合间的关系4、相等与包含的关系

定理1:设A和B是任意的集合。若A

B，且B

A,当且仅当A=B。即，A=B(A

B∧B

A)证明：A=B

x(x

A

x

B)

x(x

A

x

B)∧

x(x

B

x

A)

(A

B∧B

A)31

集合间的关系推论:对于任何集合A，有AA证明：A=A

A

A

(A

A∧A

A)4、相等与包含的关系

32

集合间的关系定理2:证明：设A、B和C是任意的集合。若A

B，且B

C，则A

C。即A

B∧B

C

ACA

B

x(x

A

x

B)B

C

x(x

B

x

C)∵∴

x(x

A

x

B)∧

x(x

B

x

C)

x(x

A

x

C)即A

B∧B

C

AC4、相等与包含的关系

33

集合间的关系5、全集定义:如果一个集合包含了所有要讨论的每一个客体，则称该集合为全集,用谓词逻辑表示为:记为E。E={xP(x)∨┐P(x)}34

集合间的关系5、全集定理3:设A是任意的集合,并且E是全集，∴AE证：∵

x(x

E)为真∴

x(x

A

x

E)为真则AE35

集合间的关系6、空集定义:没有元素的集合称为空集，用谓词逻辑表示为:

={xP(x)

┐P(x)}记为

。

与{

}不同，前者没有元素的集合，而后者是以空集为一个元素的集合。注:36

集合间的关系6、空集定理4:设A是任意的集合,并且

是空集，∴

A证：∵

x(x

x

A)永真则

A定理5:空集是唯一的。证：设有二个空集，

，

`，则

`，

`

，∴

=

`37

幂集1、幂集定义定义:设A是一个集合,A的所有子集的集合,称为A的幂集,记为ρ(A)或2A用谓词逻辑表示为:ρ(A)=2A={x|x

A}38

幂集1、幂集定义例：解：试求出集合{p,q}的幂集。集合{p,q}的子集为{p},

{p,q},{q},ρ{p,q}={

，{p},{q},{p,q}}例：试用空集构造幂集合。(a)ρ{

}{

}

的子集为,ρ{

}=(b)ρ{ρ{

}}{,{}}{

}的子集为,ρ{ρ{

}}={

}(c)ρ{ρ{ρ{

}}}子集为,{

},{{

}},{,{}}ρ{ρ{ρ{

}}}=,{

},{{

}},{,{}}{}39

幂集2、幂集的基数定理6:

设A是一个有限集合,且A的基数为|A|证：则A的幂集的基数为

ρ(A)|=2|A|设

A|=n,所以A的子集数目为即

ρ(A)|=2|A|有Cin个N个元素中选取i个不同元素的方案，=1+C1n+C2n+……+Cnn

ρ(A)|=2n=(1+1)n40集合代数命题演算与集合演算之间存在着一种类比命题代数和集合代数都是一种称为布尔代数的抽象代数依据这种类比能够构成一种集合代数41集合的运算1.集合的并、交和相对补集分别定义如下：并、交、相对补集：设A，B为两个集合，则A与B的并集A∪B，交集A∩B，A和B的并：A∪B={x

x

A∨x

B}A和B的交：A∩B={x

x

A∧x

B}A或B中的元素构成，A和B中的公共元素构成B对A的相对补集A－B，={x

x

A∧x

B}A-B={x

x

A∧┐(x

B)}B对A的相对补集：由属于A但不属于B的元素构成。

42集合的运算例如

A＝{a，b，c}，B＝{a}，C＝{b，d}

则有

A∪B＝{a，b，c}，

A∩B＝{a}，

B∩C＝Φ不相交：如果两个集合的交集为Φ

,则称这两个集合是不相交的。

例如上面的B和C是不相交的。

A－B＝{b，c}，

1.集合的并、交和相对补集43集合的运算两个集合的并和交运算可以推广成n个集合的并和交

A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An}

A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}n个集合的并和交：上述的并和交可以用下面的式子表示：Ai＝A1∪A2∪…∪An

Ai＝A1∩A2∩…∩An44集合的运算并和交运算还可以推广到无穷多个集合的情况：

＝A1∪A2∪…

＝A1∩A2∩…n个集合的并和交：45集合的运算定理1：集合的交、并运算是可交换和可结合的即有:（1）A∪B=B∪A（2）A∩B=B∩A（3）(A∪B)∪C=A∪(B∪C)

（4）(A∩B)∩C=A∩(B∩C)46集合的运算∴

x(x

A∩B

x

B∩A)证（2）A∩B=B∩A

x

E∵x

A∩Bx

A∧x

B

∩的定义

x

B∧x

A∧的可交换性

x

B∩A∩的定义即A∩B=B∩A定理1：集合的交、并运算是可交换和可结合的47集合的运算定理2：分配率(1)A∪(B∩C)=(A∪B)∩(A∪C)∪在∩上可分配(2)A∩(B∪C)=(A∩B)∪(A∩C)∩在∪上可分配证(2)

x

Ex

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∧在∨上可分配∴A∩(B∪C)=(A∩B)∪(A∩C)48集合的运算定理3：设A是全集E的任意子集,则a)

A∪A=Ab)

A∩A=Ac)

A∪

=Ad)

A∩

=

e)A∪E=Ef)A∩E=A49集合的运算定理3：b)

A∩A=Ad)

A∩

=

证:

x

E,x

A∩A

x

A∧x

A

x

A∴A∩A=A

x

E,x

A∩

x

A∧x

∴x

∴A∩

=

50集合的运算定理4：设A,B,C,D是全集E的任意子集,则d)若A

B,C

D,那么,A∩C

B∩De)A

A∪Bf)A∩B

Aa)若A

B,那么,A∪B=Bb)若A

B,那么,A∩B=A

c)

若A

B,C

D,那么,A∪C

B∪D

g)

A-B

A51集合的运算定理4：设A,B,C,D是全集E的任意子集,则d)若A

B,C

D,那么,A∩C

B∩Db)若A

B,那么,A∩B=A证:∵A

B,又A

A,根据d)A∩A

A∩Bx

(A∩C)

x

A∧x

C

x

B∧x

D

x

(B∩D)∴A∩C

B∩D即A

A∩B另一方面，A∩B

A∴A=A∩Bg)

A-B

Ax

A-B

x

A∧x

B

x

A∴A-B

A52集合的运算定理5：设A,B,C是全集E的任意子集,则a)

A-

=Ad)A－(B∪C)＝(A－B)∩(A－C)

e)A－(B∩C)＝(A－B)∪(A－C)

b)A∩(B-A)=Φc)A∪(B-A)=A∪B53集合的运算2.补运算补集定义：对于E和A所进行的差分运算，通常称为求补。

给定全集E，对于任何集合A来说，A对E的相对补集，称为A的绝对补集，或简称为A的补集,并记作~A。54集合的运算2.补运算定理6：设A是全集E的任意子集,则a)A∪~A=Eb)A∩~A=

∴A∩~A=

证a)：x

A∪~A

x

A∨x

A

T

x

E∴A∪~A=Eb)x

A∩~A

x

A∧x

A

F

x

55集合的运算定理7：设A,B是全集E的任意子集,则B=~A

A∪B=E和A∩B=

证：充分性B=~AA∪B=A∪~A=EA∩B=A∩~A=

必要性B=E∩B=（A∪~A）∩B=(A∩B)∪(~A∩B)=

∪(~A∩B)A∩B=

=(~A∩A)∪(~A∩B)=~A∩(A∪B)=~A∩E=~A补集的唯一性定理56集合的运算a)~

=Eb)~E=

∴~

=E，~E=

。证：∵E∪

=E，E∩

=

，定理7推论：57集合的运算定理8：设A是全集E的任意子集,则~~A=A证：∵A∩~A=

，A∪~A=E，又∵~~A也是~

A的补，∴由定理7，A是~A的补。由补的唯一性知，~~A=A。58集合的运算定理9：设A、B是全集E的任意子集,则a)~(A∪B)=~A∩~Bb)~(A∩B)=~A∪~B证b)式：∵(~A∪~B)∩(A∩B)=(~A∩(A∩B))∪(~B∩(A∩B))=

∪

=

(~A∪~B)∪(A∩B)=(~A∪~B∪A)∩(~A∪~B∪B)=E∴~A∪~B是A∩B的补,但~(A∩B)也是A∩B的补，由补的唯一性，∴~(A∩B)=~A∪~B。德·摩根律

59集合的运算3.对称差对称差定义：设A、B是任意两个集合。集合A和B的对称差A+B定义为:A+B=（A-B）∪（B-A）集合A+B是由或者属于A,或者属于B，但不同时属于A和B的那些元素构成。60集合的运算设A,B,C是全集E的任意子集,则引理：A+B=（A∪B）∩（~A∪~B）=（A∪B）-（A∩B）证：A+B=（A-B）∪（B-A）=(A∩~B)∪（B∩~A）=（A∩~B∪B）∩（A∩~B∪~A）=（A∪B）∩（~B∪B）∩（A∪~A）∩（~B∪~A）=(A∩~B)∪（B∩~A）=（A∪B）∩（~A∪~B）=（A∪B）∩~(A∩

B）=（A∪B）-（A∩B）61集合的运算设A,B,C是全集E的任意子集,则定理10：a)A+B=B+Ad)A+A=Φb)(A+B)+C=A+(B+C)e)A+Φ

=Ac)A+B

=(A∩~B)∪（B∩~A）62图解表示法集合之间的相互关系和有关的运算可以用文氏图(JohnVenn)形象的描述文氏图的构造方法如下:(1)首先画一个大矩形表示全集E(2)其次在矩形内画一些圆或任何其他的适当的闭曲线，用圆的内部表示集合在一般情况下，如果不作特殊的说明，这些表示集合的圆应该是彼此相交的如果已知某两个集合是不交的，则表示它们的圆彼此相离通常在图中画有阴影的区域表示新组成的集合63A∩B=ΦB

AA∪BA∩BA-B~AA+B(A∩B)-C文氏图实例64图解表示法对24名会外语的科技人员进行掌握外语情况的调查。其统计结果如下：会英、日、德和法语的人分别为13，5，10和9人，其中同时会英语和日语的有2人，会英、德和法语中任两种语言的都是4人。已知会日语的人既不懂法语也不懂德语，分别求只会一种语言(英、德、法、日)的人数和会三种语言的人数。例解令A，B，C，D分别表示会英、法、德、日语的人的集合。

使用文氏图可以方便地解决有穷集的基数计算问题

65图解表示法设同时会三种语言的有x人，只会英、法或德语一种语言的分别为y1，y2和y3人。将x和y1，y2，y3填入图中相应的区域，然后依次填入其它区域的人数。

根据题意画出文氏图

66图解表示法根据已知条件列出方程组如下：

解得x＝1，y1＝4，y2＝2，y3＝3

67包含排斥原理除使用文氏图方法外，有穷集的基数计算问题有一条重要的定理-----包含排斥原理68包含排斥原理1.有限集基数的有关结果a)|A∪B|=|A|+|B|-|A∩B|b)|A∩B|≤min(|A|,|B|)c)|A+B|=|A|+|B|-2|A∩B|d)|A-B|≥|A|-|B|包含排斥原理69包含排斥原理①当A∩B=

,则|A∪B|=|A|+|B|，a)成立。②当A∩B

，则|A||B|∴|A|+|B|=|A∪B|+|A∩B|∴|A∪B|=|A|+|B|-|A∩B|=|A∩~B|+|B∩~A|+|A∩B|+|A∩B|=|A∩~B|+|A∩B|=|(A∩B)∪(A∩~B)|=|B∩~A|+|B∩A|包含排斥原理证明：1.有限集基数的有关结果70包含排斥原理例：设某班有60名同学，其中足球队员有28名，篮球队员有15名。若有25名同学没有参加这二个队，问同时参加这二个队的队员有多少名？

解：设A为足球队员集合，B为篮球队员集合，则|A∪B|=60-25=35，∴|A∩B|=|A|+|B|-|A∪B|=28+15-35=871包含排斥原理|A1∪A2∪……∪An|=

i=1n

Ai

-

1≤i<j≤n

Ai∩Aj

+

1≤i<j<k≤n

Ai∩Aj∩Ak

+……(-1)n-1

A1∩A2∩……∩An

包含n个集合的包含排斥原理=|A1|+|A2|+|A3|-|A1∩A2|-|A1∩A3|-|A2∩A3|+|A1∩A2∩A3|特别地,n=3,

|A1∪A2∪A3|72设n-1时,结论成立,则|A1