离散数学第4章PPT优秀课件.ppt

第4章 函数4.1 函数的基本概念函数的基本概念 4.2 特殊函数类特殊函数类4.3 逆函数逆函数第第4章章 函函 数数第4章 函数4.1 函数的基本概念函数的基本概念 4.1.1 函数的定义函数的定义 函数亦称映射或变换,其定义如下: 定义定义4.1―1 设X和Y是集合,一个从X到Y的函数f记为f:X→Y,是一个满足以下条件的关系:对每一x∈X,都存在唯一的y∈Y,使〈x,y〉∈f 　　〈x,y〉∈f通常记作f(x)=y,X叫做函数f的前域,Y叫做f的陪域.在表达式f (x)=y中,x叫做函数的自变元,y叫做对应于自变元x的函数值. .第4章 函数　　从定义可看出,X到Y的函数f和一般X到Y的二元关系的不同有以下两点: (1)X的每一元素都必须作为f的序偶的第一个成分出现. (2) 如果f(x)=y1和f(x)=y2,那么y1=y2.第4章 函数 通常我们也把函数f看作是一个映射(变换)规则,它把X的每一元素映射到(变换为)Y的一个元素,因而f(x)又叫做x的映象映象. 在定义一个函数时,我们必须指定前域,陪域和变换规则,变换规则必须覆盖所有可能的自变元的值.例如例如 f:I→I,f(x)＝0,如果x≤0;f(x)=x－1,如果x＞0 定义了一个函数.第4章 函数 如果函数的前域是有限的,那么可以通过列表或画有向图表述变换规则.例如 g:｛a,b,c,d｝→｛1,2,3｝ g(a)=1 g(b)=2 g(c)=2 g(d)=1 定义了一函数.或x g (x)a 1a 2c 2d 1第4章 函数图 4.1―1第4章 函数　　　定义 4.1―2 　设f:X→Y,g:W→Z,如果X=W,Y=Z,且对每一x∈X有f(x)=g(x)则称f=g. 函数相等的定义和关系相等的定义是一致的,它们必须有相同的前域与陪域和相等的序偶集合.例如 函数f:I→I,f(x)=x2和 函数f:｛1,2,3｝→I,f(x)=x2 是两个不同的函数.第4章 函数 图 4.1―2 第4章 函数 定义4.1―3 设f是从X到Y的函数,X′是前域X的子集,那么f(X′)表示Y的子集, f(X′)=｛y｜x(x∈X′∧y=f(x))｝叫做函数f下X′的映象.整个前域的映象f(X)叫做函数f的映象(或叫f的值域).　　　对任何函数f: X→Y，定义4.1-3含蓄地指定了另一函数F，F: ρ(X)→ρ(Y)，对任一X′　 X，F(X′)=｛y｜　 x(x∈X′∧y=f(x))｝。

f和F显然不是相同的函数，f的前域和陪域是集合X和Y，f映射X的元素到Y的元素; F的前域和陪域是集合ρ(X)和ρ(Y)， F映射X的子集到Y的子集，如图4.1-2所示第4章 函数图 4.1-3 第4章 函数 例例4.1-1 (1)假定f:｛a,b,c,d｝→｛1,2,3,4｝用图4.1―3定义. 那么f (｛a｝)=｛1｝; f (｛a,b｝)=｛1,3｝; f (｛a,b,c｝)=｛1,3｝; f (｛a,b,c,d｝)=｛1,3,4｝; f ( )=第4章 函数图 4.1―4第4章 函数 (2) 设f:I→I,x≤0时f (x)=0,x＞0时f (x)=x－1,那么: f (－1)=0, f (｛－1｝)=｛0｝ f (0)=0, f (｛0｝)=｛0｝ f (1)=0, f (｛1｝)=｛0｝ f (2)=1, f (｛1,2,3,…｝)=N f (3)=2, f (｛2,4,6,8…｝)=｛1,3,5,7…｝ f (4)=3, f (｛0.－1,－2,…｝)=｛0｝ …第4章 函数 通常用YX表示从集合X到集合Y的所有函数的集合,应用这样的符号有其方便之处,因为如果X和Y都是有限集合时,设｜X｜=m ,｜Y｜=N ,则｜YX｜=Nm = ｜Y｜｜X｜.这是因为对每个自变元,它的函数值都有N 种取法,故共有nm 种从X到Y的函数. 函数的前域X时常是某个集合叉积.具有前域 的函数f叫做n个变元的函数,在〈x1,x2,…,xn 〉上的f值用f (x1,x2,…,xn )表示,这里xi∈Xi.算术运算,诸如加,减,乘等都是二元函数的例子.这些函数通常用固定的符号表示.例如加法可表示为+(x,y),或x+y.第4章 函数 例4.1-2 (a)设X=｛a,b,…,z｝,Y=｛01,02,…,26｝,f:X→Y. f (a)=01,f (b)=02,…,f (z)=26.f是一个简单的编码函数. (b)S :N →N ,S (N )=N +1.S 叫皮亚诺后继函数. (c)X和Y是非空集合,P:X×Y→X,P(x,y)=x.P称为投影函数. (d)X和Y是非空集合,f:X→ρ(X×Y),f (x)=｛x｝×Y.函数值｛x｝×Y代表X×Y在x处的截痕,f叫截痕函数.(e) 如果X=,Y是任意集合,那么空关系是从X到Y的无义的函数,叫空函数.如果X≠而Y=,那么从X到Y的唯一关系是空关系,但这空关系不是从X到Y的函数.没有一个函数,它有非空的前域和空的陪域.第4章 函数 4.1.2 合成函数合成函数 关系可以合成.函数是关系,也可以合成,下述定理将证明由合成所得的关系确是一个函数.合成是获得新函数的常用方法之一,因为直接去定义一个具有一定性质的函数,有时不如利用两个具有一定性质的已知函数合成得出来得方便. 第4章 函数 定理定理 4.1―1 设g:X→Y和 f:Y→Z是函数, 那么合成函数f·g是从X到Z的函数 g:X→Y和f:W→Z且YW时, 如果需要也可定义合成函数f·g, 不一定要求Y=W., 对一切x∈X, (f·g)(x)=f(g(x)). 证证 因为f和g都是关系, f·g是从X到Z的关系. 所以我们只须证明对每一x∈X, 有一个唯一的z∈Z使

因为f是函数，对每一y∈Y，有一z∈Z使f(y)=z因为〈x，y〉∈g，〈y，z〉∈f，这得出〈x，z〉∈f·g再者，由于g和f都是函数，x唯一地确定y，y唯一地确定z，于是x唯一地确定z所以，〈x，z〉是以x为第一分量的合成关系f·g的唯一序偶这样，f·g是一函数，而(f·g)(x)=z=f(y)=f(g(x)) 第4章 函数 例例4.1-3 (1) 设g:｛a, b, c｝→｛A, B, C, D｝和 f :｛A, B, C, D｝→｛1, 2, 3｝, 用图4.1―4定义, 那么f ·g:｛a, b, c｝→｛1, 2, 3｝如图4.1―5所示. (2) 设g:｛0, 1, 2｝→N定义为g(x)=x+1, f :N→N定义为f (x)=3x+2, 则合成函数g·f 没有定义, 因为g的前域不等于f 的陪域. 然而, 合成函数f ·g是有定义的: f ·g:｛0, 1, 2｝→N, f ·g(x)=3x+5第4章 函数图 4.1―5 第4章 函数图 4.1―6第4章 函数 定定理理 4.1―2 函数合成是可结合的. 即f , g和h都是函数, 那么(f g)h=f (gh). 本定理是定理3.2―2的一个特殊情况. 另外附带指出, 今后讨论一个合成函数时, 我们总是假定它是有定义的, 对此不再说明. 如果对某集合X, f :X→X, 那么函数f 能同自身合成任意次. f 的n次合成定义如下: (1) f 0(x)=x, (2) f n+1(x)=f (f n(x)), n∈N. 第4章 函数 4.1.3 归纳定义的函数归纳定义的函数 当函数的前域是用归纳定义的集合时, 归纳法也是指定函数的方便和有效方法. 函数的定义随着前域的定义自然地得出. 例例 4.1-4 (a) 阶乘n! 的归纳定义如下: f :N→N (1) (基础)f (0)=1. (2) (归纳)f (n+1)=(n+1)f (n). 注意这里极小性条款是不必需的, 函数已经随着N的归纳定义而在整个前域上定义.第4章 函数 (b) N上的算术运算能利用后继函数归纳地定义. 例如加法运算可如下定义. +: N×N→N (1) (基础)+(m, 0)=m, 对任一m∈N. (2) (归 纳 )+(m, S(n))=S(+(m,n)), 或 写 成 +(m, n+1)=+(m, n)+1, m, n∈N. (c) 斐波那奇(F IbonaccI)序列 0, 1, 1, 2, 3, 5, 8, 13, 21, …第4章 函数 它具有如下性质, 即第二项之后的每一项都是前两项之和. 它能作为N上的函数F 归纳地定义. F :N→N (1) (基础) F (0)=0, F (1)=1. (2) (归纳) F (n+2)=F (n+1)+F (n), 对所有n∈N. 以上都是归纳定义的例子，例子的归纳步骤中函数值都用较“早”变元的函数值指定。

对k≠n，f(n)用f(k)表达的式子叫递归公式，用递归公式定义叫递归定义递归定义时k不一定都小于n例如以下著名的麦克卡茜(McCarthy)“91函数”是递归地(但不是归纳地)定义的 第4章 函数 例4.1-5 f :N→N f (x)=x－10, 对x＞100 f (x)=f (f (x+11)), 对x≤100 这个函数有如下特性, 对所有0≤x≤100, f (x)=91, 其它情况f (x)=x－10. 在归纳定义的集合上用递归(包括归纳)方法定义一函数, 所得未必是函数. 特别, 当前域的归纳定义允许某些元素能用多种方法构造时, 更易出现这一情况. 如果定义得满足函数定义, 我们说这函数是良定的. 当一函数是递归定义时, 常需证明它是良定的. 第4章 函数 例例4.1-6 设Σ=｛a, b, c｝, Σ+定义如下: (1) (基础) a∈Σ+, b∈Σ+, c∈Σ+; (2) (归纳) 如果x∈Σ+和y∈Σ+, 那么xy∈Σ+; (3) (极小性) Σ+是满足条款1和2的最小集合. 上述Σ+的定义允许用多于一种方法构造某些元素, 例如abc, 在归纳步骤中, 可以让x是a, y是bc, 再形成abc; 也可以让x是ab, y是c, 再形成abc. 第4章 函数 现在Σ+上如下地定义一函数f : f :Σ+→N (i) (基础) f (a)=1, f (b)=2, f (c)=3; (ii) (归纳) 如果x∈Σ+和y∈Σ+, 那么f (xy)=f (x)f (y). 这个函数不是良定的, 例如: f (bac)=f (b)f (ac)= = =2 f (bac)=f (ba)f (c)=(f (b)f (a))f (c)=(21)3=8 如果Σ+ 像2.3节那样定义, 那么以上这样地定义的函数就是良定的了. 递归定义的函数常能写出计算程序. 第4章 函数 4.1.4 偏函数偏函数 有时函数f :X′→Y的前域X′没有明晰指定, 但 X′ X和X却是明确的. 对于这种情况, 有以下定义. 定义4.1―4 X和Y是集合, X′ X, 从X′到Y的任一函数f 称为具有前域X, 陪域Y的偏函数. 而对任一 x∈X－X′, 说f (x)无定义. X′=X时, 也符合以上定义, 故函数也可看作偏函数. 有时为了强调此种情况而称为全函数. 但通常仍称全函数为函数, 仅当X′ X时称为偏函数. 第4章 函数例4.1-7 (a) 求实数方根的运算是从R到R的偏函数 , 对x＜0无定义. (b) 从R到R的偏函数 , 对自变元x=0和x=1无定义. (c) 计算机程序是偏函数, 此偏函数的自变元是程序的输入, 偏函数的值是程序的输出, 如果输入使程序不终止或不正常终止, 则对这样的输入偏函数无定义. 第4章 函数 4.1.5 函数前域的扩大和缩小函数前域的扩大和缩小 有时我们需要缩小所给函数的前域, 或扩大所给函数的前域以创建新的函数. 为此有以下定义. 定义4.1―5 设f :X→Y, X′ X, f 到X′的限制是一函数, 记为f ｜x′, 定义如下: 第4章 函数 定定义义4.1―6 设f :X′→Y, g:X→Y而X′X. 如果g｜x′=f , 那么, g是f 到前域X的开拓. 例4.1-8 设f :N→N, f (x)=2x, g:I→N, 那么, f 是g到N的限制, 即f =g｜N; g是f 到I的开拓. 时时第4章 函数 本节介绍具有一定性质的函数, 因为今后应用中遇到最多的正是它们. 定义4.2―1 设f 是从X到Y的函数. (a) 如果f (X)=Y, 那么f 是满射的(映到的). (b) 如果x≠x′蕴含着f (x)≠f (x′) (即f (x)=f (x′), 那么x=x′), 那么f 是单射的(一对一的). (c) 如果f 是满射的且是单射的(一对一和映到的), 那么f 是双射的. 具有这些性质的函数分别叫做满射函数, 单射函数和双射函数. 4.2 特殊函数类特殊函数类第4章 函数 如果f :X→Y是满射的, 那么每一元素y∈Y是在f 的象中. 如果f 是单射的, 那么前域不同的元素映射到陪域不同的元素. 如果f 是双射的, 那么Y的每一元素y是且仅是X的某个元素x的映象, 常称双射为一一对应. 图 4.2―1用以说明定义4.2―1中各类函数的概念, 函数的前域和陪域分别用左边的和右边的一列小圆点表示. (a)是单射的但不满射, (b)是满射的但不单射, (c)是双射的. 显然, 如果f 是满射的, 那么至少有一条弧终止于陪域的每一个元素. 如果f 是单射的, 那么终止于陪域的每一元素的弧不多于一条. 如果f 是双射的, 那么有且只有一条弧终止于陪域的每一元素.第4章 函数 图 4.2―1第4章 函数 例4.2-1 (a) 皮亚诺函数S:N→N, S(n)=n+1是单射函数但不满射, S的映象是N的真子集｛1, 2, …｝. (b) g:［0, 1］→［a, b］, 这里a＜b, g(x)=(b－a)x+a是双射函数. (c) h:R→R, f (x)=x3+2x2是满射函数但不单射. 因为每一水平线横截图形至少一次, 而有些地方多于一次(参看图4.2―2). 第4章 函数 图 4.2―2 第4章 函数 定理定理4.2―1 设g:X→Y和f :Y→Z是函数, f g是合成函数. (a) 如果f 和g是满射的, 那么f g是满射的. (b) 如果f 和g是单射的, 那么f g是单射的. (c) 如果f 和g是双射的, 那么f g是双射的. 证证 (1) 任取z∈Z, 因f 是满射的, 存在y∈Y, 使f (y)=z; 又因g是满射的, 存在x∈X, 使g(x)=y. 于是f g(x)=f (g(x))=f (y)=z, 所以z∈f g(X). 因为z是任意的, 这就证明了(a)部分. 第4章 函数 (2) 设x1, x2是X的两个不同的元素, 因为g是单射的, 推得g(x1)≠g(x2); 又因f 是单射的且g(x1)≠g(x2), 推得f g(x1)≠f g(x2). 所以, x1≠x2蕴含着f g(x1)≠f g(x2). 这证明了(b)部分. (3) 因为f 和g是双射的, 它们都是满射和单射的. 从(a)和(b)得f g是满射和单射的, 所以是双射的. 证毕. 第4章 函数 例4.2-2 (a) 设E是偶整数集合, M是奇整数集合. 双射函数f 和g定义如下: g:I→E, g(x)=2x f :E→M, f (x)=x+1 因为f 和g都是双射函数, 故合成函数 f g:I→M, f g(x)=2x+1. 也是双射函数. 第4章 函数 (b) 设 则g, f 都是单射函数, 于是 第4章 函数 定理4.2―1的每一部分的逆定理都不真, 但有下述“部分逆定理”. 定理4.2―2 设f g是合成函数, (a) 如果f g是满射的, 那么f 是满射的. (b) 如果f g是单射的, 那么g是单射的. (c) 如果f g是双射的, 那么f 是满射的而g是单射的. 第4章 函数 定义4.2―2 对函数f :X→Y, 如果存在y∈Y使对每一x∈X有f (x)=y, 即f (X)=｛y｝, 那么f 称为常函数. 定义4.2―3 如果函数f :X→X对一切x∈X有f (x)=x, 则称f 为X上的恒等函数, 通常记为1x. 恒等函数是双射函数. 定理4.2―3 设f :X→Y是函数, 那么, f =f · 1x =1Y·f . 第4章 函数 定义4.2―4 X上的双射函数称为X上的置换或排列. 例3 (a) 一集合X上的恒等函数是一个置换, 并被称作么置换, 或恒等置换. (b) 函数f :｛1, 2, 3｝→｛1, 2, 3｝, 这里f (1)=2, f (2)=1, f (3)=3是一置换. (c) 函数f :I→I, f (x)=x+5, 是整数集合上的一个置换. 第4章 函数 当集合X是无限集时, X上的置换称为无限次的, 当集合X是有限集时, 若｜X｜=n; 则X上的置换称为n次的. n次置换常写成的形式(可以任意交换列的次序). 如例3(b)可写成第4章 函数 定定理理4.2―4 在n个元素的集合中, 不同的n次置换有n! 个. 证 用归纳法. 为了叙述方便, 我们把P:X→X记成P:X→Y. 当n=1时, X=｛x1｝, Y=｛y1｝, 于是X→Y的双射函数的数目等于1! =1. 设从n个元素的集合到n个元素的集合的双射函数的数目等于n! 个. 现在考察 X=｛x1, x2, …, xn, xn+1｝, Y=｛y1, y2, …, yn, yn+1｝, 我们可以把从X到Y的所有双射函数分割成如下n+1个不相交的集合. 第4章 函数 例4 设A=｛1, 2, 3｝, 则A上的所有置换为: 因为置换是双射函数, 而双射函数的合成是双射函数, 所以置换的合成是置换. 换言之, 置换在合成运算下封闭. 例如第4章 函数 定义4.2―5 设 U是全集合(论述域), 对每一AU, 函数ΨA:U→｛0, 1｝定义为ΨA(x)= 1 如果 x∈A 0 如果 x∈A 称它是集合A的特征函数. 特征函数ΨA(x)的前域U一般隐含在讨论的问题中, 不明确指定. 第4章 函数例4.2-5 (a) 设U=｛a, b, c, d｝, A=｛b, d｝, ΨA:U→｛0, 1｝则 ΨA(a)=0, ΨA(b)=1, ΨA(c)=0, ΨA(d)=1. (b) 设U=［0, 1］, A= [ ,1] , ΨA:U→｛0, 1｝则 ΨA(x)= 1 当 ≤x≤1时 0 当0≤x＜ 时第4章 函数 图 4.2―3第4章 函数 定定理理4.2―5 设A和B是全集合U的任意两个子集, 于是, 对所有x∈U, 下列关系式成立. (a) x(ΨA(x)=0) A= (b) x(ΨA(x)=1) A=U (c) x(ΨA(x)≤ΨB(x))A B (d) x(ΨA(x)=ΨB(x))A=B (E) Ψ (x)=1－ΨA(x) (f ) ΨA∩B(x)=ΨA(x)ΨB(x) (g) ΨA∪B(x)=ΨA(x)+ΨB(x)－ΨA∩B(x) (h) ΨA－B(x)=ΨA∩ (x)=ΨA(x)－ΨA∩B(x)第4章 函数　　　证证 只证(f ), 其它留作练习. 当 x∈A∩B时 , x∈A且 x∈B, 所 以 ΨA∩B(x)=1, ΨA(x)=1, ΨB(x)=1, 公式成立. 当xA∩B时, x A或 x B, 所以ΨA∩B(x)=0, ΨA(x)=0或ΨB(x)=0, 公式也成立. 证毕. 第4章 函数例4.2-6(a) 利用特征函数证明集合上的命题. (I)证明 =A. 证 Ψ (x)=1－Ψ (x)=1－(1－ΨA(x)) =ΨA(x), 所以, =A. (II) 证明A∩(B∪C)=A∩B∪A∩C. 第4章 函数证 ΨA∩(B∪C)(x) =ΨA(x)ΨB∪C(x) =ΨA(x)(ΨB(x)+Ψc(x)－ΨB(x)Ψc(x)) =ΨA(x)(Ψ)B(x)+ΨA(x)ΨC(x)－ΨA(x)ΨB(x)ΨC(x) =ΨA∩B(x)+ΨA∩C(x)－ΨA∩B∩C(x) =ΨA∩B(x)+ΨA∩C(x)－Ψ(A∩B)∩(A∩C)(x) =ΨA∩B∪A∩C (x)所以, A∩(B∪C)=A∩B∪A∩C 第4章 函数 (b) 若f (x)只有有穷个值, 则称f (x)是简单函数, 可用特征函数表达简单函数. 设 f :A→B是函数, 而B=｛b1, b2, …, bn｝, b1, b2, …, bn互不相同. 定义Ai=｛x｜f (x)=bi｝, 1≤i≤n. 显然 而i≠j时Ai∩Aj= . 这样f (x)可表示为 第4章 函数4.3 逆函数逆函数 4.3.1 逆函数逆函数 给定一个关系R, 颠倒R的所有序偶, 得到逆关系 . 给定一个函数f , 颠崐倒f 的所有序偶, 得到的关系 却未必是函数. 例如, X=｛1, 2, 3｝, Y= ｛a, b, c｝, f =｛<1, a〉, <2, a〉, <3, c〉｝是一函数.而 =｛

记为f -1, 称f 是可逆的. 注意仅当f 是双射函数时逆函数才有定义. 定理4.3―2 设f :X→Y是可逆的, 则f -1·f =1X, f ·f-1=1Y. 证 设x的X的任一元素, 如果f (x)=y, 则f -1(y)=x. f -1·f (x)=f -1(f (x))=f -1(y)=x 所以, f -1·f =1X. 类似地, 设y是Y的任一元素, 如果f -1(y)=x, 则f (x)=y. f ·f -1(y)=f (f -1(y))=f (x)=y 所以, f ·f -1 =1Y. 定理4.3―3 如果f 是可逆的, 那么(f －1)第4章 函数 4.3.2 规范映射规范映射 设f :X→Y是一函数, X′ X, Y′ Y. 前已介绍过f (X′)的意义, 现在建立f －1(Y′)的意义. 定义4.3―2 设f :X→Y是函数且Y′ Y, 那么 表示X的子集, 叫做f 下Y′的逆象或前象. 第4章 函数 例例1 (a) 考 虑 图 4.3―1表 示 的 函 数 , 那 么 f －1(｛0｝)=｛b｝, f －1(｛0, 1｝)=｛a, b, c｝, f －1(｛2, 3｝)=｛d｝, f －1(｛2, 4｝)= . 注意f 没有逆函数. (b) 假 定 f :X→Y, 这 里 X=｛ 0, 1｝ , Y=｛ , ｛｝｝, f (0)=, f (1)=｛｝, 那么f －1用作双射函数f 的逆函数时 f －1(｛｝)=1 但是用作诱导出的从ρ(Y)到ρ(X)的函数时 f －1(｛｝)=｛0｝第4章 函数图 4.3―1第4章 函数 如果函数f :X→Y的前域X非空, 那末集合族 ｛f －1(｛y｝)｜y∈Y∧f －1(｛y｝)≠｝ 形成X的一个划分, 与此划分相关联的等价关系R可如下定义: x1Rx2 f (x1)=f (x2) 容易证明R符合等价条件. 我们称R为f 诱导的等价关系. 第4章 函数 定义定义4.3―3 设R是一集合X上的等价关系, 函数 g:X→X／R, g(x)=［x］R 叫做从X到商集X／R的规范映射. 例4.3-2 设X=｛a, b, c, d｝, Y=｛0, 1, 2, 3, 4｝, f :X→Y, f (a)=1, f (b)=0, f (c)=1, f (d)=3, 那么f 诱导的X上的等价关系R有等价类｛a, c｝, ｛b｝和｛d｝. (参看图4.3―1). 第4章 函数 从X到X／R的规范映射是函数g. g:｛a, b, c, d｝→｛｛a, c｝,｛b｝,｛d｝｝ g(a)=｛a, c｝, g(b)=｛b｝, g(c)=｛a, c｝, g(d)=｛d｝. 从这个例子可以看出, 给定一个函数f :X→Y, 可以在f 自身前域X上诱导出一个等价关系, 对此等价关系可以定义一个规范映射. 在计算机科学上这些概念有许多应用. 第4章 函数 4.3.3 单侧逆函数单侧逆函数 定义定义4.3―4 设h:X→Y和k:Y→X, 如果kh=1X, 那么k是h的左逆元(或左逆函数), h是k的右逆元(或右逆函数). 业已证明:如果f :X→Y是双射函数, 那么函数f －1存在且f －1·f =1X和f ·f －1=1Y. 因此, f －1既是f 的左逆元又是f 的右逆元, 为了强调也称它为双侧逆元. 仅双射函数才有双侧逆元, 而某些其它函数仅有单侧逆元. 下一定理说明单射函数存在左逆元, 满射函数存在右逆元. 第4章 函数 定理定理4.3―4 设f :X→Y, X≠, 那么 (a) f 有左逆元当且仅当f 是单射的. (b) f 有右逆元当且仅当f 是满射的. (c) f 有左逆元和右逆元当且仅当f 是双射的. (d) 如果f 是双射的, 那么f 的左逆元和右逆元相等. 证 (a) 必要性. 假设g是f 的左逆元, 那么gf =1X是单射的, 根据定理4.2―2(b), f 是单射的. 第4章 函数 充分性. 用构造性证明. 选取任意元素x0∈X, 定义g如下: g:Y→X g(y)=x 如果y∈f (X)和f (x)=y g(y)=x0如果y f (X) 函数g是良定的, 因为对每一自变元y∈Y恰有一个值被指定. 再者, 如果f (x)=y, 那么gf (x)=g(f (x))=g(y)=x. 所以g是f 的左逆元. 证毕. 由左逆元的构造方法可知, 左逆元不唯一. 例如在图4.3―2中, 函数g和h都是f 的左逆元. 第4章 函数图 4.3―2 第4章 函数 (b) 必要性. 假设g是f 的右逆元, 那么f g=1Y是满射的, 根据定理4.2―2(a), f 是满射的. 充分性. 用构造性证明. 定义g如下: g:Y→X, g(y)=x 这里的x是满足f (x)=y的任意一个确定的x. 函数g显然是良定的. 再者, 如果f (x)=y, 那么f g(y)=f (g(y))=f (x)=y. 所以g是f 的右逆元. 证毕. 由以上构造方法可知, 右逆元也不唯一, 请读者自己举出例子. 第4章 函数 (c) 部分从(a)和(b)立即得出, 现在证明(d)部分. (d) 假定f 是双射的具有右逆元h和左逆元g; 那么 g·f =1Z和f ·h=1Y, 根据定理4.2―3, g=g·1Y=g·f ·h=1X·h=h. 证毕. 定定理理4.3―5 设f :X→Y和g:Y→X, f －1存在且g=f －1当且仅当g·f =1X, f ·g=1Y. 证证 必要性是显然的, 因为f －1·f =1X和f ·f －1=1Y. 现证明充分性. 第4章 函数 g是f 的左逆元, 所以f 是单射的; g是f 的右逆元, 所以f 是满射的. 因而f 是双射的, f －1存在. 再者 g=1X·g=(f －1·f )g=f －1·(f ·g)=f －1·1Y=f －1 证毕. 本定理说明逆函数是唯一的. 定理4.3―6 设f :X→Y和g:Y→Z且f 和g都是可 逆的, 则 (g·f )－1=f －1·g－1。