第7讲关系幂运算与关系闭包 内容提要 秦关系幂(oWer)运算 关系闭包 closure) 《集合论与图论》第7讲
《集合论与图论》第7讲 1 第7讲 关系幂运算与关系闭包 内容提要 关系幂(power)运算 关系闭包(closure)
关系的幂运算 n次幂的定义 指数律 癱幂指数的化简 《集合论与图论》第7讲
《集合论与图论》第7讲 2 关系的幂运算 n次幂的定义 指数律 幂指数的化简
关系的n次幂 关系的n次幂( nth power):设 RCAXA, n∈N,则 (1)R0=I (2)R+=R"oR,(n≥1) R=RR6邛 n个R 秦R表示的关系,是R的关系图中长度为n 的有向路径的起点与终点的关系 ●0 →0 《集合论与图论》第7讲
《集合论与图论》第7讲 3 关系的n次幂 关系的n次幂(nth power): 设R⊆A×A, n∈N, 则 (1) R0 = IA; (2) Rn+1 = Rn○R, (n≥1). Rn表示的关系, 是R的关系图中长度为n 的有向路径的起点与终点的关系. 1 o4 2oL4 3o n R n R R R R 个 = 12 n n-1
关系幂运算(举例 例:设A={a,bc,RAxA, R={ab>,<ba>,<a,c>}求R的各次幂 解 a C a G(R) G(RO) 《集合论与图论》第7讲
《集合论与图论》第7讲 4 关系幂运算(举例) 例: 设A={a,b,c}, R⊆A×A, R={<a,b>,<b,a>,<a,c>}, 求R的各次幂. 解: b a c b a c G( R ) G( R0 )
关系幂运算(举例续) 解(续):R0=IA, R=ROR=R=<a, b>, <b, a>, a,c>), R2=RoR=<<a, a>, <b, b><b, c>1, a HC G(R) G(R2) 《集合论与图论》第7讲
《集合论与图论》第7讲 5 关系幂运算(举例,续) 解(续): R0 = IA, R1 = R0○R = R = {<a,b>,<b,a>,<a,c>}, R2 = R1○R = {<a,a>,<b,b>,<b,c>}, b a c b a c G( R ) G( R2 )