关系及其运算

关系及其运算关系及其运算离散数学－集合论南京大学计算机科学与技术系回顾回顾l集合的基本概念l集合及其描述l集合相等、子集关系l幂集、笛卡尔乘积l集合运算l交并补、广义交、广义并l集合恒等式l集合相关命题的证明方式提要提要l关系的定义l关系的表示l关系的运算l0-1矩阵运算l关系的性质有序有序对（（Ordered pair））l(a, b)是集合{{a}, {a, b}}的简写l次序的体现l(x,y)=(u,v) iff x=u 且 y=v若{{x},{x,y}}={{u},{u,v}}，则{x}={u}或{x}= {u,v}, 因此x=u假设yv(1) 若x=y, 左边={{x}}, 而vx,右边{{x}}; (2) 若xy,则必有{x,y}= {u,v}, 但y既非u,又非v, 矛盾笛卡笛卡尔尔乘乘积（（Cartesian Product））l对任意集合A, B笛卡尔积 AB = {(a, b)|aA, bB}l例：{1,2,3}{a,b} = {(1, a), (3, a) , (3, a), (1, b), (2, b) , (3, b) }l若A，B是有限集合， |AB|= |A||B| 例题例题lA={1,2}, (A)×A=?l|A|=m, |B|=n, |A×B|=?（二元）关系的定义（二元）关系的定义l若A, B是集合,从A到B的一个关系是AB的一个子集.l集合, 可以是空集l集合的元素是有序对l关系意味着什么？l两类对象之间建立起来的联系！从从A到到B的二元关系的二元关系l笛卡尔乘积的子集l“从A到B的关系”R；RABl若A=B： 称为“集合A上的（二元）关系”l例子l常用的数学关系：不大于、整除、集合包含等 l网页链接、文章引用、相互认识特殊的二元关系特殊的二元关系 l集合A上的空关系: 空关系即空集l全域关系 EA: EA ={ (x, y) | x, yA }l恒等关系 IA : IA ={(x, x) | xA }函数是一种特殊的关系函数是一种特殊的关系 l函数 f : ABlR={ (x, f(x)) | xA }是一个从A到B的一个关系关系的表示关系的表示 假设A={a,b,c,d}, B={α,β,γ} // 假设为有限集合l集合表示: R1={(a, β), (b, α), (c, α),(c, γ)} 0-1矩阵 有向图abcd     adcb   AB二元关系和有向图二元关系和有向图关系 RABA和B是集合有序对集合(x,y)R若A=B, R中存在序列：(x1,x2), (x2,x3),…,(xn-1,xn)有向图 (VD , ED )顶点集 VD= AB有向边集ED从x到y有一条边图D中存在从 x1 到 xn 的长度为 n-1的通路关系的运算（关系的运算（1））l关系是集合, 所有的集合运算对关系均适用l例子:l自然数集合上: “<”  “=” 等同于 “”l自然数集合上: “”  “”等同于“=”l自然数集合上: “<”  “>”等同于关系的运算（关系的运算（2））l与定义域和值域有关的运算ldom R = {x | y (x,y)R}lran R = {y | x (x,y)R}lfld R = dom R  ran RlR A = {(x,y) | xA xRy}  RlR[A] = {y | x (xA  (x,y)R)}= ran(RA)  ranRl例：A={1,2,3,4,5}, B={1,3,5,6}, A上关系R： R={(1,2), (1,4),(2,3),(3,5),(5,2)}, 求 RB、R[B]、R(1)和R(2)关系的运算（关系的运算（3））l逆运算lR-1 = { (x, y) | (y,x)R}l注意:如果R是从A到B的关系,则R-1是从B到A的。

l(R-1)-1 = Rl例子：(R1R2)-1 = R1-1R2-1 l(x, y)  (R1R2)-1  (y, x)(R1R2) l (y, x)R1 或 (y, x)R2 l (x, y)R1-1 或 (x, y)R2-1关系的关系的运算（运算（4））l关系的复合（合成, Composition）设 R1AB, R2BC, R1与R2的复合（合成）, 记为 R2 ⃘ R1, 定义如下：R2 ⃘ R1={(a, c) AC | bB ((a, b) R1(b, c)R2) }复合关系的图示复合关系的图示l(a, c)R2 ⃘ R1 当且仅当 aA, cC, 且存在bB，使得(a, b)  R1, (b,c) R2abcR1R2关系的复合运算：举例关系的复合运算：举例l设A={a, b, c, d}, R1, R2为A上的关系，其中：R1 = { (a, a), (a, b), (b, d)}R2 = {(a, d), (b, c), (b, d), (c, b)}则：R2 ⃘ R1 = {(a, d), (a, c), (a, d)}R1 ⃘ R2 = {(c, d)}R12 = {(a, a), (a, b), (a, d)}关系的复合运算的性关系的复合运算的性质（（1））l结合律l给定R1AB, R2BC, R3CD, 则： (R3 ⃘ R2) ⃘ R1 = R3 ⃘ (R2 ⃘ R1) l证明左右两个集合相等.关系的复合运算的性关系的复合运算的性质（（2））l复合关系的逆关系l给定R1AB, R2BC, 则： (R2 ⃘ R1)-1 = R1-1 ⃘ R2-1 l同样，证明左右两个集合相等l(x, y) (R2 ⃘ R1)-1  (y, x) R2 ⃘ R1  tB ((y, t)R1  (t, x)R2) tB ((t, y) R1-1(x, t)R2-1 ) (x, y) R2-1 ⃘ R1-1 关系的复合运算的性关系的复合运算的性质（（3））l对集合并运算满足分配律l给定FAB, GBC, HBC, 则： (GH) ⃘ F = (G ⃘ F)  (H ⃘ F) l对集合交运算： (G  H) ⃘ F  (G ⃘ F)  (H ⃘ F) l注意：等号不成立。

A={a}, B={s,t}, C={b}; F={(a,s), (a,t)}, G={(s,b)}, H={(t,b)}; GH=Ø, (G ⃘ F)  (H ⃘ F)={(a,b)} 0-1 矩阵运算矩阵运算l令0-1矩阵M1=[aij],M2=[bij]:lC=M1  M2: cij=1 iff. aij=bij=1lC=M1  M2: cij=1 iff. aij=1或bij=1l令rs矩阵M1=[aij]；st矩阵M2=[bij]:lC=M1 M2: cij=1 iff. 关系运算的矩阵关系运算的矩阵法（法（1））l命题证明：关系的性质：自反性关系的性质：自反性 reflexivityl集合A上的关系 R 是:l自反的 reflexive：定义为：对所有的 aA, (a,a)Rl反自反的 irreflexive：定义为：对所有的aA, (a,a)R注意区分”非”与”反”l设 A={1,2,3}, RAAl{(1,1), (1,3), (2,2), (2,1), (3,3)} 是自反的l{(1,2), (2,3), (3,1)} 是反自反的l{(1,2), (2,2), (2,3),( 3,1)} 既不是自反的，也不是反自反的自反性与恒等关系自反性与恒等关系lR 是 A 上的自反关系  IAR, 这里IA是集合A上的恒等关系,即: IA={(a,a)| aA }直接根据定义证明：l 只需证明：对任意(a,b) ，若(a,b)IA, 则(a,b)Rl 只需证明：对任意的a, 若aA, 则(a,a)R自反关系的有向自反关系的有向图和和0-1矩矩阵abcA={a,b,c}关系的性质：对称性关系的性质：对称性 Symmetryl集合A上的关系R是: l对称的 symmetric：定义为：若 (a,b)R, 则 (b,a)Rl反对称的 anti-~：定义为：若(a,b)R 且(b,a)R ，则a=bl设 A={1,2,3}, RAAl{(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)} 是对称的l{(1,2),(2,3),(2,2),(3,1)} 是反对称的理解对称性理解对称性l关系R满足对称性：对任意(a,b)，若 (a,b)R, 则 (b,a)Rl注意：是对称关系。

l反对称并不是对称的否定: ( 令：A={1,2,3}, RAA)l{(1,1),(2,2)} 既是对称的，也是反对称的l是对称关系，也是反对称关系对称性与逆关系对称性与逆关系lR 是集合A上的对称关系  R-1=R l　证明一个集合等式　R-1=R l若(a,b)R-1, 则(b,a)R, 由R的对称性可知(a,b)R, 因此：R-1R; 同理可得：RR-1; l 只需证明：对任意的(a,b) 若(a,b)R, 则(b,a)R对称关系的对称关系的有向有向图和和0-1矩矩阵abcA={a,b,c}关系的性质：传递性关系的性质：传递性 transitivityl集合A上的关系R是l传递的 transitive: 若 (a,b)R, (b,c)R, 则 (a,c) Rl设 A={1,2,3}, RAAl{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)} 传递的l{(1,2),(2,3),(3,1)} 是非传递的l{(1,3)}? l?传递性与关系的乘幂传递性与关系的乘幂 l关系的复合(乘)运算满足结合律，可以用 Rn 表示R◦ R◦…◦ R (n是正整数) l命题：(a,b)Rn 当且仅当：存在t1,t2,…,tn-1A, 满足：(a,t1),(t1,t2),…,(tn-2,tn-1),(tn-1,b)R。

l对n>=1用数学归纳法：n=1, trivial. 奠基n=2,直接由关系复合的定义可得；归纳基于：Rn=Rn-1 ◦Rl集合A上的关系R是传递关系  R2Rl必要性：任取(a,b) R2 ,根据上述命题以及R的传递性可得(a,b)Rl充分性： 若(a,b)R, (b,c)R, 则(a,c)R2, 由R2R可得： (a,c)R，则 R是传递关系传递关系的有向图和传递关系的有向图和0-1矩阵矩阵abcA={a,b,c}一些常用关系的性质一些常用关系的性质= <| 3E自反自反  反自反反自反 对称对称反对称反对称    传递传递      关系运算与性质的保持关系运算与性质的保持自反自反反自反反自反对称对称反对称反对称传递传递R1-1R1R2 R1R2 R1R2 下列关系是否自反的、对称的、反对称的或可传下列关系是否自反的、对称的、反对称的或可传递的？关系递的？关系S S为：为：r r1 1≤ | r≤ | r2 2| (r| (r1 1,r,r2 2∈R)∈R)时时解：解：s s是自反的，因为对任意的是自反的，因为对任意的r∈Rr∈R，有，有r r ≤≤|r||r|。

s s不是对称的，如不是对称的，如-1-1≤≤|3||3|，但，但3>|-1|3>|-1|s s不是反对称的，如不是反对称的，如-3≤|2|-3≤|2|，，2≤|-3|2≤|-3|，但，但-3≠2-3≠2s s不是可传递的，不是可传递的，100100≤≤|-101||-101|，， -101-101≤≤|2||2|，但，但100>|2|100>|2|习题举例一习题举例一小结小结l关系：笛卡尔积的子集l关系的运算l集合运算；复合运算；逆l0-1矩阵运算l关系的性质lreflexivity, ir-~; symmetry, anti-~; transitivity l图特征；矩阵特征作业作业l教材内容：[Rosen] 2.1.3、8.1 节 8.3节l课后习题：lp. 88（英文教材 p. 120）: 30 lpp. 404-405（英文教材 pp. 528-529 ）: 25, 30, 37, 39, 43lpp. 41-417 : 14, 32, 34。