离散数学第四章二元关系

1、第四章 二元关系第四章 二元关系本章讨论的关系（主要是二元关系），它仍然是一种集合，但它是比前一章更为复杂的集合。关系是笛卡尔乘积的子集，它的元素是有序二元组的形式，这些有序二元组中的两个元素来自于两个不同或者相同的集合。因此，关系是建立在其它集合基础之上的集合。关系中的有序二元组反映了不同集合中元素与元素之间的关系，或者同一集合中元素之间的关系。本章首先讨论关系的基本表达形式，然后给出关系的运算，最后讨论几种常用的关系。 回顾主要内容关系的基本概念关系的性质关系的表示关系的运算合成关系的关系图、关系矩阵特殊关系：等价关系和划分，相容关系和覆盖，偏序关系和哈斯图等。 4.1关系的基本概念定义：

2、设 且 A1,A2,An为n个任意集合，(a) 称R为A1,A2,An间的n元关系；(b) 若n=2，则称R为A1到A2的二元关系；(c) 若 ，则称R为空关系；若 ，则称R为全关系；(d) 若A1=A2=An =A，则称R为A上的n元关系。一、关系的定义一、关系的定义例：令则称R1是N上的一元关系，R2是N上的二元关系，R3是N上的三元关系。如无特殊指定，“关系”概指二元关系。若序偶 属于R，则记作 或 ，否则，记作 或 。一、关系的定义例：设集合A=a,b,B=2,5,8则令则 均是由A到B的关系。同理，则 是由B到A的关系。同理，则 是由B到B的关系。一、关系的定义例：设集合A=2,3,

3、5,9，试给出集合A上的小于或等于关系，大于或等于关系。解：令集合A上的小于或等于关系为R1，大于或等于关系为R2，根据定义有： 二、关系的相等定义：设R1为A1,A2,An间的n元关系，R2为B1, B2,Bm间的m元关系，如果：（1）n=m （2）若 1in，则Ai=Bi（3）把R1和R2作为集合看，R1=R2。则称n元关系R1和m元关系R2相等，记作R1=R2二、关系的相等例：设R1为从Z到I+的二元关系，R2和R3都是I上的二元关系从集合的观点来看，R1=R2=R3。但是就二元关系来说，R2=R3，不等于R1。三、关系的定义域和值域关系R(从A到B的关系)的定义域(简称为域)定义为：关

4、系R的值域定义为：显然，有例：设A=2,3,5,B=2,6,7,8,9，由A到B的关系R定义为：当且仅当a整除b时，有aRb。可得:D(R)=2,3R(R)=2,6,8,9AB235268974.2关系的表示定义：设A和B为任意的非空有限集，R为任意一个从A到B的二元关系。以 中的每个元素为结点对每个 皆画一条从x到y的有向边，这样得到的一个图称为关系R的关系图。 一、关系图例：A=1,2,4; B=3,5,6;关系R=,A124B356一、关系图例：设A=2,3,4,5,6,B=6,7,8,12，从A到B的二元关系R为 ，画出其关系图。解：先求出R一、关系图 对称关系 反对称关系二、关系矩阵

5、定义： 给定两个有限集合X=x1,x2,xm和Y= y1,y2,yn，R是从X到Y的二元关系，如果有： 则称 是R的关系矩阵，记作MR。 例：设A=1,2,3,4,R为定义在A上的二元关系，R=,，写出关系矩阵。二、关系矩阵例：设A=1,2,3,B=a,b,c, R是A到B的二元关系，并且 ，试画出R的关系图，给出关系矩阵。二、关系矩阵如果关系矩阵主对角线上的记入值全为1，则R是自反的； 如果主对角线上的记入值全为0，则R是反自反的； 如果矩阵关于主对角线是对称的，则R是对称的；如果矩阵关于主对角线是反对称的，(亦即rij=1时则一定有rji=0),则R是反对称的；如果对于任意的i,j,k,

6、rij=1并且rjk=1时一定有rik=1 ，则R是可传递的； 如果存在i,j,k, rij=1并且rjk=1时，有rik 不等于1 ，则R是不可传递的；4.3关系的性质定义：设R为A上的二元关系(1)若对每个 ，皆有 ，则称R为自反的。用式子来表述即是： R是自反的 (2)若对每个 ，皆有 ，则称R为反自反的。用式子来表述即是： R是反自反的 关系的性质(3) 对任意的 ，若 ，则 ，就称R为对称的。用式子来表述即是： R是对称的 (4) 对任意的 ，若 且 ， 则x=y，就称R为反对称的。用式子来表述即是： R是反对称的 关系的性质(5) 对任意的 ，若 且 ， 则 ，就称R为可传递的。用

7、式子来表述即是： R是可传递的 (6) 存在 ，并且 而 ， 就称R为不可传递的。用式子来表述即是： R是不可传递的 关系的性质例1：考虑自然数集合上的普通相等关系“=”，大于关系“”和大于等于关系“ ”具有的性质。 解：(1) “=”关系是自反的、对称的、反对称的、可传递的；(2)“”关系是反自反的、反对称的、可传递的；(3)“ ”关系是自反的、反对称的、可传递的。例2：空集上的二元关系的性质。自反的、对称的、反对称的、反自反的、可传递的 区分概念：空关系vs空集上的关系空关系：对于任何集合A, 称空集为A上的空关系.性质：若A非空，空关系是反自反的，对称的，反对称的，可传递的；若A是空集，

8、该空关系是自反的，反自反的，对称的，反对称的，可传递的空集上的关系：自反的，反自反的，对称的，反对称的， 可传递的。在空集上可定义任意元关系。集合的压缩和开拓定义：设R为集合A上的二元关系且SA ，则称S上的二元关系R(SS)为R在S上的压缩，记为R|S， 并称R为R|S在A上的开拓。 定理：设R为A的二元关系且 ，那么：(1)若R是自反的，则 也是自反的； (2)若R是反自反的，则 也是反自反的； (3)若R是对称的，则 也是对称的； (4)若R是反对称的，则 也是反对称的； (5)若R是可传递的，则 也是可传递的； 4.4关系的运算注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中

9、。设R1和R2是从A到B的二元关系，那么R1R2， R1R2 ， R1-R2， R1R2也是从A到B的二元关系，它们分别被称为二元关系R1和R2的交、并、差分和对称差分。4.4关系的运算例：设集合A=a,b,c，B=d,e，定义A到B的二元关系R1=,R2=,则4.4关系的运算定义：设R是从X到Y的关系，S是从Y到Z的关系，于是可用RS表示从X到Z的关系，通常称它是R和S的合成关系，用式子表示即是： 一、关系的合成例： 给定集合X=1,2,3,4，Y=2,3,4和Z=1,2,3。设R是从X到Y的关系，并且S是从Y到Z的关系，并且R和S给定成： 试求R和S的合成关系，并画出合成关系图给出合成关系

10、的关系矩阵。 一、关系的合成解：找出所有这样的偶对 x, z 对于某一个y来说，能有x+y=6和y-z=1，由上述的偶对就可构成从X到Z的关系RS 。 一、关系的合成定义布尔运算：0+0=0，1+0=0+1=1+1=111=1， 01= 10= 00=0对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。一、关系的合成注意：设R是从集合X到集合Y的关系，S是从集合Y到集合Z的关系，于是有：如果R关系的值域与S关系的定义域的交集是个空集，则合成关系RS也是个空关系；若至少有一个序偶 x, yR ，其中笫二个成员是S中的某一个序偶的笫一个成

11、员，则合成关系就是个非空关系。对于合成关系RS来说，它的定义域是集合X的子集，而它的值域则是Z的子集，事实上，它的定义域是关系R的定义域的子集，它的值域是关系S的值域的子集。 一、关系的合成定理：给定集合X,Y,Z和W，设R1是从 X到Y的关系，R2和R3是Y到Z的关系，R4是从Z到W的关系，于是有：一、关系的合成证明：当且仅当存在某一个yY，能使 R1和 R2 R3 ，才有 R1 (R2 R3)，而 对任意的x,zR1o(R2R3)y(x,yR1y,zR2R3)y(x,yR1(y,zR2 y,zR3) y(x,yR1y,zR2) (x,yR1 y,zR3) y(x,yR1y,zR2) y(x

12、,yR1y,zR3) x,zR1oR2 x,zR1oR3 x,z（R1oR2）（R1oR3） 得证一、关系的合成证明：当且仅当存在某一个yY ，能使 R1和 R2 R3 ，才有 R1 (R2 R3) ，而 对以上证明过程(a)式使用的是存在量词对满足分配律对(b)存在量词对不满足分配律，但它满足蕴涵式x(A(x) B(x)xA(x) x B(x)这里应注意是一、关系的合成合成运算是对关系的二元运算，使用这种运算，能够由两个关系生成一个新的关系，对于这个新的关系又可进行合成运算，从而生成其它关系。 定理：设R1是从X到Y的关系，R2是从Y到Z的关系，R3是从Z到W的关系，于是有一、关系的合成一、

13、关系的合成例：给定关系R和S，并且则关系的幂定义：如果R1是从X1到X2的关系，R2是从X2到的X3关系，Rn是从Xn到Xn+1的关系，则无括号表达式 表达了从X1到Xn+1的关系。当X1=X2=Xn+1和R1=R2 =Rn时，也就是说当集合X中的所有Ri都是同样的关系时，X中的合成关系 可表达成Rn，并称作关系R的幂。 定义：给定集合X，R是X中的二元关系。设 ，于是R的n次幂Rn可定义成 (a) R0是集合X中的恒等关系IX，亦即(b) 关系的幂定理：给定集合X，R是X中的二元关系。设 ，于是可有 例：给定集合X=a,b,c，R1,R2,R3,R4是X中的关系，并给定给出这些关系的各次幂关

14、系的幂解：关系的幂定理：设X是含有n个元素的有限集合，R是X中的二元关系。于是存在这样的s和t，能使 ， 证明：集合X中的每一个二元关系都是 的子集，X有n个元素， 有n2个元素， 有 个元素，每一个元素都是 的一个子集，也是一种二元关系，因而，在X中有 个不同的二元关系。所以，不同的二元关系R的幂不会多于个 。但是序列 中有 项，因此这些的方幂中至少有两个是相等的。证毕。 二、合成关系的矩阵表达和图解设集合X=x1,x2,xm,Y=y1,y2 ,yn,Z=z1,z2,zp, R是从X到Y的关系，S是从Y到Z的关系，MR和MS第i行第j列的元素分别是aij和bij，它们是0或者1。则合成关系

15、关系矩阵上的元素为定义布尔运算：0+0=0，1+0=0+1=1+1=111=1， 01= 10= 00=0对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。二、合成关系的矩阵表达和图解例：求合成关系 的关系矩阵二、合成关系的矩阵表达和图解当用 表示这些矩阵的合成矩阵二、合成关系的矩阵表达和图解例：设集合X=0,1,2,3，R是X中的关系，并且画出 和 的关系图解：0231(a)0231(b)0231(c)三、关系的求逆运算关系R的逆关系 定义如下：对于所有的 和 来说，逆关系的关系矩阵：原关系矩阵转置逆关系的关系图：原关系图中颠倒弧线上箭头的方向。区分 ：逆关系vs补关系 在关系图和关系矩阵上的体现？三、合成关系的求逆运算定理：设R是从集合X到Y的关系。S是从集合Y到Z的关系。于是有 证明：对于任何 ， 和 来说，如果xRy和ySz，则会有 和 ，因为还有 和 ，所以又有 。因此可有 。利用关系矩阵也可以理解， 的转置和 是一样的。三、合成关