离散数学中的函数与映射及应用

定义1 设A和B是两个任意非空集合，而σ是A到B上的一个二元关系，如果对于每一个x∈A，有唯一的一个y∈B，使得（x，y）∈σ，则称σ为从A到B的映射（或称关系σ为函数），记作σ：A→B，或。

假设（x，y）∈σ，则称x为自由变化（原象），y称为在σ作用下的象。（x，y）∈σ亦可记作y=σ（x），且记σ（A）={σ（x）|x∈A}。

集合A称作σ的定义域，记作Dσ，σ（A）称作σ的值域，记作Rσ。

从函数的定义可以知道它与关系有别于如下两点：

（1）函数的定义域是A，而不能是A的某个真子集。

（2）一个x∈A，只能对应唯一的一个y，即如果σ（x）=y，且σ（x）=z，那么y=z。

例1 设集合A={a，b，c，d}，B={1，2，3，4，5}，σ={（a，1），（b，2），（c，3），（d，5）}，则σ是一个从A到B的函数，Dσ=A，Rσ={1，2，3，5}，σ（a）=1，σ（b）=2，σ（c）=3，σ（d）=5。

例2 设集合A=B=R，R是实数集合，且σ1={（a，a2）|a∈R}，σ2={（a2，a）|a∈R}，σ3={（a1，a2）|a1，a2∈N且a1+a2＜10}，试判定σ1，σ2，σ3是否为函数？

解 对任意a∈R，都有σ1（a）=a2，对任意的a存在唯一的σ1（a）=a2，所以σ1是函数。

因为1∈R，有σ2（1）=±1，即象不唯一，所以σ2不是函数。

因为a1不能取定义域N中的所有值，且a1对应多个a2，故σ3不构成函数。

定义2 设σ和τ是从集合A到B的两个函数，若对于所有的x∈A，都有σ（x）=τ（x），则称函数σ和τ相等，记作σ=τ。

从函数的定义可以知道，A×B的子集并不能都成为A到B的函数。例如，设A={a，b，c}，B={0，1}，A×B={（a，0），（a，1），（b，0），（b，1），（c，0），（c，1）}，A×B中有26个可能的子集，但其中只有23个为从A到B的函数：

σ0={(a,0),(b,0),(c,0)};

σ1={(a,0),(b,0),(c,1)};

σ2={(a,0),(b,1),(c,0)};

σ3={(a,0),(b,1),(c,1)};

σ4={(a,1),(b,0),(c,0)};

σ5={(a,1),(b,0),(c,1)};

σ6={(a,1),(b,1),(c,0)};

σ7={(a,1),(b,1),(c,1)}。

下面我们讨论函数的几类特殊情况。

定义3 设σ是从集合A到B的映射，

（1）若σ（A）=B，则称为从A到B的满射；

（2）若当a≠b时，有σ（a）≠σ（b），或者当σ（a）=σ（b）时，必有a=b，则称σ为从A到B的单射，或称一对一映射；(www.xing528.com)

（3）σ是满射又是单射，则称σ为从A到B的双射，或称一一对应映射。

由上述定义可知，满射也可以说成集合B中每一个元素都是A中至少一个元素的象；单射可以说成集合B中的元素如果有原象，则有唯一的原象；双射则是不仅集合A中每一个元素在集合B中有唯一的象，而且B中每一个元素在A中也只有唯一的原象。

映射除了上述三种特殊形式外，有的映射既不是满射，又不是单射，当然也不可能是双射，这种情况可以通过下面的例子看到。

图1直观地表示出了几种特殊的映射：

例3 在下列映射下，试确定哪些是满射？哪些是单射？哪些是双射？

（1）σ1：Z→R，σ1（n）=小于n的完全平方数的个数；

(2)σ2:R→R,σ2(r)=2r-10;

(3)σ3:N→R,σ3(n)=lgn。

解（1）依σ定义，σ1={（1，0），（2，1），（3，1），（4，1），（5，2），…}。故σ1既不是满射，又不是单射，更不是双射。

（2）由于σ2：R→R，σ2（r）=2r-10，由图2所示图像可以看出，σ2既是满射，又是单射，所以也是双射。

（3）由于σ3：N→R，σ3（n）=lgn，当，且n1≠n2时，显然有lgn1≠lgn2，所以σ3是单射，又因为n∈N，N是R上的离散点，不可能取遍R，所以σ1不是满射，也不是双射。

由于映射是二元关系，所以可以用关系图和关系矩阵来表达，从关系图和关系矩阵上能明显地看出以下特点：根据映射定义，定义域上每一元素均成为序偶（a，σ（a））中的第一元素，所以关系图上集合A中每一点都发出一条弧，终点为集合B中的元素。在关系矩阵的每一行上，都必然仅有一个元素1，而此行其余元素皆为0；而在关系矩阵的每一列上，则不一定只有一个元素1，因为B中某个元素的原象可能不止一个。

例4 设集合A={a，b，c，d，e}，B={1，2，3，4}，映射σ={（a，2），（b，2），（c，3），（d，4），（e，4）}，试求映射σ的关系图与关系矩阵。

解：关系图如图3所示：

关系矩阵为：

映射的概念在日常生活中也有很多应用。如设A是工人的集合，B是工作的集合，从A到B的满射是工人做工作的一种分配方案，使每项工作至少分配有一个工人。从A到B的入射，也是一种分配方案，使得没有两个工人做同一项工作。从A到B的双射，同样是一种分配方案，使每一项工作都分配有工人，且没有两个工人分配相同的工作。

定理1 令A和B为有限集，若A和B的基数相同，即|A|=|B|，则σ：A→B是入射的，当且仅当它是一个满射。

证明（1）若σ是入射，则|A|=|σ（A）|，又因为|A|=|B|，故|σ（A）|=|B|，又由σ的定义知σ（A）⊆B，B的元素个数是有限的，所以有σ（A）=B，故σ是满射。

（2）若σ是满射，根据满射定义，σ（A）=B，于是|A|=|B|=|σ（A）|，又因为|A|=|σ（A）|，且|A|是有限的，故σ是一个入射，证毕。

需要注意的是，这个定理在R是有限集时，才能成立，而在无限集时不一定有效，例如，σ：Z→Z，令σ（x）=2x，在这种情况下，整数映射到偶数，显然是一个入射，但不是满射。