目录

CONTENTS

第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证明方法概述16

1.3.1逻辑推理的形式结构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范式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一阶逻辑等值演算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章图162

6.1图的基本概念162

6.1.1无向图与有向图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.1无向图的关联矩阵177

6.3.2有向无环图的关联矩阵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根树及其应用212

7.2.1根树及其分类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排列与组合225

8.2.1集合的排列与组合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章容斥原理245

9.1容斥原理及其应用245

9.1.1容斥原理的基本形式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.4Catalan数与Stirling数284

习题289

第11章初等数论292

11.1素数292

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

11.3同余298

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

11.4.1一次同余方程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.2RSA公钥密码334

13.2产生伪随机数的方法337

13.2.1产生均匀伪随机数的方法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章代数系统356

14.1二元运算及其性质356

14.1.1二元运算与一元运算的定义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