2离散数学的应用

　　离散数学课程包括数理逻辑、集合论、代数系统和图论几个部分，下面分别介绍一下这几个部分在计算机各方面的应用。

　　2。1数理逻辑的应用

　　数理逻辑是用数学方法研究思维规律的一门学科，包括命题逻辑、谓词逻辑和推理理论等知识点。命题逻辑中的联结词广泛应用在大量信息的检索、逻辑运算和位运算中，例如目前大部分网页检索引擎都支持布尔检索，使用NOT、AND、OR等联结词进行检索有助于快速找到特定主题的网页;信息在计算机内都表示为0或1构成的位串，通过对位串的运算可以对信息进行处理，计算机字位的运算与逻辑中的联结词的运算规则是一致的，掌握了联结词的运算为计算机信息的处理提供了很好的知识基础。在计算机硬件设计中，使用了联结词完备集中的与非和或非，使用与非门和或非门设计逻辑线路，替代了之前的非门、与门和或门

　　的组合，优化了逻辑线路。谓词逻辑可以表示关系模型中的关系操作[4]，用谓词逻辑表示关系操作的关系演算形式是：{s[<属性表>]│R(s)}，其中R(s)指的是s用该满足的谓词，例如要查询不及格的女同学的名字，关系演算的表达式为：{s│s∈studentands。sex=’w’ands。score<60}。推理理论可以应用到计算机语义的理解中，在推理理论中验证某理论的逻辑正确性时首先需要将其形式化，这样在逻辑推理时就直接使用逻辑规则进行推理而不需要理会其具体含义了，在计算机语义中，也可以将其形式化，借助推理理论的方法进行计算机语义的理解。

　　2。2集合论的应用

　　集合是由各种不同元素构成的，并用统一的方法来处理的对象，集合论包括集合代数、关系和函数等知识点。集合代数中的集合的性质和集合的运算主要是为其他学科提供数学基础，现实世界中的数字、符号、图像、语音、视频等各种信息都可以作为数据存放到计算机进行处理，这些数据就构成集合。关系是一种特殊的集合，它反映了研究对象之间的联系与性质，例如关系数据库模型中，每个数据库都是一个关系，在计算机程序中输入和输出就构成一个二元关系。等价关系和偏序关系广泛的存在于实际应用中，例如利用偏序的知识可以解决调度中的最优调度问题;在软件工程的软件测试方法中有一种等价类划分的方法，即将所有待测试的数据构成的集合划分为符合软件需求规格和设计规定的有效等价类和不符合的无效等价类，因为每个等价类中只需要取一个数据代表其所在等价类的其他数据进行测试，所以大大提高了软件测试的效率。函数的应用比较广泛，例如在密码学中的应用，公钥系统中的原理是基于单向陷门函数，单向陷门函数满足3个条件：(1)对于属于定义域的任意一个x，可以很容易算出F(x)=y，(2)对于几乎所有属于值域的任意一个y，则在计算上除非获得陷门，否则不可能求出x，使得x=F-1(y)，(3)若有一额外数据z(称为陷门)，则可以很容易的求出x=F-1(z)。单向陷门函数与单向函数的差异在于可逆与不可逆。若单向陷门函数存在，则任何单向陷门函数均可用来设计公开密钥密码系统。同时，若单向函数满足 交换性，则单向函数也可能用来设计公开密钥密码系统。

　　2。3代数系统的应用

　　代数系统研究的是集合、该集合中元素的运算和一些特殊元素，其中群是一种特殊的代数系统，具有可结合、有单位元、每个元素都有逆元等性质。凯撒密码系统的原理是将字母表的字母右移n个位置，n即key，然后对字母表长度l作模运算，加密形式为：c=(m+n)modl，解密形式为：m=(c-n)modl，其实凯撒密码就是建立在26个字母之上，字母与key运算的剩余模群。椭圆曲线加密算法是利用椭圆曲线离散对数问题，椭圆曲线离散对数问题定义如下：给定素数p和椭圆曲线E，对Q=kP，在已知P，Q的情况下求出小于p的正整数k，由于已知k和P计算Q比较容易，而由Q和P计算k则比较困难，至今没有有效的方法来解决这个问题，这正是该加密算法的原理所在。

　　2。4图论的应用

　　图论在计算机领域的应用广泛，例如利用哈密顿图求最短路径问题和旅行商最优问题，利用哈夫曼算法对指令系统优化以及提高通信效率等问题[5]。在计算机体系结构中，指令系统的优化非常重要，因为可以提高整个计算机系统的性能，指令系统的优化方法很多，其中一种就是对指令的格式进行优化，是指用最短的位数来表示指令的操作码和地址码，使程