离散数学

前言
第1章 预备知识 /1
1.1 集合论的初步知识 /1
1.1.1 集合的基本概念 /1
1.1.2 集合的表示 /2
习题 1.1 /3
1.2 集合的关系与运算 /3
1.2.1 集合间的基本关系 /3
1.2.2 幂集 /5
1.2.3 集合的基本运算 /5
1.2.4 文氏图 /6
1.2.5 主要的运算律 /6
1.2.6 集合运算成员表 /8
习题 1.2 /9
1.3 有限集合中元素的计数10
1.3.1 文氏图法计数 /10
1.3.2 容斥原理 /10
习题 1.3 /12
1.4 整数的基本性质 /12
1.4.1 带余除法与整除 /12
1.4.2 最大公因数和最小公倍
数 /14
1.4.3 同余 /17
习题 1.4 /17
1.5 例题解析 /17
复习题1 /19
第2章 命题逻辑 /21
2.1 命题与命题联结词21
2.1.1 命题 /21
2.1.2 命题联结词 /22
习题2.1 /26
2.2 命题公式及其分类27
2.2.1 命题公式 /27
2.2.2 公式的赋值及分类 /28
习题 2.2 /30
2.3 等价演算 /30
2.3.1 基本等价式 /30
2.3.2 等价演算 /32
习题 2.3 /34
2.4 其他常用联结词及功
能完备集 /35
2.4.1 其他常用联结词介绍 /35
2.4.2 联结词的功能完备集 /36
习题 2.4 /37
2.5 对偶与范式 /38
2.5.1 对偶 /38
2.5.2 范式 /39
2.5.3 主范式 /40
习题 2.5 /44
2.6 推理理论 /45
2.6.1 重言蕴含式 /45
2.6.2 形式证明 /46
习题 2.6 /49
2.7 命题逻辑在门电路申的
应用介绍 /50
习题 2.7 /51
2.8 例题解析 /51
复习题2 /54
第3章 谓词逻辑 /57
3.1 谓词逻辑的基本概念57
3.1.1 个体与谓词 /57
3.1.2 量词 /58
习题 3.1 /61
3.2 谓词合式公式及解释61
3.2.1 谓词公式 /62
3.2.2 谓词公式的解释 /63
3.2.3 谓词公式的类型 /64
习题 3.2 /65
3.3 谓词逻辑等值式 /66
习题 3.3 /69
3.4 谓词逻辑推理理论69
习题3.4 /73
3.5 例题解析 /74
复习题3 /78
第4章 关系 /80
4.1 有序对与笛卡尔积 /80
4.1.1 有序对 /80
4.1.2 笛卡尔积 /81
习题4.1 /82
4.2 关系及其表示 /83
4.2.1 关系的基本概念 /83
4.2.2 关系矩阵和关系图 /84
习题4.2 /85
4.3 复合关系与逆关系 /86
4.3.1 复合关系 /86
4.3.2 复合关系的性质 /87
4.3.3 关系的幂和逆关系 /88
习题 4.3 /89
4.4 关系的性质 /90
习题 4.4 /94
4.5 关系的闭包 /94
4.5.1 关系闭包的概念 /94
4.5.2 关系闭包的求法 /95
习题4.5 /100
4.6 等价关系 /100
4.6.1 集合的划分 /100
4.6.2 等价关系 /102
4.6.3 等价类 /102
习题4.6 /105
4.7 相容关系 /105
4.7.1 相容关系 /105
4.7.2 相容类 /106
习题4.7 /107
4.8 偏序关系 /107
4.8.1 偏序关系和拟序关
系 /107
4.8.2 哈斯图 /109
4.8.3 全序关系和良序关系112
习题 4.8 /113
4.9 例题解析 /113
复习题4 /120
第5章 函数 /121
5.1 函数的基本概念 /121
习题 5.1 /123
5.2 特殊函数及特征函数 /124
5.2.1 特殊函数 /124
5.2.2 特征函数 /125
习题5.2 /127
5.3 逆函数与复合函数127
5.3.1 逆函数 /127
5.3.2 复合函数 /128
习题5.3 /131
5.4 集合的势与无限集合131
5.4.1 集合的势 /131
5.4.2 可数集 /132
习题 5.4 /134
5.5 例题解析 /134
复习题5 /136
第6章 图论基础 /138
6.1 图的基本概念 /138
6.1.1 图的定义及相关概念139
6.1.2 结点的度 /140
6.1.3 完全图和补图 /142
6.1.4 子图与图的同构 /143
习题 6.1 /145
6.2 图的连通性 /146
6.2.1 通路 /146
6.2.2 无向图和有向图的连通
性 /148
6.2.3 割边和割点 /149
习题6.2 /149
6.3 图的矩阵表示 /150
6.3.1 无向图的关联矩阵 /150
6.3.2 无环有向图的关联矩阵 /151
6.3.3 有向图的邻接矩阵 /151
6.3.4 无向简单图的邻接矩阵 /153
6.3.5 有向图的可达矩阵 /153
习题 6.3 /153
6.4 欧拉图与哈密尔顿图 /154
6.4.1 欧拉图 /154
6.4.2 哈密尔顿图 /158
习题 6.4 /160
6.5 图论的应用 /161
6.5.1 最短路问题 /161
6.5.2 中国邮递员问题 /163
6.5.3 旅行售货员问题 /166
习题6.5 /168
6.6 例题解析 /168
复习题6 /171
第7章 特殊图类 /174
7.1 树 /174
7.1.1 树的定义及性质 /174
7.1.2 生成树 /176
7.1.3 最小生成树 /178
习题 7.1 /179
7.2 根树 /180
7.2.1 根树及相关概念 /180
7.2.2 二元树 /181
7.2.3 二元树的一个应用——前缀码 /183
习题 7.2 /186
7.3 二部图与匹配 /186
7.3.1 二部图的概念及性质186
7.3.2 二部图的匹配 /187
习题7.3 /188
7.4 平面图 /189
7.4.1 平面图的定义 /189
7.4.2 欧拉公式 /190
7.4.3 库拉图斯基定理 /192
习题 7.4 /193
7.5 例题解析 /194
复习题7 /196
第8章 代数系统 /198
8.1 二元运算及其性质 /198
8.1.1 运算 /198
8.1.2 二元运算的性质 /199
8.1.3 代数系统的特殊元素201
习题8.1 /203
8.2 代数系统 子代数 积代
数 /204
8.2.1 代数系统 /204
8.2.2 子代数 /205
8.2.3 积代数 /205
习题 8.2 /206
8.3 同态与同构 /206
8.3.1 同态与同构的概念206
8.3.2 满同态的性质 /207
习题8.3 /209
8.4 例题解析 /209
复习题8 /211
第9章 特殊的代数系统212
9.1 半群与独异点 /212
9.1.1 半群 /212
9.1.2 独异点 /213
习题9.1 /214
9.2 群的定义与性质 /215
9.2.1 群的定义 /215
9.2.2 群的性质 /216
9.2.3 群的同态 /217
习题9.2 /218
9.3 循环群与置换群 /218
9.3.1 循环群 /218
9.3.2 置换群 /220
习题9.3 /223
9.4 子群及其特征 /223
习题9.4 /224
9.5 陪集 正规子群和商群225
9.5.1 子群的陪集 /225
9.5.2 正规子群 /227
9.5.3 商群 /228
习题9.5 /229
9.6 环和域 /229
9.6.1 环的定义及其性质229
9.6.2 环 /231
9.6.3 整环和域 /232
习题 9.6 /234
9.7 例题解析 /234
复习题9 /235
第10章 格和布尔代数 /237
10.1 格 /237
10.1.1 格的定义 /237
10.1.2 格的对偶原理和性质239
习题 10.1 /241
10.2 格的代数定义 /241
习题 10.2 /243
1O.3 特殊的格 /243
10.3.1 分配格 /243
10.3.2 有界格和有补格 /244
10.3.3 有补分配格 /246
习题10.3 /246
10.4 布尔代数 /247
习题 10.4 /249
10.5 例题解析 /249
复习题10 /251
参考文献 /252