关系21(运算)

1、1 二元关系的运算二元关系的运算与关系闭包与关系闭包 二元关系是集合，集合二元关系是集合，集合存在并，交，差，非和对存在并，交，差，非和对称差的运算。称差的运算。 故二元关系也存在这样故二元关系也存在这样的运算。的运算。 还有还有复合运算和逆运算复合运算和逆运算2设设1 1和和2 2是到的二元关系，则是到的二元关系，则（1）12 2（，）（，）（，）（，） 1 1或或 （，）（，）2 2（2 2）1 12 2（，）（，）（，）（，） 1 1 且且 （，）（，）2 2（3 3）1 1- -2 2（，）（，）（，）（，） 1 1 但但 （，）（，） 2 23n (4)n（5）1 2 （，）（，）（

2、，）（，）12 但但（，）（，） 1211RBAR11RBAR4例：，例：， 为整数集为整数集 （，），2ba （，），3ba , ab求：，R，5解：与都是上的二元关系解：与都是上的二元关系 （，），（，），（，），（，）， （，），（，），（，），（，），（，），（，），（，），（，），（，）（，），（，），（，）（，）（，）（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，）（，）nR 6R （，） ， （，） ， （，） ， （，） ，（，） ， （，） ， （，） ， （，） ，7关系矩阵可表示二元关系

3、，故可用矩阵的关系矩阵可表示二元关系，故可用矩阵的逻辑运算来研究二元关系的运算。逻辑运算来研究二元关系的运算。设设: : 1 1，2 2，n n 1 1，2 2，m m 1（ij），），2（ij） 则：12（cijij）12（ijij）12（ijijd）1R（ijC）8其中其中: :逻辑加逻辑加()()：， ，逻辑乘逻辑乘()()：， ， ， 逻辑非（） ：0，19对上例： 1010010110100101， 0001000000000000则用矩阵的逻辑运算:1011010110100101=SR10 0000000000000000， 0101101001011010R，11对任意二元关系

4、对任意二元关系R，G， 可以定义可以定义:n逆逆(inverse) : RC = | yRx n合成合成(复合复合)(composite):RG = | z( xRz zGy ) xzyGF12关于合成n顺序合成顺序合成(右合成右合成):RG = | z( xRz zGy ) n逆序合成逆序合成(左合成左合成):RG = | z( xGz zRy ) 13二元关系的复合（具体）二元关系的复合（具体）定义：定义： 设设1 1为到的二元关系，为到的二元关系，2 2为为 到的二元关系，到的二元关系，3 3（，）（，）（，）（，）1 1， 且且 （，）（，）2 2 记记 3 31 12 2 则则12是

5、由到的二元关系，是由到的二元关系， 称为称为1，2的复合关系的复合关系14例例2： 是父子关系，则是父子关系，则是祖孙关系。是祖孙关系。例：4321aaaa李兰，陈平，王兵，张华是学生集合4321bbbb遥感，自动化，硬件，软件是专业集合C4321cccc离散数学，操作系统，电子线路，工程制图 是课程集合15则：则：1 1（1 1，1 1），（），（1 1，3 3），）， （2 2，2 2），（），（2 2，4 4），）， （3 3，3 3），（），（3 3，4 4）, , （4 4，1 1），（），（4 4，4 4） 是选双学位专业的二元关系。是选双学位专业的二元关系。2 2（1 1，3 3

6、），（），（1 1，4 4），），（2 2，2 2），（），（2 2，3 3），（），（2 2，4 4），），（3 3，1 1），（），（3 3，2 2），（），（4 4，2 2），），（4 4，4 4） 是各专业本学期必修课的二元关系。是各专业本学期必修课的二元关系。163 31 12 2（1 1，1 1），（），（1 1，2 2），）， （1 1，3 3），（），（1 1，4 4），（），（2 2，2 2），）， （2 2，3 3），（），（2 2，4 4），（），（3 3，1 1），）， （3 3，2 2），（），（3 3，4 4），（），（4 4，2 2），）， （4 4，3 3），（

7、），（4 4，4 4） 是选双学位学生本学期必修课的二元关系是选双学位学生本学期必修课的二元关系17 )(ijanm， )(jkbLn， 则则：)(ikcLm ikjkijnjbaV1普通的矩阵乘法：普通的矩阵乘法：而二元关系的复合的矩阵布尔型乘法：而二元关系的复合的矩阵布尔型乘法：而 iknjjkijba118对 例 3， 有 ： 11001110010100101,2=1010001111101100 3 1 21110101111101111 在行处标上姓名，列处标上课程，就知在行处标上姓名，列处标上课程，就知谁该必修哪些课了。谁该必修哪些课了。19若是上二元关系，若是上二元关系， 若设

8、若设: : 1 1(1)(1)2 22 2（，）（，） （，），（，）（，），（，）(2)(2)设设n nn n已定义，则已定义，则 n+1n+1n nn nn+1n+1 = （，）（，），）（，）， （，）（，） 20关系的n次幂n关系的关系的n次幂次幂(nth power): 设设R A A, n N, 则则 (1) R0 = I IA; (2) Rn+1 = RnR, (n 1).n Rn表示的关系表示的关系, 是是R的关系图中长度为的关系图中长度为n的有向路径的起点与终点的关系的有向路径的起点与终点的关系.RnnRRRR个12nn-121 R0,R1,R2,R3,是否互不相等?R0R1

9、R2R3R4R5R6R7R8R0R1R2R3R4R5=R19=R33=R47=R6=R20=R34=R48=R7=R21=R35=R49=R8=R22=R36 =R15R9R10R11R14R16R1722n定理定理1: 设设 R A A, m,n N, 则则 (1) RmRn = Rm+n ; (2) (Rm)n = Rmn.n定理定理2: 设设 |A|=n, R A A, 则则 s,t N, 并并且且 使得使得 Rs = Rt. 23例：（，），（，），例：（，），（，）， （，），（，），（，），（，）， （，），（，）（，），（，） 是有限集，上的二元是有限集，上的二元关系。关系。的关

10、系图：的关系图：242 2（，），（，），（，），（，），（，），（，）， （，），（，），（，），（，），（，），（，）， ( (，），（，），（，），），（，），（，） 25 2 2的关系图中不存在的关系图中不存在（，），（，）， （，），故（，），故 2n n的关系图的构造：的关系图的构造： 可由的关系图来构造，从的每个结点可由的关系图来构造，从的每个结点a ai i出发，数出发，数n n条边。凡通过数条边。凡通过数n n条边能到达的结条边能到达的结点点a aj j，则有（则有（a ai i，a aj j）n n。关系图中从关系图中从i i出出发到发到j j的边是存在的。的边是存在的。

11、这样处理容易出错，用相关矩阵的布尔型这样处理容易出错，用相关矩阵的布尔型乘法来做，简单，又不容易错，还适宜于计算乘法来做，简单，又不容易错，还适宜于计算机处理。机处理。2621011110100001101010010110000100101001011000010010100101100001001R27n把逆关系也看成是一种运算，那么与其他一些运算把逆关系也看成是一种运算，那么与其他一些运算的组合可以有一些结论。设，是到的二元的组合可以有一些结论。设，是到的二元关系，是到的二元关系，是到的二元关系，是到的二元关系，是到的二元关系关系n1）（）（）cccn2）（）（）cccn3）n4）（）（

12、）CCCn5）（）（）C二元关系的运算RBAR286）（）（）CCC 7） (8) （） （） (9) （） 但： 且（） (10)CC29 1、函数复合运算应用到二元关系中、函数复合运算应用到二元关系中 2、求满足给定性质的二元关系、求满足给定性质的二元关系 -原有二元关系的扩充原有二元关系的扩充 3、从二元关系到多元关系、从二元关系到多元关系进一步的思考30关系的闭包n自反闭包自反闭包r( R )n对称闭包对称闭包s( R )n传递闭包传递闭包t( R )n闭包的闭包的性质性质, 求法求法, 相互关系相互关系31什么是闭包n闭包闭包(closure): 包含一些给定对象包含一些给定对象,

13、具有具有指定性质的最小集合指定性质的最小集合n“最小最小”: 任何包含同样对象任何包含同样对象, 具有同样具有同样性质的集合性质的集合, 都包含这个闭包集合都包含这个闭包集合n例例: (平面上平面上点点的凸包凸包)32自反闭包(reflexive closure)n自反闭包自反闭包: 包含给定关系包含给定关系R的最小自反关的最小自反关系系, 称为称为R的自反闭包的自反闭包, 记作记作r( R ). (1) R r( R ); (2) r( R )是自反的是自反的; (3) S( (R S S自反自反) t( R ) S ).G( R )G(t( R )33对称闭包(symmetric closure)n对称闭包对称闭包: 包含给定关系包含给定关系R的最小的最小对称对称关关系系, 称为称为R的的对称对称闭包闭包, 记作记作s( R ). (1) R s( R ); (2) s( R )是对称的是对称的; (3) S(