《关系的性质与闭包》PPT课件.ppt

关系的性质与闭包,离散数学 第4讲,上一讲内容的回顾,集合的笛卡尔乘积 有序对-一种特殊的集合 笛卡尔乘 笛卡尔乘积的性质 二元关系的定 关系的运算 一般集合运算 与定义域或值域有关的运算 逆运算 复合运算(乘法),二元关系的性质与闭包,关系的几类重要性质 自反 对称 传递 性质满足的充分必要条件 性质与运算之间的关系 闭包的定义与存在性 计算关系R的传递闭包的Warshall算法,自反性,集合A上的关系R: 自反：定义为：对所有的 aA, (a,a)R 反自反：定义为：对所有的aA, (a,a)R 设 A=1,2,3, RAA (1,1),(1,3),(2,2),(2,1),(3,3) 是自反的 (1,2),(2,3),(3,1) 是反自反的 (1,2),(2,2),(2,3),(3,1) 既不是自反的，也不是反自反的 R 是 A 上的自反关系 iff. IAR,自反关系的关系图和关系矩阵,对称性,集合A上的关系R： 对称的：定义为：若 (a,b)R, 则 (b,a)R 反对称的：定义为：若(a,b)R 且(b,a)R ，则a=b 强反对称的：定义为：若 (a,b)R 则 (b,a)R (注意：反对称和强反对称都不是对称的否定) 设 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),(2,3),(3,1) 既是反对称的，也是强反对称的 (1,1),(2,2) 既是对称的，也是反对称的 是对称关系，也是反对称关系，也是强反对称关系！ R 是集合A上的对称关系 iff. R-1=R,对称关系的关系图和关系矩阵,传递性,集合A上的关系R： 传递的：定义为：若 (a,b)R, (b,c)R, 则 (a,c) R 设 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)和 均为传递关系 集合A上的关系R是传递关系 iff. RnR对所有n1成立,传递关系的关系图和关系矩阵,一些常用关系的性质,正确理解自反关系,一个错误的命题及其“证明”: 如果R是集合A上的对称，传递关系，则R 是A上的自反关系 证明: 对任意的 a,bA, 若 (a,b)R, 根据R 的对称性 (b,a)R; 又根据R的传递性, (a,a)R. 所以：R 是自反关系,逆关系运算对关系性质的保持,自反性: x, (x,x)R1 (x,x) R1-1 反自反性: x, (x,x) R1 (x,x) R1-1 对称性: x,y, if (x,y) R1-1, then (y,x) R1, since R1 is symmetric，(x,y) R1, (y,x) R1-1 强反对称性: x,y, if (x,y)R1-1, (y,x)R1-1, then (y,x)R1, (x,y)R1, since R1 is antisymmetric，x=y. 传递性: x,y,z, if (x,y)R1-1, (y,z)R1-1, then (y,x)R1, (z,y)R1, since R1 is transitive，(z,x) R1, (x,z)R1-1,关系的交运算对运算性质的保持,自反: x, (x,x) R1, (x,x)R2, (x,x)R1R2 反自反: supposing x, (x,x)R1R2, then (x,x)R1, (x,x)R2, contradiction. 对称: x,y, (x,y)R1R2 (x,y)R1, (x,y)R2，since R1 and R2 are symmetric，(y,x)R1, (y,x)R2, (y,x)R1R2. 反对称: x,y, supposing (x,y)R1R2, (y,x)R1R2, then (x,y), (y,x)R1, and (x,y), (y,x)R2, since R1 and R2 are both asymmetric，x=y 传递:x,y,z, if (x,y)R1R2, (y,z)R1R2, then (x,y), (y,z)R1,and (x,y),(y,z)R2, since R1and R2 are both transitive, (x,z)R1, and (x,z)R2, (x,z)R1R2,关系的并运算对关系性质的保持,自反: x, (x,x)R1, (x,x)R2, (x,x)R1R2 反自反: supposing that x, (x,x)R1R2, then (x,x) R1 or (x,x)R2, but R1and R2 are irreflexive 对称: x,y, if (x,y)R1R2, then (x,y)R1 or (x,y)R2, without losing generality, let (x,y)R1，since R1 is symmetric, so, (y,x)R1R2 反对称: 反例: R1=(a,b), R2=(b,a) 传递: 反例: R1=(a,b), R2=(b,a),复合运算对关系性质的保持,自反: x, (x,x)R1 and (x,x)R2, (x,x) R2R1 反自反: 反例: R1=(a,b), R2=(b,a), then R2R1=(a,a) 对称: 反例: R1=(c,b),(b,c), R2=(c,d), (d,c), then R2R1=(d,b) 反对称: 反例: R1=(a,b), R2,=(b,a), then R2R1=(a,a) 传递: 反例: R1=(x,t),(y,s), R2=(t,y), (s,z), then R2R1=(x,y),(y,z),关系性质保持的总结,关系的闭包：概念,设R是集合A上的关系，P是给定的某种性质，满足下列所有条件的关系R1称为关系R的P闭包: R1 满足性质P RR1 如果存在集合A上的关系R，R 满足性质P 并包含R，则R1R ,自反闭包,关系 R的自反闭包是 RIA 对任意 xA, (x,x)IA, 因此, (x,x)RIA RRIA 设 R 集合A 上的自反关系，且RR, 则对任意 (x,y)RIA, 有(x,y)R, 或者 (x,y)IA。 对两种情况，均有 (x,y)R, 因此, RIAR,对称闭包,关系 R的对称闭包是RR-1 对任意 x,yA, 如果 RR-1, 则 R 或者 R-1, 根据R的对称性， R-1, 或者 R, RR-1 RRR-1 设R是集合A上的对称关系, 并且RR, 则对任意 RR-1, 有 R, 或者 R-1. 情况1: R, 则 R 情况2: R-1, 则 R, 于是 R。根据R的对称性： R 因此, RR-1R,连通关系,定义集合A上的“连通”关系R如下： 对任意a,bA, a Rb 当且仅当：存在t1,t2tk A(k是任意非负整数)，满足 R; R; R。(可以表述为：R中存在长度大于0的通路) 显然：对任意a,bA, a Rb 当且仅当存在某个正整数k,使得aRkb。(这里乘幂表示的是关系的复合运算，注意：关系复合运算满足结合律) 于是：R = R1R2R3Ri =,传递闭包,方法讨论：用定义 vs. 用公式,R是非空集合A上关系R的P闭包，当且仅当： R满足性质P； RR； 对于A上任意满足性质P的R”, 若RR”, 则RR,r (R)=R R0 s (R)=R R-1 t (R)=R R2R3. - rs(R) = sr(R) rt(R) = tr(R) st(R) ts(R),用定义证明有关闭包的性质,有限集合上的传递闭包,因为 A 中只有 n 个不同的元素，如果在R中存在一个序列 , , , , , 且kn-1, 则x,y和诸ti 中必有相同的元素。这很容易推导出： 若 xRy, 则存在某个自然数 k, 1kn, 满足 xRky.,矩阵乘法与关系的复合,给有限集合A,B,C。设R1AB, R2BC, M1,M2分别是R1,R2的关系矩阵，则M1M2(这里是矩阵乘法)是复合关系R1R2的关系矩阵。 即对任意ajA, ckC, R1R2 当且仅当： M1M2j,k=1 M1M2j,k=1 iff. s(s1,2,|B| 且 M1j,s=M2s,k=1) iff. bsB, 满足： R1, R2 iff. R1R2,Warshall算法原理,ai,aj,ak,all interior vertices in a1,.,a ak-1,Wki,j=1 if and only if: Wk-1i,j=1, or Wk-1i,k=1 and Wk-1