离散数学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