离散数学电子教材精品文档_001.doc
《离散数学电子教材精品文档_001.doc》由会员分享，可在线阅读，更多相关《离散数学电子教材精品文档_001.doc（30页珍藏版）》请在冰点文库上搜索。
第4章映射（函数）
映射（函数）是一个基本的数学概念，它是一个特殊的二元关系，我们可以把映射看作输入输出关系，它把一个集合（输入集合）的元素变成另一个集合（输出集合）的元素。
例如，计算机中的程序可以把一定范围内的任一组数据变化成另一组数据，它就是一个映射。
映射的概念经常出现在开关理论、自动机理论和可计算理论等领域中，在计算机科学中有着广泛的应用。
4.1映射（函数）的概念
考虑下面几个由图4-1所示的集合到集合的关系。
图4-1
在这６个关系中，后４个关系，，，与，不同，它们都有下面两个特点：
（1）其定义域为；
（2）中任一元素对应唯一一个中的元素。
我们称具有这样两个特征的关系为映射（函数）。
定义4.1.1设是两个任意的集合，而是到的一个关系，若对每一个，都存在一个唯一的，使得，则称关系为到的映射（Mapping），记作
或
若，则称为自变量（IndependentVariable），称为映射在处的值（或像（Image）），亦可记作，的值域ran，有时也记为，即
或记为
集合称为的共域，亦称为映射的像集合。
对于，称为的像（Imageof），定义为
显然,，。
映射是到的特殊的二元关系，其特殊性在于：
（1）dom，即关系的前域是本身，而不是的真子集。
（2）若，则映射在处的值是唯一的，即
例4.1.1设，且有，求dom、和。
解dom
ran
例4.1.2判别下列关系中哪个构成映射。
（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）不是映射。
（4）是映射。
dom，
请注意区别的像和的像两个不同的概念。
的像，而像。
关于像有下列性质：
定理4.1.1设为到映射，对任意，有
（1）；
（2）；
（3）。
证明
（1）对任一，
因此，。
（2）、（3）的证明请读者完成。
注意：
（2）、（3）中的“”不能用“=”代替。
下面我们举例说明。
例4.1.4设，，如图4-2所示。
那么，
图4-2例4.1.4图
由于映射归结为关系，因而映射的表示及运算可归结为集合的表示及运算，映射的相等的概念、包含概念，也便归结为关系相等的概念及包含概念。
定义4.1.2设，，如果，，且对于所有，有，则称映射和相等，记作。
如果，，且对于所有，有，则称映射包含于，记作。
事实上，当不强调映射是定义在哪个集合上的时候，由于映射是序偶的集合（特殊的关系），所以f=g的充分必要条件是且。
从映射的定义可以知道的子集并不能都成为到的映射。
例如，设，，，有个可能的子集，但其中只有个子集为从到的映射：
，
，
，
，
同理可知，从到可定义个不同的映射：
，，，
，，
，，
一般地，设和都为有限集，分别有和个不同元素，由于从到任意一个映射的定义域是，在这些映射中每一个恰有个序偶。
另外任何元素，可以有的个元素中的任何一个作为它的像，故共有个不同的映射。
在上例中，故从到有个不同的映射，从到有个不同的映射。
今后我们用符号表示从到的所有映射的集合，甚至当和是无限集时，也用这个符号，即
则有。
特别地表示集合上映射的全体。
习题4.1
1．指出下列各关系是否为到的函数：
（1），
（2）（实数集），
（3），
（4）设，，，
，。
2．设，，求证：
（1）为到的函数当且仅当。
（2）为到的函数当且仅当。
3．设为一函数，计算，，。
4．设，为：
，求，，，。
4.2特殊映射
定义4.2.1设，
（1）如果ran，即的每一个元素都是中一个或多个元素的像，则称这个映射为满射（Surjection）（或到上映射）。
（2）如果对于任意，若，则有，则称这个映射为入射（Injection）（或单射）。
（3）若既是满射又是入射，则称是双射（Bijection）。
双射也称为1—1对应（OneToOneMapping）。
由定义不难看出，如果是满射，则对于任意，必存在，使得成立；如果是入射，则中没有两个不同元素有相同的像，即对于任意，。
图4-3说明了这三类映射之间的关系。
注意，既非单射又非满射的函数是大量存在的。
图4-3
例4.2.1
（1）设，如果定义为
则是满射的。
（2）定义为，则这个函数是入射，但不是满射。
（3）令表示实数的闭区间，即，定义为：
则这个映射是双射。
例4.2.2在图4-4中，、是满射，、是入射，是双射。
图4-4
例4.2.3设是自然数集，下列映射哪些是满射、入射、双射。
（1），。
（2），。
（3），
（4），
（5），
（6），。
（7），
解：
（1）入射。
（2）一般映射（既非满射，也非入射）。
（3）一般映射（既非满射，也非入射）。
（4）满射。
（5）不是映射，无定义。
（6）一般映射（既非满射，也非入射）。
（7）不是映射，无定义。
定理4.2.1令和为有限集，若和的元素个数相同，即，则是入射的，当且仅当它是一个满射。
证明
（1）若是入射，则。
从的定义我们有，而，因为是有限的，故，因此，是一个满射。
（2）若是一个满射，则，于是。
因为和是有限的，所以，是一个入射。
这个定理必须在有限集情况下才能成立，在无限集上不一定有效，如，这里，在这种情况下整数映射到偶数，显然这是一个入射，但不是满射。
另外，还有两个特殊而又重要的映射—常映射和恒等映射。
定义4.2.2
（1）设，如果存在，使得对所有的都有，即，则称是常映射。
（2）任意集合上的恒等关系为一映射，常称为恒等映射，因为对任意都有，即
。
对任意，有，故是入射；且，是满射。
所以，是双射。
习题4.2
1．设分别表示正整数集、整数集、实数集、复数集，试指出下列映射中哪些是单射、满射、双射，并写出定义域和值域。
（1）为。
（2）为。
（3）为。
（4）为。
（5）为。
（6）为（其中为一常数）。
2．下列关系中哪些能构成映射？
。
（1），其中为自然数集。
（2），其中为实数集。
（3），其中为实数集。
3．下列集合能定义成映射吗？
如能，试求出它们的定义域及值域。
（1）。
（2）。
（3）。
（4）
4．设映射，这里，
（1）定义了何种关系？
（2）的值域是什么？
（3）有多少与具有同样定义域和陪域的不同映射？
。
（4）设的映射且，问可能是单射吗？
可能是双射吗？
（5）证明存在一个从到的单射，其中为任意集合。
（6）设与均是有限集且有个元素，有个元素，说明下列断言为真时，和必须成立的关系：
1）存在从到的单射。
2）存在从到的满射。
3）存在从到的双射。
4.3复合映射和逆映射
4.3.1复合映射
因为映射是一种特殊的关系，所以和关系一样也有复合运算。
定义4.3.1设映射，，若，则
称在映射的左边可复合。
对于映射的复合我们有下面的定理：
定理4.3.1设，，在映射的左边可复合，即，则是一个映射。
证明
（1）对于任意，因为为映射，故必有唯一的序偶，使成立，而即，又因为是映射，故必有唯一序偶，使成立，根据复合定义，，即中每个对应中某个。
（2）假定中包含序偶和，这样在中必存在和，使得在中有和，在中有和。
因为是一个映射，故；又因为是一个映射，故，即每个只能有唯一的。
由
（1）、
（2）可知是一个映射。
在定义4.3.1中，当时，则映射
称为映射与映射的复合映射，或称为对的左复合。
注意：
在定义4.3.1中，假定random，如果不满足这个条件，则定义为空。
根据复合映射的定义，显然有。
例4.3.1设。
，
，
求。
解
例4.3.2设，均为实函数，，。
求，，，。
解
所以
定理4.3.2设是一个复合映射。
（1）若和是满射，则是满射。
（2）若和是入射，则是入射。
（3）若和是双射，则是双射。
证明给定集合，，，
（1），因为是满射，故，使得；又因为是满射，故，使得，所以，
即，，使得。
因此，，是满射。
（2）对，，因为是入射，故；又因为是入射，故，于是
所以，是入射。
（3）因为和是双射，根据
（1）和
（2），为满射和入射，即是双射。
定理4.3.3设是一个复合映射。
（1）若是满射，则是满射。
（2）若是入射，则是入射。
（3）若是双射，则是满射，是入射。
证明设，，。
（1）因为是满射，则，，，使，故
使得，，可见，，所以是满射。
（2）设且。
因为是入射，故，即，因为是一个映射，则，即
所以，是入射。
（3）是双射，则是满射且是入射。
是满射，由
（1）可知是满射；是入射，由
（2）可知是入射。
由于映射的复合仍然是一个映射，故可求三个以上映射的复合。
例4.3.3设为实数集合，对，有，，
求，，与。
解：
，
所以有
一般地，有如下定理。
定理4.3.4设有函数，和，则有
证明这可由关系的复合的可结合性得出，这里我们直接由映射相等的定义证明。
首先和都是到的函数。
另外对任一，有
由元素的任意性，有
由此可见，映射的复合运算满足结合律，因此多个映射复合时可去掉括号，对3个映射的复合即有
。
若有，则仍为到的映射，简记为，一般地简记为。
显然
注意：
映射的复合运算不满足交换律。
例4.3.4
（1）设，
，，
，，
则
，
。
所以
。
映射的复合运算还有如下明显的性质：
定理4.3.5设映射，则。
证明对，有，，则
所以，
当时，有
4.3.2逆映射
在关系的定义中曾提到，从到的关系，其逆关系是到的关系，
但是，对于映射就不能用简单的交换序偶的元素而得到逆映射，这是因为若有映射，但的值域可能只是的一个真子集，即，此时，
dom，这不符合映射对定义域的要求。
此外，若的映射是多对一的，即有，其逆关系将有，这就违反了映射值唯一性的要求。
为此，有如下定理：
定理4.3.6设是一个双射，那么是的双射。
证明设，，
因为是满射，故对每一，必存在，所以，，即的前域为。
又因为是入射，对每一个恰有一个，使，即仅有一个，使，对应唯一的，故是映射。
因为random，所以，是满射。
又设时，有，令，则，故，即，与假设矛盾。
所以，即是单射。
因此，是一个双射。
定义4.3.2设是一双射，称的双射为的逆映射，记作。
例如，设。
若为：
，
则有，。
若，
则的逆关系
就不是一个函数。
再如，，，则。
函数的逆具有下面一些重要性质。
定理4.3.7如果映射有逆映射，则，
。
证明因为是双射，所以也是双射。
由定理4.3.2知，和都是双射。
任取，若，，则
所以，
；
。
定理4.3.8若是双射，则。
证明因是双射，也是双射，因此，是双射。
由于
dom=dom
且
所以，。
定理4.3.9若，均为双射，则。
证明
（1）因，均为双射，故和均存在，且
，均为双射，所以，为双射。
根据定理4.3.2，是双射，故是双射，且
dom=dom
（2）对任意存在唯一，使得
存在唯一，使得
故
又
故
因此，对任一有：
由
（1）、
（2）可知
。
例4.3.5设，若有，，其中，，求和。
解，
，
可见，
习题4.3
1．证明或反驳下列命题：
（1）设，为任一映射，则，其中，，
。
（2）是双射，当且仅当对中任两个子集与，若，则。
（3）设，均为有限集且，则下列命题等价：
①是单射；②是满射；③是可逆的。
2．设为，其中为实数集，试求。
3．证明从到存在单射，并说明此映射是否为满射。
4．设。
（1）试定义映射使且是单射。
（2）求。
（3）能否找到另一的单射，有？
（4）试定义一个映射使且。
（5）试定义一个映射使且。
5．求下列各映射的逆映射：
（1）；
（2）；
（3）；
（4）.
6．如果为且
为；
为；
为
试求，，，，，。
7．设，为任意两个映射，证明
（1）如果不是满射，则也不是满射。
（2）如果不是单射，则也不是单射。
（3）如果为满射，，则。
4.4置换
定义4.4.1设，双射称为集合的置换（Permutation），记作
这里，中元素的个数称作置换的阶。
定理4.4.1在个元素的集合中，不同的阶置换的总数为！
个。
证明形如：
中的可以取的任意一个全排列，故总数为！
个。
定义4.4.2给定，恒等映射称为集合上的恒等置换（IdenticalPermutation），记作
定义4.4.3设是集合的置换，如果可以取到的元素
，使，且的其余元素（如果还有的话）不变，则称为一个轮换，记为。
若，则的个置换
都是轮换，它们分别记为
和。
当时，置换不是轮换。
一般地，时，的置换都是轮换；时，的置换未必是轮换。
定义4.4.4把置换看作定义在集合上的双射，置换的复合定义为相应映射复合构成的置换。
例如，，
则，
可见，。
两个轮换与的复合记为：
。
定义4.4.5给定，对任意的阶置换
记
容易验证
我们称为的逆置换。
集合上的所有阶置换的全体记作。
置换的复合有以下性质：
（1）对于复合运算是封闭的；
（2）结合律成立，即，有；
（3）中有一个元素称为恒等置换，使对任意有；
（4）任意，都存在有逆置换，使。
习题4.4
1．若，试写出上的全部置换，并指出各置换的逆。
2．设，是上的置换，
，，，
求，，，，，及。
3．已知，，，
请验证：
。
4．设，计算。
5．设，上的置换，。
求
（1）；
（2）。
*4.5特征函数
有些映射与集合之间可以建立一些特殊的关系，借助于这些映射，可对集合进行运算。
定义4.5.1令是全集，，由
定义的映射，称为集合的特征函数（Eigen-function）。
定理4.5.1给定全集，且，，对于所有，特征函数有如下一些性质。
（1）
（2）
（3）
（4）
（5）
（6）
（7）
（8）
证明：
（1）、
（2）、（7）显然。
（3）若，则对，当时，必有，即，，可见，；当时，则，故也有。
若，即时，，亦即时必有，所以，。
（4）若，即且。
由（3）得且，所以，。
若，则时，，即时必有，故；时，，即时必有，则时必有，即。
所以，。
（5）且
所以
（6），有以下三种可能：
1）且，则，，，，所以，；
2）且，则，，，，所以，；
3）且，则，，，，所以，。
，则，，，所以，
。
综上所述，
。
（8）由于，则
应用特征函数的一些性质，也可以证明一些集合恒等式。
例4.5.1试证明：
（1）
（2）
证明
（1）因为，所以，。
（2）
所以，
。
例4.5.2设，的子集是：
和，试给出的所有子集的特征函数且建立特征函数与二进制之间的对应关系。
解：
的任何子集的特征函数的值由表4-1列出。
表4-1的任何子集的特征函数的值
0
0
0
1
0
0
0
1
0
0
0
1
1
1
0
1
0
1
0
1
1
1
1
1
如果规定元素的次序为，则每个子集的特征函数与一个三位二进制数相对应。
如。
令，那么表4-1亦可看作从的幂集到的一个双射。
习题4.5
1．设，其中是全集的子集，试用特征函数
来表示。
2．利用特征函数的性质证明下列等式。
（1）
（2）
（3）（4）
*4.6基数
4.6.1无限集合
定义4.6.1如果有一个从集合到的双射函数，那么称集合是有限的，并称为的计数（Counting）（中元素的个数），规定空集的计数为；如果集合不是有限的，则它是无限的。
使用定义4.6.1证明集合是无限集，就要证明对任意，在与之间都不会建立双射。
这种排除无数可能再确立结论的推论方法，其困难是固有的。
一个切实有效的克服困难的选择是：
定义4.6.2称集合是无限集，当且仅当存在到自身的单射，使得。
如果不是无限集，则称它是有限集。
定理4.6.1自然数集合是无限的。
证明存在单射，，并且，。
所以，是无限集。
定理4.6.2子集是无限集合的集合是无限集。
证明若集合的子集是无限集合，则存在上的单射，使得。
扩充到上记为，满足：
若，则；若，则。
显然，是上的单射，且。
所以，是无限集。
子集是无限集合的集合是无限集，其逆否命题是：
有限集合的子集都是有限集合。
定理4.6.3设是任意两个集合且是无限集，则：
（1）若从到存在单射，则也是无限集；
（2）的幂集是无限集；
（3）是无限集；
（4）若，则是无限集；
升级会员 