离散数学PDF电子书下载

第1章 集合 1

1.1 集合的基本概念 1

1.1.1 集合的表示方法 1

1.1.2 子集 2

1.1.3 全集和补集 3

1.1.4 幂集 3

1.2 集合的基本运算 5

1.2.1 交和并 5

1.2.2 差和对称差 8

习题 14

第2章 二元关系与函数 17

2.1 二元关系的基本概念 17

2.1.1 引言 17

2.1.2 笛卡儿乘积与二元关系的定义 18

2.1.3 二元关系的3种表示方法 19

2.1.4 二元关系的基本类型 22

2.2 等价关系与偏序关系 26

2.2.1 等价关系与划分 26

2.2.2 偏序关系 32

2.3 复合关系与逆关系 36

2.3.1 复合关系 36

2.3.2 逆关系 40

2.3.3 关系的闭包运算 42

2.4 函数 45

2.4.1 函数的基本概念 45

2.4.2 特殊函数 47

2.4.3 复合函数与逆函数 49

习题 53

第3章 组合计数初步 58

3.1 容斥原理和鸽舍原理 58

3.1.1 容斥原理 58

3.1.2 鸽舍原理 61

3.2 递推关系 63

3.2.1 递推关系的基本概念 63

3.2.2 齐次常系数线性递推关系 65

3.2.3 非齐次常系数线性递推关系 69

3.2.4 生成函数 80

习题 88

第4章 图论 92

4.1 图的基本概念 92

4.1.1 图的基本术语 92

4.1.2 图的矩阵表示 94

4.1.3 图中顶点的度数 95

4.1.4 子图与图的同构 97

4.1.5 完全图与补图 99

4.2 通路与赋权图的最短通路 103

4.2.1 通路与回路 103

4.2.2 图的连通性 104

4.2.3 赋权图的最短通路 109

4.3 树 114

4.3.1 无向树 114

4.3.2 有向树 119

4.3.3 前缀码与最优树 121

4.4 欧拉图与哈密顿图 126

4.4.1 欧拉图 126

4.4.2 哈密顿图 130

4.5 二部图和平面图 135

4.5.1 二部图 135

4.5.2 平面图 138

习题 145

第5章 命题逻辑 152

5.1 命题逻辑的基本概念 152

5.1.1 命题 152

5.1.2 命题联结词 153

5.1.3 命题公式 156

5.1.4 命题公式的真值表 158

5.1.5 永真式、永假式和可满足式 159

5.2 逻辑等价 161

5.2.1 逻辑等价 161

5.2.2 代换规则 162

5.2.3 对偶原理 165

5.2.4 联结词的完备集 165

5.3 范式和主范式 166

5.3.1 析取范式和合取范式 166

5.3.2 主析取范式和主合取范式 167

5.4 逻辑蕴涵 177

5.4.1 逻辑蕴涵的定义 177

5.4.2 逻辑蕴涵的性质 178

5.5 推理理论 181

5.5.1 前提和有效结论 181

5.5.2 直接证明法 183

5.5.3 间接证明法 183

习题 188

第6章 谓词逻辑 194

6.1 谓词逻辑的基本概念 195

6.1.1 个体词与谓词 195

6.1.2 量词 196

6.1.3 谓词公式 202

6.1.4 约束变元和自由变元 203

6.2 逻辑等价与逻辑蕴涵 205

6.2.1 永真式、永假式和可满足式 205

6.2.2 逻辑等价式和逻辑蕴涵式 205

6.2.3 前束范式 211

6.3 推理理论 212

习题 217

第7章 代数系统简介 220

7.1 代数系统的基本概念 220

7.1.1 代数系统的定义 220

7.1.2 特殊运算与特殊元素 223

7.1.3 同构 230

7.2 半群与独异点 232

7.2.1 半群与子半群 233

7.2.2 独异点与子独异点 236

7.3 群 238

7.3.1 群的定义和性质 238

7.3.2 子群 245

7.3.3 循环群 250

7.3.4 陪集和拉格朗日定理 253

7.3.5 群码 256

7.4 环和域 260

7.4.1 环 260

7.4.2 域 263

7.5 格 266

7.5.1 格的定义 266

7.5.2 格和偏序集 267

7.5.3 特殊格 270

习题 275

参考文献 281