离散数学

出版时间：2009-6  出版社：华东师范大学出版社  作者：章炯民，陶增乐 编  页数：238  

前言

　　现代社会与计算机日益密切地融合，而数字计算机本质上是一种“离散”的机器，并越来越多地用于处理离散的对象，从而使“离散数学”成为计算机科学不可或缺的理论基础和工具，并推动离散数学本身进一步发展和丰富。作为计算机专业最重要的必修课程之一，近年来离散数学越来越受到重视，它不仅是学习后继课程的基础，更是培养学生的思维、提高分析问题和解决问题的能力的重要途径。　　本书第一版成书于1985年，11年后，为了适应计算机学科的迅速发展作了一次修订。如今，距第二版成书又过去了13年。期间，不仅计算机学科本身又有了许多重大进展，而且目前的社会环境、高校和学生的情况都与以往大不一样。正是基于这样的背景，我们对第二版再次作了全面修订，以适应学科的发展和教学的需要。　　第三版的内容组织主要依据教育部计算机科学与技术专业教学指导分委员会制定的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范》，并参考了美国计算机学会ACM的Computing Curricula 2005。与第二版相比较，第三版的涵盖面有所扩大，增加了初等数论、组合数学等方面的内容；与计算机科学的结合更紧密，增加了离散数学应用的内容；压缩了某些较抽象、实际应用中较少涉及的内容，如集合的基数等。　　本书前两版的显著特点是：简洁、条理清晰。第三版在保持这两个特点的基础上，把离散数学与计算机科学有机地联系起来，力图将本教材编写成“面向计算机科学的”离散数学。一方面加强学生对基本内容的掌握，培养分析问题和解决问题的能力；另一方面，进一步激发学生的学习兴趣。此外，第三版对学生的实际情况也作了充分考虑，对难点和重点的讨论尽可能地做到直观、循序渐进、详尽，并适当地作了一些学习指导。　　第三版包含的内容较多，一般需要两个学期才能全部覆盖。教师可根据具体的专业方向、教学目标、学生的情况等进行适当组合。本书在内容的组织上已经充分考虑到这样的需要，尽可能地保持各章节内容的自含，以便于取舍。

内容概要

　　《离散数学（第3版）》前两版的显著特点是：简洁、条理清晰。第三版在保持这两个特点的基础上，把离散数学与计算机科学有机地联系起来，力图将本教材编写成“面向计算机科学的”离散数学。一方面加强学生对基本内容的掌握，培养分析问题和解决问题的能力；另一方面，进一步激发学生的学习兴趣。此外，第三版对学生的实际情况也作了充分考虑，对难点和重点的讨论尽可能地做到直观、循序渐进、详尽，并适当地作了一些学习指导。

书籍目录

第一章 集合论1.1 集合的概念和术语1.1.1 集合的基本概念和表示1.1.2 集合之间的关系1.1.3 集合簇1.2 集合的运算1.2.1 集合的基本运算1.2.2 幂集1.2.3 n元组和笛卡儿乘积1.2.4广义并和广义交1.3 集合运算的性质1.3.1 集合恒等式1.3.2 集合演算1.3.3 对偶原理1.4 有限集合的计数1.5 罗素悖论1.6 小结1.7 习题第二章 数论基础2.1 最大公因数和最小公倍数2.1.1 整除、同余、最大公因数和最小公倍数2.1.2 欧几里得算法2.1.3 最大公因数和最小公倍数的性质2.2 素数2.2.1 整数的素分解2.2.2 素性探测2.3 一次同余方程2.3.1 一次同余方程2.3.2 一次同余方程组2.3 3 大整数的剩余表示法2.4 RSA公钥密码体制2.5 小结2.6 习题第三章 命题逻辑3.1 命题和命题公式3.1.1 命题与逻辑联结词3.1.2 命题公式3.2 等值演算3.2.1 等值的概念3.2.2 等值演算3.2.3 对偶原理3.3 范式3.3.1 主析取范式3.3.2 主合取范式3.3.3 联结词的功能完备集3.4 命题逻辑的推理理论3.5 小结3.6 习题第四章 一阶逻辑4.1 谓词4.1.1 谓词和量词4.1.2 谓词公式4.2 等值演算和前束范式4.3 一阶逻辑的推理理论4.4 小结4.5 习题第五章 关系5.1 关系的概念5.1.1 二元关系5.1.2 二元关系的表示5.1.3 n元关系5.2 关系运算5.2.1 关系的基本运算5.2.2 关系运算的性质5.3 关系的特殊性质及其闭包5.3.1 关系的特殊性质5.3.2 关系的闭包5.4 等价关系和划分5.4.1 等价关系和等价类5.4.2 划分和等价关系5.5 偏序关系5.5.1 偏序关系和偏序集5.5.2 哈斯图5.5.3 偏序集的性质5.5.4 拓扑序列5.5.5 格5.6 小结5.7 习题第六章 函数和集合的基数6.1 函数的概念和性质6.1.1 函数的基本概念6.1.2 函数的复合和逆6.2 集合的基数6.2.1 集合的等势6.2.2 可数集6.2.3 无限集和集合的基数6.3 不可解问题6.3.1 不可解问题的存在性6.3.2 停机问题6.4 小结6.5 习题第七章 图论基础7.1 图及其表示7.1.1 图的概念7.1.2 图的矩阵表示7.1.3 几种特殊的图7.1.4 子图和图运算7.2 握手定理7.3 图的连通性7.3.1 通路和回路7.3.2 图的连通性7.3.3 矩阵运算和连通性7.4 最短通路和Dijkstra算法7.4.1 广度优先搜索算法7.4.2 带权图和Dijkstra算法7.5 顶点着色7.6 图同构7.7 小结7.8 习题第八章 具有特殊性质的图8.1 欧拉图8.1.1 欧拉图的概念8.1.2 无向欧拉图的性质8.1.3 有向欧拉图的性质8.2 哈密顿图8.2.1 哈密顿图的概念8.2.2 无向哈密顿图的性质8.2.3 格雷码8.2.4 竞赛图8.3 平面图8.3.1 平面图的概念8.3.2 平面图的性质8.4 无向树8.4.1 无向树的概念8.4.2 无向树的基本性质8.4.3 求最小生成树的Kruskal算法8.5 有向树8.5.1 有向树和根树及其简单性质8.5.2 求最优树的Huffman算法8.6 小结8.7 习题第九章 基本计数方法9.1 鸽笼原理9.2 加法原理与乘法原理9.3 排列与组合9.3.1 排列9.3.2 组合9.4 二项式系数9.5 可重复的排列和组合9.5.1 可重复的排列9.5.2 可重复的组合9.6 容斥原理9.7 生成排列和组合9.7.1 生成排列9.7.2 生成组合9.9 习题第十章 递推关系和生成函数10.1 递推关系10.2 常系数线性递推关系10.2.1 求解常系数线性齐次递推关系10.2.2 求解常系数线性非齐次递推关系10.3 生成函数10.3.1 幂级数型生成函数10.3.2 指数型生成函数10.4 生成函数应用举例10.5 小结10.6 习题第十一章 代数结构基础11.1 代数系统11.2 二元运算的性质11.3 半群和独异点11.4 同态和同构11.5 小结11.6 习题第十二章 群12.1 群12.2 子群12.2.1 子群12.2.2 元素的阶12.3 循环群和群的直积12.3.1 循环群12.3.2 群的直积12.4 陪集和正规子群12.5 群同态12.6 变换群和置换群12.7 群码12.7.1 纠错码的基本概念12.7.2 线性码的生成矩阵与校验矩阵12.7.3 群码12.8 小结12.9 习题第十三章 环和域13.1 环13.1.1 环的定义13.1.2 特殊元素和性质13.1.3 环的分类13.2 子环、理想和商环13.2.1 子环和理想13.2.2 商环13.3 环同态13.4 一元多项式环与多项式编码13.4. 1域上的一元多项式13.4.2 一元多项式环的主理想13.4.3多项式编码13.5 域13.5.1 域的基本概念和简单性质13.5.2 有限域13.5.3 扩域的性质和几何作图问题13.6 小结13.7 习题第十四章 格和布尔代数14.1 格14.1.1 偏序格14.1.2 代数格14.2 有界格、有补格和分配格14.3 布尔代数14.3.1 布尔格和布尔代数14.3.2 有限布尔代数14.3.3 对偶原理14.4 小结14.5 习题参考文献

章节摘录

　　第一章　集合论　　集合是数学的基本概念，很多数学家都认为，所有的数学都可以用集合论的术语来表示。集合论的起源可以追溯到16世纪末，但它的创立是在19世纪末由德国数学家康托尔（G.Cantor）完成的。最初，为了建立微积分学的严格的理论基础，人们对数集进行了研究，直到l876～1883年，康托尔对任意元素的集合进行了系统的研究，提出了基数、序数和良序集等理论，从而奠定了集合论的基础。这样的集合论基于直观的集合概念，称为朴素集合论。l900年前后，由于各种悖论的发现，特别是1901年罗素（B.Russell）悖论的发现，使集合论的发展一度受阻。l908年，策墨罗（E.Zermelo）提出了第一个集合论的公理系统，使数学哲学中产生的一些矛盾基本上得到统一。在此基础上，集合论与逻辑学相互融合并迅速发展，逐步形成了各种公理集合论。现在，集合论不仅作为一门纯数学成为数理逻辑的一个主要分支，而且作为精确、严谨而又简便的语言，已经渗透到现代数学的各个领域，成为整个数学的基础。　　计算机科学对集合论感兴趣，是因为它在计算机科学中被广泛地应用，是建立数学模型以及进行深入探讨的有力工具。比如，在形式语言、编译理论、信息检索、数据结构、程序设计、算法分析、数据库、有限自动机、人工智能等等许多领域中，集合论都是不可缺少的理论工具，起着重要的作用。　　本书仅限于讨论朴素集合论。本章介绍集合的基础知识，主要包括集合的概念、集合运算及其基本性质、n元组和笛卡儿乘积等等，这些基本概念是离散数学的基础，将贯穿整个课程。集合论的其他重要内容，如关系、函数、基数等等，将在第五章和第六章中讲述。　　……