复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）06/30

定理:设函数fA→B,则f逆关系 是函数当且仅当是双射

• 定理：设函数f:A→B, 则f的逆关系 是函数当且仅当f是双射

定义34:设函数fA→B是双射,f的逆关 系称为f的逆函数,f1:B→A。若记 a)=b,则记f1(b)=a。 定理3.1:若函数FAB是双射,则f1 B→A也是双射。 证明:(1)f-是满射(1是B到A的函数,即 证明对任意a∈A,存在b∈B使得f1(b)=a) (2)f1是内射1是B到A的映射,即证明对任意 b,b2∈B当b1≠b2时有(b1)≠f1(b2) 采用反证法。 若存在b,b2∈B,b1≠b2,但f1(b1)=f(b2)=a 由此导出矛盾

• 定义3.4：设函数f:A→B是双射, f的逆关 系称为f的逆函数，f -1：B→A。若记 f(a)=b, 则记f -1 (b)=a。 • 定理3.1：若函数f:A→B是双射,则f -1： B→A也是双射。 • 证明：(1) f -1是满射(f -1是B到A的函数,即 证明对任意aA,存在bB,使得f -1 (b)=a) • (2) f -1是内射(f -1是B到A的映射,即证明对任意 b1 ,b2B,当b1b2时有f -1 (b1 ) f -1 (b2 ))。 • 采用反证法。 • 若存在b1 ,b2B,b1b2，但f -1 (b1 )= f -1 (b2 )=a。 • 由此导出矛盾

由(1)(2)知f是双射。 FA→B是双射,则f1:B→A是双射, 称是可逆函数

• 由(1)(2)知f -1是双射。 • f:A→B是双射,则f -1：B→A是双射, • 称f是可逆函数

定理32:若A→B是双射则(f)=f。 证明:因为是A到B的双射,所以f1是B到 A的双射。 因此()4是A到B的函数且为双射。 (--sf ∫∈(f) (f1)2=f

• 定理 3.2：若f:A→B是双射,则(f -1 ) -1=f 。 • 证明：因为f是A到B的双射,所以f -1是B到 A的双射。 • 因此(f -1 ) -1是A到B的函数且为双射。 • (f -1 ) -1 f , • f (f -1 ) -1 , • (f -1 ) -1= f

F定理36:若函数A→B存在逆函数/则 f=IA,foff 证明:若函数A→B存在逆函数f1则和f1 都是双射。 是A到B的函数,f是B到A的函数, 因此八是A到A的函数,I也是A到A的函数。 (是恒等函数,即IA(a)=a 对任意a∈A,(目标是证明fyf(a)=a 类似可以证明ff=IB

• 定理3.6：若函数f:A→B存在逆函数f -1 ,则 f –1  f =IA, f f -1=IB • 证明：若函数f:A→B存在逆函数f -1 ,则f和f -1 都是双射。 • f是A到B的函数，f -1是B到A的函数， • 因此f -1  f是A到A的函数，IA也是A到A的函数。 (IA是恒等函数，即IA(a)=a) • 对任意aA，(目标是证明f -1  f(a)=a) • 类似可以证明f f -1=IB

该定理告诉我们,对于给定的fA→B和 g:B→A,g是否为的逆函数,只要验证g f=I和fg=1是否成立。 定理37:设函数g:A→B,f:B→C都是双 射,则g)=glyf1 证明:因为g和都是双射所以由定理34 知/g是A到C的双射。因此(g)是C到A 的双射 因为g和郁都是双射所以由定理32知 g1是B到A的函数,f是C到B的函数。 因此gy1是C到A的函数。 对任意c∈C,目标是g)l(c)=glf(c)

• 该定理告诉我们，对于给定的f:A→B和 g:B→A，g是否为f的逆函数，只要验证g  f =IA和 f g=IB是否成立。 • 定理3.7：设函数g:A→B, f:B→C都是双 射,则(fg) -1= g -1  f -1 • 证明：因为g和f都是双射,所以由定理3.4 知fg是A到C的双射。因此(fg) -1是C到A 的双射。 • 因为g和f都是双射,所以由定理3.2知 • g -1是B到A的函数，f -1是C到B的函数。 • 因此g -1  f -1是C到A的函数。 • 对任意cC, 目标是(fg) -1 (c)=g -1  f -1 (c)

33集合的特征函数 定义3.7:设U是全集,且AcU,函数 vA:U→{0,4定义为: x∈ A V(x)= 0 x a 称v为集合A的特征函数

3.3 集合的特征函数 • 定 义 3 . 7 ： 设 U是全集 , 且 AU, 函 数 A:U→{0,1}定义为：      = x A x A x A 0 1  ( ) 称A为集合A的特征函数

定理3.8:设A和B是全集U的子集,对于所有 x∈U,下列各式成立: (1)yA(x)=0当且仅当A=∞; 证明:当A=②时,要证明vA(x)=0。 当对于所有x∈U成立vA(x)=0时,要证明A= (2)yA(x)=1当且仅当A=U (3)yA(x)≡vBx)当且仅当AcB; (4)对任意x∈U成立vA(x)=vB(x)当且仅当A=B;

• 定理3.8：设A和B是全集U的子集,对于所有 xU,下列各式成立: • (1)A(x)=0当且仅当A=; • 证明：当A=时，要证明A(x)=0。 • 当对于所有xU 成立A(x)=0时，要证明A= (2)A(x)=1当且仅当A=U; • (3)A(x)≦B(x)当且仅当AB; • (4)对任意xU,成立A(x)=B(x)当且仅当A=B;

(5YAB(X=YA(XOYB(X) (OYaUB(X=A(X)+YB(X)-YAOB(X); (7yx(x)=1-v4(x) (8VA -B()=WAoB(x)=vA(x)-VaoB(x) 这里与特征函数一起使用的符号≡,,+,, 都是普通算术运算符号; 与集合一起使用的符号是普通集合相等符 号;∩,U,是普通的集合运算符号

• (5)A∩B(x)=A(x)•B (x); • (6)A∪B (x)=A(x)+B (x)-A∩B(x); (7) (x) 1 (x);  A = − A (8) (x) (x) (x) (x)  A−B = AB = A − AB 这里与特征函数一起使用的符号≦,=,+,-,• 都是普通算术运算符号; 与集合一起使用的符号=是普通集合相等符 号;∩,∪,-是普通的集合运算符号

例:设A是任意集合,B为A到{0,1}的 切函数所组成的集合。证明:存在P(A) 到B的双射

• 例：设A是任意集合，B为A到{0,1}的一 切函数所组成的集合。证明：存在P(A) 到B的双射