交大数理逻辑课件10-3 关系

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,10,章 关 系,10.1,二元关系,10.2,关系矩阵和关系图,10.3,关系的逆、合成、限制和象,10.4,关系的性质,10.5,关系的闭包,10.6,等价关系和划分,10.7,相容关系和覆盖,10.8,偏序关系,关系性质的充要条件,设,R,为,A,上的二元关系,则,R,在,A,上,自反,当且仅当,I,A,R,R,在,A,上,反自反,当且仅当,R,I,A,=,R,在,A,上,对称,当且仅当,R,=,R,1,R,在,A,上,反对称,当且仅当,R,R,1,I,A,R,在,A,上,传递,当且仅当,R,R,R,证：,必要性：,R,是,传递,R,R,R,R,R,(,z,)(,x,z,R,z,y,R,),R,R,R,R,充分性：,R,R,R,R,是,传递,x,z,R,z,y,R,R,R,R,R,是,传递的,R,是,传递的,R,R,R,10.5.2,关系闭包的定义,闭包的,定义,包含,R,的最小自反关系是,R,的,自反闭包,包含,R,的最小对称关系是,R,的,对称闭包,包含,R,的最小传递关系是,R,的,传递闭包,一般地，将,R,的,自反闭包,记作,r,(,R,),对称闭包,记作,s,(,R,),传递闭包,记作,t,(,R,).,10.5.3,闭包的性质,定理,10.5.4,对非空集合,A,上的关系,R,，有,若,R,是自反的,r,(,R,)=,R,;,若,R,是对称的,s,(,R,)=,R,;,若,R,是传递的,t,(,R,)=,R,.,定理,10.5.5,对非空集合,A,上的关系,R,1,、,R,2,若,R,1,R,2,则,r,(,R,1,),r,(,R,2,),s,(,R,1,),s,(,R,2,),t,(,R,1,),t,(,R,2,),定理,10.5.5,对非空集合,A,上的关系,R,1,、,R,2,，则,r,(,R,1,) ,r,(,R,1,) =,r,(,R,1,R,2,),s,(,R,1,) ,r,(,R,1,) =,s,(,R,1,R,2,),t,(,R,1,) ,r,(,R,1,) =,t,(,R,1,R,2,),10.5.4,闭包的构造方法,设,R,为,A,上的关系,则有,定理,10.5.7:,r,(,R,) =,R,R,0,=,R,I,A,定理,10.5.8:,s,(,R,) =,R,R,-1,定理,10.5.9:,t,(,R,) =,R,R,2,R,3,定理,10.5.10:,设,A,为非空集合，,|A|=n,，则存在一个正整数,kn,，使得,t,(,R,) =,R,R,2,R,3, ,R,k,(,kn),t,(,R,) =,R,R,2,R,3, ,R,n,以上分别是自反闭包,r,(,R,),、对称闭包,s,(,R,),和传递闭包,t,(,R,),的构造方法,证明,:,t,(,R,) =,R,R,2,R,3,先证,R,R,2,R,3,t,(,R,),当,n,=1,时，,R,1,=,R,t(,R,),。,设,n,=,k,时，,R,k,t,(,R,),。,下证,R,k,+1,t(,R,),x,y,R,k,+1,x,y,R,k,R,(,z,)(,x,z,R,z,y,R,k,),(,z,)(,x,z,t,(,R,),z,y,t,(,R,),x,y,t,(,R,),即,R,k,+1,t,(,R,) (k0),故,R,R,2,R,3,t,(,R,),证明,:,t,(,R,) =,R,R,2,R,3,再证,t(,R,),R,R,2,R,3,显然,R,R,R,2,R,3,下证明,R,R,2,R,3,是传递的。,x,z,R,R,2,R,3,z,y,R,R,2,R,3,(,t,)(,x,z,R,t,)(,s,)(,z,y,R,s,),(s,t0,的自然数,),x,y,R,t,R,s,=,R,t+s,R,R,2,R,3,x,y,R,R,2,R,3,根据传递关系的定义,，,有,R,R,2,R,3,是传递的。,闭包的构造方法举例,设,A,=,a,b,c,，定义,A,上的二元关系,R,为：,R,=,a,b,b,c,c,a,试用关系合成运算方法求：,r(,R,),，,s(,R,),，,t(,R,),解,:,r(,R,)=,R,I,A,=,a,b,b,c,c,a,a,a,b,b,c,c,s(,R,)=,R,R,-1,=,a,b,b,c,c,a,b,a,c,b,a,c,t,(,R,) =,R,R,2,R,3,：,R,2,=,R,R,=,a,c,b,a,c,b,R,3,=,R,2,R,=,a,a,b,b,c,c,=,I,A,t(,R,),=,a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c,=,E,A,闭包的构造方法（矩阵法）,设关系,R,r,(,R,),s,(,R,),t,(,R,),的关系矩阵分别为,M,M,r,M,s,和,M,t,则,M,r,=,M,+,I,M,s,=,M,+,M,M,t,=,M,+,M,2,+,M,3,+ ,说明,:,I,是和,M,同阶的单位矩阵,M,是,M,的转置矩阵,.,注意,:,在上述等式中矩阵的元素相加时使用,逻辑加,.,闭包的矩阵构造方法举例,设,A,=,a,b,c,，定义,A,上的二元关系,R,为：,R,=,a,b,b,c,c,a,试求：,t(,R,),解：,用关系矩阵求,t(,R,),的方法如下：,闭包的矩阵构造方法举例,其中，表示矩阵的对应元素进行逻辑加运算,。,闭包同时具有的多种性质,定理,10.5.11,对非空集合,A,上的关系,R,，有,若,R,是自反的,s,(,R,),、,t,(,R,),是自反的,;,若,R,是对称的,r,(,R,),、,t,(,R,),是对称的,;,若,R,是传递的,r,(,R,),是传递的,.,证,：,R,是传递,R,R,R,，,而,r,(,R,)=,R,I,A,r,(,R,),r,(,R,),=(,R,I,A,),(,R,I,A,),=,R,(,R,I,A,),I,A,(,R,I,A,),=,R,R,R,I,A,I,A,(,R,I,A,),=,R,R,(,R,I,A,),=,R,I,A,=,r,(,R,),注意：若,R,是传递的 ，,s,(,R,),是不一定是传递的,.,如：,A=1, 2, 3,R=,是传递的,r,(,R,) =,R,I,A,=, , ,是传递的,但,s,(,R,) =,R,R,-1,=, ,不是传递,闭包同时具有的多种性质,定理,10.5.12,对非空集合,A,上的关系,R,有,rs,(,R,) =,sr,(,R,),rt,(,R,) =,tr,(,R,),st,(,R,),ts,(,R,),设,A=1, 2,R,=,st,(,R,),=,s,(,t,(,R,),=,s,()= , ,ts,(,R,),=,t,(,s,(,R,),=,t,(, ),= , , , ,10.6,等价关系和划分,等价关系,是最重要、最常见的二元关系之一。它有良好的性质。在计算机科学和计算机技术、信息科学和信息工程中都有广泛的应用。,定义,设,R,为非空集合上的关系,.,如果,R,是,自反的,、,对称的,和,传递的,则称,R,为,A,上的,等价关系,.,等价关系的关系矩阵和关系图的特点,关系矩阵的主对角线全为,1,且是对称阵；,关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边。,等价关系的实例,设,A,=1,2,3,4,5,，,R,是,A,上的等价关系，,R,=,1,1,1,2,2,1,2,2,3,3,3,4,4,3,4,4,5,5,则,R,的关系矩阵,M,(,R,),如下：,A,上的等价矩阵可用正方形的一条对角线和线上的若干正方形表示。,M(R),的主对角线全为,1,且是对称阵，所以,R,是自反的和对称的；还可以用二元关系传递性的定义证明,R,是传递的。故,R,是,A,上的等价关系。,等价关系的实例,设,A,=1,2,3,4,5,6,7,8,A,上的关系,R,如下定义：,R,= |,x,y,A,x,y,(mod 3) ,其中,x,y,(mod 3),叫做,x,与,y,模,3,相等,即,x,除以,3,的余数与,y,除以,3,的余数相等,.,验证模,3,相等关系,R,为,A,上的等价关系,x,A, x-x=,3,0,，所以,x,x,(mod 3),(R,是自反的,),x,y,A,若,x,y,(mod 3),x,-y =,3,t,，,(,t,Z),y-x =,3,(,t,),，,(,t,Z),y,x,(mod 3),(,R,是对称的）,x,y,z,A,若,x,y,(mod 3),y,z,(mod 3),x,-y =,3,t,1,，,t,1,Z,，,y-z =,3,t,2,，,t,2,Z,x,-z=(,x,-y)+(,y,-,z,)=,3,t,1+,3,t,2=,3,(,t,1+,t,2),，,t,1+,t,2,Z,，,x,z,(mod 3),(R,是传递的,),A,上模,3,等价关系的关系图,设,A,=1,2,3,4,5,6,7,8,R,= |,x,y,A,x,y,(mod 3) ,1(mod 3)=4(mod 3)=7(mod 3)=1,2(mod 3)=5(mod 3)=8(mod 3)=2,3,(mod 3)=6(mod 3)=0,等价类,定义,设,R,为非空集合,A,上的等价关系,x,A,，令,x,R,= ,y,|,y,A,xRy,称,x,R,为,x,关于,R,的,等价类,简记为,x,.,实例,A=1,2,3,4,5,6,7,8 ,上模,3,等价关系的等价类：,1,R,=4,R,=7,R,=1,4,7 2,R,=5,R,=8,R,=2,5,8,3,R,=6,R,=3,6,等价类的性质,定理,10.6.1,设,R,是非空集合,A,上的,等价关系,，对,x, y A,，下面的结论成立。,(1) x,R,，且,x,R,A,；,(2),若,R,，则,x,R,=y,R,；,(3),若,R,，则,x,R,y,R,=,；,(4),任何等价类都是,A,的非空子集,A,中任取两个元素，它们的等价类或相等、或是不相交,所有等价类的并集就是,A,A,中任取两个元素，它们的等价类或相等、或是不相交,等价类的性质举例,实例,:,A=1,2,8 ,上模,3,等价关系的等价类：,1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,6,12=,13=,23=,1,4,7,2,5,8 3,6=A,商集,定义,设,R,为非空集合,A,上的等价关系,以,R,的,所有不交的等价类,作为元素的集合，称为,A,在,R,下的,商集,记做,A,/,R,A,/,R,= ,x,R,|,x,A,实例,A,=1,2,3,4,5,6,7,8,，,A,关于模,3,等价关系,R,的商集为,A/R,= 1,4,7, 2,5,8, 3,6 =0, 1, 2,A,关于恒等关系,I,A,商集为：,A/I,A,= 1,2, ,8= ,x,|,x,A,A,关于全域关系,E,A,的商集为：,A/E,A,= 1, 2, ,8 =A,10.6.2,集合的划分,定义,设,A,为非空集合,若存在集合,满足下面条件：,(1) (,x,)(,x,x,A) (,即,P(A),(2),(3) ,=,A,(4),x,y,(,x,y,x,y,x,y,=,),满足条件,(1)(2)(3),，称,是,A,的,覆盖,.,满足全部条件称,为,A,的一个,划分,，,称,中的元素为,A,的,划分块,.,如：,A,关于模,3,等价关系,R,的,商集,是,A,的一个,划分,A/R,= 1,4,7, 2,5,8, 3,6 , ,1,4,7, ,1,2,5,8, 3,5,6 ,为,A,的一个,覆盖,商集和划分的关系,定理,10.6.2,对非空集合,A,上的一个等价关系,R,，,A,商集,A/R,就是,A,的一个划分。它称为,由等价关系,R,诱导出来的,A,的划分,，记作,R,即由,A,上的等价关系,R,可以诱导出,A,的一个划分。,定理,10.6.3,对非空集合,A,上的一个划分,，令,A,上的关系,R,为,R,=|(,z)(z, xz yz ,则,R,是,A,上的等价关系，它称为,划分,诱导出来的,A,上的等价关系。,定理,10.6.4,对非空集合,A,上的一个划分,和,A,上的等价关系,R,，,诱导,R,当且仅当,R,诱导,。,所以，集合,A,上的等价关系与集合,A,的划分是一一对应的,。,由划分导出等价关系的方法,定理,设,S,=,S,1,，,S,2,，,，,S,m,是,A,的一个划分，,R,=,x,y,|,x,和,y,在同一个划分块中,则,R,是,A,上的等价关系,。,划分,S,导出的等价关系,R,可以表示为：,R,=(,S,1,S,1,)(,S,2,S,2,)(,S,m,S,m,),例,：设,A=,1,2,3,4,，,A,的划分,S,=,1, ,2,3, ,4,，,则从,S,导出的等价关系,R,为：,R,=,1,1,2,2,2,3,3,2,3,3,4,4,=,1,1,2,3,2,3,4,4,可以验证,R,是,A,上的等价关系。,设,A=1,2,3,，求出,A,上所有的等价关系,解：先写出集合,X,上的所有,划分,，它们是：,1,=,2,3,1,2,=,1,3,2,3,=,1,2,3,，,4,=,1,2,3,，,5,=,1,2,3,设,A=1,2,3,，求出,A,上所有的等价关系,对应的等价关系为：,R1,=,2,3,2,3,1,1,=,2,2,2,3,3,2,3,3,1,1,R,2=,1,3,1,3,2,2,=,1,1,1,3,3,1,3,3,2,2,R,3=,1,2,1,2,3,3,=,1,1,1,2,2,1,2,2,3,3,R,4=,1,2,3,1,2,3,=AA=E,A,R,5=,1,1,2,2,3,3,=,1,1,2,2,3,3,=,I,A,1,=,2,3,1,2,=,1,3,2,3,=,1,2,3,，,4,=,1,2,3,，,5,=,1,2,3,由等价关系求划分的实例,例 设,A,=1, 2, 3, 4,，在,A,上定义二元关系,R,：,R,x+y,=,u+v,，,求,R,导出的划分,.,解,：,根据,的,x,+,y,= 2,3,4,5,6,7,8,将,A,A,划分成,7,个等价类：,(,A,A,),/,R,= , , , , , , , , , ,10.7,相容关系和覆盖,定义,对非空集合,A,上的关系,R,，如果,R,是,自反的,和,对称的,，则称,R,为,A,上的,相容关系,。,相容关系的性质,所有等价关系都是相容关系。,相容关系的关系矩阵主对角线全为,1,且是对称阵。,相容关系的关系图每一个结点上都有自回路且每两个结点间如果有边，一定有方向相反的两条边,相容关系举例,设,A,=316,347,204,678,770,A,上的二元关系,R,定义为,R,=,x,y,|,x,A,y,A,x,和,y,有相同数码,，,x,A,， 有,R,，,R,是自反的；,R,， 有,R,， ,R,是对称的。,于是，,R,是相容关系。,令,a,=316,，,b,=347,，,c,=204,，,d,=678,，,e,=770,R,=,a,a,a,b,a,d,b,a,b,b,b,c,b,d,b,e,c,b,c,c,c,e,d,a,d,b,d,d,d,e,e,b,e,c,e,d,e,e,相容类,定义,对非空集合,A,上的相容关系，若,C,A,，对,a,b,C,有,a,b,R,，则称,C,是由相容关系,R,产生的,相容类,。,相容类的性质,相容类,C,A,x,A,，,x,是由相容关系,R,产生的一个相容类。,上例中，,a,a,b,b,c,都是,R,产生的相容类。,a,b,d,、,b,c,e,和,b,d,e,也是,R,产生的相容类。,最大相容类,定义,对非空集合,A,是上的相容关系,R,，一个相容类若不是任何相容类的真子集，就称为,最大相容类,。记为,C,R,。,最大相容类,C,R,的性质：,(,x,)(,y,)(x,C,R,y,C,R,),x,Ry,),C,R,中任意元素,x,与,y,都有相容关系,R,(,x,)(x,A-,C,R,(,y,)(y,C,R,x,Ry,),A,-,C,R,中没有一个元素与,C,R,中,的所有元素都有相容的关系,R,。,最大相容类,最大相容类简化关系图的特点：,最大完全多边形的顶点,构成的集合是最大相容类。,孤立点,构成的集合是最大相容类。,如果一条边不是任何完全多边形的边，则它的两个端点构成的集合是最大相容类,例如右图：,最大完全,3,边形的顶点构成的集合：,2,3,5,和,2,3,4,。,孤立点构成的集合：,6,。,不是任何完全多边形的边的,两个端点构成的集合,1,5,。,。,最大相容类的存在性,定理,10.7.1,设,R,是有限集合,A,上的相容关系，,C,是,R,产生的相容类，那么必存在最大相容类,C,R,，使得,C,C,R,。,证明：,设,A,=,a,1,a,2, ,a,n,，令,C,0,=,C,。,如下构造相容类序列：,C,0,C,1,C,2,C,i+1,=,C,i,a,j,其中：,j,是使,a,j,C,i,且,a,j,与,C,i,的每一个元素都有相容关系,R,的最小下标。,因为,|,A,|=,n,，所以至多经过,n,-|,C,|,步，可结束此过程。,序列的最后一个集合就是要求的最大相容类,C,R,。,作业,12,P190: 24,P190: 27(1),P191: 30,P191: 33,