对称、传递的闭包.pptVIP

定理10 (2)的证明 ③设R″是包含R的对称关系， 任取x,y，有 x,y∈R∪R-1 ? x,y∈R∨x,y∈R-1 ? x,y∈R∨y,x∈R ?x,y∈R″∨y,x∈R″ ?x,y∈R″∨x,y∈R″ ? x,y∈R″ 所以 R∪R-1 ?R″. 综上所述，s(R)＝R∪R-1. 证明：(1)任取x,y，有 x,y∈r(R1) ? x,y∈R1∪IA ? x,y∈R1 ∨ x,y∈IA ? x,y∈R2 ∨ x,y∈IA ? x,y∈R2∪IA ? x,y∈r(R2) * 一个计算机网络在波士顿、芝加哥、丹佛、底特律、纽约和圣地亚哥设有数据中心。从波士顿到芝加哥、波士顿到底特律、芝加哥到底特律、底特律到丹佛和纽约到圣地亚哥，都有单向的电话线。如果存在一条从数据中心a到b的电话线，a,b就属于关系R。我们如何确定从一个中心是否有一条电话线(可能不直接)链接到另一个中心？由于所有的链接不一定是直接的，例如从波士顿可通过底特律到丹佛，因此不能直接使用R来回答这个问题。用关系的语言说，R是不传递的，因而它不包含可能链接的所有的对。正如我们将要讲述的，可以通过构造包含R的最小的传递关系来找出每一对有着联系的数据中心，这个关系叫做R的传递闭包。 理学院 季丹丹 牡丹江师范学院本科生课程 1.4 关系的闭包运算 问 题 如果存在一条从数据中心a到b的电话线，a,b就属于关系R. 如何确定从一个中心是否有一条电话线(可能不直接)链接到另一个中心？ 通过构造包含R的最小的传递关系来找出每一对有着联系的数据中心，这个关系叫做R的传递闭包。 波士顿 芝加哥 丹佛 底特律 圣地亚哥 纽约 §1.4 关系的闭包运算 闭包（closure）的定义 闭包的构造方法 闭包的性质 闭包的相互关系 闭包的定义 定义14 R是非空集合A上的关系,R的自反（对称或传递）闭包是A上的关系R′，使得 R′满足以下条件： （1）R′是自反的（对称的或传递的） （2）R?R′ （3）对A上任何包含R的自反（对称或传递）关系R″有 R′? R″. 一般将R的自反闭包记作r(R)，对称闭包记作s(R)，传递闭包记作t(R). 闭包的构造方法 定理10 设R为A上的关系，则有 （1）r(R)＝R∪R0 （2）s(R)＝R∪R-1 （3）t(R)＝R∪R2∪R3∪… 证明思路 (1)和(2)：证明右边的集合满足闭包定义的三个条件。 (3)采用集合相等的证明方法。 证明左边包含右边，即t(R)包含每个Rn . 证明右边包含左边，即R∪R2∪…具有传递的性质。 定理10 (1)的证明 （1）r(R)＝R∪R0 . 证明 ①由IA＝R0 ? R∪R0，可知R∪R0是自反的， ②R ? R∪R0 . ③设R″是A上包含R的自反关系，则有R?R″和IA?R″. 任取x,y，必有 x,y∈R∪R0 ? x,y∈R∪IA ? x,y∈R″∪R″＝R″ 所以 R∪R0 ? R″. 综上所述，r(R)＝R∪R0. 定理10 (2)的证明 （2）s(R)＝R∪R-1 . 证明 ① R?R∪R-1. ②证明R∪R-1是对称的， 任取x,y，有 x,y∈R∪R-1 ? x,y∈R∨x,y∈R-1 ? y,x∈R-1∨y,x∈R ? y,x∈R∪R-1 所以 R∪R-1 是对称的。 定理10 (3)的证明 （3）t(R)＝R∪R2∪R3∪… 证明 先证R∪R2∪… ? t(R)成立，为此只需证对任意的正整数n有 Rn ? t(R).用归纳法。 n＝1时，有 R1＝R ? t(R). 假设Rn?t(R)成立，那么对任意的x,y有 x,y∈Rn+1＝Rn ?R ? ?t(x,t∈Rn∧t,y∈R) ? ?t(x,t∈t(R)∧t,y∈t(R)) ? x,y∈t(R) （因为t(R)是传递的） 这就证明了Rn+1 ? t(R). 由归纳法命题得证。 定理10 (3)的证明 （3）t(R)＝R∪R2∪R3∪… 证明 要证t(R)?R∪R2∪…成立,只须证明R∪R2∪…是传递的。 任取x,y,y,z，则 x,y∈R∪R2∪… ∧ y,z∈R∪R2∪… ? ?t(x,y∈Rt) ∧ ?s(y,z∈Rs) ? ?t?s(x,y∈Rt ∧ y,z∈Rs) ? ?t?s(x,z∈Rt ? Rs) ? ?t?s(x,z∈Rt+s) ? x,z∈R∪R2∪… 从而证明了R∪R2∪…是传递的。 推 论 推论 设R为有穷集A上的关系，则存在正整数r使得 t(R)=R∪R2∪…∪Rr . 证明 由定理7.6和7.10(