《关系及其运算.ppt》由会员分享,可在线阅读,更多相关《关系及其运算.ppt(43页珍藏版)》请在三一文库上搜索。
1、关系及其运算,离散数学集合论 南京大学计算机科学与技术系,回顾,集合的基本概念 集合及其描述 集合相等、子集关系 幂集、笛卡尔乘积 集合运算 交并补、广义交、广义并 集合恒等式 集合相关命题的证明方式,提要,关系的定义 关系的表示 关系的运算 0-1矩阵运算 关系的性质,有序对(Ordered pair),(a, b)是集合a, a, b的简写 次序的体现 (x,y)=(u,v) iff x=u 且 y=v 若x,x,y=u,u,v,则x=u或x= u,v, 因此x=u。 假设yv (1) 若x=y, 左边=x, 而vx,右边x; (2) 若xy,则必有x,y= u,v, 但y既非u,又非v,
2、 矛盾。,笛卡尔乘积(Cartesian Product),对任意集合A, B 笛卡尔积 AB = (a, b)|aA, bB 例:1,2,3a,b = (1, a), (3, a) , (3, a), (1, b), (2, b) , (3, b) 若A,B是有限集合, |AB|= |A|B|,例题,A=1,2, (A)A=? |A|=m, |B|=n, |AB|=?,(二元)关系的定义,若A, B是集合,从A到B的一个关系是AB的一个子集. 集合, 可以是空集 集合的元素是有序对 关系意味着什么? 两类对象之间建立起来的联系!,从A到B的二元关系,笛卡尔乘积的子集 “从A到B的关系”R;R
3、AB 若A=B: 称为“集合A上的(二元)关系” 例子 常用的数学关系:不大于、整除、集合包含等 网页链接、文章引用、相互认识,特殊的二元关系,集合A上的空关系: 空关系即空集 全域关系 EA: EA = (x, y) | x, yA 恒等关系 IA : IA =(x, x) | xA ,函数是一种特殊的关系,函数 f : AB R= (x, f(x) | xA 是一个从A到B的一个关系,关系的表示,假设A=a,b,c,d, B=, / 假设为有限集合 集合表示: R1=(a, ), (b, ), (c, ),(c, ) 0-1矩阵 有向图,二元关系和有向图,关系 RAB A和B是集合 有序对
4、集合 (x,y)R 若A=B, R中存在序列:(x1,x2), (x2,x3),(xn-1,xn),有向图 (VD , ED ) 顶点集 VD= AB 有向边集ED 从x到y有一条边 图D中存在从 x1 到 xn 的长度为 n-1的通路,关系的运算(1),关系是集合, 所有的集合运算对关系均适用 例子: 自然数集合上: “”等同于,关系的运算(2),与定义域和值域有关的运算 dom R = x | y (x,y)R ran R = y | x (x,y)R fld R = dom R ran R R A = (x,y) | xA xRy R RA = y | x (xA (x,y)R)= ra
5、n(RA) ranR 例:A=1,2,3,4,5, B=1,3,5,6, A上关系R: R=(1,2), (1,4),(2,3),(3,5),(5,2), 求 RB、RB、R(1)和R(2),关系的运算(3),逆运算 R-1 = (x, y) | (y,x)R 注意:如果R是从A到B的关系,则R-1是从B到A的。 (R-1)-1 = R 例子:(R1R2)-1 = R1-1R2-1 (x, y) (R1R2)-1 (y, x)(R1R2) (y, x)R1 或 (y, x)R2 (x, y)R1-1 或 (x, y)R2-1,关系的运算(4),关系的复合(合成, Composition) 设
6、R1AB, R2BC, R1与R2的复合(合成), 记为 R2 R1, 定义如下: R2 R1=(a, c) AC | bB (a, b) R1(b, c)R2) ,复合关系的图示,(a, c)R2 R1 当且仅当 aA, cC, 且存在bB,使得(a, b) R1, (b,c) R2,a,b,c,R1,R2,关系的复合运算:举例,设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
7、R2 = (c, d) R12 = (a, a), (a, b), (a, d),关系的复合运算的性质(1),结合律 给定R1AB, R2BC, R3CD, 则: (R3 R2) R1 = R3 (R2 R1) 证明左右两个集合相等.,关系的复合运算的性质(2),复合关系的逆关系 给定R1AB, R2BC, 则: (R2 R1)-1 = R1-1 R2-1 同样,证明左右两个集合相等 (x, y) (R2 R1)-1 (y, x) R2 R1 tB (y, t)R1 (t, x)R2) tB (t, y) R1-1(x, t)R2-1 ) (x, y) R2-1 R1-1,关系的复合运算的性质
8、(3),对集合并运算满足分配律 给定FAB, GBC, HBC, 则: (GH) F = (G F) (H F) 对集合交运算: (G H) F (G F) (H F) 注意:等号不成立。 A=a, B=s,t, C=b; F=(a,s), (a,t), G=(s,b), H=(t,b); GH=, (G F) (H F)=(a,b),0-1 矩阵运算,令0-1矩阵M1=aij,M2=bij: C=M1 M2: cij=1 iff. aij=bij=1 C=M1 M2: cij=1 iff. aij=1或bij=1 令rs矩阵M1=aij;st矩阵M2=bij: C=M1 M2: cij=1
9、iff.,关系运算的矩阵法(1),命题,证明:,关系的性质:自反性 reflexivity,集合A上的关系 R 是: 自反的 reflexive:定义为:对所有的 aA, (a,a)R 反自反的 irreflexive:定义为:对所有的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 上的自反关系 IAR, 这里IA是集合A上的
10、恒等关系,即: IA=(a,a)| aA 直接根据定义证明: 只需证明:对任意(a,b) ,若(a,b)IA, 则(a,b)R 只需证明:对任意的a, 若aA, 则(a,a)R,自反关系的有向图和0-1矩阵,关系的性质:对称性 Symmetry,集合A上的关系R是: 对称的 symmetric:定义为:若 (a,b)R, 则 (b,a)R 反对称的 anti-:定义为:若(a,b)R 且(b,a)R ,则a=b 设 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) 是反对称的,理解对称性,
11、关系R满足对称性:对任意(a,b),若 (a,b)R, 则 (b,a)R 注意:是对称关系。 反对称并不是对称的否定: ( 令:A=1,2,3, RAA) (1,1),(2,2) 既是对称的,也是反对称的 是对称关系,也是反对称关系。,对称性与逆关系,R 是集合A上的对称关系 R-1=R 证明一个集合等式 R-1=R 若(a,b)R-1, 则(b,a)R, 由R的对称性可知(a,b)R, 因此:R-1R; 同理可得:RR-1; 只需证明:对任意的(a,b) 若(a,b)R, 则(b,a)R,对称关系的有向图和0-1矩阵,关系的性质:传递性 transitivity,集合A上的关系R是 传递的
12、transitive: 若 (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) 是非传递的 (1,3)? ?,传递性与关系的乘幂,关系的复合(乘)运算满足结合律,可以用 Rn 表示 R R R (n是正整数) 命题:(a,b)Rn 当且仅当:存在t1,t2,tn-1A, 满足:(a,t1),(t1,t2),(tn-2,tn-1),(tn-1,b)R。 对n=1用数学归纳法:n=1, trivial. 奠基n=2,直接由关系复合的定义可得;
13、归纳基于:Rn=Rn-1 R 集合A上的关系R是传递关系 R2R 必要性:任取(a,b) R2 ,根据上述命题以及R的传递性可得(a,b)R 充分性: 若(a,b)R, (b,c)R, 则(a,c)R2, 由R2R可得: (a,c)R,则 R是传递关系,传递关系的有向图和0-1矩阵,一些常用关系的性质,关系运算与性质的保持,下列关系是否自反的、对称的、反对称的或可传递的?关系S为:r1 | r2| (r1,r2R)时,解:s是自反的,因为对任意的rR,有r |r|。 s不是对称的,如-1|3|,但3|-1|。 s不是反对称的,如-3|2|,2|-3|,但-32。 s不是可传递的,100|-101|, -101|2|,但100|2|,习题举例一,小结,关系:笛卡尔积的子集 关系的运算 集合运算;复合运算;逆 0-1矩阵运算 关系的性质 reflexivity, ir-; symmetry, anti-; transitivity 图特征;矩阵特征,作业,教材内容:Rosen 2.1.3、8.1 节 8.3节 课后习题: p. 88(英文教材 p. 120): 30 pp. 404-405(英文教材 pp. 528-529 ): 25, 30, 37, 39, 43 pp. 41-417 : 14, 32, 34,
链接地址:https://www.31doc.com/p-2440869.html