第1章 集合 1
1.1集合的基本概念 1
1.1.1集合的表示方法 1
1.1.2子集、空集和全集 2
1.1.3幂集 3
1.1.4例题选解 4
1.2集合的基本运算 5
1.2.1交运算、并运算和取补运算 5
1.2.2减运算和对称差运算 10
1.2.3对偶原理 14
1.2.4例题选解 15
习题1 19
第2章 二元关系与函数 22
2.1二元关系的基本概念 22
2.1.1笛卡儿乘积与二元关系的定义 23
2.1.2二元关系的3种表示方法 25
2.1.3关系的基本类型 27
2.1.4例题选解 34
2.2复合关系、逆关系和关系的闭包运算 36
2.2.1复合关系 36
2.2.2逆关系 39
2.2.3关系的闭包运算 40
2.2.4例题选解 42
2.3等价关系与偏序关系 44
2.3.1等价关系与划分 44
2.3.2偏序关系 49
2.3.3例题选解 53
2.4函数 55
2.4.1函数的定义 55
2.4.2特殊函数 57
2.4.3复合函数与逆函数 59
2.4.4例题选解 62
习题2 64
第3章 命题逻辑 70
3.1命题逻辑的基本概念 70
3.1.1命题和命题变元 70
3.1.2命题联结词 71
3.1.3真值表和逻辑等价 76
3.1.4例题选解 80
3.2范式和主范式 82
3.2.1析取范式和主析取范式 82
3.2.2合取范式和主合取范式 87
3.2.3例题选解 90
3.3永真蕴含式 94
3.3.1永真蕴含式的定义 94
3.3.2永真蕴含式的性质 96
3.3.3例题选解 97
3.4推理理论 99
3.4.1前提和有效结论 99
3.4.2直接证明法 101
3.4.3间接证明法 102
3.4.4例题选解 104
习题3 107
第4章 谓词逻辑 113
4.1谓词和量词 113
4.1.1谓词与命题变元 113
4.1.2量词 116
4.1.3谓词合式 120
4.1.4约束元和自由元 121
4.1.5例题选解 123
4.2等价式与永真蕴含式 125
4.2.1等价式 125
4.2.2前束范式 128
4.2.3永真蕴含式 129
4.2.4例题选解 131
4.3谓词演算的推理理论 131
4.3.1量词的指定和推广规则 132
4.3.2例题选解 134
习题4 136
第5章 图论 139
5.1图的基本概念 139
5.1.1无向图与有向图 139
5.1.2子图 141
5.1.3图中顶点的度数 142
5.1.4图的同构 143
5.1.5完全图与补图 144
5.1.6图的矩阵表示 146
5.1.7例题选解 147
5.2通路与赋权图的最短通路 150
5.2.1通路与回路 150
5.2.2图的连通性 151
5.2.3赋权图的最短通路 153
5.2.4例题选解 161
5.3欧拉图与哈密顿图 164
5.3.1欧拉图 164
5.3.2哈密顿图 168
5.3.3例题选解 172
5.4二部图和平面图 177
5.4.1二部图 177
5.4.2平面图 179
5.4.3例题选解 184
5.5树 187
5.5.1无向树 187
5.5.2有向树 189
5.5.3前缀码与最优树 192
5.5.4例题选解 197
习题5 199
第6章 组合计数初步 205
6.1包含排斥原理与鸽舍原理 205
6.1.1包含排斥原理 205
6.1.2鸽舍原理 208
6.1.3例题选解 209
6.2递推关系 212
6.3常系数线性递推关系 212
6.3.1齐次常系数线性递推关系 213
6.3.2非齐次常系数线性递推关系 217
6.3.3例题选解 223
6.4生成函数 227
6.4.1生成函数的定义 227
6.4.2生成函数与递推关系 228
6.4.3例题选解 232
习题6 238
第7章 代数系统简介 240
7.1代数系统的基本概念 240
7.1.1代数系统的定义 240
7.1.2特殊运算与特殊元素 243
7.1.3同构 248
7.1.4例题选解 250
7.2半群与独异点 252
7.2.1半群与子半群 252
7.2.2独异点与子独异点 254
7.2.3例题选解 255
7.3群 256
7.3.1群的定义和性质 256
7.3.2子群 260
7.3.3陪集和拉格朗日定理 265
7.3.4循环群 268
7.3.5群码 272
7.3.6例题选解 276
7.4环、域和格 279
7.4.1环 279
7.4.2域 282
7.4.3格 284
7.4.4例题选解 286
习题7 287
部分习题解答 292
参考文献 306