第1章 集合论 1
1.1 集合的概念 1
1.1.1 集合的表示 1
1.1.2 集合与集合之间的关系 2
1.2 集合的运算与性质 4
1.2.1 集合的基本运算 4
1.2.2 集合的运算律 7
1.3 集合元素的计数 9
1.3.1 容斥原理 9
1.3.2 推广的容斥原理 10
1.4 集合的特征函数与范式 13
1.4.1 集合的特征函数 13
1.4.2 集合的编码 15
1.4.3 集合的成员表与范式 16
1.5 集合的卡氏积 18
综合例题 20
习题一 23
第2章 二元关系 27
2.1 二元关系 27
2.1.1 二元关系的定义 27
2.1.2 二元关系的表示 29
2.2 二元关系的运算与性质 32
2.2.1 二元关系的定义域与值域 32
2.2.2 二元关系的运算 34
2.2.3 二元关系的性质 38
2.3 闭包 40
2.4 等价关系 43
2.5 偏序关系 47
2.6 函数 51
综合例题 53
习题二 58
3.1.1 图的定义 62
3.1 图的定义和分类 62
第3章 图的基本概念 62
3.1.2 图的分类 63
3.1.3 结点的度数 64
3.1.4 子图与补图 65
3.1.5 图的同构 67
3.2 路径、回路和连通性 68
3.2.1 路径与回路 68
3.2.2 可达性 69
3.2.3 连通性 70
3.3 图的矩阵表示 72
3.3.1 邻接矩阵 72
3.3.2 可达性矩阵 73
3.4 欧拉图 75
3.5 哈密尔顿图 78
3.5.1 哈密尔顿回路与哈密尔顿路 78
3.5.2 “货郎担”问题 80
综合例题 81
习题三 84
第4章 一些特殊的图 88
4.1 树 88
4.1.1 无向树及其性质 88
4.1.2 生成树 90
4.1.3 根树及其应用 92
4.2 二部图 96
4.3 平面图与欧拉公式 99
4.3.1 平面图的概念 99
4.3.2 欧拉公式 100
4.3.3 库拉托夫斯基(Kuratowski)定理 102
4.3.4 图的着色 102
综合例题 104
习题四 106
5.1.2 数理逻辑的主要内容 109
5.1.1 什么是数理逻辑 109
5.1.3 与计算机科学的关系 109
5.1 前言 109
第5章 数理逻辑初步 109
5.1.4 本章主要内容 110
5.2 命题与连接词 110
5.2.1 命题与连接词 110
5.2.2 用符号表示命题 111
5.2.3 复合命题与逻辑连接词 111
5.3 命题公式与翻译 114
5.3.1 合式公式(wff) 115
5.3.2 命题的形式化(翻译) 115
5.4 命题公式的解释及逻辑等值式 116
5.4.1 命题公式的解释 116
5.4.2 逻辑等值式 118
5.5 重言蕴涵与逻辑推理 120
5.5.1 重言蕴涵 120
5.5.2 简单的逻辑形式推理 122
5.6.1 主析取范式 123
5.6 命题逻辑的范式及其应用 123
5.6.2 主合取范式 125
5.6.3 主析取范式与主合取范式的关系 127
5.7 谓词与量词 128
5.8 谓词公式 129
5.8.1 谓词公式的符号化 129
5.8.2 谓词公式的合式公式 132
5.8.3 谓词公式的解释 134
5.9.1 几个概念 135
5.9 数学演绎 135
5.9.2 数学演绎 136
5.10 归结证明 139
综合例题 139
习题五 143
第6章 计数 146
6.1 基本计数原理 146
6.1.1 加法原理 146
6.1.2 乘法原理 147
6.2 鸽巢原理 149
6.3 排列与组合 151
6.3.1 排列 151
6.3.2 组合 151
6.3.3 重复排列 152
6.3.4 重复组合问题 153
6.4 递推关系 154
6.4.1 齐次线性递推关系 155
6.4.2 非齐次线性递推关系 157
综合例题 158
习题六 162
第7章 代数系统和群论 164
7.1 代数系统 164
7.1.1 二元运算及性质 164
7.1.2 二元运算的性质 166
7.1.3 代数系统的零元、单位元和逆元 167
7.2 群 169
7.2.1 半群和幺半群 169
7.2.2 群 170
7.2.3 子群 173
7.2.4 置换群 175
7.3 群的同态与同构 176
7.4 环与域 179
7.5 格与布尔代数 182
7.5.1 格与格代数 182
7.5.2 布尔代数 184
综合例题 187
习题七 191
习题解答 194
习题一解答 194
习题二解答 201
习题三解答 208
习题四解答 212
习题五解答 217
习题六解答 222
习题七解答 225