离散数学PDF电子书下载

第一篇 集合论与数理逻辑 3

第1章 集合 3

1.1 集合的概念及其表示 3

1.2 集合的基本运算 5

1.3 笛卡儿积 6

习题 7

第2章 关系 9

2.1 关系及其表示 9

2.2 关系的运算 10

2.3 等价关系 13

2.4 序关系 15

习题 17

第3章 映射 19

3.1 基本概念 19

3.2 映射的运算 20

习题 21

第4章 可数集与不可数集 22

4.1 等势 22

4.2 集合的基数 23

4.3 可数集与不可数集的概念 24

习题 25

第5章 命题逻辑 27

5.1 命题与逻辑联结词 27

5.2 命题公式与等值演算 29

5.3 对偶与范式 33

5.4 推理理论 38

5.5 命题演算的公理系统 42

习题 45

第6章 一阶逻辑 48

6.1 谓词与量词 48

6.2 合式公式及解释 51

6.3 等值式与范式 53

6.4 一阶逻辑的推理理论 56

习题 60

第二篇 图论与组合数学 65

第7章 图与子图 65

7.1 图的概念 65

7.2 图的同构 67

7.3 顶点的度 68

7.4 子图及图的运算 69

7.5 通路与连通图 70

7.6 图的矩阵表示 72

7.7 应用（最短通路问题） 73

习题 77

第8章 树 80

8.1 树的定义 80

8.2 生成树 82

8.3 应用（最优树问题） 84

习题 86

第9章 图的连通性 87

9.1 点连通度和边连通度 87

9.2 块 89

9.3 应用（构造可靠的通信网络） 91

习题 92

第10章 E图与H图 94

10.1 七桥问题与E图 94

10.2 周游世界问题与H图 95

10.3 应用（旅行推销员问题） 99

习题 100

第11章 匹配与点独立集 102

11.1 匹配 102

11.2 独立集和覆盖 106

11.3 Ramsey数 108

11.4 应用（人员分配问题） 112

习题 113

第12章 图的着色 115

12.1 顶点着色 115

12.2 边着色 118

12.3 色多项式 120

12.4 应用 123

习题 124

第13章 平面图 125

13.1 平面图的概念 125

13.2 欧拉公式 127

13.3 可平面性判定 129

13.4 平面图的面着色 129

13.5 应用（印制电路板的设计） 131

习题 131

第14章 有向图 133

14.1 有向图的概念 133

14.2 有向通路与有向回路 135

14.3 有向树 137

14.4 应用 139

习题 140

第15章 网络最大流 142

15.1 网络的流与割 142

15.2 最大流最小割定理 144

15.3 应用（中国邮递员问题） 147

习题 147

第16章 排列和组合的一般计数方法 149

16.1 两个基本的计数法则 149

16.2 基本排列组合的计数方法 149

16.3 可重复排列组合的计数方法 151

习题 153

第17章 容斥原理 154

17.1 容斥原理概述 154

17.2 有禁止位的排列 155

习题 158

第18章 递推关系与生成函数 159

18.1 递推关系及其解法 159

18.2 生成函数 161

习题 163

第三篇 代数结构与初等数论 167

第19章 整数 167

19.1 整除性 167

19.2 素因数分解 171

19.3 同余 173

19.4 孙子定理·Euler函数 175

19.5 数论在计算机密码学中的应用 179

习题 181

第20章 群 183

20.1 群的概念 183

20.2 子群 186

20.3 置换群 189

20.4 陪集与Lagrange定理 194

20.5 同态与同构 197

20.6 群在计算机科学与技术中的应用 201

习题 203

第21章 环与域 206

21.1 环与子环 206

21.2 环同态 209

21.3 域的特征·质域 212

21.4 有限域 214

21.5 有限域的结构 218

21.6 纠错码 222

21.7 多项式编码方法及其实现 230

习题 233

第22章 格与布尔代数 235

22.1 格的定义 235

22.2 格的性质 237

22.3 几种特殊的格 240

22.4 布尔代数 243

22.5 有限布尔代数的结构 249

22.6 格与布尔代数在计算机科学与技术中的应用 253

习题 257

第四篇 形式语言与自动机理论基础 263

第23章 形式语言 263

23.1 符号、符号串及其运算 263

23.2 文法与语言的形式定义 265

23.3 正规表达式 272

23.4 正规文法与正规式 276

习题 279

第24章 有限自动机理论 280

24.1 有限自动机的定义与构造 280

24.2 确定的有限自动机（DFA） 282

24.3 不确定的有限自动机（NFA） 283

24.4 NFA的确定化 285

24.5 DFA的最小化 288

24.6 正规集与有限自动机的等价性 290

习题 292

参考文献 294