第四章二元关系 4.1二元关系及其表示法 4.1.1序偶与笛卡尔积 定义4.1:由两个元素x和y按一定的次序组成的二 元组称为有序对或序偶( Ordered),记作 其中x是它的第一元素,y是它的第二元素。 性质4.1:(1):=当且仅当ⅹ=y; (2):=当且仅当x=u,y=Vv; 例如:平面上的坐标,ⅹ,y∈R;等都是序偶 1157
1/57 第四章 二元关系 4.1 二元关系及其表示法 4.1.1 序偶与笛卡尔积 • 定义4.1：由两个元素x和y按一定的次序组成的二 元组称为有序对或序偶(Ordered)，记作， 其中x是它的第一元素，y是它的第二元素。 • 性质4.1：(1)： = 当且仅当x=y； (2)： =当且仅当x=u, y=v; 例如：平面上的坐标，x, y R；等都是序偶。
4.1二元关系及其表示法 定义4.2:设A,B是两个集合,称集合 A×B={x,y>x∈A∧y∈B} 为集合A与B的 笛卡尔积 Descartes product)。 例:设A=1,2;B={a,b则A×B=1,a>,,,,<b, 质4.2:( A×B|=|A×|B(A,B为有限 A×O=0,0×A=O (3).不适合交换律,即A×B≠BXA(除非A,B=O 或A=B); 非A=O 倉律 (4).不适合结合 (A×B)×G≠A×(B×C(除 D) (5).对U和∩运算满足分配律, 2/57
2/57 4.1 二元关系及其表示法 •定义4.2：设A，B是两个集合，称集合 为集合A与B的 笛卡尔积(Descartes Product)。 例：设A={1,2}；B={a, b}则A ×B={，， ，}；B ×A={，，，}。 •性质4.2：(1). | A ×B |=|A|×|B|(A, B为有限 集合)； (2). ； (3). 不适合交换律，即A×B ≠B×A(除非A，B= 或A=B)； (4). 不适合结合律，(A×B)×C ≠A×(B×C)(除 非 )； (5). 对∪和∩运算满足分配律， A B ={ x, y | x A y B} A = ， A = A = B= C=
4.1二元关系及其表示法 Ax(B∪C)=(A×B)∪(AxC)(B∪C)xA=(B×A∪(C×A) A×(B∩C)=(A×B)∩(AxC)(B∩C)xA=(B×A∩C×A); 证明:∈Ax(BUC >x∈A∧y∈B∪C →x∈AA(y∈BVy∈C) 分(x∈Ay∈B)v(x∈A∧y∈C ∈(A×B)V∈(AxC) ∈(AxB)∪(A×C) (6)AcC∧BcD→A×BC×D,且当A=B=O 或A≠0∧B≠O时,逆命题成立。 3/57
3/57 4.1 二元关系及其表示法 证明： (6). ，且当 或 时，逆命题成立。 (B C ) (A B) (A C),(B C ) A (B A) (C A); (B C ) (A B) (A C),(B C ) A (B A) (C A), = = = = A A , ( ) ( ) , ( ) , ( ) ( ) ( ) ( ) , ( ) x y A B A C x y A B x y A C x A y B x A y C x A y B y C x A y B C x y A B C A CB D AB CD A = B= A B
4.1二元关系及其表示法 ·定义4.3:一个有序n≥2)元组是一个有序对, 它的第一个元素为有序的n1元组; 当且仅当a=b,i=1,2,…,n n维空间中的点M的坐标(x12x2…,x)为有序的n元组 定义4.4:设A1,A2 为n个集合(n≥2),称集 合{x12x2…,xnx1∈A1∧x2∈A2A…Axn∈An} 为n维卡氏积或n阶笛卡尔积,记作A1xA2x…×A, 当A1=A2=…=A时简记为A 4/57
4/57 4.1 二元关系及其表示法 •定义4.3：一个有序n(n≥2)元组是一个有序对， 它的第一个元素为有序的n-1元组 ，第二个元素为 ，记为 即： ； 当且仅当 n维空间中的点M的坐标 为有序的n元组 。 • 定义4.4：设 为n个集合(n ≥2)，称集 合 为n维卡氏积或n阶笛卡尔积，记作 ， 当 时简记为 。 a1 ,a2 , ,an−1 n a a1 ,a2 , ,an−1 ,an a1 ,a2 , ,an−1 ,an = a1 ,a2 , ,an a1 ,a2 , ,an = b1 ,b2 , ,bn ai = bi ,i =1,2, ,n ( , , , ) 1 2 n x x x x1 , x2 , , xn A A An , , , 1 2 { , , , | } 1 2 n 1 1 2 2 n An x x x x A x A x A1 A2 An A1 = A2 == An n A
4.1二元关系及其表示法 4.1.2二元关系 定义4.5:若集合F中的全体元素为有序的nn≥2 元组,则称F为n元关系,特别地,当n=2时,称F 为二元关系,简称关系。 对于二元关系F,若∈F,常记作xhy,反之 xy;规定O为n元空关系,也是二元空关系,简称 空关系 定义4.6:设A,B为两集合,A×B的集合子集R称 为A到B的二元关系,特别地,当A=B时,称R为A上 的二元关系。 例:A={a,b},B={o},则AXB的子集有0, ,<b,c习 5/57
5/57 4.1 二元关系及其表示法 4.1.2 二元关系 •定义4.5：若集合F中的全体元素为有序的n(n≥2) 元组，则称F为n元关系，特别地，当n=2时，称F 为二元关系，简称关系。 对于二元关系F，若 ，常记作 ，反之 ；规定 为n元空关系，也是二元空关系，简称 空关系。 •定义4.6：设A，B为两集合，A×B的集合子集R称 为A到B的二元关系，特别地，当A=B时，称R为A上 的二元关系。 例：A={a, b}，B={c}，则A×B的子集有 ， {}，{}，{, }， x, y F xFy xF y
4.1二元关系及其表示法 A到B上的全部二元关系;而Q,〖特殊的二元关系: (1).空关系 (2).全域关系:E4={x∈A∧y∈A}=A×A; (3).恒等关系:4={<x,x丬x∈A} 6/57
6/57 4.1 二元关系及其表示法 A到B上的全部二元关系；而 ，{}为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={,,,,<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={，，，，}，那么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={}；集合N上的“小于等于”关系： R={|(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 Ryvxsy R∩S={xy∧xSy} R={→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>,,,, ,,<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)/2是 整数，x, y A}，S={|(x-y)/3是正整数， x, y A}，求R∪S，R∩S，S-R，~R，R S。 解：R={，，，，， ，，}， { , | } { , | } { , | } { , | } R x y xRy R S x y xRy xSy R S x y xRy xSy R S x y xRy xSy = − = = =