南京大学：《离散数学》课程教学资源（PPT课件讲稿）关系、函数及其运算

特殊的二元关系 口集合A上的空关系:空关系即空集 口全域关系E:E4={(x,y|x,y∈A} 口恒等关系LA:I4={(x,x)xEA} 口函数f:AB R={(x,fx)|x∈A}是一个从A到硝的一个关系

特殊的二元关系  集合A上的空关系: 空关系即空集  全域关系 EA : EA ={ (x, y) | x, y A }  恒等关系 IA : IA={(x, x) | xA }  函数 f : A→B R={ (x, f(x)) | xA }是一个从A到B的一个关系 6

关系的表示 口假设A={abc4,B={a,1y//假设为有限集合 口集合表示:R1={(月,(b,∞,(ca,(c少} 0-1矩阵 有向图 010 b100 10 d000 B

关系的表示  假设A={a,b,c,d}, B={α,β,γ} // 假设为有限集合  集合表示: R1={(a, β), (b, α), (c, α), (c, γ)} 0-1矩阵 有向图 7             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到有一条边 若A=B,R中存在序列:(x1x2) 图D中存在从x到xn的长 N(X2, x3). (Xn-1,XD) 度为n-1的通路

二元关系和有向图 8 关系 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) 口关系是集合,所有的集合运算对关系均适用 例: 自然数集合上:“<”∪“=”等同于“S” 自然数集合上:“≤”∩“≥”等同于“=” 自然数集合上:“<”∩“>”等同于

关系的运算(1)  关系是集合, 所有的集合运算对关系均适用  例: ◼ 自然数集合上: “<”  “=” 等同于 “” ◼ 自然数集合上: “”  “”等同于“=” ◼ 自然数集合上: “<”  “>”等同于 9

关系的运算(2) 口与定义域和值域有关的运算 a dom r={x|3y(x,∈R} d ran r={y|彐x(x∈R fldR=domR∪ranR RA={(x)|x∈ AAxRyCR restriction也记作R个A,RA 口R[4]={y|丑x(x∈A∧(x∈}=ran( Crane 口例 口A={1,234,5},B={1356},A上关系R R={1,2),(1,4),(2,3),3,5),(5,2)}, 求R↑B、RB]

关系的运算(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 restriction 也记作 𝑅 ↾ 𝐴, 𝑅|𝐴  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] 10