离散数学PDF电子书下载

第一篇 集合论 3

第1章 集合 3

1.1 集合的概念及其表示 3

1.2 集合的基本运算 4

1.3 笛卡儿积 6

习题一 6

第2章 关系 8

2.1 关系及其表示 8

2.2 关系的运算 9

2.3 等价关系 12

2.4 序关系 14

习题二 16

第3章 映射 18

3.1 基本概念 18

3.2 映射的运算 19

习题三 20

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

4.1 等势 21

4.2 集合的基数 22

4.3 可数集与不可数集 23

习题四 24

第二篇 图论 29

第5章 图与子图 29

5.1 图的概念 29

5.2 图的同构 31

5.3 顶点的度 32

5.4 子图及图的运算 32

5.5 通路与连通图 34

5.6 图的矩阵表示 36

5.7 应用 37

习题五 40

第6章 树 43

6.1 树的定义 43

6.2 生成树 45

6.3 应用 47

习题六 48

第7章 图的连通性 50

7.1 点连通度和边连通度 50

7.2 块 52

7.3 应用 54

习题七 55

第8章 E图与H图 57

8.1 七桥问题与E图 57

8.2 周游世界问题与H图 58

8.3 应用 61

习题八 63

第9章 匹配与点独立集 65

9.1 匹配 65

9.2 独立集和覆盖 69

9.3 Ramsey数 71

9.4 应用 75

习题九 76

第10章 图的着色 78

10.1 顶点着色 78

10.2 边着色 80

10.3 色多项式 83

10.4 应用 86

习题十 86

第11章 平面图 88

11.1 平面图的概念 88

11.2 欧拉公式 90

11.3 可平面性判定 91

11.4 平面图的面着色 92

11.5 应用 94

习题十一 94

第12章 有向图 96

12.1 有向图的概念 96

12.2 有向通路与有向回路 98

12.3 有向树 100

12.4 应用 101

习题十二 103

第13章 网络最大流 105

13.1 网络的流与割 105

13.2 最大流最小割定理 107

13.3 应用 110

习题十三 110

第三篇 数理逻辑 113

第14章 命题逻辑 113

14.1 命题与逻辑联结词 113

14.2 命题公式与等值演算 115

14.3 对偶与范式 118

14.4 推理理论 123

14.5 命题演算的公理系统 127

习题十四 130

第15章 一阶逻辑 134

15.1 谓词与量词 134

15.2 合式公式及解释 137

15.3 等值式与范式 139

15.4 一阶逻辑的推理理论 143

习题十五 147

第四篇 代数结构 151

第16章 整数 151

16.1 整除性 151

16.2 质因数分解 155

16.3 同余 157

16.4 孙子定理·Euler函数 159

16.5 数论在计算机密码学中的应用 163

习题十六 165

第17章 群 167

17.1 群的概念 167

17.2 子群 170

17.3 置换群 173

17.4 陪集与Lagrange定理 178

17.5 同态与同构 181

17.6 群在计算机科学与技术中的应用 185

习题十七 187

第18章 环与域 190

18.1 环与子环 190

18.2 环同态 193

18.3 域的特征、质域 196

18.4 有限域 198

18.5 有限域的结构 202

18.6 纠错码 207

18.7 多项式编码方法及其实现 214

习题十八 217

第19章 格与布尔代数 220

19.1 格的定义 220

19.2 格的性质 222

19.3 几种特殊的格 225

19.4 布尔代数 228

19.5 有限布尔代数的结构 233

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

习题十九 241

第五篇 组合分析初步第20章 排列和组合的一般计数方法 247

20.1 两个基本的计数法则 247

20.2 基本排列组合的计数方法 248

20.3 可重复排列组合的计数方法 249

习题二十 251

第21章 容斥原理 252

21.1 容斥原理介绍 252

21.2 有禁止位的排列 253

习题二十一 256

第22章 递推关系与生成函数 257

22.1 递推关系及其解法 257

22.2 生成函数 259

习题二十二 261

参考文献 262