第1篇 预备知识

第1章 集合基础

1.1 集合与子集

1.1.1 集合

1.1.2 集合的表示

1.1.3 集合与元素的关系

1.1.4 外延性原理

1.1.5 集合之间的关系与子集

1.2 集合的运算

1.3 无限集的基本概念

1.3.1 自然数集合与可列集合

1.3.2 不可数集合

1.4 有限集合的计数

1.4.1 鸽笼原理

1.4.2 容斥原理

1.5 习题

第2章 序列（有序组）

2.1 序列与子序列

2.2 序列的运算

2.3 习题

第3章 整数中的除法

3.1 整除

3.2 最大公因子

3.3 最小公倍数

3.4 习题

第4章 矩阵的基础知识

4.1 矩阵的定义

4.2 矩阵的运算及性质

4.3 布尔矩阵及运算

4.4 习题

第2篇 数理逻辑

第5章 命题逻辑

5.1 命题与命题联结词

5.1.1 命题

5.1.2 命题联结词

5.2 命题公式、解释与真值表

5.2.1 命题公式

5.2.2 公式的解释与真值表

5.2.3 一些特殊的公式

5.2.4 等价公式

5.3 联结词的完备集

5.3.1 联结词的扩充

5.3.2 与非、或非和异或的性质

5.3.3 全功能联结词集合

5.4 范式

5.4.1 析取范式和合取范式

5.4.2 主析取范式和主合取范式

5.5 命题逻辑的推理理论

5.5.1 推理的基本概念和推理形式

5.5.2 判断有效结论的常用方法

5.6 习题

第6章 谓词逻辑

6.1 谓词逻辑中的基本概念与表示

6.1.1 谓词

6.1.2 量词

6.1.3 谓词的语言翻译

6.2 谓词公式与解释

6.2.1 谓词的合适公式

6.2.2 自由变元和约束变元

6.2.3 公式的解释

6.2.4 一些特殊的公式

6.2.5 等价关系与蕴涵关系

6.3 范式

6.3.1 前束范式

6.3.2 Skolem标准形

6.4 谓词演算的演绎与推理

6.4.1 推理规则

6.4.2 谓词演算的综合推理方法

6.5 习题

第7章 数理逻辑在计算机科学中的应用

7.1 命题逻辑在计算机科学中的应用

7.2 谓词逻辑在计算机科学中的应用

7.2.1 谓词逻辑与数据子语言

7.2.2 谓词逻辑与逻辑程序设计语言

第3篇 二元关系

第8章 二元关系

8.1 二元关系及其表示法

8.1.1 序偶与笛卡儿积

8.1.2 关系的引入

8.1.3 关系的定义

8.1.4 二元关系

8.1.5 关系的表示法

8.2 关系的运算

8.2.1 关系的交、并、补、差运算

8.2.2 关系的复合运算

8.2.3 关系的逆运算

8.2.4 关系运算的性质

8.3 关系的性质

8.3.1 自反性与反自反性

8.3.2 对称性与反对称性

8.3.3 传递性

8.3.4.关系性质的证明

8.3.5 利用集合运算来判断关系的性质

8.3.6 关系性质的保守性

8.4 关系的闭包运算

8.4.1 关系的限制与扩充

8.4.2 关系的闭包

8.5 习题

第9章 特殊关系

9.1 等价关系

9.1.1 集合的划分

9.1.2 等价关系

9.1.3 等价类与商集

9.1.4 等价关系与划分

9.2 次序关系

9.2.1 次序关系的定义

9.2.2 偏序集的哈斯图

9.2.3 偏序集中的特殊元素

9.2.4 全序与良序

9.3 习题

第10章 函数

10.1 函数的基本概念

10.2 函数的性质

10.3 函数的复合运算

10.4 函数的逆运算

10.5 置换

10.6 习题

第11章 关系在计算机科学中的应用

11.1 关系在关系数据库中的应用

11.2 关系代数与数据子语言

11.3 关系及闭包与计算机程序

11.4 划分在计算机中的应用

第4篇 图论

第12章 图

12.1 图的基本概念

12.1.1 图的定义

12.1.2 结点的度数

12.1.3 子图与补图

12.1.4 图的同构

12.1.5 图的操作

12.2 通路与回路

12.3 无向图的连通性

12.4 有向图的连通性

12.5 图的矩阵表示

12.5.1 邻接矩阵

12.5.2 可达性矩阵

12.6 习题

第13章 特殊图

13.1 欧拉图

13.2 哈密尔顿图

13.3 树

13.3.1 无向树

13.3.2 生成树

13.3.3 最小生成树

13.3.4 有向树

13.4 偶图

13.5 平面图

13.5.1 观察法

13.5.2 欧拉公式

13.5.3 库拉托夫斯基定理

13.5.4 对偶图

13.6 图的着色

13.6.1 结点着色

13.6.2 边着色

13.7 习题

第14章 图论在计算机科学中的应用

14.1 计算机鼓轮设计

14.2 巡回售货员问题

14.2.1 最邻近算法

14.2.2 抄近路算法

14.3 中国邮路问题

14.4 前缀码

14.5 波兰符号法与逆波兰符号法

14.6 网络

14.6.1 运输网络

14.6.2 关键道路法

14.6.3 通信网络

第5篇 代数系统与布尔代数

第15章 代数系统

15.1 代数系统

15.1.1 代数运算

15.1.2 代数运算的性质

15.1.3 代数系统

15.2 同态与同构

15.2.1 同态与同构

15.2.2 同态的性质

15.3 习题

第16章 群论

16.1 半群与含幺半群

16.1.1 半群与含幺半群

16.1.2 循环半群与循环独异点

16.2 群的基本概念与性质

16.2.1 群的定义和基本性质

16.2.2 元素的周期

16.2.3 子群

16.2.4 群的同态

16.3 特殊群

16.3.1 交换群（阿贝尔群）

16.3.2 循环群

16.4 陪集与拉格朗日定理

16.4.1 陪集

16.4.2 拉格朗日定理

16.5 不变子群与商群

16.5.1 不变子群（正规子群）

16.5.2 商群

16.6 习题

第17章 环与域

17.1 环

17.2 域

17.3 习题

第18章 格与布尔代数

18.1 格

18.1.1 格的定义

18.1.2 格的另一定义

18.1.3 格的性质

18.1.4 子格

18.1.5 格的同态与同构

18.2 特殊格

18.2.1 分配格

18.2.2 模格

18.2.3 有界格

18.2.4 有补格

18.3 布尔代数

18.3.1 布尔代数

18.3.2 布尔表达式

18.4 习题

第19章 代数系统的应用

19.1 有限自动机

19.2 计数问题

19.2.1 理论基础

19.2.2 图的计数问题

19.2.3 开关线路的计数问题

19.3 纠错码

19.3.1 纠错码简介

19.3.2 纠错码的纠错能力

19.3.3 纠错码的选择

19.3.4 群码的校正

19.4 开关电路

19.4.1 开关函数

19.4.2 逻辑门

19.4.3 全加器的逻辑设计