第3版前言FOREWORD



席南华院士在一次报告中提出： 数学的美的含义无疑和其他的美（如艺术等）在形式美上有一些共性，但更多的还是一种思维和逻辑的美，智慧的美，有自己的特质。每个人对数学的美的理解是不一样的，但下面的看法有助于把握数学的美的部分含义： ①形式方面清晰、简洁、简单、原创、新颖、优美； ② 内涵方面深刻、重要、基本、蕴意丰富； ③证明方面清晰、干净利落、巧妙。
离散数学是研究离散量的结构及其相互关系的数学学科。基于离散数学结构，研究基于离散量的结构和相互间的关系，具备上述数学的美的特征。离散数学是计算机类专业的重要理论基础，也是计算机类专业的专业课程的先修课程。通过学习数理逻辑、集合论、代数系统和图论的基本概念和基本原理，使学生理解离散结构之间的关系和基于这些离散结构的算法，建立起现代数学关于离散结构的观点，掌握处理离散量的一些数学方法，并形成逻辑推理和抽象思维的能力，以及用计算机算法描述世界的建模能力，为“数据结构”和“算法设计与分析”课程奠定坚实的基础，为学习“数字逻辑”“数据库系统原理”“操作系统”“计算机网络”“人工智能”等课程提供数学处理工具。
关于抽象
数学思维的抽象，在于剥离具体。数学研究从公理出发，可以变成纯思维的活动，和具体的现实脱离关系。数学上人为的“定义”和“创造”，就是为了尽可能地给出范围明确、不冗余的信息抽象。然后再利用这些信息，通过逻辑证明，得出范围明确、不冗余的抽象结论，接着这些结论就扩展了人为的“定义”和“创造”，以后就可以推理、证明出更多的结论，如此反复。可见，数学需要的是一个自洽的信息结构和关系，并且这些信息是架空具体和现实的。虽然，数学在极力地探索结构、寻找关系，但这个行为发生在有限范围内，即发生在由层层已知的定义和定理圈定的护栏内。
计算思维的抽象，在于两个A（abstraction和automation）。计算思维的第一个A是指对现实世界的模型化和数字化；第二个A是对问题求解的计算过程自动化。第一个A可以理解为是在数学思维的基础上，为第二个A做了适当的专门设计，是数学思维的应用；第二个A可以理解为现实问题的、在相应数学模型约束下的求解过程自动化。计算机是用来模拟现实和解决现实问题的。所以，计算思维是和现实极为紧密的，而现实的关系又是错综复杂的。我们无法避免信息的冗余，乱入的信息会随机出无法意料的自由组合。这也就是为什么说数学的正确和错误清晰而明确，但计算机却无法保证绝对的正确，只能说目前没有错误——缺陷（Bug）会永远存在，且需要不断地修复。因为现实变化了，计算机映射的思维模型就必须跟着变化。
可见，数学思维的抽象——服务于寻找逻辑和证明猜想，而计算思维的抽象——服务于解决现实问题和提高模拟现实的程度。这两种抽象思维的相似之处都是为了找到事物之间的本质关联；而不同之处就在于，计算思维需要有对生活的理解，有对现实问题的体验经历，并且和个人品位生活的能力息息相关，而数学思维则对现实生活的要求不高。
关于编程和数学
成为伟大的程序员是计算机专业学生的终极目标。伟大的程序员必须具备深厚的数学功底。从广义上说，程序设计必须包含4方面： ①模糊现实问题的形式化和精确定义，我们称之为现实问题向计算问题的转化； ②严格数学模型的建立，我们称之为数据结构的理论建模； ③数学模型上的规律运用和问题求解，我们称之为算法设计的“不忘初心”； ④精简代码的实现，我们称之为自动计算的依据。在这4方面中，数学的奠基性作用毋庸置疑。
编程和数学在思维的本源上有相似性和共同性——编程语言与数学语言。但编程和数学不同的思维模型，说明了它们在上层需要构建各自不同的技能树。而学习和掌握一个技能点需要花时间练习，从而在大脑中训练出特定的结构。所以，编程与数学不可能做到学一个，另一个就自然而然地掌握了。但两者的依赖关系是： 编程强依赖数学，数学弱依赖编程。
离散数学解题指导（第3版）第3版前言另外，纵然数学是工具，是基础，是上层的依赖，但并不是说，数学就高于一切，优于一切，是最强大的。
本书第3版增加了编程内容。在课程实践中主要强化两方面： ①传统“离散数学”的课程作业以推导公式，以解决小规模问题为主。在智能时代，数据集规模和问题的复杂程度都急剧增加，学生需掌握利用计算机解决复杂问题，以及推导证明的能力。以计算为模型学习离散数学知识。②“离散数学”是多门学科的先修课程，课程所学知识也将应用于后续专业课程的学习。在教学过程中需从数学的应用和专业课需求两方面寻找结合点，强化数学课程对专业课的支撑作用。以离散数学为模型解决应用问题。
Python语言具有简洁性、易读性、可扩展性，并带有一定的函数式程序设计特点。在教学过程中，可以使用Python语言加强离散数学的学习效果。教师可将计算作为认知的方法，包括：①在计算表征方面,Python表征概念、运算、关系； ②在计算认知方面，Python随机生成对象、计算判断性质、计算验证定理；③通过Python编程加深理解数学语言。
开设建议
“离散数学”是计算机类专业的一门重要的专业基础课程。它在计算机类专业中有着广泛的作用，是计算机类专业的必修课。各高校在开设该课程时可以根据生源质量及培养目标、培养方案调整以下教学内容。
（1） 依据学生的培养目标和从事的岗位，对数学基础知识的掌握程度有所区分。侧重研究的学生（或专业）可适当增加“离散数学”课程的课时，强化图论、代数系统、数论等方面的知识，并提高学生对定理证明和逻辑推导的要求；侧重工程的学生（或专业）需加强离散数学应用、问题求解的能力要求，降低对定理证明的要求；侧重应用的学生（或专业）可将离散数学的知识点与计算机语言相结合，通过Python等语言解决数学问题，对于定理证明不做过多要求。
（2） 从培养方案的角度，“离散数学”应结合各专业的课程设置调整内容。智能计算中的应用实例应结合后续课程选择。另一方面，后续课程中将详细讲解的内容（如图论、概率等）可以适当减少课时。
增加编程实践，能够使学生具有4个优势： ①有了较为深入的问题求解、算法和代码的经验； ②已经涉足一些重要的计算机科学概念，例如递归、排序、搜索以及基本的数据结构；③初步掌握了相关计算机科学知识，包括一些启发性的例子，或者其他容易理解的简单例子；④深刻理解数学概念、数学模型和数学规律在计算机上的运行。
本书第3章、第4章和第7章由袁景凌编写，谢茜参与了部分应用案例的编写；其余章节由贲可荣、谢茜编写；编程答案由谢茜完成；贲可荣组织了本书的编写，并进行统稿和定稿。南京大学陶先平教授对全书进行了审读，提出了许多建设性意见，参与了第3版序的撰写，总结了本书特色，特此致谢。感谢参考文献的相关作者，欢迎读者对本书提出修改建议。贲可荣
2023年1月6日第2版前言FOREWORD张恭庆院士在“数学的意义”一文中指出： 数学既是一种文化、一种“思想的体操”，更是现代理性文化的核心。数学的基本特征是高度的抽象性和严密的逻辑性，应用的广泛性与描述的精确性，以及研究对象的多样性与内部的统一性。
数学是一门“研究数量关系与空间形式”的学科。通常根据问题的来源把数学分为纯粹数学与应用数学。研究其自身提出的问题的数学是纯粹数学；研究来自现实世界中的数学问题的数学是应用数学。利用建立数学“模型”，使得数学研究的对象在“数”与“形”的基础上又有扩充。各种“关系”，如“语言” “程序” “DNA排序” “选举” “动物行为” 等都能作为数学研究的对象。纯粹数学与应用数学的界限有时也并不那么明显。一方面，由于纯粹数学中的许多对象追根溯源是来自解决外部问题时提出来的；另一方面，为了研究从外部世界提出的数学问题有时需要从更抽象、更纯粹的角度来考察才有可能解决。
数学作为现代理性文化的核心，提供了一种思维方式。这种思维方式包括： 抽象化、运用符号、建立模型、逻辑分析、推理、计算，不断地改进、推广，更深入地洞察内在的联系，在更大范围内进行概括，建立更为一般的统一理论等一整套严谨的、行之有效的科学方法。按照这种思维方式，数学使得各门学科的理论知识更加系统化、逻辑化。
离散数学是数学里专门用来研究离散对象的一个数学分支，是计算机专业一门重要的基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。全书共10章，主要包含数理逻辑、集合与关系、函数、图和树、组合计数、离散概率、数论与递归关系、代数系统、自动机、文法和语言等内容。基本涵盖了计算机专业必须掌握的数学内容。“离散数学”这门课程，主要介绍各分支的基本概念、基本理论和基本方法，这些知识将应用于“数字电路”“编译原理”“数据结构”“操作系统”“数据库原理”“算法分析与设计”“人工智能”“软件工程”“计算机网络”等专业课程中。
电子计算机从设想、理论设计、研制一直到程序存储等过程，数学家在其中都起到决定性的主导作用。从理论上哥德尔创建了可计算理论和递归理论，图灵第一个设计出通用数字计算机，他们都是数学家。冯·诺依曼是第一台电子计算机的研制者，是程序和存储的创建人，也是数学家。
信息科学与数学的关系最为密切。信息安全、信息传输、计算机视觉、计算机听觉、图像处理、网络搜索、商业广告、反恐侦破、遥测遥感等都大量地运用了数学技术。高性能科学计算被认为是最重要的科学技术进步之一，也是21世纪发展和保持核心竞争力的必需科技手段。例如，核武器、流体、星系演化、新材料、大工程等的计算机模拟都要求高性能的科学计算。应用好高性能计算机解决科学问题，基础算法与可计算建模是关键。
信息的“加密”与“解密”是一种对抗，而这种对抗力量的表现全在所依靠的数学理论之上。例如，公开密钥算法大多基于计算复杂度很高的难题，要想求解，需要在高速计算机上耗费许多时日才能得到答案。这些方法通常来自于数论。RSA源于整数因子分解问题，DSA源于离散对数问题，而近年发展快速的椭圆曲线密码学则基于与椭圆曲线相关的数学问题。
人们利用观察和试验手段获取数据，利用数据分析方法探索科学规律。数理统计学是一门研究如何有效地收集、分析数据的学科，它以概率论等数学理论为基础，是“定量分析”的关键学科。大数据事实上已成为信息主权的一种表现形式，将成为继边防、海防、空防之后大国博弈的另一个空间。“大数据”的核心是将数学算法运用到海量数据上，预测事情发生的可能性。
离散数学解题指导（第3版）第2版前言数学与国民经济中的很多领域紧密相关。互联网、计算机软件、高清晰电视、手机、便携式计算机、游戏机、动画、指纹扫描仪、汉字印刷、监测器等在国民经济中占有相当大的比重，成为世界经济的重要支柱产业。其中互联网、计算机核心算法、图像处理、语音识别、云计算、人工智能等IT业主要研发领域都是以数学为基础的。
严加安院士在文章“数学的奇妙： 我们身边的概率和博弈问题”中介绍了“在猜奖游戏中改猜是否增大中奖概率”问题。
这一问题出自美国的电视游戏节目“Let’s make a deal”。问题的名字来自该节目的主持人蒙提霍尔。20世纪90年代曾在美国引起广泛和热烈的讨论。假定在台上有三扇关闭的门，其中一扇门后面有一辆汽车，另外两扇门后面各有一只山羊。主持人是知道哪扇门后面有汽车的。当竞猜者选定了一扇门但尚未开启它的时候，节目主持人去开启剩下两扇门中的一扇，露出的是山羊。主持人会问参赛者要不要改猜另一扇未开启的门。问题是： 改猜另一扇未开启的门是否比不改猜赢得汽车的概率要大？答案是： 改猜能增大赢得汽车的概率，从原来的1/3增大为2/3。也许有人对此答案提出质疑，认为改猜和不改猜赢得汽车的概率都是1/2。为消除这一质疑，不妨考虑有10扇门的情形，其中一扇门后面有一辆汽车，另外9扇门后面各有一只山羊。当竞猜者猜了一扇门但尚未开启时，主持人去开启剩下9扇门中的8扇，露出的全是山羊。显然： 原先猜的那扇门后面有一辆汽车的概率只是1/10，这时改猜另一扇未开启的门赢得汽车的概率是9/10。
在离散数学教学中我们发现，通过一些应用问题的引入和求解分析，学生能够对离散数学产生兴趣，并留下深刻印象。借修订本书之际，我们对每一章均增加了应用案例，以说明相应章节知识的学习可以解决什么样的典型应用问题。
值得指出的是，我们在撰写函数、离散概率及图论章节应用案例时，选用了美国伊利诺大学刘炯朗教授“魔术中的数学”（2015年中国计算机大会报告）中的例子。命题逻辑部分的应用案例选自我的老师康宏逵先生翻译的《这本书叫什么》。
全书分为10章，每章包含内容提要、例题精选、应用案例和习题解答4部分。“命题逻辑”中的应用案例包括： 克雷格探长案卷录，忘却林中的艾丽丝（狮子与独角兽、斤斤计与斤斤较）；“谓词逻辑”中的应用案例包括： 电路领域的知识工程，基于逻辑的财务顾问；“集合与关系”中的应用案例包括： 同余关系在出版业中的应用，拓扑排序在建筑工序中的应用，等价关系在软件测试等价类划分中的应用；“函数”中的应用案例包括： 逢黑必反魔术，生成函数在解决汉诺塔问题过程中的应用；“组合计数与离散概率”中的应用案例包括： 大使馆通信的码字数，条条道路通罗马；“图论”中的应用案例包括： 网络爬虫，读心术魔术，高度互联世界的行为原理；“树及其应用”中的应用案例包括：  Huffman压缩算法的基本原理，一字棋博弈的极大、极小过程；“代数系统”中的应用案例包括： 物理世界中群的应用，群码及纠错能力；“自动机、文法和语言”中的应用案例包括： 奇偶校验机，地址分析，语音识别；“初等数论”中的应用案例包括： 密码系统与公开密钥，单向陷门函数在公开密钥密码系统中的应用。
本书既可以作为主教材的配套教学用书，也可以单独使用，为学习离散数学的其他读者在解题能力和技巧训练方面提供帮助。
本书第3章、第4章和第7章由袁景凌编写，谢茜参与了部分应用案例的编写，其余章节由贲可荣、高志华编写。于嘉维绘制了部分图形，曾杰参与了样稿校对。贲可荣组织了本书的编写，南京大学陶先平教授对全书进行了审读。本书撰写过程中参考了许多资料，特别感谢参考文献中的相关作者。同时，也欢迎读者对本书提出修改建议。贲可荣2016年3月30日第1版前言FOREWORD丁石孙（北京大学原校长）在《数学与文化》（齐民友著）序中写道“钱学森同志认为在人类整个知识系统中，数学不应被看成自然科学的一个分支，而应提高到与自然科学和社会科学同等重要的地位。”“数学不仅在自然科学的各个分支中有用，同时在社会科学的很多分支中也有用。近期随着科学的飞速发展，不仅数学的应用范围日益广泛，同时数学在有些学科中的作用也愈来愈深刻。事实上，数学的重要性不只在于它与科学的各个分支有着广泛而密切的联系，而且数学自身的发展水平也在影响着人们的思维方式，影响着人文科学的进步。总之，数学作为一门科学有其特殊的重要性。”
理性探索有一个永恒的主题“认识宇宙，也认识人类自己。”在这个探索中数学有着特别的作用。没有任何一门科学能像数学那样泽被天下。数学是现代科学技术的语言和工具，它的思想是许多物理学说的核心，并为它们的出现开辟了道路。现代科学之所以成为现代科学，第一个决定性的步骤是使自己数学化。
因为数学在人类理性思维活动中有一些特点。这些特点的形成离不开各个时代总的文化背景，同时又是数学影响人类文化最突出之点。
首先，它追求一种完全确定、完全可靠的知识。产生这个特点的原因可以由其对象和方法两方面来说明。从希腊的文化背景中形成了数学的对象并不只是具体问题，数学所探讨的不是转瞬即逝的知识，不是服务于某种具体物质需要的问题，而是某种永恒不变的东西。所以，数学的对象必须有明确无误的概念，而且其方法必须由明确无误的命题开始，并服从明确无误的推理规则，借以达到正确的结论。通过纯粹的思想竟能在认识宇宙上达到如此确定无疑的地步，当然会给一切需要思维的人以极大的启发。人们自然会要求在一切领域中这样去做。一切事物的概念都应该明确无误，绝对不允许偷换概念，作为推理出发点的一组命题必须清晰，推理过程的每一步骤都不容许有丝毫含混，整个认识和理论必须前后一贯而不允许自相矛盾。正是因为这样，而且也仅仅因为这样，数学方法既成为人类认识方法的一个典范，也成为人在认识宇宙和人类自己时必须持有的客观态度的一个标准。就数学本身而言，达到数学真理的途径既有逻辑的方面，也有直觉的方面。但是，就其与其他科学比较而言，就其影响人类文化的其他部门而言，数学的逻辑方法是最突出的。这个方法发展成为人们常说的公理方法。迄今为止，人类知识还没有哪一个部门应用公理方法获得像数学那样大的成功。当然，我们也看不出为什么其他知识部门需要这样高标准的公理化。
数学作为人类文化组成部分的另一个特点是它不断追求最简单的、最深层次的、超出人类感官所及的宇宙的根本。所有这些研究都是在极抽象的形式下进行的。这是一种化繁为简、以求统一的过程。从古希腊起，人们就有一个信念，冥冥之中最深处宇宙有一个伟大的、统一的而且简单的设计图，这是一个数学设计图。在一切比较深入的科学研究后面，必定有一种信念驱使我们。这个信念就是： 世界是合理的、简单的，因而是可以理解的。对于数学研究则要加上一点： 这个世界的合理性，首先在于它可以用数学来描述。我们为世界图景的精巧和合理而欣喜而惊异。这种感情正是人类文化精神的结晶。数学正是在这样的文化气氛中成长的，而反过来推动这种文化气氛的发展。
数学的再一个特点是它不仅研究宇宙的规律，而且也研究它自己。在发挥自己力量的同时又研究自己的局限性，从不担心否定自己，而是不断反思、不断批判自己，并且以此开辟自己前进的道路。它不断致力于分析自己的概念，分析自己的逻辑结构（如希腊人把一切几何图形都分解为点、线、面，把所有几何命题的相互关系分解为公理、公设、定义、定理）。它不断地反思： 自己的概念、自己的方法能走多远？大家都说，数学在证明一串串的定理，数学家就要问什么叫证明？数学越发展，取得的成就越大，数学家就越要问自己的基础是不是巩固。越是在表面上看来没有问题的地方，越要找出问题来。乘法明明是可以交换的，偏偏要研究不可交换的乘法。唯有数学，时常是在理性思维感到有了问题时就要变。而且，其他科学中“变”的倾向时常是由数学中的“变”直接或间接引起的。当然，数学中许多重要的变是由于直觉地感到有变的必要，感到只有变才能直视宇宙的真面目。但无论如何，是先从思维的王国里开始变，即否定自己。这种变的结果时常是“从一无所有之中创造了新的宇宙”。
离散数学解题指导（第3版）第1版前言到了最后，数学开始怀疑起自己的整体，考虑自己的力量界限何在。大概到了19世纪末，数学向自己提出的问题是： “我真是一个没有矛盾的体系吗？我真正提供了完全可靠、确定无疑的知识吗？我自认为是在追求真理，可是‘真’究竟是指什么？我证明了某些对象的存在，或者说我无矛盾地创造了自己的研究对象，可是它们的确存在吗？如果我不能真正地把这些东西构造出来，又怎么知道它是存在的呢？我是不是一张空头支票，一张没有银行的支票呢？”
总之，数学是一株参天大树，它向天空伸出自己的枝叶，吸收阳光。它不断扩展自己的领地，在它的树干上有越来越多的鸟巢，它为越来越多的科学提供支持，也从越来越多的科学中吸取营养。它又把自己的根伸向越来越深的理性思维的土地中，使它越来越牢固地站立。从这个意义上来讲，数学是人类理性发展最高的成就。
人总有一个信念： 宇宙是有秩序的。数学家更进一步相信，这个秩序是可以用数学表达的。因此，人应该去探索这种深层的内在秩序，以此来满足人的物质需要。
离散数学用数学语言来描述离散系统的状态、关系和变化过程，是计算机科学与技术的形式化描述语言，也是进行数量分析和逻辑推理的工具。
“离散数学”是计算机科学与技术专业的核心基础课，在计算机科学与技术专业课程体系中起到重要的基础理论支撑作用。学习离散数学不仅能够帮助学生更好地理解与掌握专业课程的教学内容，同时也为学生在将来的计算机科学技术的研究和工程应用中打下坚实的理论基础。随着计算机科学与技术的日益成熟，越来越完善的分析技术被用于实践，为了更好地理解将来的计算机科学技术，学生需要对离散结构有深入的理解。
通过离散数学的学习有利于培养学生的学科素质，进一步强化对计算机科学与技术学科方法的训练。通过离散数学的教学，对培养学生获取知识、应用知识的能力，对创新思维的培养有着重要的作用。
本书与《离散数学（第2版）》相配套，主要包含数理逻辑、集合与关系、函数、组合计数、图和树、代数系统、自动机和初等数论等内容。全书分为10章，每章包含内容提要、例题精选和习题解答3部分。内容提要总结本章的主要定义、定理、重要的结果等；例题精选包含与上述内容配套的典型例题；习题解答与配套教材的习题对应。
本书既可以作为主教材的配套教学用书，也可以单独使用，为学习离散数学的读者在解题能力和技巧训练方面提供帮助。
本书第3章、第4章和第7章由袁景凌编写，其余章节由贲可荣、高志华编写。贲可荣组织了本书的编写，南京大学陶先平教授对全书进行了审读。
本书编写中参考了许多离散数学教材和相关资料，出版中得到清华大学出版社编辑认真细致的加工，在此一并表示感谢。本书有些方面仍感不足，错漏在所难免。敬请读者予以斧正，以便今后补充修改。贲可荣2011年12月12日