离散数学 第3章 集合与关系.ppt

文档介绍：第3章集合与关系 (Set and Relation)
计算机科学与工程系
2
当我们已经直观地弄懂了几个简单的定理的时候……如果能通过连续的不间断的思考活动,把几个定理贯穿起来,悟出它们之间的相互关系,并能同时尽可能多地、明确地想象出其中的几个,那将是很有益的。照这样我们的知识无疑会增加,理解能力会有显著的提高。
笛卡尔
教学内容
集合的概念和表示
集合的运算

序偶与笛卡尔积
关系及其表示
复合关系和逆关系
关系的性质
关系的闭包运算
集合的划分与等价关系
偏序关系
3
4
集合的概念及表示
集合的定义与表示
集合与元素
集合之间的关系
空集
全集
幂集
5
集合定义与表示
集合没有精确的数学定义
理解:一些离散个体组成的全体
组成集合的个体称为它的元素或成员
集合的表示
列举法 A={ a, b, c, d }
描述法(谓词表示法) B={ x | P(x) }
B 由使得 P(x) 为真的 x 构成
常用数集
N, I(或Z), Q, R, C 分别表示自然数、整数、有理数、实数和复数集合,注意 0 是自然数.
6
集合与元素
元素与集合的关系:隶属关系
属于,不属于
实例
A={ x | xRx2-1=0 }, A={-1,1}
1A, 2A
注意:对于任何集合 A 和元素 x (可以是集合),
xA和 xA 两者成立其一,且仅成立其一.
7
隶属关系的层次结构
例
A={ a, {b,c}, d, {{d}} }
{b,c}A
bA
{{d}}A
{d}A
dA
8
集合之间的关系
包含(子集) A  B x (xA  xB)
不包含 A ⊈ B x (xA  xB)
相等 A = B  A  B  B  A
不相等 A  B
真包含 A  B  A  B  A  B
不真包含 A  B
思考: 和的定义
注意和是不同层次的问题
9
空集与全集
空集不含任何元素的集合
实例{x | x2+1=0xR} 就是空集
定理空集是任何集合的子集
A x (xxA) T
推论空集是惟一的.
证假设存在1和2,则12 且12,因此1=2
全集 E
相对性
在给定问题中,全集包含任何集合,即
A (AE )
10
幂集
定义 P(A) = { x | xA }
实例
P() = {},
P({}) = {,{}}
P({1,{2,3}})={,{1},{{2,3}},{1,{2,3}}}
计数
如果|A| = n,则|P(A)| = 2n