离散数学 北京理工大学珠海学院 计算机学院 龚友明 函数的定义 设f是二元关系，如果对于任意xdomf，都 存在唯一的yranf，使得xfy成立，则称f为 函数（或者映射），这时也称y为f在x的值， 记作y=f(x) 函数相等 设f，g为函数，则 domf=domg xdomf=domg，都有f(x)=g(x) 示例：函数f与g分别是： f(x)=(x2-1)/(x+1)；g(x)=x-1 f与g不相等，因为domf不包含-1 离散数学-第5章 函数（北理珠本末终始） 函数：从集合到集合 设A，B为集合，如果 f为函数，domf=A，ranfB 则称f为从A到B的函数，记作f：AB 所有从A到B的函数的集合记作BA，符号化表示为： BA=f|f:AB，若|A|=m，|B|=n，m,n0，则|BA|=nm 示例（例5.2，P143） 设A=1，2，3，B=a，b，求BA 解：BA=f0,f1,f2,f7，其中 f0=, f1=, f2=, f7=, 说明：形如,，每个”?”部分有n种取法，所以 有nm 离散数学-第5章 函数（北理珠本末终始） 重要的函数 常函数 如果存在cB使得对所有xA都有f(x)=c，则称f:AB是常函数 恒等函数 恒等函数IA，对所有的xA都有IA(x)=x 单调递增与严格单调递增 设,为偏序集，f:AB，如果对任意的x1,x2A， x1x2，就有f(x1)f(x2),称f为单调递增。 如果对任意的x1,x2A，x1x2，就有f(x1) f(x2),称f为严格单调 递增。 特征函数 设A为集合，对于任意的AA，A的特征函数A：A0，1定 义为 A：(a)=1 aA A：(a)=0 aA-A 自然映射 R是A上的等价关系，令g：AA/R g(a)=a aA 称g是从A到商集A/R的自然映射 离散数学-第5章 函数（北理珠本末终始） 示示例：术例：术语语 K.H.ROSEN离散及其应用(第5版)P78 函数表示 f(x)=y f：AB，A到B的关系 f把A映射(maps)到B f：AB A是f定义域(domain) B是f的伴域(codomain) f(a)=b b是f的像(image) a是f的原像(preimage) A中元素所有像的集合：f的值域 (range) 示例 int floor(float real) 函数floor定义域：实数集合 伴域是整数集合 G函数，表示学生的成绩 G的定义域 domG=张三，李四，王五，赵六，刘七 G的伴域 A，B，C，D，E G的值域 A，B，C，E 离散数学-第5章 函数（北理珠本末终始） 定义域相同的函数“加”与“乘” 令f1和f2是从A到R的函数，那么f1+f2和 f1*f2也是从A到R的函数，其定义为 (f1+f2)(x)=f1(x)+f2(x) (f1*fw)(x)=f1(x)*f2(x) 离散数学-第5章 函数（北理珠本末终始） 单射函数(injective,One-to-One Functions) 函数f称为一对一的或单射 的，当且仅当对于f的定义 域中的所有x和y，f(x)=f(y) 蕴含着x=y。一对一的函数 (one-to-one)称为单射 (injective)。 xy(f(x)=f(y)x=y) xy(xyf(x)f(y) 示例：判断从Z到Z的函数 f(x)=x2是否是一对一的 f(1)=f(-1)=1，所以不是一对 一的。但若是从Z+到Z+则f是 一对一的。 示例：判断f(x)=x+1是不是 一对一的 当xy，x+1y+1；所以是一 对一的 严格单调递增或递减的函数 是一对一的。 离散数学-第5章 函数（北理珠本末终始） 张三A李四王五赵六BCDE一对一函数一对一函数满射函数(surjective,Onto Functions) 从A到B的函数f称为映 上函数(onto)或满射函 数(surjective)，当且仅 当对每个bB，有元素 aA使得f(a)=b. 伴域与值域相同。即伴域 中的每个元素都是定义域 中的某个函数的像。 离散数学-第5章 函数（北理珠本末终始） 张三A李四王五赵六BCD映上映上( (满射满射) )函数函数 Onto FunctionsOnto Functions Surfective FunctionsSurfective Functions刘七一一对应(双射) 若函数f既是一对一的 ，又是映上的，就说它 是一一对应(ont-to-one corespondence)或双射 的(bijection)。 恒等函数是双射的 假定f是从有限集A到它 自己的函数，如果f是 满射的，则f是双射的 离散数学-第5章 函数（北理珠本末终始） 张三A李四王五赵六BCDE一一对应函数一一对应函数( (双射双射) ) OneOne- -toto- -One Correspondences FunctionsOne Correspondences Functions bifective Functionsbifective Functions刘七反函数(Inverse Functions) 令f为从集合A到集合B的一 一对应，f的反函数用f-1表 示，于是在f(a)=b时f-1(b)=a 不是一一对应的函数没有反 函数，也称作不可逆的。 示例 令f为从整数集到整数集 的函数，使得f(x)=x+1。f 可逆吗？反函数是什么？ 解答： f可逆。y是x的像，y=x+1. 从而x=y-1,f-1(y)=y-1 离散数学-第5章 函数（北理珠本末终始） Aa=f-1(b)Bb=f(a)ff-1反函数反函数函数的复合(Compositions) 令f为从集合A到集合B的函数，g是 从集合B到集合C的函数，函数f和g 的复合用fOg表示，定义为 :(fOg)(a)=g(f(a) 示例： 令f和g为从整数集到整数集的函数 ，其定义为f(x)=2x+3和g(x)=3x+2。 求fOg和gOf。 解 (fOg)(x)=g(f(x)=g(2x+3)=3(x2+3)+2=6x+11 (gOf)(x)=f(g(x)=f(3x+2)=2(3x+2)+3=6x+7 交换律不成立 函数与它的反函数的合成都是恒等 函数。 (fOf-1)(a)=a (f-1Of)(a)=a 离散数学-第5章 函数（北理珠本末终始） AaBf(a)f(a)函数函数f f和和g g的复合的复合Cg(f(a)fgg(f(a)(fog)(a)习题习题 屈婉玲离散数学P152-P154 5.1 5.3 5.4 5.14 5.17 5.22 5.23 离散数学-第5章 函数（北理珠本末终始）