离散数学关系.ppt

.
*
第二章
关系
.
*
在现实生活中, 集合与集合之间还存在着某种联系，如同学关系、朋友关系等。这些关系正是各门学科所要研究的主要内容。离散数学从集合出发，主要研究集合之间的关系。本章内容主要研究二元关系。
.
*
本章主要内容：
关系的基本概念
关系的表示方法
关系的运算
关系的性质
关系的闭包
等价关系与划分
偏序关系
.
*

为了讨论关系，首先引入有序对和笛卡儿积两个概念。由两个元素a, b组成的集合{a, b}中，a和b是没有次序的。有时需要考虑有次序的两个元素，所以需要由两个元素组成新的东西，并且两个元素是有次序的。
, b 有次序地放在一起，称为一个有序对或序偶，记为(a, b)。在有序对(a, b)中，a 称为第一元素，b称为第二元素。且(a1, b1) = (a2, b2)当且仅当a1 = a2 且b1 = b2。
.
*
设A, B 是两个集合，集合{(x, y) | x∈A 且y∈B}称为A 和B 的笛卡儿积，也称卡氏积，记为A×B。用属于关系来表示就是：(x, y)∈A×B 当且仅当x∈A 且y∈B和(x, y)∉A×B 当且仅当x∉A或y ∉B。其中A 称为第一集合，B 称为第二集合。
.
*
设A={1,2,3}, B={a,b}，求A×B。
由笛卡儿积的定义可知有A×=×A= 。又由有序对的性质可知，一般没有A×B≠B×A。A×B也是一个集合，所以可以和另一集合C作笛卡儿积(A×B)×C，类似地有A×(B×C)。但是，一般没有(A×B)×C=A×(B×C)，且A×B中的元素既不是A 中的元素，也不是B中的元素。
.
*
如果B1A1，B2A2，则B1×B2  A1×A2。
.
*
证明 对(x, y)∈B1×B2，有x∈B1 且y∈B2，又因为B1  A1 ，B2  A2 ，则x∈A1 且y∈A2，所以(x, y)∈A1×A2，即B1×B2  A1×A2。
.
*
A, B, C 是任意集合，则：
(1) A×(B∪C) = (A×B)∪(A×C)，(B∪C)×A = (B×A)∪(C×A)。
(2) A×(B∩C) = (A×B)∩(A×C)，(B∩C)×A = (B×A)∩(C×A)。
(3) A×(B -C) = (A×B)- (A×C)，
(B -C)×A = (B×A) - (C×A)。
.
*
证明 (1) 对(x, y)∈A×(B∪C)，有x∈A 且y∈B∪C，因此x∈A 且(y∈B 或y∈C)，当y ∈B 时，由x∈A 和y∈B 得(x, y)∈A×B，当y∈C 时，由x∈A 和y∈C 得(x, y)∈A×C，所以(x, y)∈(A×B)∪(A×C)，即A×(B∪C) ⊆ (A×B)∪(A×C)。
因为A ⊆ A，B ⊆ B∪C 和C ⊆ B∪C 得A×B ⊆ A×(B∪C)和A×C ⊆ A×(B∪C)，因此(A×B)∪(A×C) ⊆ A×(B∪C)。
因此A×(B∪C) = (A×B)∪(A×C)成立。
同理可证(B∪C)×A = (B×A)∪(C×A)。