离散数学

第一部分 数理逻辑 3

第1章 命题逻辑 3

1.1 命题的基本概念 3

1.1.1 命题及分类 3

1.1.2 逻辑联结词 4

1.2 命题公式及类型 6

1.2.1 命题公式及赋值 6

1.2.2 命题公式类型与真值表 8

1.3 命题公式的等价演算 12

1.3.1 命题公式的等价式 12

1.3.2 命题公式的等价演算 14

1.3.3 等价演算的实例应用 16

1.4 命题公式的范式及应用 17

1.4.1 析取范式与合取范式 17

1.4.2 主析取范式与主合取范式 19

1.4.3 主范式的实例应用 22

1.5 全功能逻辑联结词组 24

1.6 命题公式的推理及证明 25

1.6.1 推理基本定义 26

1.6.2 推理的证明方法 26

1.6.3 推理演算的实例应用 30

习题1 31

第2章 谓词逻辑 36

2.1 谓词逻辑基本概念 36

2.1.1 谓词逻辑三要素 36

2.1.2 多元谓词命题符号化 38

2.2 谓词公式及类型 40

2.2.1 谓词公式 40

2.2.2 谓词公式的类型 41

2.3 谓词公式的等价演算 43

2.4 谓词公式的前束范式 45

2.5 谓词公式的推理 46

习题2 49

第二部分 集合论 55

第3章 集合 55

3.1 集合的基本概念 55

3.1.1 集合与元素的基本概念 55

3.1.2 集合与集合间的关系 56

3.2 集合的运算 58

3.3 集合中元素的计数 62

习题3 66

第4章 二元关系与函数 69

4.1 集合的笛卡儿积 69

4.2 二元关系 71

4.3 关系的性质 76

4.4 关系的闭包 80

4.5 等价关系与划分 85

4.6 偏序关系 88

4.7 函数的定义与性质 90

4.8 函数的复合与反函数 94

习题4 97

第三部分 图论部分 103

第5章 图论 103

5.1 图的基本概念 103

5.1.1 图的定义及相关概念 103

5.1.2 结点的度 104

5.1.3 完全图和补图 106

5.1.4 子图与图的同构 107

5.2 图的连通性 109

5.2.1 通路和回路 110

5.2.2 图的连通性 111

5.2.3 无向图的连通度 112

5.3 图的矩阵表示 113

5.3.1 无向图的关联矩阵 114

5.3.2 有向图的关联矩阵 114

5.3.3 有向图的邻接矩阵 115

5.3.4 有向图的可达矩阵 116

5.4 最短路径与关键路径 116

5.4.1 问题的提出 116

5.4.2 最短路径 117

5.4.3 关键路径 120

5.5 欧拉图与哈密顿图 122

5.5.1 欧拉图 122

5.5.2 哈密顿图 125

5.6 平面图 129

5.6.1 平面图的定义 130

5.6.2 欧拉公式 131

5.6.3 平面图着色 134

习题5 137

第6章 树 141

6.1 树的性质 141

6.2 生成树与最小生成树 143

6.2.1 生成树 143

6.2.2 最小生成树 144

6.3 根树及其应用 146

6.3.1 有向树 146

6.3.2 根树的分类 147

6.3.3 根树的应用 149

习题6 152

第四部分 代数系统 157

第7章 排列组合 157

7.1 两个基本法则 157

7.2 排列与组合 158

7.2.1 相异元素不允许重复的排列数和组合数 158

7.2.2 相异元素允许重复的排列问题 159

7.2.3 不尽相异元素的全排列 160

7.2.4 相异元素不允许重复的圆排列 161

7.2.5 相异元素允许重复的组合问题 162

7.2.6 不尽相异元素任取r个的组合问题 163

习题7 167

第8章 代数系统 168

8.1 二元运算及其性质 168

8.2 代数系统概述 173

习题8 176

第9章 典型代数系统 178

9.1 半群与独异点 178

9.2 群的定义与性质 181

9.2.1 群的定义 181

9.2.2 Klein四元群 182

9.2.3 群的直积 182

9.2.4 群论中常用的概念或术语 182

9.2.5 群中元素的n次幂 183

9.2.6 群中元素的阶 183

9.2.7 群的性质——群的幂运算规则 184

9.2.8 消去律 185

9.3 子群 186

9.4 循环群与置换群 187

9.5 陪集与拉格朗日定理 189

9.6 同态与同构 194

9.7 环与域 199

9.8 格 204

习题9 212

参考文献 216