关系的闭包等价关系

《关系的闭包等价关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、包：一般概念设R是集合A上的关系，P是给定的某种性质（如：自反、对称、传递），满足下列所有条件的关系R1称为R的关于P的闭包:RR1R1满足性质P如果存在集合A上的关系R’，R’满足性质P并包含R，则R1R’自反闭包r(R)、对称闭包s(R)、传递闭包t(R)自反闭包的定义设R的是集合A上的关系，其自反闭包r(R)也是A上的关系，且满足：r(R)满足自反性；Rr(R);对A上的任意关系R’,若R’也满足自反性，且也包含R，则r(R)R’例子令A={1,2,3},R={(1,1),(1,3),(2,3),(3,2)}。则r(R)={(1,1),(1,3),(2,3),

3、(3,2),(2,2),(3,3)}。自反闭包的计算公式r(R)=RIA,IA是集合A上的恒等关系(证明所给表达式满足自反闭包定义中的三条性质)1.对任意xA,(x,x)IA,因此,(x,x)RIA2.RRIA3.设R’集合A上的自反关系，且RR’,则对任意(x,y)RIA,有(x,y)R,或者(x,y)IA。对两种情况，均有(x,y)R’,因此,RIAR’对称闭包的计算公式s(R)=RR-1,这里R-1是R的逆关系s(R)是对称的。对任意x,yA,如果(x,y)s(R),则(x,y)R或者(x,y)R-1,即(y,x)R-1,或者

4、(y,x)R,(y,x)s(R)Rs(R)设R’是集合A上的对称关系,并且RR’,则对任意(x,y)s(R),有(x,y)R,或者(x,y)R-1.情况1:(x,y)R,则(x,y)R’情况2:(x,y)R-1,则(y,x)R,于是(y,x)R’。根据R’的对称性：(x,y)R’因此,s(R)R’连通关系R是集合A上的关系定义集合A上的“R连通”关系R*如下：对任意a,bA,aR*b当且仅当：存在t1,t2…tkA(k是正整数)，满足(a,t1)R;(t1,t2)R;…;(tk,b)R。(可以表述为：从a到b之间存在长度至少为1的通路

5、)显然：对任意a,bA,aR*b当且仅当存在某个正整数k,使得aRkb。于是：R*=R1R2R3…Ri…=传递闭包利用公式证明闭包相等证明：r(s(R))=s(r(R))r(s(R))=r(RR-1)=(RR-1)IA=(RIA)(R-1IA-1)(注意：IA=IA-1,并用等幂率)=(RIA)(RIA)-1=s(RIA)=s(r(R))注意：r(s(R))一般省略为rs(R)用定义证明有关闭包的性质注意：传递关系的对称闭包不一定是传递的。比如：{(1,3)}关于P的闭包是否存在性？令R是A上的关系若存在，则必是唯一的。存在性：令：A×A（自反

6、、对称、传递）保证了R’存在易证：R’具有性质P闭包计算可行性尚待讨论自反闭包和对称闭包显然存在传递闭包理论上存在有限集合上的传递闭包A中只有n个不同的元素，如果在R中存在一条从a到b的长度至少为1的通路，那么存在一条长度不超过n的从a到b的通路。若xR*y,则存在某个自然数k,1kn,满足xRky.用矩阵乘法计算传递闭包nn矩阵相乘，结果中每1项，要做(2n-1次)布尔运算(积与和)，总共需要计算n2项。nn矩阵相加,要做n2次布尔运算(和)本算法共进行n-1次矩阵乘和加。总运算量(n2(2n-1)+n2)(n-1)=2n3(n-1)Warshall算法求传递闭包

7、的Warshall算法16Warshall算法的过程（续）求传递闭包的Warshall算法17求传递闭包的Warshall算法求传递闭包的Warshall算法18Warshall算法通过关系图模型更容易理解：要确定传递闭包的关系矩阵中的每一项，对应于确定关系图中任意两顶点之间是否存在路径这实际上就是把传递闭包运算通过图模型转换为找路径的运算求传递闭包的Warshall算法（续）求传递闭包的Warshall算法19aiajak中间点，在集合{a1,...,aak-1}中aiajakallinteriorvertice