4.1二元关系及其表示法 A到B上的全部二元关系；而0，{Kc,c>}为B上的二 元关系。 >一般来说，若|A=m,IB=n, A到B上的二元关系共 有2m个，A上的共有2m个二元关系； >特殊的二元关系： (1).空关系； (2).全域关系：EA={<x,y>x∈ANy∈A=A×A; (3).恒等关系：I4={<x,x>x∈A。 6/57
6/57 4.1 二元关系及其表示法 A到B上的全部二元关系；而 ，{<c, c>}为B上的二 元关系。 ➢一般来说，若|A|=m，|B|=n，A到B上的二元关系共 有 个，A上的共有 个二元关系； ➢特殊的二元关系： (1). 空关系； (2). 全域关系： ； (3). 恒等关系： 。 mn 2 2 2 m EA ={ x, y | x A y A}= A A I { x, x | x A} A =
4.1二元关系及其表示法 定义4.7：设R为二元关系，则 (1).domR={x|3y(xy)}为R的定义域； (2).ranR={y|3x(xy)》为R的值域； (3).fldR=domRUranR为R的域。 一般地，若R是A到B上的二元关系，则有 domRC A,ranR C B ·例4-1：设A={1,2,3,4,5,6},B={a,b,c,d}, 则R=[K2,a>,<2,b>,<3,b>,<4,c>,<6, c>},那么domR={2,3,4,6},ranR={a,b,c}。 7157
7/57 4.1 二元关系及其表示法 •定义4.7：设R为二元关系，则 (1). 为R的定义域； (2). 为R的值域； (3). 为R的域。 一般地，若R是A到B上的二元关系，则有 。 • 例4-1：设A={1,2,3,4,5,6}，B={a, b, c, d}， 则R={<2, a>，<2, b>，<3, b>，<4, c>，<6, c>}，那么domR={2,3,4,6}，ranR={a, b, c}。 domR ={x | y(xRy)} ranR ={y | x(xRy)} fldR = domRranR domR A,ranR B
4.1二元关系及其表示法 4.1.2关系的表示 ·1.集合表示法 由于关系也是一种特殊的集合，所以可以用集合 的两种基本的表示方法（枚举法，描述法）来表示 关系；如：设A={2],B={3},则A到B上的有关系 R={K2,3>};集合N上的“小于等于”关系： R={Kx,y>|(x,y)∈N∧(x≤y)}。 ●2. 关系图法 定义4.8：设集合A={X1,x2,…xn}到B[,y2,…yn} 上的二元关系R,以集合A,B中的元素为顶点，在 图中用“0”表示顶点，若x,,则可自顶点向 顶点y引有向边(x,y),其箭头指向y,用这种 方法画出的图称为关系图(Graph of Relation)。 8/57
8/57 4.1 二元关系及其表示法 4.1.2 关系的表示 • 1. 集合表示法 由于关系也是一种特殊的集合，所以可以用集合 的两种基本的表示方法(枚举法，描述法)来表示 关系；如：设A={2}，B={3}，则A到B上的有关系 R={<2,3>}；集合N上的“小于等于”关系： R={<x, y>|(x, y) N∧(x ≤ y) }。 • 2. 关系图法 •定义4.8：设集合A={ }到B={ } 上的二元关系R，以集合A，B中的元素为顶点，在 图中用“ο”表示顶点，若 则可自顶点 向 顶点 引有向边 ，其箭头指向 ，用这种 方法画出的图称为关系图(Graph of Relation)。 n x , x , x 1 2 n y , y , y 1 2 i Ry j x i x j y ( , ) i j x y j y
4.1二元关系及其表示法 例4-2：求集合A={1,2,3,4}的恒等关系，空关系， 全关系和小于关系的关系图。 ·3.关系矩阵 ●定义4.9：设R∈三A×B,A={a,42,…anm},B={b,b2,…bn} ,那么R的关系矩阵MR为一mXn矩阵，它的第i,j 分量)只取0或1，且 1当且仅当a,Rb 0当且仅当a,Rb 9/57
9/57 4.1 二元关系及其表示法 •例4-2：求集合A={1,2,3,4}的恒等关系，空关系， 全关系和小于关系的关系图。 • 3. 关系矩阵 •定义4.9：设 ，那么R的关系矩阵 为一m×n矩阵，它的第i，j 分量 只取0或1，且 , { , , }, { , , } R AB A = a1 a2 am B = b1 b2 bn MR ij r = i j i j i j a Rb a Rb r 当且仅当 当且仅当 0 1
4.2关系的运算 ·1.关系的交，并，补，差运算 ●定义4.10：设R和S为A到B的二元关系，其并，交 ,补，差运算定义如下： RUS={<x,y>xRyvxSy R∩S={<x,y>xy∧xy} R-S={<x,y>xy∧xy} R={<x,y>x乃y} ·例4-3：设A={1,2,3,4},若R={<x,y>|(x-y)/2是 整数，x,y∈A},S={Kx,y>|(x-y)/3是正整数， X∈yA},求RUS,R∩S,S-R,R,⊕RS。 解：R={K1,1>,<1,3>,<2,2>,<2,4>,<3,1>, <3,3>,<4,2>,<4,4>}, 10/57
10/57 4.2 关系的运算 • 1.关系的交，并，补，差运算 •定义4.10：设R和S为A到B的二元关系，其并，交 ，补，差运算定义如下： •例4-3：设A={1,2,3,4}，若R={<x, y>|(x-y)/2是 整数，x, y A}，S={<x, y>|(x-y)/3是正整数， x, y A}，求R∪S，R∩S，S-R，~R，R S。 解：R={<1,1>，<1,3>，<2,2>，<2,4>，<3,1>， <3,3>，<4,2>，<4,4>}， { , | } { , | } { , | } { , | } R x y xRy R S x y xRy xSy R S x y xRy xSy R S x y xRy xSy = − = = =