离散数学第四章二元关系-2nd

1、1/36第四章 二元关系大连理工大学软件学院陈志奎 教授办公室： 综合楼411，Tel： 87571525实验室：教学楼A318/323，Tel：87571620/24Mobile: Email: 2/36回顾关系的定义，二元关系笛卡尔积构成集合（子集）关系的性质自反，反自反，对称，反对称，传递，不可传递关系相等关系压缩与开拓3/364.3关系的表示定义：设A和B为任意的非空有限集，R为任意一个从A到B的二元关系。以 中的每个元素为结点对每个 皆画一条从x到y的有向边，这样得到的一个图称为关系R的关系图。 一、关系图例：A=1,2,4; B=3,5,6;关系R=,A124B3564/36一、关

2、系图例：设A=2,3,4,5,6,B=6,7,8,12，从A到B的二元关系R为 ，画出其关系图。解：先求出R5/36一、关系图 对称关系 反对称关系6/36二、关系矩阵定义： 给定两个有限集合X=x1,x2,xm和Y= y1,y2,yn，R是从X到Y的二元关系，如果有： 则称 是R的关系矩阵，记作MR。 例：设A=1,2,3,4,R为定义在A上的二元关系，R=,，写出关系矩阵。7/36二、关系矩阵例：设A=1,2,3,B=a,b,c, R是A到B的二元关系，并且 ，试画出R的关系图，给出关系矩阵。8/36二、关系矩阵如果关系矩阵主对角线上的记入值全为1，则R是自反的； 如果主对角线上的记入值全

3、为0，则R是反自反的； 如果矩阵关于主对角线是对称的，则R是对称的；如果矩阵关于主对角线是反对称的，(亦即rij=1时则一定有rji=0),则R是反对称的；如果对于任意的i,j,k, rij=1并且rjk=1时一定有rik=1 ，则R是可传递的； 如果存在i,j,k, rij=1并且rjk=1时，有rik 不等于1 ，则R是不可传递的；9/364.4关系的运算注意：由于关系也是特殊的集合，因此集合的运算也适用于关系中。设R1和R2是从A到B的二元关系，那么 ， ， 也是从A到B的二元关系，它们分别被称为二元关系R1和R2的交、并、差分和对称差分。10/364.4关系的运算例：设集合A=a,b,

4、c，B=d,e，定义A到B的二元关系R1=,R2=,则11/364.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的合成关系，并画出合成关系图给出合成关系的关系矩阵。 12/36一、关系的合成解：找出所有这样的偶对 对于某一个y来说，能有x+y=6和y-z=1，由上述的偶对就可构成从X到Z的关系RS 。 13/36一、关系的合成定义布尔运算：0+0=

5、0，1+0=0+1=1+1=111=1， 01= 10= 00=0对两个关系矩阵求其合成时，其运算法则与一般矩阵的乘法是相同的，但其中的加法运算和乘法运算应改为布尔加和布尔乘。14/36一、关系的合成注意：设R是从集合X到集合Y的关系，S是从集合Y到集合Z的关系，于是有：如果R关系的值域与S关系的定义域的交集是个空集，则合成关系RS也是个空关系；若至少有一个序偶 ，其中笫二个成员是S中的某一个序偶的笫一个成员，则合成关系就是个非空关系。对于合成关系RS来说，它的定义域是集合X的子集，而它的值域则是Z的子集，事实上，它的定义域是关系R的定义域的子集，它的值域是关系S的值域的子集。 15/36一、

6、关系的合成定理：给定集合X,Y,Z和W，设R1是从 X到Y的关系，R2和R3是Y到Z的关系，R4是从Z到W的关系，于是有：16/36一、关系的合成证明：当且仅当存在某一个 ，能使 和 ，才有 ，而 对任意的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,yR1y,zR3) x,zR1oR2 x,zR1oR3 x,z（R1oR2）（R1oR3） 得证17/36一、关系的合成证明：当且仅当存在某一个 ，能使 和 ，才有 ，而 18/36对以上证明过程(a)式使

7、用的是存在量词对满足分配律对(b)存在量词对不满足分配律，但它满足蕴涵式x(A(x) B(x)xA(x) x B(x)这里应注意是19/36一、关系的合成合成运算是对关系的二元运算，使用这种运算，能够由两个关系生成一个新的关系，对于这个新的关系又可进行合成运算，从而生成其它关系。 定理：设R1是从X到Y的关系，R2是从Y到Z的关系，R3是从Z到W的关系，于是有20/36一、关系的合成21/36一、关系的合成例：给定关系R和S，并且则22/36关系的幂定义：如果R1是从X1到X2的关系，R2是从X2到的X3关系，Rn是从Xn到Xn+1的关系，则无括号表达式 表达了从X1到Xn+1的关系。当X1=

8、X2=Xn+1和R1=R2 =Rn时，也就是说当集合X中的所有Ri都是同样的关系时，X中的合成关系 可表达成Rn，并称作关系R的幂。 定义：给定集合X，R是X中的二元关系。设 ，于是R的n次幂Rn可定义成 (a) R0是集合X中的恒等关系IX，亦即(b) 23/36关系的幂定理：给定集合X，R是X中的二元关系。设 ，于是可有 例：给定集合X=a,b,c，R1,R2,R3,R4是X中的关系，并给定给出这些关系的各次幂24/36关系的幂解：25/36关系的幂定理：设X是含有n个元素的有限集合，R是X中的二元关系。于是存在这样的s和t，能使 ， 证明：集合X中的每一个二元关系都是 的子集，X有n个元

9、素， 有n2个元素， 有 个元素，每一个元素都是 的一个子集，也是一种二元关系，因而，在X中有 个不同的二元关系。所以，不同的二元关系R的幂不会多于个 。但是序列 中有 项，因此这些的方幂中至少有两个是相等的。证毕。 26/36二、合成关系的矩阵表达和图解设集合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。则合成关系 关系矩阵上的元素为定义布尔运算：0+0=0，1+0=0+1=1+1=111=1， 01= 10= 00=0对两个关系矩阵求其合成时，其运算法则与一般矩

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