离散数学

出版时间：2011-10  出版社：清华大学出版社  作者：贲可荣，袁景凌，高志华　编著  

前言

　  回顾过去的一个世纪，数学科学的巨大发展，比以往任何时代都更牢固地确立了它作为整个科学技术领域的基础的地位。数学正突破传统的应用范围向几乎所有的人类知识领域渗透，并越来越直接地为人类物质生产与日常生活作出贡献。同时，数学作为一种文化，已成为人类进步的标志。因此，对于当今社会每一个有文化的人士而言，不论他从事何种职业，都需要学习数学，了解数学和运用数学。现代社会对数学的这种需要，在新的世纪中无疑将更加与日俱增。20世纪数学思想的深刻变革，已将数学这门科学的核心部分引向高度抽象化的道路。面对各种深奥的数学理论和复杂的数学方法，门外汉往往只能望而却步。　  一个本质上简单的学科却难以学习。有些困难是表面的，其一是词汇。数学家用一些对普通人来说很生僻的词来表达从实际事物中抽象出来的概念。如“四边形”和“平行四边形”有一些在其他领域遇不到的特定的精确含意，要研究数学就得学着用。另一个看得见的但同样是表面的困难是使用符号。我们要解决问题，可以以某些给定的信息为基础决定一个未知数。设此未知数是某一个长度以尺计的数字。用x去代表这个长度，而之后就只用符号x而不去说那么长的一句话，肯定是有利的，然而使用符号不会产生任何概念上的困难。　  人们能想到的第三个困难是抽象性。但是由于基本的抽象概念是直接来自日常经验的，人们很容易记住它们的含义。事实上，数学家不断地诉诸物理对象和物理图像，以便记住这些抽象概念的含义。古希腊数学家用小石子代表各类对象，用小石子学会了自然数的基本事实。顺便说一下，“计算”一词，广义地表示任一个算术或代数过程，它的英文Calculus的拉丁语源就是“小石子”。甚至更高级的数学抽象，如微积分学中的导数和积分，说到底离这些初等概念仅一步之隔，甚至微积分的概念也有图像的物理的意义。要学会这些抽象概念，并不比学习初等概念要求更高的智力。离散数学（第2版）第1版序  数学的完全的形式是一系列概念、一系列程序，例如求解某种类型方程的方法，以及一系列事实，例如定理。当然，程序和定理都要通过证明来确认。要想教会人这些数学元素，最容易的方法似乎莫过于用这些概念、过程、定理与证明的最终的、确定的形式去教学生。但是数学是一门老学科，它的某些重大的成就可以追溯到公元前3000年，过去五千多年里数学家不仅极大地扩大了这个学科的领域，当他们不断认识了新的客体和现象，当他们不断改进自己的理解，他们也重塑了这些概念、程序与证明来把这些成就组合起来。而这些订正了的版本中有许多就不再清晰易懂了。　  此外，数学的分量在增加，因此最好把它组织起来，使关于同一主题的许多定理有合乎逻辑的次序。每一门学科的基础是公理，其后就是一串定理，每一个定理都用公理和前面已证的定理来证明。把结果按这样的合乎逻辑的次序来安排，这就需要数学家找出新的、不甚自然的、不甚明白的证明。结果是许多证明都被除去了它们的直观、透明和易于理解的面貌，而被十分人为的证明代替了。　  表述上的有效性似乎导致数学的另一个特点被忽视了，而这个特点对于理解数学却是至关重要的。数学本身是一副骨骼。数学的血肉和生命在于用数学做什么。有意义的数学要为一种目的服务，这种目的用笛卡儿的话来说，就是使人成为大自然的主人和占有者。数学的意义在于数学本身之外，正如好的文学作品的意义在于纸面上堆积的文字之外。要懂得数学就要知道为什么需要这个结果，它和其他结果的关系如何，用它可以做些什么事。　  学校由于它的目的和繁多的义务，有时能够，有时又不能够给数学一种更有启发性的讲法。有志于此的学生必须要走得远一些，寻求一种完全的知识。要对数学有较彻底的理解与领会，就必须去掉那些纤巧的细节，深入到其深层的思想之中；就必须知道它的目的和用处，知道创造它的人们的动机，以及这些概念和结构的创生背景。　  创造性的活动，对学生来说则是再创造的活动，是数学的心脏。正是在这种活动中，数学家创造了最高成就，克服了最大的困难并使数学这门学科取得了最有意义的进展。创造过程不仅在解决已有问题时必不可少。没有新观点、新研究方法和新目标的创造，数学就会反反复复重新组织老的证明，使它们更加严格，并在这样的过程中日趋枯竭，丧失生命力。对已经得到的知识，重新排列其步骤，安排其定理的次序来构成一个演绎的组织，这时常需要创意，但从总体上说，这更像是把书本重新排一个次序。而这种创造的活动可以比作写书。数学给人的满足--获得猎物时的兴奋，发现的激动，成就的感觉，以及成功时的欢乐--更多更强烈的是在创造性的工作之中，而不是在最后按演绎的模式来重写论证之中。　  数学中有许多美的篇章。无疑，数学家从事数学活动也能获得其他创造活动提供的满足感，但是伟大的数学家情愿把数学的美作为一种额外报偿，激励他们奋斗的最深层的动力则是以数学为媒介在人类的探索活动中理解宇宙，也理解人类自身在其中的角色，并且探求如何利用自然现象和自然的力量为人类服务。那些作出巨大贡献的数学家们，像阿基米德、牛顿、拉格朗日、拉普拉斯、高斯、哈密顿、庞加莱，或者是一流的物理学家，或者在科学史中占据显要地位。这绝不是偶然的。几乎所有数学的目的和意义并不在于对于一堆符号作一系列的逻辑阐述，而在于这些符号必定告诉我们一些关于外部世界的知识。　  离散数学是计算机科学的基础　  离散数学是计算机专业最重要的必修课程之一，它是许多计算机专业课程的基础。　  离散数学是研究离散对象的数量和空间关系的数学，它包括多个数学分支，如本书所涉及到的集合论、图论、组合数学、古典概率、自动机理论等，是计算机科学的理论基础，也是计算机应用的有力工具。另一方面，计算机科学的发展又促进了离散数学的发展。18世纪以前的数学基本上都属于离散数学的范畴，以后，天文学、物理学等的发展极大地推动了连续数学（如微积分）的发展，直到20世纪中期，尤其是20世纪80年代以后，随着计算机日益渗透到现代社会的各个方面，离散数学又重新受到高度重视。当然，离散数学涉及的内容极其广泛，其应用全然不是仅局限于计算机科学及其应用，而是涉及到我们生活的方方面面。　  由于数字计算机软硬件结构决定了它仅适于处理离散型信息的存储与计算，因此离散数学便成为计算机科学与技术的基本数学工具。某些理论上的“先见之明”，将会给以后学科的发展带来巨大的影响。例如，对可计算的研究所建立的图灵机是计算机的理论模型，随后这种理念导致了计算机的诞生。布尔的逻辑代数已成功地用于计算机的硬件分析与设计。谓词逻辑演算为人工智能学科提供了一种重要的知识表示方法和推理方法。这些都体现了离散数学的重要作用。对于离散数学的原理和方法，经常要求其在计算机上的可实现性；而一般的数学理论和方法有时仅给出存在性的结论，并不给出构造性的问题解答，因此难以满足实用性的要求。现代数字计算机的理论模型依然是20世纪30年代提出的图灵机，这是一种“离散”的机器，可用来处理“离散”的对象。当然，正如大多数计算机的早期应用，通过近似计算等手段，计算机也可以处理“连续”的对象，但现代的数字计算机仍然是一种“离散”的机器。事实上，目前计算机已经越来越多地用于处理各种“离散”的对象。　  随着计算机技术的发展，离散数学作为计算机科学的一种数学工具，其作用显得越来越重要。对于一种程序设计语言来说，我们需要了解一些相关的问题： 为什么会提出这种语言？它能解决什么问题？优势是什么？存在什么问题？它的语法、语义怎么样？利用该语言编写的程序必然是正确的吗？更深入的分析就是，计算机到底能做些什么？不能做些什么？什么是可计算的，什么是不可计算的，以及计算的复杂性又怎样？只有懂得一些深刻的基础性数学知识，才能对这些问题给出较为准确的回答。　  离散数学为什么作为计算机专业学生的基础课？美国数学会主席Lynn A。 Steen回答了该问题：But today's growth industries are dominated by information， which is abstract and immaterial。 Where the material world is modeled by calculus， the language of continuous change， the immaterial world of information requires discontinuous discrete mathematics。 Both genetic codes and computer codes are intrinsically discrete。 Discrete mathematics basically deals with fancy ways of arranging and counting。 It can be used to enumerate genetic patterns and to count the branches in computer algorithms； it can be used to analyze the treelike branching of arteries and nerves，as well as the cascading options in a succession of either-or decisions。 It can tell us how many things are there as well as help us find what we want among a bewildering morass of possibilities。　  离散数学的主要内容　  由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系。因此无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立数学模型又如何将已经用连续数量关系建立起来的数学模型离散化，从而可以用计算机加工处理的问题。离散数学是数学里专门用来研究离散对象的一个数学分支，是计算机专业的一门重要的基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。　  20 世纪 70 年代，国外开始将离散数学作为一门大学课程。当时，有一些计算机科学家根据自己对计算机科学的理解，与一些数学家一起圈定了一些他们认为对计算机科学是必需的数学专题，结合计算机科学中的一些实例编著了一些主要命名为“离散数学结构和方法”或“离散数学基础”之类的书籍，并开设相应的课程供大学里学习计算机专业和其他一些相关工程专业的学生选修。由于反响很好，渐渐在计算机专业中，“离散数学”即作为必修课来开设。我国是在大约 20 世纪 80 年代初期，从翻译国外离散数学专著开始，逐渐编写了一些适合我国教学情况的离散数学的教材，并在计算机系中开设了相应的课程。　  如上所述，由于各专家对于计算机的主攻方向和他们对计算机教学的理解不尽相同，因此，在“离散数学”名下的内容也不完全一样。本书根据ACM和IEEE/CS最新推出的Computing Curricula 2004以及教育部高等教育司组织评审通过的《中国计算机科学与技术学科教程2002》中制定的关于“离散数学”的知识结构和体系撰写。全书共10章，主要包含数理逻辑、集合与关系、函数、图和树、组合计数、数论与递归关系、代数系统、自动机、文法和语言等内容，基本上涵盖了计算机专业所必需的数学内容。离散数学这门课程，主要介绍各分支的基本概念、基本理论和基本方法，这些知识将应用于数字电路、编译原理、数据结构、操作系统、数据库原理、算法分析与设计、人工智能、软件工程、计算机网络等专业课程之中。　  学习离散数学的方法　  离散数学是计算机科学系所有专业的基础数学课程，一方面具有实用性（应用数学的特征），另一方面又具有作为数学基础课的理论的严谨性。所以，学习任何一个专题时，首先要精确严格地掌握好概念和术语，正确理解它们的内涵和外延。因为公理、定理或定律的基石都是概念，只有正确地理解概念，才能把握定理的实质，熟练地将公理、定理应用于解决问题。完全地、精确地掌握一个概念的方法是首先深刻理解概念的内涵，然后举一些属于和不属于该概念外延的正反两方面的实例。如果对一些似是而非的例子也能辨别的话，应该说就已经真正地理解这个概念了。对一些重要的概念，能记住一两个实例也是很有好处的。　  读者应养成一种自觉的学习习惯，首先要掌握好基本概念和术语，然后在此基础上，理解每个基本定理的本质，最后通过学习和借鉴书中提供的例题，独立地完成每一次作业，并且在每次作业完成之后，自觉地归纳出其中用到的基本解题方法。注意，千万不要在完全理解相关概念和基本定理之前就匆忙去做相应的习题。　  学习数学的唯一途径是实践。就好像仅看别人怎么做，你是不可能学会弹吉他或投篮的，你也不可能仅靠阅读本书或听课就学好离散数学。你必须积极主动地思考。在阅读数学书时，你应该在手头随时备好笔和纸，以便进行详细的推导和计算。在听数学课前，你最好先阅读有关的内容，这样，你就可以专注于你对内容的理解是否与教授的理解相一致，还可以就一些难点提问。本书中有很多习题，有些是纯粹的计算题，有些测试对概念的理解，有些要求给出论证，建议读者多做。　  学习和理解术语也很重要。在数学中，传统的做法是对一些简单、常见的词汇赋予特殊的含义，如集合、函数、关系、图、树、网络。这些词都有严格的定义，必须认真学习，否则你就不能理解你在书中读到的内容和教授所讲述的课程。术语能帮助你有效地与别人共享信息，而且在现实生活中，仅仅简单地计算出某些东西往往不够，还必须能够向别人解释，使别人确信你的解是正确的。　  我们期待你成功地学好离散数学，并从中学到许多技术和观点，你将会发现它们在许多地方都是有用的。　  对数学和逻辑的感悟得益于我的老师们，他们是陈火旺先生、莫绍揆先生、王世强先生、康宏逵先生、齐治昌先生、胡静婉老师、丁德成老师，也获益于我的同学们，包括沈恩绍、宋方敏、王公宝、王怀民、王戟、王献昌，如果本书有什么新意的地方，应首先归功于他们。　  本书第1～4章、第6章、第8～9章及附录由贲可荣、高志华撰写，第5， 7， 10章由袁景凌撰写，全书由贲可荣统稿。在本书撰写过程中，钟珞教授、郭福亮教授给予了多方面的支持。武汉大学计算机学院院长何炎祥教授对全书进行了审校，特此致谢。　  贲可荣2007年1月

内容概要

　　离散数学是数学中专门用来研究离散对象及其关系的一个分支，是计算机科学与技术专业的一门重要基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。全书共10章，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。本书中的“历史注记”可以帮助读者理解数学，洞察内在本质。
　　《离散数学(第2版)》体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，书中选配了大量难度适当的习题，并给出奇数题的答案，适合教学。本书适合作为计算机和相关专业本科生“离散数学”的教学用书，亦可作为对离散数学感兴趣的人员的参考书。

书籍目录

第1章 命题逻辑1
　1.1 现代逻辑学的基本研究方法1
　1.2 命题及其表示法3
　　1.2.1 命题的概念3
　　1.2.2 联结词4
　1.3 命题公式与语句形式化7
　　1.3.1 命题公式的定义7
　　1.3.2 公式的层次8
　　1.3.3 语句形式化8
　　1.3.4 复合命题真假值9
　　1.3.5 真值表10
　1.4 重言式11
　　1.4.1 重言式概述11
　　1.4.2 逻辑等价式13
　　1.4.3 等值演算15
　1.5 对偶与范式16
　　1.5.1 对偶16
　　1.5.2 简单合取式和简单析取式16
　　1.5.3 范式17
　　1.5.4 范式的唯一性--主范式19
　1.6 其他联结词24
　　1.6.1 n元真值函数24
　　1.6.2 真值函数与命题公式的关系25
　　1.6.3 联结词完备集25
　　1.6.4 单元素联结词构成的联结词完备集26
　1.7 命题演算的推理理论27
　　1.7.1 有效推理27
　　1.7.2 有效推理的等价定理29离散数学（第2版）
　　1.7.3 重言蕴涵式31
　　1.7.4 形式推理系统32
　　1.7.5 自然推理系统p235
　1.8 命题演算中的归结推理42
　　1.8.1 归结推理规则42
　　1.8.2 归结反演43
　　1.8.3 命题逻辑归结反演的合理性和完备性44
　　习题44
第2章 谓词逻辑53
　2.1 谓词逻辑的基本概念53
　　2.1.1 个体词54
　　2.1.2 谓词54
　　2.1.3 量词55
　2.2 谓词逻辑公式与翻译56
　　2.2.1 一阶语言56
　　2.2.2 自由与约束57
　　2.2.3 闭公式58
　　2.2.4 谓词逻辑公式的解释59
　　2.2.5 谓词逻辑命题符号化60
　　2.2.6 一阶公式的分类63
　2.3 谓词逻辑等值演算64
　　2.3.1 基本等价式与置换规则64
　　2.3.2 谓词逻辑前束范式68
　2.4 谓词演算的推理理论69
　　2.4.1 推理定律69
　　2.4.2 量词消去与引入规则70
　　2.4.3 一阶谓词演算公理系统f171
　　2.4.4 自然推理系统f272
　2.5 谓词演算中的归结推理74
　　2.5.1 子句型74
　　2.5.2 置换和合一76
　　2.5.3 合一算法78
　　2.5.4 归结式79
　　2.5.5 归结反演及其完备性80
　2.6 逻辑在计算机科学中的作用81
　　2.6.1 逻辑与计算81
　　2.6.2 逻辑与计算机的起源82
　　2.6.3 逻辑与程序设计83
　　习题84
第3章 集合与关系90
　3.1 集合的概念和表示法90
　　3.1.1 集合的表示90
　　3.1.2 基本概念92
　3.2 集合的运算93
　　3.2.1 集合的基本运算93
　　3.2.2 有穷计数集93
　　3.2.3 广义交和广义并95
　3.3 有序对与笛卡儿积97
　3.4 关系及其表示99
　　3.4.1 基本概念99
　　3.4.2 关系表示法100
　3.5 关系的运算102
　　3.5.1 基本概念102
　　3.5.2 复合关系103
　　3.5.3 逆关系104
　　3.5.4 关系幂106
　　3.5.5 幂运算的性质107
　3.6 关系的性质109
　　3.6.1 关系的5种基本性质109
　　3.6.2 关系性质的等价描述 110
　3.7 关系的闭包113
　　3.7.1 基本概念114
　　3.7.2 闭包的性质118
　3.8 集合的划分与覆盖119
　3.9 等价关系和等价类120
　　3.9.1 等价关系120
　　3.9.2 等价类的性质122
　　3.9.3 商集与划分123
　3.10 相容关系和相容类124
　3.11 偏序关系125
　3.12 偏序集与哈斯图126
　3.13 包含排斥原理129
　　习题130
第4章 函数137
　　4.1 函数的定义137
　　4.1.1 函数和像137
　　4.1.2 函数的性质139
　　4.1.3 常用函数140
　　4.2 复合函数和反函数141
　　4.2.1 复合函数 141
　　4.2.2 反函数143
　　4.3 特征函数与模糊子集145
　　4.4 基数的概念147
　　4.4.1 后继与归纳集147
　　4.4.2 自然数，有穷集，无穷集148
　　4.4.3 基数152
　　4.5 可数集与不可数集153
　　4.6 数学归纳法155
　　习题158
第5章 组合计数与离散概率162
　5.1 基本原理162
　　5.1.1 加法原理162
　　5.1.2 乘法原理163
　5.2 排列与组合164
　　5.2.1 排列164
　　5.2.2 组合164
　5.3 排列组合生成算法165
　　5.3.1 排列生成算法165
　　5.3.2 组合生成算法 166
　5.4 广义的排列和组合169
　5.5 二项式系数和组合恒等式171
　　5.5.1 二项式定理171
　　5.5.2 组合恒等式172
　5.6 鸽笼原理174
　　5.6.1 鸽笼原理的简单形式174
　　5.6.2 鸽笼原理的一般形式174
　5.7 递推关系及应用176
　　5.7.1 递推定义函数176
　　5.7.2 递推定义集合178
　　5.7.3 递推关系模型179
　　5.7.4 求解递推关系181
　　5.7.5 递推在算法分析中的应用183
　　5.7.6 生成函数187
　5.8 离散概率190
　　5.8.1 随机事件与概率190
　　5.8.2 有限概率191
　　5.8.3 条件概率与独立性 193
　　5.8.4 bayes定理194
　　习题195
第6章 图论198
　6.1 图的基本概念198
　　6.1.1 图的定义和表示198
　　6.1.2 图的同构 202
　　6.1.3 完全图与正则图 204
　　6.1.4 子图与补图204
　　6.1.5 通路与回路206
　6.2 图的连通性208
　　6.2.1 无向图的连通性208
　　6.2.2 有向图的连通性209
　6.3 图的矩阵表示210
　　6.3.1 关联矩阵210
　　6.3.2 有向图的邻接矩阵211
　　6.3.3 有向图的可达矩阵 212
　6.4 欧拉图213
　6.5 哈密顿图215
　6.6 二部图218
　　6.6.1 二部图及判别定理218
　　6.6.2 完备匹配219
　6.7 平面图221
　　6.7.1 平面图及其判定定理221
　　6.7.2 平面图的对偶图226
　6.8 带权图228
　　习题229
第7章 树及其应用237
　7.1 概述237
　　7.1.1 树的定义及相关术语237
　　7.1.2 树的性质239
　7.2 生成树240
　7.3 最小生成树243
　7.4 树的遍历246
　7.5 二叉树248
　　7.5.1 二叉树的性质248
　　7.5.2 二叉搜索树249
　　7.5.3 哈夫曼树250
　7.6 决策树252
　　7.6.1 决策树的定义252
　　7.6.2 最短时间排序253
　7.7 树的同构254
　7.8 博弈树258
　　7.8.1 博弈树的概念258
　　7.8.2 极大极小分析法258
　　习题260
第8章 代数系统264
　8.1 二元运算及其性质264
　　8.1.1 定义和表示 264
　　8.1.2 二元运算的性质 266
　8.2 代数系统268
　　8.2.1 定义和实例268
　　8.2.2 子代数系统270
　　8.2.3 代数系统的同态与同构270
　8.3 半群与独异点271
　　8.3.1 定义与性质271
　　8.3.2 子系统与直积273
　8.4 群273
　　8.4.1 群的定义 273
　　8.4.2 群的性质 275
　　8.4.3 子群的定义 278
　　8.4.4 特殊的群279
　　8.4.5 陪集与拉格朗日定理282
　　8.4.6 正规子群与商群283
　　8.4.7 群的同态与同构实例286
　8.5 环与域288
　　8.5.1 环288
　　8.5.2 域289
　8.6 格与布尔代数290
　　8.6.1 格290
　　8.6.2 布尔代数295
　8.7 组合电路297
　　习题299
第9章 自动机、文法和语言306
　9.1 串和语言306
　9.2 形式文法307
　9.3 有限状态机310
　9.4 有限状态自动机312
　9.5 不确定有限状态自动机315
　9.6 语言和自动机之间的关系318
　　习题319
第10章 初等数论322
　10.1 素数322
　10.2 最大公约数与最小公倍数323
　10.3 同余326
　10.4 一次同余方程和中国剩余定理328
　　10.4.1 一次同余方程328
　　10.4.2 中国剩余定理329
　10.5 欧拉定理和费马小定理330
　10.6 数论在密码学中的应用331
　　10.6.1 公钥密码学331
　　10.6.2 rsa密码332
　　习题333
附录 历史注记335
习题答案348
参考文献370

章节摘录

版权页：插图：