离散数学电子教材4.doc

《离散数学电子教材4.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章映射（函数）映射（函数）是一个基本的数学概念，它是一个特殊的二元关系，我们可以把映射看作输入输出关系，它把一个集合（输入集合）的元素变成另一个集合（输出集合）的元素。例如，计算机中的程序可以把一定范围内的任一组数据变化成另一组数据，它就是一个映射。映射的概念经常出现在开关理论、自动机理论和可计算理论等领域中，在计算机科学中有着广泛的应用。4.1映射（函数）的概念考虑下面几个由图4-1所示的集合到集合的关系。图4-1在这６个关系中，后４个关系，，，与，不同，173它们都有下面两个特点：（1）其定义域为；（2）中任一元素对应唯一一个中的元素。我们称具有这样两个特征的关系

2、为映射（函数）。定义4.1.1设是两个任意的集合，而是到的一个关系，若对每一个，都存在一个唯一的，使得，则称关系为到的映射(Mapping)，记作或若，则称为自变量(IndependentVariable)，称为映射在处的值（或像（Image）），亦可记作，的值域ran，有时也记为，即或记为集合称为的共域，亦称为映射的像集合。对于，称为的像（Imageof），定义为显然,，。映射是到的特殊的二元关系，其特殊性在于：（1）dom，即关系的前域是本身，而不是的真子集。（2）若，则映射在处的值是唯一的，即例4.1.1设，且有，求dom、和。解domran173例4.1.2判别

3、下列关系中哪个构成映射。（1）（2）（3）（4）（5）为小于的素数个数（6）（7）（8）解（1）构成映射。（2），即值不唯一，故不构成映射。（3）因为不能取定义域中所有的值，且对应很多，故不构成映射。（4）因为不能取定义域中所有的值，故不构成映射。（5）构成映射。（6）构成映射。（7）因为对，值不唯一，故不构成映射。（8）因为对，值不唯一，故不构成映射。例4.1.3下列集合中，哪些是映射？并求映射的定义域和值域。（1）（2）（3）（4）解（1）是映射。dom，（2）是映射。dom，（3）不是映射。173（4）是映射。dom，请注意区别的像和的像两个不同的概念。的像，而像。

4、关于像有下列性质：定理4.1.1设为到映射，对任意，有（1）；（2）；（3）。证明（1）对任一，因此，。（2）、（3）的证明请读者完成。注意：（2）、（3）中的“”不能用“=”代替。下面我们举例说明。例4.1.4设，，如图4-2所示。那么，173图4-2例4.1.4图由于映射归结为关系，因而映射的表示及运算可归结为集合的表示及运算，映射的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。定义4.1.2设，，如果，，且对于所有，有，则称映射和相等，记作。如果，，且对于所有，有，则称映射包含于，记作。事实上，当不强调映射是定义在哪个集合上的时候，由于映射是

5、序偶的集合（特殊的关系），所以f=g的充分必要条件是且。从映射的定义可以知道的子集并不能都成为到的映射。例如，设，，，有个可能的子集，但其中只有个子集为从到的映射：，，，，同理可知，从到可定义个不同的映射：173，，，，，，，一般地，设和都为有限集，分别有和个不同元素，由于从到任意一个映射的定义域是，在这些映射中每一个恰有个序偶。另外任何元素，可以有的个元素中的任何一个作为它的像，故共有个不同的映射。在上例中，故从到有个不同的映射，从到有个不同的映射。今后我们用符号表示从到的所有映射的集合，甚至当和是无限集时，也用这个符号，即则有。特别地表示集合上映射的全体。习题4.11

6、．指出下列各关系是否为到的函数：（1），（2）(实数集)，（3），（4）设，，，，。2．设，，求证：（1）为到的函数当且仅当。（2）为到的函数当且仅当。3．设为一函数，计算，，。4．设，为：，求，，，。1734.2特殊映射定义4.2.1设，（1）如果ran，即的每一个元素都是中一个或多个元素的像，则称这个映射为满射(Surjection)（或到上映射）。（2）如果对于任意，若，则有，则称这个映射为入射(Injection)（或单射）。（3）若既是满射又是入射，则称是双射(Bijection)。双射也称为1—1对应(OneToOneMapping)。由定义不难看出，如

7、果是满射，则对于任意，必存在，使得成立；如果是入射，则中没有两个不同元素有相同的像，即对于任意，。图4-3说明了这三类映射之间的关系。注意，既非单射又非满射的函数是大量存在的。图4-3例4.2.1（1）设，如果定义为则是满射的。（2）定义为，则这个函数是入射，但不是满射。（3）令表示实数的闭区间，即，定义为：173则这个映射是双射。例4.2.2在图4-4中，、是满射，、是入射，是双射。图4-4例4.2.3设是自然数集，下列映射哪些是满射、入射、双射。（1），。（2），。（3），（4），（5），（6），。（7），解：（1）入射。