會計學1ChFuctionsetc離散數學英文實用DefinitionofaFunctionAfunction

fromsetAtosetB,denotedbyf:AB,istheassignmentofexactlyoneelementofBtoeachelementofA

Givenf:AB,andiff(a)=b(fmapsatob)

whereaAandbB,thenAisthedomain(定義域)offBistheco-domain(伴域)offbistheimageofaaisthepre-image(原像)ofbRange(值域)off:setofallimagesofelementsofArangeco-domainpre-imageABfab=f(a)domainimageExample:f:ZZ,f(x)=x2domain/co-domain:Z=setofintegersrange:perfectsquares{0,1,4,9,...}第1頁/共51頁FunctionsAfunctionf:A

→B

canalsobedefinedasasubsetofA×B(Cartesianproduct).ThissubsetisrestrictedtobearelationwherenotwoelementsoftherelationhavethesamefirstelementSpecifically,afunctionffromAtoBcontainsone,andonlyoneorderedpair(a,b)foreveryelementa∈

A.

x[[xAy[yB(x,y)f]]

[z(x,z)

f

y=z]]第2頁/共51頁FunctionsfromFunctionsIff1andf2aretwofunctionsfromAtoR(realnumbers),theng=f1+f2andh=f1

f2arealsofunctionsfromAtoRdefinedby:g(x)=(f1+f2)(x)=f1(x)+f2(x)h(x)=(f1f2)(x)=f1(x)f2(x)Example:f1(x)=x,f2(x)=x2.(RtoR)(f1+f2)(x)=x+x2(f1f2)(x)=x3第3頁/共51頁FunctionsofSetsf:AB,andSisasubsetofA.Thenwecandefinef:SImage(S)=f(S)ASBf(S)f第4頁/共51頁FunctionExampleThedomainoffisA={a,b,c,d}ThecodomainisB={X,Y,Z}Therangeoffis{Y,Z}Thepre-imageofYisb.TheimageofbisYThepre-imagesofZarea,canddLetS={c,d},f(S)=?LetT={a,b,c},f(T)=?f第5頁/共51頁One-to-one(Injective單射)FunctionsAfunctionfisone-to-oneifandonlyiff(x)=f(y)impliesx=yforallx,yinthedomainoffABfThisisnotallowedExample:f:ZZ,f(x)=x2one-to-one? g:ZZ,g(x)=x3one-to-one? h:Z+Z+,h(x)=x2one-to-one?Thepropositionalstatement?第6頁/共51頁Onto(Surjective滿射)functionsAfunctionffromAtoBisontoifforeveryelementbinBthereisanelementainA,f(a)=b.Co-domain=RangePropositionalStatement?ABfyxThisisnotallowedExample:f:ZZ,f(x)=x2onto?HowaboutZ+Z+?

R+

R+?

第7頁/共51頁One-to-OneAndOntoorOne-to-OneCorrespondence(Bijective雙射)FunctionsAfunctionfisinone-to-onecorrespondenceifitisbothone-to-oneandonto.ABfNumberofelementsinAandBmustbethesamewhentheyarefinite.EveryelementinAisuniquelyassociatedwithexactlyoneelementinB.Examples:f:RR,f(x)=-x?g:Z+Z+,g(x)=x2?

R+R+?第8頁/共51頁ExamplesOntobutnotOne-to-oneOne-to-onebutnotOntoOne-to-oneandOnto第9頁/共51頁Prove/Disprove:fIsOne-to-OneorOnto第10頁/共51頁TheGraphsofFunctionsThegraphofafunctionfisthesetoforderedpairs{(a,b)|ainA,f(a)=b}.ThisisasubsetoftheCartesianproductofABExample:f(n)=2n+1

fromZtoZnf第11頁/共51頁TheGraphsofFunctionsExample:f(n)=n2

fromZtoZ第12頁/共51頁IncreasingandDecreasingFunctionsStrictlyIncreasingFunctionsStrictlyDecreasingFunctionsx,yrealxy<f(x)f(y)>x’y’<f(y’)f(x’)>decreasingincreasingStrictlyincreasingandstrictlydecreasingfunctionsareone-to-onef(a)=f(b)第13頁/共51頁ExamplesDeterminewhichfunctionsareone-to-one,onto,one-to-oneandonto,strictlyincreasingorstrictlydecreasingf(x)=x,RRf(x)=x5,RRf(x)=|x|,ZZ,orZNF(x)=2x,Z+E,E={xZ+|xiseven}

NE?f(x)=sin(x),RR,R[-1,1]F(x)=x+sin(x),RR第14頁/共51頁F(x)=x+sin(x)StrictlyIncreasing第15頁/共51頁InverseFunctionsLetfbeaone-to-oneandontofunctionfromAtoB.TheinversefunctionoffisthefunctionthatassignstobinBtheelementainAsuchthatf(a)=b.ABinverseoffABfIfafunctionisnotone-to-oneandontoitisnotinvertible.f:RR,f(x)=x2.

Isf(x)=x+1invertibleoverRR?OverZZ?OverNN?第16頁/共51頁CompositionsofFunctionsAcompositionof2functionsg:ABandf:BCisdefinedby: :ACg(a)fB第17頁/共51頁CompositionsofFunctions:ExampleRangeofgmustbesubsetofdomainoff!ABCgCfABThisisonefunctionfromAtoC第18頁/共51頁CompositionsofFunctions:Fact1Theorem:Letg:ABandf:BC.If

fgisone-to-one,thengisalsoone-to-oneProof:ifabthenf(g(a))f(g(b))sincethecompositionisone-to-one(byassumption)Bycontradiction.Ifgisnotone-to-one,thena,bA,abandg(a)=g(b).Thenfwouldhavetwodifferentimagesforthesamepoint!Butfgisone-to-oneandf(g(a))f(g(b))wheneverab.Contradiction!第19頁/共51頁CompositionsofFunctions:Fact2Theorem:Letg:ABandf:BC.If

fgisone-to-oneandgisonto,thenfisalsoone-to-oneProofbycontradiction:iffisnotone-to-one,c,dB,c

dandf(c)=f(d).Sincegisonto,everyelementinBhasapreimage:a,bA

abg(a)=candg(b)=d.Wehaveacontradictionsinceabandf(g(a))=f(g(b))!

(fgisnotone-to-one)第20頁/共51頁CompositionsofFunctions:ExamplesIff(x)=x2andg(x)=2x+1,thenf(g(x))=(2x+1)2=4x2+4x+1,andg(f(x))=2x2+1Iff(x)=3x2+5x+1andg(x)=x3+1,thenf(g(x))=3(x3+1)2+5(x3+1)+1and

g(f(x))=(3x2+5x+1)3+1第21頁/共51頁FloorandCeilingFunctionsy=xy=xFloorfunctionf:RZ,xRnZ(f(x)=n(x–1<nx)).Wedenotef(x)=xCeilingfunctionf:RZ,xRnZ(f(x)=n(xn<x+1)).Wedenotef(x)=x第22頁/共51頁PropertiesoftheFloorandCeilingFunctions(1a)x=nifandonlyifn

x<n+1(1b)x=nifandonlyifn1<x

n(1c)x=nifandonlyifx

1<n

x(1d)x=nifandonlyifx

n<x+1(2)x1<x

x

x<x+1(3a)

x=

x(3b)

x=

x(4a)

x+n=x+n(4b)x+n=x+nnx<n+1=>0x–n<1=>-x–n<1–x=>xn>x–1=>(applynegativesignstoabove)x1<nxItisobviousthatwecangofrom(1c)to(1a)nisanintegerShowthat(1a)=(1c)第23頁/共51頁PropertiesoftheFloorandCeilingFunctionsProve(3a)that-x=-xProof:

Let-x=m,thenbydefinition,mZand

m-x<m+1(1a)Weneedtoshowm=-x.Or,toshow

x=-m(i).Bydefinitionof(i)and(1b)

-m–1<

x

-m.Butthisisequivalentto(1a)!(Applyanegativesigntotheinequalities)第24頁/共51頁PropertiesoftheFloorandCeilingFunctionsProve(4a)that

x+n=x+nProof:

Let

x+n=m,thenbydefinitionmZandmx+n<m+1(1a)Weneedtoshowx+n=m.Thisisequivalenttoshowx=m–n,orbydefinition,m–nx<m–n+1.Butthiscanbeobtainedfrom(1a)byaddingneverysideoftheinequalities第25頁/共51頁ApplicationofFloor-CeilingFunctionsNumberrounding(totheclosestinteger,四舍五入)

Round(34.4)=34

Round(34.5)=35Thiscanbeimplementedbyceilingorflooringfunctions

Round(a)=a+0.5Examples

Round(34.4)=34.4+0.5=34.9=34

Round(34.5)=34.5+0.5=35.0=35第26頁/共51頁ApplicationofFloor-CeilingFunctionsAnelectronicfileinacomputerhasasizeof1024bytes.Arecordthatisusedtostoreastudent’sinformation,suchasname,birthdate,year,class,…,requires15bytesQuestion:Howmanyrecordscanbestoredinafile?Answer:1024/15=68.2666…=68第27頁/共51頁ApplicationofFloor-CeilingFunctionsExample:ATMcells(packets)haveafixedsize:Transmissionrate:500kilobitspersecond(kbps)Question:howmanycellscanbetransmittedinoneminute?Answer:Numberofbitscanbetransmittedinoneminute

500,00060=30,000,000NumberofbitsinanATMpacket

538=424NumberofATMcellscanbetransmittedinoneminute30,000,000/424=70754.717=7075453bytes052第28頁/共51頁SequencesDefinition:

Asequenceisafunctionfromasubsetofthenaturalnumbers(usuallyoftheform

{0,1,2,...})toasetSNotation:

Iffisafunctionfrom{0,1,2,...n,…}toS.Weletan=f(n)andS={a0,a1,…,an,…},orsimplyS={an}aniscalleda(general)term(項)ofthesequence第29頁/共51頁SequencesExample:

Considerthesequencewhere

第30頁/共51頁GeometricProgressionDefinition:Ageometricprogression

isasequenceoftheform:wheretheinitialterm

aandthecommonratiorarerealnumbers.xi=ari,i=0,1,2,…Examples:Leta=1

andr=?1.Then:Leta=2

andr=5.Then:Leta=6

andr=1/3.Then:第31頁/共51頁ArithmeticProgressionDefinition:Anarithmeticprogression

isasequenceoftheform:wheretheinitialterm

aandthecommondifference

darerealnumbers.xi=a+id,i=0,1,2,…Examples:Leta=?1

andd=4:Leta=7

andd=?3:Leta=1andd=2:第32頁/共51頁SequenceExampleHowcanwefindthenthterm(an)ofthissequence?

5,11,17,23,29,35,41,47,53,59,…

Sinceeachnexttermisobtainedbyadding6tothepreviousterm(arithmeticprogression):

a0=5,andwhenn>0,commondifference=6

an=an-1+6=an-2+6+6=an-2+2(6)

=…=a0+n(6)=5+6n

第33頁/共51頁SequenceExampleHowcanwefindthenthtermofthissequence?

1,7,25,79,241,727,2185,6559,19681,59047,…

Notethateachnexttermmustbeobtainedbysomeexponentialoperation(geometricprogression),becausewefindoutthatthecurrenttermisabout3timesofthepreviousterm.Whentry3n+1,n=0,1,2,…,wefindadifferenceof2.Therefore

an=3n+1–2,forn=0,1,2,…Wewillcomebacktothissequenceagain,…第34頁/共51頁SequenceExampleHowcanwefindthenthtermofthissequence?

1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,…

Weneedtotryveryhardtofindthenthtermofthesequence.Somethingyoumusttryisthefloororceilingfunctions第35頁/共51頁TheSummationNotationThesummationnotation,mi=k

ak,isusedtoexpressthesumofthetermsmton

ak+ak+1+…+amfromthesequence{an}.Inthisnotation,iiscalledtheindexofsummation,kisthelowerlimitandmtheupperlimitoftheindex第36頁/共51頁SummationExamplesi=1j=0Somesumsofinfinitesequencescanbecalculated,ortheyconverge第37頁/共51頁SummationExampleProvethatMethod1:fromtheknownequation:

(x–1)(xn+xn-1+…+x+1)=xn+1–1Method2:Letthesum=S.Thenmultiplyronbothsides,…第38頁/共51頁SequenceExampleAgain:ApplicationofSummationHowcanwefindthenthtermofthesequence

1,7,25,79,241,727,2185,6559,19681,59047,…Leta0=1andn>0.Then,

an=3an-1+4=3(3an-2+4)+4=

32an-2+4(31+30)=…=3na0+4(3n-1+3n-2+…+31+30)=3n+4(3n–1)/(3–1)

(Usedthesummationprovedinthelastslide)

=3n+2(3n–1)=33n–2=3n+1–2Wearrivedatthesameresultbutusedageneralapproach第39頁/共51頁第40頁/共51頁SummationExamples[10x11x(2(10)+1)]/6–[4x5x(2(4)+1)]/6=2310/6–180/6=385–30=355FindNestedsummation:4i=1

3j=1ij=4i=1(i+2i+3i) =4i=16i =6+12+18+24=60第41頁/共51頁SummationExamplesFindthesumofS=21+22+23+24...+228

S+1=20+21+22+…+228 =(229–1)/(2–1)(1stequationinthetable) =

229–1So,S=229–2FindthesumofS=1+1/2+1/4+1/8+1/16+1/32+....S=(1/2)0+(1/2)1+(1/2)2+(1/2)3+… =1/(1–?)(5thequationinthetable) =2第42頁/共51頁CardinalityDefinition:Twosetshavethesamecardinalityifandonlyifthereisaone-to-onecorrespondence(one-to-oneandonto)betweenthemNote:thismakesitpossibletocomparethecardinalitiesoftwoinfinitesetsDefinition:

Asetthatiseitherfiniteorhasthesamecardinalityasthesetofpositiveintegers(Z+)iscalledcountable第43頁/共51頁CardinalityExampleConsiderthesequence{an},an=n2,n{1,2,3,4...}Superficially,thereseemtobemuchlesselementsin{an}thaninZ+(sinceweskipalot).

Hereistheone-to-oneandontomapping:1234567....infinity(Intuitively:countablemeansyoucanenumeratethem)Sotheset{an}iscountablebecause|{an}|=|Z+|第44頁/共51頁CardinalityExampleNaturalnumbersetN={0,1,2,3,…}iscountableTheone-to-onecorrespondence(bijection)

f:Z+

Nis

f(n)=n–1Thisshows|N|=|Z+|第45頁/共51頁CardinalityExampleExample:ShowthatthesetofintegersZiscountable.Solution:Zcanbelistedinasequence:

Z:0,1,?1,2,?2,3,?3,4,?4,……

N: 0,1,2,3,4,5,6,7,8,……Orwecandefineabijectio