三、关系、关系表示和性质.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,35关系及其表示,举例,：“大于”关系，“同学”关系，“整除”关系，电影票和座位间“对号”关系,记法：大于关系“”：,|x,y,是实数 且,xy,对号关系,R:,R,=,|x,是电影票号，,y,是座位号，且两者一致,定义：关系（,Relation）,任一,序偶,的,集合,确定了一个二元关系,。,关系是一个集合；,以,序偶,为元素。,集合元素间的某种联系我们统称为“,关系,”,如果,R,是一个关系，,序偶R,则说,x,和,y,具有关系,R，,也可记为,xRy,序偶,R,则说,x,和,y,没有关系,R，,也可记为,x R y,关系及其表示,定义：,前域（,Domain）,和值域（,Range）,由 R,的所有,x,组成的集合,domR,称为,R,的定义域或前域，即,domR,x,|(,y)(,R),；,由R,的所有,y,组成的集合,ranR,称为,R,的,值域，即,ranR,y,|(,x),(R),R,的域,FLD R domR,ranR,关系的前域、值域和域,定义,:,X,到,Y,的,关系,令,X,和,Y,是任意两个集合，直积,XY,的,子集,R,称为,X,到,Y,的,关系。,例题：关系,R=,则有：,2,R b,2 R B,dom,R=1,2,3,ran R=a,B,c,FLD R=1,2,3,a,B,c,若,R,XY，,则：,R,是从,X,到,Y,的关系,dom,R,X,ranR,Y,R,domR,ranR,XY,注意,关系及其表示,关系及其表示,如,A=1,2,3,，则I,A,说明:1、,XY,的两个平凡子集,XY,和,，,分别为,X,到,Y,的,全域关系,和,空关系,。,2、当,XY,时，称,R,为,X,上的关系。(,R,X X,),定义,恒等关系,设,I,X,是,X,上的二元关系且满足,I,X,|x,X，,则称,I,X,是,X,上的恒等关系。,定义,n,元关系,(,Relation),笛卡尔积,A,1,A,2,A,n,的,任一子集,称为一个,A,1,A,2,A,n,上的,n,元关系。,例题：若,H=f,m,s,d,表示一个家庭中父，母，子，女四个人的集合，确定,H,上的全域关系和空关系，另外再确定,H,上的一个关系，指出该关系的值域和前域。,解 设,H,上的同一家庭成员关系为,H1,，,H1=,H1,为,全域关系,例题,设,H,上互不相识的关系为,H2,H2,为,空关系,设,H,上的,长幼关系,为,H3,H3=,dom,H3=f,m,ran,H3=s,d,关系的运算,由于关系的本质仍然是,集合,，所以,集合的运算,、,也,适用于关系。,例：设,X,1,2,3,4，,若,H|(x-y)/2,是整数,S|(x-y)/3,是正整数，求,H,S，H,S，H，SH。,解：,H,=,S,=,H,S,=,H,S,=,H,=,X,X,H=,SH,=,关系运算定理,定理3-5.1:,若,Z,和,S,是从集合,X,到集合,Y,的两个关系，则,Z、S,的并、交、补、差仍是,X,到,Y,的关系。,提示,：只要证明运算的结果仍然是,XY,的子集即可,证明 因为,Z,X,Y，S,X,Y,故,Z,S,X,Y,Z,S,X,Y,S=(,X,Y-S),X,Y,Z-S=Z,S,X,Y,关系的表达形式,1、序偶的集合,2、矩阵表示,Xx,1,，x,2,，,，,x,m,，Yy,1,，y,2,，,，,y,n,，R,为从,X,到,Y,的,一个二元关系。,M,R,r,ij,mn,例：设,Aa,1,，a,2,，,Bb,1,，b,2,，b,3,，,R,写出,R,的关系矩阵,M,R,1,当,R,r,ij,0,当,R,关系的表达形式,3、图形表示,上例,R ,的关系图：,关系图主要表达结 点与结点之间的,邻接关系,，故与,结点位置,和,线段长短,无关。,作图规则：,X,集上的节点,Y,集上的节点,有向箭头与序偶对应,作业,P109(1)、(2)、(5)c、(8),？,从,A,到,B,的不同的关系共有多少？设|,A|m，|B|n,|,AB|mn AB,的子集个数为2,mn,A,到,B,上的不同关系有2,mn,种,。,36 关系的性质,定义1,自反,（,Reflexive）,设,R,为定义在集合,X,上的二元关系，如果对于每个,x,X，,有,R,，,则称二元关系,R,是自反的。,R,在,X,上自反,（,x）（x,X,R,）,例,1：设,A1,2,3，R,主对角线元素,全,为1,每个结点有自回路,比较,自反,与,恒等,关系,关系矩阵：,关系图：,关系的性质2,定义2,对称（,Symmetry）,设,R,是,X,上的二元关系，如果对于每个,x,y X,每当,R,就有,R,，,则称关系,R,在集合,X,上是,对称,的。,R,在,X,上对称,（,x)(,y)(,x,X,y,X,R,R,）,判定定理,：,R,在,X,上自反，当且仅当,I,X,R,例,：设,A1,2,3,R,为集合,A,上的二元关系，,R,弧总是成对出现,矩阵关于主对角线对称,关系的性质2,X=1,2,3 R=,X=1 R=,X=1,2,3 R=,对称的,既自反，又对称,对称而不自反,定理,R,是对称的，当且仅当,R=,R,c,例 设,A=2,3,5,7,R=|(x-y)/2,是整数，验证,R,在,A,上是自反和对称的。,证明 因为对,x,A,，（x-x）/2=0,即,R,所以,R,是自反的。,对,x,y,A,，,若,R,则有（,x-y)/2,是整数，那么,（,y-x）/2,也是整数，即 R,所以,R,是对称的。,R,定义3,传递,（,Transitive）,设,R,是,集合,X,上的二元关系,如果对于,x,y,zX，,若,R，R,，,有,R,则称,R,在,X,上是传递的。,R,在,X,上是传递的,(,x),(,y),(,z)(,xX,yX,zX,R,R,R,）,关系的性质3,关系图的特点,：如果从,a,到,b,存在一条有向路径，则,a,到,b,也,存在一条有向弧。,如,：实数集合中的大于关系，集合中的包含关系等都是传递的。,例,：设,B=1,2,3,4,5,6,定义,B,上二元,整除,关系,R=,a,b,B,a,能整除,b,验证整除关系为传递的。,R=,例,：设,X1,2,3，R,1,=,R,2,=,R,3,=,R,1,、R,2,、R,3,都是,传递的吗？,关系的性质3,解：,R,1,、R,2,都是传递的，,R,3,不是传递的,。,见书,P111,注：对于单个序偶构成的关系,认为是传递的。,关系的性质4,定义4,反自反,（,Antireflexive,）,设,R,为定义在集合,X,上的二元关系，如果对于,x,X,，,都有,R,，,则称二元关系,R,是,反自反的。,R,在,X,上反自反,（,x)(,x,X,R,）,如：父、子关系，数的大于关系等都是反自反的。,？,一个关系不是自反的，一定是反自反的吗？,？,有没有既自反又反自反的二元关系,(1)例：,A1,2,3，S,S,不是自反的，也不是反自反的。,主对角线元素,全为0；,每个结点都没有自回路,(2),空集,上的任一二元关系既是,自反,的又是,反自反,的。,定义5,反对称,（,Antisymmetric,）,设,R,是,X,上的二元关系，如果对于,每个,x,yX,每当R,和R，,必有,xy,，,则称,R,在,X,上的是反对称的。,或,每当,R,和,x,y,则必有,R,，,则称,R,在,X,上的是反对称的。,关系的性质5,R,在,X,上反对称,（,x)(,y)(,x,X,y,X,R,R,xy,),（,x)(,y)(,x,X,y,X,R,x,y,R,),关于主对角线对称的元素不能同时为1；,弧总不是成对出现的。,例如实数集合中的,关系、集合的,关系等是反对称的。,关系的性质,例6：,设,Aa,b,c,A,上的关系,R,S,T,为,R,S,T,注意：有些关系,既非对称,，也,非反对称,；,有些关系既是,对称,的，又是,反对称,的。,则,R、S,是反对称的。而,R、T,是对称的。,例：设有三个人，组成集合,AT，G，H,在,A,上的,朋友关系,具有哪些性质？,具有反自反和对称性。,关系的性质在其表达形式上的体现,关系的性质,关系矩阵,关系图,自反,主对角线上的所有元素都是1,每个结点都有自回路,反自反,主对角线上的所有元素都为0,每个结点都没有自回路,对称,关系矩阵是对称的,有向弧线成对出现,反对称,以主对角线对称的元素不能同时为1,任意两个结点间的弧线不可能成对出现,关系的证明方法：,要,证明,R,在,X,上,自反,假设,x,X,，,证出,R,要,证明,R,在,X,上对称,对,x,y,X,设,R,，,证出,R,要证明,R,在,X,上传递,对,x,y,zX,设,R,R,，,证出,R,要证明,R,在,X,上反自反,假设,x,X,，,证出,R,）,要证明,R,在,X,上反对称,对,x,y,X，,设,R,R,，,证,出,xy,作业:,P113(4),(6),