离散数学-集合论.ppt

离散数学
计算机学院软件与理论教研室(313)
Discrete Mathematics
Email:******@imu.
Tel:4994019-808
2018/5/2
1
第二部分
集合论
Set ,Relation and Mapping
2018/5/2
2
第三章集合、关系与映射
关系即二元关系,它是集合直乘积的子集
映射是特殊的二元关系
19世纪末著名德国数学家康托()
集合已经发展成为数学及其他各学科不可缺少的描述工具
成为数学中最为基本的概念
集合论分为两种体系
朴素集合论体系(康托集合论体系).
康托从抽象原则出发
概括出:满足某性质的个体放在一起组成集合
隐含矛盾,即罗素(Russell)悖论.
公理集合论体系(属于数理逻辑范畴)
2018/5/2
3
集合及其运算
1. 集合及其表示法
用大写英文字母A,B,C,…表示集合
并用x∈A表示x是集合A中的元素,读作“x属于A”
用xA表示x不是A中的元素,读作“x不属于A”.
一般,集合有两种表示法:列举法和描述元素性质法
列举法
A={a,b,c,d,e}; B={书,笔记本,铅笔,课桌,黑板};
C={0,1,-3,6}; D={北京,天坛,故宫,地球,宇宙}.
描述元素性质法
Σ={x|x是英文字母}; Z={x|x是整数};
2018/5/2
4
集合及其表示法
需要注意以下几点:
集合中的元素各不相同
如{1,2,3,4}与{1,1,2,3,4,4}是相同的集合
都是含元素1,2,3,4的集合
集合中的元素不规定次序
如:{1,2,3,4}={4,2,3,1}.
有些集合的两种表示法能互相转换,有些则不能
如:{x|x是英文字母}={a,b,c,d,e,f,g,…,x,y,z};
{x|x是非负偶数}={0,2,4,6,8,10,…,2n,…};
{x|x是实数}不能转换为列举法表示.
2018/5/2
5
集合及其表示法
一些常用集合的表示法:
N={x|x是自然数}={0,1,2,…,n,…}
Z={x|x为整数}={…,-3,-2,-1,0,1,2,3,…}
Z+={x|x∈Z∧x>0}={1,2,3,…,n,…}
Q={x|x是有理数}
R={x|x为实数}
还有:
P表示素数集合
O表示奇数集合
E表示偶数集合
2018/5/2
6
集合间的包含与相等
,B为集合,若B中的元素都是A中的元素,则称
B是A的子集,记作BA,称A包含B,或B包含于A,
并以B A表示B不是A的子集.
即BA∀x(x∈B→x∈A)
B Ax(x∈B∧xA).
,B为集合,若集合AB且A≠B,则称A为B的真子
集,记作AB.
即AB∀x(x∈A→x∈B)∧x(x∈B∧xA).
例如:若A={1,2,4},B={1,2,3,4,5},则AB, 而且AB.
对任意集合A有:AA(自反性)
对任意集合A,B,C,若AB且BC,则AC(传递性)


2018/5/2
7
空集与全集
,B为集合,若AB且BA,则称A与B相等,记作A=B.
,记作.
空集是任意集合的子集合,是任意非空集合的真子集合
和{}的关系是?
空集是任意集合的子集,可以形象地说:是“最小”的集合.
但没有最大的集合.
在讨论某些具体问题时,往往使用一个在相对的意义下是“最
大”的集合”.

2018/5/2
8
空集与全集

子集,则称E为全集
全集是一个相对的概念,不同的实际问题可以定
义不同的全集.
例如当被讨论的集合仅仅是{0,2,4},{6},{6,8}
时,全集可设为{0,2,4,6,8}
或{x|x是10以内的自然数}等
2018/5/2
9
集合的幂集
. 设A为一个集合,称由A的所有子集组成的集合为
A的幂集,记作P(A),即P(A)={X|XA}.
如:设A={1,2,3}
则P(A)={,{1},{2},{3},{1,2},1,3},{2,3},A}.
若|A|=n,则P(A)的元素个数|P(A)|=2n.
元素个数有限的集合称有穷集,对其子集有一种编码方法:设A={a1,a2,a3}则A2=A010={a2},A5=A101={a1,a3}.
2018/5/2
10