离散数学

第一篇 集合论

第1章 集合

1.1 集合的概念与表示

1.1.1 集合及其表示

1.1.2 子集与幂集

1.2 集合的运算

1.2.1 集合的交、并、补、差

第一篇 集合论

第1章 集合

1.1 集合的概念与表示

1.1.1 集合及其表示

1.1.2 子集与幂集

1.2 集合的运算

1.2.1 集合的交、并、补、差

1.2.2 集合运算的性质

*1.3 容斥原理

本章小结

习题一

第2章 关系

2.1 关系的概念与表示

2.1.1 笛卡儿积

2.1.2 关系的概念

2.1.3 关系的表示

2.2 关系的基本性质

2.2.1 自反

2.2.2 对称

2.2.3 传递

2.3 关系的运算

2.3.1 关系的交、并、补、差

2.3.2 关系的复合

2.3.3 关系的逆

2.3.4 关系的闭包

2.4 等价关系与序关系

2.4.1 等价关系与划分

2.4.2 序关系

本章小结

习题二

第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.4 基数

3.4.1 基数的概念

3.4.2 可数集与不可数集

本章小结

习题三

第二篇 图论

第4章 图

4.1 图的概念与表示

4.1.1 图的基本概念

4.1.2 图的矩阵表示

4.2 路径与连通性

4.2.1 路径与回路

4.2.2 图的连通性

4.3 欧拉图与汉密尔顿图

4.3.1 欧拉图

4.3.2 汉密尔顿图

*4.4 图的应用

4.4.1 最短路径问题

4.4.2 支配集与通信系统建站问题

本章小结

习题四

第5章 树

5.1 树与图的生成树

5.1.1 树的概念与性质

5.1.2 图的生成树

5.2 根树

5.2.1 根树的基本概念

5.2.2 二叉树

5.2.3 二叉树的遍历

*5.3 树的应用

5.3.1 决策树

5.3.2 二叉搜索树

5.3.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 推理规则

本章小结

习题六

第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.4 谓词逻辑的推理理论

本章小结

习题七

第四篇 组合数学

第8章 组合数学

8.1 基本计数原理

8.1.1 加法原理

8.1.2 乘法原理

8.2 排列与组合

8.2.1 排列

8.2.2 组合

*8.2.3 广义的排列与组合

8.3 二项式系数与组合恒等式

8.3.1 二项式系数

8.3.2 组合恒等式

*8.4 鸽笼原理

8.4.1 鸽笼原理的简单形式

8.4.2 鸽笼原理的一般形式

*8.5 递归关系及其解法

8.5.1 递归关系的定义

8.5.2 逆向代换法

8.5.3 常系数齐次线性递归关系

8.5.4 常系数非齐次线性递归关系

本章小结

习题八

第五篇 代数系统

第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.3.3 子群与陪集

9.3.4 循环群与置换群

9.4 环与域

9.4.1 环与域的概念

*9.4.2 环与域的性质

9.5 格与布尔代数

9.5.1 格的概念与性质

9.5.2 分配格、有补格

9.5.3 布尔代数

本章小结

习题九

附录A

参考文献

离散数学是计算机科学基础理论的核心课程，也是现代数学的一个重要分支。这本《离散数学》由张辉、张瑜、孙宪坤编著，包含了集合论、图论、数理逻辑、组合数学、代数系统等内容。在介绍离散数学主要内容的同时，对相关知识的专业应用也做了实用性介绍。
《离散数学》适合作为计算机和相关专业本科生“离散数学”的教学用书，也可以作为对离散数学感兴趣的学生的参考书。

这本《离散数学》由张辉、张瑜、孙宪坤编著，具有以下特色：
·注重应用，理论知识与后继课程中相关应用的介绍结合紧密，使学生充分领略离散数学的重要作用；
·内容讲述力求严谨，推演和求解务求详尽，注重培养学生的数学思维能力和分析、解决问题的能力；
·取材和组织注重传统与新颖的结合，基础理论的介绍突出重点，以“够用”为限，淡化繁琐、特殊的证明技巧；
·通过丰富多样的典型例题分析，使学生对所学知识的掌握更加系统化和条理化，更易于对所学知识融会贯通和举一反三；
·注重巩固学生所学知识，培养学生的实践能力，书中每一章都安排了一定量的习题。