离散数学论文
                 
系别： 计算机科学与技术系
班级： 10级网络工程一班
姓名：
学号：
           
离散论文
一、离散数学
离散数学是现代数学的一个重要分支，是计算机科学基础理论的核心课程，其内容一直随着计算机科学的发展而不断地扩充与更新。以离散量作为其主要研究对象，如自然数、真假值、字母表等。这使得它与数学分析（研究对象是连续量）在研究对象上形成了鲜明的差别。离散数学是研究离散量及其相互关系的一门数学学科。
二、知识点
第一部分：数理逻辑
数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。
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这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜给它们着不会引起混淆。
  电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四猜想证明的进程。美国伊利诺大学哈肯在1970年着手改进“放电过程”，后与阿佩尔合作编制一个很好的程序。就在1976年6月，他们在美国伊利诺斯大学的两台不同的电子计算机上，用了1200个小时，作了100亿判断，终于完成了四定理的证明，轰动了世界。
这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四足够”的特制邮戳，以庆祝这一难题获得解决。
“四问题”的被证明仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着问题化为图论问题，丰富了图论的内容。不仅如此，“四问题”在有效地设计航空班机日程表，设计计算机的编码程序上都起到了推动作用。不过不少数学家并不
满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍由不少数学家和数学爱好者在寻更简洁的证明方法。
四、总结
离散数学在个学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、人工智能、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具盒方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推 理能力，为将来参与创新的研究和开发工作打下坚实的基础。
数据结构与算法论文
总之，离散数学不仅是计算机技术迅猛发展的支撑学科，更是提高学生逻辑思维能力、创造性思维能力以及形式化能力的动力源，离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域。