出版者的话
译者序
前言
在线资源
致学生
作者简介
符号表
第1章　基础：逻辑和证明1
　1.1　命题逻辑1
　　1.1.1　引言1
　　1.1.2　命题1
　　1.1.3　条件语句4
　　1.1.4　复合命题的真值表7
　　1.1.5　逻辑运算符的优先级8
　　1.1.6　逻辑运算和比特运算8
　　练习9
　1.2　命题逻辑的应用15
　　1.2.1　引言15
　　1.2.2　语句翻译15
　　1.2.3　系统规范说明16
　　1.2.4　布尔搜索16
　　1.2.5　逻辑谜题17
　　1.2.6　逻辑电路18
　　练习20
　1.3　命题等价式23
　　1.3.1　引言23
　　1.3.2　逻辑等价式23
　　1.3.3　德·摩根律的运用25
　　1.3.4　构造新的逻辑等价式26
　　1.3.5　可满足性28
　　1.3.6　可满足性的应用28
　　1.3.7　可满足性问题求解30
　　练习31
　1.4　谓词和量词34
　　1.4.1　引言34
　　1.4.2　谓词34
　　1.4.3　量词37
　　1.4.4　有限域上的量词39
　　1.4.5　受限域的量词39
　　1.4.6　量词的优先级40
　　1.4.7　变量绑定40
　　1.4.8　涉及量词的逻辑等价式40
　　1.4.9　量化表达式的否定41
　　1.4.10　语句到逻辑表达式的翻译42
　　1.4.11　系统规范说明中量词的使用43
　　1.4.12　选自路易斯·卡罗尔的例子44
　　1.4.13　逻辑程序设计45
　　练习46
　1.5　嵌套量词51
　　1.5.1　引言51
　　1.5.2　理解涉及嵌套量词的语句51
　　1.5.3　量词的顺序52
　　1.5.4　数学语句到嵌套量词语句的翻译53
　　1.5.5　嵌套量词到自然语言的翻译54
　　1.5.6　汉语语句到逻辑表达式的翻译54
　　1.5.7　嵌套量词的否定55
　　练习56
　1.6　推理规则62
　　1.6.1　引言62
　　1.6.2　命题逻辑的有效论证62
　　1.6.3　命题逻辑的推理规则63
　　1.6.4　使用推理规则建立论证65
　　1.6.5　消解律66
　　1.6.6　谬误66
　　1.6.7　量化命题的推理规则67
　　1.6.8　命题和量化命题推理规则的组合使用68
　　练习69
　1.7　证明导论72
　　1.7.1　引言72
　　1.7.2　一些专用术语72
　　1.7.3　理解定理是如何陈述的73
　　1.7.4　证明定理的方法73
　　1.7.5　直接证明法73
　　1.7.6　反证法74
　　1.7.7　归谬证明法76
　　1.7.8　证明中的错误78
　　1.7.9　良好的开端79
　　练习80
　1.8　证明的方法和策略81
　　1.8.1　引言81
　　1.8.2　穷举证明法和分情形证明法81
　　1.8.3　存在性证明84
　　1.8.4　**性证明86
　　1.8.5　证明策略87
　　1.8.6　寻找反例89
　　1.8.7　证明策略实践90
　　1.8.8　拼接90
　　1.8.9　开放问题的作用92
　　1.8.10　其他证明方法93
　　练习94
　关键术语和结论96
　复习题97
　补充练习98
　计算机课题100
　计算和探索101
　写作课题101
第2章　基本结构：集合、函数、序列、求和与矩阵102
　2.1　集合102
　　2.1.1　引言102
　　2.1.2　文氏图104
　　2.1.3　子集105
　　2.1.4　集合的大小106
　　2.1.5　幂集107
　　2.1.6　笛卡儿积107
　　2.1.7　使用带量词的集合符号109
　　2.1.8　真值集和量词109
　　练习109
　2.2　集合运算112
　　2.2.1　引言112
　　2.2.2　集合恒等式114
　　2.2.3　扩展的并集和交集116
　　2.2.4　集合的计算机表示117
　　2.2.5　多重集118
　　练习119
　2.3　函数123
　　2.3.1　引言123
　　2.3.2　一对一函数和映上函数125
　　2.3.3　反函数和函数合成128
　　2.3.4　函数的图130
　　2.3.5　一些重要的函数130
　　2.3.6　部分函数133
　　练习133
　2.4　序列与求和138
　　2.4.1　引言138
　　2.4.2　序列138
　　2.4.3　递推关系139
　　2.4.4　特殊的整数序列141
　　2.4.5　求和144
　　练习147
　2.5　集合的基数150
　　2.5.1　引言150
　　2.5.2　可数集合151
　　2.5.3　不可数集合153
　　练习155
　2.6　矩阵157
　　2.6.1　引言157
　　2.6.2　矩阵算术158
　　2.6.3　矩阵的转置和幂159
　　2.6.4　0-1矩阵160
　　练习161
　关键术语和结论164
　复习题166
　补充练习166
　计算机课题168
　计算和探索169
　写作课题169
第3章　算法170
　3.1　算法170
　　3.1.1　引言170
　　3.1.2　搜索算法172
　　3.1.3　排序174
　　3.1.4　字符串匹配176
　　3.1.5　贪婪算法177
　　3.1.6　停机问题179
　　练习180
　3.2　函数的增长183
　　3.2.1　引言183
　　3.2.2　大O记号184
　　3.2.3　一些重要函数的大O估算187
　　3.2.4　函数组合的增长190
　　3.2.5　大Ω与大Θ记号191
　　练习192
　3.3　算法的复杂度196
　　3.3.1　引言196
　　3.3.2　时间复杂度196
　　3.3.3　矩阵乘法的复杂度198
　　3.3.4　算法范型199
　　3.3.5　理解算法的复杂度201
　　练习203
　关键术语和结论207
　复习题208
　补充练习209
　计算机课题211
　计算和探索211
　写作课题212
第4章　数论和密码学213
　4.1　整除性和模算术213
　　4.1.1　引言213
　　4.1.2　除法213

本书是根据我多年来讲授离散数学的经验和兴趣写成的。对学生而言，我的目的是为他们提供内容准确且可读性强的教材，清晰地介绍并展示离散数学中的概念和技术。对于那些爱怀疑的学生，我的目标是展示离散数学的相关性和实用性。对于计算机科学专业的学生，我希望为他们将来的学习提供一切必需的数学基础。而对于数学专业的学生，我希望帮助他们理解重要的数学概念，并且意识到为什么这些概念对应用来说很重要。最重要的是，希望本书既能达到这些目标，又不含太多的水分。
对教师而言，我的目的是利用数学中行之有效的教学技术来设计一个灵活而全面的教学工具：只要有本书在手，教师就能迅速地从中筛选内容，以最适合特定学生的方式有效地开展离散数学的教学工作。希望我已经实现了这些目标。
在过去的30年中，本书取得了极大的成功，被世界各地超过100万名学生使用，并被翻译成多种语言，对此我感到非常欣慰。此次第8版所做的许多改进，正是得益于大量读者的反馈和建议。在这些读者中，既有来自北美600多所学校的师生，又有来自全球各地众多高校的读者，他们都曾将本书成功用作教材。由于所收到的这些反馈，以及在不断更新中所投入的大量精力，我才能够在每次升级时显著提高本书的吸引力和有效性。
本教材是为一学期或两学期的离散数学入门课程而设计的，适用于数学、计算机科学、工程等各类专业的学生。大学代数是**要求的先修课程，不过，要想真正学好离散数学，还是需要有一定的数学素养。本书的设计目标是满足各种类型离散数学入门课程的需求，内容高度灵活且非常全面。我希望本书不仅是一本成功的教科书，而且成为学生在日后的学习和职业生涯中可以参考的有价值的资源。
离散数学课程的目标
离散数学课程有多个目标。学生应该学会一系列特定的数学知识并知道怎样应用它们，更重要的是，这门课应教会学生怎样运用数学逻辑思维。为了达到这些目标，本教材特别强调数学推理以及问题求解的不同方法。本书中，五个重要主题将交织在一起：数学推理，组合分析，离散结构，算法思维，以及应用与建模。一门成功的离散数学课程应该小心谨慎地融合并平衡所有五个主题。
●数学推理。学生必须理解数学推理以便阅读、领会并构造数学论证。本书开篇即讨论数理逻辑，这为后续讨论证明方法打下了基础。本书描述了构造证明的方法与技巧两个方面。本书特别强调数学归纳法，不仅给出了这种证明技术的许多不同类型的实例，还详细地解释了数学归纳法为什么是一种有效的证明技术。
●组合分析。一个重要的解题技巧就是计数或枚举对象。本书中关于枚举的讨论从计数的基本技术着手。重点是运用组合分析方法来解决计数问题并分析算法，而不是简单地应用公式。
●离散结构。离散数学课程应该教会学生如何处理离散结构，即表示离散对象以及对象之间关系的抽象数学结构。这些离散结构包括集合、置换、关系、图、树和有限状态机等。
●算法思维。有些类型的问题可以通过算法的规范说明来求解。当一个算法被清楚地描述后，就可以编写计算机程序来实现之。该活动涉及的数学部分包括该算法的规范说明、正确性的验证，以及执行算法所需要的计算机内存和时间分析等，这些在本书中均有阐述。算法将采用自然语言　原书采用英语，而中译版则采用汉语。——译者注和一种易于理解的伪代码形式来描述。
●应用与建模。离散数学在几乎每个可以想到的研究领域中都有应用。许多应用涉及本书提到的计算机科学和数据网络，还有一些应用涉及更为广泛的领域，如化学、生物学、语言学、地理学、商业和互联网等。这些是离散数学的自然而又重要的应用，而非人为编造的。用离散数学来建模是一项十分重要的问题求解技巧，学生可通过一些练习来自己构造模型，从而掌握这一技巧。
第8版中的变化
虽然第7版已经是一本**影响力的教材，但许多教师还是提出了一些修改请求，以使本书更适于教学。我花了大量的时间和精力来满足这些请求，努力以自己的方式改进本书并使之紧跟最新发展。
第8版的修改基于20多位正式审稿人的意见、学生和教师的反馈以及我自己的见解，希望新版本能成为一个更加有效的教学工具。第8版中所做的大量更新是为了帮助学生更好地学习这些内容。我增加了额外的解释和例子以便阐述那些学生经常感到困难的内容，增加了知识性的和富有挑战性的新练习，还增加了一些与Internet、计算机科学以及数学生物学等密切相关的应用。在开发人员的努力下，本书配套网站现在提供了很多工具，可以帮助学生掌握关键概念并探索离散数学世界。此外，还提供了有效和全面的学习和评估工具，以作为教科书的补充。
我希望教师能仔细阅读新版，以了解如何满足自己的教学需求。要列出所有更新是不切实际的，不过，我将给出概要性的描述，包括一些关键更新及其所带来的好处，这对读者来说或许是有益的。
本书新版对许多内容进行了完善、更新、补充和润色，所有这一切都是为了使本书成为现代离散数学课程的更加有效的教学工具。之前使用过本教材的教师会发现这次更新遍及全书，其中最值得注意的修订如下。
全书范围的更新
●对内容编排的完善贯