离散数学 关系及其运算

从A到B的二元关系笛卡尔乘积的子集“从A到B的关系”R；RCAxB关系”若A=B:称为“集合A上的（二元）例子常用的数学关系：不大于、整除、集合包含等网页链接、文章引用、相互认识

从A到B的二元关系 ⚫ 笛卡尔乘积的子集 ⚫ “从A到B的关系”R；RAB ⚫ 若A=B： 称为“集合A上的（二元）关系” ⚫ 例子 ⚫ 常用的数学关系：不大于、整除、集合包含等 ⚫ 网页链接、文章引用、相互认识

特殊的二元关系集合A上的空关系：空关系即空集全域关系E:E^=((x,J)Ix,y EA)恒等关系I:I={(x,x)IxEA)

特殊的二元关系 ⚫ 集合A上的空关系: 空关系即空集 ⚫ 全域关系EA : EA ={ (x, y) | x, y A } ⚫ 恒等关系IA : IA ={(x, x) | xA }

函数是一种特殊的关系函数f:A-→BR={(x,f(x)|xEA}是一个从A到B的一个关系何种关系可以看做一个函数？

函数是一种特殊的关系 ⚫ 函数 f :A→B ⚫ R={ (x, f(x)) | xA }是一个从A到B的一个关系 ⚫ 何种关系可以看做一个函数？

关系的表示假设A={a,b, c,d,B={α,β, // 假设为有限集合集合表示: R,={(a, β),(b, α),(c, α), (c, ))0-1矩阵有向图aβa2a00b100b1011CYd000dBA

关系的表示 假设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

关系的基本符号定义域和值域等有关记法domR = (x |Ey(x, y)eR)ranR = (y [Ex (x, y)eR)FldR = domR U ranRR TA= [(x,y) IxEA^xRy) 二RR[A] = (y /Ex (xEA ^ (x,y)eR))=ran(RTA) ranR例: A={1,2,3,4,5},B={1,3,5}, A上关系R:R={(1,2), (1,4), (2,3), (3,5), (5,2));求 R个B、R[B]、R(1)和R(2)

关系的基本符号 ⚫ 定义域和值域等有关记法 ⚫ domR = {x | y (x, y)R} ⚫ ranR = {y | x (x, y)R} ⚫ FldR = domR  ranR ⚫ 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}, A上关系R： R={(1,2), (1,4), (2,3), (3,5), (5,2)}, 求 RB、R[B]、R(1)和R(2)