离散数学及其应用 （原书第7版）（本科教学版）pdf

离散数学及其应用 （原书第7版）（本科教学版） 内容简介

本书是经典的离散数学教材，为全球多所大学广为采用。本书全面而系统地介绍了离散数学的理论和方法，内容涉及逻辑和证明，集合、函数、序列、求和与矩阵，计数，关系，图，树，布尔代数。全书取材广泛，除包括定义、定理的严格陈述外，还配备大量的实例和图表说明、各种练习和题目。第7版在前六版的基础上做了大量的改进，使其成为更有效的教学工具。本书可作为高等院校数学、计算机科学和计算机工程等专业的教材或参考书。

离散数学及其应用 （原书第7版）（本科教学版） 目录

出版者的话

改编者序

译者序

前言

配套网站

致学生

关于作者

符号表

第1章基础：逻辑和证明1

1.1命题逻辑1

1.1.1引言1

1.1.2命题1

1.1.3条件语句4

1.1.4复合命题的真值表7

1.1.5逻辑运算符的优先级7

1.1.6逻辑运算和位运算7

练习8

1.2命题逻辑的应用11

1.2.1引言11

1.2.2语句翻译11

1.2.3系统规范说明12

1.2.4布尔搜索12

1.2.5逻辑谜题13

1.2.6逻辑电路14

练习15

1.3命题等价式16

1.3.1引言16

1.3.2逻辑等价式17

1.3.3德·摩根律的运用19

1.3.4构造新的逻辑等价式19

1.3.5命题的可满足性20

1.3.6可满足性的应用20

1.3.7可满足性问题求解22

练习22

1.4谓词和量词24

1.4.1引言24

1.4.2谓词24

1.4.3量词25

1.4.4约束论域的量词28

1.4.5量词的优先级29

1.4.6变量绑定29

1.4.7涉及量词的逻辑等价式29

1.4.8量化表达式的否定30

1.4.9语句到逻辑表达式的翻译31

1.4.10系统规范说明中量词的使用32

1.4.11选自路易斯·卡罗尔的例子33

1.4.12逻辑程序设计33

练习34

1.5嵌套量词37

1.5.1引言37

1.5.2理解涉及嵌套量词的语句37

1.5.3量词的顺序38

1.5.4数学语句到嵌套量词语句的翻译39

1.5.5嵌套量词到自然语言的翻译40

1.5.6汉语语句到逻辑表达式的翻译40

1.5.7嵌套量词的否定41

练习42

1.6推理规则45

1.6.1引言45

1.6.2命题逻辑的有效论证45

1.6.3命题逻辑的推理规则46

1.6.4使用推理规则建立论证48

1.6.5消解律49

1.6.6谬误49

1.6.7量化命题的推理规则50

1.6.8命题和量化命题推理规则的组合使用51

练习52

1.7证明导论53

1.7.1引言53

1.7.2一些专用术语53

1.7.3理解定理是如何陈述的54

1.7.4证明定理的方法54

1.7.5直接证明法54

1.7.6反证法55

1.7.7归谬证明法57

1.7.8证明中的错误59

1.7.9良好的开端60

练习60

1.8证明的方法和策略61

1.8.1引言61

1.8.2穷举证明法和分情形证明法61

1.8.3存在性证明65

1.8.4唯一性证明66

1.8.5证明策略66

1.8.6寻找反例68

1.8.7证明策略实践68

1.8.8拼接68

1.8.9开放问题的作用71

1.8.10其他证明方法71

练习72

关键术语和结论73

复习题75

补充练习75

计算机课题78

计算和探索78

写作课题78

第2章基本结构：集合、函数、序列、求和与矩阵79

2.1集合79

2.1.1引言79

2.1.2文氏图81

2.1.3子集81

2.1.4集合的大小82

2.1.5幂集83

2.1.6笛卡儿积83

2.1.7使用带量词的集合符号84

2.1.8真值集和量词84

练习85

2.2集合运算86

2.2.1引言86

2.2.2集合恒等式88

2.2.3扩展的并集和交集90

2.2.4集合的计算机表示91

练习92

2.3函数94

2.3.1引言94

2.3.2一对一函数和映上函数96

2.3.3反函数和函数组合98

2.3.4函数的图100

2.3.5一些重要的函数101

2.3.6部分函数103

练习103

2.4序列与求和106

2.4.1引言106

2.4.2序列106

2.4.3递推关系107

2.4.4特殊的整数序列109

2.4.5求和111

练习114

2.5集合的基数116

2.5.1引言116

2.5.2可数集116

2.5.3不可数集合118

练习120

2.6矩阵121

2.6.1引言121

2.6.2矩阵算术122

2.6.3矩阵的转置和幂123

2.6.40—1矩阵124

练习125

关键术语和结论126

复习题128

补充练习129

计算机课题131

计算和探索131

写作课题131

第3章计数132

3.1计数的基础132

3.1.1引言132

3.1.2基本的计数原则132

3.1.3比较复杂的计数问题136

3.1.4减法法则（两个集合的容斥原理）137

3.1.5除法法则138

3.1.6树图138

练习139

3.2鸽巢原理141

3.2.1引言141

3.2.2广义鸽巢原理142

3.2.3鸽巢原理的几个简单应用144

练习145

3.3排列与组合146

3.3.1引言146

3.3.2排列146

3.3.3组合148

练习150

3.4二项式系数和恒等式151

3.4.1二项式定理151

3.4.2帕斯卡恒等式和三角形153

3.4.3其他的二项式系数恒等式154

练习155

3.5排列与组合的推广157

3.5.1引言157

3.5.2有重复的排列157

3.5.3有重复的组合157

3.5.4具有不可区别物体的集合的排列160

3.5.5把物体放入盒子161

练习163

3.6生成排列和组合165

3.6.1引言165

3.6.2生成排列165

3.6.3生成组合166

练习167

关键术语和结论168

复习题169

补充练习170

计算机课题173

计算和探索173

写作课题174

第4章高级计数技术175

4.1递推关系的应用175

4.1.1引言175

4.1.2用递推关系构造模型176

4.1.3算法与递推关系180

练习181

4.2求解线性递推关系184

4.2.1引言184

4.2.2求解常系数线性齐次递推关系184

4.2.3常系数线性非齐次的递推关系188

练习190

4.3分治算法和递推关系191

4.3.1引言191

4.3.2分治递推关系192

练习197

4.4生成函数198

4.4.1引言198

4.4.2关于幂级数的有用事实198

4.4.3计数问题与生成函数201

4.4.4使用生成函数求解递推关系204

4.4.5使用生成函数证明恒等式205

练习206

4.5容斥208

4.5.1引言208

4.5.2容斥原理208

练习211

4.6容斥原理的应用212

4.6.1引言212

4.6.2容斥原理的另一种形式212

4.6.3埃拉托色尼筛213

4.6.4映上函数的个数213

4.6.5错位排列214

练习216

关键术语和结论216

复习题217

补充练习218

计算机课题221

计算和探索221

写作课题221

第5章关系223

5.1关系及其性质223

5.1.1引言223

5.1.2函数作为关系224

5.1.3集合的关系224

5.1.4关系的性质225

5.1.5关系的组合227

练习228

5.2n元关系及其应用230

5.2.1引言230

5.2.2n元关系231

5.2.3数据库和关系231

5.2.4n元关系的运算232

5.2.5SQL234

练习235

5.3关系的表示236

5.3.1引言236

5.3.2用矩阵表示关系236

5.3.3用图表示关系238

练习239

5.4关系的闭包240

5.4.1引言240

5.4.2闭包241

5.4.3有向图中的路径241

5.4.4传递闭包242

5.4.5沃舍尔算法245

练习247

5.5等价关系247

5.5.1引言247

5.5.2等价关系248

5.5.3等价类249

5.5.4等价类与划分250

练习253

5.6偏序255

5.6.1引言255

5.6.2字典顺序256

5.6.3哈塞图257

5.6.4极大元与极小元259

5.6.5格260

5.6.6拓扑排序261

练习263

关键术语和结论265

复习题267

补充练习268

计算机课题271

计算和探索272

写作课题272

第6章图273

6.1图和图模型273

6.1.1图模型276

练习279

6.2图的术语和几种特殊的图281

6.2.1引言281

6.2.2基本术语281

6.2.3一些特殊的简单图283

6.2.4二分图284

6.2.5二分图和匹配286

6.2.6特殊类型图的一些应用288

6.2.7从旧图构造新图289

练习291

6.3图的表示和图的同构293

6.3.1引言293

6.3.2图的表示293

6.3.3邻接矩阵293

6.3.4关联矩阵295

6.3.5图的同构296

6.3.6判定两个简单图是否同构296

练习298

6.4连通性301

6.4.1引言301

6.4.2通路301

6.4.3无向图的连通性303

6.4.4图是如何连通的304

6.4.5有向图的连通性306

6.4.6通路与同构307

6.4.7计算顶点之间的通路数308

练习308

6.5欧拉通路与哈密顿通路311

6.5.1引言311

6.5.2欧拉通路与欧拉回路311

6.5.3哈密顿通路与哈密顿回路315

6.5.4哈密顿回路的应用316

练习318

6.6最短通路问题320

6.6.1引言320

6.6.2最短通路算法322

6.6.3旅行商问题325

练习326

6.7平面图328

6.7.1引言328

6.7.2欧拉公式329

6.7.3库拉图斯基定理332

练习333

6.8图着色334

6.8.1引言334

6.8.2图着色的应用337

练习338

关键术语和结论340

复习题343

补充练习344

计算机课题348

计算和探索349

写作课题349

第7章树351

7.1树的概述351

7.1.1有根树352

7.1.2树作为模型355

7.1.3树的性质356

练习358

7.2树的应用360

7.2.1引言360

7.2.2二叉搜索树360

7.2.3决策树362

7.2.4前缀码364

7.2.5博弈树365

练习369

7.3树的遍历371

7.3.1引言371

7.3.2通用地址系统371

7.3.3遍历算法372

7.3.4中缀、前缀和后缀记法377

练习379

7.4生成树380

7.4.1引言380

7.4.2深度优先搜索382

7.4.3宽度优先搜索384

7.4.4回溯的应用385

7.4.5有向图中的深度优先搜索387

练习388

7.5最小生成树390

7.5.1引言390

练习

关键术语和结论

复习题

补充练习

计算机课题

计算和探索

写作课题

第8章布尔代数

8.1布尔函数

8.1.1引言

8.1.2布尔表达式和布尔函数

8.1.3布尔代数恒等式

8.1.4对偶性

8.1.5布尔代数的抽象定义

练习

8.2布尔函数的表示

8.2.1积之和展开式

8.2.2函数完备性

练习

8.3逻辑门电路

8.3.1引言

8.3.2门的组合

8.3.3电路的例子

8.3.4加法器

练习

8.4电路的极小化

8.4.1引言

8.4.2卡诺图

8.4.3无须在意的条件

8.4.4奎因—莫可拉斯基方法

练习

关键术语和结论

复习题

补充练习

计算机课题

计算和探索

写作课题

推荐读物

参考文献

练习答案

离散数学及其应用 （原书第7版）（本科教学版） 精彩文摘

为了理解数学，我们必须理解正确的数学论证(即证明)是由什么组成的。只要证明一个数学语句是真的，我们就称之为一个定理。关于一个主题的定理的集合就组成我们对这个主题的认知。为了学习一个数学主题，我们需要积极地构造关于此主题的数学论证，而不仅仅是阅读论述。此外，了解一个定理的证明通常就有可能通过细小的改动来获得适应新情境的结论。

每个人都知道证明在数学中的重要性，但许多人对于证明在计算机科学中的重要程度感到惊讶。事实上，证明常常用于验证计算机程序对所有可能的输入值产生正确输出值，用于揭示算法总是产生正确结果，用于建立一个系统的安全性，以及用于创造人工智能系统。并且，自动推理系统已经被创造出来，让计算机自己来构造证明。

本章将解释一个正确的数学论证是如何组成的，并介绍构造论证的工具。我们将开发一系列不同的证明方法以证明许多不同类型的结论。在介绍了多种不同证明方法后，我们将介绍一些构造证明的策略。我们还将介绍猜想的概念，并通过研究猜想来解释数学发展的过程。