《关系及其运算》PPT课件.ppt
关系及其运算,离散数学集合论南京大学计算机科学与技术系,回顾,集合的基本概念集合及其描述集合相等、子集关系幂集、笛卡尔乘积集合运算交并补、广义交、广义并集合恒等式集合相关命题的证明方式,提要,关系的定义关系的表示关系的运算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,矛盾。,笛卡尔乘积（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；RAB若A=B：称为“集合A上的（二元）关系”例子常用的数学关系：不大于、整除、集合包含等 网页链接、文章引用、相互认识,特殊的二元关系,集合A上的空关系:空关系即空集全域关系 EA:EA=(x,y)|x,yA 恒等关系 IA:IA=(x,x)|xA,函数是一种特殊的关系,函数 f:ABR=(x,f(x)|xA 是一个从A到B的一个关系,关系的表示,假设A=a,b,c,d,B=,/假设为有限集合集合表示:R1=(a,),(b,),(c,),(c,)0-1矩阵 有向图,二元关系和有向图,关系 RABA和B是集合有序对集合(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)Rran R=y|x(x,y)Rfld R=dom R ran RR A=(x,y)|xA xRy RRA=y|x(xA(x,y)R)=ran(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）设 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 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,关系的复合运算的性质（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=1C=M1 M2:cij=1 iff.aij=1或bij=1令rs矩阵M1=aij；st矩阵M2=bij:C=M1 M2:cij=1 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上的恒等关系,即: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)是反对称的,理解对称性,关系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是传递的 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,直接由关系复合的定义可得；归纳基于：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,43pp.41-417:14,32,34,
