离散数学第8章 函数

离散数学第8章 函数

CHAPTER Eight

离散数学Discrete Mathematics

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight

第八章 函数§8.1 函数的定义与性质

§8.2 函数的复合与反函数§8.3 双射函数与集合的基数§8.4一个电话系统的描述实例

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.1 函数的定义与性质

CHAPTER Eight

定义8.1 设 F 为二元关系，若 x domF 都存在唯一的 y ranF 使xFy 成立, 则称F为函数。 对于函数F, 如果 xFy,则记y =F(x),并称y为 F 在 x 的值。 例8.1 设F1={<x1,y1>, <x2,y1>, <x3,y2>},F2={<x1,y1>, <x1,y2>}. 则F1是函数， 而F2不是函数。

定义8.2 设F、G是函数，则 F=G F G∧ G F.

注：如果F=G,那么它们满足：(1) dom F=dom G; (2) x dom F = dom G都有F(x)= G(x). 定义8.3 设A, B为集合, 如果 f 是函数, 且 dom f=A,ran f B,

则 f 称为从A到B的函数，记作 f : A→B.6/2/2013 9:02 PM Discrete Math. , Chen Chen 3

离散数学第8章 函数

§8.1 函数的定义定义8.4 所有从 A 到 B 的函数的集合记作 BA,即 BA={f | f: A→B}. A m 注：1. 若 |A|=m, |B|=n, 则 | B | = n ; 2. ΦΦ ={Φ }, BΦ={Φ}, ΦA=Φ. 例8.2 见教材P137. 定义8.5 设函数 f : A→B,A1 A,B1 B.

CHAPTER Eight

(1) 令f (A1)={ f (x)| x A1}. 称f (A1)为A1在 f 下的像。特别地，当A1=A时，称f (A)为函数的像.

(2) 令f –1(B1)={x| x A∧f(x) B1},称f –1(B1)为B1在 f 下的完全原像。例8.3 见教材P137.Discrete Math. , Chen Chen

6/2/2013 9:02 PM

离散数学第8章 函数

§8.1 函数的性质定义8.6 设 f : A→B. (1) 若 ran f =B,则称 f 是满射.

CHAPTER Eight

(2) 若 y ran f 都存在唯一的 x A使得f (x)=y,则称f 是单射. (3) 若 f 既是满射又是单射，则称 f 是双射(一一映射). 注： 1. 如果 f 是满射，则对 y B,都存在x A,使 f (x)=y

2. 如果 f 是单射，则对x1, x2 A,x1≠x2 , 必定f (x1) ≠f (x2)也就是说，如果f (x1) =f (x2),则 x1=x2。

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight例8.4 判断下列函数是否为单射、满射、双射.(1) f : R R, f ( x) x 2 x 1.2

(2) f : Z R, f ( x) ln x, Z 为正整数集. (3) f : R Z , f ( x) x . (4) f : R R, f ( x) 2 x 1. (5) f : R R , f ( x)

x 12

, 其中R 为正实数集.

x

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight解：(1) f : R R, f ( x) x 2 x 1是开口向下的抛物线。2

在x=1处取得最大值0,既不是单射，也不是满射. (2) f :Z

R, f ( x) ln x是单调增函数,是单射, 但不是

不是满射，因ranf {ln1, ln 2,...,} R. (3) f : R Z , f ( x ) x 是满射，但不是单射. (4) f : R R, f ( x) 2 x 1是满射,也是单射,从而是双射. (5) f : R R , f ( x)

x 12

, 当x 0时，f ( x )

; 而

x 当x 时，f ( x ) .在x=1处f(x)取得极小值2。 故它既不是单射，也不是满射。6/2/2013 9:02 PM Discrete Math. , Chen Chen 7

离散数学第8章 函数

CHAPTER Eight例8.5 对如下给定的A, B和f, 判断 f 是否构成A到B的函数，如果 是，说明它是否为单射、满射和双射，并按要求进行计算。(1) A {1, 2, 3, 4, 5}, B {6, 7,8, 9,10}, f { 1,8 , 3, 9 , 4,10 , 2, 6 , 5, 9 }. (2) A, B同(1),f { 1, 7 , 2, 6 , 4, 5 , 1, 9 , 5,10 } (3) A, B同(1),f { 1,8 , 3,10 , 2, 6 , 4, 9 } (4) A B R, f ( x) x (5) A B R , f ( x) 3

x x 12

(6) A B R R, f ( x, y ) x y , x y . 令 L { x, y | x, y R y x 1}. 计算f ( L ). (7) A N N , B N , f ( x, y ) | x y |,2 2

计算 f ( N {0}), f6/2/2013 9:02 PM

1

({0}).Discrete Math. , Chen Chen 8

离散数学第8章 函数

CHAPTER Eight解 : (1) A {1, 2 , 3, 4 , 5} , B {6 , 7 , 8, 9 ,1 0} , f { 1,8 , 3,9 , 4 ,1 0 , 2 ,6 , 5,9 } . f 能 构 成 A到 B的 函 数 。 它 不 是 单 射 也 不 是 满 射 。 因 为 f ( 3 ) = f ( 5 ) = 9 , 且 7 r a n f . ( 2 ) A , B 同 (1), f { 1,7 , 2 ,6 , 4 ,5 , 1,9 , 5,1 0 } f 不 能 构 成 A 到 B 的 函 数 。 因 1,7 f 且 1,9 f . ( 3 ) A , B 同 (1), f { 1,8 , 3,1 0 , 2 ,6 , 4 ,9 } f 不 能 构 成 A 到 B 的 函 数 。 因 d o m f {1, 2 ,3, 4} A (4) A B R , f ( x) x 3

f 能 构 成 A到 B的 函 数 ， 且 是 双 射 。6/2/2013 9:02 PM Discrete Math. , Chen Chen 9

离散数学第8章 函数

CHAPTER Eight(5 ) A B R , f (x) x x 2 1

f 能 构 成 A 到 B的 函 数 ， 但 既 不 是 单 射 ， 也 不 是 满 射 。 因 f (2 3 ) f (2 1 3 ) , 且 在 x=1处 取 得 最 大 值 1 . 2 4

(6 ) A B R R , f ( x , y ) x y , x y . 令 L { x , y | x , y R y x 1} . 计 算 f ( L ). f 能 构 成 A 到 B的 函 数 ， 是 双 射 且 f ( L ) = { < 2 x + 1 , - 1 > | x R } (7 ) A N N , B N , f ( x, y ) |x 2 2 1 y | , 计 算 f ( N {0} ), f ({0} ).

f 能 构 成 A 到 B的 函 数 ， 但 既 不 是 单 射 ， 也 不 是 满 射 。 因 f ( 1,1 ) f ( 2 , 2 ) 0 , 且 2 r a n f . 2 f ( N {0} ) { f ( n ,0 )| n N } { n | n N } . f 1 ({0} ) { n , n | n N } .

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

CHAPTER Eight例8.6 对给定的集合A和B构造双射函数f :A→B.(1) A P ({1, 2 , 3} ), B {0 , 1} (3) A Z , B N ;{1 ,2 ,3 }

;

( 2 ) A [ 0 , 1], B [ 4 , ]; 21 1

( 4 ) A [ , 3 ], B [ 1

,1]. 2 2 解 : (1) A { , {1} , { 2} , {3} , {1, 2} , {1, 3} , { 2 , 3} , {1, 2 , 3} }

B { f 0 , f 1 , , f 7 } , 其 中 ： f 0 { 1, 0 , 2 , 0 , 3, 0 } , f 2 { 1, 0 , 2 ,1 , 3, 0 } , f 4 { 1, 0 , 2 ,1 , 3,1 } , f 6 { 1,1 , 2 ,1 , 3, 0 } , 令 f :A B使 得 : f ( ) f 0 , f ({1, 2 ,3} ) f 7 , f ({1, 2} ) f 4 , f ({1,3} ) f 5 , f 1 { 1, 0 , 2 , 0 , 3,1 } f 3 { 1,1 , 2 , 0 , 3, 0 } f 5 { 1,1 , 2 , 0 , 3,1 } f 7 { 1,1 , 2 ,1 , 3,1 }

f ({ 2 , 3} ) f 6 , f ({1} ) f 1 , f ({2} ) f 2 , f ({3} ) f 3 , .6/2/2013 9:02 PM Discrete Math. , Chen Chen 11

离散数学第8章 函数

CHAPTER Eight1 ( 2 ) A [ 0 ,1], B [ 1 , ] 4 2 令 f : [ 0 ,1] [ 1 , 1 ], f ( x ) x 1 4 2 4 (3) A Z , B N 将 Z 中 元 素 按 下 列 方 式 与 N中 元 素 对 应 Z: N: 0 0 -1 1 1 2 -2 3 2 4 -3 5 3 6 x 0 x 0

这种对应关系表示的函数是: ( 4 ) A [ , 3 ], B [ 1,1] 2 2 令3 f : [ , 2 ] [ 1,1], 2

2 x, f (x) 2 x 1,

f ( x ) s in x .12

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

定义8.7

CHAPTER Eight

(1) 设 f : A→B,如果存在c B使得对 x A都有f(x)=c,则称 f是常 函数; (2) 称A上的恒等关系IA为A上的恒等函数，对 x A,都有IA(x)=x.

(3) 设(A, ),(B, )为偏序集，f : A→B。若对 x1, x2 A,x1 x2 时有f(x1) f(x2),则称 f 是单调递增的；若对 x1, x2 A,x1 x2时 f(x1) f(x2),则称 f 是严格单调递增的，类似可定义单调 递减和严格单调递减函数.(4) 设A为集合,对 A' A,A' 的特征函数XA' : A→{0,1}定义为 1 X A'(a ) 0 a A' 否则

(5) 设R是A上的等价关系，令 g: A→A/R, g(a)=[a], ( a A), 称g是从 A到商集A / R的自然映射。6/2/2013 9:02 PM Discrete Math. , Chen Chen 13

离散数学第8章 函数

§8.2 函数的复合与反函数函数的复合也就是关系的右复合。 定理8.1设F,G是函数，则F。G也是函数，且满足 (1) dom(F。G)={x| x∈domF ∧ F(x) ∈domG} (2) x∈dom(F 。G) 有F 。G(x)=G(F(x)) 证明： (1) ∵ F,G是关系， ∴ F 。G也是关系。若 x∈ dom(F 。G) 有x F。G y1和x F 。G y2,则<x, y1 > ∈ F 。G ∧ <x, y2 > ∈ F 。G => t1(<x, t1 > ∈F∧ < t1 , y1 >∈G)∧ t2(<x, t2>∈F∧<t2, y2>∈G)

CHAPTER Eight

=> t1(<x, t1 > ∈ F ∧ < t1 , y1 >∈G) ∧ t2(<x, t2 > ∈ F ∧ < t2 , y2 > ∈ G)=> t1 t2( t1 = t2 ∧ < t1 , y1 > ∈ G ∧ < t2 , y2 > ∈ G) (∵ F为函数) => y1 =y2 (∵ G为函数)

∴ F 。G为函数。6/2/2013 9:02 PM Discrete Math. , Chen Chen 14

离散数学第8章 函数

§8.2 函数的复合与反函数(2)对于 x, x∈dom(F。G) => t y(<x, t >∈F∧<t , y>∈G) => t (x ∈ dom

(F)∧t=F(x) ∧t ∈ dom( G)) => x ∈ {x| x ∈ dom(F) ∧ F(x) ∈ dom( G)} 对于 x,x ∈ dom(F)∧F(x)∈dom( G) => <x,F(x)>∈F∧<F(x),G(F(x))>∈ G => <x, G(F(x))>∈F。G => x ∈ dom(F) ∧F。G(x)=G(F(x))

CHAPTER Eight

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.2 函数的复合与反函数

CHAPTER Eight

推论1 设F,G,H为函数，则(F。G) 。H和F。(G 。H)都是函数， 且 (F。G) 。H=F。(G 。H) 推论2 设f:A → B, g:B → C, 则f。g: A → C,且 x∈A都有 f。g(x)=g(f(x)) 。 定理8.2 设 f:A → B, g:B → C

(1) 若f:A→B, g:B→C 都是满射的，则f。g: A → C也是满射的。(2) 若f:A→B, g:B→C 都是单射的，则f。g: A → C也是单射的。 (3) 若f:A→B, g:B→C 都是双射的，则f。g: A → C也是双射的。

证明略，参见P143。

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.2 函数的复合与反函数定理8.3 设 f:A → B, 则有 f=f。IB=IA。f 证明: 由前定理知 f 。IB :A → B, IA。f :A → B 对于 <x,y>, <x,y> ∈f => <x, y > ∈ f ∧ y ∈ B

CHAPTER Eight

=> <x, y > ∈ f ∧ <y,y> ∈ B => <x, y > ∈ f 。IB <x,y> ∈ f 。IB => t (<x, t > ∈f ∧ < t , y > ∈ IB) => <x, t > ∈ f ∧ t=y => <x, y > ∈ f

∴ f=f。IB同理可证明 f=f。IA

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.2 函数的复合与反函数考虑： 任给函数F,那么它的逆F-1是函数吗？ 答:不一定。 如F={<1,2>,<3,2>}为一从{1,3}到{2}的函数，而

CHAPTER Eight

F-1 ={<2,1>,<2,3>}不再是函数，仅是一个关系。任给单射函数f:A → B ,那么它的逆f-1是函数吗？ 答: f-1 是从ranf到A的函数，而且是双射函数。但不一定是从B到A 的函数。 对于什么样的函数f:A → B的逆f-1才是从B到A的函数呢？

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.2 函数的复合与反函数定理8.4 设 f:A → B是双射的,则f-1也是双射的。 证明: 先证明f-1是从B到A的函数f-1 :B → A。

CHAPTER Eight

∵ f是函数 ∴ f-1是关系，且 domf -1 =ranf=B, ranf -1 =domf=A 对于 x ∈B= domf -1,若 y1,y2 ∈A使得,

<x, y1 > ∈f -1 ∧ <x, y2 > ∈f -1 成立,则< y1,x > ∈ f ∧ < y2 ,x> ∈ f => y1= y2 (∵ f是单射函数 ) ∴ f -1 是函数，而且是满射函数。

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.2 函数的复合与反函数再证明f-1 :B → A的单射性。 若 x1,x2 ∈B使得f-1 (x1)= f-1 (x2)=y,则 <x1, y > ∈f -1 ∧ <x2, y > ∈f –1 => < y,x1 > ∈ f ∧ < y ,x2> ∈ f

CHAPTER Eight

=> x1= x2 (∵ f是函数 )∴ f -1 是单射函数。 综上所述 f-1是双射的。

对于双射函数f:A→B ,称f-1:B→A是它的反函数。

6/2/2013 9:02 PM

Discrete Math. , Chen Chen

离散数学第8章 函数

§8.2 函数的复合与反函数

CHAPTER Eight

定理8.5 设f: A→B是双射, 则: f-1 f = IB, f f-1 = IA. 证 由定理8.4可知: f-1: B→A也是双射. 由定理8.1的推论2可知: f-1 f

: B→B, f f-1: A→A. 任取<x, y>, <x, y> f-1 f   t(<x, t> f-1∧<t, y> f)  t(<t, x> f∧<t, y> f)  x=y∧x, y B  (因为f是函数)   <x, y> IB 任取<x, y>, <x, y> IB   x=y∧x, y B  t(<t, x> f∧<t, y> f)  (f: A→B是双射)  t(<x, t> f-1∧<t, y> f)   <x, y> f-1 f 所以有f-1 f = IB. 同理可证: f-1 f = IA.6/2/2013 9:02 PM Discrete Math. , Chen Chen 21

本文来源：https://www.bwwdw.com/article/bt2j.html