离散数学2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

离散数学PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 数学语言与证明方法1

1.1 常用的数学符号1

1.1.1 集合符号1

1.1.2 运算符号2

1.1.3 逻辑符号3

1.2 集合及其运算5

1.2.1 集合及其表示法5

1.2.2 集合之间的包含与相等6

1.2.3 集合的幂集8

1.2.4 集合的运算8

1.2.5 基本集合恒等式及其应用11

1.3.1 逻辑推理的形式结构16

1.3 证明方法概述16

1.3.2 公理、定理与证明17

1.3.3 证明方法19

1.3.4 数学归纳法24

习题30

第2章 命题逻辑35

2.1 命题逻辑基本概念35

2.1.1 命题与联结词35

2.1.2 命题公式及其分类42

2.2 命题逻辑等值演算48

2.2.1 等值式与等值演算48

2.2.2 联结词完备集53

2.3.1 析取范式与合取范式55

2.3 范式55

2.3.2 主析取范式与主合取范式58

2.4 命题逻辑推理理论66

2.4.1 推理的形式结构66

2.4.2 自然推理系统P69

2.4.3 归结证明法75

习题78

第3章 一阶逻辑84

3.1 一阶逻辑基本概念84

3.1.1 命题逻辑的局限性84

3.1.2 个体词、谓词与量词84

3.1.3 一阶逻辑命题符号化86

3.1.4 一阶逻辑公式与分类90

3.2 一阶逻辑等值演算95

3.2.1 一阶逻辑等值式与置换规则95

3.2.2 一阶逻辑前束范式99

3.3 一阶逻辑推理理论102

3.3.1 一阶逻辑中推理的形式结构102

3.3.2 量词消去与引入规则102

3.3.3 自然推理系统F104

习题107

第4章 关系113

4.1 关系的定义及其表示113

4.1.1 有序对与笛卡儿积113

4.1.2 二元关系的定义114

4.1.3 二元关系的表示116

4.2 关系的运算117

4.2.1 关系的基本运算117

4.2.2 关系的幂运算121

4.3 关系的性质124

4.3.1 关系性质的定义和判别124

4.3.2 关系的闭包128

4.4 等价关系与偏序关系133

4.4.1 等价关系133

4.4.2 等价类和商集134

4.4.3 集合的划分135

4.4.4 偏序关系137

4.4.5 偏序集与哈斯图138

习题143

第5章 函数148

5.1 函数的定义及其性质148

5.1.1 函数的定义148

5.1.2 函数的像与完全原像151

5.1.3 函数的性质151

5.2 函数的复合与反函数155

5.2.1 函数的复合155

5.2.2 反函数157

习题158

6.1.1 无向图与有向图162

6.1 图的基本概念162

第6章 图162

6.1.2 顶点的度数与握手定理164

6.1.3 简单图、完全图、正则图、圈图、轮图、方体图167

6.1.4 子图、补图169

6.1.5 图的同构170

6.2 图的连通性172

6.2.1 通路与回路172

6.2.2 无向图的连通性与连通度173

6.2.3 有向图的连通性及其分类176

6.3 图的矩阵表示176

6.3.2 有向无环图的关联矩阵177

6.3.1 无向图的关联矩阵177

6.3.3 有向图的邻接矩阵178

6.3.4 有向图的可达矩阵180

6.4 几种特殊的图181

6.4.1 二部图181

6.4.2 欧拉图184

6.4.3 哈密顿图186

6.4.4 平面图191

习题200

第7章 树及其应用205

7.1 无向树205

7.1.1 无向树的定义及其性质205

7.1.2 生成树与基本回路和基本割集208

7.1.3 最小生成树211

7.2.1 根树及其分类212

7.2 根树及其应用212

7.2.2 最优树与哈夫曼算法213

7.2.3 最佳前缀码214

7.2.4 根树的周游及其应用216

习题218

第8章 组合计数基础222

8.1 基本计数规则223

8.1.1 加法法则223

8.1.2 乘法法则224

8.1.3 分类处理与分步处理224

8.2.1 集合的排列与组合225

8.2 排列与组合225

8.2.2 多重集的排列与组合229

8.3 二项式定理与组合恒等式232

8.3.1 二项式定理232

8.3.2 组合恒等式233

8.3.3 非降路径问题237

8.4 多项式定理与多项式系数240

8.4.1 多项式定理240

8.4.2 多项式系数241

习题242

9.1.1 容斥原理的基本形式245

9.1 容斥原理及其应用245

第9章 容斥原理245

9.1.2 容斥原理的应用246

9.2 对称筛公式及其应用250

9.2.1 对称筛公式250

9.2.2 棋盘多项式与有限制条件的排列252

习题256

第10章 递推方程与生成函数257

10.1 递推方程及其应用257

10.1.1 递推方程的定义及实例257

10.1.2 常系数线性齐次递推方程的求解260

10.1.3 常系数线性非齐次递推方程的求解263

10.1.4 递推方程的其他解法265

10.1.5 递推方程与递归算法270

10.2 生成函数及其应用272

10.2.1 牛顿二项式定理与牛顿二项式系数272

10.2.2 生成函数的定义及其性质273

10.2.3 生成函数的应用276

10.3 指数生成函数及其应用281

10.4 Catalan数与Stirling数284

习题289

第11章 初等数论292

11.1 素数292

11.2 最大公约数与最小公倍数296

11.3 同余298

11.4.1 一次同余方程301

11.4 一次同余方程与中国剩余定理301

11.4.2 中国剩余定理303

11.4.3 大整数算术运算304

11.5 欧拉定理和费马小定理306

习题307

第12章 离散概率312

12.1 随机事件与概率、事件的运算312

12.1.1 随机事件与概率312

12.1.2 事件的运算314

12.2 条件概率与独立性315

12.2.1 条件概率315

12.2.2 独立性317

12.2.3 伯努利概型与二项概率公式318

12.3 离散型随机变量319

12.3.1 离散型随机变量及其分布律319

12.3.2 常用分布321

12.3.3 数学期望322

12.3.4 方差324

12.4 概率母函数326

习题329

第13章 初等数论和离散概率的应用333

13.1 密码学333

13.1.1 恺撒密码333

13.1.2 RSA公钥密码334

13.2.1 产生均匀伪随机数的方法337

13.2 产生伪随机数的方法337

13.2.2 产生离散型伪随机数的方法338

13.3 算法的平均复杂度分析340

13.3.1 排序算法340

13.3.2 散列表的检索和插入344

13.4 随机算法348

13.4.1 随机快速排序算法348

13.4.2 多项式恒零测试349

13.4.3 素数测试351

13.4.4 蒙特卡罗法和拉斯维加斯法352

习题353

14.1.1 二元运算与一元运算的定义356

14.1 二元运算及其性质356

第14章 代数系统356

14.1.2 二元运算的性质358

14.2 代数系统362

14.2.1 代数系统的定义与实例362

14.2.2 代数系统的分类363

14.2.3 子代数系统与积代数系统364

14.2.4 代数系统的同态与同构365

14.3 几个典型的代数系统367

14.3.1 半群与独异点367

14.3.2 群368

14.3.3 环与域376

14.3.4 格与布尔代数379

习题385