离散数学 第2版PDF|Epub|txt|kindle电子书版本网盘下载

离散数学 第2版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　证明方法概述15

1.3.1　逻辑推理的形式结构15

1.3.2　公理、定理与证明17

1.3.3　证明方法18

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　范式55

2.3.1　析取范式与合取范式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　一阶逻辑等值演算94

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

3.2.2　一阶逻辑前束范式99

习题101

第4章　关系107

4.1　关系的定义及其表示107

4.1.1　有序对与笛卡儿积107

4.1.2　二元关系的定义108

4.1.3　二元关系的表示110

4.2　关系的运算111

4.2.1　关系的基本运算111

4.2.2　关系的幂运算115

4.3　关系的性质118

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

4.3.2　关系的闭包122

4.4　等价关系与偏序关系127

4.4.1　等价关系127

4.4.2　等价类和商集128

4.4.3　集合的划分129

4.4.4　偏序关系131

4.4.5　偏序集与哈斯图132

习题137

第5章　函数142

5.1　函数的定义及其性质142

5.1.1　函数的定义142

5.1.2　函数的像与完全原像145

5.1.3　函数的性质145

5.2　函数的复合与反函数149

5.2.1　函数的复合149

5.2.2　反函数151

习题152

第6章　图156

6.1　图的基本概念156

6.1.1　无向图与有向图156

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

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

6.1.4　子图、补图163

6.1.5 图的同构164

6.2　图的连通性166

6.2.1　通路与回路166

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

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

6.3　图的矩阵表示170

6.3.1　无向图的关联矩阵171

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

6.3.3　有向图的邻接矩阵172

6.3.4　有向图的可达矩阵174

6.4　几种特殊的图175

6.4.1　二部图175

6.4.2　欧拉图178

6.4.3　哈密顿图180

6.4.4　平面图185

习题194

第7章　树及其应用199

7.1　无向树199

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

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

7.1.3　最小生成树205

7.2　根树及其应用206

7.2.1　根树及其分类206

7.2.2　最优树与哈夫曼算法207

7.2.3　最佳前缀码208

7.2.4　根树的周游及其应用210

习题212

第8章　组合计数基础216

8.1　基本计数规则217

8.1.1　加法法则217

8.1.2　乘法法则218

8.1.3　分类处理与分步处理218

8.2　排列与组合219

8.2.1　集合的排列与组合219

8.2.2　多重集的排列与组合223

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

8.3.1　二项式定理226

8.3.2　组合恒等式227

8.3.3　非降路径问题231

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

8.4.1　多项式定理234

8.4.2　多项式系数235

习题236

第9章　容斥原理239

9.1　容斥原理及其应用239

9.1.1　容斥原理的基本形式239

9.1.2　容斥原理的应用240

9.2　对称筛公式及其应用244

9.2.1　对称筛公式244

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

习题250

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

10.1　递推方程及其应用251

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

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

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

10.1.4　递推方程的其他解法259

10.1.5　递推方程与递归算法264

10.2　生成函数及其应用266

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

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

10.2.3　生成函数的应用270

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

10.4 Catalan数与Stirling数278

习题283

第11章　初等数论286

11.1　素数286

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

11.3　同余292

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

11.4.1　一次同余方程295

11.4.2　中国剩余定理297

11.4.3　大整数算术运算298

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

习题301

第12章　离散概率306

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

12.1.1　随机事件与概率306

12.1.2　事件的运算308

12.2　条件概率与独立性309

12.2.1　条件概率309

12.2.2　独立性311

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

12.3　离散型随机变量313

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

12.3.2　常用分布315

12.3.3　数学期望316

12.3.4　方差318

12.4　概率母函数320

习题323

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

13.1　密码学327

13.1.1　恺撒密码327

13.1.2 RSA公钥密码328

13.2　产生伪随机数的方法331

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

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

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

13.3.1　排序算法334

13.3.2　散列表的检索和插入338

13.4　随机算法342

13.4.1　随机快速排序算法342

13.4.2　多项式恒零测试343

13.4.3　素数测试345

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

习题347

第14章　代数系统350

14.1　二元运算及其性质350

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

14.1.2　二元运算的性质352

14.2　代数系统356

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

14.2.2　代数系统的分类357

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

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

14.3　几个典型的代数系统361

14.3.1　半群与独异点361

14.3.2　群362

14.3.3　环与域370

14.3.4　格与布尔代数373

习题379

参考文献383