目录 第 1章绪论 .......................................................................................................1 第一部分数学基础知识 第 2章命题 .......................................................................................................7 2.1定义和举例 .............................................................................................7 2.2命题联结词 .............................................................................................8 2.3重言式和矛盾式 .................................................................................... 13 2.4命题形式化 ........................................................................................... 17 2.5命题的量化 ........................................................................................... 18 第 3章集合和集合运算..................................................................................... 21 3.1集合 ..................................................................................................... 21 3.2集合相等 .............................................................................................. 23 3.3补集 ..................................................................................................... 25 3.4空集 ..................................................................................................... 26 3.5子集和超集 ........................................................................................... 27 3.6幂集和集合族 ....................................................................................... 28 3.7集合的交集、并集和补集 ....................................................................... 30 3.8笛卡儿积 .............................................................................................. 34 3.9集合运算的其他基本规律 ....................................................................... 37 第 4章数学证明............................................................................................... 39 第 5章关系 ..................................................................................................... 43 5.1定义和举例 ........................................................................................... 43 5.2关系运算 .............................................................................................. 47 5.3关系的重要性质 .................................................................................... 50 5.4等价关系与划分 .................................................................................... 52 计算机数学基础 (第 6版) 5.5等价关系的运算 .................................................................................... 57 5.6偏序关系 .............................................................................................. 61 第 6章映射与函数 ........................................................................................... 65 6.1定义及第一个例子 ................................................................................. 65 6.2满射、单射和双射 ................................................................................. 69 6.3序列和集合族 ....................................................................................... 74 6.4集合的基数 ........................................................................................... 77 6.5参考资料 .............................................................................................. 80 第二部分技术支持 第 7章数学证明方法 ........................................................................................ 85 7.1直接证明法 ........................................................................................... 85 7.2换质位法证明 ....................................................................................... 87 7.3反证法 ................................................................................................. 88 7.4等价证明 .............................................................................................. 89 7.5原子命题证明 ....................................................................................... 90 7.6个案分析证明 ....................................................................................... 92 7.7带量词的命题证明 ................................................................................. 93 7.8组合证明 .............................................................................................. 96 第 8章完全归纳法 ......................................................................................... 100 8.1完全归纳法的思路 ............................................................................... 101 8.2归纳证明举例 ..................................................................................... 101 8.3归纳证明的结构 .................................................................................. 104 8.4广义完全归纳法 .................................................................................. 106 8.5归纳定义 ............................................................................................ 107 第 9章组合计数............................................................................................. 116 9.1基本计数原则 ..................................................................................... 116 9.2排列和二项式系数 ............................................................................... 121 9.3计算二项式系数 .................................................................................. 125 第 10章离散概率论 ....................................................................................... 133 10.1随机试验和概率 ................................................................................ 133 10.2条件概率 .......................................................................................... 141 10.3随机变量 .......................................................................................... 143 目录 10.4二项分布和几何分布 .......................................................................... 149 10.5参考资料 .......................................................................................... 153 第三部分数学结构 第 11章布尔代数........................................................................................... 157 11.1布尔函数及其表达形式 ...................................................................... 157 11.2布尔代数的定义 ................................................................................ 163 11.3布尔代数示例 .................................................................................... 164 11.4布尔代数的性质 ................................................................................ 170 11.5布尔代数中的偏序 ............................................................................. 174 11.6布尔代数的原子 ................................................................................ 176 11.7布尔表达式的规范形式 ...................................................................... 180 11.8最小化布尔表达式 ............................................................................. 182 11.9同构基本定理 .................................................................................... 184 11.10电路代数 ......................................................................................... 188 第 12章图和树 .............................................................................................. 193 12.1基本概念 .......................................................................................... 194 12.2图中的通路和回路 ............................................................................. 199 12.3图和矩阵 .......................................................................................... 203 12.4图同构 .............................................................................................. 210 12.5树 .................................................................................................... 212 第 13章命题逻辑........................................................................................... 218 13.1布尔代数和命题逻辑 .......................................................................... 218 13.2范式 ................................................................................................. 223 13.3可满足性等价公式 ............................................................................. 225 13.4不可满足的子句集合 .......................................................................... 229 13.5霍恩子句的可满足性 .......................................................................... 232 13.6归结原理 .......................................................................................... 235 13.7 2KNF中的子句集 ............................................................................. 242 第 14章模算术 .............................................................................................. 245 14.1因数关系 .......................................................................................... 246 14.2模的加法和乘法 ................................................................................ 249 14.3模运算 .............................................................................................. 253 计算机数学基础 (第 6版) 14.4最大公因数和欧几里得算法 ................................................................ 257 14.5费马小定理 ....................................................................................... 261 14.6使用费马小定理的加密 ...................................................................... 265 14.7 RSA加密算法 .................................................................................. 270 14.8参考资料 .......................................................................................... 272