第4章 关系.ppt

宁波大学科技学院
离散数学
第二章关系
第二章关系
关系的概念
关系的表示与性质
关系的运算
关系的闭包运算
相容关系与覆盖
等价关系与划分
偏序关系
关系的概念
设A,B是任意两个集合,A×B的子集R称为从A到B的二元关系,当A=B 时,称R为A上的二元关系。
从上述定义可以看出A到B的二元关系,也是序偶的集合。
若<a, b>∈ R,则称a与b有关系R,记作a R b。
若,则称a与b没有关系R,记作。
例如:设A={a, b, c, d}, B={0, 1},则R={﹤a, 0﹥, ﹤b, 0﹥, ﹤c, 1﹥} 就是一个从A到B的二元关系。
设A,B是任意两个集合,R是A到B上的二元关系,若R=Ø,则称为空关系。若R = A×B,则称R为全关系。称为A上的恒等关系。
全关系
例如:设A={0, 1, 2},则。
例:设X={1,2,3,4},求X上的关系>解>={<2,1>,<3,1>,<4,1>,<3,2>,<4,2>,<4,3>}例:设X={1,2,3,4},若H={<X,Y>︱是正整数}
S={<x,y>︱是正整数},求H∪S,H∩S, ~H,S-HS
解:H={<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<3,1>,<4,4>,<4,2>}
S={<4,1>}
关系的概念
设A,B是两个集合,R是从A到B上的二元关系,则
(1)若存在b∈B,使得<a, b>∈R,则所有这样的a∈A组成的集合,称为二元关系R的定义域。记作dom(R)或D(R),即

(2)若存在a∈A,使得<a, b>∈ R,则所有这样的b∈B组成的集合,称为二元关系R的值域。记作ran(R)或R(R),即

R的定义域和值域一起称作R的域,记作FLDR,即
FLDR = dom(R)∪ran(R)
从X到Y的二元关系R,也可以用图解的方式表示,,X和Y是两个集合。xi是集合X中的元素,yj是集合Y中的元素,当且仅当xiRyj时,才有一条从xi指向yj的有向边。
关系的概念
图 图解表示法
关系的概念
若R和S是从集合A到B上的两个二元关系,则R和S的并、交、补、差也是A到B上的二元关系。
证明:因为R和S是从集合A到B上的二元关系
所以有R⊆ A×B,S⊆ A×B。从而有

即A∩B和A∪B都是A到B上的二元关系。
又因为

所以~R和~S也是A到B上的二元关系。
由于

故R-S也是A到B上的二元关系。
例设A={1,2,3,4},R1={(a,b);2/(a-b)},R2={(a,b);3/(a-b)}为A上的两个二元关系,求R1∪R2,R1∩R2, ,R1-R2,R1 R2
解:见p26
例设A={2,3,5,7},B={3,4,8},R={<x,y>︱x∈A,y∈B,x+y为偶数},求R的关系矩阵和关系图
R={<2,4>,<2,8>,<3,3>,<<5,3>,<7,3>}
关系矩阵为:
关系图为
关系图为
见P29
关系的表示与性质
关系的矩阵表示
关系的图形表示
关系的性质