本书较系统地介绍了计算机科学与技术专业的核心课程——离散数学的基本知识。分为经典数理逻辑、非经典数理逻辑、集合论、离散概率、抽象代数和图论6部分。

第1章命题逻辑
1.1数理逻辑简介
1.1.1从形式逻辑谈起
1.1.2数理逻辑
1.1.3数理逻辑与计算机科学的关系
1.1.4命题逻辑
1.2命题及命题符号化
1.2.1命题的概念
1.2.2逻辑联结词
1.3命题公式及命题符号化
1.3.1命题公式的定义
1.3.2公式的解释
1.3.3命题符号化
1.4公式的等价
1.4.1公式等价的基本概念
1.4.2基本等价公式
1.4.3等价演算
1.4.4公式的类型
1.5公式的蕴涵
1.5.1公式蕴涵的基本概念
1.5.2基本蕴涵式
1.5.3蕴涵式AB的证明
1.6联结词完备集
1.6.1其他联结词
1.6.2联结词的数目
1.6.3联结词完备集
1.7公式的对偶
1.7.1公式对偶的基本概念
1.7.2对偶原理
1.8公式的范式
1.8.1简单合取式与简单析取式
1.8.2公式的范式
1.9公式的主范式
1.9.1主析取范式
1.9.2主合取范式
1.10命题逻辑推理理论
1.10.1有效结论和推理规则
1.10.2由前提推导出结论的证明方法
习题
第2章一阶逻辑
2.1一阶逻辑简介
2.2一阶逻辑的基本概念
2.2.1个体词和个体域
2.2.2谓词和函词
2.2.3变元和常元
2.2.4量词
2.3一阶逻辑中命题的符号化
2.4一阶逻辑公式及其解释
2.4.1合式公式
2.4.2合式公式的语义
2.5一阶逻辑公式的等价与蕴含
2.5.1逻辑等价
2.5.2逻辑蕴含
2.6自由变元与约束变元
2.6.1量词的辖域
2.6.2自由变元与约束变元
2.7前束范式与Skolem标准形
2.7.1前束范式
2.7.2前束范式和Skolem标准形
2.7.3Skolem函词、Skolem常元和Skolem范式
2.8一阶逻辑的推理理论
2.8.1全称量词消去规则(UI规则)
2.8.2全称量词引入规则(UG规则)
2.8.3存在量词引入规则(EG规则)
2.8.4存在量词消去规则(EI规则)
2.8.5一阶逻辑推理举例
习题
第3章模态命题逻辑
3.1模态命题逻辑简介
3.2模态命题语言
3.3模态命题逻辑推理
3.4模态命题逻辑公式
习题
第4章模态一阶逻辑
4.1模态一阶逻辑简介
4.2模态一阶语言
4.2.1MPTL的语言
4.2.2MPTL的语义
4.3模态一阶逻辑推理
4.3.1时序命题演算
4.3.2带等词的一阶时序逻辑
4.4模态一阶逻辑公式
习题
第5章集合的基本关系与运算
5.1集合论简介
5.2集合的基本概念
5.2.1集合的描述性定义
5.2.2集合的表示法
5.2.3空集
5.2.4集合论的公理化简介
5.2.5韦恩图
5.3集合的运算
5.3.1集合的交与并
5.3.2集合的差与对称差
5.3.3集合等式的证明
5.4集合的覆盖与划分
5.4.1集合的覆盖
5.4.2集合的划分
习题
第6章函数
6.1函数简介
6.2函数的基本概念
6.2.1函数的定义
6.2.2特殊函数
6.2.3函数的构造
6.3函数的复合及逆函数
6.3.1函数的复合
6.3.2逆函���
6.4特征函数和模糊集简介
6.4.1特征函数
6.4.2模糊集的概念及表示
6.4.3模糊集的运算
6.4.4λ截集和分解定理
6.5集合的基数
6.5.1集合的基数
6.5.2基数的比较
6.5.3集合运算后的基数
6.6无限集合的性质
6.6.1无限集合的性质
6.6.2无限集合的基本运算
6.7可数集合与不可数集合
6.7.1可数集合与不可数集合的基本概念
6.7.2连续统假设
6.8函数的增长性
6.8.1大O记号
6.8.2大Ω记号和大θ记号
6.8.3函数运算后的增长性
习题
第7章关系
7.1关系简介
7.2关系的概念及表示法
7.2.1序偶
7.2.2笛卡儿积
7.2.3关系的概念
7.2.4关系的表示法
7.2.5几种特殊关系
7.3关系的运算
7.3.1关系的逆与关系的复合
7.3.2关系运算的矩阵表示
7.3.3关系运算的关系图表示
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.5.3关系的传递闭包
7.5.4关系闭包的矩阵和Warshall算法
7.6等划关系与等价划分
7.6.1等价关系与等价类
7.6.2等价划分
7.7偏序关系
7.7.1偏序关系的概念
7.7.2哈斯图
7.7.3格
7.7.4偏序关系的应用举例
7.8相容关系
7.8.1相容关系和相容类
7.8.2相容关系的关系图和关系矩阵
7.8.3*大相容类的存在性及求法
7.8.4相容关系与覆盖
习题
第8章离散概率
8.1离散概率简介
8.2排列与组合
8.2.1加法法则和乘法法则
8.2.2排列
8.2.3组合
8.3概率的基本概念及计算
8.3.1实验与事件
8.3.2概率的定义
8.3.3事件的运算及其概率
8.3.4条件概率与概率乘法定理
8.3.5全概率公式与贝叶斯公式
8.4离散型随机变量及其分布
8.4.1概率分布
8.4.2重要随机变量的分布
8.4.3随机向量的概率分布
8.4.4边缘分布
8.4.5条件概率分布及随机变量的独立性
8.5随机变量的函数
8.6期望与方差
8.6.1期望
8.6.2方差
8.6.3大数定理
习题
第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.4半群与子半群
9.4.1半群
9.4.2子半群
习题
第10章群
10.1群的概述
10.1.1群的概念
10.1.2元素的阶
10.2循环群和对称群
10.2.1循环群
10.2.2对称群
10.3子群与陪集
10.3.1子群的概念及判别
10.3.2陪集
10.3.3正规子群
10.4群在编码中的应用简介
10.4.1编码函数
10.4.2编码函数的查错纠错能力
10.4.3群码
习题
第11章环和域
11.1环
11.1.1环的概念
11.1.2特殊的环
11.1.3无零因子环的特征
11.2域
习题
第12章格
12.1格的简介
12.2格的性质
12.2.1格的基本性质
12.2.2格的代数系统定义
12.2.3子格
12.2.4格的同构
12.3特殊格
12.3.1分配格
12.3.2有界格
12.3.3有补格
12.3.4有补分配格
12.4布尔代数
12.4.1布尔代数的性质
12.4.2有限布尔代数的表示
12.5布尔函数与布尔表达式
12.5.1布尔函数
12.5.2布尔函数的范式
习题
第13章图的基本问题
13.1图论简介
13.2图的基本概念
13.2.1图论中的基本术语
13.2.2图的同构
13.2.3图的运算
13.3图的矩阵表示
13.3.1邻接矩阵
13.3.2关联矩阵
13.3.3图的矩阵在同构判定中的作用
13.4路与回路
13.4.1路与回路的概念
13.4.2路与回路的判别
13.4.3路在同构判定中的作用
13.5图的连通性
13.5.1无向图的连通性
13.5.2有向图的连通性
13.6连通度
13.6.1点连通度
13.6.2边连通度
13.7*短路
13.7.1*短路问题的提出
13.7.2*短路算法
13.8拉姆赛问题简介
习题
第14章树
14.1树的简介
14.2树的定义与性质
14.2.1树的定义
14.2.2树的性质
14.3生成树
14.3.1生成树的定义
14.3.2回溯法和广度优先搜索法
14.4*小生成树
14.5根树
14.5.1根树的定义及性质
14.5.2有序树
14.5.3子树
14.6有序二元树的搜索
14.6.1前序搜索
14.6.2中序搜索
14.6.3后序搜索
14.6.4波兰记号和逆波兰记号
14.7树的应用
14.7.1哈夫曼树
14.7.2前缀码
14.7.3决策树
14.7.4其他应用
习题
第15章一些特殊的图
15.1欧拉图
15.1.1欧拉图及其判定
15.1.2欧拉路与欧拉回路的简单应用
15.2哈密顿图
15.2.1哈密顿图的定义及判定
15.2.2哈密顿图的应用
15.3二分图
15.3.1二分图的基本概念
15.3.2匹配
15.4平面图
15.4.1平面图的概念
15.4.2平面图的判别
15.4.3极大平面图与极小非平面图
15.4.4平面图的对偶图
15.5图的着色
15.5.1图着色的基本概念
15.5.2颜色多项式
习题
附录A与离散数学领域相关的一些**数学家
附录B术语索引
附录C符号表
参考文献