本书共分为数理逻辑、关系、图论、代数系统及组合分析初步5个部分，其中包括命题逻辑、谓词逻辑、非经典逻辑、集合、二元关系、函数、图论、代数系统以及组合计数等内容。本书既注重各部分内容之间的联系，又注重基础理论及其实际应用。各章配有小结及大量的例题分析，除第2章外每章配有两套习题，习题一供学习者熟悉本章概念、理论和方法；  习题二供学习者进行自我检测。

本书可作为高等院校计算机及其相关专业的本科生、研究生教材，也可供从事计算机工作的科学技术人员以及相关人士使用或参考，还可用作大学毕业生的考研复习用书。

在IEEE和ACM共同起草的关于计算学科教学计划（Computing Curricula）2001中将离散结构列为计算学科14个主领域的第一个主领域，这说明了离散结构在计算科学中的重要地位，它是计算机科学与技术基础理论的核心学科。

“离散数学”课程为计算机科学各分支领域解决其基本问题提供了强有力的数学工具。作为各类计算机专业和相关专业的一门核心骨干课程，其主要任务是培养学生的抽象思维能力和逻辑推理能力，并为后续课程，如数据结构、编译原理、数据库原理、人工智能等提供必要的数学基础，为学生今后的继续学习、工作和研究提供必要的数学基础。

本教材较全面地介绍了计算机科学与技术专业及相关专业所需要掌握的离散结构的知识。全书分为数理逻辑、关系、图论、代数系统及组合分析初步5个部分，包括了离散数学结构的主要知识体系的基础和多个分支。内容力求通俗、易懂、简明扼要，既注重各部分内容之间的联系，又注重基础理论及其实际应用，特别注重对学生的计算机离散数学运算能力的培养和训练。书中每一章都有典型例题分析和小结，小结总结了本章基本概念，并指出重点、难点。除第2章外每章配有两套习题，习题一供学习者熟悉本章概念、理论和方法；  习题二有自测题性质，供学习者进行自我检测，完成后可用书后解答进行自我评判。书中内容有助于培养学生严谨科学的思考推理能力，通过练习和自测及时了解自己对课程的掌握程度，以便实时调节学习进度，从而不断提高分析与解决问题的能力。因此，本书适合于自学。

本书可作为高等院校计算机及其相关专业的本科生、研究生教材，也可作为自动化、电子信息工程、测量技术与仪器、管理科学与工程、系统科学与工程等专业的本科生、研究生教材，还可供从事计算机工作的科学技术人员以及相关人事使用或参考，也可用作大学毕业生的考研复习用书。

全书包含大约可在120个学时内讲授的内容，使用时可根据不同需要，考虑删选带“*”的章、节及习题。如果删除带“*”的章、节，则可以在60～80学时内完成教学。对于计算机专业的本科生，未带“*”的章、节是必学内容。

本书框架由昆明理工大学的吴晟和郭洪讨论制定，吴晟完成第5、6、10、11章的编写，郭洪完成第1、2、7、8章的编写，云南大学的王亚完成第9章的编写，昆明理工大学的周海河完成第3、4章的编写。本书中的插图均为昆明理工大学的刘泓滨完成，全书由吴晟统稿并定稿。

在本书编写过程中，参阅了许多国内外离散数学教材和相关文献资料，从中吸取了不少有用的素材，在此一并向有关作者表示感谢。感谢作者所在学校院、系领导在编写过程中给予的支持，感谢清华大学出版社的大力支持，使本书得以顺利出版。另外，对在书稿编写过程中进行部分录入等工作的昆明理工大学在校硕士研究生赵莉楠、许兵、蔡灿民表示感谢。

限于作者水平，书中不当和疏漏之处在所难免，敬请同行与读者不吝指正。特别期待使用本书作教材的教师和学生对本书的批评、指正和建议。

编者

2007年4月

第1章数理逻辑

1.1命题及命题联结词

1.1.1命题

1.1.2命题联结词

1.1.3命题的符号化

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.4谓词公式及谓词公式之间的逻辑关系

1.4.1谓词逻辑中的合法符号

1.4.2项

1.4.3谓词公式

1.4.4有关谓词公式的概念

1.4.5谓词公式的解释

1.4.6谓词公式的分类

1.4.7谓词公式之间的逻辑关系

1.5范式

1.5.1主析（合）取范式

1.5.2前束范式

1.6数理逻辑推理理论

1.6.1命题逻辑推理理论

1.6.2谓词逻辑推理理论

*1.7命题逻辑推理系统N

1.7.1什么是形式系统

1.7.2命题逻辑推理系统N

1.7.3N中的一些基本定理

*1.8谓词逻辑推理系统NL

1.8.1NL的构造

1.8.2NL中的形式证明

1.8.3NL中的一些基本定理

小结

习题一

习题二

*第2章非经典逻辑介绍

2.1模态逻辑

2.1.1模态

2.1.2模态命题的形式化

2.1.3模态命题形式之间的逻辑关系

2.2多值逻辑

2.2.1卢卡西维茨的多值逻辑系统

2.2.2另外一些多值逻辑系统

2.3非单调逻辑

2.4模糊逻辑

2.5道义逻辑

2.5.1道义逻辑系统

2.5.2道义逻辑的等值式与蕴含式

小结

习题一

第2篇关系

第3章集合基础

3.1集合的概念和表示法

3.1.1集合与元素

3.1.2集合的表示

3.2集合的关系

3.2.1元素的属于关系

3.2.2集合的包含关系

3.2.3集合的相等关系

3.2.4空集

3.2.5全集

3.2.6幂集

3.3集合的基本运算

3.3.1集合的并（∪）、交（∩）

3.3.2集合的差集（-）和绝对补集（~）

3.3.3集合的对称差集（⊕）

3.3.4集合运算的基本性质

3.4包含排斥原理

小结

习题一

习题二

第4章关系

4.1笛卡儿积与序偶

4.2二元关系的定义和表示

4.2.1二元关系的定义

4.2.2几种特殊关系

4.2.3几种常用的关系

4.2.4关系的表示法

4.3关系的运算

4.3.1定义域、值域、域

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

4.3.3关系逆运算

4.3.4关系的复合运算

4.3.5关系运算的性质

4.3.6关系的幂运算

*4.3.7特殊关系运算

4.4关系的性质

4.5关系的闭包

4.5.1关系闭包的定义

4.5.2关系闭包的构造

4.5.3关系闭包的性质

4.6等价关系与集合的划分

4.6.1集合的覆盖和划分

4.6.2等价关系

4.6.3等价类和商集

4.7偏序关系与偏序集

4.7.1偏序关系的定义

4.7.2序关系

4.7.3偏序关系的哈斯图

4.7.4偏序集中的特殊元素

小结

习题一

习题二

第5章函数

5.1函数的概念

5.2函数的性质

5.3函数的运算

小结

习题一

习题二

第3篇图论

第6章图论中的基本概念

6.1图与图形

6.2图论中的术语

6.2.1一些图的基本概念和常用术语

6.2.2子图

6.2.3补图

6.3同构

6.4图的连通性

6.4.1通路和回路

6.4.2无向图的连通性

6.4.3有向图的连通性

6.5图的矩阵表示

6.5.1有向图的邻接矩阵

6.5.2有向图的可达矩阵

6.5.3无向图的关联矩阵

小结

习题一

习题二

第7章特殊图

7.1欧拉图

7.2哈密尔顿图

7.3二部图

7.4平面图

7.4.1平面图的基本概念

7.4.2欧拉公式

7.4.3图的可平面性

7.5无向树

7.5.1无向树的概念及性质

7.5.2最小生成树

7.6根树

*7.7图的应用

7.7.1计算机鼓轮设计

7.7.2巡回售货员问题

7.7.3关键路径问题

7.7.4通信网络

7.7.5前缀码问题

小结

习题一

习题二

第4篇代 数 系 统

第8章代数系统

8.1代数运算及性质

8.1.1代数运算

8.1.2代数系统的定义

8.1.3几个特殊的代数系统

8.2二元运算的性质

8.3代数系统中的特殊元素

8.3.1幂等元和消去元

8.3.2幺元

8.3.3零元

8.3.4逆元

8.4同态与同构

小结

习题一

习题二

第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.3格与布尔代数

9.3.1格的概念

9.3.2同构格

9.3.3格的性质

9.3.4特殊的格

9.3.5布尔代数

小结

习题一

习题二

*第5篇组合分析初步

第10章排列与组合

10.1加法原理与乘法原理

10.1.1加法原理

10.1.2乘法原理

10.1.3加法原理与乘法原理的应用

10.2排列与组合

10.2.1集合的排列

10.2.2集合的组合

10.2.3多重集的排列

10.2.4多重集的组合

小结

习题一

习题二

第11章鸽巢原理

11.1鸽巢原理

11.1.1问题的引入

11.1.2鸽巢原理的基本形式

11.1.3鸽巢原理的推广

11.2鸽巢原理的应用

11.2.1制造鸽巢是应用鸽巢原理的关键

11.2.2较复杂问题举例

小结

习题一

习题二

附录

各章习题二答案

参考文献