离散数学 关系及其运算

关系及其运算离散数学一关系南京大学计算机科学与技术系

关系及其运算 离散数学－关系 南京大学计算机科学与技术系

关系及其运算·关系的定义·关系的运算关系的性质0-1矩阵运算

关系及其运算 ⚫ 关系的定义 ⚫ 关系的运算 ⚫ 关系的性质 ⚫ 0-1矩阵运算

有序对(Ordered pair)(a,b)是集合(a,ia,b的简写，次序的体现(x,y)=(u,v) iff x=u 且 y=)若{(x,[x,}={(u,[u,以],则(x]={u或[x}=[u,以,因此x=u。假设y￥v(1) 若x=y,左边={[(x},而vx,.右边+[(x};(2)若xy,则必有(x,y)=(u,以,但y既不是u,又不是v,矛盾

有序对（Ordered pair） ⚫ (a, b)是集合{{a}, {a, b}}的简写 ⚫ 次序的体现 ⚫ (x,y)=(u,v) iff x=u 且 y=v 若{{x},{x,y}}={{u},{u,v}}，则{x}={u}或{x}= {u,v}, 因此x=u。 假设yv (1) 若x=y, 左边={{x}}, 而vx,右边{{x}}; (2) 若xy,则必有{x,y}= {u,v}, 但y既不是u,又不是v, 矛盾

笛卡尔乘积 （Cartesian Product)对任意集合A,B笛卡尔积AxB=((a,b)laeA,beB)例: [1,2,3)x[a,b) =((1, a), (2, a) , (3, a)(1, b), (2, b) , (3, b) )若A和B都是有限集合，A×B=|A|×|B

笛卡尔乘积（Cartesian Product） ⚫ 对任意集合A, B 笛卡尔积 AB = {(a, b)|aA, bB} ⚫ 例：{1,2,3}{a,b} = {(1, a), (2, a) , (3, a), (1, b), (2, b) , (3, b) } ⚫ 若A和B都是有限集合， |AB|= |A||B|

(二元）关系的定义若A,B是集合,从A到B的一个关系是AxB的一个子集。，子集可以是空集集合的元素是有序对关系意味着什么？两类对象之间建立起来的联系！

（二元）关系的定义 ⚫ 若A, B是集合,从A到B的一个关系是AB的一个 子集. ⚫ 子集可以是空集 ⚫ 集合的元素是有序对 ⚫ 关系意味着什么？ ⚫ 两类对象之间建立起来的联系！