离散数学[电子资源.图书]

目录
第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.3 Skolem函词、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.1 MPTL的语言
4.2.2 MPTL的语义
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 符号表
参考文献