4.1二元关系及其表示法 A到B上的全部二元关系;而Q,〖<c,c}为B上的二 元关系。 一般来说,若|A-m,|B|=n,A到B上的二元关系共 有2m个,A上的共有m2个二元关系 >特殊的二元关系: (1).空关系 (2).全域关系:E4={<x,y>x∈A∧y∈A}=A×A; (3).恒等关系:4={<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|y(xy)}为R的定义域 (2).PmnR={y|x(x8y)}为R的值域; (3).R= domrUranR为R的域。 般地,若R是A到B上的二元关系,则有 domrc a. ranrc 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]。 7l57
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={<2,3 ;集合N上的“小于等于”关系: R<x,y(x,y)∈N∧(x≤y)}。 2.关系图法 定义4.8:设集合A={x12x2…xn}到B={12y2…yn} 上的二元关系R,以集合A,B中的元素为顶点,在 图中用“o”表示顶点,若x则可自顶点x向 顶点y引有向边(xy),其箭头指向y,用这种 方法画出的图称为关系图( graph of re lat on)。 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={a1,a2,…am},B={b,b2,…bn} 那么R的关系矩阵M为-m×n矩阵,它的第i,j 分量亐只取0或1,且 1当且仅当a,Rb 010当且仅当aRb 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
42关系的运算 ·1.关系的交,并,补,差运算 定义4.10:设R和S为A到B的二元关系,其并,交 ,补,差运算定义如下: R∪S={<x,y> x Ryvxsy R∩S={<x,yxy入xSy} R-S={<x,y>xy∧xSy} R={<x,y>→xy} 例4-3:设A=1,2,3,4},若R=x,y(x-y)/2是 整数,X,y∈eA},S={x, y>|(xy)/3是正整数, xyA},求RUS,R∩S,S-R,"R,RS。 解:R=区1,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 = − = = =