2.3Functions.ppt

1、1,1,DiscreteMathematics,Dr.HanHuang,SouthChinaUniversityofTechnology,2,2,Section2.3,Chapter2.LogicandProof,Sets,andFunction,Functions,3,3,Contents,Introduction,1,OnetoOneFunctionandOntoFunction,2,InverseFunctionsandCompositionofFunctions,3,GraphandSomeCaseofImportantFunction,4,4,4,Introduction,5,Fun

2、ctions,Fromcalculus,youknowtheconceptofareal-valuedfunctionf,whichassignstoeachnumberxRoneparticularvaluey=f(x),whereyR.Example:fdefinedbytherulef(x)=x2Thenotionofafunctioncanbegeneralizedtotheconceptofassigningelementsofanysettoelementsofanyset.Functionsarealsocalledoperators.,6,Function:FormalDefi

3、nition,Afunctionffrom(or“mapping”)AtoB(f:AB)isanassignmentofexactlyoneelementf(x)BtoeachelementxA.Somefurthergeneralizationsofthisidea:Functionsofnarguments:f:(A1xA2.xAn)B.Apartial(non-total)functionfassignszerooroneelementsofBtoeachelementxA.,7,Wecanrepresentafunctionf:ABasasetoforderedpairsf=(a,f(

4、a)|aA.ThismakesfarelationbetweenAandB:fisasubsetofAxB.Butfunctionsarespecial:foreveryaA,thereisatleastonepair(a,b).Formally:aAbB(a,b)f)foreveryaA,thereisatmostonepair(a,b).Formally:a,b,c(a,b)f(a,c)fbc)Arelationovernumberscanberepresentasasetofpointsonaplane.(Apointisapair(x,y).)Afunctionisthenacurve

5、(setofpoints),withonlyoneyforeachx.,8,Functionscanberepresentedgraphicallyinseveralways:,A,B,a,b,f,f,x,y,Plot,BipartiteGraph,LikeVenndiagrams,A,B,9,FunctionsWeveSeenSoFar,Apropositionmightbeviewedasafunctionfrom“situations”totruthvaluesT,Fp=“Itisraining.”s=oursituationhere,nowp(s)T,F.Apropositionalo

6、peratorcanbeviewedasafunctionfromorderedpairsoftruthvaluestotruthvalues:e.g.,(F,T)=T.,Anotherexample:(T,F)=F.,10,Morefunctionssofar,Apredicatecanbeviewedasafunctionfromobjectstopropositions:P:“is7feettall”;P(Mike)=“Mikeis7feettall.”AsetSoveruniverseUcanbeviewedasafunctionfromtheelementsofUto.,11,Sti

7、llMoreFunctions,AsetSoveruniverseUcanbeviewedasafunctionfromtheelementsofUtoT,F,sayingforeachelementofUwhetheritisinS.SupposeU=0,1,2,3,4.ThenS=1,3S(0)=S(2)=S(4)=F,S(1)=S(3)=T.,12,StillMoreFunctions,Asetoperatorsuchasorcanbeviewedasafunctionfromorderedpairsofsets,tosets.Example:(1,3,3,4)=3,13,Anewnot

8、ation,SometimeswewriteYXtodenotethesetFofallpossiblefunctionsf:XY.Thus,fYXisanotherwayofsayingthatf:XY.(Thisnotationisespeciallyappropriate,becauseforfiniteX,Y,wehave|F|=|Y|X|.),14,ANeatTrick,IfweuserepresentationsF0,T1,thenasubsetTSisafunctionfromSto0,1,Therefore,P(S)canberepresentedas0,1S(thesetof

9、allfunctionsfromSto0,1)(Notethatifwealsorepresent2:0,1,thenP(S)canberepresentedas2S.ThepowersetofSissometimeswrittenthiswaytostressthecardinalityofthepowerset.),15,SomeFunctionTerminology,Iff:AB,andf(a)=b(whereaAfisstrictlydecreasingiffxyf(x)f(y)forallx,yindomain;Iffiseitherstrictlyincreasingorstric

10、tlydecreasing,thenfmustbeone-to-one.Doestheconversehold?,27,Iffiseitherstrictlyincreasingorstrictlydecreasing,thenfisone-to-one.Doestheconversehold?NOE.g.,f:NNsuchthatifxiseventhenf(x)=x+1ifxisoddthenf(x)=x-1,28,Onto(Surjective)Functions,Afunctionf:ABisontoorsurjectiveorasurjectioniffitsrangeisequal

11、toitscodomain(bB,aA:f(a)=b).Consider“countryofbirthof”:AB,whereA=people,B=countries.Isthisafunction?Isitaninjection?Isitasurjection?,29,Onto(Surjective)Functions,Afunctionf:ABisontoorsurjectiveorasurjectioniffitsrangeisequaltoitscodomainConsider“countryofbirthof”:AB,whereA=people,B=countries.Isthisa

12、function?Yes(always1c.o.b.)Isitaninjection?No(manyhavesamec.o.b.)Isitasurjection?Probablyyes,30,Onto(Surjective)Functions,Afunctionf:ABisontoorsurjectiveorasurjectioniffitsrangeisequaltoitscodomain.Inpredicatelogic:bBaAf(a)=b,31,Onto(Surjective)Functions,Afunctionf:ABisontoorsurjectiveorasurjectioni

13、ffitsrangeisequaltoitscodomain(bBaAf(a)=b).Think:AnontofunctionmapsthesetAonto(over,covering)theentiretyofthesetB,notjustoverapieceofit.E.g.,fordomain&codomainR,x3isonto,whereasx2isnt.(Whynot?),32,Onto(Surjective)Functions,E.g.,fordomain&codomainR,x3isonto,butx2isnot.(Whynot?)Considerf:RRsuchthat,fo

14、rallx,f(x)=x2.Consideranynegativenumbera=-binR.x(x2=a).Sofisnotsurjective.Considerf:RRsuchthatforallx,f(x)=x3.Consideranynegativenumbera=-binR.Letzbesuchthatz3=b.Then(-z)3=-b=a,33,TheIdentityFunction,ForanydomainA,theidentityfunctionI:AA(alsowrittenIA)onAisthefunctionsuchthateverythingismappedtoitse

15、lfInpredicatelogic:aAI(a)=a.,34,TheIdentityFunction,ForanydomainA,theidentityfunctionI:AA(alsowrittenIA)onAisthefunctionsuchthataAI(a)=a.Istheidentityfunctionone-to-one(injective)?onto(surjective)?,35,TheIdentityFunction,ForanydomainA,theidentityfunctionI:AA(alsowrittenIA)onAisthefunctionsuchthataAI

16、(a)=a.Istheidentityfunctionone-to-one(injective)?Yesonto(surjective)?Yes,36,Theidentityfunction:,IdentityFunctionIllustrations,Domainandrange,x,y,y=I(x)=x,37,IllustrationofOnto,Arethesefunctionsontotheirdepictedco-domains?,38,IllustrationofOnto,Arethesefunctionsonto?,39,IllustrationofOnto,Arethesefu

17、nctionsonto?,onto,notonto,onto,notonto,40,IllustrationofOnto,Arethesefunctions1-1?,onto,notonto,onto,notonto,41,IllustrationofOnto,Arethesefunctions1-1?,not1-1onto,not1-1notonto,1-1onto,1-1notonto,42,42,InverseFunctionandCompositionofFunctions,43,Bijections,Afunctionissaidtobeaone-to-onecorresponden

18、ce,orabijectioniffitisbothone-to-oneandonto.,44,Twoterminologiesfortalkingaboutfunctions,injection=one-to-onesurjection=ontobijection=one-to-onecorrespondence3=1&2,45,Bijections,Forbijectionsf:AB,thereexistsaninverseoff,writtenf1:BAIntuitively,thisisthefunctionthatundoeseverythingthatfdoesFormally,i

19、tstheuniquefunctionsuchthat.,46,Bijections,Forbijectionsf:AB,thereexistsaninverseoff,writtenf1:BAIntuitively,thisisthefunctionthatundoeseverythingthatfdoesFormally,itstheuniquefunctionsuchthat(recallthatIAistheidentityfunctiononA),47,Bijections,Example1:Letf:ZZbedefinedasf(x)=x+1.Whatisf1?Example2:L

20、etg:ZNbedefinedasg(x)=|x|.Whatisg1?,48,Bijections,Example1:Letf:ZZbedefinedasf(x)=x+1.Whatisf1?f1isthefunction(letscallith)h:ZZdefinedash(x)=x-1.Proof:,h(f(x)=(x+1)-1=x,49,Bijections,Example2:Letg:ZNbedefinedasg(x)=|x|.Whatisg1?Thiswasatrickquestion:thereisnosuchfunction,sincegisnotabijection:Therei

21、snofunctionhsuchthath(|x|)=xandh(|x|)=x(NBThereisarelationhforwhichthisistrue.),50,Operatorsoverfunctions,If(“dot”)isann-aryoperatoroverB,thenwecanextendtoalsodenoteanoperatoroverfunctionsfromAtoB.E.g.:Givenanybinaryoperator:BBB,andfunctionsf,g:AB,wedefine(fg):ABtobethefunctiondefinedby:aA,(fg)(a)=f

22、(a)g(a).,51,FunctionOperatorExample,(plus,times)arebinaryoperatorsoverR.(Normaladdition&multiplication.)Therefore,wecanalso“add”and“multiply”functionsf,g:RR:(fg):RR,where(fg)(x)=f(x)g(x)(fg):RR,where(fg)(x)=f(x)g(x),52,FunctionCompositionOperator,Forfunctionsg:ABandf:BC,thereisaspecialoperatorcalled

23、compose(“”).Itcomposes(creates)anewfunctionoutoffandgbyapplyingftotheresultofapplyingg.Wesay(fg):AC,where(fg)(a):f(g(a).g(a)B,sof(g(a)isdefinedandf(g(a)C.Notethatisnon-commutative(i.e.,wedontalwayshavefg=gf).,Notematchhere.,53,FunctionCompositionOperator,“Wedontalwayshavefg=gf“Canyouexpressthisinpre

24、dicatelogic?,54,FunctionCompositionOperator,“Wedontalwayshavefg=gf“Canyouexpressthisinpredicatelogic?(fgx(fg(x)=gf(x).Donotwrite:fgx(fg(x)gf(x)(NotethatthisformulaquantifiesoverfunctionsaswellasordinaryobjectssomethingthatisnotpossibleinFirstOrderPredicateLogic(FOPL),whichiswhatwastaughtearlierinthi

25、scourse.),55,55,GraphandSomeCaseofImportantFunction,56,AsideAboutRepresentations,Itispossibletorepresentanytypeofdiscretestructure(propositions,bit-strings,numbers,sets,orderedpairs,functions)intermsofsomecombinationofotherstructures.Perhapsnoneofthesestructuresismorefundamentalthantheothers.However,logic,andsetsareoftenusedasthefoundationforallelse.E.g.in,57,ACoupleofKeyFunctions,Indiscretemath,wefrequentlyusethefollowingtwofunctionsoverrealnumbers:Thefloorfunction:RZ,wherex(“floorofx”)meansthelargestintegerx.I.e.,x:max(iZ|ix).Theceilingfunction:RZ,wherex(