南京大学：《离散数学》课程教学资源（PPT课件讲稿）集合论——关系及其运算（集合的运算）

关系的表示 假设={a,bcd},B={0,B,y}∥假设为有限集合 集合表示:R={(a,B),( b,O),(c,O)、(c,” 0-1矩阵 有向图 a010 b100 B 10 000 y B

关系的表示 假设A={a,b,c,d}, B={α,β,γ} // 假设为有限集合 ⚫ 集合表示: R1={(a, β), (b, α), (c, α),(c, γ)} 0-1矩阵 有向图             0 0 0 1 0 1 1 0 0 a 0 1 0 b c d    a d c b    A B

二元关系和有向图 关系 RCAXB 有向图(VD,ED) A和B是集合 顶点集VD=AB 有序对集合 有向边集ED (x,y)∈R 从x到y有一条边 若A=B,R中存在序列:(x1x2) 图D中存在从x1到xn的长 N(X2, x3). (Xn-1,XD) 度为n-1的通路

二元关系和有向图 关系 RAB A和B是集合 有序对集合 (x,y)R 若A=B, R中存在序列：(x1 ,x2 ), (x2 ,x3 ),…,(xn-1 ,xn ) 有向图 (VD , ED ) 顶点集 VD = AB 有向边集ED 从x到y有一条边 图D中存在从x1 到 xn 的长 度为 n-1的通路

关系的运算(1) 关系是集合,所有的集合运算对关系均适用 ●例子 自然数集合上:“<”∪“=”等同于“ ●自然数集合上:“<”“≥”等同于“ 自然数集合上“<”∩“>”等同于

关系的运算（1） ⚫ 关系是集合, 所有的集合运算对关系均适用 ⚫ 例子: ⚫ 自然数集合上: “<”  “=” 等同于 “” ⚫ 自然数集合上: “”  “”等同于“=” ⚫ 自然数集合上: “<”  “>”等同于

关系的运算(2) ●与定义域和值域有关的运算 ●domR={x|习y(xy)∈R} ●ranR={y|x(x2y)∈R} fldR=domR∪ranR R个A={(xy)|x∈ A MRy}R R]={y|3x(x∈A∧(xy)ER)}=ram(R个A)∈ranR 例:A={1,2,3,4,5},B={1,3,56},A上关系R R={(1,2),(1,4)(2,3)3,5)(5,2)}2 求R个B、R[B、R(1)和R(2)

关系的运算（2） ⚫ 与定义域和值域有关的运算 ⚫ dom R = {x | y (x,y)R} ⚫ ran R = {y | x (x,y)R} ⚫ fld R = dom R  ran R ⚫ R A = {(x,y) | xA xRy}  R ⚫ R[A] = {y | x (xA  (x,y)R)}= ran(RA)  ranR ⚫ 例：A={1,2,3,4,5}, B={1,3,5,6}, A上关系R： R={(1,2), (1,4),(2,3),(3,5),(5,2)}, 求 RB、R[B]、R(1)和R(2)

关系的运算(3) ●逆运算 R1={(x,y)(yx)∈R} 注意如果R是从A到B的关系,则R是从B到A的。 (R)=R 例子:(R∪R2)=R1UR21 (,y)E (rUr2)- e(,x)(rUR2) <>(y,x)∈R或(y,x)∈R2 (x,y)∈R1或(x,y)∈R2

关系的运算（3） ⚫ 逆运算 ⚫ R -1 = { (x, y) | (y,x)R} ⚫ 注意:如果R是从A到B的关系,则R -1是从B到A的。 ⚫ (R -1 ) -1 = R ⚫ 例子：(R1R2 ) -1 = R1 -1R2 -1 ⚫ (x, y)  (R1R2 ) -1  (y, x)(R1R2 ) ⚫  (y, x)R1 或 (y, x)R2 ⚫  (x, y)R1 -1 或 (x, y)R2 -1