本书内容包括离散数学四大支柱的基础理论：数理逻辑、集合论、代数系统和图论。兼顾学生考研的需要，简单介绍了组合数学和粗糙集理论及其应用。本书与同类教材相比，内容精炼，注重理论的思想，单薄理论的证明；加强应用，强调理论与实际相结合，在实践中理解理论的精髓；有的放矢，强化部分重要内容，压缩课时。

离散数学
张清华 蒲兴成 尹邦勇 刘勇 编著
本教材是编者在学校离散数学重点课程建设的基础上，依据工科学生特别是计算机科学与技术专业学生的特点，参考并借鉴国内外众多教材的优势和特点，结合自己多年的教学和科研成果编写而成的。本书在力求介绍离散数学基础知识的前提下，简明扼要、通俗易懂地介绍相关内容，注重理论联系实际，融入启发式教学理念，使得教师教学和学生自学浑然一体，着重培养学生的创新能力和自学能力。

本书特点
内容深入浅出，结构安排合理，知识点脉络清晰，讲解通俗易懂。
基础理论与相关实际问题相结合，变抽象思维为形象思维，提高学生创新和自学能力。
每个部分结束后给出小结，以便学生及时复习，掌握知识点和知识结构。
重点突出解题思路，注重培养学生的数学思维能力和分析、解决问题的能力。
编写的内容突出重点，便于工科学生考研复习。

离散数学，是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。该课程是以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。离散数学是随着计算机科学的发展而逐步建立的，它形成于20世纪70年代初期，是一门新兴的工具性学科。近年来，计算机科学与技术正在以惊人的速度发展，对人类社会的各个领域产生着日益广泛和深入的影响。计算机科学之所以能取得这样辉煌的成就，与其具有雄厚的理论基础——离散数学是分不开的。该课程与计算机科学中的数据结构、操作系统、编译理论、数据库系统、人工智能、计算机网络、算法分析、逻辑设计、系统结构、容错诊断、机器定理证明等理论课程联系紧密。通过离散数学的学习，不但可以掌握处理离散问题的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
　　本教材是在编者10多年离散数学教学经验的基础上，结合工科学生特别是计算科学与技术专业学生的特点，在学校离散数学重点课程建设的基础上，参考了国内众多教材的优势并借鉴国外教材的特点，结合自己多年的教学和科研成果编写而成的。本书在力求介绍离散数学基础知识的前提下，简明扼要、通俗易懂地介绍相关内容，注重理论联系实际，融入启发式教学理念，使得教师教学和学生自学浑然一体，着重培养学生的创新能力和自学能力。本书的特点如下：
　　 内容深入浅出，结构安排合理，知识点脉络清晰，讲解通俗易懂。
　　 基础理论与相关实际问题相结合，变抽象思维为形象思维，提高学生创新和自学能力。
　　 每个部分结束后给出小结，以便学生及时复习，掌握知识点和知识结构。
　　 重点突出解题思路，注重培养学生的数学思维能力和分析、解决问题的能力。
　　 编写的内容突出重点，便于工科学生考研复习。
　　全书共分为四部分。本书第一部分由张清华编写，第二部分由尹邦勇编写，第三部分由刘勇编写，第四部分由蒲兴成编写。第一部分是数理逻辑，分为两章，第1章介绍命题逻辑，第2章介绍一阶谓词逻辑；第二部分是集合论初步，分为两章，第3章介绍集合，第4章介绍二元关系与函数；第三部分是代数结构，分为两章，第5章介绍代数系统，第6章介绍几个典型的代数系统；第四部分是图论，主要介绍图论的初步知识。
　　本书不仅可以作为高等院校计算机科学与技术、软件工程等相关专业的教材，也可以作为考研和计算机工作者的参考书。
　　本书的出版得到重庆邮电大学离散数学教材立项资助，并获得重庆邮电大学信息与计算科学专业提升计划和数理学院教改项目的资助。全书的内容修改和出版还得到杨春德、胡学刚、虞继敏、郑继明、吴慧莲、刘显全、何承春等老师的支持和帮助。特别感谢吴慧莲老师为本书提出的宝贵修改意见和建议。感谢为本书出版作出积极贡献和支持的同志们！最后，还要特别感谢机械工业出版社的大力支持，使得本书得以顺利出版。
　　本书主要内容虽然在教学中多次讲授，但由于水平所限，加之时间仓促，书中难免有不妥或错误之处，恳请广大读者批评指正。
编者
2010年4月于重庆

计算机\离散数学

本教材是在学校离散数学重点课程建设的基础上，结合工科学生特别是计算科学与技术专业学生的特点，参考了国内众多教材的优势并借鉴国外教材的特点，结合自己多年的教学和科研成果编写而成的。本书在力求介绍离散数学基础知识的前提下，简明扼要、通俗易懂地介绍相关内容，注重理论联系实际，融入启发式教学理念，使得教师教学和学生自学浑然一体，着重培养学生的创新能力和自学能力。本书的特点如下：
◆内容深入浅出，结构安排合理，知识点脉络清晰，讲解通俗易懂。
◆基础理论与相关实际问题相结合，变抽象思维为形象思维，提高学生创新和自学能力。
◆每个部分结束后给出小结，以便学生及时复习，掌握知识点和知识结构。
◆重点突出解题思路，注重培养学生的数学思维能力和分析、解决问题的能力。
◆编写的内容突出重点，便于工科学生考研复习。

前言
教学建议
第一部分数理逻辑
第1章命题逻辑
11命题及联结词
11 1命题及其表示
11 2命题联结词
12命题公式与真值表
121命题公式
122命题公式的分类
13命题公式的范式与主范式
14联结词的完备集
15命题推理理论
习题1
第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4谓词公式的等值演算
25谓词公式的前束范式
26谓词演算的推理理论
261推理定律的来源
26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3集合恒等式
331运算律
332集合恒等式的证明
习题3
第4章二元关系和函数
41二元关系
411笛卡儿积
412二元关系的概念
413二元关系的表示
42关系的运算
421二元关系的域
422逆运算
423复合运算
424幂运算
43关系的性质
431性质的定义
432性质的判定
44关系的闭包
441闭包的定义
442闭包的生成
45等价关系与偏序关系
451等价关系
452偏序关系
46函数
461函数概念
462函数复合
463逆函数
47集合的基数
471可数集合
472集合的势
习题4
第二部分小结
第三部分代数结构
第5章代数系统
51二元运算及其性质
52二元运算中的特殊元素
521幺 元
522零元
523逆元
53代数系统
习题5
第6章几个典型的代数系统
61半群与群
62陪集与拉格朗日定理
6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
第三部分小结
第四部分图论
第7章图论基础
71图的一些基本概念
72欧拉图和哈密尔顿图
73树
74平面图
75独立集、覆盖集与匹配
习题7
第四部分小结
附录A数理逻辑部分典型例题与求解分析
附录B集合论部分典型例题与求解分析
附录C代数结构部分典型例题与求解分析
附录D图论部分典型例题与求解分析
参考文献