本书是根据清华大学出版社与中国计算机学会共同规划的“21世纪大学本科计算机专业系列教材”《离散数学（第3版）》(主教材)以及电子教案编写的配套教学指导用书.全书分为14章，每章包含内容提要、习题、习题解答与分析三部分.内容提要总结了本章的主要定义、定理、公式、重要的结果等；习题部分包含了与上述内容配套的数十道题；习题解答与分析部分不但对上述习题给出了详细的解答，而且对一些典型的解题方法做了比较深入的分析和总结.总计超过500道题，涵盖了数理逻辑、集合论、图论、组合数字、数论、离散概率、代数结构等不同模块的基本内容和典型的解题方法.

本书既可以作为主教材的配套教学用书，也可以单独使用，为学习离散数学的读者在解题能力和技巧的训练方面提供有益的帮助。

第3版FOREWORD作为清华大学出版社的21世纪大学本科计算机专业系列教材之一，《离散数学习题解答与学习指导》(第2版)已经出版5年了.在这5年里，一些新的教育理念、教学模式不断提出并加以实践，其中最重要的是“计算思维（computational thinking）”和“大规模开放式在线课程(massive open online course,MOOC)”.计算思维是数学思维与工程思维的互补与融合，不但是从事计算机科学技术工作的人所需要的专业素质，也对其他学科的发展产生了深远的影响，计算思维的培养已经成为大学计算机专业的重要目标之一.MOOC教学模式近年来在国外迅速增长，已经产生了巨大的影响；国内也把教学资源共享列入国家计划并给予了大力支持. 这些新的教育理念和教学模式对教材的修订有着重要的影响. 

离散数学是研究离散结构及其性质的学科，大量用于计算机系统及其应用领域的建模及分析. 离散数学对培养计算思维起着重要的作用，不但被列入计算机专业的核心课程，而且近年来电子工程、经济学等专业领域也开始在教学中加入一些离散数学的内容. 如何在离散系统建模中体现计算思维是本教材修订的指导思想. 本着对读者负责的精神，我们在这次修订中认真地审阅了原书，对其中的部分内容做了调整，更正了某些错误和疏漏之处，并对文字做了进一步的精细加工. 主教材的更新说明如下：   

对第1章“数学语言与证明方法”做了部分重写，对重要的数学证明方法进行了分类和较详细的阐述，补充了有关递归定义的内容. 第5章补充了关系与函数在数据库及软件工程建模中的应用实例. 第6章增加了二部图的匹配、着色和四色定理. 第7章删除了基本回路与基本割集系统. 第10章对递推方程在算法设计与分析中的应用加以补充.  

与主教材配套，本教学辅助用书也对上述内容做了同步更新. 

为了提高本书的质量，欢迎大家批评指正. 对广大读者的建议和意见，我们表示衷心的感谢！

作者[]2013年8月于北京大学第2版FOREWORD作为清华大学出版社和中国计算机学会共同规划的“21世纪大学本科计算机专业系列教材”之一，这本《离散数学习题解答与学习指导》已经出版两年了.在这两年的时间里，教育部推出了一系列为提高高等学校本科生教育质量的重要举措.特别是今年年初发布的《教育部、财政部关于实施高等学校本科教学质量与教学改革工程的意见》（教高［2007］1号）和《教育部关于进一步深化本科教学改革，全面提高教学质量的若干意见》（教高［2007］2号），对专业设置、教学模式、课程建设、师资队伍等各个方面不但提出了更高的建设目标，也为保证这一工程的顺利执行提供了有力的保证.

好的教师和好的教材是保证教学质量的前提条件.本着对读者负责的精神，我们在这次修订工作中认真地审阅了原书，根据教学要求对其中的部分内容做了调整，更正了某些错误和疏漏之处，并对文字做了进一步的加工.内容上主要做了如下改动：

与主教材配套，去掉了数理逻辑中有关“一阶逻辑推理理论”的内容.主要原因是： 这部分内容涉及形式系统.形式系统在系统定义和推理中应该采用完全形式化的方法，通常包含形式语言以及用形式语言表述的公理和推理规则.在形式系统中，符号串本身是没有语义的，只能通过解释赋予它们一定的语义，但在讨论系统的公理或推理规则时应该与语义无关.本书在第1版的叙述中没有完全采用这种形式化的方法.如果从知识体系的严谨性出发，应该采用这种完全形式化的表述方法.但是，这不但与本书的整体写作风格不够协调，而且内容也偏深，超出本教材的要求，因此本次修订决定删掉这部分内容.

为了进一步提高本书的质量，我们恳切地欢迎读者继续提出建议和意见.

作者[]2007年11月于北京大学第1版FOREWORD离散数学是研究离散量的结构及其相互关系的数学学科. 美国ACM和IEEE Computing Curricula 2005 (CC2005)与我国教育部高教司主持评审的《中国计算机科学与技术学科教程2002》（CCC2002）都把离散数学列为计算机科学与技术专业的核心课程. 通过离散数学的学习，不但可以使学生掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且能够提高学生的数学素养，培养抽象思维和严格的逻辑推理能力，对将来参与创新性的研究和开发工作也是非常有益的.

离散数学具有数学类课程的内容抽象、体系严谨、逻辑性强、习题量大、解题思路灵活多变等特征，除此之外还有它自己的特点，主要体现如下：

 概念多，定理多，知识点比较散，概念容易混淆，不太容易掌握知识点之间的内在联系与知识体系.

 数理逻辑、集合论、图论、组合数学、数论、离散概率、代数结构等各部分内容分别来自不同的数学分支，所采用的数学模型和处理方法差别较大，特别是解题的思路和技巧有着明显的区别.

 在学习中要用到初等数学、微积分、线性代数等多门课程中的相关的概念与结果.

 与计算机专业的其他课程，如数据结构、编译技术、人工智能、信息安全、算法设计与分析、数据库原理、网络技术等联系紧密，应用背景较强.

由于这些特点，初学者往往会感到比较困难，特别是拿到题目后不知道如何着手. 为了帮助学生更好地掌握这门课程，我们在多年教学实践和大量习题资料积累的基础上，编写了这本《离散数学习题解答与学习指导》.

本书与清华大学出版社出版的中国计算机学会“21世纪大学本科计算机专业系列教材”《离散数学（第2版）》（主教材）以及配套的电子教案一起构成了立体化离散数学系列教材. 全书分为14章，与主教材中的章对应. 每章包含内容提要、习题、习题解答与分析三部分. 内容提要总结了本章的主要定义、定理、公式、重要的结果等；习题部分包含与上述内容配套的数十道题；习题解答与分析部分不但对上述习题给出了比较详细的解答，而且对一些典型的解题方法做了比较深入的分析和总结. 解答的习题（大题）总计超过500道，涵盖了数理逻辑、集合论、图论、组合数学、数论、离散概率、代数结构等各个不同离散数学模块的基本内容和典型的解题方法. 全书内容丰富，概念清晰，讲解翔实易懂，通过不同解法的对比与分析，进一步加强了解题技巧的训练，同时本书习题中也选择了计算机科学技术中的典型应用实例，以增加理论联系实际的感性认识.

本书既可以作为主教材的配套教学用书，也可以单独使用，为学习离散数学的其他读者在解题能力和技巧的训练方面提供有益的帮助.第一版〖〗〖〗〖〗离散数学习题解答与学习指导（第3版）〖〗

本书的第1、2、3、6、7章由耿素云编写，第4、5、8、9、10、14章由屈婉玲编写，第11、12、13章由张立昂编写.

在本书编写过程中参考了国内外多种版本的离散数学教材和相关的文献资料，本书的出版也得到21世纪大学本科计算机专业系列教材编委会与清华大学出版社的大力帮助，在此表示衷心的谢意. 由于水平所限，错误和疏漏之处期待着读者的批评指正.作者[]2005年10月于北京大学

第1章数学语言与证明方法1

1.1内容提要1

1.2习题3

1.3习题解答与分析7

第2章命题逻辑17

2.1内容提要17

2.2习题20

2.3习题解答与分析25

第3章一阶逻辑50

3.1内容提要50

3.2习题51

3.3习题解答与分析55

第4章关系68

4.1内容提要68

4.2习题72

4.3习题解答与分析76

第5章函数81

5.1内容提要81

5.2习题82

5.3习题解答与分析85

第6章图89

6.1内容提要89

6.2习题92

6.3习题解答与分析98

第7章树及其应用116

7.1内容提要116

7.2习题117

7.3习题解答与分析119

第8章组合计数基础128

8.1内容提要128

8.2习题131

8.3习题解答与分析133

第9章容斥原理140

9.1内容提要140

9.2习题141

9.3习题解答与分析142

第10章递推方程与生成函数148

10.1内容提要148

10.2习题157

10.3习题解答与分析160

第11章初等数论173

11.1内容提要173

11.2习题174

11.3习题解答与分析178

第12章离散概率191

12.1内容提要191

12.2习题193

12.3习题解答与分析196

第13章初等数论和离散概率的应用210

13.1内容提要210

13.2习题210

13.3习题解答与分析213

第14章代数系统219

14.1内容提要219

14.2习题226

14.3习题解答与分析230

参考文献238