离散数学及其应用PDF电子书下载

第一部分 数理逻辑 2

第1章 命题逻辑 2

1.1命题与联结词 2

1.1.1命题的概念 2

1.1.2联结词 3

1.2命题公式及其分类 8

1.3命题演算的关系式 10

1.3.1等价关系式 10

1.3.2全功能联结词集 13

1.3.3对偶式 14

1.4范式 15

1.4.1析取范式和合取范式 15

1.4.2主析取范式和主合取范式 16

1.5命题演算的推理 20

1.5.1推理理论 20

1.5.2推理证明方法 21

习题 25

第2章 谓词逻辑 29

2.1谓词逻辑的基本概念 29

2.1.1个体词和谓词 29

2.1.2量词 31

2.2谓词合式公式 34

2.3谓词公式的解释和分类 35

2.3.1谓词公式的解释 35

2.3.2谓词公式的分类 36

2.4谓词演算的关系式 37

2.5前束范式 40

2.6谓词演算的推理 41

2.6.1推理理论 41

2.6.2推理问题的证明 43

习题 48

第二部分 集合、关系和函数 54

第3章 集合 54

3.1集合及其表示 54

3.2集合间的关系 55

3.3集合的运算 57

3.4自然数 62

3.5集合的特征函数 63

习题 64

第4章 关系和函数 67

4.1关系的概念 67

4.1.1有序对和有序n元组 67

4.1.2笛卡儿积 67

4.1.3关系的概念 69

4.2关系的表示法 71

4.2.1用集合表示关系 71

4.2.2用关系图表示关系 72

4.2.3用矩阵表示关系 73

4.3关系的运算 73

4.3.1关系的逆运算 74

4.3.2关系的复合运算 75

4.4关系的性质 79

4.5关系的闭包 85

4.6等价关系和等价类 91

4.6.1等价关系 91

4.6.2等价类 92

4.7偏序关系 96

4.8函数 100

4.8.1函数的定义 100

4.8.2特殊函数 101

4.8.3复合函数 103

4.8.4反函数 105

4.8.5集合的基数 106

习题 108

第三部分 组合数学 114

第5章 计数 114

5.1基本计数法则 114

5.1.1加法法则 114

5.1.2乘法法则 115

5.2排列与组合 117

5.2.1排列 117

5.2.2组合 118

5.2.3多重集的排列与组合 119

5.2.4二项式定理 120

5.3容斥原理 121

5.4鸽巢原理 125

习题 126

第6章 高级计数技术 128

6.1递推方程 128

6.1.1求解递推方程 130

6.1.2常系数线性齐次递推方程的求解 130

6.1.3常系数线性非齐次递推方程的求解 133

6.2生成函数 136

6.2.1牛顿二项式系数与牛顿二项式定理 136

6.2.2生成函数的定义及其性质 138

6.2.3生成函数的应用 139

6.2.4指数型生成函数 142

习题 144

第四部分 图论 148

第7章 图论 148

7.1图的基本概念 148

7.1.1无向图和有向图 148

7.1.2度的概念 150

7.1.3图的分类 151

7.1.4子图与补图 155

7.1.5图的同构 157

7.2通路与回路、连通的概念 158

7.2.1通路与回路 158

7.2.2连通的概念 160

7.3图的表示 164

7.3.1邻接表 164

7.3.2邻接矩阵 165

7.3.3可达矩阵 169

7.3.4关联矩阵 169

7.4图的运算 172

习题 172

第8章 特殊图 176

8.1欧拉图与哈密顿图 176

8.1.1欧拉图 176

8.1.2哈密顿图 178

8.2带权图 182

8.2.1旅行商问题 182

8.2.2最短路径问题 182

8.2.3中国邮路问题 184

8.3匹配和二分图 185

8.3.1匹配 185

8.3.2二分图 186

8.4平面图 189

8.4.1平面图的定义 189

8.4.2平面图的欧拉公式 191

8.4.3对偶图与着色 194

习题 197

第9章树 200

9.1树的定义和特性 200

9.2生成树 202

9.2.1生成树的定义 202

9.2.2最小生成树及其应用 203

9.3根树 205

9.3.1有向根树和有序根树 205

9.3.2有序根树的遍历 208

9.4根树的应用 209

9.4.1前缀码 209

9.4.2最优二元树和赫夫曼编码 211

9.4.3决策树 212

习题 213

第五部分 代数结构 218

第10章 代数系统 218

10.1代数系统的概念和性质 218

10.1.1二元运算及其性质 218

10.1.2代数系统和子代数 221

10.1.3代数系统的性质 222

10.1.4代数系统的分类 224

10.2代数系统的同态和同构 225

10.3半群 227

10.4群 229

10.4.1群及其基本性质 229

10.4.2子群 232

10.5循环群和置换群 233

10.5.1循环群 233

10.5.2置换群 235

10.6环和域 236

习题 238

第11章 格与布尔代数 240

11.1格 240

11.1.1格的基本概念 240

11.1.2分配格 243

11.1.3有界格和有补格 245

11.2布尔代数 246

11.2.1布尔代数的基本概念 246

11.2.2布尔表达式与布尔函数 248

11.2.3布尔代数和数字电路 249

习题 251

参考文献 254