离散数学电子教材(共30页).doc

《离散数学电子教材(共30页).doc》由会员分享，可在线阅读，更多相关《离散数学电子教材(共30页).doc（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、特征的关系为映射（函数）。定义4.1.1 设是两个任意的集合，而是到的一个关系，若对每一个，都存在一个唯一的，使得，则称关系为到的映射(Mapping)，记作 或若，则称为自变量(Independent Variable)，称为映射在处的值（或像（Image），亦可记作，的值域ran，有时也记为，即或记为集合称为的共域，亦称为映射的像集合。对于，称为的像（Image of ），定义为 显然,，。映射是到的特殊的二元关系，其特殊性在于：（1）dom，即关系的前域是本身，而不是的真子集。（2） 若，则映射在处的值是唯一的，即例4.1.1 设，且有，求 dom、和。解 dom ran 例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）不是映射。（4）是映射。dom ，请注意区别的像和的像两个不同的概念。的像，而像。关于像有下列性

4、质：定理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的

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

6、求证：（1）为到的函数当且仅当。（2）为到的函数当且仅当。3设为一函数，计算，。4设，为：，求，。4.2 特殊映射定义4.2.1 设，（1）如果ran，即的每一个元素都是中一个或多个元素的像，则称这个映射为满射(Surjection)（或到上映射）。（2）如果对于任意，若，则有，则称这个映射为入射(Injection)（或单射）。（3）若既是满射又是入射，则称是双射(Bijection)。 双射也称为11对应(One To One Mapping)。由定义不难看出，如果是满射，则对于任意，必存在，使得成立；如果是入射，则中没有两个不同元素有相同的像，即对于任意，。图 4-3说明了这三类映射之间

7、的关系。注意，既非单射又非满射的函数是大量存在的。 图 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

8、 令和为有限集，若和的元素个数相同，即，则是入射的，当且仅当它是一个满射。证明 （1）若是入射，则。从的定义我们有，而，因为是有限的，故，因此，是一个满射。（2）若是一个满射，则，于是。因为和是有限的，所以，是一个入射。 这个定理必须在有限集情况下才能成立，在无限集上不一定有效，如，这里，在这种情况下整数映射到偶数，显然这是一个入射，但不是满射。另外，还有两个特殊而又重要的映射常映射和恒等映射。定义4.2.2 （1）设，如果存在，使得对所有的都有，即，则称是常映射。（2）任意集合上的恒等关系为一映射，常称为恒等映射，因为对任意都有，即 。对任意，有，故是入射；且，是满射。所以，是双射。习题4.

9、21设分别表示正整数集、整数集、实数集、复数集，试指出下列映射中哪些是单射、满射、双射，并写出定义域和值域。(1) 为。(2) 为。(3) 为。(4) 为。(5) 为。(6) 为（其中为一常数）。2下列关系中哪些能构成映射？。（1），其中为自然数集。（2），其中为实数集。(3) ，其中为实数集。3下列集合能定义成映射吗？如能，试求出它们的定义域及值域。（1）。（2）。（3）。（4）4设映射，这里，（1）定义了何种关系？(2) 的值域是什么？（3）有多少与具有同样定义域和陪域的不同映射？。（4）设的映射且，问可能是单射吗？可能是双射吗？（5）证明存在一个从到的单射，其中为任意集合。（6）设与均是

10、有限集且有个元素，有个元素，说明下列断言为真时，和必须成立的关系：1） 存在从到的单射。2） 存在从到的满射。3） 存在从到的双射。4.3 复合映射和逆映射4.3.1 复合映射因为映射是一种特殊的关系，所以和关系一样也有复合运算。定义4.3.1 设映射，若，则称在映射的左边可复合。对于映射的复合我们有下面的定理：定理4.3.1 设，在映射的左边可复合，即，则是一个映射。证明 (1) 对于任意，因为为映射，故必有唯一的序偶，使成立，而即，又因为是映射，故必有唯一序偶，使成立，根据复合定义，即中每个对应中某个。(2) 假定中包含序偶和，这样在中必存在和，使得在中有和，在中有和。因为是一个映射，故；

11、又因为是一个映射，故，即每个只能有唯一的。由(1)、(2)可知是一个映射。在定义4.3.1中，当时，则映射称为映射与映射的复合映射，或称为对的左复合。注意：在定义4.3.1中，假定random，如果不满足这个条件，则定义为空。根据复合映射的定义，显然有。例4.3.1 设。， ，求。解 例4.3.2 设，均为实函数，。求，。解 所以 定理4.3.2 设是一个复合映射。（1）若和是满射，则是满射。（2）若和是入射，则是入射。（3）若和是双射，则是双射。证明 给定集合，（1），因为是满射，故，使得；又因为是满射，故，使得，所以，即，使得。因此，是满射。（2）对，因为是入射，故；又因为是入射，故，于是

12、所以，是入射。（3）因为和是双射，根据（1）和（2），为满射和入射，即是双射。定理4.3.3 设是一个复合映射。（1）若是满射，则是满射。（2）若是入射，则是入射。（3）若是双射，则是满射，是入射。证明 设 ，。（1） 因为是满射，则，使，故使得，可见，所以是满射。（2）设且。因为是入射，故 ，即，因为是一个映射，则，即所以，是入射。 （3）是双射，则是满射且是入射。是满射，由（1）可知是满射；是入射，由（2）可知是入射。由于映射的复合仍然是一个映射，故可求三个以上映射的复合。例4.3.3 设为实数集合，对，有， 求，与。解： ， 所以有一般地，有如下定理。定理4.3.4 设有函数，和，则有证

13、明 这可由关系的复合的可结合性得出，这里我们直接由映射相等的定义证明。 首先和都是到的函数。另外对任一， 有 由元素的任意性，有 由此可见，映射的复合运算满足结合律，因此多个映射复合时可去掉括号，对3个映射的复合即有。若有，则 仍为到的映射，简记为，一般地 简记为。显然注意：映射的复合运算不满足交换律。例4.3.4 （1）设，则，。所以 。映射的复合运算还有如下明显的性质：定理4.3.5 设映射，则 。 证明 对，有 ，则 所以， 当时，有 4.3.2 逆映射在关系的定义中曾提到，从到的关系，其逆关系是到的关系，但是，对于映射就不能用简单的交换序偶的元素而得到逆映射，这是因为若有映射，但的值域

14、可能只是的一个真子集，即，此时，dom ，这不符合映射对定义域的要求。此外，若的映射是多对一的，即有，其逆关系将有，这就违反了映射值唯一性的要求。为此，有如下定理：定理4.3.6 设是一个双射，那么是的双射。证明 设 ，因为是满射，故对每一，必存在，所以，即的前域为。又因为是入射，对每一个恰有一个，使，即仅有一个，使，对应唯一的，故是映射。因为ran dom ，所以，是满射。又设时，有，令，则，故，即，与假设矛盾。所以，即是单射。因此，是一个双射。定义4.3.2 设是一双射，称的双射为的逆映射，记作。例如，设。若为：，则有，。若 ， 则的逆关系 就不是一个函数。再如，则。函数的逆具有下面一些重

15、要性质。 定理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.31 证明或反驳下列命题：(1)

16、设，为任一映射，则，其中，。(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

17、 设，双射称为集合的置换(Permutation)，记作这里，中元素的个数称作置换的阶。 定理4.4.1 在个元素的集合中，不同的阶置换的总数为！个。 证明 形如：中的可以取的任意一个全排列，故总数为！个。定义4.4.2 给定，恒等映射称为集合上的恒等置换(Identical Permutation)，记作定义4.4.3 设是集合的置换，如果可以取到的元素，使，且的其余元素（如果还有的话）不变，则称为一个轮换，记为。若，则的个置换都是轮换，它们分别记为和。当时，置换不是轮换。一般地，时，的置换都是轮换；时，的置换未必是轮换。定义4.4.4 把置换看作定义在集合上的双射，置换的复合定义为相应映射

18、复合构成的置换。例如， ， 则 ， 可见，。两个轮换与的复合记为： 。定义4.4.5给定，对任意的阶置换记容易验证我们称为的逆置换。 集合上的所有阶置换的全体记作。置换的复合有以下性质：（1）对于复合运算是封闭的；（2）结合律成立，即，有；（3）中有一个元素称为恒等置换，使对任意有；（4）任意，都存在有逆置换，使。习题4.41若，试写出上的全部置换，并指出各置换的逆。 2设，是上的置换， ，求 ， ，及。 3已知 ， ， ，请验证：。4设，计算。5设，上的置换，。求（1）；（2）。*4.5 特征函数有些映射与集合之间可以建立一些特殊的关系，借助于这些映射，可对集合进行运算。定义4.5.1 令是

19、全集，由定义的映射，称为集合的特征函数(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）由于，则 应用特征函数的一些性

20、质，也可以证明一些集合恒等式。例4.5.1 试证明： （1） （2） 证明 （1） 因为 ，所以，。 （2） 所以，。例4.5.2 设，的子集是：和，试给出的所有子集的特征函数且建立特征函数与二进制之间的对应关系。解：的任何子集的特征函数的值由表4-1列出。表4-1 的任何子集的特征函数的值 000100010001110101011111如果规定元素的次序为，则每个子集的特征函数与一个三位二进制数相对应。如。令，那么表4-1亦可看作从的幂集到的一个双射。习题4.51设，其中是全集的子集，试用特征函数来表示。2利用特征函数的性质证明下列等式。(1) (2) (3) (4) *4.6 基数4.6

21、.1 无限集合 定义4.6.1 如果有一个从集合到的双射函数，那么称集合是有限的，并称为的计数(Counting)（中元素的个数），规定空集的计数为；如果集合不是有限的，则它是无限的。使用定义4.6.1证明集合是无限集，就要证明对任意，在与之间都不会建立双射。这种排除无数可能再确立结论的推论方法，其困难是固有的。一个切实有效的克服困难的选择是：定义4.6.2 称集合是无限集，当且仅当存在到自身的单射，使得。如果不是无限集，则称它是有限集。定理4.6.1 自然数集合是无限的。证明 存在单射，并且，。所以，是无限集。定理4.6.2 子集是无限集合的集合是无限集。证明 若集合的子集是无限集合，则存在

22、上的单射，使得。扩充到上记为，满足：若，则；若，则。显然，是上的单射，且 。所以，是无限集。子集是无限集合的集合是无限集，其逆否命题是：有限集合的子集都是有限集合。定理4.6.3 设是任意两个集合且是无限集，则：（1） 若从到存在单射，则也是无限集；（2） 的幂集是无限集；（3） 是无限集；（4） 若，则是无限集； 证明 仅证（1），其余都是（1）的推论。是无限集，存在单射，使得。是从到的单射，是从到的双射，存在逆映射。定义映射，满足：若，则；，则。由于都是单射，所以是上的单射，且 所以，是无限集。4.6.2 基数的概念 两个集合，如果它们都是有限集，其中元素哪个多哪个少是很容易知道的，只要比

23、较有限集的计数即可。但是，如果两个集合都是无限集，怎样比较它们的元素哪个多哪个少呢？例如，自然数集，正偶数集，整数集，实数集。 设与是两个集合，若中元素和中元素可以一一对应，即存在到的一个双射，这意味着的元素个数和B的元素个数一样多。但这句话很不确切，因为在无限集的情形下，谈不上其中元素个数是多少。在集合论中，若集合中元素和中元素可以一一对应，我们不说它们的元素个数相等，而说它们有相同的势。定义4.6.3 对于集合与，如果存在着从到的双射，则称与为等势的(Equivalent)，或称与对等(Equipollent)，记作。例4.6.1 验证自然数集与非负偶数集合是等势的。证明 与的元素之间可做

24、双射，即， 所以，与等势。例4.6.2 设为实数集合，是的子集，即，且 证明： 证明 令， 显然的值域是，是双射函数，所以。定理4.6.4 集合族上等势关系是一个等价关系。证明 设集合族为（1）对任意，恒等映射是到的双射，所以；（2）对任意，如果，则存在到的双射，从而为到的双射，故；（3）对任意，如果且，则存在到的双射和到的双射，由定理4.3.2知是到的双射，故。综合（1）、（2）和（3）知集合族上的等势关系是一个等价关系。显然，两个有限集对等，当且仅当它们的计数相等。即根据计数是否相等就能判断两个有限集是否对等。很自然，我们希望将有限集的计数这个概念推广到无限集。定义4.6.4 我们将相互对

25、等的集合归为同一类，不对等的集合不属于同一类，对每类集合予以一个记号，称这个记号是这一类集合中每个集合的基数(Cardinal Number)（势，浓度，权）。集合的基数记为。并规定计数就是有限集合的基数。定义4.6.5 设、是两个集合。（1） 如果，就称与的基数相同，记作；（2） 如果存在从到的入射，就称的基数小于等于的基数，记作；（3） 如果且，就称的基数小于的基数，记作 。例4.6.3 证明区间与基数相同。证明 设集合，。定义 使得则是双射，故区间与基数相同。4.6.3 可数集与不可数集定义4.6.6 我们称自然数集的基数为，称为可列基数(Countable Cardinal Numbe

26、r)。凡与自然数集对等的任意集合称为可列集（或可数集）(Countable Set)。例如， ，均为可数集。定义4.6.7 如果集合是有限的或无限可数的，则统称为至多可数的。如果集合是无限的且是不可数的，则称是不可数的(Non-countable)。定理4.6.5 为可数集的充分必要条件是可以排列成 的形式。证明 若可排成上述形式，那么将的元素与脚标对应，就得到与之间的双射，故是可数集。反之，若为可数集，那么在与之间存在一个双射，由得到的对应元素,即可写为的形式。定理4.6.6 任一无限集，必含有可数子集。证明 设为无限集合，从中取出一个元素，因为是无限的，它不因取出而耗尽，所以，从中可取元素

27、，则也是非空集，所以又可取一元素，如此继续下去，就得到的可数子集。定理4.6.7 集合是无限集，当且仅当与的一个真子集对等。证明留给读者。这一定理告诉我们任何一个无限集必定可以和它的某个真子集对等，这对于有限集来说是绝对不可能做到的。因此，能否和自己的某个真子集对等，这是无限集和有限集的本质区别。定理4.6.8 下列各结论成立：（1）可数集的任何无限子集是可数的；（2）有限或可数个可数集的并是可数集；（3）有限个可数集的直积是可数集。证明 （1）设为可数集合，为一无限子集，如将的元素排成，从开始，向后检查，不断地删去不在中的元素，则得到新的一列，它与自然数集对等，所以是可数的。（2）只需证明可

28、数多个可数集的并是可数集。设可数个可数集分别表示为：令，即，对的元素排列如下：按上面箭头指向的顺序排列得到，从中删去重复的元素。这样，中的元素可以排成一个无穷序列，故是可数集。（3）证明留给读者。定理4.6.9 有理数的全体组成的集合是可数集。证明 设和分别表示全体正有理数和全体负有理数组成的集合，则 由于每一个正有理数都可以表示为的形式，其中都是正整数，对于每一个正整数，令则有 显然，是可数集。由定理4.6.8，可数个可数集的并是可数集，所以是可数集。易知，由于，由对等的传递性，则。再应用有限个可数集的并是可数集，则是可数集。 并非所有无限集合都是可数的，例如，实数集合就是不可数的。定理4.

29、6.10 全体实数构成的集合是不可数的。证明 作映射 显然，是双射，所以。 我们只需证明不可数。用反证法。假设是可数的，则必可表示为：，其中是上的任一实数，它可写成无穷小数的形式。设 ，其中（如和可记为和），设 其次，我们构造一个实数使 显然，且与各数至少有一位数是不同的，因为对于任何一个，若中，则中；若，则。因此，和的小数第位数字是不同的，即（）。这就证明了，产生矛盾，因此，是不可数的，即是不可数集。我们把集合的基数记为“”，因为，故 。“”称作连续基数。习题4.61下列集合的基数是什么？（1）。 （2）。（3）都是整数。 （4）都是有理数。（5）是由所有半径为，圆心在轴上的圆周所组成的集合。（6）是由所有圆心在原点的圆周所组成的集合。（7）是由所有圆心在原点，以正有理数为半径的圆周所组成的集合。2证明下列集合是可数的。（1）。 （2）。（3）（1）与（2）中两集合的并。 （4）都是有理数。3构造从到下列集合的一个双射，以证明它们有基数。（1）。 （2） （3） （4）专心-专注-专业