离散数学教程PDF电子书下载

第1章 命题逻辑 1

1.1命题的表示与逻辑联结词 1

1.2命题合适公式与真值表 6

1.3命题公式的等价 9

1.4命题公式的范式表示 13

1.5命题公式的蕴含 17

1.6命题逻辑的推理方法 20

1.7逻辑联结词的功能完备集 24

1.8应用：数字逻辑电路设计 26

第2章 一阶谓词逻辑 30

2.1量词化逻辑 30

2.2谓词合适公式及其解释 33

2.3谓词公式的等价与范式表示 37

2.4谓词公式的蕴含 42

2.5谓词逻辑的推理方法 45

2.6应用：逻辑程序设计 49

第3章 集合及其运算 52

3.1集合的基本概念 52

3.2集合间的运算 55

3.3集合的范式表示 58

3.4集合的幂集和笛卡尔集 60

3.5应用：形式语言 62

第4章 初等数论和证明方法 66

4.1整数集合 66

4.2商和余数 68

4.3整除和素因子分解 70

4.4最大公因子 72

4.5数学归纳法 74

4.6应用：随机数 77

第5章 二元关系 79

5.1二元关系及其表示 79

5.2二元关系的性质 82

5.3关系的运算 84

5.4二元关系的闭包 87

5.5等价关系 91

5.6偏序关系 94

5.7应用：关系数据库管理系统 99

第6章 函数 101

6.1一般集合的函数概念 101

6.2单射、满射和双射 104

6.3函数的递归定义 108

6.4集合的基数、可数集和不可数集 111

6.5应用：算法的复杂性表示 116

第7章 基本计数方法 120

7.1排列计数 120

7.2组合计数 123

7.3组合恒等式 126

7.4容斥原理 128

7.5鸽巢原理 131

第8章 生成函数和递推关系 134

8.1序列与生成函数 134

8.2组合问题的生成函数 137

8.3递推关系式及其解 141

8.4递推关系式的生成函数求解 146

8.5应用：排序算法 150

第9章 无向图和有向图 153

9.1图的基本概念 153

9.2图的道路与连通性 161

9.3图的矩阵表示 166

9.4独立集、点团和极图问题 174

9.5图的着色 179

第10章 基本图类和算法 186

10.1树与生成树 186

10.2根树及其应用 190

10.3图的生成树构造和计数 196

10.4平面图与对偶图 203

10.5欧拉图及其应用 207

10.6哈密顿图及其应用 212

10.7图的匹配与匈牙利算法 217

10.8网络 222

第11章 群和环 230

11.1运算与代数系统 230

11.2半群 233

11.3群和子群 236

11.4交换群和循环群 239

11.5陪集与拉格朗日定理 241

11.6同态与同构 243

11.7环和域 246

11.8应用：群码 250

第12章 格与布尔代数 253

12.1格的两个等价定义 253

12.2格的性质和格同态 256

12.3分配格和有补格 259

12.4布尔代数 262

附录 266

一、本书使用记号一览 266

二、离散数学术语的中、英文对照（以汉语拼音为序） 268

三、离散数学自测试题 276

参考文献 279