离散数学：r03关系a

1关系的概念及运算关系的性质关系的闭包运算等价关系序关系关系2关系的基本概念A×B的子集称为A到B的一个二元关系(arelationfromAtoB)。A×B有多少个子集，就有多少种二元关系。关系通常用R表示，二元关系是由序偶构成的集合，

若〈a,b〉∈R,称a,b有关系R，记为aRb。

若〈a,b〉∉R,

称a,b没有关系R，记为。A1×A2×...×An的子集称为A1×A2×...×An上的一个n元关系(relation)。An＝A×A×...×A(n个A)的子集称为A上的n元关系。特别的，A2＝A×A的子集称为A上的二元关系。换句话讲，求关系R，就是求对应的序偶集合。3关系的基本概念 例1.设H={a,b,c,d}表示一个家庭中的父、母、子、女四个人构成的集合。从集合H到H上有以下二元关系： H1：同一家庭成员关系 H2：互不相识的关系 H3：长幼关系 求H1、H2、H3

。

解：H1=H×H H2=∅ H3={<a,c>,<a,d>,<b,c>,<b,d>}4关系的基本概念思考：对于A1×A2×...×An，若每个集合Ai是有限的，且|Ai|=ri，则A1×A2×...×An上不同的n元关系有多少个？关系相等的定义：设R1是A1×A2×...×An上的n元关系，R2是B1×B2×...×Bm上的m元关系，那么R1＝R2，当且仅当n＝m，且对一切i，1≤

i≤

n，Ai＝Bi，并且R1和R2是相等的有序n重组集合。5二元关系

最重要的关系是二元关系，本章主要讨论二元关系。令R为集合A到B的二元关系，由<x,y>∈R的所有x组成的集合domR称为R的定义域(domain)，即

由<x,y>∈R的所有y组成的集合ranR称为R的值域(range)，即集合A称为R的前域(predomain)，集合B称为R的陪域(codomain)。6二元关系domRX ranRY y4y5X1X2X5X4X3y3y2y1domRranRX到Y的关系7二元关系例2：设A＝{1,2,3,5}，B＝{1,2,4}，A到B的一个关系 H＝{<1,2>,<1,4>,<2,4>,<3,4>}，求domH,ranH.例3：设X＝{1,2,3,4}，求X上的大于关系>和dom>,ran>。解：domH={1,2,3}ranH={2,4}解：>={<2,1>,<3,1>,<4,1>,<3,2>,<4,2>,<4,3>}domH={2,3,4}ranH={1,2,3}8二元关系设IX是X上的二元关系，且满足IX={<x,x>|x∈X}，则称IX(或EX)是X上的相等关系。设R是A1×A2×...×An上的n元关系，如果R＝Φ，则称R为空关系。如果R＝A1×A2×...×An，则称R为全域关系(U)。几种特殊的关系：9关系的表示关系的矩阵表示： 设给定两个有限集合X={x1,x2,...xm}，Y={y1,y2,...,yn}，R为从X到Y的一个二元关系。则对应于关系R有一个关系矩阵(relationmatrix)

MR=[rij]m×n。其中，例4：设X＝{1,2,3,4}，求X上的大于关系>及其关系矩阵。解：>={<2,1>,<3,1>,<4,1>,<3,2>,<4,2>,<4,3>}10关系的表示关系的图形表示： 设给定两个有限集合X={x1,x2,...xm}，Y={y1,y2,...,yn}，R为从X到Y的一个二元关系。首先在平面上作出m个结点分别记为x1,x2,...,xm，然后另外作出n个结点分别记为y1,y2,...,yn，如果xiRyj，则可自结点xi至结点yj处作一有向弧，其箭头指向yj。这种方法联结起来的图就称为R的关系图(relationgraph)

。 如果X和Y是同一个集合，可以只画出一个集合的结点。例5：设A＝{1,2,3,5}，B＝{1,2,4}，A到B的一个关系H＝{<1,2>,<1,4>,<2,4>,<3,4>}，求H的关系图。11

例6.A={1,2,3},画出<,≤,>,UA和EA的关系图。

<：≤：>：UA：EA：

123123123123关系的表示12关系的表示 例7.设A={1,2,4,7,8}，B={2,3,5,7}，定义A到B的二元关系R={<a,b>|5能整除a+b}。分别用列举法、关系图和关系矩阵法描述R。 解:R={<2,3>,<7,3>,<8,2>,<8,7>}。R的关系矩阵和关系图分别如图所示:

MR=13关系的运算关系是序偶的集合，所以同一域上的关系，可以进行集合的所有运算。若Z和S是集合X到集合Y的两个关系，则Z、S的并、交、补、差仍是X到Y的关系。(因为Z和S都是X×Y的子集)14例8.

解：关系的运算15复合运算设R为A到B的关系，S为从B到C的关系，则R◦S称为A到C的复合(composite)关系，表示为

从R和S求R◦S称为关系的合成运算。例如，R1是关系“是···的兄弟”，R2是关系“是···的父亲”，则R1◦R2是关系“是···的叔伯”，R2◦R2是关系“是···的祖父”a1a2a3akb3b1bnbn-1b2c1c2c3cm-1cmABCRS16复合运算 例10.设集合A={1,2,3,4,5},R和S都是A上的二元关系，R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>},求R◦S,S◦R,R◦(S◦R),(R◦S)◦R。解：R◦S={<1,5>,<3,2>,<2,5>}S◦R={<4,2>,<3,2>,<1,4>}R◦(S◦R)={<3,2>}(R◦S)◦R={<3,2>}例9.如果关系R的值域与关系S的定义域的交集是空集,求合成关系R◦S。R◦S是空关系17复合运算性质：1)不可交换2)(可以结合)：设R1，R2和R3分别是从A到B，B到C和C到D的关系，那么(R1◦R2)◦R3=R1◦(R2◦R3)。证:设〈a,d〉∈(R1R2)R3,

那么存在c∈C,使〈a,c〉∈R1R2和〈c,d〉∈R3。因为〈a,c〉∈R1R2,则存在b∈B使〈a,b〉∈R1和

〈b,c〉∈R2。因为〈b,c〉∈R2和〈c,d〉∈R3,得〈b,d〉∈R2R3

又因为〈a,b〉∈R1，所以〈a,d〉∈R1(R2R3)。

这样,就证明了(R1R2)R3⊆

R1(R2R3)。

同理可证R1(R2R3)⊆(R1R2)R3

所以(R1R2)R3=R1(R2R3)18复合运算性质：3)设R是从X到Y的二元关系，IX和IY分别是X和Y上的相等关系，则IX◦R=R◦IY=R。4)关系的幂：设R是集合A上的二元关系,n∈N,那么R的n次幂记为Rn，且有R0＝IA，R◦R=R2，R◦R◦R=R3，...，Rn+1=Rn◦R。Rm◦Rn=Rm+n，(Rm)

n=Rmn

(m,n∈N)注意区分集合的笛卡尔积19复合运算性质：5)设R1是从A到B的关系，R2和R3是从B到C的关系，R4是从C到D的关系，那么20举反例证明R1(R2∩R3)≠R1R2∩R1R3。如果A={a},B={b1,b2,b3},C={c}

A到B的关系R1={〈a,b1〉,〈a,b2〉}

B到C的关系R2={〈b1,c〉,〈b3,c〉}

B到C的关系R3={〈b2,c〉,〈b3,c〉}

那么,R1(R2∩R3)=∅,R1R2∩R1R3={〈a,c〉}。证毕。21复合运算复合关系的矩阵表示 已知从集合X＝{x1,x2,...,xm}到集合Y＝{y1,y2,...yn}有关系R，则MR=[uij]表示R的关系矩阵。从集合Y＝{y1,y2,...yn}到集合Z＝{z1,z2,...,zp}的关系S，则MS=[vjk]表示S的关系矩阵。复合关系R◦S的矩阵MR◦S可构造如下：式中，∨代表逻辑加，满足0∨0=0,0∨1=1,1∨0=1,1∨1=1； ∧代表逻辑乘，满足0∧0=0,0∧1=0,1∧0=0,1∧1=1。22复合运算 例11：设集合A＝{1,2,3,4,5}，A上关系R={<1,2>,<1,3>,<3,4>,<2,2>},S={<4,2>,<2,1>,<2,5>,<3,1>,<1,3>}，求R◦S。23逆关系设R为X