出版者的话 译者序 前言 第1章基础:逻辑和证明 1.1命题逻辑 1.1.1引言 1.1.2命题 1.1.3条件语句 1.1.4复合命题的真值表 1.1.5逻辑运算符的优先级 1.1.6翻译语句 1.1.7系统规范说明 1.1.8布尔检索 1.1.9逻辑难题 1.1.10逻辑运算和位运算 练习 1.2命题等价 1.2.1引言 1.2.2逻辑等价 1.2.3德摩根律的运用 1.2.4构建新的逻辑等价式 练习 1.3谓词和量词 1.3.1引言 1.3.2谓词 1.3.3量词 1.3.4其他量词 1.3.5约束论域量词 1.3.6量词的优先级 1.3.7绑定变量 1.3.8涉及量词的逻辑等价 1.3.9否定量化表达式 1.3.10翻译语句为逻辑表达式 1.3.11在系统说明中运用量词 1.3.12选自Lewis Carroll的例子 1.3.13逻辑程序设计 练习 1.4嵌套量词 1.4.1引言 1.4.2量词的顺序 1.4.3将数学语句翻译成涉及嵌套量词的语句 1.4.4将嵌套量词翻译为汉语 1.4.5将汉语语句翻译成逻辑表达式 1.4.6否定嵌套量词 练习 1.5推理规则 1.5.1引言 1.5.2命题逻辑的有效论证 1.5.3命题逻辑的推理规则 1.5.4用推理规则建立论证 1.5.5消解 1.5.6谬误 1.5.7带量词命题的推理规则 1.5.8命题推理和量化语句推理规则的结合 练习 1.6证明导论 1.6.1引言 1.6.2一些专用术语 1.6.3定理陈述的理解 1.6.4证明定理的方法 1.6.5直接证明 1.6.6反证法 1.6.7归谬证明 1.6.8证明中的错误 1.6.9仅仅是开始 练习 1.7证明的方法和策略 1.7.1引言 1.7.2穷举证明和分情形证明 1.7.3存在性证明 1.7.4唯一性证明 1.7.5证明策略 1.7.6寻找反例 1.7.7行动证明策略 1.7.8填充 1.7.9未解决问题的作用 1.7.10其他证明方法 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第2章基本结构：集合、函数、数列与求和 2.1集合 2.1.1引言 2.1.2幂集合 2.1.3笛卡儿积 2.1.4使用带量词的集合符号 2.1.5量词的真值集合 练习 2.2集合运算 2.2.1引言 2.2.2集合恒等式 2.2.3扩展的并集和交集 2.2.4计算机表示集合的方式 练习 2.3函数 2.3.1引言 2.3.2一对一函数和映上函数 2.3.3反函数和函数组合 2.3.4函数的图像 2.3.5几个重要的函数 练习 2.4序列与求和 2.4.1引言 2.4.2序列 2.4.3特殊的整数序列 2.4.4求和 2.4.5基数 练习 关键术语与结果 复习题 补充练习 计算机课题 计算和研究 写作题目 第3章基础：算法、整数和矩阵 3.1算法 3.1.1引言 3.1.2搜索算法 3.1.3排序 3.1.4贪心算法 3.1.5停机问题 练习 3.2函数的增长 3.2.1引言 3.2.2大O记号 3.2.3一些重要的大O结果 3.2.4函数组合的增长 3.2.5大Ω与大Θ记号 练习 3.3算法的复杂度 3.3.1引言 3.3.2时间复杂度 3.3.3理解算法的复杂度 练习 3.4整数和除法 3.4.1引言 3.4.2除法 3.4.3带余除法 3.4.4同余算术 3.4.5同余应用 3.4.6密码学 练习 3.5素数和最大公约数 3.5.1引言 3.5.2素数 3.5.3关于素数的猜想和一些未解决问题 3.5.4最大公约数和最小公倍数 练习 3.6整数和算法 3.6.1引言 3.6.2整数表示 3.6.3整数运算算法 3.6.4同余幂 3.6.5欧几里得算法 练习 3.7数论应用 3.7.1引言 3.7.2若干有用的结果 3.7.3线性同余 3.7.4中国剩余定理 3.7.5大整数计算机算术 3.7.6伪素数 3.7.7公钥密码学 3.7.8RSA密码系统 3.7.9RSA加密 3.7.10RSA解密 3.7.11用RSA作为公钥系统 练习 3.8矩阵 3.8.1引言 3.8.2矩阵算术 3.8.3矩阵乘法算法 3.8.4矩阵转置和幂 3.8.501矩阵 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第4章归纳与递归 4.1数学归纳法 4.1.1引言 4.1.2数学归纳法 4.1.3利用数学归纳法证明的例子 4.1.4为什么说数学归纳法是有效的 4.1.5使用数学归纳法时犯的错误 练习 4.2强归纳法与良序性 4.2.1引言 4.2.2强归纳法 4.2.3利用强归纳法证明的例子 4.2.4计算几何学中使用强归纳法 4.2.5利用良序性证明 练习 4.3递归定义与结构归纳法 4.3.1引言 4.3.2递归地定义函数 4.3.3递归地定义集合与结构 4.3.4结构归纳法 4.3.5广义归纳法 练习 4.4递归算法 4.4.1引言 4.4.2证明递归算法的正确性 4.4.3递归与迭代 4.4.4归并排序 练习 4.5程序正确性 4.5.1引言 4.5.2程序验证 4.5.3推理规则 4.5.4条件语句 4.5.5循环不变量 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第5章计数 5.1计数的基础 5.1.1引言 5.1.2基本的计数原则 5.1.3比较复杂的计数问题 5.1.4容斥原理 5.1.5树图 练习 5.2鸽巢原理 5.2.1引言 5.2.2广义鸽巢原理 5.2.3巧妙使用鸽巢原理 练习 5.3排列与组合 5.3.1引言 5.3.2排列 5.3.3组合 练习 5.4二项式系数 5.4.1二项式定理 5.4.2帕斯卡恒等式和三角形 5.4.3其他的二项式系数恒等式 练习 5.5排列与组合的推广 5.5.1引言 5.5.2有重复的排列 5.5.3有重复的组合 5.5.4具有不可区别物体的集合的排列 5.5.5把物体放入盒子 练习 5.6生成排列和组合 5.6.1引言 5.6.2生成排列 5.6.3生成组合 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第6章离散概率 6.1离散概率引论 6.1.1引言 6.1.2有限概率 6.1.3事件组合的概率 6.1.4概率的推理 练习 6.2概率论 6.2.1引言 6.2.2概率指派 6.2.3事件的组合 6.2.4条件概率 6.2.5独立性 6.2.6伯努利试验与二项分布 6.2.7随机变量 6.2.8生日问题 6.2.9蒙特卡罗算法 6.2.10概率方法 练习 6.3贝叶斯定理 6.3.1引言 6.3.2贝叶斯定理 6.3.3贝叶斯spam过滤器 练习 6.4期望值和方差 6.4.1引言 6.4.2期望值 6.4.3期望的线性性质 6.4.4平均情形下的计算复杂度 6.4.5几何分布 6.4.6独立随机变量 6.4.7方差 6.4.8切比雪夫不等式 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第7章高级计数技术 7.1递推关系 7.1.1引言 7.1.2递推关系 7.1.3用递推关系构造模型 练习 7.2求解线性递推关系 7.2.1引言 7.2.2求解常系数线性齐次递推关系 7.2.3常系数线性非齐次的递推关系 练习 7.3分治算法和递推关系 7.3.1引言 7.3.2分治递推关系 练习 7.4生成函数 7.4.1引言 7.4.2关于幂级数的有用事实 7.4.3计数问题与生成函数 7.4.4使用生成函数求解递推关系 7.4.5使用生成函数证明恒等式 练习 7.5容斥 7.5.1引言 7.5.2容斥原理 练习 7.6容斥原理的应用 7.6.1引言 7.6.2容斥原理的另一种形式 7.6.3埃拉托色尼筛 7.6.4映上函数的个数 7.6.5错位排列 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第8章关系 8.1关系及其性质 8.1.1引言 8.1.2函数作为关系 8.1.3集合的关系 8.1.4关系的性质 8.1.5关系的组合 练习 8.2n元关系及其应用 8.2.1引言 8.2.2n元关系 8.2.3数据库和关系 8.2.4n元关系的运算 8.2.5SQL 练习 8.3关系的表示 8.3.1引言 8.3.2用矩阵表示关系 8.3.3用图表示关系 练习 8.4关系的闭包 8.4.1引言 8.4.2闭包 8.4.3有向图的路径 8.4.4传递闭包 8.4.5沃舍尔算法 练习 8.5等价关系 8.5.1引言 8.5.2等价关系 8.5.3等价类 8.5.4等价类与划分 练习 8.6偏序 8.6.1引言 8.6.2字典顺序 8.6.3哈塞图 8.6.4极大元素与极小元素 8.6.5格 8.6.6拓扑排序 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第9章图 9.1图和图模型 练习 9.2图的术语和几种特殊的图 9.2.1引言 9.2.2基本术语 9.2.3一些特殊的简单图 9.2.4偶图 9.2.5特殊类型的图的一些应用 9.2.6从旧图到新图 练习 9.3图的表示和图的同构 9.3.1引言 9.3.2图的表示 9.3.3邻接矩阵 9.3.4关联矩阵 9.3.5图的同构 练习 9.4连通性 9.4.1引言 9.4.2通路 9.4.3无向图的连通性 9.4.4有向图的连通性 9.4.5通路与同构 9.4.6计算顶点之间的通路数 练习 9.5欧拉通路与哈密顿通路 9.5.1引言 9.5.2欧拉通路与欧拉回路 9.5.3哈密顿通路与哈密顿回路 练习 9.6最短通路问题 9.6.1引言 9.6.2最短通路算法 9.6.3旅行商问题 练习 9.7可平面图 9.7.1引言 9.7.2欧拉公式 9.7.3库拉图斯基定理 练习 9.8图着色 9.8.1引言 9.8.2图着色的应用 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第10章树 10.1概述 10.1.1树作为模型 10.1.2树的性质 练习 10.2树的应用 10.2.1引言 10.2.2二叉搜索树 10.2.3决策树 10.2.4前缀码 10.2.5博弈树 练习 10.3树的遍历 10.3.1引言 10.3.2通用地址系统 10.3.3遍历算法 10.3.4中缀、前缀和后缀记法 练习 10.4生成树 10.4.1引言 10.4.2深度优先搜索 10.4.3宽度优先搜索 10.4.4回溯 10.4.5有向图中的深度优先搜索 练习 10.5最小生成树 10.5.1引言 10.5.2最小生成树算法 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第11章布尔代数 11.1布尔函数 11.1.1引言 11.1.2布尔表达式和布尔函数 11.1.3布尔代数恒等式 11.1.4对偶性 11.1.5布尔代数的抽象定义 练习 11.2布尔函数的表示 11.2.1积之和展开式 11.2.2函数完全性 练习 11.3逻辑门电路 11.3.1引言 11.3.2门的组合 11.3.3电路的例子 11.3.4加法器 练习 11.4电路的极小化 11.4.1引言 11.4.2卡诺图 11.4.3无需在意的条件 11.4.4奎因莫可拉斯基方法 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 第12章计算模型 12.1语言和文法 12.1.1引言 12.1.2短语结构文法 12.1.3短语结构文法的类型 12.1.4派生树 12.1.5巴克斯诺尔范式 练习 12.2带输出的有限状态机 12.2.1引言 12.2.2带输出的有限状态机 练习 12.3不带输出的有限状态机 12.3.1引言 12.3.2串的集合 12.3.3有限状态自动机 12.3.4有限状态机的语言识别 12.3.5非确定型有限状态自动机 练习 12.4语言的识别 12.4.1引言 12.4.2正则集合 12.4.3克莱因定理 12.4.4正则集合和正则文法 12.4.5一个不能由有限状态自动机识别的集合 12.4.6一些更强大的机器 练习 12.5图灵机 12.5.1引言 12.5.2图灵机的定义 12.5.3用图灵机识别集合 12.5.4用图灵机计算函数 12.5.5不同类型的图灵机 12.5.6丘奇图灵论题 12.5.7计算复杂度、可计算性和可判定性 练习 关键术语和结果 复习题 补充练习 计算机题目 计算和研究 写作题目 附录A实数和正整数公理 附录B指数函数和对数函数 附录C伪代码 推荐读物 参考文献