离散结构

第1章 命题逻辑1
1.1 命题和逻辑运算1
1.1.1 命题1
1.1.2 逻辑联结词和复合命题2
1.2 合式公式6
1.2.1 语法6
1.2.2 语义（semantics）7
1.3 逻辑等价8
1.4 范式12
1.4.1 析取范式12
1.4.2 合取范式13
1.4.3 用等价替换方法构造主范式14
1.5 联结词的完备集及应用15
1.5.1 联结词的完备集15
1.5.2 一些计算机应用16
1.6 蕴涵和演绎19
1.7 本章小结22
习题23
第2章 一阶逻辑26
2.1 谓词和量词26
2.1.1 谓词26
2.1.2 量词27
2.2 合式公式29
2.2.1 语法29
2.2.2 语义31
2.3 逻辑等价和蕴涵33
2.4 范式37
2.5 数学归纳法39
2.5.1 归纳推理和演绎推理39
2.5.2 数学归纳法41
2.5.3 数学归纳法的应用43
2.6 本章小结44
习题45第3章 集合48
3.1 集合及子集48
3.1.1 集合及其表示48
3.1.2 子集49
3.1.3 幂集50
3.1.4 多重集合51
3.2 集合上的运算51
3.2.1 集合的并51
3.2.2 集合的交52
3.2.3 集合的差53
3.2.4 集合的对称差53
3.3 集合的笛卡儿乘积54
3.3.1 有序对54
3.3.2 集合的笛卡儿乘积55
3.4 本章小结56
习题56
第4章 关系60
4.1 关系的基本概念60
4.1.1 二元关系的定义60
4.1.2 关系矩阵62
4.1.3 关系图63
4.1.4 n元关系及其应用64
4.2 复合关系和逆关系64
4.2.1 复合关系65
4.2.2 逆关系67
4.3 关系的性质69
4.4 等价关系和集合的划分72
4.4.1 等价关系73
4.4.2 集合的划分75
4.5 关系的闭包76
4.6 本章小结79
习题80
第5章 函数84
5.1 函数的基本概念84
5.2 特殊函数86
5.3 函数的运算88
5.4 一些常见的函数91
5.5 本章小结92
习题93
第6章 计数初步95
6.1 计数的两个基本原理95
6.1.1 加法原理(addition principle of counting)95
6.1.2 乘法原理(multiplication principle of counting)96
6.2 排列与组合97
6.2.1 排列97
6.2.2 组合99
6.3 鸽笼原理101
6.4 容斥原理及其应用103
6.4.1 容斥原理103
6.4.2 容斥原理的应用104
6.5 递归关系106
6.5.1 递归关系模型106
6.5.2 递归关系的基本解法109
6.6 本章小结114
习题115
第7章 图论118
7.1 图的基本概念118
7.1.1 图的定义、表示和一些术语118
7.1.2 图的同构120
7.1.3 关联矩阵和邻接矩阵122
7.1.4 子图122
7.1.5 顶点的度123
7.1.6 路和连通124
7.1.7 回路126
7.1.8 最短路问题127
7.2 欧拉图130
7.2.1 基本概念130
7.2.2 中国邮递员问题133
7.3 哈密尔顿图134
7.3.1 基本概念134
7.3.2 巡回售货员问题(TSP)137
7.4 可平面性137
7.4.1 平面图和可平面图137
7.4.2 平面图的欧拉公式及其应用139
7.4.3 可平面图的判定140
7.4.4 平面图的对偶图141
7.5 本章小结142
习题143
第8章 树147
8.1 无向树147
8.1.1 无向树的定义和基本性质147
8.1.2 生成树和最小生成树149
8.2 有向树及根树151
8.2.1 有向树及根树的定义151
8.2.2 有序树153
8.2.3 树搜索155
8.2.4 前缀码和最优树158
8.3 本章小结161
习题162
部分习题的提示与解答165
参考文献176