离散数学及其应用-第2版 课件 第3章集合

第三章集合1背景：集合是现代数学的基础。集合不仅可以用来表示数及其运算，还可以用于非数值计算信息的表示和处理，如数据的增加、删除、修改、排序，以及数据间关系的描述。集合论在计算机语言、数据结构、编译原理、数据库与知识库、形式语言及人工智能等许多领域得到广泛的应用。集合的基本概念3.1 集合及其表示 3.2 集合间的关系 3.3 集合的运算 3.4 自然数 3.5 集合的特征函数33.1集合及其表示集合是由一些对象聚集在一起构成的。例如，全体整数全体中国人26个英文字母构成集合的对象可以是各种类型的事物。定义3.1.1集合中的对象叫集合的元素，或成员。4集合的表示法通常用大写的英文字母来标记一些集合。例如，

N：代表自然数集合(包括0)，

Z：代表整数集合，

Q：代表有理数集合，

R：代表实数集合，

C：代表复数集合。5集合的表示法（1）1.列举法

列举法是列出集合的所有元素，元素之间用逗号隔开，并把它们用花括号括起来。

例如，A={a，b，c，d}，B={1，2，3，4}N={1，2，3，

}，C={2，4，6，

，2n，

}，Z={0，

1，

2，…}等。6集合的表示法（2）2.描述法

描述法不要求列出集合中的所有元素，只要把集合中的元素具有的性质或所满足的条件描述出来即可。

可以用谓词公式描述集合中的元素具有的性质或所满足的条件。一般地，用B={x|P(x)}表示集合B是由具有性质P的元素x构成。例如，B={x|x

Z

3<x

6}，C={x|x是小于10的正整数}注意:谓词P(x)的范围一定要明确清楚，否则，集合无法构造。如：A={x|P(x)}，P(x)：x是公园里的美丽的花。}7集合的表示法(3)3.归纳法归纳法是通过归纳定义集合，主要由三部分组成：指出某些最基本的元素属于集合；指出由基本元素构造新元素的方法；指出该集合的界限。如：集合A按归纳法定义如下：（1）0和1都是集合A的元素；（2）如果a、b是A的元素，则ab和ba也是A的元素；（3）有限次地使用（1）（2）后所得到的字符串都是A的元素。8集合的元素

集合中的元素可以具有共同性质，也可以表面上看起来不相干。如{2，Tom，计算机，广州}在集合论中，规定元素之间是彼此相异的，并且是没有次序关系的。例如，{3,4,5},{3,4,4,5,5},{5,3,4}都是同一个集合。例如，A={3,4,5},3A,6A9特殊集合定义3.1.2有限个元素构成的集合A，称为有限集，其中包含的元素个数称为该集合的元素数，记为|A|。无限个元素构成的集合称为无限集。定义3.1.3不含任何元素的集合称为空集，记为

。空集可以符号化表示为

={x|x

x}定义3.1.4所考虑的所有对象的集合，称为全集，记为E。对于任一元素x，有x

F，x

E

T。

103.2集合间的关系定义3.2.1设A，B为集合，当且仅当它们恰有完全相同的元素时，称A与B相等，记作A=B。符号化表示为A=B

x(x

A

x

B)定义3.2.2

设A,，B为两个集合，如果B中的每个元素都是A中的元素，则称B为A的子集合，简称子集。这时也称B被A包含，或A包含B。记作B

A

或A

B。可符号化表示为B

A

x（x

B

x

A）如果B不被A包含，则记作B

A

。11集合间的关系定义3.2.3

设A，B为集合，如果B

A且B

A(即集合B的每一个元素都属于A，但集合A中至少有一个元素不属于B)，则称B是A的真子集。这时也称B被A真包含，或A真包含B。记作A

B

，亦即B

A。可符号化表示为B

A

x（x

B

x

A）

x（x

A

x

B）12集合的性质对任何集合A都有A

A

。设A、B为集合，A

B

B

A

A=B。设A、B、C为集合，A

B

B

C

A

C。证明①显然成立。②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=B13

③A

B

B

C

x（x

A

x

B）

x（x

B

x

C）

x（（x

A

x

B）

（x

B

x

C））

x（x

A

x

C）

A

C。14空集定理3.2.1

空集

是一切集合的子集。

证明

任给集合A，由子集的定义有

A

x（x

x

A）

由于x

为假，所以整个蕴涵式x

x

A对一切x为真，因此

A

为真。

推论

空集是唯一的。

证明

假设存在空集

1和

2，根据定理3.2.1，有

1

2和

2

1

，根据集合相等的定义得

1=

2

。1516例题

确定下列命题是否为真。解：(1)，(3)，(4)为真，(2)为假。17例题

求A={a，b，c}的全部子集。解：将A的子集从小到大分类：0元子集，即空集，只有1个：

。1元子集，即单元子集，有3个：{a}，{b}，{c}。2元子集，有3个：{a，b}，{a，c}，{b，c}。3元子集，有1个：{a，b，c}。18幂集定义3.2.4设A为集合，把A的全体子集构成的集合叫做A的幂集，记作P(A)（或2A），符号化表示为P(A)={x|x

A}。若A是n元集，则P(A)有2n个元素。

例如：A=={a，b，c}，A的幂集：P(A)={

，{a}，{b}，{c}，{a，b}，{a，c}，{b，c}，{a，b，c}}。19例题

计算以下幂集：，{}；{，{}}解：

P()={}

P({})={，{}}

P({，{}})={,{}，{{}},{，{}}}

例题例3.2.5证明A

B当且仅当P(A)

P(B)证明

（1）先证明必要性，对任意的x，有x

P(A)

x

A⇒x

B(∵A

B)

x

P(B)，所以P(A)

P(B)成立。（2）再证明充分性，对任意的y，有y

A

{y}

P(A)⇒{y}

P(B)(∵P(A)

P(B))

y

B，所以A

B成立。20213.3集合的运算集合的运算并，交，补（绝对补），差（相对补－），和对称差等。集合的并运算定义3.3.1设A，B为集合，由A和B的所有元素组成的集合称为A与B的并集，可表示为：

A

B={x|x

A

x

B}

其文氏图：

22对于n个集合A1，A2….An的并集为:23集合的交运算定义3.3.2设A，B为集合，由同时属于集合A和集合B的元素组成的集合，称为集合A与集合B的交集，可符号化表示为：A

B={x|x

A

x

B}。文氏图：

对于n个集合A1，A2….An的交集为:24当两个集合的交集是空集时，称它们是不交的。下面例子中的B和C是不交的，其文氏图如下：集合运算的性质定理3.3.1

设A，B为集合，则下列交换律成立。（1）A

B=B

A（2）A

B=B

A定理3.3.2

设A，B，C为任意三个集合，则下列结合律成立。（1）（A

B）

C=A

（B

C）

（2）（A

B）

C=A

（B

C）证明

用逻辑等价的方法证明（2）对任意x,x

（A

B）

C

x

（A

B）

x

C

x

A

x

B

x

C

x

A

x

（B

C）

x

A

（B

C）所以（A

B）

C=A

（B

C）成立。25集合运算的性质定理3.3.4

设A，B为任意二个集合，则下列吸收律成立。（1）A

（A

B）=A

（2）A

（A

B）=A证明集合等式的证明还可以利用一些集合恒等式证明。（1）对任意x,x

A

（A

B）

x

（A

B）

x

A

（x

A

x

B）

x

A

x

A

所以A

（A

B）=A成立。

26集合运算的性质定理3.3.3

设A，B，C为任意三个集合，则下列分配律成立。（1）A

（B

C）=（A

B）

（A

C）（2）A

（B

C）=（A

B）

（A

C）证明

用逻辑等价的方法证明。（1）对任意x,x

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

C）=（A

B）

（A

C）成立。（2）证明同（1）。2728集合的差运算定义3.3.3设A，B为任意二个集合，由属于A但不属于B的元素构成的集合，称为A和B的差，又称为集合B对于A的补集或相对补集，记为A−B。可符号化表示为：A

B={x|x

A

x

B}。其文氏图如下：

A-B=A

~B29集合的补运算定义3.3.4设E为全集，A

E，则称E和A的差集为A的补集或绝对补集，记作

A，即：

A=E-A={x|x

E

x

A}。或：

A=E-A={x|x

A}。

其文氏图如下：~E=

，~

=E，~（~A）=AA

~A=

，A

~A=E德.摩根定律定理3.3.5

设A，B为任意二个集合，则有：（1）

（A

B）=

A

B（2）

（A

B）=

A

B证明设E为全集，显然有A

E=A，A

E=E成立。（1）

（A

B）={x|x

E

x

（A

B）}={x|x

E

(x

(A

B))}={x|x

E

（

（x

A）

（x

B）}={x|x

E

（x

A

x

B）}={x|（x

E

x

A

）

（x

E

x

B）}=

A

B（2）证明同（1）。30集合的对称差运算定义3.3.5

设A，B为集合，由属于A而不属于B的所有元素和属于B而不属于A的所有元素组成的集合，称为集合A与B的对称差，记为A

B。可符号化表示为：A

B={x|（x

A

x

B）

（x

B

x

A）}文氏图为：31

A

B=（A-B）

（B-A）=(A~B)(B~A)

例题例3.3.4

设集合A={1，2，3，4，5}，B={2，4，6}则A

B={1，3，5，6}。对称差运算满足如下性质：A

A=

A

=A

A

B=B

A（A

B）

C=A

（B

C）32集合恒等式名称等式恒等律A

=A，

A

E=A支配律A

E=E，

A

=

幂等律A

A=A，

A

A=A双重否定律~(~A)=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)

(A

C)，

A

(B

C)=(A

B)

(A

C)德摩根律~(A

B)=~

B

~A，~(A

B)=~A

~

B吸收律A

(A

B)=A，

A

(A

B)=A补律A

~A=

，

A

~A=E3334例题例3.3.5证明

证明

对任意x,所以例题

35例3.3.5证明

证明

利用集合恒等式证明例题例3.3.6证明A

B当且仅当（A

B）=B或（A

B）=A。证明

首先证明当（A

B）=B或（A

B）=A时，A

B。

对任一x

A，有x

A

B，当（A

B）=B时，则有x

B；当（A

B）=A时，有x

A

B，从而x

B。因而A

B。其次证明若A

B则有（A

B）=B或（A

B）=A。

对任一x

A

B，有x

A或x

B。若x

A，因为A

B，则x

B，所以任一x

A

B均有x

B。因而A

B

B。又因为B

A

B，所以（A

B）=B。

对任一x

A，若A

B，则有x

B，因而有x

A

B。所以A

A

B。又因为A

B

A，所以（A

B）=A。36自然数自然数集合包含无限多元素，用空集和后继集可以把所有自然数定义为集合。定义3.4.1

设A是一集合，A的后继集A+为：A+=A

{A}例3.4.1

已知集合A={1，2，3}，求A的后继集A+。解

A的后继集

A+=A

{A}={1，2，3}

{{1，2，3}}={1，2，3，{1，2，3}}37例题例3.4.2对于空集

，求(1)

+，(2)(

+)+，(3)((

+)+)+。解

(1)

+=

{

}={

}(2)(

+)+={

}+={

}

{{

}}={

，{

}}(3)((

+)+)+={

，{

}}+={

，{

}}

{{

，{

}}}={

，{

}，{

，{

}}}若集合A有n个元素，则A的后继集A+有n+1个元素。38自然数集0=

1=

+={

}2=（

+）+={

，{

}}3=（（

+）+）+={

，{

}，{

，{

}}}……因此有：1=0+，2=1+，3=2+，……。以这些集合为元素构成的集合{0，1，2，3，……}是自然数集合。定义3.4.2

用空集和后继集(紧跟在n后面的自然数)可以把所有自然数定义为集合，即由此可见，任一个自然数都是一个集合的名称。39自然数集定义3.4.3

自然数集N可以用如下的递归方式定义：（1）

N（2）如果n

N，则n+=n

{n}

N（3）如果S

N且S满足条件(1)和(2)，则S=N上述定义中，(1)给出了自然数集的首个元素，(2)给出了归纳条件，(3)则规定了N的封闭性和极小性，即N是同时满足条件(1)和(2)的最小集合。40第一数学归纳法定义3.4.4

设P(n)（n

N）是论域在自然数集上的性质（或谓词），若能证明（1）P(0)为真（2）对任何n

N，P(n)⇒P(n+)，则对所有n

N，P(n)为真。这种证明方法称为第一数学归纳法。步骤(1)称为归纳基，是归纳法的基础条件；步骤(2)称为归纳步，一般假定若n=k时，P(k)成立，要证明出P(k+)也成立。上述方法可形式化表达为

P(0)

(

n)(P(n)→P(n+))⇒(

n)(P(n))数学归纳法在论域为自然数集的相关定理证明中有重要的作用。41例题例3.4.1

证明空集属于除0以外的一切自然数。证明：采用数学归纳法1）n=0时，

∉0，上述命题成