第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的一个关系，若对每一个都存在一个唯一的y?Y，使得x,y?f，则称关系f为X到Y的映射(Mapping)，x?X，记作
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} （2）是映射。dom S2?{1,2,3}，RS2?{2,3,3,2,3,4} （3）不是映射。
（4）是映射。dom S4?{1,2,3}，RS4?{2,3}
请注意区别x的像和{x}的像两个不同的概念。x的像f(x)?Y，而像f({x})?Y。关于像有下列性质：
定理4.1.1 设f为X到Y映射，对任意A?X,B?X，有 （1）f(AUB)?f(A)Uf(B)； （2）f(AIB)?f(A)If(B)； （3）f(A)?f(B)?f(A?B)。 证明 （1）对任一y?Y，
y?f(AUB)??x((x?AUB)?(y?f(x)))
??x(((x?A)?(x?B))?(y?f(x)))
??x(((x?A)?(y?f(x)))?((x?B)?(y?f(x))))
??x((x?A)?(y?f(x)))??x((x?B)?(y?f(x)))
?(y?f(A))?(y?f(B)) ?y?f(A)Uf(B)
因此，f(AUB)?f(A)Uf(B)。
（2）、（3）的证明请读者完成。 注意：（2）、（3）中的“?”不能用“=”代替。下面我们举例说明。
例4.1.4 设X?{a,b,c,d}，Y?{1,2,3,4,5}，f：X?Y如图 4-2所示。那么，
f({a})?{2}
f({b})?{2}
f({a})If({b})?{2} f({a})?f({b})??
f({a}I{b})?f(?)??f({a}?{b})?f({a})?{2}
f({a}I{b})?f({a})If({b})
f({a})?f({b})?f({a}?{b})
图 4-2 例4.1.4图
由于映射归结为关系，因而映射的表示及运算可归结为集合的表示及运算，映射的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。
定义4.1.2 设f：A?B，g：C?D，如果A?C，B?D，且对于所有x?A，有f(x)?g(x)，则称映射f和g相等，记作f?g。如果A?C，B?D，且对于所有
x?A，有f(x)?g(x)，则称映射f包含于g，记作f?g。
事实上，当不强调映射是定义在哪个集合上的时候，由于映射是序偶的集合（特殊的关系），所以f = g的充分必要条件是f?g且g?f。
从映射的定义可以知道X?Y的子集并不能都成为X到Y的映射。
例如，设X?{a,b,c}， Y?{0,1}，X?Y?{a,0,b,0,c,0,a,1,b,1,c,1}，
X?Y有26个可能的子集，但其中只有23个子集为从X到Y的映射：
f0?{a,0,b,0,c,0}，f1?{a,0,b,0,c,1} f2?{a,0,b,1,c,0}，f3?{a,0,b,1,c,1} f4?{a,1,b,0,c,0}，f5?{a,1,b,0,c,1} f6?{a,1,b,1,c,0}，f7?{a,1,b,1,c,1}
同理可知，从Y到X可定义3个不同的映射：
2g0?{0,a,1,a}，g1?{0,a,1,b}，g2?{0,a,1,c}，
离散数学电子教材4 - 图文
