第1章 集合论 1
1.1 基础知识 1
1.1.1 集合的概念与运算 1
1.1.2 二元关系 1
1.1.3 关系的性质及闭包运算 2
1.1.4 关系的闭包运算 2
1.1.5 序关系 3
1.1.6 等价关系 3
1.1.7 映射 4
1.1.8 数学归纳法 4
1.1.9 计数 4
1.1.10 排列组合生成算法 5
1.1.11 离散概率简介 6
1.2 教学要求 7
1.3 典型习题 7
1.4 课后习题及答案 10
1.5 练习题及答案 22
1.6 自测与测试 32
参考答案 34
第2章 命题逻辑 35
2.1 基础知识 35
2.1.1 命题与联结词 35
2.1.2 命题公式、指派及真值表 35
2.1.3 命题公式的等值式 36
2.1.4 主析取范式和主合取范式 37
2.1.5 联结词完备集 37
2.1.6 可满足性问题与消解法 38
2.1.7 推理的形式结构 38
2.1.8 自然推理系统N中的形式证明 38
2.2 教学要求 39
2.3 典型习题 39
2.4 课后习题及答案 45
2.5 练习题及答案 58
2.6 自测与测试 62
参考答案 64
第3章 谓词逻辑 66
3.1 基础知识 66
3.1.1 基本概念 66
3.1.2 一阶逻辑公式及解释 66
3.1.3 一阶逻辑等值式 67
3.1.4 前束范式与斯科林范式 68
3.1.5 谓词演算的推理理论 68
3.2 教学要求 69
3.3 典型习题 69
3.4 课后习题及答案 71
3.5 练习题及答案 82
3.6 自测与测试 89
参考答案 90
第4章 公理系统下的形式证明 92
4.1 基础知识 92
4.1.1 命题逻辑的公理推理系统 92
4.1.2 谓词逻辑的公理系统 93
4.1.3 定理的机器证明 94
4.2 教学要求 94
第5章 图论 95
5.1 基础知识 95
5.1.1 图的基本概念 95
5.1.2 通路、回路与连通性 95
5.1.3 欧拉图与中国邮递员问题 95
5.1.4 哈密尔顿图与旅行售货商问题 96
5.1.5 树 96
5.1.6 图的矩阵表示 97
5.1.7 平面图与图的着色 98
5.2 教学要求 98
5.3 典型习题 99
5.4 课后习题及答案 101
5.5 练习题及答案 111
5.6 自测与测试 126
参考答案 127
第6章 代数系统 129
6.1 基础知识 129
6.1.1 二元运算与代数系统 129
6.1.2 群和半群 129
6.1.3 子群 129
6.1.4 循环群和生成群，群的同构 130
6.1.5 变换群和置换群，凯莱定理 130
6.1.6 子群的陪集和拉格朗日定理 130
6.1.7 正规子群和商群 131
6.1.8 共轭元和共轭子群 131
6.1.9 群的同态 131
6.1.10 环与域 132
6.2 教学要求 132
6.3 典型习题 133
6.4 课后习题及答案 135
6.5 练习题及答案 143
6.6 自测与测试 153
参考答案 154
第7章 格与布尔代数 156
7.1 基础知识 156
7.1.1 格 156
7.1.2 格同态 156
7.1.3 分配格和有补格 156
7.1.4 布尔代数 157
7.1.5 布尔函数及其表达式 157
7.2 教学要求 158
7.3 典型习题 158
7.4 课后习题及答案 160
7.5 练习题及答案 163
7.6 自测与测试 166
参考答案 167