前 言 离散数学(discretemathematics)是以可枚举(enumerable)的数量或形状作为研究对象的数学分支。这里可枚举的含义是指离散数学研究的对象与对象之间有清晰明确的界限，从而可以一一罗列出来，或者用数学语言说，可枚举的对象与若干自然数可以有一一对应的关系。当前现有的计算机只能处理可枚举的信息，因此离散数学在计算机科学中有着广泛的应用。 “离散数学基础”课程是计算机专业学生的核心基础课程，提供包括逻辑(logic)、集合(set)、算法(algorithm)、图论(graphtheory)和代数(algebra)在内的数学语言描述可枚举的数学对象，使得人们在利用计算机求解问题时可建立合适的数学模型并对其进行分析。 编写新工科建设背景下计算机专业的离散数学教材，应注重离散数学在利用计算机求解问题时的应用。建立离散模型通常是利用计算机求解问题的第一步。因此，我们认为“离散数学基础”课程的核心目标应该是培养学生具备初步的离散建模能力。在这种课程目标的指导下，与传统的离散数学教材不同，我们力图将逻辑、集合、算法、图论和代数的相关知识从离散模型描述语言的角度进行阐述，重点将它们作为表达和交流的工具，基于描述离散模型的需要，讨论这些语言的核心词汇和核心问题。 在这些语言中，逻辑语言主要用于描述模型的性质和约束，其核心词汇是“命题”和“真值”，核心问题是如何确定命题的真值以及命题之间的真值关系；集合语言用于描述模型的元素与结构，核心词汇是“集合”“函数”与“关系”，核心问题是如何确定集合的元素以及不同集合之间元素的对应关系；算法语言用于描述模型的行为和实现，核心词汇是“指令”“输入”和“输出”，核心问题是如何利用顺序、分支和循环三种结构组合一些基本操作，即基本指令，描述如何从输入得到期望的输出；图论语言可用于可视化地描述模型结构，核心词汇是“顶点”“边”和“关联”，核心问题是满足条件的顶点、边或子图的搜索与构造；代数语言可用于描述模型的结构与约束，核心词汇是“运算”“代数”和“同态”，核心问题是利用基本运算刻画代数的性质以及代数之间的关系。 在进行离散数学建模时，人们还运用关系思维、逻辑思维、计算思维、量化思维和递归思维等去组织和运用离散数学语言，找到建模的切入点，并使得自己的思考更为周密、严谨。关系思维引导人们建模时去分析事物之间的关键关系；逻辑思维强调对模型性质与约束应使用严谨的逻辑语言表达，并考查模型元素之间的逻辑关系；计算思维强调关注模型的可实现性；量化思维强调关注模型的规模以及模型动态行为的效率；递归思维引导人们关注模型在结构或行为方面的自相似性，思考如何将大规模的模型结构或行为归结为小规模的模型结构或行为。 为构建有利于计算机自动实现的“好”模型，人们在离散建模时应具备离散化、模块化、层次化、公理化和系统化的计算机专业意识。离散化意识使得人们在建模时思考如何将复杂问题进行分解，并清晰地罗列和枚举模型的元素、结构、行为和约束；模块化意识使得人们在建模时思考模型元素间关系的紧密程度，尽量将要考虑的范围局部化，从而更好地把握住复杂的问题；层次化意识告诉人们在对复杂问题进行分解时应逐步求精和细化，形成不同的抽象层次；公理化意识引导人们在繁杂的模型元素、结构、行为或约束中找到最基本的构件，利用基本的构件和一些通用的规则去构造和描述复杂的模型元素、结构、行为或约束；系统化意识引导人们将模型的元素、结构、行为或约束从某种角度进行系统化思考，形成有机的整体，从而做到不遗漏、不重复，使得模型能在某种程度上全面地刻画要解决的问题。 本书作为“离散数学基础”课程的教材，从描述离散数学模型的需要出发，给出有关逻辑语言、集合语言、算法语言、图论语言和代数语言的基础知识，培养学生运用这些离散数学语言和包括关系思维、逻辑思维、计算思维、量化思维和递归思维在内的思维方式建立离散数学模型的初步能力，并逐步树立离散化、模块化、层次化、公理化和系统化的计算机专业意识。本书的核心内容是关于逻辑、集合、算法、图论和代数5种离散数学语言的基础知识，引导读者运用这些离散数学语言表达要利用计算机进行求解的问题。图1给出了本书章节内容的整体框架结构。 图1 本书章节内容的整体框架结构 第1 章“基础知识”介绍有关逻辑语言、集合语言、图论语言、代数语言和算法语言的基础知识。这些基础知识大部分在中学学习中已经接触过，是对高中数学知识的衔接。这一章介绍这些离散数学语言的基本概念，并尽早地引入集合的归纳定义法、图的基本概念、代数运算的基本概念以及算法的描述方法和算法的递归调用。这些内容在后面的章节中到处出现，是学习后面内容的准备，后面要学习的内容则是这一章内容的拓展与深入。 第2章“命题逻辑”、第3章“一阶逻辑”和第4章“证明方法”属于逻辑语言的深入介绍。逻辑语言使用命题描述事物的性质和事物之间的关系，核心的问题是确定命题的真值以及命题真值之间的关系，包括逻辑等值和逻辑推理关系。第2章学习命题逻辑的基本概念、命题逻辑公式的语法和真值确定、命题逻辑公式的等值演算和基于命题逻辑公式的推理系统。第3章介绍有关一阶逻辑的基本概念、一阶逻辑公式的语法和真值确定、一阶逻辑公式的等值演算和基于一阶逻辑公式的推理。第4章介绍基本的证明方法，包括直接证明与间接证明、分情况证明、构造性与非构造性存在证明、数学归纳法、集合的归纳定义与结构归纳法。通过第4章的学习，读者不仅可熟悉基本的数学证明方法和思路，提高自己的数学证明能力，而且可进一步体会逻辑语言的严谨性。 第5章“集合”、第6章“关系”和第7章“函数”属于集合语言的深入介绍。集合语言是现代数学的基本语言，使用集合、关系、函数等描述所要研究的数学对象以及它们之间的联系。第5章介绍集合的基本概念、集合运算、集合等式和子集关系证明。第6章介绍关系的基本概念、关系的运算、关系的性质、关系的闭包，以及两种特殊的关系——等价关系和偏序关系。第7章介绍函数的基本概念、函数的性质和函数的运算，并介绍集合等势、有穷集和无穷集、可数集和不可数集的基础知识，讨论函数的增长及其在算法效率分析方面的应用和一些关于算法复杂度的基础知识。 逻辑语言和集合语言是学习组合计数、图论语言和代数语言的基础。第8章“计数与组合”介绍基本的组合计数原理、排列与组合、二项式定理及二项式系数恒等式的证明、递推关系的构建与线性递推关系式的求解。第2~4章，特别是第4章的证明体现逻辑思维的运用，而第5~7章，特别是第6章的关系和第7章的函数体现关系思维，第8章展示量化思维的运用，不仅讨论集合元素的计数，而且进一步讨论算法效率的分析，特别是递归算法和分治算法的效率分析。 第9 章“图与树”对图论语言做比较深入的介绍，在总结图和树的基本概念的基础上，对图的连通性、图的遍历、树的遍历，以及带权图的顶点间最短距离、最优二叉树、图的最小生成树等做更多的讨论，并对一些特殊的图，包括平面图、欧拉图、哈密顿图做简单的介绍。 第10章“代数系统”对代数语言做比较深入的介绍，在定义运算及其性质的基础上，介绍代数系统的基本概念、代数的构造（子代数、同余关系和商代数）、代数同态和同构，并介绍代数系统的例子，包括群、格与布尔代数的一些基础知识。 第11章“结束语”总结全书的内容，介绍可以进一步学习的离散数学相关知识，并给出一些推荐阅读的参考文献。 本书没有单列一章介绍算法的相关内容，但第1章的“基础知识”有一节专门介绍算法语言的基础知识，包括算法的基本概念和基本特点，结合例子给出了如何使用结构化自然语言描述算法的顺序结构、选择结构和循环结构，以及算法调用的方法，并尽早引入了递归调用和递归算法的概念。计算机专业的学生在学习离散数学时应注意思考如何利用计算机辅助求解离散数学的问题，因此算法语言的使用和计算思维、递归思维的运用应该贯穿对逻辑、集合、图论和代数的学习，相关的章节也会给出许多算法的例子。另外，第7章对函数的介绍会讨论函数的增长及其在算法效率分析中的应用，第8章的“计数与组合”会介绍递推关系式及其在算法效率分析中的应用。 不少离散数学教材有关于数论的基础知识，我们没有单列一章介绍有关数论，但不少内容，包括简单的算法例子、数学问题的证明、计数与组合中都有涉及整数性质的例子。这些例子会给出一些重要的数论基础知识，包括最大公因数及其欧几里得算法、素数及素数的无穷性、两整数最大公因数的贝祖定理(Bézout’sTheorem)等。 本书每章的定义、定理和例子都分别按章跨节编号。我们只将能够严格使用数学语言定义，并且对于“离散数学基础”课程学习非常重要的概念作为定义，定义的正文使用楷体以与其他正文区别，其中被定义的概念使用黑体。定理、引理和推论都沿用定理的编号，给出每章最重要的结论。我们精心挑选每一知识模块所需的定义和定理，使得它们能形成一个相对完整的整体，但不至于有太多、太散的概念和结论需要读者记忆和学习。 我们将例子进一步分为例子和问题，所以例子和问题进行了统一编号，一起按章跨节编号。例子主要用于进一步解释定义给出的概念或定理给出的结论，问题则偏向定义和定理的应用，给出的问题在形式上与这一章的习题及运用离散数学要求解的实际问题相同，并且除给出参考的【解答】或【证明】外，通常在解答前有【分析】部分介绍求解问题的思路和切入点，在解答后有【讨论】部分补充解答的一些注意事项以及可能的启发。因此，不少问题也适合用于翻转课堂教学模式中在学生自学章节主要内容之后进行的讨论式教学。 本书每一章除给出大量例子和问题外，还给出了“本章小结”，总结这一章的主要概念、主要结论，以及学习这一章之后读者应该了解、熟悉的概念和应该能求解的问题。每章的习题在这章的最后一节给出，其中大部分习题用于巩固学习的内容，与这章中给出的问题十分类似，但也给出了一些扩展性的、有一定难度的习题，供基础好的读者练习，其中标记星号“*”的习题是推荐的习题，可作为课后作业布置给学生完成。经过登记和验证的课程任课教师，可以通过邮箱bailj@tup.tsinghua.edu.cn获得习题的参考答案。 本书只假定学生有中学数学知识，如果已经接触过矩阵的基础知识，以及使用某门程序设计语言编写过计算机程序则更好。本书可作为高等院校计算机相关专业本科一、二年级72~108 学时的“离散数学基础”课程的教材，或者作为离散数学相关课程的参考书，也可供从事计算机专业相关工作的科研人员、工程技术人员及其他有关人员参考。表1给出了参考的课程学习计划和学时建议，其中列①针对周学时为4学时（总学时为72学时①）的课程，列②针对周学时为6学时（总学时为108学时①）的课程（每学期上课周数设为18周），任课教师可根据情况选用。本书对应表中列出的每个教学单元的起始点给出了二维码，扫描该二维码可获得该教学单元的课件和视频讲解等教学资源。 表1 课程学习计划和学时建议 序号教学单元主要内容选讲或略讲内容.. 基础知识：逻辑语言、集合1.3图论语言1 第1 章语言、算法语言1.4代数语言34 2.1 节、2.2节、命题逻辑的基本概念、命2.2.2命题逻辑公式的语法性 2 2.3节题逻辑公式的语法和语义质23 32.4节命题逻辑的等值演算2.4.3命题逻辑公式的范式23 2.5.3 构造验证推理有效性的 4 2.5 节命题逻辑的推理理论论证23 52.6节命题逻辑的应用2.6.3算法性质的逻辑分析23 3.1 节、3.2节、一阶逻辑的基本概念、一 6 3.3 节阶逻辑公式的语法和语义3.3.1 一阶逻辑公式的解释34 73.4节一阶逻辑的等值演算3.4.3一阶逻辑的前束范式23 8 3.5 节 一阶逻辑的推理理论 3.5.2 量词公式的推理规则 2 4 9 3.6 节 一阶逻辑的应用 3.6.3 算法性质的逻辑分析 2 3 10 4.1节、4.2节 直接证明、间接证明、分情况证明、存在性证明 4.2.4 基本证明策略 3 4 11 4.3 节 数学归纳法、良序原理、归纳定义、结构归纳法、递归算法、归纳证明 4.3.1数学归纳法与良序原理4.3.3递归算法与归纳证明 3 4 12 5.1节、5.2节 集合的基本概念、集合运算 5.1.3文氏图与成员关系表5.2.5集合运算的算法 3 3 13 5.3 节 集合等式 2 3 14 6.1 节 关系的定义、关系的表示、关系的运算 2 3 15 6.2 节 关系的性质 6.2.4 关系性质与关系运算 2 3 16 6.3 节 关系的闭包 2 4 17 6.4 节 特殊关系举例 2 3 18 7.1 节 函数的基本概念、性质和函数运算 7.1.3 函数运算与函数的性质 2 3 19 7.2 节 集合等势、无穷集、可数集 7.2.2 有穷集与无穷集 2 3 20 7.3 节 函数的增长、算法效率分析 7.3.3 算法复杂度基础知识 2 3 21 8.1 节 加法原理、乘法原理、容斥原理、鸽笼原理 8.1.3 鸽笼原理 3 4 . 表1 中列. 和列. 分别留2 学时和3 学时的机动时间。 (续表1) 序号教学单元主要内容选讲或略讲内容.. 22 8.2.1节、8.2.2排列与组合、二项式定理、2 节组合等式 8.2.3 节、8.2.4允许重复的排列与组合、 23容斥原理及其应用、排列8.2.5排列与组合的生成算法3 节、8.2.5节与组合的生成算法 递推关系式及其求解、分 24 8.3 节 治算法与递推关系式2 图的基本概念、图的连通 259.1节性、图的表示、无向图的遍9.1.4无向图的遍历2历 269.2节树的基础知识23 279.3节带权图及其应用24 289.4节平面图、欧拉图、哈密顿图23 10.1 节、10.2运算及其性质、代数及同 29 节 态10.2.2 同余关系与商代数3 30 10.3 节 群、子群、陪集、正规子群、商群 10.3.2群元素的阶10.3.5群同态 2 3 31 0.4 节 格与布尔代数 10.4.2 分配格与有界格 2 3 总学时数 70 105 在本书的编写过程中，参考了许多国内外同类教材，得到了许多领导和老师的支持，在此对这些教材的编者以及支持我们的领导和老师表示衷心的感谢。教材于2020年2—7月在中山大学数据科学与计算机学院计算机大类四个教学班进行了试用，非常感谢参与的老师和学生在试用过程中提出的许多宝贵意见和建议。这里还要特别感谢清华大学出版社的编辑，特别是白立军老师，没有他们的耐心和支持，本书不可能得以出版。 在新工科建设背景下，基于培养计算机专业学生离散建模能力，编写一本与计算机专业其他课程，特别是与程序设计课程内容紧密结合的离散数学教材是我们努力尝试的方向，但限于编者的水平，不一定能达到预期的目标。书中可能存在不少的疏漏和不妥之处，恳请广大读者批评指正。 作者 2020 年7 月 ① 表1中列?和列?分别留2学时和3学时的机动时间。 ?? ?? ??

• 课件下载
• 样章下载
• 暂无网络资源

扫描二维码
下载APP了解更多

版权图片链接