离散数学教程
2010-7
王元元、 等 高等教育出版社 (2010-07出版)
王元元
383
教过多年的离散数学课程，也写过离散数学教材，但总觉得这门课程现有的一些教材内容过于“离散”，体系结构间的相互衔接不尽合理，知识模块的内在联系不够紧密。教学之余，笔者感到似乎需要一本系统性更强的离散数学教程，以更好地满足教学的需求。因此，笔者在传统内容的基础上对内容进行扩展梳理，试图做成这样一部“离散数学教程”：它首先把离散结构涉及的原始概念，诸如集合、命题、谓词、运算等，提炼出来作为全部学习内容的准备知识，为其后的各大组成模块作统一的铺垫；然后介绍离散结构形式化表示的理论，即逻辑代数和集合代数；再基于所有这些公共基础，由浅入深、由简单到复杂、由具体到抽象地依次推出各类离散结构及其数学模型。现在呈现在读者面前的，正是笔者努力想要达成的“离散数学教程”的雏形。它在选材和编排上的内在逻辑大致体现在以下图示中。如果说本教程在教学内容系统性的改造上所做的工作还只是一种尝试，那么在教学内容广泛性的开拓上可以说是用心良苦了。本教程不仅覆盖了集合论、数理逻辑、数论、组合论、图论、可计算性、抽象代数等基础理论部分，还包含了这些基本理论在粗糙集、模糊集、自动推理、智能搜索、加密技术等领域的应用，并涉及公理化集合论、数理逻辑形式系统、形式语言与自动机等相关理论。为了教师和学生能更好地使用本教程，更加便捷地在这个浩瀚的知识海洋里选取适合的模块、章节，以便设计出具有自己所在院校及专业特色的离散数学课程，我们把教程的全部内容分为了如下三个层次。（1）基本内容，它们是教程的主体。运用本教程的教师，可以依据教育部计算机科学与技术教学指导委员会编制的《高等学校计算机科学与技术专业规范》和《高等学校计算机科学与技术专业核心课程教学实施方案》，以及所在学校的特色、定位，在基本内容中选取大部或全部内容进行教学。（2）推荐内容，其标题被标记了*号。教程的这部分内容理论上较为深入，理解上有些难度，推荐给使用本教程的教师，可视情况选作教学内容或课外讲座。
《离散数学教程》打破了传统离散数学教材几大模块分割的编写方式，突出知识的内在联系，强调理论的循序渐进、相互依存，从而更具有可读性和系统性。 《离散数学教程》覆盖了集合论、数理逻辑、组合论、数论、图论、抽象代数、可计算性等基础理论部分，还包含了这些理论在粗糙集、模糊集、自动推理、智能搜索、加密技术等领域的应用，并涉及公理化集合论、数理逻辑形式系统、形式语言与自动机等相关理论。 《离散数学教程》以离散结构为建模对象，紧密联系计算机科学技术，特别强调应用能力、证明技术、计算思维的培养。此外，《离散数学教程》内容宽泛，深度适当，每章后还安排了与本章内容有关的阅读材料，便于学生及时复习并巩固所学知识。 《离散数学教程》配有教学课件与详细的习题解答，便于教师教学。
王元元，中国人民解放军理工大学教授、博士研究生指导教师，长期从事计算机基础理论的研究和教学工作。先后被评为总参优秀教员，全军优秀教员；荣获国家教学名师奖、国家级教学成果二等奖；荣立二等功一次，三等功三次。其任教的主要课程有离散数学、组合数学以及数理逻辑等，其中离散数学课程被推荐为军队级优质课程和国家精品课程。所主编的教材《计算机科学中的逻辑学》、《离散数学》曾分别获得国家级优秀教材奖和电子工业部优秀教材奖。
第0章 准备知识0.1 集合、命题、谓词和运算0.1.1 集合0.1.2 命题与谓词0.1.3 集合的表示0.1.4 外延性原理与子集合0.1.5 运算练习0.1 0.2 鸽笼原理0.2.1 鸽笼原理基本形式0.2.2 鸽笼原理加强形式练习0.2 第1章 逻辑代数(上)：命题演算1.1 逻辑联结词与命题公式1.1.1 逻辑联结词1.1.2 命题公式1.1.3 语句形式化练习1.1 1.2 逻辑等价式和逻辑蕴涵式1.2.1 重言式1.2.2 逻辑等价式和逻辑蕴涵式1.2.3 对偶原理1.2.4 应用逻辑练习1.2 1.3 范式1.3.1 析取范式和合取范式1.3.2 主析取范式与主合取范式1.3.3 联结词的扩充与归约练习1.3 1.4 命题演算消解原理练习1.4 1.5 阅读材料：布尔代数第2章 逻辑代数(下)：谓词演算2.1 谓词演算基本概念2.1.1 个体2.1.2 谓词2.1.3 量词2.1.4 谓词公式及语句形式化练习2.1 2.2 谓词演算永真式2.2.1 谓词公式的语义2.2.2 谓词演算永真式2.2.3 谓词公式等价变换的几个基本原理练习2.2 2.3 谓词演算消解原理2.3.1 前柬化和消去量词2.3.2 谓词演算消解原理练习2.3 2.4 阅读材料：形式推理与形式系统[2]2.4.1 一个形式系统的例子2.4.2 自然推理形式系统ND第3章 集合代数3.1 集合运算3.1.1 集合的并、交、差、补运算3.1.2 集合的环和与环积运算3.1.3 幂集与广义并、交运算练习3.1 3.2 集合的笛卡儿积练习3.2 3.3 集合定义的自然数和归纳法证明3.3.1 集合定义的自然数3.3.2 归纳法证明练习3.3 3.4 阅读材料：公理化集合论简介[4]第4章 初等数论4.1 整除和素数4.1.1 整除4.1.2 最大公因子4.1.3 算术基本定理4.1.4 素数的性质4.1.5 实数的取整[z]与取另{z)练习4.1 4.2 同余4.2.1 同余的基本性质4.2.2 剩余系4.2.3 一次同余方程4.2.4 同余式组4.2.5 Euler定理和Fetmat小定理练习4.2 4.3 阅读材料：数论在加密技术中的应用4.3.1 仿射加密方法4.3.2 RSA加密方法4.3.3 数字签名第5章 计数5.1 计数基本原理5.1.1 加法原理和乘法原理5.1.2 包含排斥原理练习5.1 5.2 排列与组合5.2.1 排列的计数5.2.2 组合的计数练习5.2 5.3 重集的排列与组合5.3.1 重集的排列5.3.2 重集的组合5.3.3 错置的计数练习5.3 5.4 递归式及其应用5.4.1 递归式建模5.4.2 递归式求解练习5.4 5.5 阅读材料：母函数第6章 关系6.1 关系6.1.1 关系及二元关系6.1.2 关系基本运算6.1.3 关系数据库中的关系运算6.1.4 关系的基本特性6.1.5 关系的特性闭包练习6.1 6.2 等价关系6.2.1 等价关系及其等价类6.2.2 等价关系与划分6.2.3 等价关系的应用练习6.2 6.3 序关系6.3.1 序关系和有序集6.3.2 全序集与良序集6.3.3 有序集的应用练习6.3 6.4 阅读材料：格第7章 函数7.1 函数及函数的合成7.1.1 函数基本概念7.1.2 函数的合成7.1.3 函数的递归定义练习7.1 7.2 特殊函数类7.2.1 单射、满射和双射7.2.2 函数的逆7.2.3 谓词、集合、函数的统描述与模糊子集练习7.2 7.3 有限集和无限集7.3.1 有限集、可数集与不可数集7.3.2 无限集的特性练习7.3 7.4 阅读材料：集合基数与基数比较第8章 可计算函数8.1 函数概念的拓广练习8.1 8.2 初等函数8.2.1 初等函数集8.2.2 初等谓词练习8.2 8.3 原始递归函数8.3.1 初等函数集的不足8.3.2 原始递归式8.3.3 原始递归函数集练习8.3 8.4 递归函数8.4.1 阿克曼函数及其性质8.4.2 pc一递归式8.4.3 递归函数集(口一递归函数集)练习8.4 8.5 阅读材料：图灵机8.5.1 图灵机的组成8.5.2 图灵可计算函数第9章 图与树9.1 图9.1.1 图的基本概念9.1.2 结点的度9.1.3 子图、补图及图同构9.1.4 图的应用练习9.1 9.2 路径、回路及连通性9.2.1 路径、通路与回路9.2.2 连通性9.2.3 连通度练习9.2 9.3 图的矩阵表示9.3.1 邻接矩阵9.3.2 路径矩阵与可达性矩阵练习9.3 9.4 树9.4.1 树的基本概念9.4.2 生成树练习9.4 9.5 阅读材料：图搜索算法9.5.1 图搜索算法(A算法)9.5.2 启发式图搜索算法(A算法)第10章 特殊图10.1 欧拉图与哈密顿图10.1.1 欧拉图及欧拉路径10.1.2 哈密顿图及哈密顿通路10.1.3 欧拉图与哈密顿图的应用练习10.1 10.2 二分图10.2.1 二分图基本概念l0.2.2 二分图的匹配及其应用练习10.2 10.3 平面图l0.3.1 F面图基本概念10.3.2 欧拉公式和库拉托夫斯基定理10.3.3 F面图的应用：着色问题练习10.3 10.4 根树10.4.1 根树的概念10.4.2 二元树的性质及应用练习10.4 10.5 阅读材料：博弈树与智能博弈第11章 代数结构通论11.1 代数结构11.1.1 代数结构的组成11.1.2 代数结构的特殊元素11.1.3 子代数练习11.1 11.2 同态和同构练习11.2 11.3 同余关系11.3.1 同余关系的意义11.3.2 同态与同余关系11.3.3 同余关系的应用练习11.3 11.4 阅读材料：正则语言及其代数性质第12章 群、环、域12.1 半群12.1.I芦群及独异点12.1.2 自由独异点练习12.1 12.2 群12.2.1 群及其基本性质12.2.2 群的元素的阶12.2.3 子群、陪集和拉格朗日定理12.2.4 iE规子群和商群练习12.2 12.3 循环群和置换群12.3.1 循环群12.3.2 置换群12.3.3 置换群的应用练习12.3 12.4 环和域12.4.1 环12.4.2 域练习12.4 12.5 阅读材料：有穷自动机12.5.1 有穷自动机12.5.2 状态迁移幺半群12.5.3 语言同余关系参考文献
插图：什么是离散数学？离散数学是研究离散数量关系和离散结构数学模型的数学分支的一个集成。“离散”是“连续”的否定，即“不连续”；“连续”则是事物、数量的一种属性，这种属性使得它们容易被分割或结合，并且不会因此而丧失它们原有的属性。举例来说，整数是离散的，实数则是连续的；马铃薯是离散的，马铃薯羹则是连续的。与初等数学和高等数学不同，离散数学处理的对象不再局限于连续的实数，而对离散的整数情有独钟，甚至不再局限于“数”，而是要面对任意对象所组成的离散结构；离散数学关注的问题也不再局限于数的运算，而是任意对象的总体属性以及它们之间的关系和运算。本章是阅读全书的准备内容，因此，首先要介绍各个章节公共的基础——离散结构的原始概念，包括集合、命题、谓词、运算等；然后介绍在逻辑推理中常常涉及的最为简单的一个数学原理——鸽笼原理。0.1 集合、命题、谓词和运算0.1.1 集合集合（sets）是一个十分常用的基本概念。在中学的数学课程中，读者对集合及其元素的意义已经有所了解。集合是由确定的、互相区别的、并作整体识别的一些对象组成的总体。通常用{..·）表示一个集合，其中…是集合中的对象，对象间用逗号分开。确切地说这不是集合的定义，因为“总体”只是“集合”一词的同义反复。实际上，集合是一个未作定义的原始概念（就像几何学中的点、线、面等概念一样）。不过，上述关于集合概念的描述，有益于对它的内涵和外延作直观的理解和认识。例0.1 （1）“北京大学全体学生”为一集合，组成这一集合的对象是北京大学的学生。（2）“全体正整数”为一集合，其组成对象是正整数。（3）“本书中所有汉字”的集合，其组成对象是本书中的不同汉字。（4）“获1921年诺贝尔物理学奖的科学家”构成一个集合，尽管它只有一个对象——爱因斯坦。
《离散数学教程》：教育部高等理工教育教学改革与实践项目研究成果
我现在还没开始用，但有翻过里边，还不错