离散数学讲义PDF电子书下载

第一章 数理逻辑基础 1

第一节 命题逻辑 1

1.1.1 命题与逻辑联结词 1

1.1.2 命题公式与真值表 5

1.1.3 永真式和永假式 8

1.1.4 公式间的等价关系 10

3.1.3 图的连通性 11

1.1.5 公式间的蕴涵关系 16

1.1.6 其它联结词 18

1.1.7 公式的范式 22

1.1.8 命题演算的推理理论 29

习题 34

第二节 一阶谓词逻辑 38

1.2.1 谓词与个体 39

1.2.2 量词与全总个体域 41

1.2.3 谓词公式 43

1.2.4 自由（个体）变元和约束（个体）变元 45

1.2.5 谓词逻辑中的永真公式 46

1.2.6 含有量词的等价式和蕴涵式 47

1.2.7 合式谓词公式的范式 51

1.2.8 谓词逻辑的推理理论 53

1.2.9 谓词演算在程序正确性证明中的应用举例 55

习题 57

第二章 集合论 61

第一节 集合论基础 61

2.1.1 集合及其运算 61

2.1.2 集合成员表 66

2.1.3 自然数集合与数学归纳法 67

2.1.4 笛卡尔乘积 69

习题 71

2.2.1 关系的基本概念 74

第二节 二元关系 74

2.2.2 复合关系与逆关系 77

2.2.3 关系的闭包运算 83

2.2.4 等价关系与划分 88

2.2.5 相容关系 91

2.2.6 次序关系 93

习题 97

第三节 函数 100

2.3.1 函数的基本概念 100

2.3.2 复合函数与逆函数 104

2.3.3 集合的特征函数 106

2.3.4 集合的基数 108

习题 114

3.1.1 图与子图 117

第三章 图论 117

第一节 图的基本概念 117

3.1.2 图的运算 121

习题 124

第二节 图的矩阵表示 126

3.2.1 邻接矩阵 126

3.2.2 可达性矩阵 129

3.2.3 关联矩阵 134

习题 136

第三节 路径与回路 138

3.3.1 最短路径 138

3.3.2 最优路径与关键路径 143

3.3.3 欧拉回路 146

3.3.4 哈密顿回路 149

习题 153

第四节 树与割集 155

3.4.1 无向树 155

3.4.2 有向树 161

3.4.3 割集 168

习题 171

第五节 平面图与偶图 174

3.5.1 平面图 174

3.5.2 对偶图 177

3.5.3 偶图 180

习题 183

第一节 代数系统 186

4.1.1 集合中的代数运算 186

第四章 代数结构 186

4.1.2 代数系统的基本概念 189

4.1.3 同构与同态 192

4.1.4 同余关系 198

4.1.5 商代数与积代数 201

习题 204

第二节 群、环和域 206

4.2.1 半群和含幺半群 207

4.2.2 群 212

4.2.3 变换群与循环群 215

4.2.4 子群 222

4.2.5 环 231

4.2.6 域 235

习题 237

4.3.1 格—偏序集合 241

第三节 格布尔代数 241

4.3.2 格—代数系统 245

4.3.3 几种特殊格 249

4.3.4 布尔代数 254

习题 265

第五章 组合学导论 269

第一节 排列与组合 269

5.1.1 排列 269

5.1.2 组合 274

5.1.3 集合的分割 276

习题 278

第二节 鸽巢原理与容斥原理 279

5.2.1 鸽巢原理 279

5.2.2 容斥原理 281

习题 284

5.3.1 Pascal公式 285

5.3.2 二项式定理及恒等式 287

5.3.3 二项式系数的单峰性质 290

5.3.4 多项式定理 291

习题 292

第四节 母函数与递推关系 293

5.4.1 母函数与递推关系 293

5.4.2 母函数与递推关系举例 301

5.4.3 catalan数 308

习题 310

附录： 310

参考书目 312

第三节 二项式系数 385