离散数学412 关系.ppt

第4章关系
关系的定义及其表示
关系运算
关系的性质
等价关系与偏序关系
1
关系的定义及其表示
有序对与笛卡儿积
二元关系的定义
二元关系的表示
2
由两个元素,如x和y,按照一定的顺序
组成的二元组称为有序对,记作<x,y>
实例:点的直角坐标(3,4)
有序对的性质
有序性<x,y><y,x> (当x y时)
<x,y>与<u,v>相等的充分必要条件是
<x,y>=<u,v>  x=u  y=v
例1 <2,x+5>=<3y4,y>,求 x, y.
解 3y4=2, x+5=y  y=2, x= 3
有序对
3
笛卡儿积
设A, B为集合,A与B 的笛卡儿积记作AB,
AB = { <x,y> | xA  yB }.
例2 A={0, 1}, B={a, b, c}
AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>}
BA ={<a,0>,<b,0>,<c,0>,<a,1>,<b,1>,<c,1>}
A = {}, B = 
P(A)A = {<,>, <{},>}
P(A)B = 
4
笛卡儿积的性质
对于并或交运算满足分配律
A(BC)=(AB)(AC)
(BC)A=(BA)(CA)
A(BC)=(AB)(AC)
(BC)A=(BA)(CA)
若A或B中有一个为空集,则AB就是空集.
A=B=
不适合交换律
ABBA (AB, A, B)
不适合结合律
(AB)CA(BC) (A, B, C)
若|A|=m, |B|=n, 则|AB|=mn
5
有序 n 元组和 n 阶笛卡尔积

(1) 由 n 个元素 x1, x2, …, xn按照一定的顺序排列构成
有序 n 元组,记作<x1, x2, …, xn>
(2) 设A1, A2, …, An为集合,称
A1A2…An={<x1, x2, …, xn> | xiAi, i=1,2, …,n}
为 n 阶笛卡儿积.
实例
(1,1,0)为空间直角坐标,(1,1,0)R R R
6
二元关系的定义

如果一个集合满足以下条件之一:
(1)集合非空, 且它的元素都是有序对
(2)集合是空集
则称该集合为一个二元关系, 简称为关系,记作R.
如<x,y>∈R, 可记作 xRy;如果<x,y>R, 则记作x y
实例:R={<1,2>,<a,b>}, S={<1,2>,a,b}.
R是二元关系, 当a, b不是有序对时,S不是二元关系
根据上面的记法,可以写1R2, aRb, a c等.
7
实例
例3
(1) R={<x,y> | x,yN, x+y<3}
={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}

(2) C={<x,y> | x,yR, x2+y2=1},其中R代表实数集合,
C是直角坐标平面上点的横、纵坐标之间的关系,
C中的所有的点恰好构成坐标平面上的单位圆.

(3) R={<x,y,z> | x,y,zR, x+2y+z=3},
R代表了空间直角坐标系中的一个平面.
8
5元关系的实例—数据库实体模型
员工号
姓名
年龄
性别
工资
301
302
303
304
…
张林
王晓云
李鹏宇
赵辉
…
50
43
47
21
…
男
女
男
男
…
1600
1250
1500
900
…
5元组:
<301,张林,50,男,1600>,<302,王晓云,43,女,1250>
9
从A到B的关系与A上的关系
设A,B为集合, A×B的任何子集所定义的二元关系叫做从 A 到 B 的二元关系, 当 A=B 时则叫做 A上的二元关系.
例4 A={0,1}, B={1,2,3},
R1={<0,2>}, R2=A×B, R3=, R4={<0,1>},
从A到B的关系: R1, R2, R3, R4, A上的关系R3和R4.
计数:
|A|=n, |B|=m, |A×B|=nm, A×B 的子集有个. 所以从A到B有个不同的二元关系. |A|=n, A上有不同的二元关系.
例如|A|=3, 则 A上有512个不同的二元关系.
10