第1章 集合论基础 1
1.1 集合的概念及运算 1
1.1.1 集合的基本概念 1
1.1.2 集合间的关系与子集 3
1.1.3 集合运算 4
1.1.4 集合的笛卡儿积 7
1.2 集合的归纳定义 8
1.2.1 集合的归纳定义 8
1.2.2 归纳法证明 10
1.3 习题 13
第2章 整数的性质 16
2.1 整除及其取整 16
2.1.1 整除及其性质 16
2.1.2 质数和合数 18
2.2 最大公因子 20
2.2.1 基本概念和性质 20
2.2.2 辗转相除法 22
2.2.3 尼考曼彻斯法 24
2.3 最小公倍数 24
2.4 同余 25
2.4.1 同余及其性质 25
2.4.2 一次同余式 27
2.5 习题 28
第3章 矩阵初步 30
3.1 行列式 30
3.2 矩阵的定义 34
3.3 矩阵的运算及性质 35
3.3.1 矩阵的基本运算及性质 35
3.3.2 矩阵的转置 38
3.3.3 矩阵的逆 39
3.4 布尔矩阵及其运算 42
3.5 习题 44
第4章 组合论原理 47
4.1 两个基本原理 47
4.2 排列与组合 48
4.2.1 排列与组合 48
4.2.2 排列、组合的进一步讨论 51
4.2.3 排列与组合的生成 53
4.3 组合数恒等式 54
4.4 容斥原理 55
4.5 鸽笼原理 58
4.6 递推 61
4.6.1 递推的概念 61
4.6.2 递推求解 62
4.7 习题 67
第5章 命题逻辑 70
5.1 命题与逻辑联结词 70
5.1.1 命题 70
5.1.2 逻辑联结词 71
5.1.3 命题公式 74
5.1.4 语句形式化 75
5.2 逻辑等价式与逻辑蕴涵式 76
5.2.1 重言式与矛盾式 76
5.2.2 公式的等价与蕴涵 77
5.2.3 对偶原理 80
5.3 范式 82
5.3.1 析取范式与合取范式 82
5.3.2 主析取范式与主合取范式 84
5.4 习题 87
第6章 一阶谓词逻辑 90
6.1 基本概念 90
6.1.1 个体与个体域 90
6.1.2 谓词 91
6.1.3 量词 92
6.1.4 谓词公式 93
6.1.5 语句形式化 94
6.2 谓词演算永真式 97
6.2.1 谓词公式的真值规定 97
6.2.2 一些特殊的谓词永真式 98
6.2.3 永真式的几个基本原理 101
6.3 习题 103
第7章 关系 106
7.1 二元关系 106
7.1.1 关系及其表示 106
7.1.2 关系的运算 109
7.1.3 关系的性质 114
7.2 等价关系 117
7.2.1 集合的划分 117
7.2.2 等价关系与等价类 118
7.2.3 等价关系与划分 120
7.3 序关系 121
7.3.1 序关系 121
7.3.2 良序集 124
7.4 习题 125
第8章 函数 130
8.1 函数的基本概念 130
8.2 函数的合成 132
8.3 函数的性质 135
8.4 函数的逆 138
8.5 习题 142
第9章 图 146
9.l 图的基本概念 146
9.1.1 图的定义 147
9.1.2 结点的度 148
9.1.3 子图与补图 150
9.1.4 图的同构 15
9.2 路径、回路及连通性 152
9.2.1 路径与回路 152
9.2.2 无向图的连通性 153
9.2.3 有向图的连通性 155
9.3 图的矩阵表示 156
9.3.1 邻接矩阵 156
9.3.2 路径矩阵与可达性矩阵 159
9.4 习题 161
第10章 特殊图 164
10.1 欧拉图与欧拉路径 164
10.2 哈密顿图与哈密顿通路 167
10.3 二分图 170
10.3.1 二分图的基本概念 170
10.3.2 匹配 171
10.4 平面图 175
10.4.1 平面图的基本概念 175
10.4.2 欧拉公式 177
10.5 树 180
10.5.1 树的基本概念 181
10.5.2 生成树 182
10.5.3 根树 185
10.6 习题 191
参考文献 195