离散数学 第四章 二元关系和函数

*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,4,章 二元关系与函数,4.1,集合的笛卡儿积与二元关系,4.2,关系的运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义和性质,4.7,函数的复合和反函数,1,4.1,集合的笛卡儿积和二元关系,有序对,笛卡儿积及其性质,二元关系的定义,二元关系的表示,2,有序对,定义,由两个客体,x,和,y,，按照一定的顺序组成的,二元组称为,有序对,，记作,实例：点的直角坐标,(3,4),有序对性质,有序性,（当,x,y,时）,与,相等的充分必要条件是,=,x=u,y=v,例,1 =,，求,x,y,.,解,3,y,4=2,x,+5=,y,y,=2,x,=3,3,有序,n,元组,定义,一个,有序,n,(,n,3,),元组,是一个,有序对，其中第一个元素是一个有序,n,-1,元组，即,=,x,n,当,n,=1,时,形式上可以看成有序,1,元组,.,实例,n,维向量是有序,n,元组,.,4,笛卡儿积,定义,设,A,B,为集合，,A,与,B,的,笛卡儿积,记作,A,B,，即,A,B,=|,x,A,y,B,例,2,A,=1,2,3,B,=,a,b,c,A,B,=,B,A,=,A,=,P,(,A,),A,=,5,笛卡儿积的性质,不适合交换律,A,B,B,A,(,A,B,A,B,),不适合结合律,(,A,B,),C,A,(,B,C,)(,A,B,),对于并或交运算满足分配律,A,(,B,C,)=(,A,B,),(,A,C,),(,B,C,),A,=(,B,A,),(,C,A,),A,(,B,C,)=(,A,B,),(,A,C,),(,B,C,),A,=(,B,A,),(,C,A,),若,A,或,B,中有一个为空集，则,A,B,就是空集,.,A,=,B,=,若,|,A,|=,m,|,B,|=,n,则,|,A,B,|=,mn,6,性质的证明,证明,A,(,B,C,)=(,A,B,),(,A,C,),证 任取,A,(,B,C,),x,A,y,B,C,x,A,(,y,B,y,C,),(,x,A,y,B,)(,x,A,y,C,),A,B,A,C,(,A,B,)(,A,C,),所以有,A,(,B,C,)=(,A,B,)(,A,C,).,7,例题,解,(1),任取,A,C,x,A,y,C,x,B,y,D,B,D,例,3 (1),证明,A,=,B,C,=,D,A,C,=,B,D,(2),A,C,=,B,D,是否推出,A,=,B,C,=,D,?,为什么？,(2),不一定,.,反例如下：,A,=1,，,B,=2,C,=,D,=,则,A,C,=,B,D,但是,A,B,.,8,二元关系的定义,定义,如果一个集合满足以下条件之一：,（,1,）集合非空,且它的元素都是有序对,（,2,）集合是空集,则称该集合为一个,二元关系,简称为,关系,，记作,R,.,如,R,可记作,xRy,；如果,R,则记作,x y,实例：,R,=,S,=,a,b,.,R,是二元关系,当,a,b,不是有序对时，,S,不是二元关系,根据上面的记法，可以写,1,R,2,aRb,a c,等,.,9,从,A,到,B,的关系与,A,上,的关系,定义,设,A,B,为集合,A,B,的任何子集所定义的二元,关系叫做,从,A,到,B,的二元关系,当,A,=,B,时则叫做,A,上,的二元关系,.,例,4,A,=0,1,B,=1,2,3,R,1,=,R,2,=,A,B,R,3,=,R,4,=.,那么,R,1,R,2,R,3,R,4,是从,A,到,B,的二元关系,R,3,和,R,4,同时也是,A,上的二元关系,.,计数,|,A,|=,n,|,A,A,|=,n,2,A,A,的子集有 个,.,所以,A,上有,个不同的二元关系,.,例如,|,A,|=3,则,A,上有,=512,个不同的二元关系,.,10,A,上重要关系的实例,设,A,为任意集合，,是,A,上的关系，称为,空关系,E,A,I,A,分别称为,全域关系,与,恒等关系,，定义如下：,E,A,=|,x,A,y,A,=,A,A,I,A,=|,x,A,例如,A,=1,2,则,E,A,=,I,A,=,11,A,上重要关系的实例（续）,小于等于关系,L,A,整除关系,D,A,包含关系,R,定义：,L,A,=|,x,y,A,x,y,A,R,，,R,为实数集合,D,B,=|,x,y,B,x,整除,y,B,Z*,Z*,为非,0,整数集,R,=|,x,y,A,x,y,A,是集合族,.,类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等,.,12,实例,例如,A,=1,2,3,B,=,a,b,则 ,L,A,=,D,A,=,A,=,P,(,B,)=,a,b,a,b,则,A,上的包含关系是,R,=,13,关系的表示,表示方式：关系的集合表达式、关系矩阵、关系图,关系矩阵,：若,A,=,a,1,a,2,a,m,，,B,=,b,1,b,2,b,n,，,R,是从,A,到,B,的关系，,R,的关系矩阵是布尔矩阵,M,R,=,r,ij,m,n,其中,r,ij,=1,R,.,关系图,：若,A,=,x,1,x,2,x,m,，,R,是从,A,上的关系，,R,的关系图是,G,R,=,其中,A,为结点集，,R,为边集,.,如果,属于关系,R,，在图中就有一条从,x,i,到,x,j,的有向边,.,注意：,A,B,为有穷集，关系矩阵适于表示从,A,到,B,的关系或者,A,上的关系，关系图适于表示,A,上的关系,14,实例,A,=1,2,3,4,R,=,R,的关系矩阵,M,R,和关系图,G,R,如下：,15,基本运算定义,定义域、值域、域,逆、合成、限制、像,基本运算的性质,幂运算,定义,求法,性质,4.2,关系的运算,16,关系的基本运算定义,定义域,、,值域,和,域,dom,R,=,x,|,y,(,R,),ran,R,=,y,|,x,(,R,),fld,R,=,dom,R,ran,R,例,1,R,=,则,dom,R,=1,2,4,ran,R,=2,3,4,fld,R,=1,2,3,4,17,关系的基本运算定义（续）,逆,与,合成,R,1,=|,R,R,S,=|,y,(,R,S,),例,2,R,=,S,=,R,1,=,R,S,=,S,R,=,18,合成运算的图示方法,利用图示（不是关系图）方法求合成,R,S,=,S,R,=,19,限制与像,定义,F,在,A,上的,限制,F,A,=|,xFy,x,A,A,在,F,下的,像,F,A,=,ran(,F,A,),实例,R,=,R,1=,R,1=2,4,R,=,R,1,2=2,3,4,注意：,F,A,F,F,A,ran,F,20,关系基本运算的性质,定理,1,设,F,是任意的关系,则,(1),(F,1,),1,=F,(2)dom,F,1,=,ran,F,ran,F,1,=,dom,F,证,(1),任取,由逆的定义有,(,F,1,),1,F,1,F,所以有,(,F,1,),1,=,F,(2),任取,x,x,dom,F,1,y,(,F,1,),y,(,F,),x,ran,F,所以有,dom,F,1,=,ran,F,.,同理可证,ran,F,1,=,dom,F,.,21,定理,2,设,F,G,H,是任意的关系,则,(1)(,F,G,),H,=,F,(,G,H,),(2)(,F,G,),1,=,G,1,F,1,证,(1),任取,(,F,G,),H,t,(,F,G,H,),t,(,s,(,F,G,),H,),t,s,(,F,G,H,),s,(,F,t,(,G,H,),s,(,F,G,H,),F,(,G,H,),所以,(,F,G,),H,=,F,(,G,H,),关系基本运算的性质（续）,22,(2),任取,(,F,G,),1,F,G,t,(,F,(,t,x,),G,),t,(,G,1,(,t,y,),F,1,),G,1,F,1,所以,(,F,G,),1,=,G,1,F,1,关系基本运算的性质（续）,23,A,上关系的幂运算,设,R,为,A,上的关系,n,为自然数,则,R,的,n,次幂,定义为：,(1),R,0,=|,x,A,=,I,A,(2),R,n,+1,=,R,n,R,注意：,对于,A,上的任何关系,R,1,和,R,2,都有,R,1,0,=,R,2,0,=,I,A,对于,A,上的任何关系,R,都有,R,1,=,R,24,幂的求法,对于集合表示的关系,R,，计算,R,n,就是,n,个,R,右复合,.,矩阵表示就是,n,个矩阵相乘,其中相加采用逻辑加,.,例,3,设,A,=,a,b,c,d,R,=,求,R,的各次幂,分别用矩阵和关系图表示,.,解,R,与,R,2,的,关系矩阵,分别为,25,同理，,R,0,=,I,A,R,3,和,R,4,的矩阵分别是：,因此,M,4,=,M,2,即,R,4,=,R,2,.,因此可以得到,R,2,=,R,4,=,R,6,=,R,3,=,R,5,=,R,7,=,幂的求法（续）,26,R,0,R,1,R,2,R,3,的关系图如下图所示,幂的求法（续）,27,幂运算的性质,定理,3,设,A,为,n,元集,R,是,A,上的关系,则存在自然数,s,和,t,使得,R,s,=,R,t,.,证,R,为,A,上的关系,由于,|,A,|=,n,A,上的不同关系只有 个,.,当列出,R,的各次幂,R,0,R,1,R,2,必存在自然数,s,和,t,使得,R,s,=,R,t,.,28,定理,4,设,R,是,A,上的关系,m,n,N,则,(1),R,m,R,n,=,R,m,+,n,(2)(,R,m,),n,=,R,mn,证 用归纳法,(1),对于任意给定的,m,N,施归纳于,n,.,若,n,=0,则有,R,m,R,0,=,R,m,I,A,=,R,m,=,R,m,+0,假设,R,m,R,n,=,R,m,+,n,则有,R,m,R,n,+1,=,R,m,(,R,n,R,)=(,R,m,R,n,),R,=,R,m,+,n,+1,所以对一切,m,n,N,有,R,m,R,n,=,R,m,+,n,.,幂运算的性质（续）,29,(,接上页证明,),(2),对于任意给定的,m,N,施归纳于,n,.,若,n,=0,则有,(,R,m,),0,=,I,A,=,R,0,=,R,m,0,假设,(,R,m,),n,=,R,mn,则有,(,R,m,),n,+1,=(,R,m,),n,R,m,=(,R,mn,),R,m,=,R,mn,+,m,=,R,m,(,n,+1),所以对一切,m,n,N,有,(,R,m,),n,=,R,mn,.,幂运算的性质（续）,30,