《关系的性质与闭包》由会员分享，可在线阅读，更多相关《关系的性质与闭包（28页珍藏版）》请在金锄头文库上搜索。
1、关系的性质与闭包离散数学 第4讲上一讲内容的回顾l集合的笛卡尔乘积有序对-一种特殊的集合笛卡尔乘笛卡尔乘积的性质l二元关系的定l关系的运算一般集合运算与定义域或值域有关的运算逆运算复合运算(乘法)二元关系的性质与闭包l关系的几类重要性质自反对称传递l性质满足的充分必要条件l性质与运算之间的关系l闭包的定义与存在性l计算关系R的传递闭包的Warshall算法自反性l集合A上的关系R:自反：定义为：对所有的 aA, (a,a)R反自反：定义为：对所有的aA, (a,a)Rl设 A=1,2,3, RAA(1,1),(1,3),(2,2),(2,1),(3,3) 是自反的(1,2),(2,3),(3,
2、1) 是反自反的(1,2),(2,2),(2,3),(3,1) 既不是自反的，也不是 反自反的lR 是 A 上的自反关系 iff. IAR自反关系的关系图和关系矩阵abcA=a,b,c对称性l集合A上的关系R：对称的：定义为：若 (a,b)R, 则 (b,a)R反对称的：定义为：若(a,b)R 且(b,a)R ，则a=b强反对称的：定义为：若 (a,b)R 则 (b,a)R (注意：反对称和强反对称都不是对称的否定)l设 A=1,2,3, RAA(1,1),(1,2),(1,3),(2,1),(3,1),(3,3) 是对称的(1,2),(2,3),(2,2),(3,1) 是反对称的(1,2),
3、(2,3),(3,1) 既是反对称的，也是强反对称的(1,1),(2,2) 既是对称的，也是反对称的 是对称关系，也是反对称关系，也是强反对称关系！lR 是集合A上的对称关系 iff. R-1=R 对称关系的关系图和关系矩阵abcA=a,b,c传递性 l集合A上的关系R：传递的：定义为：若 (a,b)R, (b,c)R, 则 (a,c) Rl设 A=1,2,3, RAA(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3) 传递的(1,2),(2,3),(3,1) 是非传递的Both (1,3)和 均为传递关系l集合A上的关系R是传递关系 iff. RnR对所有 n
4、1成立传递关系的关系图和关系矩阵abcA=a,b,c一些常用关系的性质= RR-1, 则 R 或者 R- 1, 根据R的对称性， R-1, 或者 R, RR-1 RRR-1 设R是集合A上的对称关系, 并且RR, 则对任意 RR- 1, 有 R, 或者 R-1.l情况1: R, 则 Rl情况2: R-1, 则 R, 于是 R。根据R的对称 性： R因此, RR-1R连通关系l定义集合A上的“连通”关系R如下：对任意a,bA, a Rb 当且仅当：存在t1,t2tk A(k 是任意非负整数)，满足 R; R; R。(可以表述为：R中存在长度大于0的通路)显然：对任意a,bA, a Rb 当且仅当
5、存在某个正整数 k,使得aRkb。(这里乘幂表示的是关系的复合运算，注意： 关系复合运算满足结合律)于是：R = R1R2R3Ri = 传递闭包方法讨论：用定义 vs. 用公式R是非空集合A上 关系R的P闭包，当 且仅当： R满足性质P； RR； 对于对于A A上任意满足上任意满足 性质性质P P的的R”, R”, 若若 R R R”, R”, 则则R R RRr (R)=R R0 s (R)=R R-1 t (R)=R R R R2 2R R3 3- rs(R) = sr(R) rt(R) = tr(R) st(R) ts(R)用定义证明有关闭包的性质有限集合上的传递闭包因为 A 中只有 n
6、 个不同的元素，如果在R中存在一个序 列 , , , , , 且kn-1, 则x,y和诸 ti 中必有相同的元素。这很容易推导出：若 xRy, 则存在某个自然数 k, 1kn, 满足 xRky. 矩阵乘法与关系的复合l给有限集合A,B,C。设R1AB, R2BC, M1,M2 分别是R1,R2的关系矩阵，则M1M2(这里是矩阵乘法)是复合关系R1R2的关系矩阵。l即对任意ajA, ckC, R1R2 当且仅当 ： M1M2j,k=1M1M2j,k=1 iff. s(s1,2,|B| 且 M1j,s=M2s,k=1) iff. bsB, 满足： R1, R2 iff. R1R2 Warshall算法原理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算法过程lALGORITHM WARSHALLl1. CLOSURE MATl2. FOR k=1 THRU nl FOR i=1 THRU nl FOR j=1 THRU nl CLOSUREi,j CLOSUREi,j (CLOSUREi,kCLOSUREk,j )lEND OF ALGORITHM WARSHALL作业l140-22-2426-30
