售嘉 自反闭包的定义 ●设R的是集合A上的关系，其自反闭包r(R)也是A 上的关系，且满足： 。(R)满足自反性； OR三r(R); ●对A上的任意关系R',若R也满足自反性，且也包含R,则 rR)CR ·例子 令A={1,2,3},R={1,1),(1,3),(2,3),(3,2)}。则(R)={(1,1), (1,3),(2,3)2(3,2),(2,2),(3,3)}
自反闭包的定义 设 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,2), (2,2), (3,3)}
急雪扇 自反闭包的计算公式 ●(R)=ROIA IA是集合A上的恒等关系 (证明所给表达式满足自反闭包定义中的三条性质) 1.对任意x∈A,(x,x)EI4,因此，(x,x)∈RUI4 2.RCROI 3.设R集合A上的自反关系，且RcR',则对 任意(x,y)∈RUI4有(xy)∈R,或者(x,y)∈IA 对两种情况，均有(x,y)∈R',因此，RUI4R
自反闭包的计算公式 r(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’
对称闭包的计算公式 ·s(R)=RURl,这里RI是R的逆关系 ·s(R)是对称的。对任意xyEA,如果(x,y)Es(R),则(x,y)ER或 者(x,y)∈R-l,即y,x)∈R1,或者Oy,x)∈R,y,x)Es(R) ●RCS(R) ●设R是集合A上的对称关系，并且RcR',则对任意(x,y)∈s(R), 有(x,y)∈R,或者(x,y)∈R1 ●情况1：(x,y)∈R,则(x,y)∈R ·情况2：(x,y)∈R1,则Oy,x)∈R,于是y,x)∈R’。根据R的对称 性：(xy)∈R 因此，s(R)二R
对称闭包的计算公式 s(R) = RR-1 , 这里R-1是R的逆关系 s(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) R s(R) 设R’是集合A上的对称关系, 并且RR’, 则对任意(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,aRb当且仅当：存在t1,2.(∈A(k是正整 数)，满足(a,)∈R,(t1,)eR,;(4,b)eR。(可以表述为： 从a到b之间存在长度至少为1的通路) ●显然：对任意a,b∈A,aR*b当且仅当存在某个正整数k, 使得aRb。 。于是：R*=RUR2UR3U.RU..= R
连通关系 R是集合A上的关系 定义集合A上的“R连通”关系R*如下： 对任意a,bA, a R*b 当且仅当：存在t1 ,t2…tk A(k是正整 数)，满足(a,t1 ) R; (t1 ,t2 )R;…; (tk ,b)R。(可以表述为： 从a到b之间存在长度至少为1的通路) 显然：对任意a,bA, a R*b 当且仅当存在某个正整数k, 使得aRkb。 于是：R* = R1R2R3…Ri… = k k R 1
传递闭包 190 1(R)=R* 1.若(xy)∈R*,(y,2)∈R*,则有S1,S2,,S,以及t,t2,,4, 满足：(x,S),…,(s,y),(y,t)2…,(,2)∈R, 因此，（x,z)∈R*. 2.RCR 3.设R是集合A上的传递关系，且包含R。若(x,y)∈R, 则有t,t2,,t,满足：(x,t)2…,(t,y)∈R, 于是(x,t),(t,2),…,(t,y)∈R 根据R的传递性，(x,y)∈R
传递闭包 t(R) R* ,( , ) *. ( , ), ,( , ),( , ), ,( , ) , 1. ( , ) *,( , ) *, , ,..., , ,..., , 1 1 1 2 1 2 x z R x s s y y t t z R x y R y z R s s s t t t j k j k 因此 满足： 若 则有 以及 ' ( , ) '. ( , ),( , ), ,( , ) ' , ,..., , ( , ), ,( , ) , 3. ' , ( , ) , 2. 1 1 2 1 2 1 * * R x y R x t t t t y R t t t x t t y R R A R x y R R R k k k 根据 的传递性， 于是 则有 满足： 设 是集合 上的传递关系 且包含 。若