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

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

离散数学教案 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使得 <x,y>∈f。 <x,y>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>,<x,y2>,<X3y2>,F={<X,y>,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={<x1,y1>,<x2,y2>,<x3,y2>}，F2={<x1,y1>,<x1,y2>}，判断它们是否 为函数。 解 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>,<a2,b2>,<a3,b>}, 8={Kb,G>,<b2,C2>,<b,C3>,<b,C3>},则有 fo8={ka,G>,<a2,C2>,<a,C>},不难看出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>,<42,b>,<a,b2>},g={Kh,G>,<b,92>,<b,92>}, 则有f°g={Ka,G>,<4,G>,<a,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 一些特殊的函数类