资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,An Introduction to Database Systenm,99,离散数学,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.1,迪卡尔乘积与二元关系,定义,4.1,一、有序对,由两个元素,x,和,y,（允许,x=y,）按一定的顺序排列成的二元,组叫做一个有序对或序偶，记作,，其中,x,是它的第一,元素，,y,是它的第二元素。,有序对性质,当,x,y,时，,=,的充分必要条件是,x=u,且,y=v,集合中的元素具有无序性，但是有序对中的元素是有序的。,4.1,迪卡尔乘积与二元关系,例,1,：已知,=,求,x,和,y,解得：,x=3,，,y=-2,根据,有序对的性质,得：,x+2=5,2x+y=4,有序,n,元组,一个有序,n,元组,(n=3),是一个有序对，其中第一个元素是,一个有序,n-1,元组，一个有序,n,元组记作,，即,=,x,n,例如：空间直角坐标系中点的坐标,、,等有序,3,元组。,n,维空间中点的坐标或,n,维向量都是有序,n,元组。,4.1,迪卡尔乘积与二元关系,定义,4.3,二、迪卡尔乘积,设,A,，,B,为集合，用,A,中元素为第一元素，,B,中元素为第二,元素构成有序对。所有这样的有序对组成的集合叫做,A,和,B,的迪卡尔乘积，记作,AB,。符号化表示为：,AB=|,x,A,yB,4.1,迪卡尔乘积与二元关系,迪卡尔乘积的性质,如果,|A|=,m,|B,|=n,，则,|AB|=,mn,对任意集合,A,，根据定义有：,A,=,，,A=,一般地说，迪卡尔乘积运算不满足交换律，即：,ABBA(,当,A B AB,时,),迪卡尔乘积运算不满足结合律，即：,（,AB,）,CA,（,BC,）（当,A B C,）,4.1,迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(1)A,（,BC,）,= (AB)(AC,）,证明： 对于任意的,A,（,BC,）,xA,yBC,xA, (,yB, y C),(,xAyB)(xAyC,),AB AC,(AB)(AC),4.1,迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(2),（,BC,）,A= (BA)(CA,）,证明： 对于任意的,（,BC,）,A,xBC,yA,(,xB, x C) ,yA,(,xB,yA)(xC,yA,), BA CA,(BA)(CA),4.1,迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(3)A,（,BC,）,= (AB)(AC,）,证明： 对于任意的,A,（,BC,）,xA,yBC,xA, (,yB, y C),(,xAyB,) (,xAyC,),AB AC,(AB)(AC),4.1,迪卡尔乘积与二元关系,迪卡尔乘积运算对并和交运算满足分配律，即：,(4),（,BC,）,A= (BA)(CA,）,证明： 对于任意的,（,BC,）,A,xBC,yA,(,xB, x C) ,yA,(,xB,yA)(xC,yA,), BA CA,(BA)(CA),4.1,迪卡尔乘积与二元关系,A,C BD AB CD,证明： 对于任意的,AB,xA, y B,xC, y D,xCD,所以：,AB CD,4.1,迪卡尔乘积与二元关系,n,阶迪卡尔乘积（定义,4.4,）,设,A,1,，,A,2,，,，,A,n,是集合,(n=2),，它们的,n,阶迪卡尔乘积记作,A,1,A,2,A,n,，其中：,A,1,A,2,A,n,=|x,1,A,1, x,2,A,2,x,n,A,n,4.1,迪卡尔乘积与二元关系,例,2,：设,A=1,2,，求,P(A)A,解：,P(A)=,1,2,1,2,P(A)A=,4.1,迪卡尔乘积与二元关系,例,3,：设,A,B,C,D,为任意集合，判断以下等式是否成立？,（,1,）,(A,B),(C,D)=,(A,C)(BD,),证明： 对于任意的,(A,B),(C,D),x,A,B,y,C,D,xA,xB,yC,yD,(,xA,yC)(xB,yD,),AC BD,(AC)(BD),4.1,迪卡尔乘积与二元关系,（,2,）,(A,B),(C,D)=,(A,C)(BD,),证明：设,A=,、,B=1,、,C=2,、,D=3,(A,B),(C,D)=,、,(A,C)(BD,)=,、,所以：等式不成立,（,3,）,(A,-B),(C,-D)=,(A,C)-(BD,),证明：设,A=1,、,B=1,、,C=2,、,D=3,(A,-B),(C,-D)= ,(A,C)-(BD,)=,所以：等式不成立,4.1,迪卡尔乘积与二元关系,（,4,）,(A,B),(C,D)=,(A,C)(BD,),证明：设,A=1,、,B=1,、,C=2,、,D=3,(A,B),(C,D)= ,(A,C)(BD,)=,所以：等式不成立,4.1,迪卡尔乘积与二元关系,例,4,：设,A,B,C,D,为任意集合，判断真假。,（,1,）,AB=AC,B=C,证明：若,A=,，,B=1,，,C=2,则,AB=AC=,，而,BC,。,所以：命题真假不定,4.1,迪卡尔乘积与二元关系,（,2,）,A-(BC)=(AB)-(AC),证明：若,A=0,，,B=1,，,C=2,则,A-(BC),=0,(AB)-(AC)=,所以：命题真假不定,4.1,迪卡尔乘积与二元关系,（,3,）,A=B, C=D,(AC)=(BD),证明：对任意,AC,x,A,yC,x,B,yD,x,所以：命题真值为,1,4.1,迪卡尔乘积与二元关系,（,4,）存在集合,A,，使得,A,AA,证明：令,A=,则,AA=,所以：,A,AA,该命题真值为,1,4.1,迪卡尔乘积与二元关系,定义,4.5,三、二元关系,如果一个集合满足以下条件之一：,集合非空，且它的元素都是有序对,集合是空集,则称这样的集合为二元关系，记作,R,。二元关系也可以简,称为关系。对于二元关系,R,，如果,R,，可记作,xRy,。,例：,R1=,，,R2=,a,b,则,R1,为二元关系；,R2,不是二元关系，仅仅是一个集合。,4.1,迪卡尔乘积与二元关系,集合上元素的关系（定义,4.6,）,三、二元关系,设,A,，,B,为集合，,AB,的任何子集所定义的二元关系叫做,从,A,到,B,的二元关系，特别当,A=B,是则叫做,A,上的二元关系。,例：,A=0,1,、,B=1,2,3,，,那么,R1=,，,R2=AB,，,R3=,，,R4=,等都是,A,到,B,的二元关系。,R3,和,R4,是,A,上的二元关系。,集合,A,上的二元关系的数目依赖于,A,中的元素数：设,|A|=n,，则,|AA|=,。,AA,的子集有 个。每个子集代表一个,A,上的二元关系，所以,A,上的二元关系数目为： 。,4.1,迪卡尔乘积与二元关系,全域关系与恒等关系,例：,A=0,1,A,上的全域关系为：,.,A,上的恒等关系为：,.,对于任意集合,A,，定义：,E,A,=|,x,A,yA,=AA,I,A,=|,x,A,L,A,=|,x,y,A, x=y,这里,A,R,D,A,=|,x,y,A, x,整除,y, ,这里,A,4.1,迪卡尔乘积与二元关系,例：,A=4,0.5,-1,B=1,2,3,6,，则,L,A,=,L,B,=,4.1,迪卡尔乘积与二元关系,例,5,：设,A=,a,b,，,R,是,P(A),上的包含关系，,R=|,x,y,P(A)xy,解：,P(A)=,a,b,a,b,R=,4.1,迪卡尔乘积与二元关系,关系的表示方法,集合表达式：,例,6,：设,A=1,2,3,4,，下面各式定义的,R,都是,A,上的,关系，试用列元素法表示,R,R1=|x,是,y,的倍数,R2=|(,x-y)(x-y),A,R3=|,x/y,是素数,R4=|,x,y,4.1,迪卡尔乘积与二元关系,关系的表示方法,关系矩阵：,设,A=x1,x2,xn,，,R,是,A,上的关系，令,则,是,R,的关系矩阵，记作,M,R,。,4.1,迪卡尔乘积与二元关系,关系的表示方法,关系图：,设,A=x1,x2,xn,，,R,是,A,上的关系，令图,G=,，,其中顶点集合,V=A,，边集为,E,。对于,x,i,，,x,j,V,，满足,Ex,i,Rx,j,称图,G,为,R,的关系图，记作,G,R,。,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.2,关系的运算,关系的定义域、值域、域（定义,4.8,）,一、关系的基本运算,设,R,是二元关系。,R,中所有有序对的第一元素构成的集合称为,R,的定义,域，记作,domR,，形式化表示为：,domR,=,x|,y,(R),R,中所有有序对的第二元素构成的集合称为,R,的值,域，记作,ranR,，形式化表示为：,ranR,=,y|,x,(R),4.2,关系的运算,R,的定义域和值域的并集称为,R,的域，记作,fldR,，形式化,表示为：,fldR,=,domR,ranR,例,1,：设,R=,，则,domR,=1,2,4,ranR,=2,3,4,fldR,=1,2,3,4,4.2,关系的运算,例,2,：下列关系都是整数集,Z,上的关系，分别求出它们的,定义域和值域。,(1)R1=|,x,y,Z, x=y,(2)R2=|,x,y,Z, x*,x+y,*y=1,(3)R3=|,x,y,Z, y=2x,(4)R4=|,x,y,Z, |x|=|y|=3,4.2,关系的运算,关系的逆运算（定义,4.9,）,设,R,为二元关系，,R,的逆关系，简称,R,的逆，记作 ，其中,关系的合成运算（定义,4.9,）,设,F,，,G,为二元关系，,F,和,G,的合成记作,F,G,，其中,F,G=|,z(xGz,zFy,),4.2,关系的运算,例,3,：设,F=,，,G=,，则,F,G=,=,G,F=,例,4,：设,F=|,x,y,N, y=x*x,，,G=|,x,y,N, y=x+1,，,求,4.2,关系的运算,限制与像（定义,4.9,）,设,F,为二元关系，,A,是集合,F,在,A,上的限制记作,F A,，其中,F A=|,xFy,xA,A,在,F,上的象记作,FA,，其中,FA=,ran(F,A),F,在,A,上的限制,F A,是,F,的子关系，而,A,在,F,下的像,FA,是,ranF,的子集。,4.2,关系的运算,例,5,：设,R=,则,R1=2,3,R 1=,R,=,R 2,3=,R,=,R2,3=2,4,4.2,关系的运算,关系的运算的顺序,关系运算中的逆运算优先于其他运算；,所有的关系运算都优先于集合运算；,没有规定优先权的运算以括号决定运算顺序。,4.2,关系的运算,定理,4.1,二、关系基本运算的性质,设,F,G,H,是任意的关系，则,=F,dom,=,ranF,ran,=,domF,(F,G),H =F,(GH),(F,G) =G, F,4.2,关系的运算,定理,设,R,为,A,上的关系，则,R,I,A,=I,A,R=R,定理,4.2,F,(GH)=,F,G FH,(GH)F=G,F, HF,F,(GH),F,G FH,(GH)F,G,F HF,4.2,关系的运算,定义,4.10,三、关系的,n,次幂,设,R,为,A,上的关系，,n,为自然数，则,R,的,n,次幂定义为：,=|,x,A,=I,A,注,：,(1),。,(2),。,4.2,关系的运算,例,6,：设,A=,a,b,c,d,R,=,求,=I,A,=,=,=,=,=,=,4.2,关系的运算,定理,4.3,设,R,为,A,上的关系，,m,n,N,，则,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.3,关系的性质,自反性、反自反性,一、关系的性质,设,R,是,A,上的关系，,若,x(xA, R),，则称,R,在,A,上是自反的。,若,x(xA, R),，则称,R,在,A,上是反自反的。,A,上的全域关系,E,A,、恒等关系,I,A,、都是,A,上的自反关系。,小于等于关系,L,A,、整除关系,D,B,分别为,A,和,B,上的自反关系。,小于关系、真包含关系是给定集合或集合族上的反自反关系。,4.3,关系的性质,例,8,：设,A=1,2,3,，,R1,，,R2,和,R3,是,A,上的关系，其中,R1=,R2=,R3=,说明,R1,，,R2,和,R3,是否为,A,上的自反关系和反自反关系。,R3,是,A,上的反自反关系，,R2,是,A,上的自反关系。,1,2,3,4.3,关系的性质,对称性、反对称性,设,R,是,A,上的关系，,若,xy(x,yA, R R),，,则称,R,为,A,上对称的关系。,若,xy(x,yA, R R x=y),，,则称,R,为,A,上反对称的关系。,A,上的全域关系,E,A,、恒等关系,I,A,、空关系都是,A,上的对称关系。,恒等关系,I,A,、空关系也是,A,上的反对称关系。,4.3,关系的性质,例,9,：设,A=1,2,3,，,R1,，,R2,和,R3,是,A,上的关系，其中,R1=,R2=,R3=,R4=,说明,R1,，,R2,，,R3,和,R4,是否为,A,上的对称关系和反对称关系。,1,2,3,1,2,3,1,2,3,1,2,3,4.3,关系的性质,传递性,设,R,是,A,上的关系，若,xyz(x,y,zA, R R R),，,则称,R,为,A,上传递的关系。,A,上的全域关系,E,A,、恒等关系,I,A,、空关系都是,A,上的传递关系。,小于或等于,L,A,、整除关系和包含关系也是相应集合上的的传递关系。,小于关系、真包含关系也是相应集合上的的传递关系。,4.3,关系的性质,例,10,：设,A=1,2,3,，,R1,，,R2,和,R3,是,A,上的关系，其中,R1=,R2=,R3=,说明,R1,，,R2,，,R3,和,R4,是否为,A,上的传递关系。,1,2,3,1,2,3,1,2,3,4.3,关系的性质,定理,二、关系性质的相关定理,设,R,是,A,上的关系，则,R,在,A,上的自反当且仅当,I,A,R,。,R,在,A,上的反自反当且仅当,RI,A,=,。,R,在,A,上的对称当且仅当 。,R,在,A,上的反对称当且仅当 。,R,在,A,上的传递当且仅当 。,4.3,关系的性质,例,11,：设,A,是集合，,R1,和,R2,是,A,上的关系，证明：,(1),若,R1,，,R2,是自反的和对称的，则,R1,R2,也是自反的和对称的。,证明：（,1,）,4.3,关系的性质,例,11,：设,A,是集合，,R1,和,R2,是,A,上的关系，证明：,(2),若,R1,和,R2,是传递的，则,R1R2,也是传递的。,证明：（,2,）,4.3,关系的性质,五种性质在关系矩阵和关系图中的特点,性质,表示,自反性,反自反性,对称性,反对称性,传递性,集合表达式,I,A,R,R,I,A,关系矩阵,主对角线元素全是,1,主对角线元素全是,0,矩阵是对称矩阵,若,r,ij,=1,，且,i,j,，则,r,ij,=0,对,M,M,中,1,所在的位置，,M,中相应位置都是,1,关系图,每个顶点都是环,每个顶点都没有环,如果两个顶点之间有边，一定是一对方向相反的边,如果两个顶点之间有边，一定是一条有向边,如果顶点,x,i,到,x,j,有边，,x,j,到,x,k,有边，则从,x,i,到,x,k,也有边,4.3,关系的性质,关系运算与关系性质,原有性质,运算,自反性,反自反性,对称性,反对称性,传递性,R,1,R,2,R,1,R,2,R,1,R,2,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.4,关系的闭包,一、关系闭包的定义,设,R,是非空集合,A,上的关系，,R,的自反（对称或传递）闭包,是,A,上的关系,R,，使得,R,满足以下条件：,（,1,）,R,是自反的（对称或传递的）,（,2,）,R,R,（,3,）对,A,上的任何包含,R,的自反（对称或传递）关系,R,有,R,R,一般将,R,的自反闭包记作,r(R,),对称闭包记作,s(R,),传递闭包记作,t(R,).,4.4,关系的闭包,例,1,：设,A=,a,b,c,d,，,R=,则,R,关系图如下图，则如何求,A,上关系,R,的闭包？,a,b,c,d,4.4,关系的闭包,设,R,为非空集合,A,上的二元关系，则有,二、关系闭包的求法（关系运算方法）,；,；,。,4.4,关系的闭包,例,2,：设,A=,a,b,c,d,，,R=,则,R,和,r(R),s(R),t(R,),的关系图如下图，则如何求,A,上关系,R,的闭包？,a,b,c,d,r(R,)=,I,A,=,s(R,)=,=,t(R,)=,=,4.4,关系的闭包,设,R,为非空集合,A,上的二元关系，则有,三、关系闭包的求法（矩阵运算方法）,M,r,=M+E,；,M,s,=M+M,；,。,4.4,关系的闭包,三、关系闭包的性质（,1,）,R,是自反的当且仅当,r(R,)=R,；,R,是对称的当且仅当,s(R,)=R;,R,是传递的当且仅当,t(R,)=R;,设,R,是非空集合,A,上的关系，则,4.4,关系的闭包,三、关系闭包的性质（,2,）,r(R1), r(,R2),；,s(R1), s(,R2);,t(R1), t(,R2),;,设,R1,和,R2,是非空集合,A,上的关系，且,R1,R2,，则,4.4,关系的闭包,三、关系闭包的性质,(3),；,；,。,设,R,是非空集合,A,上的关系，则,4.4,关系的闭包,三、关系闭包的性质,(4),r(s(R,)=,s(r(R,),。,r(t(R,)=,t(r(R,),。,s(t(R)t(s(R,),。,设,R,是非空集合,A,上的关系，则,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.5,等价关系与偏序关系,一、等价关系的定义,设,R,为非空集合,A,上的关系，如果,R,是自反的、对称的、,传递的，则称,R,为,A,上的等价关系。对任何,x,y,A,，如果,等价关系,R,，则记作,xy,。,4.5,等价关系与偏序关系,例,4,：,A=1,2,3,8,R=|,x,y,A,xy(mod,3),其中,xy(mod,3),的含义就是,x-y,可以被,3,整除。求证：,R,是否为等价关系？,5,8,2,4,7,1,6,3,对任何正整数,n,可以定义整数集合,Z,上模,n,的等价关系：,R=|,x,yZ,xy(mod,n),4.5,等价关系与偏序关系,例,5,:,在一群人的集合上，年龄相等的关系、朋友关系。,动物是按种属分类的，,“,具有相同种属,”,的关系。,集合上的恒等关系。,在同一平面上，三角形之间的相似关系。,在同一平面上，直线间的平行关系。,4.5,等价关系与偏序关系,二、等价类的定义,设,R,是非空集合,A,上的等价关系，对任意的,x,A,，令,x,R,=,y|yA,xRy,则称,x,R,为,x,关于,R,的等价类，简称为,x,的等价类，简记为,x,。,集合,A=1,2,3,8,R=|,x,y,A,xy(mod,3),中的,等价类有：,1=4=7=1,4,7,2=5=8=2,5,8,3=6=3,6,4.5,等价关系与偏序关系,三、等价关系、等价类的性质,x,，且,xA,;,若,xRy,，则,x=y;,若,R,，则,xy,=;,;,4.5,等价关系与偏序关系,四、商集的定义,设,R,是非空集合,A,上的等价关系，以,R,的不交的等价类为元素的,集合叫做,A,在,R,下的商集，记作,A/R,，即,A/R=,x,R,|xA,。,集合,A=1,2,3,8,R=|,x,y,A,xy(mod,3),，则,A,在,R,下的商集是：,A/R=,1,4,7,，,2,5,8,，,3,6,4.5,等价关系与偏序关系,例,6,:,非空集合,A,上的全域关系,E,A,是,A,上的等价关系，对任意,x,A,有,x= ,商集,A/,E,A,=,非空集合,A,上的恒等关系,I,A,是,A,上的等价关系，对任意,x,A,有,x= ,商集,A/,E,A,=,。,4.5,等价关系与偏序关系,五、划分的定义,设,A,是非空集合，如果存在一个,A,的子集族,(P(A),满足以下,条件：,，,中任意两个元素不交，,中所有元素的并集等于,A,，,则称为,A,的一个划分，且称中的元素为划分块。,4.5,等价关系与偏序关系,例,7,:,考虑集合,A=,a,b,c,d,的下列子集族，哪些是,A,的划分,a,b,c,d,a,b,c,d,a,b,c,a,d,a,b,c,d,a,b,c,集合,A,上的等价关系与集合,A,的划分是一一对应的。,4.5,等价关系与偏序关系,例,8,:,设,A=1,2,3,，求出,A,上所有的等价关系。,2,3,1,R1,2,3,1,R2,2,3,1,R3,2,3,1,R4,2,3,1,R5,R1=,=E,A,R2=,R3=,R4=,R5=,=I,A,4.5,等价关系与偏序关系,五、偏序关系的定义,设,R,为非空集合,A,上的关系，如果,R,是自反的、反对称的和传递,的，则称,R,为,A,上的偏序关系，简称偏序，记作 。,例如：集合,A=1,2,3 ,R=,则,关系,R,是偏序关系。,整数集合上的小于等于关系为偏序关系；,集合幂集上的子集关系为偏序关系。,4.5,等价关系与偏序关系,六、可比和盖住的定义,设,为偏序集，对于任意,x,y,A,，如果,x y,或者,y x,成立,则称,x,与,y,是,可比,的，如果,xy(,即,x y,xy,),，且不存在,z,A,使得,xzy,，则称,y,盖住,x,。,例如：集合,A=1,2,3,4,5 ,是整除关系。那么，对于任意,xA,都有,1 x,，所以,1,和,1,，,2,，,3,，,4,，,5,都是可比的。但,2,和,3,不可比。又,12,，且,24,所以,4,不能盖住,1,。,4.5,等价关系与偏序关系,七、全序关系的定义,设,为偏序集，对于任意,x,y,A,，,x,和,y,都可比，则称,为,A,上的全序关系，且称,为全序集。,例如：集合,A=1,2,3,4,5,上的小于等于关系为全序关系，而整除 关系不是全序关系。,4.5,等价关系与偏序关系,八、最小元、最大元、极小元和极大元,设,为偏序集，,B,A.,若,y,B,，使得,x(xB,yx,),成立，则称,y,为,B,的最小元。,若,yB,，,使得,x(xB,xy,),成立，则称,y,为,B,的最大元。,若,yB,，,使得,x(xB,xy,),成立，则称,y,为,B,的极小元。,若,yB,，,使得,x(x,B ,yx,),成立，则称,y,为,B,的极大元。,4.5,等价关系与偏序关系,例,9,:,设偏序集,，求,A,的极小元，最小元，极大元，最大元,a,b,c,g,h,d,e,f,4.5,等价关系与偏序关系,九、上界、下界、上确界和下确界,设,为偏序集，,B,A.,若,yA,，,使得,x(xB,xy,),成立，则称,y,为,B,的上界。,若,yA,，,使得,x(xB,yx,),成立，则称,y,为,B,的下界。,若,C=,y|y,为,B,的上界,，则称,C,的最小元为,B,的最小上界或上确界。,若,D=,y|y,为,B,的下界,，则称,D,的最大元为,B,的最大下界或下确界。,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.6,函数的定义与性质,一、函数的定义（定义,4.22,）,设,F,为二元关系，若对任意的,x,domF,都存在唯一的,yranF,使得,xFy,成立，则称,F,为函数。,例,1,：设,F,1,=,F,2,=,判断他们是否为函数。,4.6,函数的定义与性质,二、集合,A,到,B,的函数（定义,4.23,）,设,A,，,B,为集合，如果函数,f,满足以下条件,（,1,）,domf,=A,（,2,）,ranf,B,则称,f,是从,A,到,B,的函数,，记作,f:A,-B,。,例如：,f:N,-N,，,f(x,)=2x,g:N,-N,，,g(x,)=2,4.6,函数的定义与性质,三、集合,A,到,B,的函数（定义,4.24,）,所有从,A,到,B,的函数的集合记作,B,A,，读作,“,B,上,A,”,。符号化,表示为,B,A,f|f:A,-B,4.6,函数的定义与性质,f,0,=,例,2,：设,A=1,2,3,B=,a,b,求,=f,0,f,1,f,7,，其中：,f,1,=,f,2,=,f,3,=,f,4,=,f,5,=,f,6,=,f,7,=,根据排列组合得知：,|A|=,m,|B,|=n,|B,A,|=n,m,4.6,函数的定义与性质,设函数,f:A,B,，,A,A,，,四、函数的像（定义,4.25,）,令,f(A,)=,f(x)|x,A,，称,f(A,),为,A,在,f,下的,像,。,特别地，当,A,=A,时称,f(A,)=,f(A,)=,ranf,为,函数的像,。,x,A,f(x,),与,f(A,),的区别？,4.6,函数的定义与性质,例,3,：设,f,：,N,N,，且,令,A=0,1,B=2,那么有：,f(A,)=f(0,1)=f(0),f(1)=0,2,4.6,函数的定义与性质,五、满射、单射和双射的定义（定义,4.26,）,若,ranf,=B,，则称,f:A,B,是,满射,的。,若,对于任意,x,1,x,2,A,x,1,x,2,都有,f(x,1,),f(x,2,),则,f,是,单射,的。,若,f,既是满射又是单射的，则称,f,是,双射,的。,设,f:A,B,，,4.6,函数的定义与性质,例,4,：,A=1,2,3,4,5,，,B=6,7,8,9,10,判断下列函数是否为单射、满射、双射的。为什么？,(1)f=,(2)f=,(3)f=,4.6,函数的定义与性质,六、几个特殊的函数,（,1,）设,f:A,B,，如果存在,c,B,使得对所有的,xA,都有,f(x,)=c,，则称,f:AB,是,常函数,。,（,2,）称,A,上的恒等关系,I,A,为,A,上的,恒等函数,。对所有的,x,A,都有,I(,x,)=x,。,（,3,）设,f:,RR,如果对任意的,x1,x2R,x1x2,就有,f(x1)f(x2),，则称,f,为单调递增的；如果对任意的,x1,x2A,x1x2,就有,f(x1)f(x2),，则称,f,为严格单调递增的。,4.6,函数的定义与性质,六、几个特殊的函数,（,5,）设,R,是,A,上的等价关系，令,g:A,A/R,g(a,)=,a,aA,称,g,是从,A,到商集,A/R,的,自然映射,。,（,4,）设,A,为集合，对于任意的,A,A,，,A,的,特征函数,A,:A,0,1,，定义为,4.6,函数的定义与性质,例,6,：,A=1,2,3,，,R=,I,A,g,为自然映射。,g(1)=g(2)=1,2,g(3)=3,第四章,二元关系和函数,4.1,迪卡尔乘积与二元关系,4.2,二元运算,4.3,关系的性质,4.4,关系的闭包,4.5,等价关系和偏序关系,4.6,函数的定义与性质,4.7,函数的复合与反函数,4.7,函数的复合与反函数,一、函数的复合定理（定理,4.6,）,dom(F,G,)=,x|x,domG,G(x)domF,；,x,dom(F,G,),有,F,G(x,)=,F(G(x,),；,设,F,G,是函数，则,F,G,也是函数，且满足,4.7,函数的复合与反函数,二、函数复合的结合律（推论）,设,f:A,B,g:B,C,则,f,g,：,A,C,，且,xA,都有,f,g(x,)=,f(g(x,),。,4.7,函数的复合与反函数,三、函数复合的性质（定理,4.7,）,设,f:B,C,g:A,B,。,(1),如果,f,，,g,都是满射的,，则,f,g:,A,C,也是满射的。,(2),如果,f,，,g,都是单射的,，则,f,g:,A,C,也是单射的。,(3),如果,f,，,g,都是双射的,，则,f,g:,A,C,也是双射的。,4.7,函数的复合与反函数,四、反函数（定理,4.8,）,设,f:A,B,是双射的，则有 是函数，并且是双射函数。,五、反函数的性质,设,f:A,B,是双射的，则有,f,-1,f=I,A,f,f,-1,=I,B,4.7,函数的复合与反函数,例,7,：设,求,f, g,，,g f,。如果,f,和,g,存在反函数，求出它们的反函数。,
展开阅读全文