《离散数学》

学习体会

院 校 xxxx 专 业 离散数学 姓 名 xxxxx 学 号 xxxxxxxxxxxxx 时 间 xxxxxxxxxxxxxx] 成 绩

首先感谢各位老师对我们接受继续教育的学子帮助和支持，祝老师们工作顺利，身体健康；离散数学是这学期新接触的一门自学课程，因此，在学习的同时还要去学习针对这一学科的学习方法。

一、离散数学

离散数学是现代数学的一个重要分支，是计算机科学基础理论的核心课程，其内容一直随着计算机科学的发展而不断地扩充与更新。以离散量作为其主要研究对象，如自然数、真假值、字母表等。这使得它与数学分析（研究对象是连续量）在研究对象上形成了鲜明的差别。离散数学是研究离散量及其相互关系的一门数学学科。

二、知识点

第一部分：数理逻辑

数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。

1、在命题逻辑的基本概念中学习了命题与联结词、命题与联结词、命题及其分类、联结词与复合命题、命题公式及其赋值。

2、在命题逻辑的等值演算中主要学习了等值式与基本的等值式、等值演算与置换规则、析取范式与合取范式，主析取范式与主合取范式、联结词完备集可满足性问题与消解法。

3、题逻辑的推理理论中主要学习了推理的形式结构、推理的正确与错误、推理形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P中构造证明：直接证明法、附加前提证明法、归谬法。

4、在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、谓词、量词、一阶逻辑命题符号化、一阶逻辑公式及其解释、一阶语言、合式公式、合式公式的解释、永真式、矛盾式、可满足式。

5、在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统NL 及其推理规则、数理逻辑应用。

第二部分：集合论

在集合论中，主要学习了集合代数、二元关系、函数。

1、在集合代数中，学习了集合的基本概念：属于、包含、幂集、空集、文氏图等；集合的基本运算：并、交、补、差等；集合恒等式：集合运算的算律、恒等式的证明方法。

2、在二元关系中学习了有序对与笛卡儿积、二元关系的定义与表示法、关系的运算、关系的性质、关系的闭包、等价关系与划分、偏序关系。

3、在函数中学习了函数的定义与性质、函数运算。

第三部分：代数结构

在代数结构中，主要学习了代数系统、群与环。

1、在代数系统中学习了二元运算及其性质：一元和二元运算定义及其实例、二元运算的性质代数系统：代数系统定义及其实例、子代数、积代数；代数系统的同态与同构。

第四部分：图论

在图论中主要学习了图的基本概念、欧拉图与哈密顿图、树。

1、在图的基本概念中学习了图、通路与回路、图的连通性，图的矩阵表示、图的运算。

2、在欧拉图与哈密顿图中学习了欧拉图、哈密顿图。

3、在树中学习了无向树及其性质、生成树、根数及其应用。

三、应用

1、代数系统在计算机科学中的应用：

人们研究和考察现实世界中的各种现象或过程，往往要借助某些数学工具。在代数中，可以用正整数集合上的“并”、“交”运算来描述单位与单位之间的关系等。我们所接触过的数学结构，连续的或离散的，常常是对研究对象（然数、实数、多项式、矩阵、命题、集合乃至图）定义各种运算（加、减、乘，与、或、非，并、交、补），然后讨论这些对象及运算的有关性质。 在计算机科学研究中，始终围绕着两个问题展开：第一，研究的任务能否由计算机来解决；第二，计算机如何执行这个任务。要解决这两个问题，就必须针对具体的任务建立相关的计算机模型，例如，应用于编译器的构造的文法模型，应用于语言识别的有限状态等等。要建立计算机模型，就必然要使用离散数学作为理论基础，建立起对应的数学模型。

针对某个具体问题选用适宜的数学结构去进行较为确切的描述，这就是所谓“数学模型”。可见，数学结构在数学模型中占有极为重要的位置。而代数系统是一类特殊的数学结构——由对象集合及运算组成的数学结构，我们通常称它为代数结构。它在计算机科学中有着广泛的应用，对计算机科学的产生和发展有重大影响；反过来，计算机科学的发展对抽象代数又提出了新的要求，促使抽象代数学不断涌现新的概念，发展新理论。

格与布尔代数的理论成为电子计算机硬件设计和通讯系统设计中的重要工具。半群理论在自动机和形式语言研究中发挥了重要作用。关系代数理论成为最流行的数据库理论模型。格论事计算机语言的形式语义的理论基础。抽象代数规范理论和技术广泛用于计算机软件形式说明和开发，以及硬件体系结构设计。有限域的理论是编码理论的数学基础，在通讯中发挥了重要作用。在计算机算法设计与分析中，代数算法研究占有主导地位。

2、离散数学在关系数据库中的应用：

数据库是指按照一定的数据模型组织并存放在外存上的一组相关数据集合，数据库管理系统，是对数据进行管理的软件系统。关系数据库是以关系模型为数据模型建立的，它的基本元素是表，即关系。在关系数据库中，所

有的数据都存储在一张二维表格中，每一张命名的二维表就是一个关系。表的每一行称为一个记录，每一列称为一个属性。

关系模型中包含内容有：关系的投影、关系的连接、关系的自然连接、关系的选择、关系的笛卡尔积、关系的并差交等。

3、图论的实例——Huffman压缩算法、网络流等。

4、实例分析

地图着色问题又称为“四色问题”，四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”

您提供的图可以这样着颜色：1区着1色、2区着2色、3区着3色、4区着2色、5区着3色、6区着4色。

四色问题又称四色猜想，是世界近代三大数学难题之一。

四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”用数学语言表示，即“将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。

电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。美国伊利诺大学哈肯在19xx年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。就在19xx年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四色定理的证明，轰动了世界。

这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。

“四色问题”的被证明仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍由不少数学家和数学爱好者在寻找更简洁的证明方法。

四、总结

离散数学在个学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、人工智能、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具盒方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推 理能力，为将来参与创新的研究和开发工作打下坚实的基础。

总之，离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域。

第二篇：《离散数学》本科教学大纲

《离散数学》

本科教学大纲

课程编号：140B7030

上海立信会计学院

《离散数学》课程教学大纲

一、课程基本信息

课程名称：离散数学

英文名称：Discrete Mathematics

课程编号：140B7030

课程类别：学科基础课

预修课程：《高等数学》、《C语言程序设计》

开设部门：信息科学系

适用专业：计算机科学与技术专业

学 分：3

总 课 时： 51学时 其中：理论教学课时：51学时，实践教学课时0学时 选用教材：邓辉文：《离散数学》，清华大学出版社，20xx年10月

二、课程性质、目的

本课程是计算机科学与技术专业的主要基础课。其目的是介绍在用计算机进行问题求解时常用的数学模型以及相关的数学方法；同时培养学生的问题抽象能力、推理能力、利用数学模型解决问题的能力。要求学生掌握集合、关系和映射、图、代数系统等几类模型的有关概念、基本理论和一定的应用技巧，了解一些基于这些模型的典型算法，初步掌握通过建立数学模型来解决非数值应用问题的思维方法和基本技术。

三、与其他课程的衔接

为加强离散结构的训练，修完此课程后，可选修数据结构、数据库原理，这样对于集合和图论的应用能加深了解，温故知新。另外，离散数学与计算机网络与通信，以及计算机系统结构等课程关系密切，是本专业其它专业基础课程和专业课的先修课程。

四、教学基本要求

1．掌握离散数学的基本概念，特别是数理逻辑、图论和代数系统的基本内容，是离散数学的主要组成部分。

2．在讲授基本理论的过程中，应注意引入离散数学的在计算机科学中的应用实例。 3．本课程是一门综合的数学学科，概念抽象，推理严格，因此教学形式以讲授方式为主。

4．有些关键性概念（如图论）的问题可辅以算法描述。 5．条件许可，应利用网络技术进行授课、答疑和讨论。

6．安排必要的作业、习题课与辅导答疑，及时发现学生学习中存在的共性问题。

五、教学内容与课时

本课程教学内容与课时分配见下表：

六、课程考核

1． 考核方式：考试。

2． 考核内容：以离散数学的基本理论、概念、方法为主要内容。 3． 成绩评定：平时成绩占30%，期末考试占70%。

七、参考文献资料

1.耿素云等：《离散数学》（第三版），清华大学出版社，20xx年7月 2.李大友主编：《离散数学》，清华大学出版社20xx年版。

八、制定与审定签章

本大纲自20xx年2月起开始执行。