第3章函数

3.1函数的概念

3.1.1函数的定义
在许多情况下，需要对一个集合里的每个元素指定本集合或另一集合中的一个特定的元素。例如，由选修了程序设计实验课的学生组成的集合为{赵明，钱华，孙丽，李思，周军，吴敏}。一个学期结束，需要为选修了该实验课的每个学生确定一个{优，良，中，及格，不及格}中的元素作为实验课的成绩，如图3.1所示。这些学生和成绩之间的关系就是函数的一个例子。
函数是最基本的数学概念之一，也是最重要的数学工具。连续变量函数或实函数在微积分学中的地位是众所周知的，离散对象之间的函数关系在计算机科学研究中有着极其重要的意义。
定义3.1设f是集合A到B的关系，如果对每个x∈A，都存在唯一的y∈B使得<x，y>∈f，则称关系f为集合A到B的函数(function)或映射(mapping)，记为f： A→B或y=f(x)。并称x为函数f的自变量(argument)或源点，y为x在函数f下的函数值(value)或像点(individual image)。集合A称为函数f的定义域(domain)，记为dom f=A。所有像点组成的集合称为函数f的值域(range)或函数f的像(image)，记为ran f或f(A)。
函数定义的示意图如图3.2所示。


图3.1实验课成绩的确定




图3.2集合A到B的函数f


由定义3.1可知，函数是一种特殊的关系，它要求A中每个元素都与B中一个且仅一个元素相关。同时，也可以通过集合A上的关系，定义出集合A到A的函数。
例3.1对于图3.1所描述的学生与成绩的关系，试写出该函数的定义域和值域。
解令集合A={赵明，钱华，孙丽，李思，周军，吴敏}，集合B={优，良，中，及格，不及格}。由图3.1可知，f为A到B的函数，表示在程序设计实验课上各个学生与成绩的关系，如f(赵明)=优。可知，f的定义域是dom f={赵明，钱华，孙丽，李思，周军，吴敏}； f的值域是ran f={优，良，及格，不及格}，因为除了“中”以外，每个成绩值都被确定给了某个学生。





例3.2设集合A={1，2，3，4}和B={a，b，c，d}，判断下列A到B的关系哪些是函数，并写出函数的值域。
① f1={<1，a>，<2，a>，<3，d>，<4，c>}。 
② f2={<1，a>，<2，a>，<2，d>，<4，c>}。 
③ f3={<1，a>，<2，b>，<3，d>，<4，c>}。 
④ f4={<1，a>，<2，b>，<2，c>，<3，d>，<4，c>}。 
⑤ f5={<2，a>，<2，b>，<2，c>，<2，d>，<3，b>，<4，c>}。 
⑥ f6={<1，a>，<2，b>，<3，a>，<4，b>}。
解① f1是函数，值域为f1(A)={a，c，d}。 
② f2不是函数，因为元素3没有像点，且元素2在关系f2下的像点为a和d，即不存在唯一的像点。 
③ f3是函数，值域为f3(A)={a，b，c，d}。 
④ f4不是函数，因为元素2在关系f4下的像点为b和c，即不存在唯一的像点。 
⑤ f5不是函数，因为元素1没有像点，且元素2在关系f5下的像点为a、b、c和d，即不存在唯一的像点。 
⑥ f6是函数，值域为f6(A)={a，b}。
例3.3设集合A={“www.edu.cn”，“peking university”，“Guilin”，“discrete structure”，“function”，“range”}，f是集合A到整数集Z的函数，表示对每个字符串返回其长度。写出函数f的定义域和值域。
解由函数f的定义可知，该函数的定义域dom f=A，值域ran f={10，17，6，18，8，5}。
例3.4判断下列关系哪些是函数：
① f1={<x，y>| x∈N，y∈N，x+y<10}； 
② f2={<x，y>| x∈R，y∈R，|x|=y}； 
③ f3={<x，y>| x∈R，y∈R，x=|y|}； 
④ f4={<x，y>| x∈Z，y∈Z，y是x的2倍}； 
⑤ f5={<x，y>| x∈R，y∈R，|x|=|y|}； 
⑥ f6={<x，y>| x∈R，y∈R，x2=y}。
解根据函数的定义知，f2、f4和f6是函数。f1不是函数，因为f1既不满足定义域为N，又不满足唯一像点条件； f3不是函数，因为f3既不满足定义域为R，又不满足唯一像点条件； f5不是函数，因为f5不满足唯一像点条件。
由上面的几个例子，可以总结出函数的以下几个特点： 
① 定义域是集合A，而不能是集合A的任意一个真子集； 
② 对于定义域中的任意一个元素都有唯一的值和其对应，也就是说只能是多对一，而不能是一对多，称之为像点的单值性； 
③ 集合A到B的函数f的值域f(A)是集合B的子集，即f(A)B； 
④ 集合A到B的函数f的基数等于其定义域的基数，即|f |=|A|； 
⑤ f(x)表示一个函数值，而f是一个序偶的集合，因此f(x)≠f。
例3.5对于集合A={1，2，3}和B={a，b}，试列写出A到B的所有函数和B到A的所有函数。
解设函数f： A→B，函数g： B→A。根据函数的定义，f(1)可以取a或者b两个值； f(1)取定一个值时，f(2)可以取a或者b两个值； 而f(2)取定一个值时，f(3)可以取a或者b两个值。因此，集合A到B可以定义出以下23种不同的函数：
f1={<1，a>，<2，a>，<3，a>}；f2={<1，a>，<2，a>，<3，b>}；
f3={<1，a>，<2，b>，<3，a>}；f4={<1，a>，<2，b>，<3，b>}；
f5={<1，b>，<2，a>，<3，a>}；f6={<1，b>，<2，a>，<3，b>}；
f7={<1，b>，<2，b>，<3，a>}；f8={<1，b>，<2，b>，<3，b>}。
同理，集合B到A可以定义出以下32种不同的函数：
g1={< a，1>，< b，1>}； g2={< a，1>，< b，2>}；
g3={< a，1>，< b，3>}； g4={< a，2>，< b，1>}；
g5={< a，2>，< b，2>}； g6={< a，2>，< b，3>}；
g7={< a，3>，< b，1>}； g8={< a，3>，< b，2>}；
g9={< a，3>，< b，3>}。
图3.3描述了函数的取值过程。


图3.3函数的取值过程


从例3.5可以看出，对于有限集合A和B，如果|A|=m和|B|=n，那么，集合A到B可以定义出nm种不同的函数。通常，将集合A到B的所有函数构成的集合记为BA，即
BA={f | f： A→B}
例3.6对于集合A={1，2，3}到B={a，b，c}的关系f={<1，a>，<2，b>，<3，c>}和g={<1，b>，<2，b>，<3，a>}，判断f、g、f∪g、f∩g、f-g、～f和fg是否为A到B的函数。
解根据函数的定义，f和g都是集合A到B的函数。
f∪g={<1，a>，<1，b>，<2，b>，<3，a>，<3，c>}不是集合A到B的函数，因为元素1和3都不满足唯一像点条件。
f∩g={<2，b>}不是集合A到B的函数，因为元素1和元素3都没有像点。
f-g={<1，a>，<3，c>}不是集合A到B的函数，因为元素2没有像点。
～f={<1，b>，<1，c>，<2，a>，<2，c>，<3，a>，<3，b>}不是集合A到B的函数，因为元素1、2、3都不满足唯一像点条件。
fg={<1，a>，<1，b>，<3，a>，<3，c>}不是集合A到B的函数，因为元素1和元素3都不满足唯一像点条件，且元素2没有像点。
例3.7
对于集合A={1，2，3}上的关系f={<1，1>，<2，2>，<3，3>}和g={<1，2>，<2，2>，<3，1>}，判断f、g、f∪g、f∩g、f-g、～f和fg是否为A到A的函数。
解根据函数的定义，f和g都是集合A到A的函数。
f∪g={<1，1>，<1，2>，<2，2>，<3，1>，<3，3>}不是集合A到A的函数，因为元素1和元素3都不满足唯一像点条件。
f∩g={<2，2>}不是集合A到A的函数，因为元素1和元素3都没有像点。
f-g={<1，1>，<3，3>}不是集合A到A的函数，因为元素2没有像点。
～f={<1，2>，<1，3>，<2，1>，<2，3>，<3，1>，<3，2>}不是集合A到A的函数，因为元素1、2、3都不满足唯一像点条件。
fg={<1，1>，<1，2>，<3，1>，<3，3>}不是集合A到A的函数，因为元素1和元素3都不满足唯一像点条件，且元素2没有像点。
通过例3.6和例3.7可以看出，函数是一种特殊的关系，可以进行关系的基本运算，但是，函数的并、交、差、补和对称差运算的结果并不一定是函数。
3.1.2特殊函数
函数描述了集合A中元素和集合B中元素之间的特殊对应关系。这种对应关系可以是一对一的或多对一的。同时，函数的值域可以是集合B的一个真子集，也可以是集合B自身。这些不同的情形，形成了下面一些特殊函数。
定义3.2设f是集合A到B的函数，对于A中任意两个元素x和y，如果x≠y时，都有f(x)≠f(y)，则称f是集合A到B的单射函数(injection)或一对一的映射。
例如，集合A={1，2，3}到B={a，b，c，d}的函数f={<1，a>，<2，b>，<3，c>}，对于A中任意两个元素x和y，如果x≠y时，都有f(x)≠f(y)。所以，f是集合A到B的单射函数。
定义3.3设f是集合A到B的函数，如果函数f的值域恰好是集合B，即f(A)=B，则称f是集合A到B的满射函数(surjection)或A到B上的映射。
例如，集合A={1，2，3}到B={a，b}的函数f={<1，a>，<2，b>，<3，a>}，函数的值域f(A)={a，b}=B。所以，f是集合A到B的满射函数。
定义3.4设f是集合A到B的函数，如果函数f既是集合A到B的单射函数又是集合A到B的满射函数，则称f是集合A到B的双射函数(bijection)或一一对应的映射。
例如，集合A={1，2，3}到B={a，b，c}的函数f={<1，a>，<2，b>，<3，c>}，对于A中任意两个元素x和y，如果x≠y时，都有f(x)≠f(y)。并且，函数的值域f(A)={a，b，c}=B。所以，f既是集合A到B的单射函数又是集合A到B的满射函数。因此，f是集合A到B的双射函数。
例3.8判断下列A到B的关系哪些是函数，并说明是单射函数、满射函数还是双射函数：
① 集合A={1，2，3}和B={a，b，c，d}，关系f1={<1，a>，<2，b>，<3，d>}； 
② 集合A={1，2，3}和B={a，b}，关系f2={<1，a>，<2，a>，<3，b>}； 
③ 集合A={1，2，3}和B={a，b}，关系f3={<1，a>，<2，a>，<3，a>}； 
④ 集合A={1，2，3}和B={a，b，c}，关系f4={<1，a>，<2，b>，<3，c>}； 
⑤ 集合A={1，2，3，4}和B={a，b，c}，关系f5={<1，a>，<2，b>，<3，a>，<4，c>}； 
⑥ 集合A={1，2，3}和B={a，b}，关系f6={<1，a>，<2，a>，<2，b>，<3，a>}。
解① f1是函数，且是单射函数。
② f2是函数，且是满射函数。
③ f3是函数，既不是单射函数，也不是满射函数。
④ f4是函数，且是单射函数、满射函数、双射函数。
⑤ f5是函数，且是满射函数。
⑥ f6不是函数。
例3.9判断下列函数是单射函数、满射函数还是双射函数：
① f： R→R，f(x)=-x2+2x-1；
② f： Z→Z，f(x)=|x|；
③ f： Z→Z，f(x)=x-1；
④ f： N→N×N，f(x)=<x，x+1>；
⑤ f： R+→R+，f(x)=(x2+1)/x，R+为正实数集；
⑥ f： Z+→R，f(x)=ln x，Z+为正整数集。 
解① f(0)=f(2)=-1，因此不是单射函数； f在x=1处取得最大值0，因此不是满射函数。
② f(1)=f(-1)=1，因此不是单射函数； f的像点都非负，因此不是满射函数。 
③ f是单射函数、满射函数、双射函数。 
④ f是单射函数； <0，0>ran f，因此不是满射函数。 
⑤ f(2)=f(1/2)=5/2，因此不是单射函数； f有最小值2，因此不是满射函数。 
⑥ f是单射函数； f的像点都非负，因此不是满射函数。
从例3.8和例3.9可以看出，若f是有限集A到有限集B的函数，则有：
① f是单射函数的必要条件是|A|≤|B|； 
② f是满射函数的必要条件是|B|≤|A|； 
③ f是双射函数的必要条件是|A|=|B|。
例3.10试证明以下论断： 若f是有限集A到有限集B的函数，且|A|=|B|，那么，f是单射函数当且仅当f是满射函数。
证明(必要性) 设f是单射函数。显然，f是A到f(A)的满射函数，故f是A到f(A)的双射函数，因此|A|=|f(A)|。从而，由|A|=|B|知|f(A)|=|B|。进而，由|f(A)|=|B|且f(A)B可得f(A)=B。所以，f是有限集A到有限集B的满射函数。
(充分性) 设f是满射函数。对于任意元素x、y∈A，x≠y，假设f(x)=f(y)。由于f是A到B的满射函数，所以f也是(A-{x})到B的满射函数，故|A-{x}|≥|B|，即|A|-1≥|B|，这与|A|=|B|矛盾。因此，f是有限集A到有限集B的单射函数。证毕。
例3.11对于有限集A和有限集B，设|A|=3、|B|=4，计算可定义多少种不同的A到B的单射函数。
解A到B的单射函数数目为4个元素中取3个的排列，即
P(4，3)=4!/(4-3)!=24
例3.12对于有限集A和有限集B，设|A|=4、|B|=3，计算可定义多少种不同的A到B的满射函数。
解如果把A中元素的两个元素“合并”成1个元素，即把A看作由3个元素组成的集合，由于从3个元素的集合到3个元素的集合可定义的双射函数为3！=6个，而4个元素“合并”成3个元素共有C(4，2)=6种方案，所以，根据乘法原理，A到B的满射函数数目共有6×6=36。
例3.13对于集合A={a，b，c，d}，计算可定义多少种不同的A到A的双射函数。
解为了便于分析问题，先画出双射函数的图形表示，如图3.4所示。
由图3.4可看出，a、b、c和d的一种排列就确定了A到A的一个双射函数，所以，A到A可定义的双射函数数目是4个元素的全排列，即4!=24。


图3.4双射函数的图形表示



3.2函数的运算
3.2.1复合运算
函数是一种特殊的关系，也应该能够进行关系的复合运算。那么，复合运算的结果是不是像基本运算那样，不一定是函数呢？回答是否定的。函数经复合运算后仍然是函数。
定理3.1对于集合A、B和C，f是A到B的关系，g是B到C的关系，如果f和g分别是A到B和B到C的函数，那么，复合关系fg是A到C的函数。
证明首先证明dom(fg)=A。
对于任意x∈A，由函数f： A→B知，必存在y∈B使得<x，y>∈f； 由函数g： B→C知，对于y∈B必存在z∈C使得<y，z>∈g； 因此，<x，z>∈fg，即x∈dom(fg)。因此，Adom(fg)。
又由复合关系fg的定义知，fg是A到C的关系，所以dom(fg)A。
所以，dom(fg)=A。
再证明fg的单值性。设任意x∈A，有z1∈C和z2∈C使得<x，z1>∈fg和<x，z2>∈fg，那么，有y1∈B和y2∈B使得<x，y1>∈f、<y1，z1>∈g、<x，y2>∈f和<y2，z2>∈g。由f为函数知y1=y2； 又由g为函数知z1=z2。所以，fg 为A到C的函数。证毕。
定义3.5对于集合A到B的函数f和集合B到C的函数g，复合关系fg称为函数f和函数g的复合函数(composition function)，记为fg： A→C。并称“”为函数的复合运算(composition operation)。
注意： <x，z>∈fg是指存在y使得<x，y>∈f和<y，z>∈g，即y=f(x)、z=g(y)=g(f(x))，因而 fg(x)=g(f(x))。这说明，当f和g为函数时，它们的复合作用于自变量的次序刚好与复合原始记号的次序相反。
例3.14设集合A={a，b，c，d}、B={b，c，d}和C={a，b，d}，集合A到集合B的函数f={<a，b>，<b，b>，<c，d>，<d，d>}，集合B到集合C的函数g={<b，a>，<c，d>，<d，b>}，求复合函数fg。
解依据复合函数的定义可以得到 
fg={<a，a>，<b，a>，<c，b>，<d，b>}
例3.15对于R到R的函数f(x)=2x+1和g(x)=x2+1，求fg、gf、ff和gg。
解依据复合函数的定义可以得到 
fg(x)=g(f(x))=(2x+1)2+1=4x2+4x+2
gf(x)=f(g(x))=2(x2+1)+1=2x2+3
ff(x)=f(f(x))=2(2x+1)+1=4x+3
gg(x)=g(g(x))=(x2+1)2+1=x4+2x2+2
例3.16对于函数f： A→B和g： B→C，证明以下论断： 
① 如果f和g是单(满、双)射函数，则fg是单(满、双)射函数； 
② 如果fg是单射函数，则f是单射函数； 
③ 如果fg是满射函数，则g是满射函数； 
④ 如果fg是双射函数，则f是单射函数，g是满射函数。
证明① 设f和g是单射函数。对于任意x1∈A和x2∈A，x1≠x2，由f是单射函数知，必有y1∈B和y2∈B，y1≠y2且y1=f(x1)、y2=f(x2)。又由g是单射函数知，z1∈C和z2∈C，z1=g(y1)，z2=g(y2)，必有z1≠z2。所以，g(f(x1))≠g(f(x2))，即fg(x1)≠fg(x2)。因此，fg是单射函数。
设f和g是满射函数。对于任意z∈C，由g是满射函数知，必有y∈B使得g(y)=z。又由f是满射函数知，必有x∈A使得y=f(x)。所以，必有g(f(x))=z，即fg(x)=z。因此，fg是满射函数。同理，可证得： 如果f和g是双射函数，则fg是双射函数。
② 设fg是单射函数，而f不是单射函数。那么，有x1∈A和x2∈A，x1≠x2，使得f(x1)=f(x2)。从而g(f(x1))=g(f(x2))，即fg(x1)=fg(x2)。与fg是单射函数矛盾。故f是单射函数。 
③ 设fg是满射函数，那么，对于任意z∈C，必有x∈A使得fg(x)=z，即g(f(x))=z。因此，必有y∈B，y=f(x)且g(y)=z。故g是满射函数。
④ 设fg是双射函数，由②知f是单射函数，由③知g是满射函数。证毕。
例3.17对于集合A={a1，a2，a3}、B={b1，b2，b3，b4}和 C={c1，c2，c3，c4}，函数f={<a1，b1>，<a2，b2>，<a3，b3>}和函数g={<b1，c1>，<b2，c2>，<b3，c3>，<b4，c3>}，可求得fg={<a1，c1>，<a2，c2>，<a3，c3>}。fg是单射函数，但g不是单射函数。
例3.18对于集合A={a1，a2，a3}，B={b1，b2，b3}和 C={c1，c2}，函数f={<a1，b1>，<a2，b2>，<a3，b2>}和函数g={<b1，c1>，<b2，c2>，<b3，c2>}，可求得fg={<a1，c1>，<a2，c2>，<a3，c2>}。fg是满射函数，但f不是满射函数。
例3.19对于集合A={a1，a2，a3}、B={b1，b2，b3，b4}和 C={c1，c2，c3}，函数f={<a1，b2>，<a2，b1>，<a3，b3>}和函数g={<b1，c1>，<b2，c2>，<b3，c3>，<b4，c3>}，可求得fg={<a1，c2>，<a2，c1>，<a3，c3>}。fg是双射函数，但g不是单射函数，f不是满射函数。
3.2.2逆运算
任意关系都可以进行逆运算得到其逆关系。但是对函数而言，就略有不同。由于在函数中一定要求dom f=A和A中每个元素有唯一的像点。所以，在对一个函数进行逆运算时，为了保证逆运算的结果仍是一个函数，就有相应的特殊要求。
定义3.6对于集合A到B的关系g，如果关系g是A到B的函数，且其逆关系g-1是B到A的函数，那么称g-1是函数g的逆函数(inverse function)或反函数，记为g-1： B→A。并称“-1”为函数的逆运算(inverse operation)。
例3.20判断下列函数哪些存在逆函数，并计算逆函数：
① 集合A={1，2，3}到B={a，b，c}的函数s={<1，c>，<2，b>，<3，a>}； 
② 集合A={1，2，3}到B={a，b，c，d}的函数f={<1，a>，<2，b>，<3，d>}； 
③ h={<x，x+1>| x∈Z}； 
④ g： Z→Z，g(x)=x+4； 
⑤ f： Z→Z，f(x)=2x+1； 
⑥ 集合A={1，2，3}到B={a，b}的函数g={<1，a>，<2，a>，<3，b>}。
解① 集合A={1，2，3}到B={a，b，c}的逆函数s-1={<c，1>，<b，2>，<a，3>}。
② 关系f-1={<a，1>，<b，2>，<d，3>}不是集合B={a，b，c，d}到A={1，2，3}的函数，所以，函数f不存在逆函数。
③ 逆函数h-1={<x，x-1>| x∈Z}。
④ 对于<x，x+4>∈g，应有<x+4，x>∈g-1。令x+4=y，可得x=y-4，即<y，y-4>∈g-1。所以，逆函数g-1(x)=x-4。
⑤ 对于<x，2x+1>∈f，应有<2x+1，x>∈f-1。令2x+1=y，可得x=(y-1)/2，即<y，(y-1)/2>∈f-1。f-1不是Z到Z的函数。所以，函数f不存在逆函数。
⑥ 关系g-1={<a，1>，< a，2>，<b，3>}不是集合B={a，b}到A={1，2，3}的函数，所以，函数g不存在逆函数。
定理3.2如果g是集合A到B的双射函数，则g的逆关系g-1是集合B到A的函数。
证明由于g为双射函数，那么g为满射函数，因此对于任意y∈B，必有x∈A使得g(x)=y，从而<y，x>∈g-1，这表明dom(g-1)=B。
对于任意y∈B，设<y，x1>∈g-1和<y，x2>∈g-1，那么g(x1)=g(x2)=y。由于g是双射函数，那么g是单射函数，必有x1=x2，从而g-1具有单值性。所以，g-1是集合B到A的函数。证毕。
例如，例3.20中①、③和④列出的都是双射函数，它们的逆关系都是函数； ②和⑤中的函数都是单射函数，但都不是满射函数，它们的逆关系都不是函数； ⑥中的函数是满射函数，但不是单射函数，它的逆关系不是函数。
例3.21双射函数及其逆函数是密码学中的重要工具，可用于密码系统中的加密与解密。假设函数f的定义如表3.1所示，即f(A)=R，f(B)=S，f(C)=T等。现有一段加密后的密文为“UZJTIVKVJKILTKLIV”，试对该密文进行解密，找出其加密前的原文，即明文。

表3.1函数f



xABCDEFGHIJKLM
f(x)
R
S
T
U
V
W
X
Y
Z
A
B
C
D
x
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
f(x)
E
F
G
H
I
J
K
L
M
N
O
P
Q
解由表3.1可知，函数f是一个双射函数。为了求出给定密文的明文，需求出函数f的逆函数f-1，按照f-1的对应关系依次还原对应的字母在函数f下的源点，即可得到该密文对应的明文。由表3.1可知，函数f的逆函数f-1如表3.2所示。

表3.2函数f-1



xABCDEFGHIJKLMf-1(x)
JKLMNOPQRST
U
V
x
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
f-1(x)W
X
Y
Z
A
B
C
D
E
F
G
H
I
将密文“UZJTIVKVJKILTKLIV”中的每个字母在函数f-1中找到其对应的像，就可以得到对应的明文，即“DISCRETESTRUCTURE”。
例3.22设集合A={0，1，2，3，4，5，6，7，8，9}，f和g均为A上的函数，且对于任意x∈A，f(x)=(x+5)(mod 10)，g(x)=(x+1)(mod 10)。若数字串按(f-1g)f的方式加密，试求数字串“26198750”加密后的密文，以及密文“19250683”加密前的数字串。
解由于(f-1g)f(x)=f(f-1g(x))=f(g(f-1(x)))，根据函数f和g的定义，对于任意x∈A，f(x)、g(x)、f-1(x)、g(f-1(x))和f(g(f-1(x)))的函数值如表3.3所示。

表3.3各函数值



x0123
4
5
6
7
8
9
f(x)
5
6
7
8
9
0
1
2
3
4
g(x)
1
2
3
4
5
6
7
8
9
0
f-1(x)
5
6
7
8
9
0
1
2
3
4
g(f-1(x))
6
7
8
9
0
1
2
3
4
5
f(g(f-1(x)))
1
2
3
4
5
6
7
8
9
0
由表3.3可知，数字串“26198750”加密后的密文为“37209861”。
为求解密文“19250683”加密前的数字串，首先求出解密函数。根据数字串的加密方式，可知解密函数为((f-1g)f)-1=f-1(g-1f)。
又因f-1(g-1f)(x)=(g-1f)(f-1(x))=f(g-1(f-1(x)))。对于任意x∈A，f(g-1(f-1(x)))的函数值如表3.4所示。
由表3.4可知，密文“19250683”加密前的数字串为“08149572”。

表3.4各函数值



x0123456789

f(x)
5
6
7
8
9
0
1
2
3
4
g(x)
1
2
3
4
5
6
7
8
9
0
f-1(x)
5
6
7
8
9
0
1
2
3
4
g-1(x)
9
0
1
2
3
4
5
6
7
8
g-1(f-1(x))
4
5
6
7
8
9
0
1
2
3
f(g-1(f-1(x)))
9
0
1
2
3
4
5
6
7
8



3.3函数的应用
哈希函数(Hash function)也称为散列函数或Hash函数，是一种将任意长度的输入字符串变换成固定长度的输出字符串的函数。在数据结构中，通常借助哈希函数来加速对数据项的查找过程。根据应用情况的不同，通常也将哈希函数的输出称为哈希值、哈希码、散列值等。
在线性表、树等数据结构中，每个记录所在的相对位置是随机的，与记录的关键字之间不存在确定关系，因此，在这些数据结构中查找记录时需要进行一系列的关键字比较操作，相应的查找效率依赖于查找过程中所进行的比较次数。如果希望不经过任何比较，仅用一次存取就能得到需要的记录，就必须建立一个关于存储位置和关键字的对应关系f，使得每个关键字与一个唯一的存储位置相对应。在查找时，只要根据这个对应关系f就能找到给定值key的像f(key)。而一旦数据结构中存在关键字与key相等的记录，则其必定在f(key)存储位置上，这样不需要进行比较就可以直接取得所查找的记录。这里的对应关系f实际上就是一个哈希函数，而按照这种思路建立的表格则称为哈希表(Hash table)。
例如，如果要建立一张学生成绩表，最简单的方法是以学生的学号作为关键字，1号学生的记录位置在第1条，10号学生的记录位置在第10条，以此类推。此时，如果要查看学号为5的学生成绩，则只要取出第5条记录就可以。这样建立的表实际上就是一张简单的哈希表，其哈希函数为f(key)=key。然而，很多情况下的哈希函数并不如此简单。为了查看方便，可能会以学生的名字作为关键字。此时，为了能够根据学生的名字直接定位出相应记录所在的位置，需要将这些名字转换为数字，构造出相应的哈希函数。下面给出两个不同的哈希函数。 
(1) 考察学生名字的汉语拼音，将其中第一个字母在英语字母表中的序号作为哈希函数值。例如，“蔡军”的汉语拼音第一个字母为字母C，因此取03作为其哈希值。
(2) 考察学生名字的汉语拼音，将其中第一个字母和最后一个字母在英语字母表中的序号之和作为哈希函数值。例如，“蔡军”的汉语拼音第一个字母和最后一个字母分别为C和N，因此取17作为其哈希值。
分别应用这两个哈希函数，成绩表中部分学生名字不同的哈希函数值如表3.5所示。 

表3.5学生名字的哈希函数值


key李丽
(LILI)赵宏英
(ZHAOHONGYING)肖军
(XIAOJUN)吴小艳
(WUXIAOYAN)
肖秋梅
(XIAOQIUMEI)陈伟
(CHENWEI)


f1(key)
12
26
24
23
24
03
f2(key)
21
33
38
37
33
12
在哈希表的构造过程中，可能会出现不同的关键字映射到同一地址的情况，即key1≠key2，但f(key1)=f(key2)，也将这种现象称为冲突或碰撞(collision)。实际上，由于哈希函数是把任意长度的字符串映射为固定长度的字符串，冲突是必然存在的。可以说，冲突不可能避免，只能尽可能减少。例如，上面给出的两个哈希函数中，应用第二个函数时出现的碰撞比应用第一个函数出现的碰撞要少得多。
常见的构造哈希函数的方法有以下几种。 
(1) 直接定址法。直接定址法取关键字或关键字的某个线性函数值为哈希地址，即f(key)=key或f(key)=a·key+b，其中a和b为常数。直接定址法所得到的地址空间与关键字集合的大小相同，对于不同的关键字不会发生冲突，但在实际应用中使用这种哈希函数的情况比较少。
(2) 数字分析法。数字分析法适合于关键字由若干数码组成，同时各数码的分布规律事先知道的情况。具体方法是： 分析关键字集合中每个关键字中的每位数码的分布情况，找出数码分布均匀的若干位作为关键字的存储地址。
例如，一个由80个结点组成的结构，其关键字为6位十进制数。选择哈希表长度为100，则可取关键字中的两位十进制数作为结点的存储地址。具体采用哪两位数码，需要用数字分析法对关键字中的数码分布情况进行分析。假设结点中有一部分关键字如下： 
key1=3 0 1 5 1 4key2=3 0 3 0 2 7
key3=3 0 1 1 0 3key4=3 0 8 3 2 9
key5=3 0 0 2 8 7key6=3 0 5 9 3 9
key7=3 0 0 7 9 2key8=3 0 0 4 6 3
对上述关键字分析可以发现，关键字的第1位均为3，第2位均为0，分布集中，不适合作为存储地址。而第4位和第5位分布均匀，所以该哈希函数可以构造为取第4、5位作为结点的存储地址。上述8个结点的散列地址为： 
f(key1)=51f(key2)=02f(key3)=10f(key4)=32 
f(key5)=28f(key6)=93f(key7)=79f(key8)=46 
(3)  平方取中法。平方取中法是一种比较常用的构造哈希函数的方法，具体是： 将关键字求平方后，取其中间的几位数字作为散列地址。由于关键字平方后的中间几位数字和组成关键字的每一位数字都有关，因此产生冲突的可能性较小，最后究竟取几位数字作为散列地址需要由散列表的长度决定。例如，若结构的存储地址范围是1～999，则取平方值的中间3位，如表3.6所示。

表3.6平均取中法


关键字keykey2哈希地址压缩地址


11032710
121720689944100
689
344
11054312
122197813793344
813
406
01110345
001232866019025
866
433
01111401
001235212182801
212
106
若所取哈希函数值超出了存储区的地址范围，则可以再乘以一个比例因子，把哈希函数值放大或缩小，使其位于存储区的范围内。如果上述示例中存储地址范围是1～500，则可以对哈希地址再乘以0.5取整。
(4) 折叠法。折叠法适用于关键字位数很多且关键字中每一位上数字分布大致均匀的情况。具体方法是： 将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址。叠加又可分为移位叠加和间界叠加。其中，移位叠加是将分组后的每组数字的最低位对齐，然后相加； 间界叠加是将分组后的每组数字从一端向另一端沿分界线进行来回折叠，然后对齐相加。
例如，西文图书的国际标准图书编号是一个10位的十进制数，对某图书编号为0383402846，则其通过移位叠加和间界叠加所得到的哈希地址分别如图3.5(a)和图3.5(b)所示。


图3.5折叠法


(5) 除留余数法。除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址，即f(key)=key(mod p)，其中p≤m。这是一种最简单也最常用的构造哈希函数的方法。它不仅可以对关键字直接取模(mod)，也可在折叠、平方取中等运算之后取模。值得注意的是，在使用除留余数法时，对p的选择很重要。若p选得不好，容易产生同义词。由经验得知，一般情况下可以选p为质数或不包含小于20的质因数的合数。
(6) 随机数法。随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即f(key)=random(key)，其中，random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较恰当。
哈希函数中会不可避免地存在冲突，因此在建造哈希表时不仅要设定一个“好”的哈希函数，而且要设定一种处理冲突的方法。假设哈希表的地址集为0～(n-1)，冲突是指由关键字得到的哈希地址为j(0≤j≤n-1)的位置上已存有记录，则“处理冲突”就是为该关键字的记录找到另一个“空”的哈希地址。在处理冲突的过程中可能得到一个地址序列hi，其中，hi∈［0，n-1］，i=1，2，…，k。即在处理哈希地址的冲突时，若得到的另一个哈希地址h1仍然发生冲突，则再求下一个地址h2，若h2仍然冲突，再求得h3。以此类推，直至hk不发生冲突为止，则hk为记录在表中的地址。通常处理冲突的方法有下列几种。 
(1) 开放定址法。开放定址法是当冲突发生时，形成一个检测序列； 沿此序列逐个进行地址检测，直至找到一个空位置(开放的地址)，将发生冲突的记录放到该地址中，即hi=(f(key)+di)(mod m)，i=1，2，…，k(k≤m-1)，其中，f(key)为哈希函数，m为哈希表表长，di为增量序列。根据对di的设置又可以有以下3种不同的方法：  
① di=1，2，3，…，m-1，称为线性检测再散列； 
② di=12，-12，22，-22，33，…，±k2，(k≤m/2)，称为二次检测再散列； 
③ di=伪随机数序列，称为伪随机检测再散列。
(2) 再哈希法。再哈希法是当同义词产生地址冲突时计算另一个哈希函数地址，直到冲突不再发生。这种方法不易产生“聚集”，但增加了计算的时间。 
(3) 拉链法。拉链法是将所有关键字为同义词的记录存储在同一线性链表中。假设某哈希函数产生的哈希地址在区间［0…m-1］上，则首先设立一个指针型向量ChainHash［m］，其每个分量的初始状态都是空指针。接下来，对于哈希地址为i的所有记录都插入到以ChainHash［i］为头指针的链表中。
例如，已知一组关键字为(26，36，41，38，44，15，68，12，06，51)，表长为13，选定的散列函数为f(key)=key (mod 13)，则用拉链法构造的哈希表如图3.6所示。


图3.6拉链法构造的哈希表




习题

3.1对于集合A={x，y，z}和B={1，2，3}，判断下列 A到B的关系哪些构成函数：
① {<x，1>，<x，2>，<y，1>，<y，3>}； 
② {<x，1>，<y，3>，<z，3>}； 
③ {<x，1>，<y，1>，<z，1>}； 
④ {<x，2>，<y，3>}； 
⑤ {<x，1>，<y，2>，<z，3>}； 
⑥ {<x，1>，<x，2>，<y，1>，<y，3>，<z，2>，<z，3>}。
3.2判断下列关系哪些是函数：
① {<x，|x|> | x∈R}； 
② {<|x|，x> | x∈R}； 
③ {<x，y> | x∈R，y∈R，|x|=|y|}； 
④ {<x，y> | x∈Z，y∈Z，y整除x}； 
⑤ {<x，y> | x∈Z，y∈Z，x=y+1}； 
⑥ {<x，y> | x∈N，y∈N，x=y+1}。
3.3对于集合A={a，b，c}，问：
① A到A可以定义多少个不同的函数？
② A×A到A可以定义多少个不同的函数？
③ A到A×A可以定义多少个不同的函数？
3.4对于集合A={a，b，c，d}和B={1，2，3}，A到B可以定义多少个不同的函数？写出 A到B的3个不同函数。
3.5对于函数f： A→B和g： A→B，求证：
① f∪g为A到B的函数当且仅当f=g； 
② f∩g为A到B的函数当且仅当f=g。
3.6下列函数哪些是单射函数、满射函数或双射函数：
① f： Z+→Z+(Z+是正整数集合)，f(x)=3x； 
② f： Z→Z，f(x)=|x|； 
③ 集合A={0，1，2}到B={0，1，2，3，4}的函数f，f(x)=x2； 
④ f： R→R，f(x)=x+1； 
⑤ f： N→N×N，f(x)=<x，x+1>； 
⑥ f： Z→N，f(x)=|2x|+1。
3.7对于集合A和B，且|A|=m，|B|=n，问：
① A到B可以定义多少个不同的函数？
② A到B可以定义多少个不同的单射函数？
③ A到B可以定义多少个不同的满射函数？
④ A到B可以定义多少个不同的双射函数？
3.8对于下列集合对A和B，构造一个A到B的双射函数：
① A=N，B=N-{0}； 
② A=P({1，2，3})，B={0，1}3； 
③ A=［0，1］，B=［1/4，1/2］。
3.9对于函数f： A→B和g： B→C，试证明以下结论：
① 如果f和g是单射函数，则fg是单射函数； 
② 如果f和g是满射函数，则fg是满射函数； 
③ 如果f和g是双射函数，则fg是双射函数。
3.10对于函数f： A→B和g： B→C，举例说明以下论断是成立的。
① 如果f和g是单(满、双)射函数，则fg是单(满、双)射函数； 
② 如果fg是单射函数，则f是单射函数； 
③ 如果fg是满射函数，则g是满射函数； 
④ 如果fg是双射函数，则f是单射函数，g是满射函数。
3.11对于函数f： A→B和g： B→C，举例说明以下论断是不成立的：
① 如果fg是双射函数，则g是单射函数，f是满射函数； 
② 如果fg是单射函数，则g是单射函数； 
③ 如果fg是满射函数，则f是满射函数。
3.12对于集合A={a，b，c，d}、B={1，2，3}和C={a，b，d}，计算以下函数f： A→B和g： B→C的复合函数fg：
① f={<a，1>，<b，2>，<c，1>，<d，3>}，g={<1，a>，<2，b>，<3，d>}； 
② f={<a，2>，<b，3>，<c，1>，<d，3>}，g={<1，a>，<2，a>，<3，a>}； 
③ f={<a，3>，<b，1>，<c，2>，<d，3>}，g={<1，b>，<2，b>，<3，b>}； 
④ f={<a，2>，<b，1>，<c，3>，<d，3>}，g={<1，d>，<2，b>，<3，a>}。
3.13对于下列实数集合上的函数f(x)=2x2+1，g(x)=-x+7，h(x)=2x和k(x)=x+3，求fg、gf、ff、gg、fh、fk、kh、hk。
3.14对于集合A={a，b，c，d}和B={1，2，3，4}，判断以下函数f： A→B的逆关系是否为函数：
① f={<a，1>，<b，2>，<c，3>，<d，4>}； 
② f={<a，2>，<b，3>，<c，1>，<d，3>}； 
③ f={<a，3>，<b，1>，<c，2>，<d，4>}； 
④ f={<a，4>，<b，3>，<c，2>，<d，1>}。
3.15设满射函数f： A→A满足ff=f，证明f=IA。
3.16对于函数f： Z×Z→Z×Z，f(<x，y>)=<x+y，x-y>，证明f是单射函数，并举例说明其不是满射函数。
3.17对于函数f： Z×Z→Z×Z，f(<x，y>)=<x+2，x-y>，求逆函数f-1。
3.18对于函数f： Z×Z→Z×Z，f(<x，y>)=<x-y，x-3>，求复合函数f-1f和ff。
3.19(凯撒密码)设26个英文小写字母构成的集合A={a，b，…，z}，由0～25这26个整数构成的集合B={0，1，2，…，25}。函数f： A→B表示小写英文字母与其字典排序位置的对应关系，且f(a)=0，f(b)=1，…，f(z)=25，B上的函数g定义为g(x)=(x+3)(mod 26)。若明文按(fg)f-1的方式加密，试求：
① 明文“computer”对应的密文； 
② 密文的解密函数，并给出密文“khoor”对应的明文。




第2篇数理逻辑



数理逻辑(mathematical logic)是由莱布尼茨于17世纪中叶创立的。当时古典形式逻辑不足之处已为某些逻辑学者所理解。数学方法对认识自然和发展科学技术已显示出重要作用。人们感到演绎推理和数学计算有相似之处，希望能把数学方法推广到思维的领域。莱布尼茨在他1666年出版的《组合术》一书中表达了系统化形式论证的观点。他首先明确地提出了数理逻辑的指导思想，设想能建立“普遍的符号语言”，这种语言包含着“思想的字母”，每个基本概念应该由一个表意符号来表示，一种完善的符号语言又应该是一个“思维的演算”，论辩或争论可以用演算来解决。莱布尼茨提出的这种符号语言和思维演算正是现代数理逻辑的主要特证，并为实现其设想做了不少具体的工作。他给出了一个关于两个概念相结合的演算，解释了这种结合的内涵和外延，得到了一些与之相关的重要定理。同时，成功地将古典逻辑的4个简单命题表达为符号公式。1679—1690年期间，他在无定义术语、公理、假定、逻辑规则和导出命题的基础上发展了一个体系。 
在18世纪前后，欧洲大陆有许多人继续做了莱布尼茨的工作，但没有得到更多的重要结果。19世纪中叶两个英国学者布尔(George Boole，1800—1864)和德·摩根(Augustus de Morgan，1806—1874)打破了沉闷的局面。布尔是代数学家，他设想给代数系统以逻辑的解释或可构成一个思维的演算。他也认为，思维的运算和一般代数的规律可以有差异，不能机械地推广。他给予代数以4种解释： 其中一种为类的演算，两种是命题演算，还有一种是概率理论。类演算所特有的规律为x2=x。命题演算中的命题变元只取0或1为值，此系统可被看作二值代数，他就用此二值代数作为推导的工具。布尔于1847年和1854年分别发表了《逻辑的数学分析》和《思维规律的研究》，建立了“布尔代数”，创造了一套符号系统和一系列运算法则，利用符号和代数的方法来研究逻辑中的各种概念和问题。德·摩根的《形式逻辑： 推理的演算，必要性和可能性》充实了这些工作。他突破了古典谓词逻辑的局限性，提出关系命题和关系推理，第一个在证明方法中使用“归纳”一词，并将逻辑学的大部分研究纳入数学的任务。从17世纪末到19世纪末，约200年的时间，人们开始用数学方法研究和处理形式逻辑，其代表成果是逻辑代数和布尔代数。这段时间是数理逻辑发展的第一个阶段或初始阶段。 
19世纪中叶之后的约60年是数理逻辑发展的第二个阶段。在此期间，数学科学的发展提出了研究数学思想方法和数学基础问题的必要性。数理逻辑适应数学的需要，联系数学实际，奠定了它的理论基础，创建了特有的新方法，取得了飞跃的发展，成长为一门新学科。这段时间又称为数理逻辑发展的过渡阶段。
19世纪70年代，弗雷格(Ludwig Gottlob Frege，1848—1925)首先建立了一个完全的逻辑演算体系，其后佩亚诺(Giuseppe Peano，1858—1932)也为此做了不少贡献，最后由罗素(Bertrand A.W.Russell，1872—1970)和怀特海德(Alfred North Whitehead，1861—1947)完成了建立一个初步的二值外延逻辑系统的工作。弗雷格对逻辑的兴趣来自数学基础问题的研究。他认为，人们应该考虑如何定义数的概念并证明关于自然数的定理。同时，数学真理需通过感性才为人所认识，但认识的来源并不等于证明的根据，数学命题似乎可以纯粹从逻辑规律得到证明。从日常语言不能表达严格和复杂的思想这一考虑出发，他发明了一种表意的语言，称之为“概念语言”，用以表达其逻辑演算。这种语言虽然精确，但由于是二维的图形，不便于理解，因此他的著作开始时影响很小。弗雷格的重要贡献是把数学里的函数概念引入逻辑发展了量词理论，并区别了对象语言(演算里的语言)和语法语言(讲述演算所用的语言)。一个严格的逻辑演算必须有它本身的推导或演算规则，这种规则不应在演算里表达，而是现代逻辑所谓的变形规则。在其概念语言中，弗雷格曾举出一些演算规则，如分离规则等。佩亚诺认为，语言含混是数学基础问题难以解决的根源。他创造了一个符号体系，并用来精确地分析了大量的数学命题。他的符号简单适用，其中一部分仍被保留在逻辑文献中。他在逻辑方面的重要贡献有两个方面： 一是区别两类间的包含关系与类和元素的从属关系； 二是区别某一个体和以此个体为唯一元素的类。佩亚诺没有给出逻辑演算体系，只列举出了一系列定理。在公理方法方面，他的5条算术公理获得了公认。
1928年希尔伯特(David Hilbert，1862—1943)和阿克曼(Wilhelm Ackermann，1896—1962)合著的《理论逻辑基础》第一版首先把一阶逻辑分离出来并证明其一致性。同年，希尔伯特在波劳亚数学会议上提出逻辑演算的完全性问题。哥德尔(Kurt Godel，1906—1978)于1930年发表了博士论文的修改稿“逻辑谓词演算公理的完全性”，证明了一阶谓词演算的有效公式皆可证。他在1931年的论文中证明了公理化方法有局限性。
20世纪30年代后期，数理逻辑进入发展的第三阶段，数理逻辑成为数学大家庭的成员。目前其中心内容大致可以分为5个部分，即证明论、集合论、递归论、模型论和各种逻辑系统的研究。前4个分支各有其中心课题，近年来都有长足和重大的进展。最后一个分支的方向是用古典演算的元逻辑方法来处理各种非经典逻辑系统，如模态逻辑(modal logic)、多值逻辑(multivalued logic)、时态逻辑(temporal logic)、模糊逻辑(fuzzy logic)和描述逻辑(description logic)等。20世纪40年代以后，从事非经典逻辑研究的学者逐渐增多，在各方面的作用也不同程度地显示出来。 
数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号来简洁地表达各种推理的逻辑关系，因此，数理逻辑又称为符号逻辑(symbolic logic)。数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、可计算性理论、计算机辅助设计、人工智能和知识工程等计算机应用和理论研究提供了必要的理论基础。