可编辑
第4章 映射（函数）
映射（函数）是一个基本的数学概念，它是一个特殊的二元关系，我们可以把映射看作输入输出关系，它把一个集合（输入集合）的元素变成另一个集合（输出集合）的元素。例如，计算机中的程序可以把一定范围内的任一组数据变化成另一组数据，它就是一个映射。
映射的概念经常出现在开关理论、自动机理论和可计算理论等领域中，在计算机科学中有着广泛的应用。
4.1 映射（函数）的概念
考虑下面几个由图 4-1所示的集合X到集合Y的关系。
图 4-1
精品
可编辑
在这６个关系中， 后４个关系R3，R4，R5，R6与R1，R2不同， 它们都有下面两个特点：
（1） 其定义域为X；
（2） X中任一元素a对应唯一一个Y中的元素b。 我们称具有这样两个特征的关系为映射（函数）。
定义4.1.1 设X,Y是两个任意的集合，而f是X到Y的一个关系，若对每一个
x?X，都存在一个唯一的y?Y，使得x,y?f，则称关系f为X到Y的映射
(Mapping)，记作
f?Y f：X?Y 或X??若x,y?f，则称x为自变量(Independent Variable)，称y为映射f在x处的值（或像（Image）），x,y?f亦可记作y?f(x)，f的值域ranf?Y，有时也记为Rf，即
Rf?{yy?Y?(?x)(x?X?y?f(x))}
或记为
f(X)?{f(x)x?X}
集合Y称为f的共域，Rf亦称为映射f的像集合。对于A?X，称f(A)为A的像（Image of A），定义为
f(A)?{f(x)x?A}?{y?x(x?A?y?f(x))}
显然,，f(?)??,f({x})?{f(x)}(x?X)。
映射f是X到Y的特殊的二元关系，其特殊性在于：
（1）domf?X，即关系f的前域是X本身，而不是X的真子集。 （2） 若x,y?f，则映射f在x处的值y是唯一的，即
x,y?f?x,z?f?y?z
例4.1.1 设X?{a,b,c,d},Y?{1,2,3,4,5}，且有f?{a,1,b,3,c,4,d,4}，求 domf、Rf和f(x)。
解 domf?X?{a,b,c,d}精品
可编辑
ranf?{1,3,4}
f(a)?1,f(b)?3,f(c)?4,f(d)?4 例4.1.2 判别下列关系中哪个构成映射。 （1）f?{x,x2x?R} （2）f?{x2,xx?R}
（3）f?{x1,x2x1,x2?N,且x1?x2?10} （4）f?{x1,x2x1,x2?N,且x1?x2?10}
（5）f?{x1,x2x1,x2?N,x2为小于x1的素数个数} （6）f?{x,yx,y?R,x?y} （7）f?{x,yx,y?R,y?x} （8）f?{x,yx,y?R,x?y} 解 （1）构成映射。
（2）x2,x?f,x2,?x?f，即值y不唯一，故不构成映射。
（3）因为x1不能取定义域中所有的值，且x1对应很多x2，故不构成映射。 （4）因为x1不能取定义域中所有的值，故不构成映射。 （5）构成映射。 （6）构成映射。
（7）因为对?x?R，值y不唯一，故不构成映射。 （8）因为对?x?R，值y不唯一，故不构成映射。
例4.1.3 下列集合中，哪些是映射？并求映射的定义域和值域。 （1）S1?{1,2,3,2,3,4,3,1,4,4,1,4} （2）S2?{1,2,3,2,3,4,3,3,2} （3）S3?{1,2,3,1,2,4,2,3,4} （4）S4?{1,2,3,2,2,3,3,2,3}
解 （1）是映射。domS1?{1,2,3,4}，RS1?{1,4,2,3,3,4}
精品
离散数学电子教材
