离散数学

第1章 命题逻辑 1

1.1 基本概念 1

1.1.1 命题 1

1.1.2 连接词 2

1.1.3 公式 3

1.1.4 重言式 5

习题 6

1.2 公式的等价关系 6

1.2.1 等价 6

1.2.2 等价代换 7

1.2.3 对偶性 8

习题 9

1.3 范式 10

1.3.1 范式 10

1.3.2 主析取范式 10

1.3.3 主合取范式 12

1.3.4 判定问题 13

习题 14

1.4 公式的蕴涵关系 14

1.4.1 蕴涵 14

.1.4.2 论证 16

习题 18

1.5 连接词的完备集合 18

习题 21

1.6 半形式化推导方法 21

1.6.1 推理规则 21

1.6.2 推导举例 22

1.6.3 间接推导方法 22

习题 23

第2章 谓词逻辑 25

2.1 谓词与量词 25

习题 28

2.2 合式公式 28

2.2.1 公式 28

2.2.2 自由变元和约束变元 29

习题 29

2.3 谓词演算中的永真公式 29

2.3.1 基本概念 29

2.3.2 谓词演算的基本永真式 30

2.3.3 谓词演算的基本永真式表 31

2.3.4 前缀范式 32

习题 32

2.4 谓词演算中的半形式化推导 32

2.4.1 推理规则 32

2.4.2 推导举例 33

2.4.3 间接推导方法 33

习题 34

第3章 集合 35

3.1 集合的基本概念 35

3.1.1 集合与元素 35

3.1.2 集合间的关系 36

3.1.3 幂集 37

习题 38

3.2 集合的运算 39

3.2.1 集合的交与并 39

3.2.2 集合的差与补 41

3.2.3 集合的对称差 42

习题 43

3.3 n元组与笛卡儿乘积 44

习题 45

第4章 二元关系 47

4.1 二元关系的概念 47

4.1.1 基本定义 47

习题 50

4.2 二元关系的基本特性 50

习题 52

4.3 合成关系与逆关系 54

4.3.1 合成关系的定义 54

4.3.2 合成关系的矩阵表示及图形表示 57

4.3.3 逆关系 58

习题 59

4.4 关系的闭包运算 60

习题 62

4.5 等价关系与相容关系 63

4.5.1 集合的覆盖与划分 63

4.5.2 等价关系与等价类 65

4.5.3 相容关系 67

习题 70

4.6 次序关系 71

4.6.1 次序关系 71

4.6.2 偏序集与哈斯图 72

习题 76

第5章 映射 79

5.1 映射的概念 79

习题 81

5.2 映射的合成 81

习题 83

5.3 逆映射 84

习题 85

5.4 集合的特征函数 85

习题 87

5.5 基数 87

5.5.1 基数的概念 87

5.5.2 可数集与不可数集 89

习题 92

第6章 图的基本概念 93

6.1 基本定义 93

习题 96

6.2 子图和图的同构 97

习题 98

6.3 通路与回路 99

习题 102

6.4 最短路算法 103

6.4.1 moore算法（bfs算法） 103

6.4.2 dijkstra算法 103

习题 104

6.5 图的连通性 105

习题 108

6.6 图的矩阵表示 108

6.6.1 邻接矩阵 109

6.6.2 可达性矩阵 111

6.6.3 无向图、多重图、带权图的

6.6.3 矩阵表示法 112

习题 112

第7章 树 115

7.1 无向树 115

习题 117

7.2 根树 118

习题 121

7.3 带权树 121

习题 124

7.4 生成树 124

习题 125

7.5 最小生成树算法 126

7.5.1 prim算法 126

7.5.2 kruskal算法 127

习题 129

第8章 特殊图 131

8.1 欧拉图 131

习题 134

8.2 哈密顿图 135

习题 138

8.3 中国邮路问题与旅行推销员问题 139

8.3.1 中国邮路问题 139

8.3.2 旅行推销员问题 140

习题 141

8.4 平面图 142

8.4.1 平面图 142

8.4.2 欧拉公式 143

8.4.3 图的可平面性 145

8.4.4 平面图的对偶图 146

8.4.5 可着色性 148

习题 151

8.5 偶图与匹配 153

8.5.1 偶图 153

8.5.2 匹配 155

习题 156

第9章 代数结构 159

9.1 二元运算 159

习题 161

9.2 半群与群 161

习题 164

9.3 子群与正规子群 166

习题 170

9.4 循环群 171

习题 173

9.5 变换群 174

习题 176

9.6 同态与同构 176

习题 182

9.7 环与域 184

9.7.1 环 184

9.7.2 子环 186

9.7.3 域 187

习题 187

第10章 格与布尔代数 191

10.1 格 191

10.1.1 格的定义 191

10.1.2 子格、格同态 194

习题 197

10.2 特殊格 199

习题 205

10.3 布尔代数 206

习题 209

第11章 组合与计数基础 211

11.1 排列与组合 211

11.1.1 排列 211

11.1.2 组合 211

11.1.3 计数的基本法则 211

11.1.4 举例 211

习题 212

11.2 递推关系 213

11.2.1 母函数 213

11.2.2 递推关系 213

习题 214

11.3 容斥原理 215

习题 216

11.4 鸽巢原理 216

习题 216

部分习题答案及提示 217

参考文献