中国科学技术大学：《离散数学》课程教学资源（PPT课件讲稿）第二部分 集合论 第四章 二元关系

第四章二元关系 4.1二元关系及其表示法 4.1.1序偶与笛卡尔积 ● 定义4.1：由两个元素x和y按一定的次序组成的二 元组称为有序对或序偶(0 rdered),记作, 其中x是它的第一元素，y是它的第二元素。 ·性质4.1：(1)：=当且仅当x=y; (2):=当且仅当x=u,y=v; 例如：平面上的坐标,x,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={lx∈A∧y∈B} 为集合A与B的 笛卡尔积(Descartes Product)。 ，品安 2, a> 1>,}。 性质4.2：(1).AB=A×B|A,B为有限 ●1 集合)； (2.A×0=0,0×A=0 (3).不适合交换律，即AXB≠BXA(除非A,E =0 或A=B); (4).不适合结合律， (AXB)XC丰AX(BXC)(除 非A=⑩VB=⑦VC=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二元关系及其表示法 A×(BUC)=(A×B)U(A×C),(BUC)×A=(B×A)U(C×A) A×(B∩C)=(A×B)∩(A×C),(B∩C)×A=(B×A)∩(C×A) 证明：∈A×(BUC) 台x∈AAy∈BUC 台x∈AA(y∈BVy∈C) 台(x∈AAy∈B)V(x∈A∧y∈C) 台∈(A×B)V∈(A×C) →∈(A×B)U(A×C) (6).ACCABED→A×BC×D,且当A=B=0 或A≠①人B≠①时，逆命题成立。 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  CB  D AB  CD A = B=  A   B 

4.1二元关系及其表示法 定义4.3：一个有序n(n≥2)元组是一个有序对， 它的第一个元素为有序的n-1元组 ,第二个元素为an,记为 即：,an>= =; 当且仅当4，=b,i=1,2,…,n n维空间中的点M的坐标(x,x2,…,xm)为有序的n元组 定义4.4：设A1,A2,…,An为n个集合(n≥2），称集 合{X1∈A∧x2∈A2∧…∧n∈An} 为n维卡氏积或n阶笛卡尔积，记作A×A,××A, 当A1=A,=…=An时简记为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中的全体元素为有序的n(n≥2) 元组，则称F为n元关系，特别地，当n=2时，称F 为二元关系，简称关系。 对于二元关系F,若eF, 常记作xy,反之 xy;规定0为n元空关系， 也是二元空关系，简称 空关系。 定义4.6：设A,B为两集合， ● AXB的集合子集R称 为A到B的二元关系，特别地，当A=B时，称R为A上 的二元关系。 例：A={a,b},B={c}, 则AXB的子集有O {Ka,c>},{Kb,c>},{Ka,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上的全部二元关系；而0，{Kc,c>}为B上的二 元关系。 >一般来说，若|A=m,IB=n, A到B上的二元关系共 有2m个，A上的共有2m个二元关系； >特殊的二元关系： (1).空关系； (2).全域关系：EA={x∈ANy∈A=A×A; (3).恒等关系：I4={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|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>,,,,},那么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={，，，，}，那么domR={2,3,4,6}，ranR={a, b, c}。 domR ={x | y(xRy)} ranR ={y | x(xRy)} fldR = domRranR 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={}；集合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={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  AB 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={xRyvxSy R∩S={xy∧xy} R-S={xy∧xy} R={x乃y} ·例4-3：设A={1,2,3,4},若R={|(x-y)/2是 整数，x,y∈A},S={Kx,y>|(x-y)/3是正整数， X∈yA},求RUS,R∩S,S-R,R,⊕RS。 解：R={K1,1>,,,,, ,,}, 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 =    − =     =    =        