离散数学总结

1 / 35 离散数学总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中， p、 q、 r 等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设 A 为一命题公式， p ,p ,p 为出现在 A 中的所有命题变项。给 p ,p ,p 指定一组真值，称为对 A 的一个赋值或解释。若指定的一组值使 A 的值为真，则称成真赋值。 真 值 表 ： 含 n 个 命 题 变 项 的 命 题 公 式 ， 共 有 22 / 35 组赋值。将命题公式 A在所有赋值下的取值情况列成表，称为 A 的真值表。 命题公式的类型：若 A 在它的各种赋值下均取值为真，则称 A 为重言式或永真式。 若 A 在它的赋值下取值均为假，则称 A为矛盾式或永假式。 若 A 至少存在一组赋值是成真赋值，则 A 是可满足式。 主析取范式：设命题公式 A 中 含 n个命题变项，如果 A 得析取范式中的简单合取式全是极小项，则称该析取范式为 A的主析取范式。 主合取范式：设命题公式 A中含 n个命题变项，如果 A得析取范式中的简单合析式全是极大项，则称该析取范式为 A 的主析取范式。 命题的等值式：设 A、 B为两命题公式，若等价式 A?B是重言式，则称 A 与 B是等值的，记作AB。 约束变元和自由变元：在合式公式 ?x A 和 ?x A 中，称 x 为指导变项，称 A 为相应量词的辖域， x称为约束变元，x 的出现称为约束出现， A 中其他出现称为自由出现。 一阶逻辑等值式：设 A， B 是一阶逻辑中任意的两公式，若 A?B为逻辑有效式，则称 A 与 B 是等值的，记作 AB，称 AB 为等值式。 前束范式：设 A 为一谓词公式，若 A 具有如下形式Q1x1Q2x2QkxkB ，称 A为前束范式。 集合的基本运算：并、 交、差、相对补和对称差运算。 笛卡尔积：设 A 和 B 为集合，用 A 中元素为第一元素，用 B 中元素为第二元素构成有3 / 35 序对组成的集合称为 A 和 B 的笛卡尔积，记为 AB 。 二元关系：如果一个集合 R为空集或者它的元素都是有序对，则称集合 R 是一个二元关系。 特殊关系：、空关系： 全域关系： EA= | xA yA = AA 恒等关系： IA= | xA 小于等于关系： LA=| x, yAxyA ,A ? R 整除关系： R? =| x， y x ? y , 是集合族 二元关系的 运算：设 R 是二元关系， R中所有有序对的第一元素构成的集合称为 R的定义域 domR = x | ?y R 中所有有序对的第二元素构成的集合称为 R的值域 ranR = y | ?x R 的定义域和值域的并集称为 R的域 fldR= domR ranR 二元关系的性质：自反性，反自反性，对称性，反 (来自 : 海 达范文网 :离散数学总结 )对称性，传递性。 等价关系：如果集合 A上的二元关系 R是自反的，对称的和传递的，那么称4 / 35 R 是等价关系。设 R 是 A 上的等价关系， x , y 是 A 的任意元素，记作 x y。 等价类：设 R 是 A 上的等价关系，对任意的 ?xA ，令 xR= y | yA x R y ，称 xR 为 x关于 R的等价类。 偏序关系：设 R 是集合 A上的二元关系，如果 R是自反的，反对称 的和传递的，那么称 R为 A 上的偏序，记作 ；称序偶为偏序集合。 函数的性质：设 f: A?B， 若 ranf = B，则称 f 是满射的。 若 ?y? ranf 都存在唯一的 x ?A 使得 f(x)=y,则称 f 是单射的。 若 f 既是满射又是单射的，则称 f 是双射的。 无向图：是一个有序的二元组，记作 G，其中： (1) V? 称为顶点集，其元素称为顶点或 结点。 (2) E 为边集，它是无序积 V&V 的多重子集，其元素称为无向边，简称边。 有向图：是一个有序的二元组 ,记作 D,其中 (1) V同无向图。 (2) E为边集，它是笛卡尔积 V?V 的多重5 / 35 子集，其元素称为有向边。 设 G=是一个无向图或有向图。 有限图：若 V, E是有限集，则称 G为有限 图。 ：若 | V |=n，称 G 为 n阶图。 零图：若 | E |=0，称 G 为零图 ,当 | V |=1 时，称 G 为平凡图。 基图：将有向图变为无向图得到的新图，称为有向图的基图。 图的同构：在用图形表示图时，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构。 带权图：在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。 连 通图：若无向图是平凡图，或图中任意两个顶点都是连通的，则称 G 是连通图。否则称为非连通图。设 D 是一个有向图，如果 D 的基图是连通图，则称 D是弱连通图，若 D 中任意两个顶点至少一个可达另一个，则称 D 是单向连通图。若 D中任意两个顶点是相互可达的，则称 D 是强连通图。 欧拉图：通过图中所有边一次且仅一次并且通过所有定点的通路，称为欧拉通路。存在欧拉回路的图称为欧拉图。 哈密顿图：经过图中每个顶点一次且仅一次的通路，称为哈密顿通路，存在哈密顿回路的图称为哈密顿图。 平面图：一个图 G 如果能以这样的方式画在平面上：出定点处外 没有变交叉出现，则称 G 为平面图。画出的没有边交叉出现的图称为 G的一个平面嵌入。 二部图：若无向图 G= V, E的6 / 35 顶点集合 V可以划分成两个子集 V1和 V 2，使 G中的任何一条边的两个端点分别属于 V1 和 V2，则称 G 为二部图。二部图可记为 G = , V1 和 V 2称为互补顶点子集。 树的定义：连通无回路的无向图称为无向树，简称树，常用 T 表示树。平凡图称为平凡树。若无向图 G至少有两个连通分支，每个连通都是树，则称 G 为森林。在无向图中，悬挂顶点称为树叶，度数大于或等于 2的顶点称为分支点。 树的性质：性质 1、设 G=是 n阶 m 条边的无向图，则下面各命题是等价的： G是树 G中任意两个顶点之间存在唯一的路径 G中无回路且m=n-1. G 是连通的且 m=n-1. G 是连通的且 G 中任何边均为桥。 G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 性质 2、设 T 是 n 阶非平 凡的无向树，则 T中至少有两片树叶。 证：设 T 有 x 片树叶，由握手定理及性质 1 可知，2(n-1)=d(vi)x+2(n -x)由上式解出 x2. 最小生成树：设 T 是无向图 G 的子图并且为树，则称 T 为 G 的树。若T 是 G 的树且为生成子图，则称 T 是 G 的生成树。设 T 是 G的生成树。 eE(G) ，若 eE(T) ，则称 e 为 T的树枝，否则7 / 35 称 e 为 T 的弦。并称导出子图 GE(G)-E(T)为 T的余树，记作 T。 最优二 元树：设 2 叉树 T有 t 片树叶 v1,v2,vt ，权分别为 w1,w2,wt ，称 W(t)=wil(vi)为 T的权，其中 l(vi)是 vi 的层数。在所有有 t 片树叶，带权 w1,w2,wt 的 2叉树中，权最小的 2 叉树称为最优 2 叉树。 最佳前缀码：利用 Huffman算法求最优 2叉树，由最优 2叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。 蕴含式推理 集合恒等式： P61 幂等律： AA=A ； AA=A 结合律： (AB)C=A(BC) ； (AB)C=A(BC) 交换律： AB=BA ； AB=BA 分配律： A(BC)=(AB)(AC) ；A(BC)=(AB)(A C) 8 / 35 同一律： A? =A ； AE=A 零 律： AE =A ； A? = ? 排中律： AA=E 矛盾律： AA =? 吸收律： A(AB)=A ； A (AB)=A 德 摩 根 定 律 ： A-(BC)=(A -B)(A -C) ；A-(BC)=(A -B)(A -C) (BC)= BC ； (BC)= BC ； ?=E； E=? 双重否定律： dom(F -1)=ranF ； ran (F -1)=domF 则称 n? m为 G 的关联矩阵。记为 M(G)。 有向图的关联矩阵：设无向图 D=, V=v1,v2,vn, E=e1,e2,em ， 9 / 35 1, vi 是 ej的始点 mij = 0, vi 与 ej不关联 -1， vi是 ej的终点 则称 n? m 为 D的关联矩阵。记为 M(D) 。 XX20174036 何志伍 计算机科学与技术 离散数学学期总结 离散数学是描绘一些离散量与量之间的相互逻辑结构及关系的学科。它的思想方法及内容渗透到计算机学科的各个领域中。因此它成为计算机及相关专业的一门重要专业基础课。主要内容包括：集合论、关系 、代数系统、图论和数理逻辑五个部分。结构上，从集合论入手，后介绍数理逻辑，便于学生学习。为了能很好的消化理解内容，列举了大量的较为典型、易于接受、说明问题的例题，配备了相当数量的习题，也列举了部分实际应用问题。 10 / 35 一 知识点 第一章 .集合论 集合论或集论是研究集合的数学理论，包含集合、元素和成员关系等最基本数学概念。在大多数现代数学的公式化中，集合论提供了要如何描述数学物件的语言。 本章主要介绍集合的基本概念、运算及幂集合和笛卡尔乘积。这章是本书的基础部分，要学 好离散数学就必须很好的掌握集合的内容。集合论的概念和方法已经渗透到所有的数学分支，因而各数学分支的完整体系，都是在所取集合上。 第二章关系 关系在我们日常生活中经常会遇到关系这一概念。但在数学中关系表示集合中元素间的联系。本章主要学习关系的基本概念、关系的性质、闭包运算、次序关系、 等价关系，本章学习的重点：关系的性质、闭包运算、次序关系。 关系这一章是集合论这一章的延伸，对集合论的理解程度对学习关系这一章是非常有影响的。而关系又是学习下一章代11 / 35 数系统必不可少的，所以本章是非常重要的章节。 第三章代数系统 代数结构也叫做抽象代数，主要研究抽象的代数系统。抽象代数研究的中 心问题就是一种很重要的数学结构 -代数系统：半群、群等等。 本章主要学习了运算与半群、群。学习本章需要学会判断是否是代数系统、群和半群，以及判断代数系统具有哪些运算规律，如：结合、交换律等及单位元、逆元。这些都在我们计算机编码中体现出重要的作用。 第四章图论 图论 Graph Theory起源于著名的柯尼斯堡七桥问题，以图为研究对 象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。 12 / 35 本章主要学习图的基本概念、路径与回路、图的矩阵表示、平面图和二部图、以及树。学习的重点：图的矩阵表示、平面图和二部图、以及树。 第五章数理逻辑 数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。 数理逻辑与计算机科学有着密切的关系，它已成为计算机科学的基础理论。 本章学习的重点：命题及联结词、命题公式及公式的等值和蕴含关系、对偶与范式、命题演算的推理规则、谓词逻辑简介。 二学习情况 离散数学作为一门必修课，其地位是非常重要的。学习好这门课对于我们也是颇有益处。而且离散数学还是一门有很深13 / 35 内涵的学科。 集合论是本书的这一章节，我们在以前已经学习过集合，为什么现在还要学习呢，这就足见集合在离散数学这门课程中的重要，把集合的知识作为一个基础的知识点，来作铺垫。所以说要想学习好离散数学就必须先将集合的知识掌握好。 关系是集合知识点的延伸，关系是相对于集合而言的。关系也是一个重要的知识点，对后续知识的学习也有重要的 作用。后面的代数系统就必须依赖关系才存在的。如果一个系统里不存在关系，那么这个系统也是不存在的。系统里必然存在某种关系，这才使系统存在有意义。 代数系统的学习是对前面的集合论与关系的以个总结。学习了集合论与关系有什么用，在这一章节我们就可以看出来。通过学习这一章，对前面两章有了更深的理解，也对前面所学知识有了一个总结。但同时本章也是本书中比较难以了理解的章节，在本章的学习中遇到一些问题，但是在同 学的帮助下都一一解决了。 图论的学习对于我们计算机专业的学生来说是非常的重要的，因为它与我们 14 / 35 计算机专业的关系最密切。在学习中，图不再是我们以前接触的图，而是学习的事如何在点与 点之间连结的问题。这对于发散我们的思维有很大的帮助。 数理逻辑是本书最重要的章节，它是培养我们的抽象思维，让我们能在其他学科能够运用一定的思维方式来解决问题。对于计算机专业来说，数理逻辑提高了计算机的工作效率。数理逻辑在计算机专业方面起到了重要的作用。 三学习体会 学习了离散数学这门课程，对于一个爱好数学的人来说，我是非常受益的。同时，离散数学作为一门与计算机学科相关的专业基础课，对我学专业知识也有很大的帮助。 学习离散数学，可以培养我们的逻辑思维方式，对于我们学习计算机方向的学生来说是非常有用的。尤其是在计算机编程方面对逻辑思维就有一定的要求。离散数学这门课 程，是一门比较难学的课程，它有太多的概念、定义，需要我们有很好的记忆力，但是要完全记住这么多的概念、定义是非常困难的。所以说我们在有好的记忆力之外，还要运用理解记15 / 35 忆的方法来解决，这样我们就不必花费过多的时间和精力去记忆这么多的概念和定义了。离散数学作为一门理科学科，在我看来最好的学习方法就是多动手、多做题，在做题得过程中，慢慢积累做题得经验，同时也可以对概念和定义有一个更深层次的理解。 学习各个 学科都有其各自的学习方法与思维方式，只有运用对了学习方法才能更好的学习这门课程。学习一门课程都是为了解决实际问题，学习离散数学也不例外。学通了一门课程才能在解决问题的时候不会走弯路。 上面说到了离散数学是一门比较难学的课程，在学习的过程中，也肯定会遇到许多的问题，比如在第三章学习的代数系统中的半群与运算，关于单位元与逆元素这两个知识点遇到一些问题。但是通过反复的理解概念及做练习题和与同学交流，最 后还是解决了这些问题。当解决问题的时候心中有一种成就感。 学习离散数学的过程中，也有许多的乐趣。但在轻松学习的过程中，还得从中学到东西，学到道理。我在学习这门课程之后，对我的专业知识方面有了很大的帮助，让我的思维有了进一步的发散，使我在其他的学科中受益匪浅。 16 / 35 离散数 学心得体会 离散数学，对绝大多数学生来说是一门十分困难的课程，当然也包括我在内，而当初选这门课是想挑战一下自己。通过这一学期的学习，我对这门课程有一些初步的了解，现在的心情和当初也很不相同。 在还没有接触的时候，看见课本就想退缩，心想：这是什么课程啊，这叫数学吗，这些符号都是之前没有 见过的呢！但是既然都说是挑战就没有退缩的道理。虽然不能说是抱着“ 视死如归 ” 的精神，至少能说是忐忑不安。第一次听老师讲课的时候已经是落后别人两次课，前面的知识都是自己看书，所以难免有些看不懂，在听老师讲课的时候有些定义性的东西就会混淆，我自认为是个越挫越勇的人，并没有因此退缩。超乎想象的是，老师讲课好仔细，好详细，因为前面的知识是为后面做铺垫，所以在后面老师经常强调，那么，我错过的东西也都掌握了。 在听过老师讲解以后，我觉得前三章自己都能很好的掌握。后面的开始深入一些，对于好多以前没有接触过的名词定义不能马上理解，但是只要跟着老师的思维走，上课认真听讲，17 / 35 课后看一下书本就能懂。有了这些认知，我觉得这门课的难点在于课程比较枯燥，好多理论的知识需要我们去理解。 前三章主要是认识逻辑语言符号，了解了数理逻辑的特点，并做一些简单的逻辑推理和运算。这些知识都是以前所学的进一步转换，只要将数学的函数符 号逻辑化就行。也就是说，那些符号知识形式上的不同，实质上是一样的。不同的是，之前的数学只需要运用结论证明其他的案例等。但是逻辑数学不仅要知其然还要知其所以然，运用结论正结论。即使如此，我还是觉得这几章学着很轻松，只要熟练掌握公式定理就会觉得离散数学并不像之前想象的那么困难。第四章讲的是关系。这一章，进一步认识、运用数理逻辑语言，熟练强化练习，深入理解。这一章的难度相较于前几章要繁琐些，有很多的符号转换，运算，运算过程很复杂。对于计算能力不强的我来说，这一章或许是最吃力的，即使知道原理也需要通过大量的练习强化 巩固，而这其中用到的还有线性代数里面的矩阵。第五章学的是函数，定义和高中所学一样，只不过是把它转换运用于数理逻辑，并用逻辑符号进行运算。虽说如此，但是这其中仍然有更深层次的概念和逻辑公式，如果单纯的用原有的思维是很难想透彻的。 第六章 “ 图 ” 和第七章 “ 树及其应用 ” 可以归为 “ 图论 ” 。18 / 35 在刚接触到 “ 图 ” 这一章的时候我是抱着好奇之心去学习的，因为这章都是关于 “ 图 ” ，想了解一下和几何图形的差别，所以觉得善长 几何的我应该能够把它学好。但是不可否认，随着知识的深入，这一章一定会比前面的更难理解，更难学。因此，上课的时候听得格外认真，课后还找了一些相关书籍阅览。在看过这些书籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常广泛，并且应用于我们整个日常生活中。比如：怎样布线才能使每一部电话互相连通，并且花费最小？从首府到每州州府的最短路线是什么？ n 项任务怎样才能最有效地由 n个人完成？管道网络中从源点到集汇点的单位时间最大流是多少？一个计算机芯片需要多少层才能使得同一层的路线互不相交？怎样安排一个体育联盟季度赛的日程表使其在最少的周数内完成？一位流动推销员要以怎样的顺序到达每一个城市才能使得旅行时间最短？我们能用 4种颜色来为每张地图的各个区域着色并使得相邻的区域具有不同的颜色吗？这些问题以及其他一些实际问题都涉及 “ 图论 ” 。 这里所说的图并不是几何学中的图形，而是客观 世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接19 / 35 这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。哥尼斯堡桥问题，这个著名的数学难题，在经过如此漫长的时间最终还是瑞士数学家欧拉利用图论解决了它，并得出没有一种方法使得从这块陆地中的任意一块开始，通 过每一座桥恰好一次再回到原点。 树是指没有回路的连通图。它是连通图中最简单的一类图，许多问题对一般连通图未能解决或者没有简单的方法，而对于树，则已圆满解决，且方法较为简单。而且在许多不同领域中有着广泛的应用。例如家谱图就是其中之一。如果将每个人用一个顶点来表示，并且 在父子之间连一条边，便得到一个树状图。 图论中最著名的应该就是图的染色问题。这个问题的研究来源于著名的四色问题。四色问题是图论中也许是全部数学中最出名、最难得一个问题之一。所谓四色猜想就是在平面上任何一张地图，总可以用至多四种颜色给每一个国家染色，使得任何相邻国家的颜色是不同的。四色问题粗看起来似乎与我们所讨论的图没有什么联系。其实也是可以转化为图论中的问题来讨论。首先从地图出发来构作一个图，让 每一个20 / 35 顶点代表地图的一个区域，如果两个区域有一段公共边界线，就在相应的顶点之间连上一条边。由于地图中每一块区域对应图的一个顶点，两个相邻顶点对应两个相邻的区域。所以对地图染色使相邻的区域染以不同的颜色相当于对图的每个顶点染以相应的一种颜色，使得相邻的顶点有不同的颜色。总之，图论是数学科学的一个分支，而四色问题是典型的图论课题。 通过对图论的初步理解和认识，我深深地认识到，图论的概念虽然有其直观、 通俗的方面，但是这许多日常生活用语被引入图论后就都有了其严格、确切的含义。我们既要学会通过术语的通俗含义更快、更好地理解图论概念，又要注意保持术语起码的严格。 本以为枯燥乏味的离散数学竟然会是贴近生活是我意想不到的，这些历史难题等等，都让我对它产生了一定的兴趣，虽然不可否认的是，对我来说它确实是一门很难很深奥很抽象的课程，但是仍然不减我对图论产生的兴趣，或许这也就是我选择这门课程最大的收获吧。 离散数学论文 21 / 35 系别： 计算机科学与技术系 班级： 10级网络工程一班 姓名： 学号： 离散论文 一、离散数学 离散数学是现代数学的一个重要分支，是计算机科学基础理论的核心课程，其内容一直随着计算机科学的发展而不断地扩充与更新。以离散量作为其主要研究对象，如自然数、真假值、字母表等。这使得它与数学分析在研究对象上形成了鲜明的差别。离散数学是研究离散量及其相互关系的一门数学学科。 二、知 识点 第一部分：数理逻辑 22 / 35 数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。 1、在命题逻辑的基本概念中学习了命题与联结词、命题与联结词、命题及其分类、联结词与复合命题、命题公式及其赋值。 2、在命题逻辑的等值演算中主要学习了等值式与基本的等值式、等值演算与置换规则、析取范式与合取范式，主析取范式与主合取范式、联结词完备集可满足性问题与消解法。 3、 在命题逻辑的推理理论中主要学习了推理的形式结构、推理的正确与错误、推理形 式结构、判断推理正确的方法、推理定律；自然推理系统 P、形式系统的定义与分类、自然推理系统 P，在 P 中构造证明：直接证明法、附加前提证明法、归谬法 4、在一阶逻辑基本概念中主要学习了 一阶逻辑命题符号化、23 / 35 个体词、谓词、量词、一阶逻辑命题符号化、一阶逻辑公式及其解释、一阶语言、合式公式、合式公式的解释、永真式、矛盾式、可满足式。 5、在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统 NL 及其推理规则、数理逻辑应用。 第二部分：集合论 在集合论中，主要学习了集合代数、二元关系、函数。 1、在集合代数中，学习了集合的基本概念：属于、包含、幂集、空集、文氏图等；集合的基本运算：并、交、补、差等；集合恒等式：集合运算的算律、恒等式的证明方法。 2、在二元关系中学习了有序对与笛卡儿积、二元关系的定义与表示法、关系的运算、关系的性质、关系的闭包、等价关系与划分、偏序关系。 3、在函数中学习了函数的定义与性质、函数运算。 24 / 35 第三部分：代数结构 在代数结构中，主要学习了代数系统、群与环。 1、在代数系统中学习了二元运算及其性质：一元和二元运算定义及其实例、二元运算的性质代数系统：代数系统定义及其实例、子代数、积代数；代数系统的同态与同构。 第四部分：图论 在图论中主要学习了图的基本概念、欧拉图与哈密顿图、树。 1、在图的基本概念中学习了图、通路与回路、图的连通性，图的矩阵表示、图的运算。 2、在欧拉图与哈密顿图中学习了欧拉图、哈密顿图。 3、在树中学习了无向树及其性质、生成树、根数及其应用。 三、应用 1、代数系统在计算机科学中的应用： 25 / 35 人们研究和考察现实世界中的各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的 “ 并 ” 、“ 交 ” 运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象定义各种运算，然后讨论这些对象及运算的有关性质。 在计算机科学研究中，始终围绕着两个问题展开：第一，研究的任务能否由计算机来解决；第二，计算机如何执行这个任务。要解决这两个问题，就必须针对具体的任务建立相关的计算机模型，例如，应用于编译器的构造的文法模型，应用于语言识别的有限状态等等。要建立计算机模型，就必然要使用离散数学作为理论基础，建立起对应的数学模型。 针对某个具体问题选用适宜的数学 结构去进行较为确切的描述，这就是所谓 “ 数学模型 ” 。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构 由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数又提出了新的要求，促使抽象代数学不断涌现新的概念，发展新理论。 格与布尔代数的理论成为电子计算26 / 35 机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库理论模型 。格论事计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。 2、离散数学在关系数据库中的应用： 数据库是指按照一定 的数据模型组织并存放在外存上的一组相关数据集合，数据库管理系统，是对数据进行管理的软件系统。关系数据库是以关系模型为数据模型建立的，它的基本元素是表，即关系。在关系数据库中，所有的数据都存储在一张二维表格中，每一张命名的二维表就是一个关系。表的每一行称为一个记录，每一列称为一个属性。 关系模型中包含内容有：关系的投影、关系的连接、关系的自然连接、关系的选择、关系的笛卡尔积、关系的并差交等。 3、图论的实例 Huffman 压缩算法、网络流等。 27 / 35 4、实例分析 地图 着色问题又称为 “ 四色问题 ” ，四色问题的内容是：“ 任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。 ” 您提供的图可以这样着颜色： 1区着 1 色、 2 区着 2色、 3区着 3 色、 4 区着 2 色、 5区着 3色、 6 区着 4 色。 四色问题又称四色猜想，是世界近代三大数学难题之一。 四色问题的内容是： “ 任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。 ” 用数学语言表示，即“ 将平面任意地细分为不相重迭的区域，每一个区域总可以用 1， 2， 3， 4 这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。 ” 这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点 或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。 电子计算机问世以后，由于演算速度迅速提高，加之人机对28 / 35 话的出现，大大加快了对四色猜想证明的进程。美国伊利诺大学哈肯在 1970 年着手改进 “ 放电过程 ” ，后与阿佩尔合作编制一个很好的程序。就在 1976 年 6 月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了 1200 个小时，作了 100 亿判断，终于完成了四色定理的证明，轰动了世界。 这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了 “ 四色足够 ” 的特制邮戳，以庆祝这一难题获得解决。 “ 四色问题 ” 的被证明仅解决了一个历时 100多年的难题，而且成为数学史上一系列新思维的起点。在 “ 四色问题 ” 的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此， “ 四色问题 ” 在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍 由不少数学家和数学爱好者在寻找更简洁的证明方法。 四、总结 29 / 35 离散数学在个学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、人工智能、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握 处理离散结构的描述工具盒方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推 理能力，为将来参与创新的研究和开发工作打下坚实的基础。 总之，离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域。 离散数学总结 班级： 学号： 姓名： 临近期末各科课程已经结束，随之而来就是总结各科学习总结和对这门学科的建议。离散数学这门课程当然也不会例外了。经过一个学期的学习我发现离散数学是一门理30 / 35 论性非常强 的课程，而且知识点非常多，定义和定理以及定律是数之不尽。 离散数学顾名思义就是一门数学，它是数学众多领域中的一个小分支，即使是一个小小的分支，但是它的内容也非常之多，同时也非常抽象。自认我的数学成绩还是不错的，但是面对离散数学我就头痛，书本里面很多知识点我都是似懂非懂地。但鉴于离散数学在计算科学中的重要性，这是一门必须牢牢掌握的课程。因此我也很无奈，只好硬着头皮去学好它了。 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学 (集合论、数理逻辑和图论 )有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 离散数学的特点是： 1、知识点集中，概念和定理多。离散数学是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意31 / 35 概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身 的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困