关系的闭包、等价关系关系的闭包、等价关系离散数学集合论南京大学计算机科学与技术系回顾回顾l关系：笛卡尔积的子集l关系的运算l集合运算；复合运算；逆l0-1矩阵运算l关系的性质l自反，反自反，对称，反对称，传递l图特征；矩阵特征l函数的定义l子集的像l单射与满射l反函数l函数的复合l函数加法与乘法提要提要l闭包的定义l闭包的计算公式l传递闭包的Warshall算法l等价关系l等价类l划分“闭包闭包”一个对象橘黄色圈满足：是圆的（性质）包含所给对象如果有个绿色圆也能包含该对象，就一定也能包含这个橘黄圈青色框满足：是正方形的（性质）包含所给对象如果有个红色正方形也能包含该对象，就一定也能包含这个青色框关系的闭包：一般概念关系的闭包：一般概念l设R是集合A上的关系，P是给定的某种性质（如：自反、对称、传递），满足下列所有条件的关系R1称为R的关于P的闭包:lRR1 lR1 满足性质P l如果存在集合A上的关系R，R 满足性质P 并包含R，则R1R l自反闭包r(R)、对称闭包s(R)、传递闭包t(R)自反闭包的定义自反闭包的定义l设 R的是集合A上的关系，其自反闭包r(R)也是A上的关系，且满足：l r(R)满足自反性；l R r(R); l对A上的任意关系R, 若R也满足自反性，且也包含R，则r(R)Rl例子l令A=1,2,3, R=(1,1), (1,3), (2,3), (3,2)。则r(R)=(1,1), (1,3), (2,3), (3,2), (2,2), (3,3)。自反闭包的计算公式自反闭包的计算公式lr(R) = RIA, IA是集合A上的恒等关系(证明所给表达式满足自反闭包定义中的三条性质) 1. 对任意 xA, (x,x)IA, 因此, (x,x)RIA 2. RRIA 3. 设 R 集合A 上的自反关系，且RR, 则对 任意 (x,y)RIA, 有(x,y)R, 或者 (x,y)IA。 对两种情况，均有 (x,y)R, 因此, RIAR 对称闭包的计算公式对称闭包的计算公式ls(R) = RR-1, 这里R-1是R的逆关系ls(R)是对称的。对任意 x,yA, 如果 (x,y)s(R), 则(x,y)R 或者(x,y) R-1, 即(y,x) R-1, 或者 (y,x) R, (y,x)s(R)lR s(R)l设R是集合A上的对称关系, 并且RR, 则对任意(x,y)s(R), 有(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) R 因此, s(R) R连通关系连通关系lR是集合A上的关系l定义集合A上的“R连通”关系R*如下：l对任意a,bA, a R*b 当且仅当当且仅当：存在t1,t2tk A(k是正整数)，满足(a,t1) R; (t1,t2)R; (tk,b)R。(可以表述为：从a到b之间存在长度至少为1的通路)l显然：对任意a,bA, a R*b 当且仅当存在某个正整数k,使得aRkb。l于是：R* = R1R2R3Ri =传递闭包传递闭包利用公式证明闭包相等利用公式证明闭包相等l证明：r(s(R) = s(r(R)lr(s(R) = r(RR-1) = (RR-1)IA = (RIA)(R-1IA-1) (注意：IA=IA-1, 并用等幂率) = (RIA)(RIA)-1 = s(RIA) = s(r(R)注意：r(s(R)一般省略为rs(R)用定义证明有关闭包的性质用定义证明有关闭包的性质注意：传递关系的对称闭包不一定是传递的。比如：(1,3)关于关于P的的闭包是否存在性？闭包是否存在性？l令R是A上的关系l若存在，则必是唯一的。l存在性：l令：lAA（自反、对称、传递）保证了R存在l易证：R具有性质Pl闭包计算可行性尚待讨论l自反闭包和对称闭包显然存在l传递闭包理论上存在有限集合上的传递闭包有限集合上的传递闭包A 中只有中只有 n 个不同的元素，如果在个不同的元素，如果在R中存在一条从中存在一条从a到到b的长度至少为的长度至少为1的通路，那么存在一条长度不超过的通路，那么存在一条长度不超过n的的从从a到到b的通路。的通路。 若若 xR*y, 则存在某个自然数则存在某个自然数 k, 1 k n, 满足满足 xRky. 用矩阵乘法计算传递闭包用矩阵乘法计算传递闭包nn矩阵相乘，结果中每1项，要做(2n-1次)布尔运算(积与和)，总共需要计算n2项。nn矩阵相加,要做n2次布尔运算(和)本算法共进行n-1次矩阵乘和加。总运算量(n2(2n-1)+n2) (n-1)=2n3(n-1)Warshall算法算法l求传递闭包的Warshall算法16Warshall算法的过程（续）求传递闭包的Warshall算法17求传递闭包的求传递闭包的Warshall算法算法求传递闭包的Warshall算法18nWarshall算法通过关系图模型更容易理解：要确定传递闭包的关系矩阵中的每一项，对应于确定关系图中任意两顶点之间是否存在路径这实际上就是把传递闭包运算通过图模型转换为找路径的运算求传递闭包的求传递闭包的Warshall算法（续）算法（续）求传递闭包的Warshall算法19aiajak中间点 ，在集合a1,.,a ak-1中aiajakall 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算法20Warshall算法的过程算法的过程l求传递闭包的Warshall算法21Warshall算法的过程（续）算法的过程（续）l求传递闭包的Warshall算法22Warshall算法算法过过程程lALGORITHM WARSHALL (MR : nn的0-1矩阵）l1. W := MRl2. FOR k :=1 to nl FOR i :=1 to nl FOR j :=1 to nl Wi, j Wi, j (Wi, kWk, j)l3. 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, 使xk=yl；并有m, n, 使yn=zm；则有 xkn=zml等价类等价类lR是非空集合A上的等价关系，xA，等价类xR=y| yA xRyl每个等价类是A的一个非空子集。l例子：对3同余关系: RZZ， xRy 当且仅当 是整数。l个等价类： 0=, -6, -3, 0, 3, 6, 9, ; 1=, -5, -2, 1, 4, 7, ; 2=, -4, -1, 2, 5, 8, 11, 等价类的代表元素等价类的代表元素l对于等价类xR= y | yA xRy ，x称为这个等价类的代表元素l其实，该等价类的每个元素都可以做代表元素：若xRy，则x=yl证明：对任意元素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:(a, b)R(c,d) 当且仅当 a+d=b+c 证明这是等价关系，并给出其商集 等价关系的一个例子等价关系的一个例子lR1,R2分别是集合X1,X2上的等价关系。定义X1X2上的关系S：(x1,x2)S (y1,y2) 当且仅当 x1R1y1 且 x2R2y2l证明：S是X1X2上的等价关系l自反性 对任意(x,y)X1X2, 由R1,R2满足自反性可知， (x,x)R1, ( y,y) R2; (x,y)S(x,y); S自反。l对称性 假设( x1,x2)S ( y1,y2), 由S的定义以及R1,R2满足对称性可知： ( y1,y2)S (x1,x2); S对称。l传递性 假设(x1,x2)S ( y1,y2), 且( y1,y2)S ( z1,z2), 则x1R1y1, y1R1z1, x2R2y2, y2R2z2, 由R1,R2满足传递性可知：x1R1z1, 且x2R2z2, 于是： (x1,x2)S (z1,z2); S传递。集合的划分集合的划分A1A6A5A4A3A2A集合A的 划分, , 是A的一组非空子集的集合，即 (A), 且满足： 1. 对任意 xA, 存在某个 Ai, 使得 xAi. 2. 对任意 Ai, Aj, 如果 ij, 则：由等价关系定义的划分由等价关系定义的划分l假设R是集合A上的等价关系，给定aA, R(a)是由R 所诱导的等价类。lQ=R(x)|xA是相应的商集。l容易证明，这样的商集即是A的一个划分：l对任意 aA, aR(a) (R 是自反的)l对任意 a,bAl(a,b) R 当且仅当 R(a)=R(b), 同时l(a,b) R 当且仅当 R(a)R(b)= 商集即划分商集即划分 证明证明l不相等的等价类必然不相交。换句话说，有公共元素的任意两个等价类必然相等。l证明：l假设R(a)R(b), 设c是一个公共元素。l根据等价类的定义，(a,c)R, (b,c)Rl对任意xR(a), (a,x)R, 由R的传递性和对称性，可得(c,x)R, 由此可知(b,x)R, 即xR(b), R(a)R(b)l同理可得：R(b)R(a)。因此: R(a)=R(b)根据一个划分定义等价关系根据一个划分定义等价关系A1A6A5A4A3A2Axyz给定 A 上一个划分，可以如下定义A 上的等价关系 R :x,yA, (x,y)R 当且仅当: x,y 属于该划分中的同一块。显然，关系 R 满足自反性、对称性、传递性。因此：R 是等价关系。利用等价类解题：利用等价类解题：l证明： 从1,2,.,2000中任取1001个数，其中必有两个数x,y，满足x/y=2k。 (k为整数)。想起鸽笼原理没？等价关系与划分：一个例子等价关系与划分：一个例子-解解l建立1000个集合, 每个集合包括1至2000之间的一个奇数以及该奇数与2的k次幂的乘积, 但最大不超过2000。可以证明这1000个集合的集合是集合1,2,3,., 2000上的一个划分。注意任意两个1到2000之间的正整数x,y在同一划分块中当且仅当x/y=2k。(k为整数)。l定义集合1,2,3,., 2000上的一个关系R，任意x,y，xRy当且仅当x/y=2k。易证这是一个等价关系。其商集即上面的划分。小结小结l闭包的定义l闭包的计算公式l传递闭包的Warshall算法l等价关系，等价类l商集，划分作业作业l教材教材8.4lp. 424-425：23, 28l教材教材8.5lp. 430-434：15, 20, 35, 41, 54