第四章关系

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第四章 关系,4.1,序偶与笛卡儿积,4.1.1,有序,n,元组,定义,4.1,由两个固定次序的个体,x,，,y,组成的序列称为序偶，,记为,，,其中,x,，,y,分别称为序偶的第一、二分量（或称第,一、二元素）。,定义,4.2,两序偶,，,是相等的，当且仅当,a=c,，,b=d,；,记作,=,。,关系,本章学习目标：,关系是一个很重要的数学基本概念，它在计算机科学中的许多方面如数据结构、数据库、情报检索、算法分析等都有很多应用。本章主要讨论二元关系理论。通过本章学习，读者应该掌握以下内容：,（,1,）关系的表示,（,2,）,关系的性质和运算,（,3,）,等价关系和集合的划分,（,4,）,偏序关系,第四章 关系,1,序偶与笛卡儿积,2,二元关系及其表示,3,关系的运算,4,关系的性质,5,关系的闭包,6,等价关系与集合的划分,7,相容关系,8,偏序关系,第四章 关系,4.1,序偶与笛卡儿积,4.1.1,有序,n,元组,定义,4.1,由两个固定次序的个体,x,，,y,组成的序列称为序偶，,记为,，,其中,x,，,y,分别称为序偶的第一、二分量（或称第,一、二元素）。,定义,4.2,两序偶,，,是相等的，当且仅当,a=c,，,b=d,；,记作,=,。,第四章 关系,4.1,序偶与笛卡儿积,4.1.2,笛卡儿积的概念,定义,4.3,给定两个集合,A,和,B,，,如果序偶的第一个分量是,A,中的,一个元素，第二个分量是,B,中的一个元素，则所有这种序偶的集,合称为集合,A,和,B,的笛卡儿积，简称为卡氏积，记为,AB,，,即,AB=,xAyB,。,第四章 关系,4.1,序偶与笛卡儿积,4.1.2,笛卡儿积的概念,例,4.1,（,1,）,A=a,，,b,，,B=c,，,d,，求,A,B,。,（,2,）,A=a,，,b,，,B=c,，,d,，求,B,A,。,（,3,）,A=a,，,b,，,B=1,，,2,，,C=c,，,求（,A,B,）,C,和,A,（,B,C,）。,第四章 关系,4.1,序偶与笛卡儿积,4.1.2,笛卡儿积的概念,解 （,1,）,A,B=a,，,b,c,，,d=,，,，,，,。,（,2,）,B,A=c,，,d,a,，,b=,，,，,，,。,（,3,）（,A,B,）,=a,，,b,1,，,2=,，,，,，,。,第四章 关系,4.1,序偶与笛卡儿积,4.1.2,笛卡儿积的概念,（A,B）,C=，c，c，c，,，c,=，。,B,C=1，2,c=，。,A,（B,C）=， 。,第四章 关系,4.1,序偶与笛卡儿积,4.1.3,笛卡儿积的性质,定理,4.1,设,A,，,B,，,C,为任意,3,个集合，则有,（,1,）,A,（,B,C,）,=,（,A,B,）,（,A,C,）,（,2,）,A,（,B,C,）,=,（,A,B,）,（,A,C,）,（,3,）（,A,B,）,C=,（,A,C,）,（,B,C,）,（,4,）（,A,B,）,C=,（,A,C,）,（,B,C,）,第四章 关系,4.1,序偶与笛卡儿积,4.1.3,笛卡儿积的性质,定理,4.3,设,A,，,B,，,C,，,D,为四个非空集合，则,A,B,C,D,的充,分必要条件是：,A,C,且,B,D,。,定理,4.2,设,A,，,B,，,C,为任意,3,个集合，且,C,，,则有,A,B,（,A,C,B,C,）,（,C,A,C,B,）,第四章 关系,4.1,序偶与笛卡儿积,4.1.3,笛卡儿积的性质,反之，如果,A,C,且,B,D,，,设任意,x,C,和,y,B,，,有,A,B,x,A,y,B,x,C,y,D,x,C,y,D,C,D,所以，,A,B,C,D,。,第四章 关系,4.2,二元关系及其表示,4.2.1,二元关系的概念,定义,4,.,5,设,R,是二元关系，由,R,的所有,x,组成的集合称,为,R,的定义域，记作,D,（,R,），即,D,（,R,）,=x,y,（,y,B,R,）,。,由,R,的所有,y,组成的集合称为,R,的值域，记作,R,（,R,），即,R,（,R,）,=y,x,（,x,A,R,）,。,定义,4,.,4,设,A,，,B,是两个集合，,R,是笛卡儿积,A,B,的任一子集，,则称,R,为从,A,到,B,的一个二元关系，简称关系。特别当,A,=,B,时，,则称,R,为,A,上的二元关系（或,A,上的关系）。,第四章 关系,4.2,二元关系及其表示,4.2.1,二元关系的概念,例,4.3,设,A=1,，,3,，,5,，,7,，,R,是,A,上的二元关系，当,a,，,b,A,且,ab,时，,R,，求,R,和它的定义域和值域。,解,R=,，,，,，,，,，,D,（,R,）,=1,，,3,，,5,，,R,（,R,）,=3,，,5,，,7,。,例,4.2,设,A=a,，,b,，,c,，,d,，,e,，,B=1,，,2,，,3,，,R=,，,，,，求,R,的定义域和值域。,解,D,（,R,）,=a,，,b,，,c,，,R,（,R,）,=2,，,3,。,第四章 关系,4.2,二元关系及其表示,4.2.1,二元关系的概念,定义,4.6,设,I,A,为集合,A,上的二元关系，且满足,I,A,=,x,A,，,则称,I,A,为集合,A,上的恒等关系。,第四章 关系,4.2,二元关系及其表示,4.2.2,二元关系的表示,1,关系矩阵表示法,设给定集合,A=a,1,，,a,2,，,，,a,n,，,集合,B=b,1,，,b,2,，,，,b,m,，,R,为,从,A,到,B,的一个二元关系，构造一个,nm,矩阵。用集合,A,的元素标,注矩阵的行，用集合,B,的元素标注矩阵的列，对于,aA,和,bB,，,若,R,，,则在行,a,和列,b,交叉处标,1,，否则标,0,。这样得到的,矩阵称为,R,的关系矩阵。,第四章 关系,4.2,二元关系及其表示,4.2.2,二元关系的表示,2,关系图表示法,有限集的二元关系可以用有向图来表示，设集合,A=a,1,，,a,2,，,，,a,n,，,集合,B=b,1,，,b,2,，,，,b,m,，,R,为从,A,到,B,的一个二元关系，首先在平面上作出,n,个结点分别记作,a,1,，,a,2,，,，,a,n,，,然后另外作出,m,个结点分别记作,b,1,，,b,2,，,，,b,m,，,如果,a,A,、,b,B,且,R,，,则自结点,a,到结点,b,作出一条有向弧，其箭头指向,b,。,如果,R,，,则结点,a,和结点,b,之间没有线段联结。用这种方法得到的图称为,R,的关系图。,第四章 关系,4.2,二元关系及其表示,4.2.1,二元关系的概念,解,R,的关系图，如图所示：,例,4.8 A=1,，,2,，,3,，,4,，,B=5,，,6,，,7,，,R=,，,，,，,，,作出,R,的关系图。,第四章 关系,4.2,二元关系及其表示,4.2.1,二元关系的概念,解,A,上的关系图如图所示。,例,4.9,设,A=1,，,2,，,3,，,4,，,R=,，,，,，,。,画出,A,上的关系图。,第四章 关系,4.3,关系的运算,4.3.1,关系的交、并、差、补运算,例,4.10,设,X=1,，,2,，,3,，,4,，,5,，若,A=,x,与,y,的差能被,2,整,除,，,B=,x,与,y,的差为正且能被,3,整除,，求,A,B,，,A,B,，,A,-,B,，,B,-,A,，,A,。,第四章 关系,4.3,关系的运算,4.3.1,关系的交、并、差、补运算,解,A=,，,，,，,，,，,，,，,，,，,，,，,，,B=,，,AB=,，,，,，,，,，,，,，,，,，,，,，,，,，,，,AB=,A,-,B=,，,，,，,，,，,，,，,，,，,B,-,A=，,A=1，2，3，4，51，2，3，4，5,-,，,，,，,=，,第四章 关系,4.3,关系的运算,4.3.2,关系的复合运算,定义,4.7,设,R,是从集合,A,到集合,B,上的二元关系，,S,是从集合,B,到,集合,C,上的二元关系，则,RS,称为,R,和,S,的复合关系，表示为,RS=,x,A,z,C,y,（,y,B,R,S,第四章 关系,4.3,关系的运算,4.3.2,关系的复合运算,例,4.10,（,1,）,A=1,，,2,，,3,，,4,，,B=3,，,5,，,7,，,C=1,，,2,，,3,，,R=,，,，,，,S=,，,，,RS=,，,。,如图所示：,第四章 关系,4.3,关系的运算,4.3.2,关系的复合运算,（,2,）设,R,，,S,都是,A,上的关系，,A=1,，,2,，,3,，,4,。,R=,，,，,，,S=,，,，,，,，即,S,为,A,上的恒等关系，则,RS=SR=R,。,如图所示：,（,3,）设,R,是,A,上的关系，,S,为,A,上的空关系，即,S=,，,则,RS=SR=,。,第四章 关系,4.3,关系的运算,4.3.2,关系的复合运算,定理,4.4,设,R,是从,A,到,B,的关系，,S,是从,B,到,C,的关系，其中,A=a,1,，,a,2,，,，,a,m,，,B=b,1,，,b,2,，,，,b,n,，,C=c,1,，,c,2,，,，,c,t,。,而,M,R,，,M,S,和,M,R S,分别为关系,R,，,S,和,RS,的关系矩阵，则有,M,RS,=M,R,M,S,。,第四章 关系,4.3,关系的运算,4.3.2,关系的复合运算,定理,4.5,设,R,是从集合,A,到集合,B,上的二元关系，,S,是从集合,B,到,集合,C,上的二元关系，,T,是从集合,C,到集合,D,上的二元关系，则有：,（,1,）,R,（,ST,）,=RSRT,（,2,）,R,（,S,T,）,RS,RT,（,3,）（,RS,）,T= RTST,（,4,）（,R,S,）,T,RT,ST,第四章 关系,4.3,关系的运算,4.3.2,关系的复合运算,定理,4.6,设,R,是从,A,到,B,的关系，,S,是从,B,到,C,的关系，,T,是从,C,到,D,的关系，则有,R,（,ST,）,=,（,RS,）,T,。,定义,4.8,设,R,是从,A,上的关系，,n,为整数，关系,R,的,n,次幂定义如下：,（,1,）,R,0,=x,A=I,A,；,（,2,）,R,n+1,=,R,n,R,。,从关系,R,的,n,次幂定义，可得出下面的结论：,（,1,）,R,n+m,=,R,n,R,m,；,（,2,）（,R,n,）,m,=,R,nm,。,第四章 关系,4.3,关系的运算,4.3.3,关系的逆运算,定义,4.9,设,R,是从集合,A,到集合,B,的二元关系，如果将,R,中每序偶,的第一元素和第二元素的顺序互换，所得到的集合称为,R,的逆关,系，记为,R,1,，,即,R,1,=,R,定理,4.7,设,R,，,S,和,T,都是从,A,到,B,的二元关系，则下列各式成立：,（,1,）（,R,）,1,）,1,=R,（,2,）,（,R,S,）,1,=R,1,S,1,（,3,）,（,R,S,）,1,=R,1,S,1,（,4,）（,A,B,）,1,=B,A,（,5,）（,R,）,1,= ,（,R,1,）（,这里,R=,A,B,-,R,）,（,6,）（,R,-,S,）,1,=R,1,-,S,1,第四章 关系,4.3,关系的运算,4.3.3,关系的逆运算,定理,4.8,设,R,是从,A,到,B,的二元关系，,S,是从,B,到,C,的二元关系，则,下面的式子成立：（,RS,）,1,=S,1,R,1,证明,（,RS,）,1,RS,y,（,y,B,R,S,）,y,（,y,B,S,1,R,1,）,S,1,R,1,。,所以，（,RS,）,1,=S,1,R,1,。,第四章 关系,4.4,关系的性质,4.4.1,自反性和反自反性,定义,4.10,设,R,是集合,A,上的二元关系，如果对于每个,x,A,，,都有,R,，,则称二元关系,R,是自反的。,R,在,A,上是自反的,x,（,x,A,R,）,定义,4.11,设,R,是集合,A,上的二元关系，如果对于每个,x,A,，,都有,R,，,则称二元关系,R,是反自反的。,R,在,A,上是反自反的,x,（,x,A,R,）,第四章 关系,4.4,关系的性质,4.4.2,对称性和反对称性,定义,4.12,设,R,是集合,A,上的二元关系，如果对于每个,x,，,y,A,，,当,R,，,就有,R,，,则称二元关系,R,是对称的。,R,在,A,上是对称的,x,y,（,x,A,y,A,R,R,）,定义,4.13,设,R,是集合,A,上的二元关系，如果对于每个,x,，,y,A,，,当,R,和,R,时，必有,x=y,，,则称二元关系,R,是反对,称的。,第四章 关系,4.4,关系的性质,4.4.3,传递性,定义,4.14,设,R,是集合,A,上的二元关系，如果对于任意,x,，,y,，,z,A,，,当,R,，,R,，,就有,R,，,则称二元,关系,R,在,A,上是传递的。,R,在,A,上是传递的,x,y,z,（,x,A,y,A,z,A,R,R,R,）,第四章 关系,4.4,关系的性质,4.4.3,传递性,例,4,.,13,设,A=a,，,b,，,c,，,R,，,S,，,T,是,A,上的二元关系，其中,R=,，,，,S=,，,，,T=,说明,R,，,S,，,T,是否为,A,上的传递关系。,解 根据传递性的定义知，,R,和,T,是,A,上的传递关系，,S,不是,A,上的,传递关系，,因为,R,，,R,，,但,R,。,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,1,自反性的判定方法,定理,4.9,设,R,是,A,上的二元关系，则,R,在,A,上是自反的当且仅当,I,A,R,。,证明 先证必要性。,任取,，,由于,R,在,A,上是自反的，则有,I,A,x,，,y,A,x=y,R,从而证明了,I,A,R,。,再证充分性。任取,x,A,，,有,x,A,I,A,R,因此，,R,在,A,上是自反的。,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,1,自反性的判定方法,R,的关系矩阵为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,1,自反性的判定方法,R,的关系图为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,2,反自反性的判定方法,定理,4.10,设,R,是,A,上的二元关系，则,R,在,A,上是反自反的当且仅,当,I,A,R=,。,例,4,.,15,设集合,A=a,，,b,，,c,，,d,，,A,上的二元关系,R=,，,，,，,，,，,，,，,讨论,R,的性质，写出,R,的关系矩阵，画出,R,的关系图。,解 由于,，,，,，,R,，即,I,A,R=,，,所以,R,是反自反的。,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,2,反自反性的判定方法,R,的关系矩阵为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,2,反自反性的判定方法,R,的关系图为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,3,对称性的判定方法,定理,4.11,设,R,是,A,上的二元关系，则,R,在,A,上是对称的当且仅当,R=R,1,。,例,4.16,设集合,A=a,，,b,，,c,，,d,，,A,上的二元关系,R=,，,，,，,，,，,，,，,，,，,讨论,R,的性质，写出,R,的关系矩阵，画出,R,的关系图。,解 因为,R,，,所以,R,不是自反的。,由于,R,，即,I,A,R,，,所以,R,不是反自反的。,R,1,=,，,，,，,，,，,，,，,，,，,R=R,1,，,由上面的定理可知，,关系,R,是对,称的。,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,3,对称性的判定方法,R,的关系矩阵为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,3,对称性的判定方法,R,的关系图为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,4,反对称性的判定方法,定理,4.12,设,R,是,A,上的二元关系，则,R,在,A,上是反对称的当且仅,当,R,R,1,I,A,。 ：,例,4.17,设集合,A=a,，,b,，,c,，,d,，,A,上的二元关系,R=,，,，,，,，,，,，,讨论,R,的性质，写出,R,的关系矩阵，画出,R,的关系图。,解 因为,R,，,所以,R,不是自反的。,由于,R,，即,I,A,R,，,所以,R,不是反自反的。,因为,R,1,=,，,，,，,，,，,，,R,R,1,，,所以,关系,R,不是对称的。,RR,1,=,I,A,），,由上面的定理可知，,R,是反对称的。,R,的关系矩阵为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,4,反对称性的判定方法,R,的关系矩阵为：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,4,反对称性的判定方法,R,的关系图如图,4.8,所示： ：,第四章 关系,4.4,关系的性质,4.4.4,关系性质的判定,5,传递性的判定方法,定理,4.3,设,A,，,B,，,C,，,D,为四个非空集合，则,A,B,C,D,的充,分必要条件是：,A,C,且,B,D,。,定理,4.13,设,R,是,A,上的二元关系，则,R,在,A,上是传递的当且仅当,RR,R,。,定理,4.14,设集合,A=a,1,，,a,2,，,，,a,n,，,R,是,A,上的二元关系，,R,的关系矩阵为,M,R,，令,M=M,R,M,R,，则,R,在,A,上是传递的当且仅当矩阵,M,的第,i,行，第,j,列元素为,1,时，,M,R,的第,i,行，第,j,列元素必为,1,。,第四章 关系,4.5,关系的闭包,定义,4.15,设是集合,A,上的二元关系，如果有另一个关系,满足：,（,1,）是自反的（对称的、传递的）；,（,2,）,；,（,3,）对于任何自反的（,对称的、传递的）关系，如果有,，就,有,。,则称关系为,R,的自反（对称、传递）闭包。,定理,4.15,设是集合,A,上的二元关系，则,r,（）,=,I,A,，,第四章 关系,4.5,关系的闭包,定理,4.16,设是集合,A,上的二元关系，则,s,（）,=,1,定理,4.17,设,R,是集合,A,上的二元关系，则,t,（,R,）,=R,R,2,R,3,定理,4.18,设,A=a,1,，,a,2,，,，,a,n,，,R,是集合,A,上的二元关系，,则存在一个正整数,k,n,，,使得,t,（,R,）,= R,R,2,R,3,R,k,第四章 关系,4.5,关系的闭包,定理,4.19,设,R,是非空集合,A,上的关系，则,（,1,）,R,是自反的，当且仅当,r,（,R,）,=R,；,（,2,）,R,是对称的，当且仅当,s,（,R,）,=R,；,（,3,）,R,是传递的，当且仅当,t,（,R,）,=R,。,定理,4.20,设,R,，,S,是非空集合,A,上的关系，且,R,S,，,则,（,1,）,r,（,R,）,r,（,S,）；,（,2,）,s,（,R,）,s,（,S,）；,（,3,）,t,（,R,）,t,（,S,）。,第四章 关系,4.5,关系的闭包,定理,4.21,设,R,是非空集合,A,上的关系，则,（,1,）,rs,（,R,）,=,sr,（,R,）；,（,2,）,rt,（,R,）,=,tr,（,R,）；,（,3,）,ts,（,R,）,st,（,R,）。,第四章 关系,4.6,等价关系与集合的划分,4.6.1,等价关系,定义,4.16,设,R,是非空集合,A,上的二元关系，如果有,R,是自反的、,对称的和传递的，则称,R,是集合,A,上的等价关系,例,4.23,设集合,A=a,，,b,，,c,，,d,，,，,R=,，,，,，,，,，,，,，,。,验证,R,是,A,上的等价关系。,证明,写出,R,的关系矩阵,第四章 关系,4.6,等价关系与集合的划分,4.6.1,等价关系,从关系矩阵主对角线元素都是,1,，可知,R,是自反的。关系矩阵是,对称的，故,R,是对称的。从,R,的序偶表达式中，可以看出,R,是传,递的，逐个检查序偶，如,，,R,，,有,R,。,，,R,，,有,R,，,，,R,，,有,R,，,。故,R,是,A,上的等价关系。,第四章 关系,4.6,等价关系与集合的划分,4.6.2,等价类,定义,4,.,17,设,R,是非空集合,A,上的等价关系，对于任何,a,A,，,集合,a,R,=x,x,A,且,R,称为元素,a,形成的,R,等价类。,。,定理,4.22,设,R,是非空集合,A,上的等价关系，对于,a,，,b,R,，,有,R,当且仅当,a,R,=b,R,。,第四章 关系,4.6,等价关系与集合的划分,4.6.2,等价类,定义,4,.,18,设,R,是集合,A,上的等价关系，等价类集合,a,R,a,A,称作,A,关于,R,的商集，记作,A/R,。,定理,4.22,设,R,是非空集合,A,上的等价关系，对于,a,，,b,R,，,有,R,当且仅当,a,R,=b,R,。,定义,4,.,19,设,A,是一个集合，,A,1,，,A,2,，,，,A,m,是它的子集，,如果它满足下列条件：,（,1,）所有,A,i,间均是分离的，亦即对所有,i,，,j,（,i=1,，,2,，,，,m,，,j=1,，,2,，,，,m,），,如果,i,j,，则,A,i,A,j,=,。,（,2,）,A,1,A,2,A,m,=A,则称,A=A,1,，,A,2,，,，,A,m,为集合,A,的一个划分，而,A,1,，,A,2,，,，,A,m,称为这个划分的块。,第四章 关系,4.6,等价关系与集合的划分,4.6.2,等价类,定理,4.23,设,R,是非空集合,A,上的等价关系，确定了,A,的一个划,分，该划分就是商集,A/R,。,定理,4.24,集合,A,的一个划分确定,A,上的一个等价关系。,定理,4.25,设,R,1,和,R,2,是非空集合,A,上的等价关系，则,R,1,=R,2,当且,仅当,A/R,1,=A/R,2,。,第四章 关系,4.6,等价关系与集合的划分,4.6.2,等价类,例,4.28,设集合,A=1,，,2,，,3,，,4,，,5,上的关系,R,为,R=,，,，,，,，,，,，,，,，,，,，,，,，,。,解 它的关系图如图,4.9,所示：,由此图可以看出关系,R,是等价关系，并且它的等价类分别为,1,R,=2,R,=3,R,4,R,=5,R,由等价关系所构成的等价类在图中即是等价关系图中的完全图，所谓完全图是指图形中每个结点与其它结点有边联结的图形。,