离散数学（第3版）

图书标准信息

• 作者 贲可荣；袁景凌；谢茜
• 出版社 清华大学出版社
• 出版时间 2021-02
• 版次 3
• ISBN 9787302571049
• 定价 59.99元
• 装帧 平装

【内容简介】

离散数学是计算机科学与技术专业的一门重要基础课。全书共10章，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。新增应用案例，阐明相应章节的知识可以解决什么样的典型应用问题。本书“历史注记”可以帮助读者理解数学，洞察内在本质。
   本书体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，并给出奇数题的答案，适合教学。本书适合作为计算机类和相关专业本科生“离散数学”的教学用书。

【目录】

第1章命题逻辑1

 

1.1现代逻辑学的基本研究

 

方法1

 

1.2命题及其表示法3

 

1.2.1命题的概念3

 

1.2.2联结词4

 

1.3命题公式与语句形式化8

 

1.3.1命题公式的定义8

 

1.3.2公式的层次8

 

1.3.3语句形式化9

 

1.3.4复合命题真假值9

 

1.3.5真值表11

 

1.4重言式12

 

1.4.1重言式概述12

 

1.4.2逻辑等价式13

 

1.4.3等值演算16

 

1.5对偶与范式16

 

1.5.1对偶16

 

1.5.2简单合取式和简单

 

析取式17

 

1.5.3范式18

 

1.5.4范式的唯一性――

 

主范式20

 

1.6其他联结词24

 

1.6.1n元真值函数24

 

1.6.2真值函数与命题

 

公式的关系25

 

1.6.3联结词完备集25

 

1.6.4单元素联结词构成

 

的联结词完备集26

 

1.7命题演算的推理理论27

 

1.7.1有效推理27

 

1.7.2有效推理的等价

 

定理29

 

1.7.3重言蕴涵式30

 

1.7.4形式推理系统31

 

1.7.5自然推理系统P234

 

1.8命题演算中的归结推理38

 

1.8.1归结推理规则38

 

1.8.2归结反演40

 

1.8.3命题逻辑归结反演的

 

合理性和完备性41

 

1.9应用案例41

 

1.9.1克雷格探长案卷录41

 

1.9.2忘却林中的艾丽丝

 

（狮子与独角兽）43

 

习题44

 

计算机编程题52

 

第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谓词逻辑前束

 

范式67

 

2.4谓词演算的推理理论68

 

2.4.1推理定律69

 

2.4.2量词消去与引入

 

规则69

 

2.4.3一阶谓词演算公理

 

系统F170

 

2.4.4自然推理系统F271

 

2.5谓词演算中的归结推理73

 

2.5.1子句型73

 

2.5.2置换和合一75

 

2.5.3合一算法77

 

2.5.4归结式77

 

2.5.5归结反演及其完

 

备性78

 

2.6应用案例79

 

2.6.1电路领域的知识

 

工程79

 

2.6.2基于逻辑的财务

 

顾问80

 

2.7逻辑在计算机科学中的

 

作用80

 

2.7.1逻辑与计算80

 

2.7.2逻辑与计算机的

 

起源81

 

2.7.3逻辑与程序设计81

 

习题81

 

计算机编程题86

 

离散数学（第3版）目录第3章集合与关系88

 

3.1集合的概念和表示法88

 

3.1.1集合的表示88

 

3.1.2基本概念89

 

3.2集合的运算91

 

3.2.1集合的基本运算91

 

3.2.2有穷计数集92

 

3.2.3包含排斥原理93

 

3.2.4广义交和广义并94

 

3.3有序对与笛卡儿积96

 

3.4关系及其表示98

 

3.4.1基本概念98

 

3.4.2关系表示法99

 

3.5关系的运算101

 

3.5.1基本概念101

 

3.5.2复合关系102

 

3.5.3逆关系103

 

3.5.4关系幂105

 

3.5.5幂运算的性质106

 

3.6关系的性质108

 

3.6.1关系的5种基本

 

性质108

 

3.6.2关系性质的等价

 

描述109

 

3.7关系的闭包112

 

3.7.1基本概念112

 

3.7.2闭包的性质116

 

3.8集合的划分与覆盖118

 

3.9等价关系和等价类119

 

3.9.1等价关系119

 

3.9.2等价类的性质120

 

3.9.3商集与划分121

 

3.10相容关系和相容类122

 

3.11偏序关系124

 

3.12偏序集与哈斯图125

 

3.13应用案例128

 

3.13.1同余关系在出版

 

业中的应用128

 

3.13.2拓扑排序在建筑

 

工序中的应用128

 

3.13.3等价关系在软件

 

测试等价类划分

 

中的应用129

 

习题129

 

计算机编程题135

 

第4章函数136

 

4.1函数的定义136

 

4.1.1函数和像136

 

4.1.2函数的性质138

 

4.1.3常用函数139

 

4.2复合函数和反函数140

 

4.2.1复合函数140

 

4.2.2反函数142

 

4.3特征函数与模糊子集144

 

4.4基数的概念146

 

4.4.1后继与归纳集146

 

4.4.2自然数，有穷集，

 

无穷集147

 

4.4.3基数152

 

4.5可数集与不可数集153

 

4.6数学归纳法154

 

4.7应用案例157

 

4.7.1逢黑必反魔术157

 

4.7.2生成函数在解决汉诺塔

 

问题中的应用158

 

习题158

 

计算机编程题162

 

第5章组合计数163

 

5.1基本原理163

 

5.1.1加法原理163

 

5.1.2乘法原理164

 

5.2排列与组合165

 

5.2.1排列165

 

5.2.2组合165

 

5.3排列组合生成算法166

 

5.3.1排列生成算法166

 

5.3.2组合生成算法168

 

5.4广义的排列和组合170

 

5.5二项式系数和组合恒

 

等式171

 

5.5.1二项式定理171

 

5.5.2组合恒等式173

 

5.6鸽笼原理174

 

5.6.1鸽笼原理的简单

 

形式174

 

5.6.2鸽笼原理的一般

 

形式174

 

5.7递推关系及应用176

 

5.7.1递推定义函数176

 

5.7.2递推定义集合177

 

5.7.3递推关系模型178

 

5.7.4求解递推关系180

 

5.7.5递推在算法分析中的

 

应用181

 

5.7.6生成函数183

 

5.8应用案例186

 

5.8.1大使馆通信的码

 

字数186

 

5.8.2条条道路通罗马186

 

习题187

 

计算机编程题188

 

第6章图论189

 

6.1图的基本概念189

 

6.1.1图的定义和表示189

 

6.1.2图的同构194

 

6.1.3完全图与正则图195

 

6.1.4子图与补图195

 

6.1.5通路与回路198

 

6.2图的连通性199

 

6.2.1无向图的连通性199

 

6.2.2有向图的连通性201

 

6.3图的矩阵表示202

 

6.3.1关联矩阵202

 

6.3.2有向图的邻接

 

矩阵203

 

6.3.3有向图的可达

 

矩阵204

 

6.4欧拉图204

 

6.5哈密顿图207

 

6.6二部图210

 

6.6.1二部图及判别

 

定理210

 

6.6.2完备匹配211

 

6.7平面图213

 

6.7.1平面图及其判定

 

定理213

 

6.7.2平面图的对偶图219

 

6.8带权图220

 

6.9应用案例221

 

6.9.1网络爬虫221

 

6.9.2读心术魔术222

 

6.9.3高度互联世界的

 

行为原理222

 

习题222

 

计算机编程题229

 

第7章树及其应用230

 

7.1概述230

 

7.1.1树的定义及相关

 

术语230

 

7.1.2树的性质232

 

7.2生成树233

 

7.3最小生成树237

 

7.4树的遍历239

 

7.5二叉树241

 

7.5.1二叉树的性质241

 

7.5.2二叉搜索树242

 

7.5.3哈夫曼树242

 

7.6决策树244

 

7.6.1决策树的定义245

 

7.6.2最短时间排序246

 

7.7树的同构247

 

7.8博弈树251

 

7.8.1博弈树的概念251

 

7.8.2极大极小分析法252

 

7.9应用案例254

 

7.9.1哈夫曼压缩算法的

 

基本原理254

 

7.9.2决策树在风险决策

 

中的应用254

 

7.9.3一字棋博弈的极大

 

极小过程255

 

习题255

 

计算机编程题257

 

第8章代数系统259

 

8.1二元运算及其性质259

 

8.1.1定义和表示259

 

8.1.2二元运算的性质261

 

8.2代数系统263

 

8.2.1定义和实例263

 

8.2.2子代数系统265

 

8.2.3代数系统的同态

 

与同构266

 

8.3半群与独异点266

 

8.3.1定义与性质266

 

8.3.2子系统与直积268

 

8.4群269

 

8.4.1群的定义269

 

8.4.2群的性质271

 

8.4.3子群的定义273

 

8.4.4特殊的群274

 

8.4.5陪集与拉格朗日

 

定理277

 

8.4.6正规子群与商群278

 

8.4.7群的同态与同构

 

实例280

 

8.5环与域282

 

8.5.1环282

 

8.5.2域284

 

8.6格与布尔代数284

 

8.6.1格284

 

8.6.2布尔代数288

 

8.7应用案例291

 

8.7.1组合电路291

 

8.7.2物理世界中群的

 

应用292

 

8.7.3群码及纠错能力292

 

习题292

 

计算机编程题299

 

第9章自动机、文法和语言300

 

9.1串和语言300

 

9.2形式文法301

 

9.3有限状态机304

 

9.4有限状态自动机306

 

9.5不确定有限状态自动机310

 

9.6语言和自动机之间的

 

关系313

 

9.7应用案例314

 

9.7.1奇偶校验机314

 

9.7.2识别地址的有限

 

状态机314

 

9.7.3语音识别315

 

习题315

 

计算机编程题318

 

第10章数论与密码学319

 

10.1素数319

 

10.2最大公约数与最小公

 

倍数320

 

10.3同余323

 

10.4一次同余方程和中国

 

剩余定理325

 

10.4.1一次同余方程325

 

10.4.2中国剩余定理326

 

10.5欧拉定理和费马小

 

定理327

 

10.6数论在密码学中的

 

应用328

 

10.6.1公钥密码学328

 

10.6.2RSA密码328

 

10.7应用案例330

 

10.7.1密码系统与公开

 

密钥330

 

10.7.2单向陷门函数在

 

公开密钥密码系

 

统中的应用330

 

习题331

 

计算机编程题331

 

附录历史注记332

 

参考文献334