第1章 集合 1
1.1 集合的基本概念 1
1.1.1 集合的定义 1
1.1.2 集合与元素的关系 2
1.1.3 集合与集合的关系 3
1.1.4 几种特殊集合 3
1.1.5 集合的基数 4
1.2 集合的运算 5
1.2.1 并运算 5
1.2.2 交运算 5
1.2.3 补运算 5
1.2.4 差运算 6
1.2.5 对称差运算 6
1.2.6 集合间的等值式 6
1.3 有限集合中元素的计数 8
1.3.1 文氏图法计数 8
1.3.2 容斥原理法计数 9
1.4 集合在信息学科中的应用 10
本章总结 11
习题 12
兴趣阅读 14
第2章 关系 17
2.1 关系的概念 17
2.1.1 序偶 17
2.1.2 笛卡儿积 18
2.1.3 关系的定义 18
2.1.4 关系的定义域与值域 20
2.1.5 关系的表示方法 20
2.2 关系的运算 22
2.2.1 关系的集合运算 22
2.2.2 关系的逆运算 23
2.2.3 关系的复合运算 23
2.2.4 关系的幂运算 24
2.3 关系的性质 26
2.3.1 自反性与反自反性 26
2.3.2 对称性与反对称性 27
2.3.3 传递性 29
2.4 关系的闭包 30
2.5 等价关系 32
2.5.1 等价关系的定义 32
2.5.2 等价关系的划分 34
2.6 偏序关系 36
2.6.1 偏序的定义及表示 36
2.6.2 偏序关系的哈斯图 36
2.6.3 偏序关系的特殊元素 37
2.6.4 全序和良序 38
2.7 关系的应用 38
本章总结 39
习题 40
兴趣阅读 43
第3章 函数 45
3.1 函数的定义与类型 45
3.1.1 函数的定义 45
3.1.2 函数的类型 47
3.2 函数的运算 49
3.2.1 函数的复合运算 49
3.2.2 函数的逆运算 50
3.3 函数的应用 51
本章总结 53
习题 53
兴趣阅读 55
第4章 命题逻辑 57
4.1 命题与联结词 57
4.1.1 命题 57
4.1.2 联结词 58
4.1.3 语句的符号化 61
4.2 命题公式及其分类 62
4.2.1 命题公式与真值表 62
4.2.2 命题公式的分类 64
4.3 命题公式的等值 65
4.3.1 等值式 65
4.3.2 用真值表判断公式的等值 65
4.3.3 等值演算 65
4.3.4 对偶式 67
4.3.5 等值演算的应用 68
4.4 范式 69
4.4.1 析取范式和合取范式 69
4.4.2 主析取范式与主合取范式 70
4.4.3 主范式的应用 73
4.5 推理理论 76
4.5.1 命题的蕴涵关系 76
4.5.2 形式证明 77
4.6 命题逻辑的应用 81
本章总结 81
习题 82
兴趣阅读 85
第5章 谓词逻辑 87
5.1 谓词逻辑的基本概念 87
5.1.1 个体词 87
5.1.2 谓词 88
5.1.3 量词 89
5.1.4 命题符号化 90
5.2 谓词公式与类型 91
5.2.1 谓词公式 91
5.2.2 谓词公式的解释 93
5.2.3 谓词公式的类型 94
5.3 谓词逻辑等值式 94
5.3.1 基本等值式 94
5.3.2 基本规则 96
5.3.3 等值演算 96
5.4 谓词逻辑的前束范式 97
5.5 谓词演算的推理规则 98
5.5.1 推理定律 98
5.5.2 推理规则 99
5.6 谓词逻辑的应用 103
本章总结 104
习题 105
兴趣阅读 106
第6章 图论 109
6.1 图的基本概念 109
6.1.1 图的定义 109
6.1.2 邻接与关联 110
6.1.3 顶点的度 111
6.1.4 图的分类 112
6.1.5 图的同构 114
6.2 图的连通性 115
6.2.1 通路与回路 115
6.2.2 图的连通性 116
6.3 图的矩阵表示 120
6.3.1 图的关联矩阵 120
6.3.2 图的邻接矩阵 121
6.3.3 图的可达矩阵 123
6.4 图的应用 125
本章总结 127
习题 128
兴趣阅读 130
第7章 特殊图 131
7.1 欧拉图 131
7.2 哈密顿图 134
7.3 二部图 137
7.4 树 140
7.4.1 无向树 140
7.4.2 有向树 142
7.5 特殊图的应用 143
本章总结 144
习题 145
兴趣阅读 146
第8章 代数系统 148
8.1 代数系统的概念 148
8.1.1 代数运算 148
8.1.2 代数系统 149
8.2 代数运算的性质 150
8.2.1 基本性质 150
8.2.2 特殊元素 151
8.3 半群和群 153
8.3.1 半群 153
8.3.2 群 153
8.3.3 特殊群 155
8.4 环和域 158
8.4.1 环 158
8.4.2 域 159
8.5 格与布尔代数 160
8.5.1 格 160
8.5.2 几种特殊格 162
8.5.3 布尔代数 164
8.6 代数系统的应用 165
本章总结 165
习题 166
兴趣阅读 169
参考文献 172