离散数学

第1章　命题逻辑

1-1　命题

1-1-1　命题与真值

1-1-2　原子命题与复合命题

1-2　逻辑联结词

1-2-1　否定联结词

1-2-2　合取联结词

1-2-3　析取联结词

1-2-4　蕴含联结词

1-2-5　等价联结词

1-3　命题公式

1-3-1　命题公式的概念

1-3-2　命题符号化

1-3-3　命题公式真值表

1-3-4　命题公式的类型

1-3-5　重言式的性质

1-4　命题逻辑的等价关系

1-4-1　等价

1-4-2　基本等价式

1-4-3　置换规则

1-5　命题公式的标准化

1-5-1　析取范式与合取范式

1-5-2　主析取范式与主合取范式

1-5-3　主范式的应用

1-6　命题逻辑的蕴含关系

1-6-1　蕴含

1-6-2　证明蕴含关系的方法

1-6-3　基本蕴含式

1-7　命题逻辑的推理理论

1-7-1　论证的有效性

1-7-2　有效论证的判断方法

1-7-3　自然推理系统

1-7-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-3　谓词逻辑的等价关系

2-3-1　等价关系

2-3-2　基本等价式

2-4　谓词公式的标准化

2-5　谓词逻辑的蕴含关系

2-5-1　蕴含关系

2-5-2　基本蕴含式

2-6　谓词逻辑的推理理论

本章总结

习题

第3章　集合

3-1　集合的概念与表示

3-1-1　集合的定义

3-1-2　集合的表示方法

3-2　集合之间的关系

3-2-1　集合之间的关系

3-2-2　特殊集合

3-3　集合的运算

3-3-1　集合的基本运算

3-3-2　集合关系的证明方法

3-3-3　笛卡儿积

本章总结

习题

第4章　关系

4-1　关系的概念及表示

4-1-1　关系的概念

4-1-2　关系的表示方法

4-2　关系的性质

4-2-1　自反性与反自反性

4-2-2　对称性与反对称性

4-2-3　传递性

4-3　关系的运算

4-3-1　关系的复合运算

4-3-2　关系的逆运算

4-3-3　关系的闭包运算

4-4　等价关系与划分

4-4-1　等价关系的概念

4-4-2　等价类

4-4-3　划分

4-5　次序关系

4-5-1　偏序关系

4-5-2　其他次序关系

本章总结

习题

第5章　函数

5-1　函数的概念与性质

5-1-1　函数的概念

5-1-2　函数的性质

5-2　函数的运算

5-2-1　函数的复合运算

5-2-2　函数的逆运算

5-3　基数

5-3-1　基数的概念

5-3-2　基数的比较

本章总结

习题

第6章　代数结构

6-1　代数系统的概念

6-2　代数系统的运算及其性质

6-2-1　二元运算的性质

6-2-2　小结

6-3　半群与含幺半群

6-3-1　半群和子半群

6-3-2　含幺半群和子含幺半群

6-4　群与子群

6-4-1　群

6-4-2　子群

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-7-3　同余关系

6-8　环与域

6-8-1　环

6-8-2　域

本章总结

习题

第7章　格与布尔代数

7-1　格

7-1-1　格的概念

7-1-2　格的性质

7-2　分配格

7-3　有补格

7-4　布尔代数

本章总结

习题

第8章　图论及其应用

8-1　图的基本概念

8-1-1　图

8-1-2　结点的度

8-1-3　图的同构

8-1-4　子图和补图

8-2　图的连通性

8-2-1　路径与回路

8-2-2　连通图

8-3　图的矩阵表示

8-3-1　图的邻接矩阵

8-3-2　图的可达矩阵

8-4　最短路径与关键路径

8-4-1　最短路径

8-4-2　评审图与关键路径

8-5　树

8-5-1　无向树

8-5-2　有向树

本章总结

习题

附录　习题答案及提示

第1章　习题参考答案

第2章　习题参考答案

第3章　习题参考答案

第4章　习题参考答案

第5章　习题参考答案

第6章　习题参考答案

第7章　习题参考答案

第8章　习题参考答案

参考文献

《离散数学/普通高等教育软件工程“十二五”规划教材》介绍计算机专业必需的离散数学基础知识，包括离散数学四大分支的基础理论，它们是数理逻辑、集合论、代数系统和图论，共8章，依次为命题逻辑、谓词逻辑、集合、关系、函数、代数结构、格与布尔代数、图论及其应用。本书包含较多的与计算机科学和工程有关的例题和习题。
　　《离散数学/普通高等教育软件工程“十二五”规划教材》适合作为高等理工科院校计算机科学与技术、软件工程等相关专业教材，也可供教师、研究生、有关工程技术人员作为参考书。