离散数学及应用（第2版高等学校计算机专业规划教材）

作者简介

内容简介

第5章 函数 　　 　　 　　 　　 　　函数是一种特殊的关系，也称为映射，它在计算机科学与技术以及相关学科中有着重要的作用和广泛的应用。 　　最初开始使用“函数”一词的是莱布尼茨（Leibniz，1646—1716），用以描述曲线的一个相关量；而中文的“函数”一词由清朝数学家李善兰（1811—1882）译出。 　　本章主要介绍函数的定义、几种特殊的函数及相关性质、函数的运算以及常用的一些函数。 5.1 函数的定义 　　定义5.1 设f为集合A到B的二元关系, 若对于任意xDom(f)都存在唯一的yRan(f)使得(x, y)f成立，则称f为函数(function)，此时记y=f(x)，称x为自变量（argument），y为f在x的值（value）或x在f作用下的像（image）。函数也称作映射（mapping）或变换（transformation）。 　　注：A=A1A2…An时，一般也将f((x1, x2, …, xn))简记为f(x1, x2, …, xn)。 　　函数的定义如图5.1所示。 图5.1 函数 　　【例5.1】 R1={(1,1), (2,3), (4,1), (3,5), (5,3)}是函数，而R2={(1,1), (1,3), (4,1), (3,5), (5,3)}不是函数，因为R2(1)={1, 3}。 　　在函数R1中，R1(1)=1, R1(2)=3, R1(4)=1, R1(3)=5, R1(5)=3，于是R1也可以写作R1= {(1, R1(1)), (2, R1(2)), (4, R1(4)), (3, R1(3)), (5, R1(5))}。 　　【例5.2】 设A=B=，则、、都是函数。 　　注：两个函数f和g相等当且仅当满足下面两个条件： 　　（1）Dom(f) = Dom(g)。 　　（2）对于任意xDom(f) = Dom(g)都有f(x) = g(x)。 　　例如，函数f(x)=(x2-1)/(x-1)和g(x)=x+1不相等，因为Dom( f )Dom(g)。 　　定义5.2 设A、B是非空集合，f是A到B的一个关系，如果对每个xA，存在唯一的yB，使得(x, y)f，则称f为A到B的函数，记作f : A→B。 　　注：对于A到B的函数f，Dom( f )=A，Ran( f )B。 　　如果一个A到B的关系是函数，则它的关系矩阵中每一行至多有一个1；如果它是一个A到B的函数，则它的关系矩阵每一行恰好有一个1。 　　如果一个A上的关系是函数，则它的关系图中每一个顶点至多发出一条有向边（出度不超过1）；如果它是一个A上的函数，则它的关系图中每一个顶点恰好发出一条有向边（出度恰为1）。 　　【例5.3】 设A=B=，则是到的函数，而、则不是。 　　定义5.3 设函数f : A→B, A1A，则称f(A1) = { f(x) | xA1 }为A1在f下的像（image of A1 under f），f(A)称为函数的像（image）。 　　【例5.4】 设函数f :→定义为f (1)=1，f (n)=n–1 (n>1)，则有f ({2,3})=f ({1,2,3}) = {1,2}。 　　下面定义一些常用的函数。 　　定义5.4 　　（a）设f: A→B，如果存在cB使得对所有的xA都有f(x)=c，则称f: A→B是常值函数。 　　（b）设A是非空集合，称A上的恒等关系IA为A上的恒等函数（identity function），也记作1A。即对于所有的xA，1A(x)=x。 　　（c）设R是A上的等价关系，定义从A到A/R的函数g: A→A/R，对任意aA， g(a)=[a]，即将元素映到该元素所在的等价类，称g是从A到商集A/R的典范映射（canonical map）或自然映射。 　　注：给定集合A和A上的一个等价关系R，就可以确定一个典范映射g: A→A/R。不同的等价关系确定不同的典范映射。 　　【例5.5】 定义函数g为g(x)=2，则g是到的常值函数。 　　【例5.6】 A={1, 2, 3}上的等价关系R={(1,1), (1,3), (2,2), (3,1), (3,3)}∪IA所确定的典范映射是g1(1) = g1(3) = {1, 3}, g1(2) = {2}；A={1, 2, 3}上的等价关系IA所确定的典范映射是g2(1)={1}, g2(2)={2}, g2(3)={3}。 5.2 函数的性质 　　定义5.5 设函数f : A→B。 　　（a）若Ran( f ) = B，则称f是满射（surjection）或映上的（onto）。 　　（b）若任意yRan( f )都存在唯一的xA使得f(x)=y，则称f: A→B是单射（injection）或一一的（one-to-one）； 　　（c）若f既是满射又是单射，则称f是双射（bijection）或一一对应（one-to-one correspondence）。 　　函数的满射、单射和双射如图5.2所示。其中，(a)是满射，(b)是单射，(c)是双射。 “中国大学MOOC”平台“离散数学”课程指定教材