前言
第1章 集合论
1.1 集合的概念和表示
1.1.1 集合
1.1.2 集合的表示
1.1.3 集合与元素的关系
1.1.4 集合之间的关系
1.2 集合的运算
1.2.1 集合的运算
1.2.2 绝对补集
1.2.3 对称差集
1.3 集合恒等式和运算性质
1.3.1 集合恒等式
1.3.2 集合运算性质的一些重要结果
1.3.3 对偶原理
1.3.4 集合恒等式的证明方法
1.4 集合的计数
1.4.1 限集的基本概念
1.4.2 有限集合的计数
1.4.3 容斥原理
1.4.4 鸽巢原理
本章小结
习题
第2章 二元关系
2.1 二元关系
2.1.1 序偶和笛卡儿积
2.1.2 关系的定义
2.1.3 关系的表示法
2.2 关系的运算
2.2.1 关系的定义域、值域、域
2.2.2 关系的交、并、补、差运算
2.2.3 关系的复合运算
2.2.4 关系的逆运算
2.2.5 关系的幂运算
2.3 关系的性质
2.3.1 自反性与反自反性
2.3.2 卜称性与反对称性
2.3.4 关系性质的证明
2.3.5 利用集合运算来判断关系的性质
2.3.6 关系性质的保守性
2.4 关系的闭包
2.5 等价关系
2.5.1 等价关系
2.5.2 商集与划分
2.6 偏序关系
2.6.1 次序关系的定义
2.6.2 偏序集的哈斯图
本章小结
习题
第3章 命题逻辑
3.1 命题
3.2 联结词
3.3 命题公式及其真值表
3.4 命题公式的等价、蕴涵
3.5 对偶与范式
3.5.1 对偶公式
3.5.2 析取范式与合取范式
3.5.3 范式的唯一性——主范式
3.6 推理的形式结构及自然推理系统
3.6.1 有效推理
3.6.2 形式推理系统p1
本章小结
习题
第4章 一阶谓词逻辑
4.1 谓词
4.2 量词
4.3 谓词公式
4.4 自由与约束
4.5 谓词公式的等价、蕴涵
4.5.1 等价式
4.5.2 蕴涵式
4.6 谓词逻辑中的范式
4.7 谓词演算的推理理论
本章小结
习题
第5章 代数系统
5.1 代数系统的概念
5.1.1 代数运算
5.1.2 代数系统
5.2 代数系统的同态和同构
5.2.1 同态与同构的概念
5.2.2 同态和同构的性质
5.2.3 代数系统的同余关系
本章小结
习题
第6章 几种典型的代数系统
6.1 半群与含幺半群
6.1.1 半群和含幺半群的概念
6.1.2 丰群的基本性质
6.1.3 子半群和子含幺半群
6.2 群与子群
6.2.1 群的概念
6.2.2 子群的概念及性质
6.2.3 群的同态与同构
6.3 交换群、循环群与置换群
6.3.1 交换群
6.3.2 循环群
6.3.3 置换群
6.4 陪集与拉格朗日定理
6.4.1 陪集的定义及基本性质
6.4.2 拉格朗日定理
6.5 环与域
6.5.1 环的概念及性质
6.5.2 几种特殊的环
6.6 格与布尔代数
6.6.1 格的概念及性质
6.6.2 格的同态和同构
6.6.3 几种特殊格
6.6.4 布尔代数与布尔表达式
本章小结
习题
第7章 图论
7.1 图的基本概念
7.1.1 图的定丈
7.1.2 顶点的度及其性质
7.1.3 图的分类
7.2 子图、图的同构和运算
7.2.1 子图
7.2.2 图的同构
7.2.3 图的运算
7.3 路和连通性
7.3.1 途径、迹和路
7.3.2 图的连通性
7.4 图的矩阵表示
7.4.1 关联矩阵
7.4.2 邻接矩阵和相邻矩阵
7.4.3 可达矩阵和连通矩阵
7.5 最短路问路
7.5.1 赋权图
7.5.2 最短路问题
本章小结
习题
第8章 树
8.1 无向树
8.1.1 无向树的概念
8.1.2 无向树的性质
8.2 生成树
8.2.1 生成树
8.2.2 生成树的应用
8.3 有向树和根树
8.3.1 根树及其性质
8.3.2 二叉树
8.3.3 最优二叉树(optimal binary tree)
8.3.4 二叉树的应用——前缀码
8.3.5 二叉树的遍历
本章小结
习题
第9章 特殊图
9.1 欧拉图
9.1.1 欧拉图
9.1.2 欧拉图的应用
9.2 哈密顿图
9.2.1 哈密顿图
9.2.2 哈密顿应用—货郎问题
9.3 二部图与匹配
9.3.1 支配集、点覆盖集与点独立集
9.3.2 偶图与匹配
9.4 平面图及对偶图
9.4.1 平面图的基本概念
9.4.2 平面图的定理和性质
9.4.3 平面的对偶图
9.5 平面图的着色问题
9.5.1 图的顶点着色
9.5.2 五色定理和四色猜想
9.5.3 边着色
本章小结
习题
参考答案