计算机数学基础.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,清华大学现代远程教育,*,专升本课程,*,单击此处编辑母版标题样式,清华大学现代远程教育,*,专升本课程,计算机数学基础,集合代数,关系与函数,清华大学现代远程教育,*,专升本课程,函数,函数,-,单值的二元关系,设,F,为二元关系，如果,x,dom,F,，,!,y,ran F,，使得,x,F,y,成立，则称,F,为函数。,如果,F,，则记,F(,x,)=,y,，并称,y,是,F,的函数值。,!,=,存在唯一的,清华大学现代远程教育,*,专升本课程,函数,设,A,、,B,是集合，如果函数,f,满足以下条件：,a)dom,f,A,b)ran,f,B,则称,f,是从,A,到,B,的偏函数，记为,f,：,A+B,。,其中,A,是,f,的前域，,B,是陪域。,清华大学现代远程教育,*,专升本课程,函数,设,A,、,B,是集合，如果函数,f,满足以下条件：,a)dom,f,=A,b)ran,f,B,则称是从,A,到,B,的全函数，简称从,A,到,B,的函数。,记为,f,：,AB,。,清华大学现代远程教育,*,专升本课程,函数,显然一个从,A,到,B,的函数，是满足下列性质的二元关系：,(1),每个元素,xA,，都必须有一个,yA,与之成为二元关系中一个元素,即函数的定义域就是,A,本身，而不是,A,的一个真子集。,清华大学现代远程教育,*,专升本课程,函数,(2),任何一个,xA,，都只能有唯一一个,yA,与之成为二元关系中一个元素，,即,f,f,y=z,(3),如果任何一个,yA,，都只有唯一一个,xA,与之成为二元关系中一个元素，则函数称为单根的。,清华大学现代远程教育,*,专升本课程,函数,对一个从,A,到,B,的函数来说，其值域可能是,B,的真子集。,如下术语都是函数的同义词，在不同的场合可交替使用：,“变换”,“映射”,“对应”,“运算”,清华大学现代远程教育,*,专升本课程,函数,将所有从,A,到,B,的函数构成的集合记为,B,A,B,A,=,f,|,f,：,AB,如果,A,、,B,分别为,n,、,m,元集合，则,B,A,的元素个数为,m,n,。,如果,A,、,B,至少有一个是,，而从,A,到,B,的函数存在，则,=B,=,不存在从,A,到,的函数。,清华大学现代远程教育,*,专升本课程,函数性质,设函数,f,：,AB,，,(1),若,ran,f,=B,，则称,f,是满射的；,(2),若对任意的,y,ran,f,，只存在唯一的,x,使得,f,(x)=y,，则称,f,是单射的，或一对一的；,(3),若,f,既是满射的，又是单射的，则称,f,是双射的，或一一对应的。,清华大学现代远程教育,*,专升本课程,函数性质,为使得从,A,到,B,的函数具有某种性质，,A,、,B,的元素个数需要满足一定的条件。,对于有限集合，我们有,1)|A|B|,，从,A,到,B,才能存在单射函数,2)|A|B|,，从,A,到,B,才能存在满射函数,3)|A|=|B|,，从,A,到,B,才能存在双射函数,清华大学现代远程教育,*,专升本课程,函数性质,其中,1),也称为鸽巢原理（抽屉原则），其通俗说法是,如果,m,只鸽子（物体）放入,n,个鸽巢（盒子）里，且,m,n,则某个鸽巢（盒子）里一定有两个或更多的鸽子（物体）。,清华大学现代远程教育,*,专升本课程,函数性质,例,某校某个班有,49,人，其中年龄最大的是,20,岁，最小的,17,岁，,则其中必有两个学生是同年同月生。,清华大学现代远程教育,*,专升本课程,常见的函数,常数函数：,f,：,AB,，,如果存在,y B,，使得所有的,x A,都有,f,(x)=y,，则,f,称为常数（常值）函数,恒等函数：,A,上的恒等关系,I,A,称为恒等函数，它是双射的。,清华大学现代远程教育,*,专升本课程,常见的函数,单调增加函数：,f,：,R,R,称为,单调增加：,如果对于任意的,x,1,、,x,2,，如果,x,1,x,2,，,则,f,(x,1,),f,(x,2,),严格单调增加,如果对于任意的,x,1,、,x,2,，如果,x,1,x,2,，,则,f,(x,1,),f,(x,2,),清华大学现代远程教育,*,专升本课程,常见的函数,单调递减函数：,f,：,R,R,称为,单调递减：,如果对于任意的,x,1,、,x,2,，如果,x,1,x,2,，,则,f,(x,1,),f,(x,2,),；,严格单调递减：,如果对于任意的,x,1,、,x,2,，如果,x,1,f,(x,2,),；,清华大学现代远程教育,*,专升本课程,函数的合成,函数是关系的特例，因此函数也有合成的概念。,设,f,：,X,Y,和,g,：,Y,Z,是两个函数，则合成关系,f,g,是,f,和,g,的合成函数,清华大学现代远程教育,*,专升本课程,函数的合成,1)dom(,f,g,),=,x,|,x,dom,f,f,(,x,)dom,g,因为,i,）,dom(,f,g,)dom,f,；,Ii,）,ran,f,dom,g,，否则,f,g,是空函数。,清华大学现代远程教育,*,专升本课程,函数的合成,2)x dom,(,f,g,),有,f,g,(x)=,g,(,f,(x,),。,设,f,：,X,Y,和,g,：,Y,Z,则有,f,g,：,X,Z,，,且,x,X,，有,f,g,(x,)=,g,(,f,(x,),；,清华大学现代远程教育,*,专升本课程,函数的合成,函数的合成满足结合律,(,f,g,),h,=,f,(,g,h,),函数的幂定义,:,i,）,(1),f,0,(x)=I(x),(2),f,n+1,(x)=,f,(,f,n,(x,),Ii,）,如果,f,2,=,f,，则称,f,是等幂函数。,清华大学现代远程教育,*,专升本课程,函数合成的性质,设,f,：,X,Y,和,g,：,Y,Z,，,(1),如果,f,、,g,是满射(单射、双射)函数，则,f,g,是满射(单射、双射)函数,(2a)如果,f,g,是满射函数，则,g,是满射函数,(2b)如果,f,g,是单射函数，则,f,是单射函数,清华大学现代远程教育,*,专升本课程,函数合成的性质,设,f,：,X,Y,和,g,：,Y,Z,，,(2c)如果,f,g,是双射函数，则,f,是单射函数，,g,是满射函数,与恒等函数的合成,设,f,：XY,，则,f,=I,X,f,=,f,I,Y,清华大学现代远程教育,*,专升本课程,逆关系与函数,不能直接用逆关系来定义反函数。因为关系是函数，逆关系不一定是函数。,1),逆关系,F,-1,是函数,关系,F,是单根的；,关系,f,是函数,逆关系,f,-1,是单根的；,因此，逆关系,F,-1,是函数，并没有限定,F,是函数，而只是说明关系,F,是单根的，所以如果,F,是函数，则,F,一定是单射函数。,清华大学现代远程教育,*,专升本课程,逆关系与函数,2),如果,f,：,X,Y,是单射函数，,则逆关系,f,-1,是函数，,且,x dom,F,=,X,，,有,f,-1,(f(x,)=x,，,y ran,f,，有,f,(,f,-1,(y)=y,注意,f,-1,不一定是从,Y,到,X,的函数。,清华大学现代远程教育,*,专升本课程,反函数,如果函数,f,是双射函数，则,f,的逆关系是,f,的反函数，记为,f,1,。,如果函数,f,存在反函数,f,1,，则称,f,是可逆的,(1),仅当函数,f,是双射,的,，,才定义反函数,(2),f,：,X,Y,，则,f,1,：,Y,X,，也是双射的,(3),函数,f,：XY,是双射,的,，则,反函数,f,1,：YX，也是双射的,清华大学现代远程教育,*,专升本课程,反函数,(4),如果函数,f,：XY,的逆关系,f,1,是从Y 到X,的函数，则,f,是双射的,(5),如果函数,f,：XY，是可逆的，则,f,f,1,=,I,X,，,f,1,f,=I,Y,(6),设函数,f,：XY，,g,：YX，,g,=,f,1,当且仅当,f,g,=,I,X,，,g,f,=I,Y,清华大学现代远程教育,*,专升本课程,反函数,左逆和右逆,对于函数,f,：,X,Y,，如果存在,g,：,Y,Z,1),使得,g,f,=,I,Y,，则称,g,是,f,的左逆,2),使得,f,g,=,I,X,，则称,g,是,f,的右逆,左逆和右逆可能没有，也可能有多个,清华大学现代远程教育,*,专升本课程,反函数,设函数,f,：,X,Y,，X,，则,f,有一个右逆,f,是单射的,；,f,有一个左逆,f,是满射的,；,f,有一个左逆且有一个右逆,f,是双射的,左逆与右逆相等,清华大学现代远程教育,*,专升本课程,特殊函数,特征函数,：,设全集为U，对于任意的A U,A,的特征函数,A,：A,0,1定义为,清华大学现代远程教育,*,专升本课程,函数表示,为了,描述,特征函数的性质，首先规定如下的函数表示方法,设X 是任意集合，Y,R，f,和g,都是从X 到Y的函数，则,(1),fg,表示,对于每个xX，都有f(x,),g(x,),(2)f+g,表示,对于每个xX，都有(f+g)(x,)=,f(x)+g(x,),清华大学现代远程教育,*,专升本课程,函数表示,(3)fg,表示,对于每个xX，都有(f,g)(x,)=,f(x,),g(x,),(4)f g,表示,对于每个xX，都有(fg)(x,)=,f(x)g(x,),0 表示从U 到0,1的函数|,xA,1 表示从U 到0,1的函数|,xA,清华大学现代远程教育,*,专升本课程,特征函数,特征函数的特性,1),A,=1,A,2),AB,=,A,B,3),AB,=,A,+,B,A,B,4),A,B,=,A,A,B,清华大学现代远程教育,*,专升本课程,特征函数,特征函数的特性,5)A(AU0,A,1),6),A,=0 A=,7),A,=1,A=U,8),A,B A B,清华大学现代远程教育,*,专升本课程,特征函数,特征函数的特性,9),A,=,B,A=B,10),A,B,=,A,A B,11),A,A,=,A,清华大学现代远程教育,*,专升本课程,变换和置换函数,非空集合A 上的函数，即一个从A 到A 的函数称为A,的一个变换,。,如果是双射函数则称为A,的一个一一变换,。,相应A,上的恒等关系称为恒等变换,清华大学现代远程教育,*,专升本课程,变换和置换函数,按照函数合成的概念，A 上两个变换是可以合成的，合成函数仍然是从A 到A,的函数，即仍然是一个变换,任何一个变换和恒等变换的合成仍为原变换，即,：,f,=IA,f,=,f,IA,清华大学现代远程教育,*,专升本课程,变换和置换函数,由于只有双射函数才有反函数，所以只有一一变换才有反变换,对于A,上的一一变换,f,，有,f,f,1,=,f,1,f,=I,A,如果A 是有限集，则A 上的一个一一变换称为A的一个置换。,清华大学现代远程教育,*,专升本课程,变换和置换函数,如果A=,a,1,a,2,.,a,n,则置换习惯记作,这是有,n,个元素的置换，称为,n,元置换。共有,n,！个,清华大学现代远程教育,*,专升本课程,变换和置换函数,以,S,n,表示这,n,！个,n,元置换的集合,例,A=1,2,3,，则,S,3,=,1,2,.,6,),其中,清华大学现代远程教育,*,专升本课程,变换和置换函数,1,是恒等置换,清华大学现代远程教育,*,专升本课程,变换和置换函数,可以计算任何两个置换的合成，如,一般合成运算不满足交换律，通常,清华大学现代远程教育,*,专升本课程,变换和置换函数,对于,n,个元素的集合,A,中的,m,个不同元素,b,1,b,2,.,b,m,，如果,n,元置换,定义为：,这时称,为,m,次轮换。,m=2,时称为对换。简单表示成,=(,b,1,b,2,.,b,m,),清华大学现代远程教育,*,专升本课程,变换和置换函数,如上述的,等等。其中,2,，,3,，,4,是对换,清华大学现代远程教育,*,专升本课程,变换和置换函数,轮换也能进行合成运算。,显然一个对换与其自己的合成为恒等置换,即,(bi,bj,),(bi,bj,)=I,A,。,清华大学现代远程教育,*,专升本课程,变换和置换函数,例,A=1,2,3,4,5,6,，,1,=(4,1,3,5),，,2,=(5,6,3),清华大学现代远程教育,*,专升本课程,变换和置换函数,例,A=1,2,3,4,5,6,，,1,=(4,1,3,5),，,2,=(5,6,3),清华大学现代远程教育,*,专升本课程,变换和置换函数,一般情况下，轮换的合成不满足交换律，而且也不再是轮换。,在什么情况下，轮换的合成还是轮换呢？,如果,A,中元素没有同时出现在其上的两个轮换，这两个轮换称为是不交的。,如,S,6,中的轮换,(1,2,4),和,(3,5),是不交的,清华大学现代远程教育,*,专升本课程,变换和置换函数,两个不交的轮换的合成运算满足交换律,任何一个置换，都可以表示成一系列不交轮换的合成，且表达式是唯一的。,任何一个轮换，都可以表示成一系列对换的合成，但表达式不是是唯一的。,清华大学现代远程教育,*,专升本课程,变换和置换函数,例如,显然两个表达式是不同的。,清华大学现代远程教育,*,专升本课程,集合的基数,对于有限集合的基数，有包含排斥定理。,现在不局限于有限集。,基数定义：集合,A,的元素数，记为,#A,实际度量和比较集合大小的根本方法是建立一一对应关系,这个方法可推广到任意集合上。,清华大学现代远程教育,*,专升本课程,集合的基数,集合等势的概念,A,和,B,为集合,如果存在双射函数,f,：,AB,则称,A,和,B,等势或等位,记为,A,B,；,清华大学现代远程教育,*,专升本课程,集合的基数,集合,NN,与,N,等势。,存在双射函数,f,:NNN,f,(m,n,)=(m+n)2+3m+n/2,所以集合,NN,N,。,清华大学现代远程教育,*,专升本课程,集合的基数,双射函数,f,:NNN,如下图,清华大学现代远程教育,*,专升本课程,集合的基数,自然数集合,N,与有理数集合,Q,等势。,函数,f,:NQ,，,f,(n,),就是,n,旁边的有理数（见下图），由于,f,的双射性，,N,Q,。,清华大学现代远程教育,*,专升本课程,集合的基数,基数比较定义：,1)A,B,，则称,A,和,B,的基数相等，,即,#A=#B,；,2),如果存在单射函数,f,：,AB,则称,#A,#B,；,3),如果,#A.#B,，且,#A#B,则称,#A#B,。,清华大学现代远程教育,*,专升本课程,集合的基数,基数比较定义：,4),自然数集合,N,的基数为,即,#,N,=,可数集合：等位于自然数集合的的任何集合。,可计数集合：有限集和无穷可数集。,清华大学现代远程教育,*,专升本课程,集合的基数,对于任意的自然数,n,，都有,n,+,5),实数集合,R,的基数为,=,即,#R=,清华大学现代远程教育,*,专升本课程,集合的计算机表示,设,A,1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,B,x|x,A,x,是奇数,C,x|x,A,x,是偶数,D,x|x,A,x 5,B=10 1010 1010,C=01 0101 0101,D=11 1100 0000,清华大学现代远程教育,*,专升本课程,符号,