ChFuctionsetc离散数学英文实用.pptx
Definition of a FunctionA function from set A to set B,denoted by f:A B,is the assignment of exactly one element of B to each element of A Given f:A B,and if f(a)=b(f maps a to b)where a A and b B,thenA is the domain(定义域)of fB is the co-domain(伴域)of fb is the image of aa is the pre-image(原像)of bRange(值域)of f:set of all images of elements of Arangeco-domainpre-imageABfab=f(a)domainimageExample:f:Z Z,f(x)=x2domain/co-domain:Z=set of integersrange:perfect squares 0,1,4,9,.第1页/共51页Functions A function f:ABcan also be defined as a subset of AB(Cartesian product).This subset is restricted to be a relation where no two elements of the relation have the same first elementSpecifically,a function f from A to B contains one,and only one ordered pair(a,b)for every element a A.x x A yy B (x,y)f z(x,z)f y=z 第2页/共51页Functions from FunctionsIf f1 and f2 are two functions from A to R(real numbers),then g=f1+f2 and h=f1 f2 are also functions from A to R defined by:g(x)=(f1+f2)(x)=f1(x)+f2(x)h(x)=(f1f2)(x)=f1(x)f2(x)Example:f1(x)=x,f2(x)=x2.(R to R)(f1+f2)(x)=x+x2 (f1f2)(x)=x3第3页/共51页Functions of Setsf:A B,and S is a subset of A.Then we can define f:S Image(S)=f(S)ASBf(S)f第4页/共51页Function ExampleThe domain of f is A=a,b,c,dThe codomain is B=X,Y,ZThe range of f is Y,Z The pre-image of Y is b.The image of b is YThe pre-images of Z are a,c and dLet S=c,d,f(S)=?Let T=a,b,c,f(T)=?f第5页/共51页One-to-one(Injective单射)FunctionsA function f is one-to-one if and only if f(x)=f(y)implies x=y for all x,y in the domain of fABfThis is not allowed Example:f:Z Z,f(x)=x2 one-to-one?g:Z Z,g(x)=x3 one-to-one?h:Z+Z+,h(x)=x2 one-to-one?The propositional statement?第6页/共51页Onto(Surjective满射)functionsA function f from A to B is onto if for every element b in B there is an element a in A,f(a)=b.Co-domain=RangePropositional Statement?ABfyxThis is not allowed Example:f:Z Z,f(x)=x2 onto?How about Z+Z+?R+R+?第7页/共51页One-to-One And Onto or One-to-One Correspondence(Bijective双射)FunctionsA function f is in one-to-one correspondence if it is both one-to-one and onto.ABfNumber of elements in A and B must be the same when they are finite.Every element in A is uniquely associated with exactly one element in B.Examples:f:RR,f(x)=-x?g:Z+Z+,g(x)=x2?R+R+?第8页/共51页ExamplesOnto but not One-to-oneOne-to-one but not Onto One-to-one and Onto 第9页/共51页Prove/Disprove:f Is One-to-One or Onto第10页/共51页The Graphs of FunctionsThe graph of a function f is the set of ordered pairs(a,b)|a in A,f(a)=b.This is a subset of the Cartesian product of ABExample:f(n)=2n+1from Z to Znf第11页/共51页The Graphs of FunctionsExample:f(n)=n2 from Z to Z第12页/共51页Increasing and Decreasing FunctionsStrictly Increasing FunctionsStrictly Decreasing Functionsx,y realxyxydecreasingincreasingStrictly increasing and strictly decreasing functions are one-to-onef(a)=f(b)第13页/共51页ExamplesDetermine which functions are one-to-one,onto,one-to-one and onto,strictly increasing or strictly decreasingf(x)=x,R Rf(x)=x5,R Rf(x)=|x|,Z Z,or Z N F(x)=2x,Z+E,E=x Z+|x is even N E?f(x)=sin(x),R R,R -1,1F(x)=x+sin(x),R R 第14页/共51页F(x)=x+sin(x)Strictly Increasing第15页/共51页Inverse FunctionsLet f be a one-to-one and onto function from A to B.The inverse function of f is the function that assigns to b in B the element a in A such that f(a)=b.ABinverse of fABfIf a function is not one-to-one and onto it is not invertible.f:R R,f(x)=x2.Is f(x)=x+1 invertible over R R?Over Z Z?Over N N?第16页/共51页Compositions of FunctionsA composition of 2 functions g:A B and f:B C is defined by:A Cg(a)fB第17页/共51页Compositions of Functions:ExampleRange of g must be subset of domain of f!ABCgCfABThis is one function from A to C第18页/共51页Compositions of Functions:Fact 1Theorem:Let g:A B and f:B C.If fg is one-to-one,then g is also one-to-oneProof:if a b then f(g(a)f(g(b)since the composition is one-to-one(by assumption)By contradiction.If g is not one-to-one,then a,bA,a b and g(a)=g(b).Then f would have two different images for the same point!But fg is one-to-one and f(g(a)f(g(b)whenever a b.Contradiction!第19页/共51页Compositions of Functions:Fact 2Theorem:Let g:A B and f:B C.If fg is one-to-one and g is onto,then f is also one-to-oneProof by contradiction:if f is not one-to-one,c,dB,c d and f(c)=f(d).Since g is onto,every element in B has a preimage:a,bA a b g(a)=c and g(b)=d.We have a contradiction since a b and f(g(a)=f(g(b)!(fg is not one-to-one)第20页/共51页Compositions of Functions:ExamplesIf f(x)=x2 and g(x)=2x+1,then f(g(x)=(2x+1)2=4x2+4x+1,and g(f(x)=2x2+1If f(x)=3x2+5x+1 and g(x)=x3+1,then f(g(x)=3(x3+1)2+5(x3+1)+1 and g(f(x)=(3x2+5x+1)3+1第21页/共51页Floor and Ceiling Functionsy=xy=xFloor function f:R Z,x R n Z(f(x)=n (x 1 n x).We denote f(x)=xCeiling function f:R Z,x R n Z(f(x)=n (x n x+1).We denote f(x)=x第22页/共51页Properties of the Floor and Ceiling Functions(1a)x=n if and only if n x n+1(1b)x=n if and only if n 1 x n(1c)x=n if and only if x 1 n x(1d)x=n if and only if x n x+1(2)x 1 x x x x+1(3a)x=x(3b)x=x(4a)x+n=x+n(4b)x+n =x+nn x 0 x n-x n x n x 1=(apply negative signs to above)x 1 n xIt is obvious that we can go from(1c)to(1a)n is an integerShow that(1a)=(1c)第23页/共51页Properties of the Floor and Ceiling FunctionsProve(3a)that-x=-xProof:Let -x=m,then by definition,m Z and m -x m+1 (1a)We need to show m=-x.Or,to show x=-m(i).By definition of(i)and(1b)-m 1 x -m.But this is equivalent to(1a)!(Apply a negative sign to the inequalities)第24页/共51页Properties of the Floor and Ceiling FunctionsProve(4a)that x+n=x+nProof:Let x+n=m,then by definition m Z and m x+n m+1 (1a)We need to show x+n=m.This is equivalent to show x=m n,or by definition,m n x 0,common difference=6an=an-1+6=an-2+6+6=an-2+2(6)=a0+n(6)=5+6n第33页/共51页Sequence ExampleHow can we find the nth term of this sequence?1,7,25,79,241,727,2185,6559,19681,59047,Note that each next term must be obtained by some exponential operation(geometric progression),because we find out that the current term is about 3 times of the previous term.When try 3n+1,n=0,1,2,we find a difference of 2.Therefore an=3n+1 2,for n=0,1,2,We will come back to this sequence again,第34页/共51页Sequence ExampleHow can we find the nth term of this sequence?1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,We need to try very hard to find the nth term of the sequence.Something you must try is the floor or ceiling functions第35页/共51页The Summation NotationThe summation notation,mi=k ak,is used to express the sum of the terms m to nak+ak+1+am from the sequence an.In this notation,i is called the index of summation,k is the lower limit and m the upper limit of the index第36页/共51页Summation Examplesi=1j=0Some sums of infinite sequences can be calculated,or they converge 第37页/共51页Summation ExampleProve thatMethod 1:from the known equation:(x 1)(xn+xn-1+x+1)=xn+1 1 Method 2:Let the sum=S.Then multiply r on both sides,第38页/共51页Sequence Example Again:Application of SummationHow can we find the nth term of the sequence 1,7,25,79,241,727,2185,6559,19681,59047,Let a0=1 and n 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)(Used the summation proved in the last slide)=3n+2(3n 1)=33n 2=3n+1 2We arrived at the same result but used a general approach第39页/共51页第40页/共51页Summation Examples 10 x 11 x(2(10)+1)/6 4 x 5 x(2(4)+1)/6=2310/6 180/6=385 30=355FindNested summation:4i=1 3j=1 ij =4i=1(i+2i+3i)=4i=1 6i=6+12+18+24=60 第41页/共51页Summation ExamplesFind the sum of S=21+22+23+24.+228 S+1=20+21+22+228=(229 1)/(2 1)(1st equation in the table)=229 1So,S=229 2Find the sum of S=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 )(5th equation in the table)=2第42页/共51页CardinalityDefinition:Two sets have the same cardinality if and only if there is a one-to-one correspondence(one-to-one and onto)between themNote:this makes it possible to compare the cardinalities of two infinite setsDefinition:A set that is either finite or has the same cardinality as the set of positive integers(Z+)is called countable第43页/共51页Cardinality ExampleConsider the sequence an,an=n2,n1,2,3,4.Superficially,there seem to be much less elements in an than in Z+(since we skip a lot).Here is the one-to-one and onto mapping:1 2 3 4 5 6 7.1 4 9 16 25 36 49.infinity(Intuitively:countable means you can enumerate them)So the set an is countable because|an|=|Z+|第44页/共51页Cardinality ExampleNatural number set N=0,1,2,3,is countableThe one-to-one correspondence(bijection)f:Z+N is f(n)=n 1This shows|N|=|Z+|第45页/共51页Cardinality Example Example:Show that the set of integers Z is countable.Solution:Z can be listed in a sequence:Z:0,1,1,2,2,3,3,4,4,N N:0,1,2,3,4,5,6,7,8,Or we can define a bijection f:N Z:When n=0:f(n)=0When n is odd:f(n)=(n+1)/2When n0 is even:f(n)=n/2Thisshows|N N|=|Z Z|(=|Z Z+|)第46页/共51页Cardinality ExampleNow what about the positive rational numbers:p/q,where p,q are integers,and q 0?We have found a one-to-one and onto mapping to Z+Conclusion:the set of positive rational numbers are countable12 3 4 5 6 7 8 9 10 1 2 3 1/3 2/3 3/2 4 5 第47页/共51页Cardinality ExampleProve that the real numbers are not countable!Prove by contradiction:Assume that the real numbers are countableThen real numbers in(0,1)are countable(since it is a subset),Thus there is a complete list of real numbers as follows:r1=0.d11 d12 d13 d14.r2=0.d21 d22 d23 d24.r3=0.d31 d32 d33 d34.r4=0.d41 d42 d43 d44.where dij 0,1,2,9 (i,j=1,2,3,4,)第48页/共51页Cardinality ExampleProve that the real numbers are not countable!Proof continues:Construct the number:r=0.c1 c2 c3 c4.where ci=4 if dii 4 and ci=5 if dii=4This guarantees r to be different from any real number on the list,so it is not in the list,so the list is not complete.Contradiction!Because real numbers in(0,1)are uncountable,all real numbers are uncountable.第49页/共51页Exercises#4P153:7,9,23,30,31,48,54P167:3,25d-hP 176:2,10,11第50页/共51页感谢您的欣赏！第51页/共51页
