离散数学

第一编 数理逻辑 3

第1章 命题逻辑的基本概念 3

1.1 命题与命题联结词 3

1.2 命题公式及其赋值 9

习题一 15

第2章 命题逻辑等值演算 17

2.1 等值式 17

2.2 命题公式的标准形——范式 25

2.3 联结词的完备集 37

习题二 41

3.1 推理的形式结构 43

第3章 命题逻辑的推理理论 43

3.2 自然推理系统P 48

习题三 56

第4章 一阶逻辑基本概念 58

4.1 一阶逻辑的符号化 58

4.2 一阶逻辑公式及解释 64

习题四 71

第5章 一阶逻辑等值演算与推理 74

5.1 一阶逻辑等值式与置换规则 74

5.2 一阶逻辑公式的标准形——前束范式 79

5.3 一阶逻辑推理理论 81

习题五 87

6.1 集合的基本概念 91

第6章 集合代数 91

第二编 集合论 91

6.2 集合的运算 95

6.3 集合恒等式 101

习题六 106

第7章 二元关系 112

7.1 有序对与笛卡尔积 112

7.2 二元关系 115

7.3 关系的运算 118

7.4 关系的性质 128

7.5 关系的闭包 135

7.6 等价关系与划分 140

7.7 偏序关系 145

习题七 149

第8章 函数 155

8.1 函数的定义与性质 155

8.2 函数的复合与反函数 162

习题八 167

第9章 集合基数 170

9.1 集合的等势与优势 170

9.2 集合的基数 178

习题九 183

第三编 代数结构 187

第10章 代数结构 187

10.1 二元运算及其性质 187

10.2 代数系统 193

习题十 195

第11章 半群与群 200

11.1 半群与独异点 200

11.2 群的定义与性质 203

11.3 子群 209

11.4 群的分解 211

11.5 正规子群与商解 217

11.6 群的同态与同构 221

11.7 循环群与置换群 228

习题十一 237

第12章 环与域 239

12.1 环的定义与性质 239

12.2 整环与域 243

习题十二 245

第13章 格与布尔代数 247

13.1 格的定义与性质 247

13.2 子格与格同态 252

13.3 分配格与有补格 257

13.4 布尔代数 262

习题十三 268

第四编 图论 275

第14章 图的基本概念 275

14.1 图 275

14.2 通路、回路、图的连通性 289

14.3 图的矩阵表示 293

习题十四 298

第15章 欧拉图与哈密顿图 300

15.1 欧拉图 301

15.2 哈密顿图 302

习题十五 306

第16章 树 308

16.1 无向树及其性质 308

16.2 生成树 312

习题十六 316

第17章 平面图及图的着色 317

17.1 平面图的基本概念 317

17.2 欧拉公式 321

17.3 平面图的判断 325

17.4 平面图的对偶图 328

17.5 图中顶点的着色 331

17.6 地图的着色与平面图的点着色 332

17.7 边着色 334

17.8 图的强边染色、邻强边染色、全染色、邻点可区别全染色 336

习题十七 338

第18章 支配集、覆盖集、独立集与匹配 340

18.1 支配集、点覆盖集、点独立集 340

18.2 边覆盖集与匹配 342

18.3 二部图中的匹配 347

习题十八 349

部分习题参考答案 351

参考文献 396