离散数学 第2版
2010-1
机械工业出版社
王元元 等 著
314
“离散”与“连续”是数量关系中一对极为深刻的矛盾，它们之间的对立与统一是数学发展的重要原动力之一。“离散”是“连续”的否定，即“不连续”；而“连续”则是指事物、数量的一种属性，这种属性使它们容易被分割或结合，并且不会因分割或结合而丧失它们原有的本性。例如，实数是连续的，整数则是离散的；二次函数是连续的，二次函数值的计算则是离散的。 “离散数学”作为一门学科，其研究对象是离散数量关系以及离散系统结构的数学模型及建模方法；而其作为一门课程，则是众多离散数学分支的一个拼盘，包括集合论基础、逻辑代数、图论基础、关系与函数、抽象代数学基础和组合论基础知识，以及形式系统、形式推理、可计算性的基础理论。其内容大致可以划分为以下三个组成部分。 一、离散结构的研究中所需的基本数学知识 集合论基础和两个常用数学基本原理（第1、2章）。 二、研究计算机本身离散结构的数学模型及数学方法 1.作为计算机运算基础的逻辑代数（第4、5章）。 2.作为计算机表示基础的形式化、形式系统技术（第6章）。 3.作为计算机科学中“力学”的、讨论计算能力的可计算性理论（第11章）。 三、研究计算机应用对象的离散结构的数学模型及建模方法 1.离散结构的计数模型及递归关系模型（第3章）。 2.离散结构的图模型（第7、8章）。 3.离散结构的一般关系模型及函数模型（第9、10章）。 4.离散结构的抽象代数模型（第12—14章）。 不难看出，本书完全覆盖了经典的“离散结构”或“离散数学”课程的主要内容，既适合于对离散数学课程的教学内容有全面要求的院校，又可通过适当选材，有针对性地分别用于注重计算机科学理论的或强调计算机应用技术的学科专业。因而，本书可作为高等院校计算机科学与技术专业及计算机软件学院本科生、专科生的离散数学课程的教材，以及毕业生考研复习用书，也可作为计算机教育工作者、研究开发技术人员的参考读物。 本书包含了大约100个学时的内容；如果全部或部分删除标记*的内容，则完成教学计划的学时数可控制在80学时左右；如果根据学校的具体情况，按照以下两种思路来筛选素材（参见下页图表），则可以将课时控制在70～80学时。
《离散数学（第2版）》是机械工业出版社2004年出版的《计算机科学中的离散结构》的新版教材。《离散数学（第2版）》涵盖了经典“离散结构”或“离散数学”课程的主要内容，包括集合论基础、逻辑代数、图论基础、关系与函数、抽象代数学基础，并适度扩充了计算机科学中常用的组合论基础知识，以及形式系统、形式推理、可计算性的基础理论。 《离散数学（第2版）》内容既适合于对“离散数学”课程的教学内容有全面要求的院校，又可通过适当选材，有针对性地分别用于注重计算机科学理论或强调计算机应用技术的学科专业，具有内容系统全面、阐述浅显易懂、编排合理新颖、习题编配丰富、使用灵活方便的特点。 《离散数学（第2版）》可作为高等院校计算机科学与技术专业及计算机软件学院本科生、专科生的“离散数学”课程的教材，以及毕业生考研复习用书，也可作为计算机教育工作者、研究开发技术人员的参考读物。
出版说明前言第1章 集合代数1.1 集合的概念与表示1.1.1 集合及其元素1.1.2 集合的表示1.1.3 外延性公理与子集合练习1.11.2 集合运算1.2.1 并、交、差、补运算1.2.2 幂集运算和广义并、交运算1.2.3 集合的笛卡儿积练习1.21.3 集合的归纳定义的意义1.3.1 集合的归纳定义1.3.2 集合定义的自然数练习1.3第2章 两个常用数学基本原理2.1 归纳原理2.1.1 结构归纳原理2.1.2 数学归纳原理练习2.12.2 鸽笼原理2.2.1 鸽笼原理的基本形式2.2.2 鸽笼原理的加强形式练习2.2第3章 组合论基础计数3.1 计数基本原理3.1.1 加法原理和乘法原理3.1.2 包含排斥原理练习3.13.2 排列与组合3.2.1 排列的计数3.2.2 组合的计数练习3.23.3 重集的排列与组合3.3.1 重集的排列3.3.2 重集的组合3.3.3 禁位排列的计数练习3.33.4 递归关系3.4.1 一个重要的递归关系3.4.2 递归关系的求解练习3.4第4章 逻辑代数（上）：命题演算4.1 命题与逻辑联结词4.1.1 命题4.1.2 逻辑联结词4.1.3 命题公式4.1.4 语句的形式化练习4.14.2 逻辑等价式和逻辑蕴涵式4.2.1 重言式4.2.2 逻辑等价式和逻辑蕴涵式4.2.3 对偶原理练习4.24.3 范式4.3.1 析取范式和合取范式4.3.2 主析取范式与主合取范式4.3.3 联结词的扩充与归约练习4.3 第5章 逻辑代数（下）：谓词演算5.1 谓词演算基本概念5.1.1 个体与个体域5.1.2 谓词与谓词填式5.1.3 量词及其辖域5.1.4 谓词公式及语句的形式化练习5.15.2 谓词演算永真式5.2.1 谓词公式的真值规定5.2.2 谓词演算永真式5.2.3 关于永真式的几个基本原理练习5.25.3 谓词公式的前束范式练习5.3第6章 形式系统与推理技术6.1 谓词演算形式系统FC6.1.1 FC的基本构成6.1.2 系统内的推理：证明与演绎6.1.3 FC的重要性质练习6.16.2 自然推理形式系统ND6.2.1 ND的基本构成6.2.2 ND的系统内推理及性质练习6.2第7章 图7.1 图的基础知识7.1.1 图的基本概念7.1.2 结点的度7.1.3 子图、补图及图同构练习7.17.2 路径、回路及连通性7.2.1 路径与回路7.2.2 连通性7.2.3 连通度练习7.27.3 欧拉图与哈密顿图7.3.1 欧拉图及欧拉路径7.3.2 哈密顿图及哈密顿通路练习7.37.4 图的矩阵表示7.4.1 邻接矩阵7.4.2 路径矩阵与可达性矩阵练习7.4第8章 二分图、平面图和树8.1 二分图8.1.1 二分图的基本概念8.1.2 匹配练习8.18.2 平面图8.2.1 平面图的基本概念8.2.2 欧拉公式和库拉托夫斯基定理8.2.3 着色问题练习8.28.3 树8.3.1 树的基本概念8.3.2 生成树8.3.3 根树练习8.3第9章 关系9.1 关系9.1.1 关系的基本概念9.1.2 关系的基本运算9.1.3 关系的基本特性9.1.4 关系特性闭包练习9.19.2 等价关系9.2.1 等价关系与等价类9.2.2 等价关系与划分练习9.29.3 序关系9.3.1 序关系和有序集9.3.2 良基性与良序集，完备序集9.3.3 全序集与良序集的构造练习9.3第10章 函数10.1 函数及函数的合成10.1.1 函数的基本概念10.1.2 函数概念的拓广10.1.3 函数的合成10.1.4 函数的递归定义练习10.110.2 特殊函数类10.2.1 单射的、满射的和双射的函数10.2.2 规范映射、单调映射和连续映射练习10.210.3 函数的逆练习10.3 10.4 有限集和无限集10.4.1 有限集、可数集与不可数集10.4.2 无限集的特性10.4.3 有限集和无限集的基数10.4.4 基数比较练习10.4第11章 递归函数集与可计算性11.1 初等函数集11.1.1 初等函数11.1.2 初等谓词练习11.111.2 原始递归函数集11.2.1 初等函数集的不足11.2.2 原始递归式11.2.3 原始递归函数练习11.211.3 递归函数集11.3.1 阿克曼函数及其性质11.3.2 μ-递归式11.3.3 递归函数集(μ-递归函数集)练习11.3 11.4 图灵机与可计算函数集11.4.1 图灵机11.4.2 图灵可计算函数练习11.4第12章 代数结构概论12.1 代数结构12.1.1 代数结构的意义12.1.2 代数结构的特殊元素12.1.3 子代数结构练习12.112.2 同态、同构及同余12.2.1 同态与同构12.2.2 同余关系练习12.212.3 商代数练习12.3第13章 群、环、域13.1 半群13.1.1 半群及独异点13.1.2 自由独异点13.1.3 高斯半群练习13.113.2 群13.2.1 群及其基本性质13.2.2 子群、陪集和拉格朗日定理13.2.3 正规子群、商群和同态基本定理练习13.213.3 循环群和置换群13.3.1 循环群13.3.2 置换群练习13.313.4 环13.4.1 环和整环13.4.2 子环和理想练习13.413.5 域和有限域练习13.5第14章 格与布尔代数14.1 格14.1.1 格——有序集14.1.2 格代数14.1.3 分配格和模格练习14.114.2 布尔代数14.2.1 有界格和有补格14.2.2 布尔代数14.2.3 布尔代数表示定理14.2.4 布尔表达式与布尔函数练习14.2参考文献
