译者序

离散数学以研究离散量的结构和相互间的关系为主要目标， 包括数理逻辑、集合论、数论、图论、组合学和计算几何等，是计算机科学与技术专业的一门重要基础课。
本书的第一版出版于上个世纪80年代，那时许多大学需要一门涉及组合数学、算法和图论等内容的课程来拓宽学生的数学知识和处理抽象概念的能力。该书的出版满足了这种需求，并对以后离散数学课程的发展产生了深远的影响。本版本的离散数学教材，不仅包括了算法、组合数学、集合、函数、数学归纳法等内容，同时还涉及证明的理解和构造技术，通过学习，学生可提高数学涵养，能更好理解后序课程的内容。
自本书第4版引进国内，本书译者就一直使用该教材于离散数学课程的教学。从内容上看，这是一本深入浅出的好教材，不要求学生具备任何预备知识，可广泛应用于普通高等院校、成人教育、远程教育和高等专科学校计算机相关专业的离散数学教学。可以说这是国内目前可见的最明了、简单的离散数学教材，可适用于任何层次的学生以不同的途径学习，包括自学和网络教学。
本书由上海交通大学计算机系的黄林鹏教授、陈俊清博士和王欣博士共同翻译，由黄林鹏审校。此外还要感谢彭冲、王德俊、徐小辉、伍建焜、张迎春、冯志宇、杨欢和林海源等的帮助。
这里还要提一下我的研究生导师左孝凌教授，他在上个世纪80年代撰写的离散数学教材曾再版30余次，影响了几代学子。译者在1986至1988年间作为他的研究生，在他指导下开始学习离散数学知识，再此饮水思源，并表示感谢。
由于译者水平所限，错误难免，译文不当不周之处难免，敬请读者将意见寄到lphuang@sjtu.edu.cn，不胜感激。

这本新版的离散数学书籍，是基于作者多年来的教学经验并根据读者意见修改而成，可作为一个或两个学期的离散数学课程的教材，本书不需要作者先期掌握形式化方法，也不需要具备微积分的知识，当然更不需要计算机科学的前期知识。本书包括例题、练习、图表、问题求解要点，每个章节还包括复习、注释、自测题和上机练习等，这些丰富的材料可帮助读者快速掌握离散数学的基本知识。与本书配套的材料还包括教学参考书和Web站点。
     在20世纪80年代初期，几乎没有离散数学入门课程的合适教材。但那时许多大学需要一门涉及组合数学、算法和图论等内容的课程来拓宽学生的数学知识和处理抽象概念的能力。本书第一版（1984）的出版满足了这种需求，并对离散数学课程的发展产生了深远的影响。此后，离散数学课程得到了包括数学和计算机等专业的许多学科的认可。美国数学学会（MAA）的一个专门小组曾提议离散数学应作为一学年的课程讲授。电气和电子工程师协会（IEEE）的教育委员会也建议在大学一年级开设离散数学课程。随后，美国计算机学会（ACM）和IEEE给出了离散数学课程的推荐性大纲。本版和前面各版一样，不仅包括了算法、组合数学、集合、函数、数学归纳法等被这些组织所认可的内容，同时还涉及证明的理解和构造技术，学生通过学习可提高数学上的涵养。

逻辑和证明发方面的修改
本书第7版的修改来自于许多读者对本书先前版本的意见和要求。对第6版的最大修改是第1章到第3章。本书第6版的第1章，逻辑和证明，在第7版中被分为两章，集合与逻辑（第1章）和证明（第2章）。除了集合一节，第6版中的第2章（数学的语言）和第3章（关系）被合并为第7版中的第3章（函数、序列和关系）。从本书预印版已经看出读者对于这些修改的热切期望。
集合一节现在是本书的第一节。这种改变使本书可以自始至终使用与集合相关的术语。现在可以在例子和练习的证明中使用集合的概念，由此可以给出比先前版本更有意思的例子。甚至可以在完整讨论证明和证明技术之前就可以使用集合来引入证明的概念（例如，证明两个集合是相等的，证明一个集合是另一个集合的子集）。
对于证明构造技术的内容也大大拓广了。2.1和2.2节是和数学系统、证明技术相关的新章节。除此之外，还有关于等价性证明和存在性证明（包括构造和非构造存在性证明）的扩展内容。几乎每一个证明都有前导性的讨论章节和/或伴随的图解。问题求解部分包括了如何进行证明，如何书写证明以及证明中常见的错误等额外的建议和例子。有两个新的问题求解段落，一是关于量词的，另一个与证明有关（参见证明实数的若干性质）。
关于证明的论据和规则的讨论则被移到关于命题的讨论之后。与量词有关的推理规则被整合进量词一节。
例子和习题的数量也有了大量的提升。在第6版，前3章大约有1370个例子和习题。而在第7版，前3章大约有1640个例子和习题。当然，不仅数量增加了，质量也得到了提高。对于第6版中的大部分例子，第7版都进行了讨论并增加了分析。

对第6版所进行的其他修改
对第6版所进行的其他修改如下：
* 在本书前头就引入了整数（Z，Z#+，Z#-，Z＃nonneg）、有理数（用Q代替Z）、实数（用R代替Z）的概念描述和记法（见1.1节，集合）。
* 给出定理5.1.17和定理5.1.22的证明，本书第6版只是给出证明概要，这两个定理描述了从给定的两个整数的素因子表示法中得出最大公因子和最小公倍数的过程。
* 给出计算两个整数a和b的最大公因子的递归算法gcd(a,b)，以及如何计算满足gcd(a,b)=sa+tb的整数s和t的算法。
* 6.1节增加了包含排斥原理。
* 6.1节增加了几个实例以说明乘法原理和加法原理的应用。这些例子所处的位置在读者了解该使用何种原理或混合使用两种原理之前。
* 和广义排列组合有关的章节（第6版中的6.6节）现在放在6.1节和6.2节之后（基本原理、排列和组合），因为广义排列组合的概念和6.1节、6.2节中的材料较为相近。
* 在介绍鸽巢（6.9节）之前给出了一些简单、直接的“热身”练习。
* 加入更多的（8.6节）图同构的练习，练习分为3类，一类要求给出两个给定的图是同构的证明，另一类要求给出两个给定的图不是同构的说明，还有一类是要求读者确定是否两个给定的图是同构的并给出证明。
* 9.3节新增了一些使用回溯法的练习，包括流行的数独智力游戏。
* 给出更多的例子和练习以提示常见的错误（例如，在2.1节复习和练习前的“常见错误”部分就给出了一些证明中常见的错误，例6.2.24也说明了一个常见的计数错误）。
* 在参考文献中加入了近期的一些书籍和文章。一些参考书籍被更新为最新的版本。
* 例子的数量增加到650（第6版大概有600个例子）。
* 练习的数量增加到4200左右（第6版大概有4000个例子）。


内容和结构
本书内容包括
* 集合和逻辑（包括量词）。实例包括Google搜索引擎的使用（例 1.2.13）等。本书使用程序逻辑来讨论自然语言到符号表达式的翻译。例1.6.15讨论了逻辑游戏，该游戏给出了一种确定量化命题函数的值是否为真的方法。
* 讨论了证明技术（第2章），包括直接证明、反例、反证法、逆否证明法、分情况证明法、（构造和非构造）存在性证明和数学归纳法。使用循环不变式做为数学归纳法的应用例子之一。包括了一节可选的，简短的对归结证明方法（自动证明技术的基础）的讨论。
* 函数、序列、和与积的记法、串和关系（第3章），包括新的13位国际标准书号（ISBN）的构造、Hash函数和伪随机数发生器（3.1节）的介绍、偏序关系在任务调度中的应用（3.3节）和关系数据库（3.6节）等。
* 详细讨论了算法、递归算法和算法分析技术（第4章）。在说明“大O”和相关记法之前列举了若干例子（4.1节和4.2节），对引入该记法的动机进行了简要的介绍。算法的使用将贯穿全书。本书将提到许多现代算法可能没有传统算法的许多特征（如许多现代算法不是通用、确定的、甚至有的不是有限的）。为了说明这点，本章给出了一个随机算法作为例子（例4.2.4）。算法以伪代码的灵活形式书写，其和目前流行的程序设计语言如C、C＋＋和Java相似（本书不要求读者预先具有计算机科学的知识，所使用的伪代码的描述在附录C中给出）。本身介绍的算法包括覆盖算法（4.4节）、计算最大公约数的欧几里德算法（5.3节）、RSA公共密钥算法（5.4节）、排列组合生成算法（6.4节）、归并排序算法（7.3节）、Dijkstra最短路径算法（8.4节）、回溯算法（9.3节）、深度优先和广度优先算法（9.3节）、树的遍历算法（9.6节）、博弈树求值算法（9.9节）、网络最大流量算法（10.2节）、寻找最小距点对算法（13.1节）和凸包计算算法（13.2节）等。
* 关于函数增长的“大O”、Ω、Θ记法的讨论（4.3节）。使用这些记法可以准确地描述函数的增长以及算法的时间和空间复杂度问题。
* 数论的介绍（第5章）。包括一些传统的结论（如整除性、素数个数是无限的、基本的算术定理）和数论算法（如寻找最大公约数的欧几里德算法、基于重复平方法计算数的指数的算法，计算满足gcd(a,b)=sa+tb的整数s和t的算法，计算一个整数针对某个模的逆的算法等。本章介绍的方法可应用于RSA公共密钥算法（5.4节）中涉及的计算。
* 排列、组合、离散概率和鸽巢原理（第6章）。可选章节（6.4节和6.5节）介绍了离散概率。
* 递推关系及其在算法分析中的应用（第7章）。
* 图，包括并行计算机体系结构的图型表示和映射、骑士旅行、Hamilton回路、图的同构、平面图（第8章）等。定理8.4.3给出了Dijkstra算法正确性的简短优美的证明。
* 树，包括二叉树、树的遍历、最小生成树、决策树、排序的时间下界、树的同构（第9章）等。
* 网络最大流量算法和匹配问题（第10章）。
* Boole代数，重点是Boole代数与组合电路的关系（第11章）。
* 介绍了基于有限自动机的建模技术和应用（第12章）。例12.1.11讨论了SR触发电路。例12.3.19以von Koch雪花为例，给出了分形的语法描述。
* 第13章介绍了计算几何学。
* 附录给出了矩阵理论、一些基本的代数概念和伪代码的描述。
* 强调了本书各部分内容之间的相互联系。例如，数学归纳法与递归算法的密切关系（4.4节）；Fibonacci数列在欧几里德算法分析中的应用（5.3节）；本书有许多练习需要数学归纳法的应用；本书还介绍了如何通过定义节点集上的等价关系的方法来刻画图的分支（见例8.2.13后的讨论）的方法，给出了计算n个节点的非同构二叉树的个数（定理9.8.12）的技术。
* 强调证明细节的理解和证明的构造。多数定理的证明带有插图注释并（或）有专门的讨论。有独立的小节（问题求解部分）向学生讲解如何进行问题求解以及如何进行定理证明。一些章节后的问题求解要点则对本章节涉及的主要技术和方法进行总结。
* 包括了大量的应用描述，特别是离散数学在计算机科学中的应用。
* 利用图表描述概念、表示算法的工作原理、对定理进行阐释，从而使内容讲解更加生动。有些定理的证明辅以图示，以期对证明进行一步的解释和揭示。
* 每节都包括练习。
* 每章的注解部分给出了学习建议和进一步阅读的文献资料目录。
* 每章都包含有复习。
* 每章都包含自我测验。
* 上机练习。
* 参考文献部分包含了160多条文献。
* 给出了本书所使用的数学记法和算法符号。

每章的结构如下
每章按下面的方式组织：
         概述
         章节
         章节复习
         章节练习
         章节
         章节复习
         章节练习
         ……
         注释
         本章复习
         本章自测题
         上机练习
章节练习帮助学生复习本章节的重要概念、定义、定理和求解技巧等，书后附有部分章节练习的答案。尽管章节练习是为复习章节准备的，但也可作为作业或考试题目。
注释给出了进一步学习的建议。本章复习给出每章的基本概念。本章自测题中每节可对应4道练习，相关的答案在书后给出。
上机练习包括项目、一些算法的实现以及其他与程序设计有关的活动。本书不要求读者具备程序设计的能力，本书也没有有关程序设计内容的介绍，因而这些练习只是为那些具有程序设计基础并愿意利用计算机来分析离散数学的一些概念的同学准备的。
此外，几乎各章都有问题求解部分。
练习
书中包括4200多道练习题，其中145道是上机练习。超过一般难度的练习题用“*”标出。一些练习（约占三分之一）书后有提示或答案。其他练习的答案可以在教学参考书中找到。有少数练习明确标示需要微积分知识，但书中的主要章节不使用微积分概念。因此除了那些有标示的练习外，其他练习是不需要用到微积分知识的。

例题
本书包括650多道例题。这些例题向学生展示如何用离散数学解决问题、介绍理论的应用、阐述证明过程，从而使有关内容的讲解更加生动。

问题求解
问题求解部分旨在帮助学生对一些问题进行研究和探索，展示如何给出一个问题的证明。问题求解部分的内容是使用非形式化的风格书写的，是对一个问题进行讨论之后出现的独立一节，其目的是展示另一种求解问题的方法、讨论如何寻找问题的答案、说明问题求解和证明的技巧，而不是简单地给出一个问题的证明和答案。
问题求解部分由问题陈述开始，接着是讨论解决问题的方法。在得出求解方法以后，进一步说明该如何正确地书写形式化的求解过程。最后，再对使用的求解技巧进行总结。此外，有的问题求解部分还包括注释并讨论其与数学和计算机科学其他内容的联系，有的给出问题的背景和进一步阅读的参考文献目录，有的以练习作为结束。

教学参考书
选用本书作为教材的教师可与当地的Prentice Hall代表联系，并从出版社那里免费得到配套的教学参考书。本书没有给出的练习答案可以在教学参考书中找到。

致谢
许多同仁对本书的出版提供了有益的帮助，他们是Gray Andrus、Kendall Atkinson、Greg Bachelis、Andre Berthiaume、Gregory Brewster、Robert Busby、David G. Cantor、Tim Carroll、Joseph P. Chan、Hon-Wing Cheng、I-Ping Chu、Robert Crawford、Henry D’Angelo、Jerry Delazzer、Br. Michael Driscoll、Carl E. Eckberg、Herbert Enderton、Susanna Epp、Bob Fisher、Brendan Frey、Dennis Garity、Gerald Gordon、Jerrold Grossman、Reino Hakala、Mark Herbster、Craig Jensen、Steve Jost、Martin Kalin、Aaron Keen、Nicholas Krier、Warren Krueger、Glenn Lancaster、Miguel Lerma、Donald E. G. Malm、Nick Meshes、Truc Nguyen、Suely Oliveira、Kevin Phelps、Jenni Piane、Randall Pruim、Mansur Samadzadeh、Sigrid(Anne) Settle、David Stewart、James H. Stoddard、Chaim Goodman Strauss、Bogdan Suceava、Michael Sullivan、Edward J. Williams、Anthony S. Wojcik和 Hanyi Zhang等。感谢所有发来信件和电子邮件的读者。
本版本特别要感谢我在DePaul的同事Greg Brewster，他提供了关于Internet地址分配的咨询意见。
感谢加州州立大学Fullerton分校的Scott Annnin、Westminster学院的Natacha Fontes -Merz、Loyola 大学的Ronald I. Greenberg、Rice大学的John Greiner、哥伦比亚大学的Eitan Grinspun、Fayetteville州立大学的Wu Jing、UNC Charlotte的Harold Reiter、Ashland大学的Christopher N. Swanson，他们浏览了本书初稿。
感谢本书编审Patricia Johnsonbaugh，她仔细阅读了本书草稿、改进了行文，找出了许多不该有的错误并且协助作者完成了索引的编定。
本书的出版得到了Prentice Hall出版社的支持，在此特别感谢副编辑Dee Bernhard、资深管理编辑Scott Disanno、编辑部主任Marcia Horton、编辑助理Jennifer Lonschein、资深编辑Holly Stark和产品编辑Irwin Zucker。
     

                                                        Richard Johnsonbaugh