本书是介绍离散数学理论和方法的经典教材，已经成为全球500多所大学的指定教材，获得了极大的成功。中文版也已被国内大学广泛采用为教材。第5版在前四版的基础上做了大量的改进，使其成为更有效的教学工具。
　　本书可作为1至2个学期的离散数学课入门教材，适用于数学、计算机科学、计算机工程等专业的学生。

第5版的特点
　　● 易入门：实践证明本书对初学者来说易读易懂
　　● 灵活：本教材为灵活使用做了精心设计，各章对其前面内容的依赖降到最小
　　● 广泛的课堂实践：本书已在500多所大学得到了多年实践检验
　　● 实例：书中有700多个实例，用于阐明概念，联系不同内容，并引入各种应用
　　● 应用：本书涉及的应用领域很广，包括计算机科学、数据网络、心理学、化学、工程、语言学、生物学、商业和互联网
　　● 历史资料：本书以脚注的形式给出了60多位数学家和计算机科学家的传记
　　● 关键术语和结论：每一章后面都列出了本章的关键术语和结论
　　● 练习、复习题、补充练习：正文中有3 500多道练习，每章最后都有一组复习题和一组丰富多样的补充练习
　　● 计算机课题：每一章后面还有一组计算机课题，把学生已经学到的计算和离散数学的内容结合在一起

无

本书是根据我多年讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供准确而可读的教材，使离散数学的概念和技术得以清晰地介绍。我的目标是向爱怀疑的学生们展示离散数学的实用性，希望为学习计算机科学的学生提供一切必需的数学基础，也希望学数学的学生理解数学概念的重要性，以及这些概念为什么对应用是重要的,还希望本书既能达到这些目标，又不含太多的水分。
　　对教师(指导者)而言，我的目的是使用成熟的数学教学技术设计一个灵活而全面的教学工具,希望为教师们提供能够高效地、以最适合特定学生特点的方式讲授离散数学的教材。希望本书能够达到这些目标。
　　我为本教材在过去已经取得的巨大成功而分外高兴。根据成功使用本书的500多所学校的大批师生的反馈和建议，此次第5版进行了许多改进。很多内容有所提高,辅助材料更加丰富，配套网站提供的材料更有帮助性，使师生更容易达到他们的目标。
　　本教材是为1至2个学期的离散数学入门课程而设计的，适用于数学、计算机科学、工程等许多专业的学生。唯一的先修课要求是大学代数。
　　离散数学课的目标
　　离散数学课有多个目标。学生不仅要学会一些特定的数学知识并知道怎样应用，更重要的是，这样一门课应教会学生怎样进行数学思维。为此,本教材特别强调数学推理及用不同的方法解题。本教材有5个重要的主题交织在一起：数学推理、组合分析、离散结构、算法思维、应用与建模。成功的离散数学课程应该努力使这五部分内容相互融合、平衡。
　　1数学推理: 学生必须理解数学推理，以便阅读、理解和构造数学证明。本教材以数理逻辑开篇，在后面证明方法的讨论中，数理逻辑是基础。本书还十分强调数学归纳法,不仅用许多证明的实例进行介绍,还详细地解释了数学归纳法为什么是有效的证明方法。
　　2组合分析：解题的一项重要技巧是计数或枚举对象。本书中，对枚举的讨论从基本的计数方法着手，重点是用组合分析方法来解决计数问题，而不直接使用公式。
　　3离散结构：离散数学课应该教会学生如何使用离散结构，即学会如何使用表示离散对象及其之间的关系的抽象数学结构。离散结构包括：集合、置换、关系、图、树和有限状态机等。
　　4算法思维：有些问题是通过详细说明其算法来求解的。算法在描述后就可构造计算机程序来实现。这一过程中用到的数学部分包括：算法描述、正确性证明以及执行算法所需要的计算机内存和时间的分析。这些内容在本书中均有介绍。算法是用英语和一种易于理解的伪码描述的。
　　译著中采用汉语。——译者注5应用与建模：离散数学几乎应用在所有研究领域中。本书既介绍了其在计算机科学和数据网络中的许多应用，也介绍了在其他各种领域中的应用，如化学、植物学、动物学、语言学、地理、商业以及互联网等。这些均是离散数学的实际而重要的应用，而不是编造的。用离散数学来建模是十分重要的问题求解技巧。本书中的一些练习让学生有机会通过自己构造模型来掌握这一技巧。
　　第5版的修改
　　本书的第4版已在美国的500多所学校使用并获得了成功。加拿大的几十所大学以及欧洲、亚洲和大洋洲的一些大学使用第4版也获得了成功。虽然第4版已经是一本非常有效的教材，但许多教师（包括长期使用者）还是提出了使本书更有效的修改要求。我花了大量的时间和精力来满足这些要求。
　　修改的结果就是现在的第5版，它为教师和学生提供了比第4版更多的内容。最重要的是，第5版的内容结构已大为改进，从而使本书成为一本更有效的教学工具。有关逻辑、证明方法和证明策略的材料有了实质性的改进，更能帮助学生掌握数学推理。对于学生经常感到困难的内容，增加了解释和例子加以阐述。在习题中还插入了一些新的练习，有通常的练习，也有富于挑战性的练习。还增加了一些与内容密切相关的应用，如在网络及计算机科学中的应用。配套网站在大量开发活动支持下初具规模，现在已经能提供一些工具，学生可用来掌握一些关键的概念和探索离散数学的奇妙世界。
　　前言
　　前言结构的改进
 第1章集中介绍了数学推理，先介绍命题和谓词逻辑，然后是推理规则，最后是基本的证明技术。
 大O及相关记号的讨论直接放在算法复杂性的前面。
 数列与求和的讨论直接放在数学归纳法的前一节。
 用单独一节专门介绍二项式系数。
 用单独一章专门介绍概率论。
 排序安排在第2章，强调更多的排序算法。
逻辑
 蕴含式的介绍更深入，还介绍了蕴含式的否命题、逆命题和逆否命题。
 增加一小节介绍逻辑难题。
 量词分在两节中介绍。
 将英语或数学命题翻译为逻辑表达式的解释更加详细，反过来的解释亦然。
 量词否定的介绍更加深入。
 介绍了求解及Prolog中谓词逻辑的使用。
 描述了逻辑在系统规范中的应用，这是系统工程师、软件工程师和硬件工程师都感兴趣的内容。
书写和理解证明
 证明方法安排在第1章，这样，书中前面的一些章节就可以直接使用这些材料了。
 明确讨论了唯一性证明。
 31节进一步探讨了证明策略，扩充了第1章中的初步证明策略。
 用更多的解释和新例子加强了数学归纳法和强数学归纳法的介绍。
 介绍了结构归纳法。
 讨论了递归算法的正确性证明。
算法
 第2章介绍了贪心算法。
 扩充了递归算法的介绍。
 加强了深度优先和宽度优先算法的介绍。
 分析或讨论了更多算法的复杂性。
 也扩充了分治算法及用来分析其复杂性的递推关系式的介绍。
 增加了快速模指数算法、求最近点对问题算法、赫夫曼（Huffman）编码算法以及找零钱问题的贪心算法。
　　应用
 图模型中增加了网页图、电话呼叫图、好莱坞图、熟人关系图和合作图。
 讨论了网页蜘蛛所用的搜索方法。
 描述了卡诺图中格雷码的使用。
 加强了巴克斯范式的讨论。
 扩展了n元关系和关系数据库的讨论。
　　数论、组合学和概率论
 更深入讨论了数论中与公钥密码学相关的内容，如伪素数、卡米切尔数及概率素数测试。
 扩充了有关不同基扩张之间变换的材料。
 单用一节专门介绍二项式系数和二项式定理。
 扩充了概率论的内容。许多关键内容都得到了扩充，并都放在同一章介绍。
　　图和树
 增加了用归纳法构造n方体的解释。
 哈密顿回路存在性的充分条件的介绍更加详细。
 讨论了博弈树和最小最大策略。
 介绍了赫夫曼编码。
 扩充了深度优先和宽度优先搜索。
　　练习
 增加了600多道练习，有普通的，也有富有挑战性的。特别强调有关逻辑和证明以及数学归纳法的新练习。
 增加了一些练习来平衡偶数编号的练习和带答案的奇数编号的练习。
新的人物传记和历史资料
 增加了下列人物的传记：亚里士多德（Aristotle）、谢佛（Sheffer）、Smullyan、Rivest、Shamir、Adleman、卡米切尔（Carmichael）、麦卡锡（McCarthy）和赫夫曼（Huffman）。
　　网站
 增加了数百个网络资源的链接。
 在某些关键领域中增加了新的例子。
 可以访问一些例子和证明的更详细解释。
 对某些主题，用于自评的工具已经可以使用，主题包括蕴含、量词、证明方法、函数、大O记号、数学归纳法和计数问题。
 在课本中设置图标，指示网站中相应内容的类型。
 开发了关键算法的交互式演示，便于与课本一起使用。
　　特点
　　易入门实践证明：此课本对初学者来说易读易懂。它的大部分内容只要求学生学过大学代数，不需要其他的预备知识，少数几个涉及微积分的地方也有明确说明。大部分学生应该很容易理解课本中用于表示算法的伪码，不管他们是否学过程序设计语言。本书不要求正规计算机科学方面的预备知识。
　　每章都是从易理解的基础开始。基础的数学概念精确地研究之后，其他领域中更难的部分和应用就提出来了。
　　灵活课本为灵活使用作了精心设计。各章对其前面内容的依赖都降到最低程度。每一章分成长度大致相等的若干节。每一节又根据内容划分成小节以便教学。教师可以根据这些分块很容易地安排进度。
　　写作风格本书的写作风格是直接和实用。使用准确的数学语言，但没有过分的形式化与过分的抽象。在记号和数学命题的词汇间作了精心的平衡。
　　广泛的课堂实践本书已在500多所学校使用过，其中400多所使用了不止一次。这些学校师生的反馈意见使第5版比前几版更成功。
　　数学严密性和准确性本书中所有定义和定理的陈述都十分详细，所以学生可以欣赏其语言的准确以及数学所需的严密。但证明则是缓慢引入并展开的，每一步都经过了详细论证。本书解释并大量使用了递归定义。
　　实例本书使用了700多个例子来阐述概念、建立不同内容之间的关系或导入应用。在大部分例子中，先提出问题，再适当给出它的解。
　　应用书中叙述的应用展示了离散数学在解决现实问题中的使用价值，所涉及的范围很广，包括计算机科学、数据网络、心理学、化学、工程、语言学、生物学、商业和互联网。
　　算法离散数学的结论常常要用算法来表示，因此，本书每一章都介绍了一些关键算法。这些算法既可以用文字叙述，也可以用更易于理解的结构化伪码来叙述。附录B对伪码作了描述和规范。书中所有算法的计算复杂性也都给出了初步的分析。
历史资料本书对许多内容的背景作了简要介绍。以脚注的形式给出了60多位数学家和计算机科学家的简短传记。这些传记介绍了对离散数学做出过重要贡献的科学家们的生活、事业及成就。此外，脚注中还包含了大量历史资料，作为正文中历史资料的补充。
　　关键术语和结果每一章后面都列出了本章的关键术语和结果，但只列出了学生必须学会的那些最重要的关键术语，而不是在该章中定义的所有术语。
　　练习书中包含3500多道练习，提出了大量不同类型的问题。本书不仅提供了足够多简单问题用于练习基本技巧，还提供了大量的中等难度的练习和许多有挑战性的练习。练习的叙述清晰而无歧义，并按难易程度进行了分级。有些特殊的论题还设计成系列练习。这些练习不仅给出了正文中没有介绍的新概念，还使学生可以通过自己的努力发现新思想。
　　比平均水平稍难的练习用单个星号作标记，相当有挑战性的问题则用两个星来标记。必须用微积分来解的练习也作了明确说明。导出正文要用到的结果的练习则用符号识别。课本最后给出了所有奇数号的练习的答案或解题大纲。解题大纲清楚地给出了大多数证明步骤。
　　复习题每章最后都有一组复习题。设计这些问题的目的是帮助学生重点学习该章最重要的概念和技术。要回答这些复习题，学生必须写出较长的答案，而只做点计算或简答是不够的。
　　补充练习集每章后面都有一组丰富而多变的补充练习。这些练习一般比每节的练习难度大。补充练习强化该章中的概念，并把不同内容更有效地综合起来。
　　计算机题目每一章后面还有一组计算机题目。大约有150个这样的题目，把学生可能已经学到的有关计算和离散数学的内容联系起来。如果从数学角度或程序设计角度来看，其难度超过平均水平的计算机题目用一个星标记，特别有挑战性的则用两颗星标记。
　　计算和研究每一章的结论部分都有一组计算和研究性问题。要完成这些练习(大约有100道)需要软件工具的帮助，例如学生或教师自己编写的程序，或数学计算软件包如MAPLE或Mathematica。大部分这样的练习为学生提供了通过计算发现新事实或新思想的机会。(在《用MAPLE研究离散数学及其应用》一书中也讨论了一些这类练习。)
　　写作题目每一章后面都有一组应该书面完成的题目。要完成这类题目，学生需要查阅参考数学文献。有些题目在过去的历史上是很重要的，学生需要查找原始资料，其他的题目则是通往新内容和新思想的途径。所有此类练习均向学生展示正文中没有深入探讨的思想。这些题目把数学概念和书面写作的过程结合在一起，以帮助学生探索未来的研究领域。(在《学生解题指南》中可以找到为这些题目准备的参考文献。)
　　附录正文有两个附录，附录A介绍指数函数和对数函数，目的是复习在课程中要反复使用的某些基本内容；附录B则介绍正文中用来描述算法的伪码。
　　推荐读物在正文的最后，专门有一节用来为各章推荐参考读物，其中有不超过本书水平的书籍，也有较难的书籍；有综述性文章，也有发表离散数学新发现的原始文章。
　　怎样使用本书
　　本书经过了精心写作和编排，适用于不同水平有不同重点的离散数学课。下表列出了核心章节和可选章节。为大学二年级学生开设的一学期的入门课程可以以核心章节为基础，其他章节由教师取舍。两学期的入门课可以在核心章节外加上所有可选的数学章节。强调计算机科学的课程可以使用计算机科学的部分或全部可选章节。
　　章核心节
　　可选的计算机科学章节
　　可选的数学章节1
　　11~18(根据需要)2
　　21~24,27(根据需要)
　　25
　　263
　　31~34
　　35,364
　　41~43
　　46
　　44,455
　　51
　　53
　　526
　　61,65
　　63
　　62,64,667
　　71,73,75
　　72
　　74,768
　　81~85
　　86~889
　　91
　　92,93
　　94，9510
　　101~10411
　　111~115
　　使用本书的教师可以选用或略去每节最后有挑战性的例题及练习，以调整课程的难度。每章对以前各章的依赖关系如下图所示。
　　辅助资料
　　《学生解题指南》(Student Solutions Guide)这本可以单独购买的学生手册包含了各组练习中所有奇数编号问题的完整解答。这些解答解释了为什么要用某种特定的方法以及为什么这个方法管用。有些问题还给出了一两种其他可能的解法，以说明一个问题可以用不同的方法求解。本指南还包含了为每章后面的写作题目推荐的参考文献，以及对学生书写证明的指导意见，并列出了学生在做离散数学题时常犯的错误。本指南还为每一章提供考试样题及解答，以帮助学生准备考试。学生们感到本指南分外有用。
　　《教师资料手册》(Instructors Resource Guide)本手册包含所有偶数编号练习题的完整解答。它对教材的每一章提出了讲解建议，包括每一节中应强调的重点，以及本节内容在整个体系中的位置。此外，本手册为每章提供了考试题库，还包括一些样卷及解答。最后，本手册还给出了教学大纲的样本。
　　《离散数学应用》（Applications of Discrete Mathematics）这本辅助读物是一本独立的教程，既可结合课本使用，也可独立使用。它包含了使用过课本的教师们撰写的20多章内容(每章均有各自的练习)。因为其编排格式与课本类似，所以该书既可作为一门独立课程的课本，也可作为学生讨论班的教材，还可供学生独立研究使用。
　　试题库本题库内容广泛，包含了1600多道习题，可以在Windows系统或　　Macintosh系统中使用。教师可以使用这一软件选择试题，也可随机产生试题。对同样的试题，教师可以加上自己的标题和要求，也可以打乱其顺序后再打印；既可以编排已有的问题，也可以加上自己的问题。在《教师资料手册》中有此题库的打印版，包括试题和解答。
　　《用MAPLE研究离散数学及其应用》(Exploring Discrete Mathematics and Its Applications with MAPLE)这本补充读物用来帮助学生使用计算机代数系统MAPLE来完成离散数学的各种计算。对本书的每一章，这本补充读物包括下列内容：相关的MAPLE函数及其使用方法的描述，完成相关计算的MAPLE程序，每章结尾处还有阐明怎样使用MAPLE做计算和研究的建议和例子，以及可用MAPLE做的练习题。
　　配套网站
　　为本书开发的一个内容广泛的配套网站。该网站将不断地维护和改进。可以多种方式使用该网站进一步学习离散数学，网站地址是：
　　wwwmhhecom/rosen
　　由此地址进入该网站的主页。该网页有下列链接：
　信息中心
　学生中心
　教师中心
　　信息中心：该中心包含本书及其辅助资料的基本信息。教师在这个网页中可以利用网页抽取系统“Page Out”，建立自己的课程网页，还能学习定制出版信息。从该信息中心出发，沿着适当的链接，可以看到本书网站的一个概观。
　　学生中心：该中心包含了可供学生使用的丰富资源，包括下列与课本紧密相关的资源（在课本中用相应的图标加以标记）：
　网络资源指南：该指南提供了数百个含相关资料的外部网站的链接。可以通过关键词浏览或存取这些链接，它们将把你带到包含下列信息的网站：历史及传记信息、谜题及问题、讨论、Java小程序、程序以及其他类型的资源。
　额外的例子：这个网站包含了大量额外的例子。这些例子主要集中在学生经常需要的课外资料的领域。虽然大部分例子只是扩充了基本概念，但还有一部分十分具有挑战性。
　额外的步骤：对一些困难的知识点，提供了更深入的解释帮助理解，尤其是一些特殊的证明和例子。
　评估：提供对七个关键概念理解程度的评估。每个评估都提供了一个题库，其中的每个试题由两部分构成：先是一段简短的复习，然后是一个多选题。如果你选择的答案不正确，该系统还能提供建议，帮助你理解错在什么地方。这样的评估系统应该能诊断出你学习中的问题，从而把精力集中在寻找纠正办法上。
　交互式演示：已经开发了八个交互式演示系统，你可以用它们考查一些重要算法是怎么工作的。这些演示都与课本中的相应材料相对应。
　　从该学生中心你可以访问网络教学系统“Net Tutor”。它提供了在线教学帮助。当你提问与课本内容相关的问题时，如果是在规定教学时间内，你会收到实时回答；否则稍后才会收到回答。
　　学生中心还支持能发布消息的公告板系统。使用该系统，你可以提出问题，还可以回答其他学生提出的问题。
　　除此之外，学生中心还包括下列资源：
　证明书写指南
　离散数学的常见错误
　写作题目的建议
　MAPLE软件
　　教师中心：除了包含学生中心和信息中心提供的所有链接外，网站中的教师中心还包含下列链接：
　教学大纲样本
　教学建议
　《Applications of Discrete Mathematics》一书中的某些章节
写给学生
　　什么是离散数学？离散数学是数学中研究离散对象的部分。(这里“离散”的含义是“由不同的或不相连的元素组成”。)离散数学能解决的问题包括：
 在计算机系统中，有多少种方式可以选择一个合法口令？
 赢彩票的概率是多少？
 两台计算机之间在网络上是否有通路？
 在某一交通系统下，两个城市之间的最短路径是什么？
 怎样把整数序列按递增序排列？
 完成上述排序需要多少步骤？
 如何证明一个排序方法能正确地排序？
 怎样设计两个整数相加的电路？
 有多少合法的因特网网址？
　 你们将学习解决诸如以上问题要用到的离散结构和技术。
　 更一般地，在对对象进行计数时要用到离散数学，研究两个有限(或可数)集合之间的关系时要用到离散数学，分析只含有限步的进程时也要用到离散数学。离散数学的重要性还在不断增长，一个关键原因就是计算机以离散的方式存储和处理信息。
　　为什么要学离散数学？有几条重要的理由需要学习离散数学。首先，通过这个课程你们可以发展自己的数学素质，即理解和创造数学证明的能力。没有这些技巧，你们在学习数学时不可能太深入。
　　第二，离散数学是学习所有更高级数学课程的必经之路。离散数学为学习计算机科学课程提供必要的数学基础，这些课程如：数据结构、算法、数据库理论、自动机理论、形式语言、编译理论、计算机安全以及操作系统。学生如果没有适当的离散数学基础，在学习上述课程时会感到很困难。有个学生给我发电子邮件说，在她学习的每一门计算机科学的课中都用到了本书的知识。
　　以离散数学为基础的数学课程包括逻辑、集合论、数论、线性代数、抽象代数、组合论、图论及概率论(其离散部分)。
　　此外，离散数学还包括了用来解运筹学问题(包括许多离散优化技术)、化学问题、工程问题及生物学问题等必要的数学背景。从本书中你将学到在上述某些领域中的应用。
　　许多学生都感到，与他们以前学过的课程相比，离散数学入门课程的挑战性大得多。这是因为，本课程的一个主要目的是教你进行数学推理和问题求解，而不只是一些分散的技巧。从课本中练习的设计可以看出这个目的。课本中虽然有大量与重点例子类似的练习，但还是有相当比例的练习需要创造性思想。这是有意设计的。虽然课本中的材料提供了解这些问题的工具，但你的任务是创造性地使用这些工具并取得成功。本课程的另一个主要目的是学会处理你以前没有见过的问题。然而，只学会解特殊类型的练习还无法保证能学会足够多的解题技巧，也不能保证在后继课程的学习中或在将来的职业生涯中取得成功。虽然课本讨论了许多主题，但离散数学是一个极为广泛且充满变化的研究领域。作为作者，我的任务之一是帮助你开发学习新知识的能力，在将来的奋斗中你十分需要新的知识。
　　练习我愿意就如何学好离散数学（或数学的其他学科和计算机科学）给同学们提点有益的建议。积极地做练习能使你最大地获益。我建议你尽可能地多做练习。在做完老师布置的练习后，我鼓励你做更多的练习，包括本书每节后面的练习和每章后面的补充练习。（注意练习前面的分级标记。）练习标记
　　含义无标记
　　常规练习*
　　较难的练习**
　　富有挑战性的练习
　　正文中要用到该练习的某个结论(需要用到微积分)
　　解题时要用到极限或微积分的概念
　　解题时，最好在查阅书后的答案或《学生解题指南》中的答案以前，自己先进行尝试。书后提供了所有奇数编号练习的答案。注意，只是答案，而不是完整解答。特别地，答案中省略了解的推导过程。《学生解题指南》包括了课本中所有奇数编号练习的完整解答。在解奇数编号练习时，只有当你身陷绝境时，才建议查阅《学生解题指南》寻找解题指导。你尝试得越多，而不只是被动查阅或抄袭解答，你学到的就越多。出版商有意不提供偶数编号的练习的答案和解答。在解这些练习时，若遇到问题就问老师。
　　网络资源我强烈推荐你利用网络提供的新资源，特别是专为本书设计的网站http://wwwmhhecom/rosen中的资源。其中有许多额外的例子，有为学生经常会遇到的问题而补充的额外步骤，有测量你对关键概念理解程度的评估，有考察关键算法的生动演示，还有一个指向外部网站的链接的大杂烩，通过它们可以探索离散数学的奇妙世界。还有一个能和其他学生进行讨论的公告板系统，可以用它请求其他学生帮助你理解概念或指导解题。帮助其他人的学生会发现，回答问题的同时也帮助了自己更好地掌握内容。你甚至还能访问到一个在线教学网站，可以和老师进行实时交流，得到老师的帮助。（关于使用他人帮助结果的问题，请征求老师的意见。）有关这个网站的详细信息，请参阅前面“配套网站”的描述。
　　本书的价格最后，我了解到本书的价格偏高，但我希望你在本书的投资能得到优质的回报。我们花了多年的努力来开发和优化本书及其配套的辅助读物和网站。对大多数人来说，我很自信本书及其配套资料对掌握离散数学大有帮助。即使你现在的课程可能略去了其中某些章节，但当你学习新课程时就会发现，阅读本书中的相关章节对新课程仍然十分有益，许多学生都有这样的感觉。许多人会在将来的研究工作时又找到本书，把它当做一本有用的工具书，特别是那些继续学习计算机科学、数学或工程的人。
　　致谢
　　我要感谢很多学校中使用本书的大批师生们，是他们向我提出了宝贵的反馈和有益的建议。没有他们的反馈和建议，本书不可能有很大的改进。我要特别感谢　　Jerrold Grossman和John Michaels，感谢他们对第5版的技术审阅，他们敏锐的目光确保了本书的准确性。我也要感谢通过网站提交评论的人们提供的帮助。
　　我感谢本书第5版及前面四版的许多评阅人，他们对我提出了许多有益的批评和鼓励，我希望本版将不辜负他们的期望。
　　第5版评阅人名单
　　前4版评阅人名单
　　我还要感谢McGrawHill出版社高等教育组的工作人员对本课题强有力的支持。特别要感谢出版人Bill Barter的支持，感谢执行编辑Robert Ross的提倡和热情，感谢开发编辑Michelle Munn的献身和关注，还要感谢原编辑Wayne Yuhasz，是他的洞察力和技巧保证了本书的成功。同样要感谢本版的策划编辑Maggie Rogers，是他协助策划并启动了本版的工作。我和他已经共事了很多年。
我还要对制作本书第5版做出过贡献的职员表示感谢，他们有：高级项目经理Joyce Berendes、设计师K Wayne Harms、网站开发者Jeff Huettman、补充读物协调人Laura Fuller以及市场经理Mary Kittell。我还很感谢Georgia Kamvosoulis Mederer，他检查了全部初稿以保证准确性，感谢校对员Mary Ellen Oliver，感谢Paul Lorczak，他检查了题解手册部分及习题答案部分的准确性。
　　我一直十分感激我在AT&T实验室的领导对我的支持。他们为我的专业发展提供了必要的环境，并无私地给我提供必需的资源，没有这些支持也就没有本书的成功。

　　Kenneth HRosen

出版者的话
专家指导委员会
作者介绍
前言
第1章基础：逻辑和证明、集合、函数
11逻辑
111引言
112命题
113蕴含
114逻辑运算符的优先级
115翻译语言的句子
116系统规范说明
117布尔检索
118逻辑难题
119逻辑运算和位运算
练习
12命题等价
121引言
122逻辑等价
练习
13谓词和量词
131引言
132量词
133绑定变量
134否定
135翻译语句为逻辑表达式
136选自Lewis Carroll的例子
137逻辑程序设计
练习
14嵌套量词
141引言
142翻译涉及嵌套量词的语句
143将语句翻译成逻辑表达式
144否定嵌套量词
145量词的顺序
练习
15证明方法
151引言
152推理规则
153有效的论证
154消解
155谬误
156带量词命题的推理规则
157证明定理的方法
158定理与量词
159证明中的错误
1510关于证明的一些评注
练习
16集合
161引言
162幂集合
163笛卡儿积
164使用带量词的集合符号
练习
17集合运算
171引言
172集合恒等式
173扩展的并集和交集
174计算机表示集合的方式
练习
18函数
181引言
182一对一函数和映上函数
183反函数和函数组合
184函数的图像
185几个重要的函数
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第2章基础：算法、整数和矩阵
21算法
211引言
212搜索算法
213排序
214贪心算法
练习
22函数的增长
221引言
222大O记号
223一些重要的大O结果
224函数组合的增长
225大Ω与大Θ记号
练习
23算法的复杂度
231引言
232时间复杂度
233理解算法的复杂度
练习
24整数和除法
241引言
242除法
243素数
244整除算法
245最大公约数和最小公倍数
246同余算术
247同余应用
248密码学
练习
25整数和算法
251引言
252整数表示
253整数运算算法
254同余幂
255欧几里得算法
练习
26数论应用
261引言
262若干有用的结果
263线性同余
264中国剩余定理
265大整数计算机算术
266伪素数
267公钥密码学
268RSA加密
269RSA解密
2610用RSA作为公钥系统
练习
27矩阵
271引言
272矩阵算术
273矩阵乘法算法
274矩阵转置和幂
27501矩阵
ⅩⅨ练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第3章数学推理、归纳与递归
31证明策略
311引言
312证明策略
313猜想与证明
314猜想与反例
315停机问题
316其他证明方法
练习
32序列与求和
321引言
322序列
323特殊的整数序列
324求和
325基数
练习
33数学归纳法
331引言
332数学归纳法
333数学归纳法证明的例子
334强归纳法
335良序性
336为什么数学归纳法有效
练习
34递归定义与结构归纳法
341引言
342递归地定义函数
343递归地定义集合与结构
344结构归纳法
345广义归纳法
练习
35递归算法
351引言
352递归与迭代
353归并排序
练习
36程序正确性
361引言
362程序验证
363推理规则
364条件语句
365循环不变量
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第4章计数
41计数的基础
411引言
412基本的计数原则
413比较复杂的计数问题
414容斥原理
415树图
练习
42鸽巢原理
421引言
422广义鸽巢原理
423巧妙使用鸽巢原理
练习
43排列与组合
431引言
432排列
433组合
练习
44二项式系数
441二项式定理
442帕斯卡恒等式和三角形
443其他的二项式系数恒等式
练习
45一般性的排列和组合
451引言
452有重复的排列
453有重复的组合
454具有不可区别物体的集合的
排列
455把物体放入盒子
练习
46生成排列和组合
461引言
462生成排列
463生成组合
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第5章离散概率
51离散概率引论
511引言
512有限概率
513事件组合的概率
514概率的推理
练习
52概率论
521引言
522概率指派
523事件的组合
524条件概率
525独立性
526伯努利试验与二项分布
527随机变量
528生日问题
529蒙特卡罗算法
5210概率方法
练习
53期望值和方差
531引言
532期望值
533期望的线性性质
534平均情形下的计算复杂度
535几何分布
536独立随机变量
537方差
538切比雪夫不等式
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第6章高级计数技术
61递推关系
611引言
612递推关系
613用递推关系构造模型
练习
62求解递推关系
621引言
622求解常系数线性齐次递推
关系
623常系数线性非齐次的递推
关系
练习
63分治算法和递推关系
631引言
632分治递推关系
练习
64生成函数
641引言
642关于幂级数的有用事实
643计数问题与生成函数
644使用生成函数求解递推关系
645使用生成函数证明恒等式
练习
65容斥
651引言
652容斥原理
练习
66容斥原理的应用
661引言
662容斥原理的另一种形式
663埃拉托色尼筛
664映上函数的个数
665错位排列
练习
关键术语和结果
ⅩⅩⅠ复习题
补充练习
计算机题目
计算和研究
写作题目
第7章关系
71关系及其性质
711引言
712函数作为关系
713集合的关系
714关系的性质
715关系的组合
练习
72n元关系及其应用
721引言
722n元关系
723数据库和关系
724n元关系的运算
725SQL
练习
73关系的表示
731引言
732用矩阵表示关系
733用图表示关系
练习
74关系的闭包
741引言
742闭包
743有向图的路径
744传递闭包
745沃舍尔算法
练习
75等价关系
751引言
752等价关系
753等价类
754等价类与划分
练习
76偏序
761引言
762字典顺序
763哈塞图
764极大元素与极小元素
765格
766拓扑排序
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第8章图
81概述
811图的种类
812图模型
练习
82图的术语
821引言
822基本术语
823一些特殊的简单图
824偶图
825特殊类型的图的一些应用
826从旧图到新图
练习
83图的表示和图的同构
831引言
832图的表示
833邻接矩阵
834关联矩阵
835图的同构
练习
84连通性
841引言
842通路
843无向图的连通性
844有向图的连通性
845通路与同构
846计算顶点之间的通路数
练习
85欧拉通路与哈密顿通路
851引言
852欧拉通路与欧拉回路
853哈密顿通路与哈密顿回路
练习
86最短通路问题
861引言
862最短通路算法
863旅行商问题
练习
87可平面图
871引言
872欧拉公式
873库拉图斯基定理
练习
88图着色
881引言
882图着色的应用
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第9章树
91概述
911树作为模型
912树的性质
练习
92树的应用
921引言
922二叉搜索树
923决策树
924前缀码
925博弈树
练习
93树的遍历
931引言
932通用地址系统
933遍历算法
934中缀、前缀和后缀记法
练习
94生成树
941引言
942深度优先搜索
943宽度优先搜索
944回溯
945有向图中的深度优先搜索
练习
95最小生成树
951引言
952最小生成树算法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第10章布尔代数
101布尔函数
1011引言
1012布尔表达式和布尔函数
1013布尔代数恒等式
1014对偶性
1015布尔代数的抽象定义
练习
102布尔函数的表示
1021积之和展开式
1022函数完全性
练习
103逻辑门电路
1031引言
1032门的组合
1033电路的例子
1034加法器
练习
104电路的极小化
1041引言
1042卡诺图
1043无需在意的条件
1044奎因莫可拉斯基方法
练习
关键术语和结果
复习题
补充练习
计算机题目
计算和研究
写作题目
第11章计算模型
111语言和文法
1111引言
1112短语结构文法
1113短语结构文法的类型
1114派生树
1115巴克斯诺尔范式
练习
112带输出的有限状态机
1121引言
1122带输出的有限状态机
练习
113不带输出的有限状态机
1131引言
1132串的集合
1133有限状态自动机
练习
114语言的识别
1141引言
1142正则集合
1143克莱因定理
1144正则集合和正则文法
1145一个不能由有限状态自动机
识别的集合
1146一些更强大的机器
练习
115图灵机
1151引言
1152图灵机的定义
1153用图灵机识别集合
1154用图灵机计算函数
1155不同类型的图灵机
1156丘奇图灵论题
练习
关键术语和结果
复习题
补充练习计算机题目
计算和研究
写作题目
附录A指数函数和对数函数
附录B伪代码
奇数练习题答案
推荐读物
参考文献