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

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

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

目录1

第1章　数理逻辑基础1

1.1　命题1

1.1.1　命题的概念1

1.1.2　命题联结词3

1.2　命题公式与翻译6

1.2.1　命题变元与命题公式6

1.2.2　命题公式真值表的构造7

1.2.3　翻译语言句子为逻辑表达式8

1.3　命题等价8

1.3.1　命题逻辑中的永真式8

1.3.2　命题的逻辑等价9

1.3.3　对偶公式与对偶定理12

1.4　命题逻辑的范式13

1.4.1　析取范式与合取范式13

1.4.2　主析取范式15

1.4.3　主合取范式18

1.4.4　范式的作用20

1.4.5　范式的应用举例22

1.5　谓词和量词24

1.5.1　谓词与个体24

1.5.2　命题函数与函数26

1.5.3　量词27

1.6　谓词公式及其翻译29

1.6.1 谓词公式29

1.6.2　翻译语言句子为谓词公式31

1.7 自由变元和约束变元32

1.7.1 自由出现与约束出现32

1.7.2　改名与代入33

1.8　谓词逻辑中的永真式34

1.8.1　解释、真假性34

1.8.2　等价永真公式与蕴涵永真公式37

1.9.1　前束范式41

1.8.3　对偶公式和对偶定理41

1.9　谓词逻辑中的范式41

1.9.2　斯科林（skolem）范式44

小结45

习题一45

一、基础题45

二、证明题49

第2章 集合50

2.1 集合概述50

2.1.1　集合的发展50

2.1.2　集合的概念51

2.1.3　集合的表示法53

2.1.4　集合的基数55

2.1.5　集合的相等关系与包容关系55

2.2.1 交运算57

2.2.2　并运算57

2.2　集合的运算57

2.2.3　差运算58

2.2.4　补运算58

2.2.5　对称差59

2.3　集合运算定律59

2.3.1　集合成员表59

2.3.2　集合运算的定律62

2.3.3　幂集67

2.4　笛卡尔乘积68

2.4.1 笛卡尔乘积的概念69

2.4.2　笛卡尔乘积的有关性质70

2.5　集合在计算机中的表示71

小结72

习题二72

一、基础题72

二、证明题74

3.1.1　关系的概念75

第3章　关系75

3.1　关系的基础知识75

3.1.2　关系的性质78

3.1.3　关系的表示法82

3.2　关系的运算88

3.2.1　关系的交、并、差、补运算88

3.2.2　关系的逆运算89

3.2.3　关系的复合运算90

3.3　关系的闭包运算95

3.3.1　关系闭包的概念95

3.3.2　关系闭包的计算96

3.4　等价关系99

3.4.1　等价关系的概念99

3.4.2　等价类101

3.5　相容关系103

3.5.1　相容关系的概念104

3.5.2　最大相容类105

3.6　偏序106

3.6.1　偏序的概念106

3.6.2　字典顺序108

3.6.3　偏序的哈斯图109

3.6.4　极大元素和极小元素110

3.6.5　格112

小结114

习题三114

一、基础题114

二、证明题116

第4章 函数118

4.1 函数基础知识118

4.1.1　函数的概念118

4.1.2　函数的图像121

4.1.3　几个重要的特殊函数121

4.2.1　复合函数的概念123

4.2　复合函数123

4.2.2　复合函数的性质124

4.3　反函数126

4.3.1　反函数的概念126

4.3.2　反函数的性质127

4.4　集合的基数129

4.4.1　基数的概念129

4.4.2　可数集的概念及其性质130

4.4.3　不可数集132

4.4.4　集合基数的比较133

小结134

习题四135

一、基础题135

二、证明题137

5.1　推理规则138

5.1.1　命题逻辑的推理规则138

第5章　数学推理138

5.1.2　谓词逻辑的推理规则145

5.2　证明定理的方法149

5.2.1　蕴涵式的证明方法149

5.2.2　带量词的命题的证明方法157

5.3　重要的证明方法——数学归纳法160

5.3.1　数学归纳法概述160

5.3.2　第一数学归纳法162

5.3.3　第一数学归纳法证明的例子163

5.3.4　第二数学归纳法168

5.3.5　为什么数学归纳法是有效的171

5.4　递归的定义方法171

5.4.1　递归定义序列171

5.4.2　递归定义函数173

5.4.3　递归定义集合174

小结175

一、基础题176

习题五176

二、证明题178

第6章　组合数学180

6.1　基本计数原则180

6.1.1　加法原则180

6.1.2　乘法原则181

6.2　鸽巢定理182

6.2.1　鸽巢定理的概念182

6.2.2　鸽巢定理的推广182

6.3　排列与组合184

6.3.1　事物的排列184

6.3.2　事物的组合186

6.3.3　多重集188

6.4　二项式定理与组合等式192

6.5　离散概率195

6.5.1　集合的离散概率196

6.5.2　条件概率198

6.5.3　贝努利实验和二项式分布199

6.6　递推关系201

6.6.1　递推关系基础知识201

6.6.2　汉诺塔问题模型202

6.6.3　递推关系的求解203

6.7　生成函数206

6.7.1 生成函数的定义207

6.7.2　生成函数与计数问题207

小结208

习题六208

一、基础题208

二、证明题209

第7章　基础代数210

7.1　基本概念210

7.1.1　除法210

7.1.3　模运算211

7.1.2　素数211

7.1.4　同余应用212

7.2　数论的应用212

7.2.1　若干有用的结果212

7.2.2　线性同余213

7.2.3 中国剩余定理214

7.2.4　伪素数215

7.2.5　数论在计算机上的应用——密码学216

7.3　矩阵218

7.3.1　矩阵概述218

7.3.2　矩阵的运算218

7.3.3　0-1矩阵220

7.4　群222

7.4.1 代数系统的基本概念与性质222

7.4.2　同构、同态与自然同态226

7.4.3　群、正规子群及其同态定理232

7.4.4　几类特殊的群240

7.4.5　群、理想、整环和域243

小结248

习题七249

一、基础题249

二、证明题249

第8章　布尔代数与逻辑电路251

8.1　布尔函数251

8.1.1　布尔函数概述251

8.1.2　布尔表达式与布尔函数252

8.1.3　格253

8.1.4　布尔代数258

8.2　布尔函数的表示265

8.2.1　积之和展开式266

8.2.2　函数完备性267

8.3　逻辑门电路268

8.3.1　逻辑门电路概述268

8.3.2　门的组合269

8.3.3　触发器270

8.4　电路的极小化272

8.4.1　电路极小化的概述272

8.4.2　卡诺图273

8.4.3　奎因-莫可拉斯基方法279

小结281

习题八282

一、基础题282

二、证明题284

第9章　图论286

9.1 图的基础知识286

9.1.1　图的基本概念286

9.1.2　图的运算291

9.1.3　图的同构293

9.2.1　通路、回路与连通性294

9.2　通路与回路294

9.2.2　欧拉图296

9.2.3　哈密顿图299

9.2.4　图的矩阵表示301

9.2.5　最短路径304

9.3　平面图与图着色306

9.3.1 平面图306

9.3.2　欧拉公式与库拉图斯基定理308

9.3.3 图着色311

9.4　树314

9.4.1　树的基本概念314

9.4.2　树的基本性质318

9.4.3　树的应用321

9.5　树的遍历与排序323

9.5.1 树的遍历323

9.5.2　树的排序329

9.6.1　生成树概述331

9.6　生成树331

9.6.2　最小生成树335

小结337

习题九338

一、基础题338

二、证明题344

第10章　离散数学在计算机中的应用345

10.1　离散数学在编译器构造中的应用345

10.1.1　编译器简介345

10.1.2　编译器的计算机模型——文法模型346

10.1.3　编译器的词法分析349

10.2　离散数学在关系数据库中的应用351

10.2.1　关系数据库简介351

10.2.2　数据模型354

10.2.3　关系模型355

10.3.2　Huffman算法360

10.3.1　Huffman树360

10.3　图论实例——Huffman压缩算法360

10.3.3　Huffman算法在编码理论中的应用361

10.4　图论实例——网络流362

小结364

习题十365

参考答案366

第1章366

第2章367

第3章369

第4章370

第5章370

第6章372

第7章375

第8章375

第9章376

第10章379

参考文献380