第1章 集合论 1
1.1 集合的概念与运算 2
1.1.1 集合的概念和表示法 2
1.1.2 集合论的公理系统 2
1.1.3 集合相等与包含 3
1.1.4 空集与基础集 3
1.1.5 无限集与幂集 3
1.1.6 集合的并集 4
1.1.7 集合的交集 4
1.1.8 集合的补集 5
1.1.9 集合的对称差集 5
1.2 关系的概念 6
1.2.1 笛卡儿积 6
1.2.2 关系 7
1.2.3 恒同关系 8
1.2.4 关系图与关系矩阵 8
1.3 关系的性质与运算 9
1.3.1 关系的性质 9
1.3.2 关系的运算 12
1.3.3 复合关系 12
1.3.4 逆关系 13
1.3.5 关系的相关运算 14
1.4 关系的闭包 16
1.4.1 闭包的概念 16
1.4.2 闭包的计算 16
1.4.3 传递闭包的Warshall计算方法 18
1.5 等价关系 21
1.5.1 集合的覆盖与划分 21
1.5.2 等价关系 21
1.5.3 相容关系 22
1.6 序关系 24
1.6.1 偏序关系 24
1.6.2 盖住关系 24
1.6.3 哈斯图 24
1.6.4 最（极）大（小）元 25
1.6.5 上（下）（确）界 26
1.6.6 全序集与良序集 26
1.7 函数 27
1.7.1 函数的概念 27
1.7.2 特殊的函数 28
1.7.3 逆函数 29
1.7.4 复合函数 30
1.8 基数 31
1.8.1 基数的概念 31
1.8.2 可数集 32
集合论习题 33
第2章 数理逻辑 37
2.1 命题与联结词 37
2.1.1 命题的概念 38
2.1.2 命题符号 38
2.1.3 复合命题 39
2.1.4 常用的五个命题联结词 39
2.2 命题公式与真值表 43
2.2.1 命题变元 43
2.2.2 命题公式 43
2.2.3 真值表 44
2.3 等价及等价公式 46
2.3.1 等价或逻辑相等 46
2.3.2 等价公式表 46
2.4 重言式与蕴含式 48
2.4.1 重言式 48
2.4.2 蕴含 48
2.4.3 蕴含式的证明方法 49
2.4.4 蕴含公式表 50
2.4.5 其他联结词 50
2.5 范式 51
2.5.1 合取范式与析取范式 51
2.5.2 小项与主析取范式 53
2.5.3 大项与主合取范式 55
2.5.4 用真值表表示主范式 58
2.6 推理理论 59
2.6.1 推理规则 59
2.6.2 直接证法 60
2.6.3 反证法 61
2.6.4 CP规则法 61
2.7 谓词与谓词公式 62
2.7.1 谓词的概念 62
2.7.2 命题函数与论域 63
2.7.3 量词 64
2.7.4 谓词公式 65
2.8 谓词演算 66
2.8.1 谓词公式的等价式和蕴含式 66
2.8.2 前束范式 69
2.8.3 谓词公式演算的推理理论 70
数理逻辑习题 72
第3章 代数系统 76
3.1 代数运算及性质 76
3.1.1 代数运算的概念 76
3.1.2 二元运算的性质 76
3.1.3 单位元、零元、逆元 78
3.2 代数系统与半群 80
3.2.1 代数系统 80
3.2.2 半群 80
3.3 群 82
3.3.1 群的概念 82
3.3.2 子群 84
3.4 置换群 86
3.4.1 置换 86
3.4.2 置换群 88
3.4.3 循环置换与对换 88
3.5 交换群与循环群 91
3.5.1 交换群 91
3.5.2 循环群 91
3.6 陪集与拉格朗日定理 93
3.6.1 陪集 93
3.6.2 拉格朗日定理 95
3.7 环与域 96
3.7.1 环 96
3.7.2 域 97
3.8 格 99
3.8.1 格 99
3.8.2 分配格 103
3.8.3 有界格 103
3.8.4 有补格 104
3.8.5 布尔代数 105
代数系统习题 105
第4章 图论 107
4.1 图的概念 107
4.1.1 图的概念 107
4.1.2 结点的度数 110
4.2 路与回路 112
4.2.1 通路与回路 112
4.2.2 连通性与割点 113
4.2.3 有向图的连通性 116
4.3 图与矩阵 117
4.3.1 图的矩阵 117
4.3.2 可达性矩阵 118
4.4 欧拉图 119
4.4.1 欧拉通路与欧拉回路 119
4.4.2 欧拉图的判定 120
4.4.3 中国邮递员问题 120
4.5 哈密尔顿图 124
4.5.1 哈密尔顿图 124
4.5.2 哈密尔顿路 124
4.5.3 旅行商问题 126
4.6 平面图 128
4.6.1 平面图的概念 128
4.6.2 平面图的区域 128
4.6.3 欧拉定理 129
4.6.4 四色定理 132
4.7 两步图 133
4.7.1 两步图 133
4.7.2 匹配 136
4.8 树 136
4.8.1 树的概念 137
4.8.2 生成树 138
4.9 有向树 140
4.9.1 外向树 140
4.9.2 二元树 141
4.9.3 最优树 143
图论习题 145
附录 148
模拟试题（一） 148
模拟试题（二） 150
硕士研究生入学考试试题（一） 152
硕士研究生入学考试试题（二） 154
《离散数学》教学大纲（72学时） 155
《离散数学》教学大纲（48学时） 159
参考文献 162