关系的闭包等价关系ppt课件

1、关系的闭包、等价关系关系的闭包、等价关系离散数学集合论南京大学计算机科学与技术系回想回想l关系：笛卡尔积的子集l关系的运算l集合运算；复合运算；逆l0-1矩阵运算l关系的性质l自反，反自反，对称，反对称，传送l图特征；矩阵特征l函数的定义l子集的像l单射与满射l反函数l函数的复合l函数加法与乘法提要提要l闭包的定义l闭包的计算公式l传送闭包的Warshall算法l等价关系l等价类l划分“闭包闭包一个对象橘黄色圈满足：是圆的性质包含所给对象假设有个绿色圆也能包含该对象，就一定也能包含这个橘黄圈青色框满足：是正方形的性质包含所给对象假设有个红色正方形也能包含该对象，就一定也能包含这个青色框关系的闭

2、包：普通概念关系的闭包：普通概念l设R是集合A上的关系，P是给定的某种性质如：自反、对称、传送，满足以下一切条件的关系R1称为R的关于P的闭包:lRR1 lR1 满足性质P l假设存在集合A上的关系R，R 满足性质P 并包含R，那么R1R l自反闭包rR、对称闭包sR、传送闭包tR自反闭包的定义自反闭包的定义l设 R的是集合A上的关系，其自反闭包rR也是A上的关系，且满足：l rR满足自反性；l R rR; l对A上的恣意关系R, 假设R也满足自反性，且也包含R，那么rRRl例子l令A=1,2,3, R=1,1, 1,3, 2,3, 3,2。那么rR=1,1, 1,3, 2,3, 3,2, 2

3、,2, 3,3。自反闭包的计算公式自反闭包的计算公式lrR = RIA, IA是集合A上的恒等关系l证明所给表达式满足自反闭包定义中的三条性质l 1. 对恣意 xA, x,xIA, 因此, x,xRIAl 2. RRIAl 3. 设 R 集合A 上的自反关系，且RR, 那么对 恣意 x,yRIA, 有x,yR, 或者 x,yIA。 对两种情况，均有 x,yR, 因此, RIAR 对称闭包的计算公式对称闭包的计算公式lsR = RR-1, 这里R-1是R的逆关系lsR是对称的。对恣意 x,yA, 假设 x,ysR, 那么x,yR 或者x,y R-1, 即y,x R-1, 或者 y,x R, y,

4、xsRlR sRl设R是集合A上的对称关系, 并且RR, 那么对恣意x,ysR, 有x,y R, 或者x,y R-1.l情况1: x,y R, 那么 x,y Rl情况2: x,y R-1, 那么 y,x R, 于是 y,x R。根据R的对称性：x,y Rl 因此, sR R连通关系连通关系lR是集合A上的关系l定义集合A上的“R连通关系R*如下：l对恣意a,bA, a R*b 当且仅当：存在t1,t2tk Ak是正整数，满足a,t1 R; t1,t2R; tk,bR。可以表述为：从a到b之间存在长度至少为1的通路l显然：对恣意a,bA, a R*b 当且仅当存在某个正整数k,使得aRkb。l于

5、是：R* = R1R2R3Ri = kkR1传送闭包传送闭包*)(RRt.*),( , ,),( ,),(),( ,),( ,., ,., , *),( , *),( 1.112121RzxRzttyyssxtttsssRzyRyxkjkj因此满足：以及则有若.),( ),( ,),(),( ,),( ,),( ,., ,),( , 3. . 2211121*RyxRRyttttxRyttxtttRyxRARRRkkk的传递性，根据于是满足：则有若。且包含上的传递关系是集合设利用公式证明闭包相等利用公式证明闭包相等l证明：rsR = srRlrsR = rRR-1l = RR-1IAl = R

6、IAR-1IA-1 留意：IA=IA-1, 并用等幂率l = RIARIA-1l = sRIAl = srRl留意：rsR普通省略为rsR用定义证明有封锁包的性质用定义证明有封锁包的性质 )()(2) ; )(1 )( RtsRtRtsRt满足对称性）（明：根据定义，我们只需证的对称闭包，左边是注意：)()(RtsRst证明：满足对称性。于是：对称性，满足而满足对任意证明。显然满足传递性，显然我们只需要证明：的传递闭包，考虑到左边是证明)(),(),(),(),(),(),(.,),(),()(),(),(),.,(),(),(),( ,., ),()yx,( : ) 1 ()()( (ii)

7、 )( )( (i) ),2(11221121RtsRtsxyRsxtRsttRstyRsRsytRsttRstxtttRtsRtsRtsRRkkk留意：传送关系的对称闭包不一定是传送的。比如：1,3关于关于P的闭包能否存在性？的闭包能否存在性？l令R是A上的关系l假设存在，那么必是独一的。l存在性：l令：lAA自反、对称、传送保证了R存在l易证：R具有性质Pl闭包计算可行性尚待讨论l自反闭包和对称闭包显然存在l传送闭包实际上存在P|具有性质XXRXR 有限集合上的传送闭包有限集合上的传送闭包niRRRRRAnA2n1i t(R) ,| 的传递闭包是：上的关系则假如A 中只需中只需 n 个不同

8、的元素，假设在个不同的元素，假设在R中存在一条从中存在一条从a到到b的长度至少为的长度至少为1的通路，那么存在一条长度不超越的通路，那么存在一条长度不超越n的的从从a到到b的通路。的通路。 假设假设 xR*y, 那么存在某个自然数那么存在某个自然数 k, 1kn, 满足满足 xRky. 有何差别？上述公式和1*)(:iiRRRt用矩阵乘法计算传送闭包用矩阵乘法计算传送闭包nRRRRRtniMMMMMRRRRRt.)( 32)(2n1i传递闭包：nn矩阵相乘，结果中每1项，要做2n-1次布尔运算积与和，总共需求计算n2项。nn矩阵相加,要做n2次布尔运算和本算法共进展n-1次矩阵乘和加。总运算量

9、n22n-1+n2 n-1=2n3n-1Warshall算法算法l Warshall算法的过程续求传送闭包的求传送闭包的Warshall算法算法nWarshall算法经过关系图模型更容易了解：n要确定传送闭包的关系矩阵中的每一项，对应于确定关系图中恣意两顶点之间能否存在途径n这实践上就是把传送闭包运算经过图模型转换为找途径的运算求传送闭包的求传送闭包的Warshall算法续算法续 aiajak中间点 ，在集合a1,.,a ak-1中也就是所需的结果。即内的通路。均在集合存在中间节点到从当且仅当对。的关系矩阵即为这里：计算算法迭代式地用的乘幂不直接计算 , 3. , 1, , 2 , 1 2.

10、, 1. Warshall , )(2101RtnkjikRiiRMWaaaaajiWnkMRWWWMaiajakall interior vertices in a1,.,a ak-1Wki,j=1 if and only if:Wk-1i,j=1, or Wk-1i,k=1 and Wk-1k,j=1 求传送闭包的求传送闭包的Warshall算法续算法续Warshall算法的过程算法的过程l Warshall算法的过程续算法的过程续l Warshall算法过程算法过程lALGORITHM WARSHALL MR : nn的0-1矩阵l1. W := MRl2. FOR k :=1 to n

11、l FOR i :=1 to nl FOR j :=1 to nl Wi, j Wi, j Wi, kWk, jl3. Output WlEND OF ALGORITHM WARSHALL这个语句在三重循环内，执行n3次，每次执行2个布尔运算和与积总运算量: 2n3等价关系的定义等价关系的定义l满足性质：自反、对称、传送。l“等于关系的推行l例子l对3同余关系: RZZ， xRy 当且仅当 是整数。lRNN， xRy iff 存在正整数k,l，使得xk=yl。l自反: 假设x是恣意自然数，当然xk=xk ;l对称：假设有k,l, 使xk=yl；也就有l,k, 使yl=xk；l传送：假设有k,l

12、, 使xk=yl；并有m, n, 使yn=zm；那么有 xkn=zml3yx 等价类等价类lR是非空集合A上的等价关系，xA，等价类xR=y| yA xRyl每个等价类是A的一个非空子集。l例子：对3同余关系: RZZ， xRy 当且仅当 是整数。l个等价类：0=, -6, -3, 0, 3, 6, 9, ; l1=, -5, -2, 1, 4, 7, ; l2=, -4, -1, 2, 5, 8, 11, 3yx等价类的代表元素等价类的代表元素l对于等价类xR= y | yA xRy ，x称为这个等价类的代表元素l其实，该等价类的每个元素都可以做代表元素：假设xRy，那么x=yl证明：对恣意

13、元素t, 假设tx, 那么xRt, 根据R的对称性与传送性，且xRy, 可得yRt, 因此 ty, xy; 同理可得yx 。商集商集lR是非空集合A上的等价关系，xA，那么其一切等价类的集合称为商集，A/Rl集合A=a1,a2, , an上的恒等关系IA是等价关系，商集A/IA=a1, a2, anl定义自然数集的笛卡儿乘积上的关系R:la, bRc,d 当且仅当 a+d=b+cl 证明这是等价关系，并给出其商集 等价关系的一个例子等价关系的一个例子lR1,R2分别是集合X1,X2上的等价关系。定义X1X2上的关系S：lx1,x2S y1,y2 当且仅当 x1R1y1 且 x2R2y2l证明：

14、S是X1X2上的等价关系l自反性 对恣意x,yX1X2, 由R1,R2满足自反性可知， x,xR1, y,y R2; x,ySx,y; S自反。l对称性 假设 x1,x2S y1,y2, 由S的定义以及R1,R2满足对称性可知： y1,y2S x1,x2; S对称。l传送性 假设x1,x2S y1,y2, 且 y1,y2S z1,z2, 那么x1R1y1, y1R1z1, x2R2y2, y2R2z2, 由R1,R2满足传送性可知：x1R1z1, 且x2R2z2, 于是： x1,x2S z1,z2; S传送。集合的划分集合的划分A1A6A5A4A3A2A集合A的 划分, , 是A的一组非空子集

15、的集合，即 A, 且满足： 1. 对恣意 xA, 存在某个 Ai, 使得 xAi. AAii i.e.2. 对恣意 Ai, Aj, 假设 ij, 那么：jiAA由等价关系定义的划分由等价关系定义的划分l假设R是集合A上的等价关系，给定aA, Ra是由R 所诱导的等价类。lQ=Rx|xA是相应的商集。l容易证明，这样的商集即是A的一个划分：l对恣意 aA, aRa R 是自反的l对恣意 a,bAla,b R 当且仅当 Ra=Rb, 同时la,b R 当且仅当 RaRb= 商集即划分商集即划分 证明证明l不相等的等价类必然不相交。换句话说，有公共元素的恣意两个等价类必然相等。l证明：l假设RaRb

16、, 设c是一个公共元素。l根据等价类的定义，a,cR, b,cRl对恣意xRa, a,xR, 由R的传送性和对称性，可得c,xR, 由此可知b,xR, 即xRb, RaRbl同理可得：RbRa。因此: Ra=Rb根据一个划分定义等价关系根据一个划分定义等价关系A1A6A5A4A3A2Axyz给定 A 上一个划分，可以如下定义A 上的等价关系 R :x,yA, x,yR 当且仅当: x,y 属于该划分中的同一块。显然，关系 R 满足自反性、对称性、传送性。因此：R 是等价关系。利用等价类解题：利用等价类解题：l证明：l 从1,2,.,2000中任取1001个数，其中必有两个数x,y，满足x/y=2k。l k为整数。等价关系与划分：一个例子等价关系与划分：一个例子-解解l建立1000个集合, 每个集合包括1至2000之间的一个奇数以及该奇数与2的k次幂的乘积, 但最大不超越2000。可以证明这100