离散数学课件(英文版)----Function.ppt

《离散数学课件(英文版)----Function.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FunctionsDefinitionofFunctionDefinition:LetAandBbenonemptysets.AfunctionffromAtoB,whichisdenotedf:AB,isarelationfromAtoBsuchthatforallaA,f(a)containsjustoneelementofB.AspecialkindofbinaryrelationUnderf,eachelementinthedomainoffhasauniqueimage.Note:thedomainof:ABi

2、sA，buttherangeisnotnecessarilyequaltoB.ImageandcounterimageLetf:AB,A’A,then(A’)={y

3、y=f(x)，xA’}iscalledtheimageofA’underf.AnelementinDom(f)correspondsavalueAsubsetofDom(f)correspondsanimageLetB’B,thenf-1(B’)={x

4、xA,f(x)B’}iscalledthecounterimageofB’underf.Whatis

5、f-1(f(A’))?A’f-1(f(A’))?f-1(f(A’))A’?BAB’A’fImageandCounterimageSpecialTypesofFunctionsSurjection:ABisasurjectionor“onto”iff.Ran()=B,iff.yB,xA,suchthatf(x)=yInjection(one-to-one):ABisone-to-oneiff.yRan(f),thereisatmostonexA,suchthatf(x)=yiff.x1,x2A,if

6、x1x2，then(x1)(x2)iff.x1,x2A,if(x1)=(x2)，thenx1=x2Bijection(one-to-onecorrespondence)surjectionplusinjectionIfA,BarenonemptysetshowmanydifferentfunctionsfromAtoBarethere?

7、B

8、

9、A

10、howmanyInjectionfromAtoBarethere?If

11、A

12、>

13、B

14、then0else

15、A

16、!*

17、A

18、C

19、B

20、howmanyBijectionfromA

21、toBarethere?If

22、A

23、=

24、B

25、=mthenM!else0SpecialTypesofFunctions:Examples:Z+R,(x)=lnx,one-to-one:RZ,(x)=x,onto:RR,(x)=2x-1，bijection:RRRR,()=,bijectionTrytoproveitWhatis({

26、x,yR,y=x+1})?R{-1}:NNN,()=

27、x2-y2

28、(N{0})={n2

29、nN},-1(

30、{0})={

31、nN}CharacteristicFunctionofSetLetUbetheuniversalset,foranyAU,thecharacteristicfunctionofA,fA:U{0,1}isdefinedasfA(x)=1iff.xANaturalFunctionRisanequivalencerelationonsetA,g:AA/R,forallaA,g(a)=R(a),thenGiscalledanaturalfunctiononANaturalfunctionissurje

32、ctionForanyR(a)A/R,thereexistssomexA，suchthatg(x)=R(x)ImagesofUnionandIntersectionGivenf：AB，andX,YaresubsetsofA,then:f(XY)=f(X)f(Y)f(XY)f(X)f(Y)CompositionofFunctionsSincefunctionisrelationaswell,thecompositionofrelationcanbeappliedforfunctions,withtheresults

33、beingrelation.ThecompositionoffunctionsisstillfunctionSupposef:AB,g:BC,gfisarelationfromAtoC.xA,wehavegf(x)=g(f(x)).Itiseasyt