理学第二章关系

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,2.1,关系的基本概念,定义,2.1,从集合,A,到集合,B,的一个,关系,R,是,A,与,B,的笛卡尔积,AB,的一个子集,关系,R,中有序偶第一个客体所允许选取对象的集合称为关系,R,的,定义域,，记以,D(R),，第二个客体所允许选取对象集合称为关系,R,的,值域,，记以,C(R),在特殊情况下，当,D(R)=C(R)=M,时，,M,为一集合，此时称为关系为,M,上的关系,例：实数集,R,上的“,”,关系可以定义为：,=(x,y),|,x,R,y,R,且,xy,2.1,关系的基本概念,如果从,X,到,Y,不存在某种关系,R,，则称这种关系为,空关系,，如果从,X,的每个元素到,Y,的每个元素之间均具有某种关系，则称此关系为,全关系,.,从,X,到,Y,的全关系即,XY.,定义,2.2,由集合,X,1,、,X,2,、,、,X,n,所确定的的,n,元关系,是,X,1,X,2,X,n,的一个子集,2.1,关系的基本概念,大型的计算机结构中或一个大型软件结构中所谓的内部逻辑关系复杂，所指的“逻辑关系”就是这里的“关系”，只要把这些结构内的关系搞清，则任何结构的“正确性”“可靠性”就迎刃而解了,.,2.1,关系的基本概念,关系的图,的表示法,一个集合,X=x,1,x,2,x,n,上的关系可用一关系图表示之,.,集合,X,中元素可用图中结点表示；关系,R,的有序偶,(x,i,x,j,),可用图中从结点,x,i,到,x,j,的有向边表示。,例：,2.2,关系的运算,关系的,交、并、补、差,关系是特殊的集合,有关集合的交、并、补、差在关系中也适用，有关集合运算的一些公式在关系中也适用,2.2,关系的运算,复合运算,定义,2.3,设,R,是一个从,X,到,Y,的关系，,S,是一个从,Y,到,Z,的关系，则,R,与,S,的复合关系：,RoS=(x,z),|,x,X,z,Z,至少存在一个,y,Y,有,(x,y),R,且,(y,z),S,计算方法,：,1,）从定义入手,2,）有向图法,3,）布尔矩阵,2.2,关系的运算,定理（复合运算满足结合律）：,设,R,、,S,、,T,分别表示从,X,到,Y,、,Y,到,Z,、,Z,到,U,的关系，则有,(RoS)oT=Ro(SoT)=RoSoT,定义,2.4,设有一个集合,X,上的关系,R,，则,R,n,可定义如下：,1,）,R,1,=R,2,）,R,n+1,=R,n,oR,故，,R,m,oR,n,=R,m+n,(R,m,),n,=R,mn,2.2,关系的运算,例：,设,R,和,S,是集合,X=0,1,2,3,上的关系，有,R=(x,y),|,j=i+1,或,j=i/2,S=(x,y),|,i=j+2,求,RoS,，,SoR,解：,R=(0,1),(1,2),(2,3),(0,0),(2,1),S=(2,0),(3,1),RoS=(1,0),(2,1),SoR=(2,1),(2,0),(3,2),2.2,关系的运算,例：,设有,X,上的关系,R,1,R,2,R,3,，试证：,如,R,1,R,2,，则,R,1,oR,3,R,2,oR,3,证明：,对任意,(a,c)R,1,oR,3,，存在,bX,，使得,(a,b)R,1,且,(b,c)R,3,由于,R,1,R,2,，所以存在,bX,，使得,(a,b)R,2,且,(b,c)R,3,，于是,(a,c)R,2,oR,3,因而,R,1,oR,3,R,2,oR,3,2.2,关系的运算,逆运算,是一种一元运算，其结果组成的关系，称关系的逆关系,.,定义,2.5,设,R,是一个从,X,到,Y,的关系，即,R=(x,y),|,x,X,y,Y,，则从,Y,到,X,的关系,称为,R,的逆关系,.,例：,R=(1,a),(2,b),(3,c),2.2,关系的运算,定理,设,R,，,S,分别是从,X,到,Y,及,Y,到,Z,的关系，则有,1),2),3),4),5),2.3,关系的重要性质,自反性,反自反性,对称性,反对称性,传递性,2.3,关系的重要性质,定义,2.6,在集合,X,上的关系,R,，如对任意,x,X,，有,(x,x),R,则,R,是,自反,的,定义,2.7,在集合,X,上的关系,R,，如对任意,x,X,，有,(x,x)R,则,R,是,反自反,的,例：,在整数集,Z,上的关系，“”是自反的，不是反自反的；“,”,是反自反的，不是自反的。,在集合,X=1,2,3,4,上的关系,R,：,R=(1,1),(2,1),(3,4),(4,2),既不是自反的也不是反自反的,2.3,关系的重要性质,一个关系的自反性在图形表示法中相当于一个关系图中的每个结点均,有环出现,而一个关系的反自反性相当于一个关系图中的每个结点均,无环出现,2.3,关系的重要性质,定义,2.8,在集合,X,上的关系,R,，如果有,(x,y),R,必有,(y,x),R,，则称,R,是,对称,的,定义,2.9,在集合,X,上的关系,R,，如果有,(x,y),R,且,xy,必有,(y,x),R,，则称,R,是,反对称,的,例,：有一些人的集合中“同事”关系是对称的，“父子”关系则是反对称的。,在集合,X=1,2,3,4,上的关系,R,：,R=(1,2),(2,1),(3,4),(4,2),既不是对称的也不是反对称的,2.3,关系的重要性质,关系的对称性在图形表示中相当于关系图中两个结点间如有有向边相连，则一定有方向相反的,两条有向边连接,一个关系的反对称性相当于关系图中两个结点间如有有向边相连则一定,只有一条边,2.3,关系的重要性质,定义,2.10,在集合,X,上的关系,R,，如果有,(x,y),R,且,(y,z),R,，则必有,(x,z),R,则称,R,是,传递,的,例：,在一些人的集合上，“同事”关系是传递的，但“父子”关系不是传递的,整数集,Z,上的“”、“,”都是传递的,一些城市所组成的集合上，“线路的连通”关系是传递的,2.3,关系的重要性质,注意：,一个关系可以,既不是自反的，又不是反自反的；,即是对称的，又是反对称的；,根据定义，一个有序偶的第一元素和第二元素如果可以交换且存在反对称关系的话，则第一和第二元素应该相同,但是传递与非传递不能同时存在,传递意为如果有,(a,b),(b,c),就应该有,(a,c),如果没有,(a,c),就是非传递，一个关系要么是传递的要么是非传递的，两者只能居其一，而如果没有,(a,b)(b,c),出现的情况也归为满足传递性。,2.3,关系的重要性质,一个集合,X,上的关系可能具有上述,5,个性质中的若干性质,.,全关系是自反的、对称的，传递的,空关系是反自反的、对称的、反对称的，传递的,例：,设集合,A=a,b,c,d,，判定下列关系具有什么性质,1,）,R1=(a,a),(b,a),2,）,R2=(c,d),3,）,R3=(a,a),(b,b),(c,c),例：,集合,A=1,2,10,的关系,R=(x,y),x+y=10,且,x,y,A,，则,R,具有什么性质？,解：,R=(1,9),(2,8),(3,7),(4,6),(5,5),(6,4),(7,3),(8,2),(9,1),R,是对称的,反对称的，传递的,反自反的，反对称的，传递的,自反的，对称的，反对称的，传递的,2.3,关系的重要性质,例：试判断图中关系的性质,(a)(b)(c),解,:,a)R,是对称的，非传递的,b)R,是反自反的，对称的，非传递的,c)R,是自反的，反对称的，非传递的,a,b,c,a,b,c,a,b,c,2.3,关系的重要性质,定义,集合,关系图,关系矩阵,自反的,任取,aA,有,(a,a)R,I,A,R,图中每个结点都有自回路,主对角线上全为,1,反自反的,任取,aA,有,(a,a),R,R,I,A,=,图中每个结点都无自回路,主对角线上全为,0,对称的,若,(a,b)R,则,(a,b)R,R=R,-1,任意两个不同的结点要么没有弧，要么有方向相反的一对弧,对称阵,反对称的,若,(a,b)R,(a,b)R,则,a=b,R,R,-1,I,A,任意两结点间至多有一条弧,反对称阵,传递的,若,(a,b)R,(b,c)R,则,(a,c)R,RoRR,若,a,到,b,有弧,b,到,c,有弧,则,a,到,c,有弧,-,2.4,关系上的闭包运算,定义,2.11,设,R,是集合,X,上的一个关系，则,R,的自反,(,对称、传递,),闭包,是一个满足下列条件的关系,R,：,1,）,R,是自反的,(,对称的、传递的,),；,2,）,RR,；,3,）设,R,是自反的,(,对称的、传递的,),且,RR,，则必有,RR.,通常用,r(R),表示,R,的自反闭包,s(R),表示,R,的对称闭包,t(R),表示,R,的传递闭包,2.4,关系上的闭包运算,例：整数集,Z,上的“,”,关系的自反闭包是“”关系；对称闭包是“”关系；传递闭包是它本身。,定理：,设,R,是集合,X,上的关系，则,r(R)=RUQ,，其中,Q=(x,x),|,x,X,s(R)=RU,t(R)=,=RUR,2,UR,3,U,设,X,是有限集，并设,X,有,n,个元素，则,t(R)=,2.4,关系上的闭包运算,例,：设集合,A=a,b,c,d,，定义,R=(a,b),(b,a),(b,c),(c,d),，求,r(R),，,s(R),，,t(R),解：,r(R)=RUQ,=(a,a),(b,b),(c,c),(a,b),(b,a),(b,c),(c,d),s(R)=RU,=(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),t(R)=RUR,2,UR,3,UR,4,=(a,b),(b,a),(b,c),(c,d)U(a,a),(a,c),(b,b),(b,d)U,(a,b),(a,d),(b,a),(b,c)U(a,a),(a,c),(b,b),(b,d),=(a,a),(b,b),(a,b),(a,c),(a,d),(b,a),(b,c),(b,d),(c,d),2.4,关系上的闭包运算,例：设有,X,上的关系,R,1,R,2,且,R,1,R,2,试证,1)r(R,1,)r(R,2,)2)s(R,1,)s(R,2,)3)t(R,1,)t(R,2,),证明：,1),因为,R,1,R,2,所以,R,1,ER,2,E,即,r(R,1,)=r(R,2,),2),因为,R,1,R,2,所以,所以,即,s(R,1,)=s(R,2,),3),对任意的,nN,根据数学归纳法可知：,又因为,t(R)=RUR,2,UR,3,U,所以,t(R,1,)t(R,2,),2.4,关系上的闭包运算,集合,A,上的二元关系,R,的闭包运算可以,复合,，例如,ts(R)=t(s(R),表示,R,的对称闭包的传递闭包，可以简称为,R,的对称传递闭包。,tsr(R),则表示,R,的自反对称传递闭包。,定理：,设,R,是集合,A,的二元关系，则有,1),如果,R,是自反的，那么,s(R),和,t(R),也是自反的；,2),如果,R,是对称的，那么,r(R),和,t(R),也是对称的；,3),如果,R,是传递的，那么,r(R),也是传递的,4)rs(R)=st(R),5)rt(R)=tr(R),6)ts(R)st(R),2.5,次序关系,定义,2.12,集合,X,上的关系,R,如果是自反的、反对称的、传递的，则称,R,在,X,上是,偏序,的或称,R,是集合,X,上的偏序关系。而称集合,X,为,R,的,偏序集,用,(X,R),表示,.,一般用符号“,”表示偏序,(,有时我们用,x,y,表示,xy,且,xy