第1章 绪论 1
1.1 离散数学的研究对象 1
1.2 离散数学的主要内容 2
1.3 学习离散数学的方法 2
第2章 数理逻辑 3
2.1 命题 4
2.1.1 命题的概念 4
2.1.2 命题的表示 4
2.2 命题联结词 5
2.2.1 联结词的定义 6
2.2.2 命题逻辑中联结词的最小集 9
2.3 命题的合式公式 10
2.3.1 合式公式 10
2.3.2 语句的符号化 10
2.4 真值表、永真式和永假式 11
2.4.1 真值表 11
2.4.2 永真式和永假式 13
2.5 公式的等价和蕴含 14
2.5.1 公式的等价 14
2.5.2 公式的蕴含 17
2.6 公式的主范式 19
2.6.1 主析取范式 19
2.6.2 主合取范式 22
2.7 命题演算的推理理论 23
2.7.1 有效推理的概念 24
2.7.2 有效推理的方法 24
2.8 命题逻辑和二值逻辑器件 27
2.9 一阶谓词逻辑 31
2.10 命题函数和个体变量及量词 32
2.10.1 命题函数 33
2.10.2 量词 33
2.11 谓词公式 34
2.11.1 谓词公式 34
2.11.2 变量的约束和替换 36
2.11.3 谓词演算中的等价与蕴含 38
2.12 谓词演算的推理理论 42
习题 45
第3章 集合和关系 51
3.1 集合和集合的运算 51
3.1.1 集合的基本概念 51
3.1.2 集合的运算 52
3.1.3 集合运算中的恒等式 55
3.1.4 序偶和笛卡儿积 57
3.2 关系 58
3.2.1 关系及其表示法 58
3.2.2 几种特殊的关系 61
3.2.3 关系的运算 63
3.3 等价关系和集合的划分 72
3.3.1 等价关系 72
3.3.2 等价关系与划分 74
3.4 序关系和哈斯图 75
3.4.1 序关系 75
3.4.2 偏序关系的哈斯图 75
3.4.3 偏序集中的某些特殊元素 76
3.5 函数及其运算 78
3.5.1 函数的概念 78
3.5.2 函数的复合 81
3.5.3 逆函数 83
习题 84
第4章 数函数和递推关系 88
4.1 数函数的概念 88
4.2 数函数的基本运算 88
4.3 数函数的母函数 89
4.4 递推关系 92
4.4.1 常系数的线性递推关系 93
4.4.2 用母函数求解数函数的通式 95
习题 96
第5章 图论 97
5.1 图的基本概念和术语 97
5.2 路和回路 100
5.3 图的矩阵表示 103
5.4 树和生成树 106
5.4.1 无向树的概念 106
5.4.2 最小生成树 107
5.5 有向树及其应用举例 108
5.5.1 有向树的概念 108
5.5.2 根树的一个应用举例 110
5.6 欧拉图与哈密顿图 112
5.6.1 欧拉图 112
5.6.2 欧拉定理的一个应用举例 113
5.6.3 哈密顿图 114
5.7 最短路径与最长路径问题 116
5.7.1 最短路径 116
5.7.2 最长路径 118
5.8 平面图 122
习题 125
第6章 代数系统 130
6.1 运算和代数系统 130
6.1.1 运算的概念 130
6.1.2 运算的性质 131
6.2 半群和独异点 133
6.3 群和子群 135
6.3.1 群的概念 135
6.3.2 子群的概念 138
6.4 阿贝尔群和循环群 139
6.4.1 阿贝尔(Abel)群 139
6.4.2 循环群 141
6.5 置换群和伯恩赛德定理 142
6.5.1 置换群 142
6.5.2 伯恩赛德(Burnside)定理 144
6.6 陪集和正规子群 147
6.7 拉格朗日定理 149
6.8 同态、同构和同余 150
6.8.1 同态和同构 150
6.8.2 同余关系和同态 154
6.9 环和域 155
习题 158
第7章 格与布尔代数 162
7.1 偏序集、格和格代数 162
7.1.1 偏序和格 162
7.1.2 对偶原理 164
7.1.3 格的初等性质 164
7.1.4 格与代数系统的对应 166
7.2 有补格和分配格 167
7.3 布尔代数 170
7.4 布尔表达式 172
7.5 布尔函数的表示及极小化 178
7.5.1 布尔函数的表示法 178
7.5.2 布尔函数的极小化 180
习题 183
参考文献 186