离散数学是数学里专门用来研究离散对象的一个分支，是计算机专业的一门重要的基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。 全书共10章，主要包含数理逻辑、集合与关系、函数、图和树、组合计数、数论与递归关系、代数系统、自动机、文法和语言等内容。本书附录中的“历史注记”可以帮助学生理解数学，给出内在的洞察。

本书体系严谨，选材精炼，讲解翔实，例题丰富，注重理论与计算机科学技术的实际问题相结合，并选配了大量难度适当的习题，适合教学。本书适合作为计算机和相关专业本科生“离散数学”的教学用书，也可以作为对离散数学感兴趣的人士的参考书。

随着信息社会的到来，我国的高等学校计算机教育迎来了大发展时期。在计算机教育不断普及和高等教育逐步走向大众化的同时，高校在校生的人数也随之增加，就业压力随之加大。灵活应用所学的计算机知识解决各自领域的实际问题已经成为当代大学生必须具备的能力。为此，许多高等学校面向不同专业的学生开设了相关的计算机课程。

时代的进步与社会的发展对高等学校计算机教育的质量提出了更高、更新的要求。抓好计算机专业课程以及计算机公共基础课程的教学，是提高计算机教育质量的关键。现在，很多高等学校除计算机系（学院）外，其他系（学院）也纷纷开设了计算机相关课程，在校大学生也必须学习计算机基础课程。为了适应社会的需求，满足计算机教育的发展需要，培养基础宽厚、能力卓越的计算机专业人才和掌握计算机基础知识、基本技能的相关专业的复合型人才迫在眉睫。为此，在进行了大量调查研究的基础上，通过借鉴国内外最新的计算机科学与技术学科和计算机基础课程体系的研究成果，规划了这套适合计算机专业及相关专业人才培养需要的、适用于高等学校学生学习的《高等学校计算机教育规划教材》。

“教育以人为本”，计算机教育也是如此，“以人为本”的指导思想则是将“人”视为教学的主体，强调的是“教育”和“引导”，而不是“灌输”。本着这一初衷，《高等学校计算机教育规划教材》注重体系的完整性、内容的科学性和编写理念的先进性，努力反映计算机科学技术的新技术、新成果、新应用、新趋势；针对不同学生的特点，因材施教、循序渐进、突出重点、分散难点；在写作方法上注重叙述的逻辑性、系统性、适用性、可读性，力求通俗易懂、深入浅出、易于理解、便于学习。

本系列教材突出计算机科学与技术学科的特点，强调理论与实践紧密结合，注重能力和综合素质的培养，并结合实例讲解原理和方法，引导学生学会理论方法的实际运用。

本系列教材在规划时注重教材的立体配套，教学资源丰富。除主教材外，还配有电子课件、习题集与习题解答、实验上机指导等辅助教学资源。有些课程将开设教学网站，提供网上信息交互、文件下载，以方便师生的教与学。

《高等学校计算机教育规划教材》覆盖计算机公共基础课程、计算机应用技术课程和计算机专业课程。既有在多年教学经验和教学改革基础上新编著的教材，也有部分已经出版教材的更新和修订版本。这套教材由国内三十余所知名高校从事计算机教学和科研工作的一线教师、专家教授编写，并由相关领域的知名专家学者审读全部书稿，多数教材已经经受了教学实践的检验，适用于本科教学，部分教材可用于研究生学习。

我们相信通过高水平、高质量的编写和出版，这套教材不仅能够得到大家的认可和支持，也一定能打造成一套既有时代特色，又特别易教易学的高质量的系列教材，为我国计算机教材建设及计算机教学水平的提高，为计算机教育事业的发展和高素质人才的培养作出我们的贡献。

《高等学校计算机教育规划教材》编委会

2005年7月

序言

数学源于实践,汇于实践

回顾过去的一个世纪，数学科学的巨大发展比以往任何时代都更牢固地确立了它作为整个科学技术的基础地位。数学正突破传统的应用范围,向几乎所有的人类知识领域渗透，并越来越直接地为人类物质生产与日常生活作出贡献。同时，数学作为一种文化，已成为人类进步的标志。因此，对于当今社会每一位有文化的人士而言，不论他从事何种职业，都需要学习数学、了解数学和运用数学。现代社会对数学的这种需要，在新的世纪中无疑将更加与日俱增。20世纪数学思想的深刻变革，已将数学这门科学的核心部分引向高度抽象化的道路。面对各种深奥的数学理论和复杂的数学方法，门外汉往往只能望而却步。

一个本质上简单的学科却难于学习。不过，有些困难其实是表面的。其中之一是词汇。数学家用一些对普通人很生僻的词来表达从实际事物中抽象出来的概念。如“四边形”和“平行四边形”在其他领域遇不到的特定的精确含义，要研究数学就得学着用。另一个看得见的，但同样是表面的困难是使用符号。比如我们要解决问题，以某些给定的信息为基础决定一个未知数。设此未知数是某一个长度为尺计的数字，用x代表这个长度，而在以后就只用符号x而不用说这么长一句话，这样做肯定是有利的，因为使用符号不会产生任何概念上的困难。

人们设想到的第三个困难是抽象性。但是由于基本的抽象或概念是直接来自日常经验，人们心中很容易保存它们的含义。事实上，数学家不断地诉诸物理对象和物理图像，以便不忘记这些抽象概念的含义。古希腊数学家用小石子代表各类对象，用小石子学会了自然数的基本事实。顺便说一下，“计算”一词广义地表示任一个算术或代数过程，它的英文calculus的拉丁语源就是小石子。甚至更高级的数学抽象如微积分学中所学的导数和积分，说到底离这些初等概念仅一步之隔，而微积分的概念也有图像的物理的意义。学会这些抽象概念比学习初等概念并不要求具有更高的智力。

数学的完成了的形式是一系列概念、一系列程序，例如求解某种类型方程的方法；还有一系列事实，例如定理。当然，程序和定理都要通过证明来确认。要想使学生学好这些数学元素，最容易的方法似乎莫过于用这些概念、过程、定理和证明的最终的、确定的形式去教学生。但是数学是一门老学科，它的某些重大成就可以追溯到公元前3000年。过去5000多年里，数学家极大地扩大了这个学科的领域，当他们不断认识新的客体和现象，不断改进自己的理解时，他们也就重塑了这些概念、程序和证明，并把这些成就组合起来。许多订正了的版本就不再清晰易懂了。

此外，数学的分量在增加，最好把它组织起来，使关于同一主题的许多定理有合乎逻辑的次序。每一门学科的基础是公理，后面就是一串定理，每一个定理都用公理和前面已证的定理来证明。把结果按这样的合于逻辑的次序来安排，这种需要就要迫使数学家找出新的、不甚自然、不甚明白的证明。结果是许多证明都被除去了它们的直观、透明和易于理解的面貌，而被十分人为的证明代替了。离散数学

表述上的有效性似乎导致忽视数学的另一个特点，而这个特点对于理解数学却是至关重要的。数学本身是一副骨骼。数学的血肉和生命在于用数学做什么。有意义的数学要为一种目的服务，这种目的用笛卡儿的话来说，就是使人成为大自然的主人和占有者。数学的意义在于数学本身之外，正如好的文学作品的意义在于纸面上文字的堆积之外。因此，要懂得数学就要知道为什么需要这个结果，它和其他结果关系如何，用它可以做些什么事。

学校由于它的目的和义务繁多，有时能够、有时又不能够给数学一种更有启发性的讲法。有志于此的学生必须要走得远一些，寻求一种完全的知识。要对数学有较彻底的理解与领会，就必须去掉那些纤巧的细节，深入到其深层的思想之中；要知道它的目的和用处，知道创造它的人们的动机，以及这些概念和结构的创生背景。

创造性的活动，对学生来说则是再创造的活动，是数学的心脏。正是在这种活动中，数学家创造了最高成就，克服了最大的困难并使数学这门学科取得了最有意义的进展。创造过程不仅仅在解决已有问题时是必不可少的。没有新观点、新研究方法和新目标的创造，数学就会反反复复重新组织老的证明，使它们更加严格，在这样的过程中日趋枯竭，丧失生命力。对已经得到的知识，重新排列其步骤，安排其定理的次序来构成一个演绎的组织，这时常需要创意，但从总体上说，这更像是把书本重新排一个次序，而创造的活动，却可以比作写书。数学给人的满足——获得猎物时的兴奋，发现的激动，成就的感觉，以及成功时的欢乐——更多更强烈的是在创造性的工作之中，而不是在最后按演绎的模式来重写论证之中。

数学中有许多美的篇章。无疑，数学家从事数学活动也能获得其他创造活动提供的满足感，但是伟大的数学家情愿把数学的美作为一种额外报偿，激励他们奋斗的最深层的动力则是以数学为媒介，在人类的探索活动中理解宇宙，也理解人类自身在其中的角色，并且探求如何利用自然现象和自然的力量为人类服务。那些作出巨大贡献的数学家们，像阿基米德、牛顿、拉格朗日、拉普拉斯、高斯、哈密尔顿、庞加莱，或者是一流的物理学家，或者在科学史中占据显要地位。这绝不是偶然的。几乎所有数学的目的和意义并不在于对于一堆符号做一系列的逻辑阐述，而在于这些符号必定告诉我们关于外部世界的一些知识。离散数学是计算机科学的基础

离散数学是计算机专业最重要的必修课程之一，它是许多计算机专业课程的基础。

    离散数学是研究离散对象的数量和空间关系的数学，它包括多个数学分支，如本书所涉及的集合论、图论、组合数学、古典概率、自动机理论等，是计算机科学的理论基础，也是计算机应用的有力工具。另一方面，计算机科学的发展又促进了离散数学的发展。18世纪以前的数学基本上都属于离散数学的范畴，以后，天文学、物理学等的发展极大地推动了连续数学(如微积分)的发展，直到20世纪中期，尤其是20世纪80年代以后，随着计算机日益渗透到现代社会的各个方面，离散数学又重新受到高度重视。当然，离散数学涉及的内容极其广泛，其应用全然不是仅局限于计算机科学及其应用，而是涉及我们生活的方方面面。

由于数字计算机软硬件结构决定了它仅适于处理离散型信息的存储与计算，因此离散数学便成为计算机科学与技术的基本数学工具。某些理论上的“先见之明”，将会给以后学科的发展带来巨大的影响。例如，对可计算的研究所建立的图灵机是计算机的理论模型，随后这种理念导致了计算机的诞生。布尔的逻辑代数已成功地用于计算机的硬件分析与设计。谓词逻辑演算为人工智能学科提供了一种重要的知识表示方法和推理方法。这些都体现了离散数学的重要作用。对于离散数学的原理和方法，经常要求其在计算机上的可实现性；而一般的数学理论和方法有时仅给出存在性的结论，并不给出构造性的问题解答，因此难于满足实用性的要求。现代数字计算机的理论模型依然是20世纪30年代提出的图灵机，这是一种“离散”的机器，可用来处理“离散”的对象。当然，正如大多数计算机的早期应用，通过近似计算等手段，计算机也可以处理“连续”的对象，但现代的数字计算机仍然是一种“离散”的机器。事实上，目前计算机已经越来越多地用于处理各种“离散”的对象。

    随着计算机技术的发展，离散数学作为计算机科学的一种数学工具，其作用显得更加重要。对于一种程序设计语言来说，我们需要了解一些相关的问题：为什么会提出这种语言？它能解决什么问题？优势是什么？存在什么问题？它的语法、语义怎么样？利用该语言编写的程序必然是正确的吗？更深入的分析就是，计算机到底能做些什么？不能做些什么？什么是可计算的，什么是不可计算的，以及计算的复杂性又怎样？只有懂得一些深刻的基础性数学知识，才能对这些问题给出较为准确的回答。

    离散数学为什么作为计算机专业学生的基础课？美国数学会主席Lynn A. Steen回答了该问题：…But today’s growth industries are dominated by information, which is abstract and immaterial. Where the material world is modeled by calculus, the language of continuous change,the immaterial world of information requires discontinuous discrete mathematics. Both genetic codes and computer codes are intrinsically discrete. Discrete mathematics basically deals with fancy ways of arranging and counting. It can be used to enumerate genetic patterns and to count the branches in computer algorithms; it can be used to analyze the treelike branching of arteries and nerves, as well as the cascading options in a succession of eitheror decisions. It can tell us how many things are there as well as help us find what we want among a bewildering morass of possibilities. 离散数学的主要内容 

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系。因此无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立数学模型；又如何将已经用连续数量关系建立起来的数学模型离散化，从而可以用计算机加工处理。离散数学是数学里专门用来研究离散对象的一个数学分支，是计算机专业的一门重要的基础课。它所研究的对象是离散的数量关系和离散的数学结构模型。 

20 世纪 70 年代，国外开始将离散数学作为一门大学课程。当时，有一些计算机科学家根据自己对计算机科学的理解，与一些数学家一起圈定了一些他们认为对计算机科学是必需的数学专题，结合计算机科学中的一些实例编著了一些主要是命名为“离散数学结构和方法”或“离散数学基础”之类的书籍，开设相应的课程供大学里学习计算机专业和其他一些相关工程专业的学生选修。由于反应很好，渐渐在计算机专业中，“离散数学”作为必修课来开设。我国是在大约 20 世纪 80 年代初期，从翻译国外离散数学专著开始，逐渐编写了一些适合我国教学情况的离散数学的教材，并在计算机系中开设了相应的课程。

如上所述，由于各专家主攻计算机的方向和他们对计算机教学的理解不尽相同，因此，在“离散数学”名下的内容也不完全一样。本书根据ACM和IEEE/CS最新推出的Computing Curricula 2004，以及教育部高等教育司组织评审通过的《中国计算机科学与技术学科教程2002》中制定的关于“离散数学”的知识结构和体系撰写。全书共10章，主要包含数理逻辑、集合与关系、函数、图和树、组合计数、数论与递归关系、代数系统、自动机、文法和语言等内容。基本上涵盖了计算机专业所需的数学内容。离散数学这门课程，主要介绍各分支的基本概念、基本理论和基本方法，这些知识将应用于数字电路、编译原理、数据结构、操作系统、数据库原理、算法分析与设计、人工智能、软件工程、计算机网络等专业课程之中。学习离散数学的方法 

离散数学是计算机科学系所有专业的基础数学课程。一方面有其实用性（应用数学的特征），另一方面有其本身作为数学基础课的理论的严谨性。所以，学习任何一个专题时，首先要精确严格地掌握好概念和术语，正确理解它们的内涵和外延。因为公理、定理或定律的基石都是概念。只有正确地理解了概念，才能把握定理的实质，熟练地将公理、定理应用于解决问题。完全地、精确地掌握一个概念首先要深刻理解概念的内涵，然后举一些属于和不属于该概念外延的正反两方面的实例。如果对一些似是而非的例子也能辨别的话，应该说就是对这个概念真正理解了。对一些重要的概念，能记住一两个实例也很管用，这对牢固掌握一个概念是很有好处的。 

读者应养成一种自觉的学习习惯，就是首先要掌握好基本概念和术语，在此基础上，理解每个基本定理的本质，最后通过学习和借鉴书中提供的例题，独立地完成每一次作业，并且在每次作业完成之后，能自觉地归纳出其中用到的基本解题方法。注意，千万不要在完全理解相关概念和基本定理之前就匆忙去做相应的习题。

学习数学的唯一途径是实践。仅看别人怎么做，是不可能学会弹吉他或投篮的，也不可能仅靠阅读本书或听课就能学好离散数学。必须积极主动地思考。在阅读数学书时，应该在手头随时备好笔和纸，以便进行详细的推导和计算。在听数学课前，最好先阅读有关的内容，这样，就可以专注于对内容的理解是否与教授的理解相一致，还可以就一些难点提问。本书中有很多习题，有些是纯粹的计算题，有些要测试对概念的理解，有些习题则要求给出论证，建议读者多做习题。

    学习和理解术语也很重要。在数学中，传统的做法是对一些简单、常见的词汇赋予特殊的含义，如集合、函数、关系、图、树以及网络。这些词都有严格的定义，必须认真学习，否则，就不能理解你在书中读到的内容和教授所讲述的课程。这些术语对有效地交流是必需的。术语能帮助你有效地与别人共享信息。在现实生活中，仅仅简单地计算出某些东西往往是不够的，还必须能够向别人解释，使别人确信你的解是正确的。

我们期待你成功地学好离散数学，并从中学到许多技术和观点，你将会发现它们在许多地方都是有用的。

对数学和逻辑的感悟得益于我们的老师们，他们是陈火旺先生、莫绍揆先生、王世强先生、康宏逵先生、齐治昌先生、胡静婉老师、丁德成老师。也获益于我的同学们，包括沈恩绍教授、宋方敏教授、王公宝教授、王怀民教授、王戟教授、王献昌教授。如果本书有什么新意的地方，首先归功于他们，错误和疏漏由我负责。

本书第1～5章、第9章、第10章及附录由贲可荣、高志华撰写，第6～8章由袁景凌撰写，全书由贲可荣统稿。郭翠翠、刘鹏、俞洋参与了第6～8章的部分工作。陈志伟、陈振兴分别参与了第5章、第10章的部分工作。魏娜参与了校对工作。

在本书撰写过程中，武汉理工大学计算机学院院长钟珞教授、海军工程大学计算机系主任郭福亮教授给予了多方面的支持。武汉大学计算机学院院长何炎祥教授对全书进行了审校，特此致谢。

贲可荣2007年1月

第1章命题逻辑1

1.1现代逻辑学的基本研究方法1

1.1.1思维： 感知的概念化和理性化1

1.1.2现代逻辑学求助数学——符号化2

1.1.3现代逻辑学追随数学——公理化2

1.1.4现代逻辑学改造数学——形式化3

1.2命题及其表示法4

1.2.1命题的概念4

1.2.2复合命题4

1.2.3联结词5

1.2.4复合命题真假值7

1.3命题公式与翻译9

1.3.1命题公式的定义9

1.3.2公式的层次10

1.3.3翻译10

1.4真值表与等价公式11

1.4.1真值表11

1.4.2等价公式12

1.5重言式与等值演算12

1.5.1重言式12

1.5.2等值演算14

1.6对偶与范式16

1.6.1对偶16

1.6.2简单合取式和简单析取式17

1.6.3范式18

1.6.4范式的唯一性——主范式20

1.7其他联结词25

1.7.1n元真值函数26

1.7.2真值函数与命题公式的关系26

1.7.3联结词完备集27

1.7.4单元素联结词构成的联结词完备集28

1.8推理理论29

1.8.1有效推理29

1.8.2有效推理的等价定理30

1.8.3重言蕴涵式32

1.8.4形式推理系统P134

1.8.5自然推理系统P235

习题41

第2章谓词逻辑51

2.1谓词逻辑的基本概念51

2.1.1个体词52

2.1.2谓词52

2.1.3量词53

2.2谓词逻辑公式与翻译54

2.2.1一阶语言54

2.2.2自由与约束55

2.2.3闭公式56

2.2.4谓词逻辑公式的解释57

2.2.5谓词逻辑命题符号化58

2.2.6谓词逻辑公式的分类61

2.3谓词逻辑等值演算62

2.3.1基本等价式与置换规则62

2.3.2谓词逻辑前束范式66

2.4谓词演算的推理理论68

2.4.1推理定律68

2.4.2量词消去与引入规则69

2.4.3一阶谓词演算公理系统F169

2.4.4自然推理系统F271

2.5逻辑在计算机科学中的作用73

2.5.1逻辑与计算73

2.5.2逻辑与计算机的起源74

2.5.3逻辑与程序设计75

习题76离散数学

第3章集合与关系82

3.1集合的概念和表示法82

3.1.1集合的表示82

3.1.2集合的基本概念84

3.2集合的运算85

3.2.1集合的基本运算85

3.2.2有穷计数集86

3.2.3广义交和广义并87

3.3有序对与笛卡儿积89

3.4关系及其表示91

3.4.1关系的基本概念91

3.4.2关系表示法92

3.5关系的运算94

3.5.1基本概念94

3.5.2复合关系95

3.5.3逆关系96

3.5.4关系幂98

3.5.5幂运算的性质99

3.6关系的性质101

3.6.1关系的五种基本性质101

3.6.2关系性质的等价描述102

3.7关系的闭包106

3.7.1闭包的基本概念106

3.7.2闭包的性质110

3.8集合的划分与覆盖111

3.9等价关系和等价类112

3.9.1等价关系112

3.9.2等价类的性质114

3.9.3商集与划分115

3.10偏序关系116

3.11偏序集与哈斯图117

3.12包含排斥原理120

习题121

第4章函数128

4.1函数的定义128

4.1.1函数和像128

4.1.2函数的性质130

4.1.3常用函数131

4.2复合函数和反函数132

4.2.1复合函数132

4.2.2反函数134

4.3特征函数与模糊子集136

4.3.1特征函数136

4.3.2模糊集合137

4.4基数的概念138

4.4.1后继与归纳集138

4.4.2自然数，有穷集，无穷集139

4.4.3基数144

4.5可数集与不可数集144

4.6数学归纳法146

4.6.1归纳法证明146

4.6.2数学归纳法第一原理146

4.6.3数学归纳法第二原理147

习题149

第5章图论153

5.1图的基本概念153

5.1.1图的定义和表示153

5.1.2图的同构157

5.1.3完全图与正则图159

5.1.4子图与补图159

5.1.5通路与回路161

5.2图的连通性163

5.2.1无向图的连通性163

5.2.2有向图的连通性165

5.3图的矩阵表示165

5.3.1关联矩阵165

5.3.2有向图的邻接矩阵166

5.3.3有向图的可达矩阵168

5.4二部图168

5.4.1二部图及判别定理168

5.4.2完备匹配169

5.5欧拉图171

5.6哈密顿图174

5.7平面图177

5.7.1平面图及其判定定理177

5.7.2平面图的对偶图183

5.8带权图184

习题185

第6章树及其应用193

6.1树的术语和性质193

6.1.1树的定义及相关术语193

6.1.2树的性质195

6.2生成树196

6.3最小生成树199

6.4树的遍历202

6.5二叉树204

6.5.1二叉树的性质204

6.5.2二叉搜索树205

6.5.3赫夫曼树206

6.6决策树207

6.6.1决策树的定义207

6.6.2最短时间排序209

6.7树的同构209

6.8博弈树213

6.8.1博弈树的概念213

6.8.2极大极小分析法213

6.8.3αβ剪枝技术216

习题218

第7章计数方法与鸽巢原理222

7.1基本原理222

7.1.1加法原理222

7.1.2乘法原理223

7.2排列与组合224

7.2.1排列224

7.2.2组合224

7.3排列组合生成算法225

7.3.1排列生成算法225

7.3.2组合生成算法226

7.4离散概率论229

7.4.1离散概率简介229

7.4.2有限概率230

7.4.3条件概率与独立性232

7.4.4Bayes定理233

7.5广义的排列和组合234

7.6二项式系数和组合恒等式236

7.6.1二项式定理236

7.6.2组合恒等式238

7.7鸽巢原理239

7.7.1鸽巢原理的简单形式239

7.7.2鸽巢原理的一般形式240

习题241

第8章数论与递归关系243

8.1素数243

8.2最大公约数与最小公倍数244

8.3同余247

8.4一次同余方程和中国剩余定理249

8.4.1一次同余方程249

8.4.2中国剩余定理250

8.5数论在密码学中的应用251

8.5.1公钥密码学251

8.5.2RSA密码252

8.6递归关系简介252

8.6.1递归定义函数252

8.6.2递归定义集合254

8.6.3递推关系模型255

8.7求解递归关系257

8.8递归在算法分析中的应用259

习题262

第9章代数系统264

9.1二元运算及其性质264

9.1.1定义和表示264

9.1.2二元运算的性质266

9.2代数系统268

9.2.1定义和实例268

9.2.2子代数系统270

9.2.3代数系统的同态与同构270

9.3半群与独异点271

9.3.1定义与性质271

9.3.2子系统与直积272

9.4群273

9.4.1群的定义273

9.4.2群的性质275

9.4.3子群的定义277

9.4.4正规子群与商群278

9.4.5群的同态与同构实例281

9.4.6循环群与置换群284

9.5环与域286

9.5.1环286

9.5.2域287

9.6格与布尔代数288

9.6.1格288

9.6.2布尔代数292

9.7组合电路295

习题297

第10章自动机、文法和语言305

10.1串和语言305

10.2形式文法306

10.3有限状态机309

10.4有限状态自动机311

10.5不确定有限状态自动机314

10.6语言和自动机之间的关系317

习题318

附录A历史注记322

参考文献332