离散数学3

离散数学DiscreteMathematics倪子伟ComputerScienceDepartmentXiamenUniversity•在高等数学中,函数的定义域和值域都是在数集上讨论,这种函数一般是连续或间断连续的函数。•本章把将函数的概念推广到对离散量的讨论,将函数看作是一种特殊的关系,其定义域和值域可以是各类集合。•计算机科学把程序的输出看作是输入的函数,并充分运用数学分析对函数研究的成果,在高级程序设计语言标准子程序库中的Sqrt(x)、Sin(x)、Log(x)等就是按Taylor级数展开而编成供使用时直接调用。第三章函数(Function)•两个集合上的二元关系是一个意义相当广泛的概念,它没有对两个集合的元素作任何特殊的限制。•本章引入的函数(也称映射mapping)概念,表明了两个集合元素之间的对应关系。定义3.1.1设A和B是集合,f是从A到B的关系。如果对于每一个aA,存在唯一的bB,使afb,则称关系f是由A到B的一个函数,记作f:AB。若afb,称a为像源或自变量;称b为a的像(image)或对应于a的函数值,记作b=f(a)。A称作f的定义域(domain),记作Df。§3.1函数的基本性质•由所有映像组成的集合称为f的值域(range),记作Rf。Rf=f(A)={b|bB,存在aA,使得f(a)=b}。RfB,B称为f的陪域(codomain)。•函数是一个附加有限制条件的特殊关系,其特殊之处在于:(1)函数的定义域是集合A而不能是A的真子集,即Df=A,每个像源都有像,也称f为全(total)函数。(2)每一个函数中序偶的第一个元素一定是互不相同的,即每个像源只有一个像。f的这种性质称为单值。•若A=,B为非空的任一集合,由定义空关系为A到B的空函数。•若A=,B=,则从A到B的关系是无效关系,不是函数。例3.1.1设A={a,b,c},B={0,1},判别下列二元关系中哪个是函数？(1)R1={‹a,0›,‹b,1›,‹c,1›}。(2)R2={‹a,0›,‹a,1›,‹b,0›,‹c,1›}。(3)R3={‹a,0›,‹b,1›}。解(1)R1是函数,函数的定义允许多个元素共有一个像。(2)R2不是函数,因为A中元素a有两个不同的像。(3)R3不是函数,因为A中元素c没有像。例3.1.2设f是N上的二元关系,a,bN,若a+b=24,则afb。问f是否是N上的函数？解由于f仅涉及N中的元素0,1,2,…,24，而其它元素没有像,所以f不是N上的函数。定义3.1.2设有函数f:AB和g:CD,如果A=C,B=D,并且任意的aA(或aC),都有f(a)=g(a),则称函数f和g相等,记作f=g。定义3.1.3设有函数f:CB,CA,f在A–C上无定义,则称f是A到B的偏(partial)函数。定义3.1.4设有函数f:AB和g:CB,如果CA,且对于所有的aC,有g(a)=f(a),则称g是f的限制(restriction),f是g的扩充(extension)。•如果g是A到B偏函数,当对g无定义处规定一个值(补充定义),可构造出g的一个扩充。例3.1.3f(x)=;g(x,y)=规定：xyx若x0,f(x)=0;g(x,0)=0。例3.1.4设A={0,1,2,3,4,5},B={0,1},f定义为:f(2n)=0,f(2n+1)=1,(n=0,1,2);C={2,3},则g(2)=0,g(3)=1就是f在C上的限制。•给定有限集合A和B,从A到B共有2|A||B|=2nm个不同的二元关系,但并非每个关系都是函数,那么究竟有多少个关系是函数呢？定理3.1.1设A、B是有限集合,则从A到B共有|B||A|个不同的函数。证明设|A|=n,|B|=m。因为任一函数f是由A中n个元素的取值所唯一确定的,A中的任一元素a,f在a处的取值都有m种可能,所以A到B可以定义m·m…m=mn=|B||A|个不同的函数。▎n•常将从A到B的所有不同函数构成的集合记作BA:BA={f|f：AB}。例3.1.5设A={a,b,c},B={0,1},从A到B共有232=26=64个不同的二元关系。但仅有23=8个不同的函数,它们是:R1={‹a,0›,‹b,0›,‹c,0›}；R2={‹a,0›,‹b,0›,‹c,1›}；R3={‹a,0›,‹b,1›,‹c,0›}；R4={‹a,0›,‹b,1›,‹c,1›}；R5={‹a,1›,‹b,0›,‹c,0›}；R6={‹a,1›,‹b,0›,‹c,1›}；R7={‹a,1›,‹b,1›,‹c,0›}；R8={‹a,1›,‹b,1›,‹c,1›}。•一般地,A到B的函数决定A到B的一个关系,反之却不一定正确。定理3.1.2设f:XY,A,BP(X)(powerset),则f(A∪B)=f(A)∪f(B)；f(A∩B)f(A)∩f(B)。证明(1)设yf(A∪B),则存在xA∪B,使f(x)=y即xA∨xB时有y=f(x)。故f(x)f(A)∨f(x)f(B),因此yf(A)∪f(B),于是f(A∪B)f(A)∪f(B)•反之,设yf(A)∪f(B),则有yf(A)或yf(B)于是,在A与B两集合中,至少有一个集合里有一个x使f(x)=y,即xA∪B。从而y=f(x)f(A∪B),于是f(A)∪f(B)f(A∪B)所以f(A∪B)=f(A)∪f(B)。▎一般地,有f()=。iiA)(iiAfiiAiiAf)((2)设yf(A∩B),则存在xA∩B,使f(x)=y。即存在xA∧xB,使f(x)=y。故yf(A)∧yf(B)y(f(A)∩f(B))所以f(A∩B)f(A)∩f(B)。一般地,有f()例3.1.6设X={a,b,c}，Y={1,2,3}。f:XY,f(a)=1,f(b)=f(c)=2。A={a,b},B={c}。于是A∩B=，f(A∩B)=。但是,f(A)∩f(B)={1,2}∩{2}={2}。这表明f(A∩B)f(A)∩f(B)。§3.2特殊函数•根据函数的不同对应关系,可将函数进行分类定义3.2.1设f:AB是一个函数,(1)对任意的ai,ajA,如aiaj,有f(ai)f(aj)(即当f(ai)=f(aj)时,有ai=aj),则称f为从A到B的单射(injection)。单射函数也称一对一的函数。(2)若Rf=B,则称f为从A到B的满射(surjection)。满射函数也称映上的函数。(3)若f既是单射又是满射,则称f为从A到B的双射(bijection)。双射函数也称一一对应。•下面图3.2.1可加深对这三种函数区别的理解：•从定义可知:当A、B为有限集时,f:AB1.f为单射的必要条件是|A|≤|B|；2.f为满射的必要条件是|A|≥|B|；3.f为双射的必要条件是|A|=|B|。设|A|=n,|B|=m,(1)当nm,AB中共含A=mi0)1(imnmm(m–1)(m–2)…(m–n+1)个不同的单射函数;但不含满射函数,故不含双射函数。(2)当n=m,AB中共含n!个双射函数。(3)当nm,AB中不含单射函数,故不含双射函数。存在iC(m–i)n个不同的满射。定义3.2.2设f:AB,若存在bB,使任意的aA,有f(a)=b,则称f为常值(constant)函数。定义3.2.3设IA:AA,若对任意的aA,均有IA(a)=a,则称IA为恒等(identity)函数。•由定义3.2.1知,常值函数不是单射函数,恒等函数是双射函数。定义3.2.4设R是A上的等价关系,aA,f:AA/R,使得f(a)=[a]R,它把元素a映到a的等价类,称f为A到商集A/R的典型(自然)映射•显然,典型映射是一个满射。但当等价关系不是恒等关系时,典型映射都不是单射的。例3.2.1设有函数f:IZ6,f(i)=Res6(i),这是一个从I到Z6的满射,但不是单射。例3.2.2设有函数g:NN,g(i)=2i,这是一个从N到N的单射,但不是满射。例3.2.3设有函数h:RR,h(x)=3x+8,这是一个从R到R的双射。例3.2.4f(n)=,表示n开平方后取算术根的整数部分,问f是N到N的什么函数？nn2n12解任给nN,则=n,而n2N，即f是N到N的满射。1,2N,12,f(1)==1,f(2)==1.414…=1，即f不是N到N的单射,因此f不是N到N的双射例3.2.5在64人参加的围棋单淘汰赛,问要举行多少场次比赛才能定出冠军？解除冠军外,每一选手都只失败一次,正好与比赛场次成一一对应的双射,所以要举行63场次的比赛。•函数的合成(又称复合)本质上就是关系合成,第二章有关关系合成的所有定理都适合于函数的合成。任意两个函数的合成可构造出新的函数•定义3.3.1设有函数f:AB和g:BC,则f和g的合成函数是一个由A到C的函数,记为gof(简记成gf)。对于aA,有(gof)(a)=g(f(a))。•注意:合成关系的记号为fog(前f后g),而合成函数记号为gof(前g后f),这是为了和数学复合函数的习惯写法相一致。§3.3合成函数约定:只有当Rf=B时,它们的合成才有意义。当这一要求不满足时,可利用函数的限制和扩充来弥补。定理3.3.1设有函数f:AB,g:BC,h:CD,则有h(gf)=(hg)f。证明aA,根据合成函数的定义,有[h(gf)](a)=h[(gf)(a)]=h(g(f(a)))=(hg)(f(a))=[(hg)f](a)所以,h(gf)=(hg)f。▎•因为合成函数满足结合律,所以通常省略括号而写成hgf。•归纳地,设有n个函数f1:A1A2,f2:A2A3,…,fn:AnAn+1,则不加括号的表达式fnfn–1…f1唯一地表示一个从A1到An+1的函数。•特别地,当f:AA,则f可与自身合成任意次。归纳定义为：1.f0(a)=a,f0=IA;2.fn(a)=f(fn–1(a))=fn–1(f(a))。例3.3.1设f(x)=1+x2,g(x)=2+x,则fog(x)=f(2+x)=1+(2+x)2=5+4x+x2gof(x)=g(1+x2)=2+1+x2=3+x2gof≠fog,可见合成函数“o”不满足交换律。定义3.3.2设有函数f：AA，且f2=f，则称f是幂等函数。例3.3.2设f:INk,Nk={0,1,2,…k–1},f(i)=i(modk)。f2(i)=f(f(i))=f(i(modk))=((i(modk))(modk))=i(modk)=f(i)•当n2时,f3=f2f=ff=f,…,fn=f。•若f是幂等函数,则对所有正整数n,都有fn=f定理3.3.2设有函数f:AB和g:BC,那么(1)如果f和g都是单射,则gf也是单射;证明(1)因为f是单射,任意的ai,ajA,当aiaj,有f(ai)f(aj)。又因为g也是单射,当f(ai)f(aj)时,g(f(ai))g(f(aj))。即当aiaj,gf(ai)gf(aj),所以gf是单射。(2)如果f和g都是满射,则gf也是满射;证明任取cC,因为g是满射,必存在某一bB,使得g(b)=c。又因为f也是满射,必存在某一aA,使得f(a)=b。因此任取cC,存在某一aA,使(gf)(a)=g(f(a))=g(b)=c,所以gf是满射。(3)如果f和g都是双射,则gf也是双射。证明由(1)和(2)立即可得。▎•定理3.3.2的逆定理不成立,但有如下“部分可逆”的结论。定理3.3.3设有函数f：AB和g：BC，那么(1)如果gf是单射,则f是单射;证明(1)因为gf是单射,当aiaj,有gf(ai)gf(aj)即g(f(ai))g(f(aj))。假设f不是单射,有f(ai)=f(aj)=b,则对同一变