离散数学课件第四章(第3讲).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,4,关系的运算,关系的复合,定义,：设,（,R,关系），,（,S,关系），,于是可获得：,（,R,S,）,的关系，称,R,S,为,R,和,S,的复合关系，并规定为：,例：设,A=1,2,3,4,5,，,R,S,均为,AA,的关系，且,R=S=,则,R,S=,S,R=,讨论：,（,1,）,R,S,S,R,，,因此,“,”,是不可交换的。,（,2,）,R,S,为新的二元关系，且,R,S,为,X,Z,上的二元关系。,定理,：设,则有：,即,:,关系的复合运算满足结合律,.,定义,给定集合,X,，,R,是,X,中的二元关系，设,于是,R,的,n,次幂,可以定义成：,例：,多个相同的二元关系,R,复合,复合运算的矩阵表示：,设有三个集合：,而,|X|=m,|Y|=n,|Z|=p,，则关系矩阵：,例：设,X=1,2,3,R,S,均是,X,中的二元关系，,R=,S=,0 1 0,0 1 0,1 0 0,M,R,=,0,1 1,0,0 1,1,0 0,M,S,=,（,0,0,）,（,1,0,）,（,0,1,）,=0,0,0,1,0 0 1,0 1 1,M,RS,=,2,逆关系,定义,:,设,X,Y,是二个集合，若,R,是,XY,的关系，从,YX,的关系，称为,R,的逆关系，用,表示，或用,表示。,例：,X=0,1,2,，,R=,=,2,逆关系,讨论定义：,（,1,）只要将,R,中每一个序偶中的元素全部调换位置，就可得到,R,的逆关系。,（,2,）,的关系矩阵为,的转置矩阵；,（,3,）在,R,的关系图中，只要把所有箭头改换方向就可得到,的关系图。（自回路箭头改变与否无关）,定理,设,，则可有：,同样,证明：对于任一,来讲，若有,同理可证,R,一定是对称的,定理,:,设,R,是集合,X,中的二元关系，当且仅当,则,R,才是对称的。,证明：充分性：,R,是对称的,对于任一,必要性：,R,是对称的，,对任一,定理：给定集合,X,Y,，于是可有：,3.,闭包运算,定义,：给定集合,X,，,R,是,X,中的二元关系，若有另一关系,R,满足下列条件：,（,1,）,R,是自反的（对称，可传递的）；,（,2,）,则称,R,是,R,的自反（对称，传递的）闭包，,并依次用,r(R),s(R),t(R),来表示。,4,关系的运算,，则,（,3,）对于任一自反（对称，传递的）关系 ，若,例：设,A=1,2,3,，,R,为,AA,的关系，且,R=,R=,具有自反性质,R=,具有自反性质,R,是包含,R,的具有自反性质的,最小,的二元关系,讨论定义：,（,1,）已知一个集合中的二元关系,R,，则,r(R),s(R),t(R),是包含,R,的具有自反（对称，传递）性质的,最小,的二元关系,它们是,唯一,的；,（,2,）若,R,不是自反（对称，传递）的，则我们可以补上,最少,序偶，使之变为自反、对称、传递关系，从而得到,r(R),s(R),t(R),；,定理,：给定集合,X,，,R,是,X,中的二元关系，于是可有：,（,1,）当且仅当,r(R)=R,，则,R,是自反的；,（,2,）当且仅当,s(R)=R,，则,R,是对称的；,（,3,）当且仅当,t(R)=R,，则,R,是可传递的。,该定理说明：若,R,是自反（对称，传递）的，则,r(R),s(R),t(R),就是,R,本身。,定理,：,R,是,X,中的二元关系,是,X,中的恒等关系，,则有,证明：按定义证：,（,1,）,设,，则,R,是自反的，,（,3,）设有任一包含,R,的二元关系,R,也是自反的，即,则,例：设,X=a,b,c,R=,，求,r(R),解：,r(R)=,定理,：给定集合,X,，,R,是,X,中的二元关系，则有,例：设,X=a,b,c,R=,，求,s(R),s(R)=,定理,：设,X,是一集合，,R,是,X,中的二元关系，则：,例：,X=a,b,c,R=,，,|X|=3,计算,t(R),例：,X=a,b,c,d,R=,计算,t(R),定理,：设,|X|=n,，,R,是,X,中的二元关系，则,例：设,X=a,b,R=,，求,r(R),s(R),t(R),r(R)=,s(R)=,t(R)=R,定理,：设,X,是一集合，,R,是,X,中的二元关系，则有：,r(S(R)=S(r(R),r(t(R)=t(r(R),S(t(R),t(S(R),证明：,r(s(R),r(S(R)=S(r(R),例：设,X=a,b,c,R=,（,1,）,rs(R)=r=,sr(R)=s=,（,2,）,rt(R)=r=,tr(R)=t=,（,3,）,ts(R)=t=,st(R)=S=,