浅论离散数学的实际应用 学习此文

浅论离散数学的实际应用 学习此文 浅论离散数学的实际应用(学习此文)2010-12-21 20:42浅论离散数学的实际应用?xml:namespace prefix=o ns="urn:schemas-microsoft-com:office:office"/ 摘要: 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义:它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用:数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字:离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。 1.2离散数学的内容 离散数学是传统的逻辑学，集合论(包括函数)，数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数(包括代数系统，群、环、域等)，布尔代数，计算模型(语言与自动机)等汇集起来的一门综合学科。离散 数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括:数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的"真"与"假"或二进制当中的1和0，从而实现逻辑运算。常见的逻辑门包括"与"门，"或"门，"非"门，"异或"门(也称:互斥或)等等。逻辑门可以组合使用实现更为复杂的逻辑运算。 2.2在门电路设计中的应用 在数字电路中，离散数学的应用主要体现在数理逻辑部分的使用。在数字电路中广于使用的逻辑代数即为布尔代数。逻辑代数中的逻辑运算与、或、非、异或与离散数学中的合取，析取、否定、异或(排斥或)相对应。 数字电路的学习重点在于掌握电路设计技术，在设计门电路时，要求设计者根据给出的具体逻辑问题，求出实现这一逻辑功能的逻辑电路。一般的设计过程为如下: 首先，进行逻辑抽象.分析给定的逻辑问题，确定输入、输出变量,一般把引起事件的原因作为输入变量，把事件的结果作为输出变量。再以二值逻辑的0、1两种状态分别代表变量的两种不同状态，并根据给定的因果关系列出逻辑真值表。于是，这个实际的逻辑问题被抽象成一个逻辑函数了，而且这个逻辑函数是以真值表形式给出的。 然后根据真值表写出逻辑函数式。在这一步的主要工作为对逻辑函数进行化简和变换，此时采用的方法一般为使用逻辑代数公式，即离散数学中的命题演算公式将命题公式直接进行化简;或者用卡诺图法进行化简;或者同时采用两种方法，互相验证结果是否最简。但在一般情况下，在真值表中变量较多，逻辑函数式较为复杂时，我们采用卡诺图法更为方便快捷，且出错率更低。 在得到最简逻辑函数式后，选定器件类型，开始构建实际电路。在对所用器件种类有所限制或使用中规模集成电路构建设计好的电路时，需要把函数式变换为适当的形式。此时，我们将采用命题等值演算对函数式进行变换，变换的结果通常为合取范式和析取范式，以便使用最少的器件和最简单的连线。 3.离散数学在软件技术中的应用 离散数学作为计算机科学技术的支撑学科之一，它在计算机程序中有着极其重要和广泛的应用。在软件技术基础中，我们所学习的数据结构极其运算，查找与排序技术，数据库技术，无一不是建立在离散数学的基础上的。 数据存储结构分为顺序存储和链式存储两大类，无论是哪种存储结构，我们都必须存储数据元素和元素之间的前后件关系这两方面的内容。通过数据元素间的特定关系，我们可以得出数据结构的集合，写出关系矩阵，画出关系图。对于线性结构的数据，我们构造顺序表或链表对数据进行存储处理和分析，对于非线性结构的数据，我们则经常使用树和图来表示。树和图的概念对于非线性结构数据非常重要，例如一个学校的行政层次结构，我们可以用树来表示，一个城市中的交通路线可以用图来描述。 在查找和排序技术中，树显得尤为重要。在多种排序技术中，树概念的使用在堆排序技术中直观可见。堆排序的基本思想是，先将所需要排序的元素用完全二叉树表示成堆，堆定义为:具有n个元素的序列(h1,h2,…hn),当且仅当满足hi?h2i,hi?h2i+1或hi?h2i,hi?h2i+1时称为堆。然后在调整建堆的过程中，总是将根结点值与左右子树的根结点值进行比较，若不满足堆的条件，则将左右子树根结点值中的大者(或小者)与根结点值进行交换。这个调整过程一直做到所有子树均为堆为止。查找技术史建立在树的基础之上的，首先要构建二叉排序树，然后在其中进行查找。为提高查找数据的效率，一般采用多层索引树进行查找。主要的查找方法建立在树的遍历基础上。遍历一棵树有3种方法:前序遍历、中序遍历和后序遍历。具体采用哪种遍历方法由所选择的查找方法所决定。 数据库技术主要是实现对数据的加工和管理。在关系模型数据库中，对数据的操作归结为各种集合运算。在关系模型的数据语言中，我们除了要运用常规的集合运算(并、交、差、笛卡尔积等)外，还定义了一些专门的关系运算， 如投影、选择、连接等运算。前者是将关系(即二维表)看成元素组的集合，这些运算主要是从二维表中行的方向来进行的;后者主要是从二维表中列的方向来进行运算的。两者统称为关系代数。由于这方面的内容在离散数学和软件技术基础两门课程中都刚开始进入学习，所以在此不做进一步的研究。 4.离散数学在现实生活中的应用 离散数学不仅在于软硬件设计和计算机科学中有着广泛的应用，同时它也能解决一些生活中的问题，实用而且有趣，以下仅举一些例子作为说明。 图是由一些顶点和连接这些顶点的一些边所组成的离散结构。存在多种不同类型的图，其间的区别在于连接顶点对的边的种类和数目。在实际应用中，有值图广为使用。例如计算航线网络里两个城市之间航班的不同组合的数目，确定是否可能走遍城市里所有街道而不重复经过街道，以及求地图区域着色所需要的颜色数等等。树在生活中的最常见的应用则是描述一个家族的家谱，同时这种家谱树在生物遗传学中对于某个家族的遗传病史的研究也有很大作用。组合数学这一研究个体安排的学科，是离散数学的重要组成部分，它可以用来求解各种各样的问题，计算事件的概率，可以用来分析赌博游戏，如扑克，抽奖，计算及系统中的密码等等。离散数学可以解决的问题甚多，它包括: 有多少种方式可以在一个计算机系统上选择一个合法口令? 赢彩票的概率是多少? 网络上两台计算机之间是否有通路? 使用某一运输系统的两个城市之间的最短路径是什么? 怎样把整数列表按增序排列? 完成上述排列需要多少步骤? 怎样设计两个整数相加的电路? 有多少合法的因特网地址? 如果知道了学习离散数学能解决上述这类问题，你会突然对离散数学产生极大的兴趣，你会迫不及待地想学好它，至少我就是这样的。 参考文献: 【1】离散数学耿素云、屈婉玲、张立昂编著清华大学出版社 离散数学及其应用美Kenneth H.Rosen著袁崇义屈婉玲王捍贫刘田译 【3】百度百科词条