复旦大学：《离散数学》PPT教学课件（赵一鸣）05/28

Chapter 3 Functions 令P181( Sixth edition &P168 (Fifth Edition)

Chapter 3 Functions ❖ P181(Sixth Edition) ❖ P168(Fifth Edition)

Theorem 3.1: Let f be an everywhere function from a to b and a and a be subsets of a. then &(1)IfA,cA2, then f(ACf(A,2) (2)f(A1A2)f(A1)f(A2) (3)f(A1UA2)=f(A1)∪f(A2) (4)f(A1)-f(A2)∈f(A1-A2) o Proof:(3)(afADUf(AcA, UA2) 令(b)fA1UA2)∈fA1Uf(42)

❖Theorem 3.1: Let f be an everywhere function from A to B, and A1 and A2 be subsets of A. Then ❖(1)If A1A2 , then f(A1 ) f(A2 ) ❖(2) f(A1∩A2 ) f(A1 )∩f(A2 ) ❖(3) f(A1∪A2 )= f(A1 )∪f(A2 ) ❖(4) f(A1 )- f(A2 ) f(A1 -A2 ) ❖ Proof: (3)(a) f(A1 )∪f (A2 ) f(A1∪A2 ) ❖ (b) f(A1∪A2 ) f(A1 )∪f (A2 )

(4)f(A1)-f(4A2)Cf(A1-A2 今 for any y∈∫(A1)f(A2)

❖ (4) f (A1 )- f (A2 ) f (A1 -A2 ) ❖ for any y f (A1 )-f (A2 )

Theorem 3.2: Let f be an everywhere function from A to B, and A cA(i-1, 2,o.n). Then (1)f(4)=Uf(4) (2)f(4)∩f(4) i=1

❖ Theorem 3.2：Let f be an everywhere function from A to B, and AiA(i=1,2,…n). Then   n i i n i f Ai f A 1 1 (1) ( ) ( ) = = =   n i i n i f Ai f A 1 1 (2) ( ) ( ) = = 

2. Special Types of functions &o Definition 3.2: Let a be an arbitrary nonempty set. The identity function on A, denoted by a, is defined by la(a=a Definition 3.3. Let f be an everywhere function from A to B. Then we say that f is onto(surjective) ifRFB. We say that f is one to one(injective) if we cannot have fa-f(az) for two distinct elements a and a2 of A. Finally, we say that f is one-to-one correspondence(bijection), if f is onto and one-to one . &o The definition of one to one may be restated in the following equivalent form 今If(a1)=f(a2) then a1=a2 for all a1,a2∈AOr 令Ifa1≠a2 then j(a1)≠f(a2) for all a,a2∈A

❖ 2. Special Types of functions ❖ Definition 3.2：Let A be an arbitrary nonempty set. The identity function on A, denoted by IA, is defined by IA(a)=a. ❖ Definition 3.3.: Let f be an everywhere function from A to B. Then we say that f is onto(surjective) if Rf=B. We say that f is one to one(injective) if we cannot have f(a1 )=f(a2 ) for two distinct elements a1 and a2 of A. Finally, we say that f is one-to-one correspondence(bijection), if f is onto and one-to￾one. ❖ The definition of one to one may be restated in the following equivalent form: ❖ If f(a1 )=f(a2 ) then a1=a2 for all a1 , a2A Or ❖ If a1a2 then f(a1 )f(a2 ) for all a1 , a2A

Example: 1) Let R(the set of real numbers)C(the set of complex number), fa=ial; 令2)Letg:R( the set of real numbers→C(the set of complex number), ga=ia; 今3)Leth:Z一Zm={0,1,…m-1},h(a)= a mod n . s onto. one to one

❖ Example:1) Let f: R(the set of real numbers)→C(the set of complex number), f(a)=i|a|; ❖ 2)Let g: R(the set of real numbers)→C(the set of complex number), g(a)=ia; ❖ 3)Let h:Z→Zm={0,1,…m-1}, h(a)=a mod m ❖ onto ,one to one?

%o 3.2 Composite functions and Inverse functions %o1 Composite functions o Relation, Composition, o Theorem3.3: Let g be a(everywhere)function from A to B, andf be a(everywhere)function from B to C. Then composite relation f og is a (everywhere)function from A to C

❖ 3.2 Composite functions and Inverse functions ❖ 1.Composite functions ❖ Relation ,Composition, ❖ Theorem3.3: Let g be a (everywhere)function from A to B, and f be a (everywhere)function from B to C. Then composite relation f g is a (everywhere)function from A to C

Proof:(1) For every a∈A, If there exist x, y∈C such that(a,x)∈ fogang(a2y)∈∫g, then x=y? (2) For any a∈A, there exists c∈ C such that (a2c)∈f? o Definition 3.4: Let g be a(everywhere) function from A to B, and f be a(everywhere) function from B to C. Then composite relation fog is called a(everywhere) function firom a to o, we write fog:A→C.Ifa∈A, then(°g)(a)=f(g(a)

❖ Proof: (1)For every aA, If there exist x,yC such that (a,x) f gand (a,y) f g，then x=y? ❖ (2)For any aA, there exists cC such that (a,c) f g ? ❖ Definition 3.4: Let g be a (everywhere) function from A to B, and f be a (everywhere) function from B to C. Then composite relation f g is called a (everywhere) function from A to C, we write f g:A→C. If aA, then(f g)(a)=f(g(a))

Since composition of relations has been shown to be associative(Theorem 20), we have as a special case the following theorem Theorem 3.4: Letf be a(everywhere) function from A to B, and g be a(everywhere) function from B to C, and h be a(everywhere) function from c to D. Then h°(g)=(h°g)°f

❖ Since composition of relations has been shown to be associative (Theorem 2.), we have as a special case the following theorem. ❖ Theorem 3.4: Let f be a (everywhere) function from A to B, and g be a (everywhere) function from B to C, and h be a (everywhere) function from C to D. Then h(gf )=(hg)f

Theorem 3.5: Letf be an everywhere function from a to B. Then 令(1)f i)lB°f=f s Property(i) is proved similarly to properr (a) 今 Proof Concerning(),leta∈A,(fIA)(a)?=f(

❖ Theorem 3.5: Let f be an everywhere function from A to B. Then ❖ (i)f IA =f. ❖ (ii)IB  f = f. ❖ Proof. Concerning(i), let aA, (f  IA)(a) ?=f(a). ❖ Property (ii) is proved similarly to property (i)