第1章 准备知识 1
1.1集合 1
1.1.1集合的基本概念 1
1.1.2集合的基本运算和性质 2
1.1.3集合的笛卡儿积 5
1.1.4集合的计算机表示 5
1.2整数 6
1.2.1整除 6
1.2.2最大公约数和最小公倍数 8
1.2.3模运算 11
1.3序列和递推关系 12
1.3.1序列 12
1.3.2序列求和 13
1.3.3递推关系 13
1.4矩阵 15
1.4.1矩阵的概念 15
1.4.2矩阵的运算 16
1.4.3布尔矩阵 19
习题1 20
第2章 数理逻辑 24
2.1命题及联结词 24
2.1.1命题的概念 24
2.1.2命题联结词 26
2.2命题公式和分类 29
2.2.1命题变元和命题公式 29
2.2.2命题公式的赋值和真值表 30
2.2.3命题公式的类型 32
2.3等值演算与范式 33
2.3.1等价和基本等价式 33
2.3.2等值演算 35
2.3.3范式 37
2.4命题逻辑的推理理论 43
2.4.1推理的形式结构 43
2.4.2演绎法证明推理 45
2.5谓词逻辑基础 48
2.5.1谓词逻辑的基本概念 48
2.5.2谓词公式及其解释 51
2.6谓词逻辑等值式与范式 56
2.6.1谓词逻辑等值式 56
2.6.2前束范式 58
2.7谓词逻辑的推理理论 59
2.7.1有关量词的基本蕴涵式 59
2.7.2有关量词的推理规则 60
习题2 63
第3章 计数 70
3.1基本计数、排列与组合 70
3.1.1基本的计数原则 70
3.1.2排列与组合 71
3.2排列组合的进一步讨论 74
3.2.1圆周排列 74
3.2.2有重复的排列 74
3.2.3有重复的组合 76
3.3生成排列和组合 78
3.3.1生成排列 78
3.3.2生成组合 80
3.4生成函数及其应用 81
3.4.1生成函数的定义 81
3.4.2生成函数求解计数问题 82
3.4.3使用生成函数求解递推关系 84
3.5鸽巢原理 86
3.5.1一般的鸽巢原理 86
3.5.2推广的鸽巢原理 87
3.6容斥原理 88
3.6.1容斥原理 88
3.6.2容斥原理的应用 91
习题3 93
第4章 关系 96
4.1关系定义及其表示 96
4.1.1关系的基本概念 96
4.1.2二元关系的表示 97
4.2关系的运算 98
4.2.1关系的合成 98
4.2.2逆运算 100
4.3关系的性质 101
4.3.1自反性与反自反性 101
4.3.2对称性与反对称性 102
4.3.3传递关系 103
4.4 n元关系及其应用 105
4.5关系的闭包 108
4.5.1闭包的概念和求法 108
4.5.2 Warshall算法 111
4.6等价关系 112
4.6.1等价关系与等价类 112
4.6.2等价关系与划分 114
4.7偏序关系 115
4.7.1偏序关系和哈斯图 115
4.7.2极值和最值 116
4.7.3拓扑排序 117
习题4 119
第5章 布尔代数 123
5.1布尔函数 123
5.1.1布尔函数和布尔表达式 123
5.1.2布尔代数中的恒等式 125
5.2布尔函数的表示 127
5.2.1布尔函数的主析取范式 127
5.2.2函数完备性 128
5.3布尔代数的应用 129
5.3.1门电路 129
5.3.2卡诺图 130
习题5 132
第6章图 134
6.1图的基本概念 134
6.1.1无向图和有向图 134
6.1.2握手定理 138
6.1.3图的同构 139
6.2图的连通性 141
6.2.1通路和回路 141
6.2.2无向图的连通性 143
6.2.3有向图的连通性 144
6.3图的矩阵表示 144
6.3.1关联矩阵 145
6.3.2邻接矩阵 146
6.3.3有向图的可达矩阵 148
6.4一些特殊的图 149
6.4.1二部图 149
6.4.2欧拉图 150
6.4.3哈密尔顿图 152
6.5带权图的最短路径 155
6.5.1 Dijkstra算法 155
6.5.2 Floyd算法 157
6.5.3旅行商问题 159
6.6平面图 160
6.6.1平面图的定义 160
6.6.2欧拉公式 161
6.6.3库拉图斯基定理 162
习题6 164
第7章树 167
7.1无向树的概念 167
7.1.1无向树的定义 167
7.1.2无向树的应用例子 168
7.2生成树 169
7.2.1生成树的定义 169
7.2.2求最小生成树的算法 170
7.3根树及应用 172
7.3.1根树的定义及应用 172
7.3.2最优二叉树和Huffman编码 174
7.3.3二叉树的遍历 177
习题7 179
参考文献 181