离散数学 第三章：集合的基本概念和运算.ppt

第3章集合的基本概念和运算
§ 集合的基本概念
§ 集合的基本运算
§ 集合中元素的计数
关于集合的有趣的例子
在一个僻静的孤岛上,住着一些人家,岛上只有一位理发师,该理发师专给那些并且只给那些自己不刮脸的人刮脸。那么谁给这位理发师刮脸?
分析设 C={x | x是不给自己刮脸的人},b是这位理发师.
一方面, 如果bC,则b是不给自己刮脸的人;另一方面,由
题意知,这位理发师b只给集合C中的人刮脸。所以b要给b刮
脸,即bC;
另一方面, 如果bC,则b是要给自己刮脸的人;另一方
面,由题意知,理发师只给自己不刮脸的人刮脸。所以b是不给
自己刮脸的人,即bC。
无论如何,都有bC和bC同时成立。这种情况称为罗素悖论。
§ 集合的基本概念
1. 集合的概念
没有精确的定义,但一般认为一个集合指的是可确定的
可分辨的事物构成的整体。
元素:集合里所含的个体称为集合的元素。
1)集合的三要素:确定性,无序性,互异性。
2)集合的元素:可以是任意类型的事物,也可以为一个集合。
例如:
3)可以用树形结构把集合与元素之
间的关系表示出来。
在每层次上,把集合作为一个结点,它的元素则作为它的儿子。
A
{b,c}
a
d
{{d}}
b
c
{d}
d
注:

包含关系:
相等关系:
B为A的子集
真子集:
空集:
定理1. 空集是一切集合的子集.
证明: 任给一个集合A, 只需证
即可.
事实上,由子集的定义,
而右端的蕴涵式中因前件
为假,
所以整个
蕴涵式对一切x为真,所以
为真.

推论. 空集是唯一的.
证明: 假设存在两个空集
则由定理1知
且
从而
例1.
求A 的全部子集.
解: 将A的子集从小到大分类;
0元子集: 1个,
1元子集:
个,
2元子集:
个,
3元子集:
个,
注:
一般的,对于n元子集A,它的m元子集共有
个,
所以不同的子集总数有:
定义:A的所有子集构成的集合叫做A的幂集,记作 P(A).

例: 设 A= { a, b, c },则
符号化为:
注:
若A为n元集, 则 P(A)=2n 个元素.
例3: 计算以下幂集:
集合的运算及性质
一、集合的运算
集合的运算,就是以给定集合为对象,按照确定的规则得到另外一些集合。

定义1 设A,B为任意两集合,由集合A和B的所有共同元素组成的集合S,称为A和B的交集,记作A∩B。
S= A∩B={x | x ∈A ∧ x ∈B}
用文氏图表示如下:
E
A
B
例:A={0,2,4,6,8}, B={1,2,3,4,5,6},则:
A∩B={2,4,6}
并、交的推广
两个集合的并交运算可推广至n个集合:
A1∩A2 ∩…∩An ={x | x ∈A1 ∧x∈A2∧…∧ x∈An }
A1∪A2 ∪…∪An ={x | x ∈A1∨x∈A2∨…∨ x∈An }
可以把n个集合的交和并简记为和, 即

定义3 设A,B为任意两集合,所有属于A而不属于B的一切元素组成的集合S,称为B对于A的补集,或称相对补,记作A-B。
S= A-B={x | x ∈A ∧ x B}
= {x | x ∈A ∧(x B) }
A-B 也称为集合A和B的差。
用文氏图表示如下:
E
A
B
例:设A={2,5,6}, B={1,2,4,7,9},则
A-B={5,6}