第1章 集合论初步 1
1.1 集合的概念 1
1.1.1 集合 1
目录 1
1.1.2 集合的表示 2
1.1.3 集合上的包含关系 3
1.1.4 特殊集合 4
习题1.1 5
1.2.1 集合交、并和补的运算 6
1.2 集合的运算 6
1.2.2 集合交、并和补运算的性质 7
1.2.3 其他运算及其性质 7
1.2.4 利用集合的编码表示运算 9
习题1.2 10
1.3 有穷集合的计数 11
习题1.3 13
第2章 关系 15
2.1.1 笛卡儿积 16
2.1 集合的笛卡儿积和二元关系的概念 16
2.1.2 二元关系的概念 17
2.1.3 二元关系的表示 17
习题2.1 20
2.2 二元关系的特性 20
习题2.2 23
2.3 二元关系运算 23
2.3.1 交、并和补运算 23
2.3.2 逆运算和复合运算 24
2.3.3 投影、选择和联系的运算 27
2.3.4 闭包 28
习题2.3 32
2.4 等价关系和相容关系 33
2.4.1 等价关系 33
2.4.2 模m同余关系 35
2.4.3 等价关系和划分 36
2.4.4 相容关系 36
习题2.4 37
2.5 序关系 38
2.5.1 偏序关系 38
2.5.2 偏序集中具有特殊位置的元素 41
2.5.3 拟序、全序和良序 42
习题2.5 44
2.6 函数 45
2.6.1 函数的概念 45
2.6.2 特殊函数 46
2.6.3 函数的逆和复合 49
习题2.6 50
第3章 代数系统 52
3.1.1 运算 53
3.1 运算和代数系统 53
3.1.2 运算性质 54
3.1.3 运算性质示例 57
3.1.4 代数系统 59
习题3.1 60
3.2 半群和群 61
3.2.1 半群、含幺半群和群 61
3.2.2 交换半群、交换独异点和交换群 62
3.2.3 幂 63
3.2.4 生质 64
习题3.2 65
3.3.1 子代数 66
3.3 子半群和子群 66
3.3.2 子半群 67
3.3.3 子群 68
习题3.3 69
3.4 循环群 69
3.4.1 元素周期 70
3.4.2 循环群概念 70
3.4.3 循环群和循环子群的性质 71
3.5.1 概念 73
习题3.4 73
3.5 置换群 73
3.5.2 伯恩赛德定理 76
习题3.5 78
3.6 同态和同构初步 78
3.6.1 同态和同构定义 78
3.6.2 代数系统中关于同态与同构的性质 80
3.6.3 同态核 81
3.6.4 同余关系 82
习题3.6 83
3.7 环和域 84
3.7.1 环 84
3.7.2 整环、除环和域 87
习题3.7 93
第4章 格和布尔代数 94
4.1 格 94
4.1.1 偏序集中的格 94
4.1.2 偏序集中与格有关的性质 95
4.1.3 对偶原理 97
4.1.4 格的代数性质 98
4.1.5 子格和格同态 101
习题4.1 104
4.2 格的分类 104
4.2.1 有界格 104
4.2.2 有补格 105
4.2.3 分配格 106
4.2.4 有补分配格 108
习题4.2 110
第5章 命题逻辑 111
5.1.1 命题 112
5.1 命题符号化 112
5.1.2 命题的联结词 113
5.1.3 合式公式 116
5.1.4 真值函数 116
5.1.5 全功能集 117
习题5.1 118
5.2 等值演算和范式 121
5.2.1 恒等式和永真蕴涵式 121
5.2.2 范式 123
习题5.2 126
5.3 逻辑推理 128
5.3.1 推理的形式结构 128
5.3.2 推理系统 128
5.3.3 证明方法 130
习题5.3 132
5.4 例题与分析 133
第6章 谓词逻辑 140
6.1 谓词和量词 140
6.1.1 个体词和谓词 141
6.1.2 量词 142
习题6.1 143
6.2 谓词逻辑公式及解释 144
习题6.2 146
6.3 等价值蕴涵和前束范式 147
习题6.3 150
6.4 谓词的逻辑推理理论 151
习题6.4 154
第7章 图论初步 156
7.1.1 定义 157
7.1 图的基本概念 157
7.1.2 顶点的度 158
7.1.3 特殊的图 159
7.1.4 图的同构 161
习题7.1 162
7.2 通路、回路和连通性 163
7.2.1 通路和回路 163
7.2.2 无向图的连通性 164
7.2.3 有向图的连通性 166
7.2.4 图的连通性和等价关系 167
习题7.2 169
7.3 图的矩阵表示 170
习题7.3 176
第8章 典型的图及其应用 177
8.1 无向树和生成树 177
习题8.1 182
8.2 有向树及其应用 183
8.2.1 有向树的概念 183
8.2.2 根树转化成二元树 186
8.2.3 最优树 187
8.2.4 前缀码 188
8.2.5 树的遍历 190
习题8.2 191
8.3 欧拉图和哈密顿图 192
习题8.3 195
8.4 平面图和图的着色 195
习题8.4 200
附录A 部分习题参考答案 201
附录B 符号表 218
参考文献 221