《离散数学》课程教学资源（教案讲义）第四章 函数

离散数学教案 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组

离散数学教案 1 《离散数学》课程教学教案 内蒙古农业大学计算机与信息工程学院 《离散数学》课程建设组

离散数学教案 函数 一、学习目的与要求 通过本章的学习，深刻理解离散与连续的函数、关系、集合的概念，掌握集合基 数的概念。 二、知识点 1.函数基本概念： 2.逆函数和复合函数： 3.基数的概念： 4.可数集与不可数集： 5.基数的比较。 三、要求 1.识记 常函数、恒等函数、置换函数、特征函数、简单函数等基本概念。 2.领会 函数的基本概念、合成函数的性质及函数合成的方法、单射、满射和双射的定义、 性质及证明方法、逆函数的概念及主要性质。 四、主要内容 第4章函数 4.1函数的基本概念 4.1.1函数的定义 定义4.1.1设X和Y是集合，一个从X到Y的函数（映射或变换）记为 f:X→Y,是一个满足以下条件的关系：对每一x∈X,都存在唯一的y∈Y使得 ∈f。 ef通常记做y=f(x),X叫做函数f的前域，Y叫做函数f的陪域。 在表达式y=f(x)中，x叫做函数∫的自变元，y叫做函数∫对应于自变元x的函 数值。 注意：函数与关系的联系及区别 (①)函数是一种特殊的二元关系： (2)X的每一元素都必须作为∫的序偶的第一个成分出现： 2

离散数学教案 2 函数 一、学习目的与要求 通过本章的学习，深刻理解离散与连续的函数、关系、集合的概念，掌握集合基 数的概念。 二、知识点 1．函数基本概念； 2．逆函数和复合函数； 3．基数的概念； 4．可数集与不可数集； 5．基数的比较。 三、要求 1．识记 常函数、恒等函数、置换函数、特征函数、简单函数等基本概念。 2．领会 函数的基本概念、合成函数的性质及函数合成的方法、单射、满射和双射的定义、 性质及证明方法、逆函数的概念及主要性质。 四、主要内容 第 4 章 函数 4.1 函数的基本概念 4.1.1 函数的定义 定义 4.1.1 设 X 和 Y 是集合，一个从 X 到 Y 的函数（映射或变换）记为 f X Y : → ，是一个满足以下条件的关系：对每一 x X  ，都存在唯一的 y Y  使得   x y f , 。   x y f , 通常记做 y f x = ( ) ，X 叫做函数 f 的前域，Y 叫做函数 f 的陪域。 在表达式 y f x = ( ) 中， x 叫做函数 f 的自变元， y 叫做函数 f 对应于自变元 x 的函 数值。 注意：函数与关系的联系及区别 (1) 函数是一种特殊的二元关系； (2) X 的每一元素都必须作为 f 的序偶的第一个成分出现；

离散数学教案 (3)如果f(x)=y和，那么片=为。 (4)定义一个函数时，必须指定前域、陪域和变换规则。 例4.1.1设F1=(X1y>,,,F={,x1,y2>,判断它们是否 为函数。 解F1是函数，F2不是函数，因为对应于x1存在y1和y2满足XFy1和xF2y2, 与函数定义矛盾。 定义4.12设f:X→Y,g:W→Z是函数，如果X=W,Y=Z,且对每 一x∈X有f(x)=g(x),则称∫-g,即两个函数相等。 注：由上述定义可见：两个函数相等当且仅当它们有相同的前域、陪域和相等 的序偶集合。 例4.1.2函数F(x)=x2.1)/x+I)和G(x)=x-1是不相等的， 因为domF={xk∈RAx≠-1}而domG-R。domF≠domG. 定义4.1.3y上X:从集合X到Y的所有函数的集合记做了x,即 Yx={fIf:A→B}. 例4.12设A={1,2,3},B={a,b},求B4(共8个) 由排列组合的知识不难证明：若|A上m,1B上n,且m,n>0,则|B上m”。 当A或B中至少有一个集合是空集时，可以分成下面三种情况： (a).A=中且B=中，则B=Φ={Φ}： (b).A=D且B≠D,则B=B=D}: (C.A≠Φ且B=Φ，则B=Φ=D。 定义4.14设∫是从X到Y的函数，X'cX是前域X的子集，那么fX)为 陪域Y的子集，f(X)={Uy3x(x∈X'Af(x)=y)}叫做函数∫下X'的映象。整 个前域的映象f(X)叫做函数∫的映象（或叫做函数∫的值域）。 注意：函数的值和映象的区别：函数值f(x)eY,而映象f(X)二Y。 4.1.2函数的合成 函数是特殊的关系，可以利用关系的合成定义函数的合成运算。 3

离散数学教案 3 (3) 如果 1 f x y ( ) = 和，那么 1 2 y y = 。 (4) 定义一个函数时，必须指定前域、陪域和变换规则。 例 4.1.1 设 F1={,,}，F2={,}，判断它们是否 为函数。 解 F1 是函数，F2 不是函数，因为对应于 x1 存在 y1 和 y2 满足 x1F2y1 和 x1F2y2， 与函数定义矛盾。 定义 4.1.2 设 f X Y : → ，g W Z : → 是函数，如果 X W= ，Y Z = ，且对每 一 x X  有 f x g x ( ) ( ) = ，则称 f g = ，即两个函数相等。 注： 由上述定义可见：两个函数相等当且仅当它们有相同的前域、陪域和相等 的序偶集合。 例 4.1.2 函数 F(x)=(x2 -1)/(x+1)和 G(x)=x-1 是不相等的， 因为 domF={x|x∈R∧x≠-1} 而 domG=R。domF≠domG。 定义 4.1.3 Y 上 X ：从集合 X 到 Y 的所有函数的集合记做 X Y ，即 { | : } X Y f f A B = → 。 例 4.1.2 设 A = {1, 2,3}， B a b ={ , } ，求 A B （共 8 个） 由排列组合的知识不难证明：若 | | A m= ，| | B n = ，且 m n, 0  ，则 | | A n B m= 。 当 A 或 B 中至少有一个集合是空集时，可以分成下面三种情况： (a). A = 且 B = ，则 { } A B  =  =  ； (b). A = 且 B  ，则 { } A B B = =  ； (c). A  且 B = ，则 A A B =  =  。 定义 4.1.4 设 f 是从 X 到 Y 的函数， X X   是前域 X 的子集，那么 f X( ) 为 陪域 Y 的子集， f X y x x X f x y ( ) { | ( ( ) )}   =    = 叫做函数 f 下 X  的映象。整 个前域的映象 f X( ) 叫做函数 f 的映象（或叫做函数 f 的值域）。 注意：函数的值和映象的区别：函数值 f x Y ( ) ，而映象 f X Y ( )  。 4.1.2 函数的合成 函数是特殊的关系，可以利用关系的合成定义函数的合成运算

离散数学教案 定理4.11设g:X→Y,∫：Y→Z是函数，那么合成函数fg(简记为g) 是从X到Z的函数，对x∈X,了g(x)=f(g(x)》. 注意：函数合成的记法8与关系合成的记法次序相反。 定理4.1-2函数的合成是可结合的，即若f,8,h都是函数，则f(gh)=(g)h。 4.2特殊函数类 4.2.1函数的性质 定义4.2.1设∫是从X到Y的函数， ()如果f(X)=Y,那么∫是满射的（映到的）： (2)若x≠x蕴含f(x)≠f(x)(即f(x)=f(x)→x=x'),那么∫是单射的 (一对一的)： (3)如果f是满射的且是单射的（一对一的和映到的），那么∫是双射的。 具有这些性质的函数分别叫做满射函数、单射函数和双射函数。 例4.2.1(1)∫：R→R,f(x)=-x2+2x-1:(既不是单射也不是满射的) (2)f:Z→R,f(x)=m,Z为正整数集：（是单射的，但不是满射的） (3)fR→Z,f(x)=Lx」小：（是满射的，但不是单射的） (4)f:R→R,f(x)=2x-1:(是满射，单射，双射的) (⑤)f:R*→R,f(x)=(x2+1)/x,其中R为正实数集：（不是单射的也不 是满射的) 当x→0时，f(x)→+0：而当x→o时，也有f(x)→+0：在x=1处函 数f(x)取得极小值f)-2。所以该函数既不是单射的也不是满射的。 定理4.2-1 (1)如果f:A→B,g:B→C都是满射的，则fg=g:A→C也是满 射的： (2)如果f:A→B,g:B→C都是单射的，则fog=g:A→C也是单 射的： (3)如果f:A→B,g:B→C都是双射的，则fg=g:A→C也是双

离散数学教案 4 定理 4.1-1 设 g X Y : → ，f Y Z : → 是函数，那么合成函数 f g （简记为 fg ） 是从 X 到 Z 的函数，对  x X ， f g x f g x ( ) ( ( )) = 。 注意：函数合成的记法 fg 与关系合成的记法次序相反。 定理 4.1-2 函数的合成是可结合的，即若 f g h , , 都是函数，则 f gh fg h ( ) ( ) = 。 4.2 特殊函数类 4.2.1 函数的性质 定义 4.2.1 设 f 是从 X 到 Y 的函数， (1) 如果 f X Y ( ) = ，那么 f 是满射的（映到的）； (2) 若 x x   蕴含 f x f x ( ) ( )   （即 f x f x x x ( ) ( ) =  =   ），那么 f 是单射的 （一对一的）； (3) 如果 f 是满射的且是单射的（一对一的和映到的），那么 f 是双射的。 具有这些性质的函数分别叫做满射函数、单射函数和双射函数。 例 4.2.1 (1) f R R : → ， 2 f x x x ( ) 2 1 = − + − ；（既不是单射也不是满射的） (2) f Z R : + → ， ( ) x f x ln = ， Z + 为正整数集；（是单射的，但不是满射的） (3) f R Z : → ， f x x ( ) =     ；（是满射的，但不是单射的） (4) f R R : → ， f x x ( ) 2 1 = − ；（是满射，单射，双射的） (5) f R R : + + → ， 2 f x x x ( ) ( 1) / = + ，其中 R + 为正实数集；（不是单射的也不 是满射的） 当 x →0 时， f x( ) → + ；而当 x → + 时，也有 f x( ) → + ；在 x =1 处函 数 f x( ) 取得极小值 f (1) 2 = 。所以该函数既不是单射的也不是满射的。 定理 4.2-1 （1） 如果 f A B : → ， g B C : → 都是满射的，则 f g gf A C = → : 也是满 射的； （2） 如果 f A B : → ， g B C : → 都是单射的，则 f g gf A C = → : 也是单 射的； （3） 如果 f A B : → ， g B C : → 都是双射的，则 f g gf A C = → : 也是双

离散数学教案 射的： 证(1)任取c∈C,因为g:B→C是满射的，3b∈B使得g(b)=c:对于 这个b,由于f:A→B也是满射的，所以3a∈A使得f(a)=b,所以有 f°g(@)=gf(a》=gb)=c,从而证明了fg=g:A→C是满射的。 (2)假设存在x,x∈A使得∫g(x)=∫g(x2),则有 g(f(x)》=g(f(x),因为g:B→C是单射的，故f(x)=f(x):又由于 f:A→B也是单射的，所以x=x2:从而证明了∫og=g对：A→C是单射的。 (3)由(1)和(2)得证。 注意：该定理的逆命题不为真，即如果∫·g=g对：A→C是单射（或满射、双 射)的，不一定有∫：A→B,g:B→C都是单射（或满射、双射）的。 例4.2.2考虑集合A={a,a2,a},B={亿，b2,b,b},C={C,C2,C} 令f={ka,b>,,}, 8={Kb,G>,,,},则有 fo8={ka,G>,,},不难看出f:A→B和 f©g-g对：A→C都是单射的，但g:B→C不是单射的。 再考虑集合A={a,a2,a},B={h,b2,b},C={G,c2}, 令f={ka,b>,,},g={Kh,G>,,}, 则有f°g={Ka,G>,,},不难看出g:B→C和 ∫。g=g:A→C是满射的，但∫：A→B不是满射的。 定理4.2-2设8是合成函数， (1)如果是满射的，那么∫是满射的： (2)如果B是单射的，那么g是单射的： (3)如果8是双射的，那么∫是满射的而g是单射的。 4.2.2一些特殊的函数 定义4.2.2一些特殊的函数类

离散数学教案 5 射的； 证 （1） 任取 c C ，因为 g B C : → 是满射的，  b B 使得 g b c ( ) = ；对于 这个 b ，由于 f A B : → 也是满射的，所以  a A 使得 f a b ( ) = ，所以有 f g a g f a g b c ( ) ( ( )) ( ) = = = ，从而证明了 f g gf A C = → : 是满射的。 （2） 假设存在 1 2 x x A ,  使得 1 2 f g x f g x ( ) ( ) = ，则有 1 2 g f x g f x ( ( )) ( ( )) = ，因为 g B C : → 是单射的，故 1 2 f x f x ( ) ( ) = ；又由于 f A B : → 也是单射的，所以 1 2 x x = ；从而证明了 f g gf A C = → : 是单射的。 （3） 由(1)和(2)得证。 注意：该定理的逆命题不为真，即如果 f g gf A C = → : 是单射（或满射、双 射）的，不一定有 f A B : → ， g B C : → 都是单射（或满射、双射）的。 例 4.2.2 考虑集合 1 2 3 A a a a ={ , , }， 1 2 3 4 B b b b b ={ , , , }， 1 2 3 C c c c ={ , , }， 令 1 1 2 2 3 3 f a b a b a b =       { , , , , , }， 1 1 2 2 3 3 4 3 g b c b c b c b c =         { , , , , , , , } ，则有 1 1 2 2 3 3 f g a c a c a c =       { , , , , , } ，不难看出 f A B : → 和 f g gf A C = → : 都是单射的，但 g B C : → 不是单射的。 再考虑集合 1 2 3 A a a a ={ , , }， 1 2 3 B b b b ={ , , }， 1 2 C c c ={ , }， 令 1 1 2 2 3 2 f a b a b a b =       { , , , , , }， 1 1 2 2 3 2 g b c b c b c =       { , , , , , }， 则有 1 1 2 2 3 2 f g a c a c a c =       { , , , , , } ，不难看出 g B C : → 和 f g gf A C = → : 是满射的，但 f A B : → 不是满射的。 定理 4.2-2 设 fg 是合成函数， (1) 如果 fg 是满射的，那么 f 是满射的； (2) 如果 fg 是单射的，那么 g 是单射的； (3) 如果 fg 是双射的，那么 f 是满射的而 g 是单射的。 4.2.2 一些特殊的函数 定义 4.2.2 一些特殊的函数类

离散数学教案 (1)设f:X→Y,若存在yeY使得对x∈X都有f(x)=y,则称 f:X→Y是常函数。 (2)如果函数f:X→X对x∈X都有f(x)=x,那么f称为X上的恒等函 数，记为lx (3)设为偏序集，∫：X→Y,如果对x,x3∈A,x, ，其中R为集合的包含关系，≤为一般的小于等于关系。令 f:p({a,b})→0,1}，f()=f({a)=f({b;)=0,f({a,b;)=1,则f单调递 增，但非严格单调递增的。 (3)集合A的每一个子集A都对应于一个特征函数，不同的子集对应于不同的特 征函数。 例如，令A-{a,b,c,则有Ψa={Ka,1>,,}: 平={ka,0>,,}:Ψab={ka,1>,,}: 6

离散数学教案 6 (1) 设 f X Y : → ，若存在 y Y  使得对  x X 都有 f x y ( ) = ，则称 f X Y : → 是常函数。 (2) 如果函数 f X X : → 对  x X 都有 f x x ( ) = ，那么 f 称为 X 上的恒等函 数，记为 1X 。 (3) 设   X , ，   Y, 为偏序集， f X Y : → ，如果对 1 2   x x A , ， 1 2 x x 有 1 2 f x f x ( ) ( )  ，则称 f 为单调递增的；如果对 1 2   x x A , ， 1 2 x x 有 1 2 f x f x ( ) ( ) ，则称 f 为严格单调递增的。类似的也可以定义单调递减和严格单调 递减的函数。 (4) X 上的双射函数称为 X 上的置换函数或排列。 (5) 设 A 为集合，对   A A  ， A 的特征函数 : {0,1}  A A→ 定义为 1 ( ) 0 A x A x x A     =     。 (6) 若 f x( ) 只有有限个值，则称 f x( ) 为简单函数。 注：(1)设 f A B : → ，则 A B I f f I f = = ，特别地，若 f A A : → ，则 A A I f f I f = = (2) 大家都很熟悉实数集 R 上的函数，如 f R R : → ， f x x ( ) 1 = + ，它是单调 递增的和严格单调递增的，但它只是上面定义中的单调函数的特例。而在上面的定义 中，单调函数可以定义于一般的偏序集上。例如，给定偏序集   ({ , }), a b R ，   {0,1}, ，其中 R 为集合的包含关系，  为一般的小于等于关系。令 f a b : ({ , }) {0,1}  → ， f f a f b ( ) ({ }) ({ }) 0  = = = ， f a b ({ , }) 1 = ，则 f 单调递 增，但非严格单调递增的。 (3) 集合 A 的每一个子集 A 都对应于一个特征函数，不同的子集对应于不同的特 征函数。 例如，令 A a b c = { , , } ，则有 { } { ,1 , ,0 , ,0 } a  =       a b c ； { ,0 , ,0 , ,0 } abc  =        ； { , } { ,1 , ,1 , ,0 } a b  =       abc ；

离散数学教案 由于A的子集与特征函数的对应关系，可以用特征函数来标记A的不同的子集。 特征函数的性质 (I)A=Φ台x(w,(x)=0): (2)A=U台x(y(x)=1): (3)AcB台x(w,(x)≤w(x) (4)"nB(x)=(x)wa(x) 证： "0a(x)=1台x∈AnB白x∈AAx∈B台Ψ(x)=1AΨa(x)=1P"(xwa(x)=1 4.3.1逆函数的定义 注意：任意给定一个关系R,颠倒R的所有序偶，可得到逆关系R。 但给定一个函数∫，颠倒∫的所有序偶，得到的关系了却不一定是一个函数。 例4.3.1设∫={Kx,片>，}是从{：，x}到{y,乃2}的函数，但 了={K片，x>,}显然不是函数。 对于什么样的函数∫：A→B,它的逆f:B→A是从B到A的函数呢？ 定理4.31设f:A→B是从A到B双射函数，则f:B→A是从B到A双 射函数。 定理4.3-2设∫：A→B是双射的，则f。f=Ig,fof=14: 特别地，对于双射函数f:A→A,有f。∫=∫=14。 定义4.3.1设∫：A→B是从A到B双射函数，称逆关系了为∫的逆函数，记 为∫~，并称∫是可逆的。 定理4.3-3如果f是可逆的，那么(f)=∫。 4.3.2规范映射（自然映射） 定义4.3.1设f:X→Y是函数，且Y'二Y,那么(Y)={xf(x)eY为 X的子集，叫做∫在Y'下的逆象或前象。 注意：逆象和逆函数的区别，尽管两者都用记号∫~

离散数学教案 7 由于 A 的子集与特征函数的对应关系，可以用特征函数来标记 A 的不同的子集。 特征函数的性质 (1) ( ( ) 0) A x x =    =  A ； (2) ( ( ) 1) A U x x =   =  A ； (3) ( ( ) ( )) A B x x x       A B ； (4) ( ) ( ) ( ) A B A B    x x x = 。 证： ( ) 1 ( ) 1 ( ) 1 ( ) ( ) 1 A B A B A B      x x A B x A x B x x x x =        =  =  = 4.3.1 逆函数的定义 注意：任意给定一个关系 R ，颠倒 R 的所有序偶，可得到逆关系 R 。 但给定一个函数 f ，颠倒 f 的所有序偶，得到的关系 f 却不一定是一个函数。 例 4.3.1 设 1 1 2 1 f x y x y =     { , , , } 是从 1 2 { , } x x 到 1 2 { , } y y 的函数，但 1 1 1 2 f y x y x =     { , , , } 显然不是函数。 对于什么样的函数 f A B : → ，它的逆 1 f B A : − → 是从 B 到 A 的函数呢？ 定理 4.3-1 设 f A B : → 是从 A 到 B 双射函数，则 1 f B A : − → 是从 B 到 A 双 射函数。 定理 4.3-2 设 f A B : → 是双射的，则 1 B f f I − = ， 1 A f f I − = ； 特别地，对于双射函数 f A A : → ，有 1 1 A f f f f I − − = = 。 定义 4.3.1 设 f A B : → 是从 A 到 B 双射函数，称逆关系 f 为 f 的逆函数，记 为 1 f − ，并称 f 是可逆的。 定理 4.3-3 如果 f 是可逆的，那么 1 1 ( ) f f − − = 。 4.3.2 规范映射（自然映射） 定义 4.3.1 设 f X Y : → 是函数，且 Y Y   ，那么 1 f Y x f x Y ( ) { | ( ) } −   =  为 X 的子集，叫做 f 在 Y  下的逆象或前象。 注意：逆象和逆函数的区别，尽管两者都用记号 1 f −

离散数学教案 如果函数∫：X→Y的前域X非空，那么集合族 {∫({y)川y∈Y入()≠D;形成X的一个划分。与此划分相关联的等价关系 可定义为：x台f(x)=f(x) 易证，上述定义的关系符合等价条件，称R为∫诱导的等价关系。 定义4.32设R是一集合X上的等价关系，函数g:X→X/R,g(x)=[x]R 叫做从X到商集X/R的规范映射。 给定集合A和A上的等价关系R,就可以确定一个规范映射g:A→A/R:例 如A={L,2,3},R={,,,,}是A上的等价关系， 那么有g()=g(2)=1,2},g(3)=3}:不同的等价关系将确定不同的规范映射， 其中恒等关系所确定的规范映射是双射，而其他的规范映射一般来说只是满射。 4.3.3单侧逆函数 定义4.3.3设h:X→Y和k:Y→X,如果kh=1x,那么k是h的左逆元（或 左逆函数)，h是k的右逆元（或右逆函数）。 定理4.3-4设f:X→Y,X≠中，那么 (I)f有左逆元当且仅当f是单射的： (2)∫有右逆元当且仅当∫是满射的： (3)∫有左逆元和右逆元当且仅当∫是双射的： (4)如果∫是双射的，那么∫的左逆元和右逆元相等。 证明：（仙）必要性：假设g是∫的左逆元，那么g对=1x是单射的，所以∫是单 射的。 充分性：用构造法证明。选取任意元素x。∈X,定义函数g:Y→X如下： 「x如果y∈f(X)且f(x)=y 80)={民如果yef00 则函数g是良定的，因为对每一自变元yeY,恰有一个值被指定。 又因为如果f(x)=y,那么g(x)=g(f(x)》=g(y)=x,所以g是∫的左逆 元。 8

离散数学教案 8 如果函数 f X Y : → 的前域 X 非空，那么集合族 1 1 { ({ }) | ({ }) } f y y Y f y − −     形成 X 的一个划分。与此划分相关联的等价关系 可定义为： 1 2 1 2 x Rx f x f x  = ( ) ( ) 。 易证，上述定义的关系符合等价条件，称 R 为 f 诱导的等价关系。 定义 4.3.2 设 R 是一集合 X 上的等价关系，函数 g X X R : / → ， ( ) [ ]R g x x = 叫做从 X 到商集 X R/ 的规范映射。 给定集合 A 和 A 上的等价关系 R ，就可以确定一个规范映射 g A A R : / → ；例 如 A = {1, 2,3}， R =           { 1,1 , 2,2 , 3,3 , 1,2 , 2,1 } 是 A 上的等价关系， 那么有 g g (1) (2) {1, 2} = = ， g(3) {3} = ；不同的等价关系将确定不同的规范映射， 其中恒等关系所确定的规范映射是双射，而其他的规范映射一般来说只是满射。 4.3.3 单侧逆函数 定义 4.3.3 设 h X Y : → 和 k Y X : → ，如果 1X kh = ，那么 k 是 h 的左逆元（或 左逆函数）， h 是 k 的右逆元（或右逆函数）。 定理 4.3-4 设 f X Y : → ， X  ，那么 (1) f 有左逆元当且仅当 f 是单射的； (2) f 有右逆元当且仅当 f 是满射的； (3) f 有左逆元和右逆元当且仅当 f 是双射的； (4) 如果 f 是双射的，那么 f 的左逆元和右逆元相等。 证明：(1) 必要性：假设 g 是 f 的左逆元，那么 1X gf = 是单射的，所以 f 是单 射的。 充分性：用构造法证明。选取任意元素 0 x X  ，定义函数 g Y X : → 如下： 0 ( ) ( ) ( ) ( ) x y f X f x y g y x y f X   = =    如果 且 如果 ， 则函数 g 是良定的，因为对每一自变元 y Y  ，恰有一个值被指定。 又因为如果 f x y ( ) = ，那么 gf x g f x g y x ( ) ( ( )) ( ) = = = ，所以 g 是 f 的左逆 元

离散数学教案 (2)必要性：假设g是∫的右逆元，那么B=1y是单射的，所以∫是满射的。 充分性：用构造法证明。定义函数g:Y→X如下：g(y)=x,这里的x是满 足f(x)=y的任意一个确定的x。函数g显然是良定的。 又因为如果f(x)=y,那么g(y)=f(g(y)》=f(x)=y,所以g是∫的右逆 元。 (3)由(1)和(2)直接得到。 (4)假设f是双射的，具有右逆元h和左逆元g,那么g对=1x,h=1y,因此 8=gly=gh=1xh=h。 注：上述(1)中的左逆元和(2)中的右逆元不一定唯一。 例如：设f:{a,b}→{0，l2},f={ka,0>,},则 g={k0,a>,,},g={k0,a>,,}都是函数f的左逆 元。右逆元类似。 定理4.3-5设f:X→Y,g:Y→X,存在且g=当且仅当g对=1x, g=ly。 证明：(1)必要性：因为∫，∫=1x,f·f=1y,所以必要性显然成立。 充分性：由g=1x,尽=1y知g既是∫的左逆元，又是∫的右逆元。 g是∫的左逆元，所以∫是单射的：g是f的右逆元，所以∫是满射的：所以f 是双射的，存在，且g=1xg=(f.)g=f(fg)=.ly=。 注：该定理说明了函数的逆是唯一的。 定理4.3-6设∫：X→Y，g:Y→Z,且f和g都是可逆的，则 (gf)=fg

离散数学教案 9 (2) 必要性：假设 g 是 f 的右逆元，那么 1Y fg = 是单射的，所以 f 是满射的。 充分性：用构造法证明。定义函数 g Y X : → 如下： g y x ( ) = ，这里的 x 是满 足 f x y ( ) = 的任意一个确定的 x 。函数 g 显然是良定的。 又因为如果 f x y ( ) = ，那么 fg y f g y f x y ( ) ( ( )) ( ) = = = ，所以 g 是 f 的右逆 元。 (3) 由(1)和(2)直接得到。 (4) 假设 f 是双射的，具有右逆元 h 和左逆元 g ，那么 1X gf = ， 1Y fh = ，因此 1 1 Y X g g gfh h h = = = = 。 注：上述(1)中的左逆元和(2)中的右逆元不一定唯一。 例如：设 f a b :{ , } {0,1,2} → ， f a b =     { ,0 , ,2 } ，则 g a a b =       { 0, , 1, , 2, }， g a b b =       { 0, , 1, , 2, } 都是函数 f 的左逆 元。右逆元类似。 定理 4.3-5 设 f X Y : → ，g Y X : → ， 1 f − 存在且 1 g f − = 当且仅当 1X gf = ， 1Y fg = 。 证明：(1) 必要性：因为 1 1X f f − = ， 1 1Y f f − = ，所以必要性显然成立。 充分性：由 1X gf = ， 1Y fg = 知 g 既是 f 的左逆元，又是 f 的右逆元。 g 是 f 的左逆元，所以 f 是单射的； g 是 f 的右逆元，所以 f 是满射的；所以 f 是双射的， 1 f − 存在，且 1 1 1 1 1 ( ) ( ) 1 X Y g g f f g f f g f f − − − − = = = = = 。 注：该定理说明了函数的逆是唯一的。 定理 4.3-6 设 f X Y : → ， g Y Z : → ，且 f 和 g 都是可逆的，则 1 1 1 ( ) gf f g − − − =