离散数学

本书是机械工业出版社2004年出版的《计算机科学中的离散结构》的新版教材。本书涵盖了经典“离散结构”或“离散数学”课程的主要内容，包括集合论基础、逻辑代数、图论基础、关系与函数、抽象代数学基础，并适度扩充了计算机科学中常用的组合论基础知识，以及形式系统、形式推理、可计算性的基础理论。
本书内容既适合于对“离散数学”课程的教学内容有全面要求的院校，又可通过适当选材，有针对性地分别用于注重计算机科学理论或强调计算机应用技术的学科专业，具有内容系统全面、阐述浅显易懂、编排合理新颖、习题编配丰富、使用灵活方便的特点。
本书可作为高等院校计算机科学与技术专业及计算机软件学院本科生、专科生的“离散数学”课程的教材，以及毕业生考研复习用书，也可作为计算机教育工作者、研究开发技术人员的参考读物。

出版说明
前言
第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
1.3集合的归纳定义的意义
1.3.1集合的归纳定义
1.3.2集合定义的自然数
练习1.3
第2章两个常用数学基本原理
2.1归纳原理
2.1.1结构归纳原理
2.1.2数学归纳原理
练习2.1
2.2鸽笼原理
2.2.1鸽笼原理的基本形式
2.2.2鸽笼原理的加强形式
练习2.2
第3章组合论基础计数
3.1计数基本原理
3.1.1加法原理和乘法原理
3.1.2包含排斥原理
练习3.1
3.2排列与组合
3.2.1排列的计数
3.2.2组合的计数
练习3.2
3.3重集的排列与组合
3.3.1重集的排列
3.3.2重集的组合
3.3.3禁位排列的计数
练习3.3
3.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.1
4.2逻辑等价式和逻辑蕴涵式
4.2.1重言式
4.2.2逻辑等价式和逻辑蕴涵式
4.2.3对偶原理
练习4.2
4.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.1
5.2谓词演算永真式
5.2.1谓词公式的真值规定
5.2.2谓词演算永真式
5.2.3关于永真式的几个基本原理
练习5.2
5.3谓词公式的前束范式
练习5.3
第6章形式系统与推理技术
6.1谓词演算形式系统Fc
6.1.1FC的基本构成
6.1.2系统内的推理：证明与演绎
6.1.3FC的重要性质
练习6.1
6.2自然推理形式系统ND
6.2.1ND的基本构成
6.2.2ND的系统内推理及性质
练习6.2
第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图的矩阵表示
7.4.1邻接矩阵
7.4.2路径矩阵与可达性矩阵
练习7.4
第8章二分图、平面图和树
8.1二分图
8.1.1二分图的基本概念
8.1.2匹配
练习8.1
8.2平面图
8.2.1平面图的基本概念
8.2.2欧拉公式和库拉托夫斯基定理
8.2.3着色问题
练习8.2
8.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.1
9.2等价关系
9.2.1等价关系与等价类
9.2.2等价关系与划分
练习9.2
9.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.1
10.2特殊函数类
10.2.1单射的、满射的和双射的函数
10.2.2规范映射、单调映射和
连续映射
练习10.2
10.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.1
11.2原始递归函数集
11.2.1初等函数集的不足
11.2.2原始递归式
11.2.3原始递归函数
练习11.2
11.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.1
12.2同态、同构及同余
12.2.1同态与同构
12.2.2同余关系
练习12.2
12.3商代数
练习12.3
第13章群、环、域
13.1半群
13.1.1半群及独异点
13.1.2自由独异点
13.1.3高斯半群
练习13.1
13.2群
13.2.1群及其基本性质
13.2.2子群、陪集和拉格朗日定理
13.2.3正规子群、商群和同态基本定理
练习13.2
13.3循环群和置换群
13.3.1循环群
13.3.2置换群
练习13.3
13.4环
13.4.1环和整环
13.4.2子环和理想
练习13.4
13.5域和有限域
练习13.5
第14章格与布尔代数
14.1格
14.1.1格——有序集
14.1.2格代数
14.1.3分配格和模格
练习14.1
14.2布尔代数
14.2.1有界格和有补格
14.2.2布尔代数
14.2.3布尔代数表示定理
14.2.4布尔表达式与布尔函数
练习14.2
参考文献