离散数学 等值演算法

设p:派赵出国，q:派钱出国，r:派孙出国，s:派李出国，t:派周出国。则各条件分别符号化为: 
(1) p→q，  (2) (sVt),  (3) (qA 7r)V(-q ^r)，(4) (r As)V(→rA -s)，  (5) 1- +(p ^q) 要求满足各条件，
因而要求(1)~(5)的合取式为真.设:A≈(p→q) A(sV1)八((q八→r)V(→qλr))A((rAs)V(r八-s))∩(t→(p^q)) 
为了求出各派遣方案,应求出A的析取范式，最好是主析取范式，主析取范式中含的极小项个数为派遣方案数，由各极小项的成真赋值给出如何派法.  所以要求出A的主析取范式。
下面给出求A的主析取范式的主要步骤:

易知，成真赋值为00110与11001。
方案1：孙、李出国，而赵.钱、周不去。
方案2：赵、钱、周出国，而孙、李不去。
扩展资料
随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。
离散数学也可以说是计算机科学的基础核心学科，在离散数学中的有一个著名的典型例子-四色定理又称四色猜想，这是世界近代三大数学难题之一，它是在1852年，由英国的一名绘图员弗南西斯·格思里提出的，他在进行地图着色时，发现了一个现象，“每幅地图都可以仅用四种颜色着色，并且共同边界的国家都可以被着上不同的颜色”。
那么这能否从数学上进行证明呢？100多年后的1976年，肯尼斯·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）使用计算机辅助计算，用了1200个小时和100亿次的判断，终于证明了四色定理，轰动世界，这就是离散数学与计算机科学相互协作的结果。
参考资料：搜狗百科--离散数学

离散数学题：甲、乙、丙、丁四个人有且仅有两个人参加比赛,

由条件1和2可以推算出 如果丙参加 那么丁页参加 甲乙两人中必须有一人参加 这样就有三人参加 所以得出丙肯定不参加 由条件4可以得出 如果丁不参加 那甲也不参加 丙已经不参加了 这样就会有三人不参加 所以得出丁肯定参加 再根据条件三得出乙不参加 所以参加人为甲和丁

离散数学题，求证循环群的子群仍是循环群？

设G为循环群，那么G有生成元x，使得任何非单位元g属于G，均存在最小的正整数n，满足g=x^n。因此若H是G的子群,其任何元素非单位元h，均有h=x^n的形式。
不妨设d>0是满足x^d属于H的最小整数。任取x^a属于H(a>0)。则x^(am+tn)=(x^a)^m*(x^t)^n属于H。由Euclid辗转相除法知，存在m，n使得：
am+dn=(a，d)>0，表明x^((a，d))属于H，因为a=a1*(a，d)，d=d1*(a，d)，所以x^a，x^d可由x^((a，d))生成。
因此(a，d)<=d。由于d是最小的故(a，d)=d。又x^a是在H中任意取的非单位元。故H中的任何元素均可由x^d生。即H中的非单位元均是形如x^(dn)形式。故H是循环群。
扩展资料：
循环群的性质
1、设(a)是—个循环群，(1)若|a|=∞，则(a)与整数加群Z同构；(2)若IaI=n，则(a)与模n的剩余类加群Zn同构。
2、有且仅有两个元1和-1可以作为整数加群Z的生成元，且在Z中除零元外，每个元的阶都是无限的。
3、在模n的剩余类Zn中，有(1)|[k]|=n/(k，n)；(2)[k]是Zn的生成元<=>(k，n)=1。
参考资料来源：搜狗百科-循环群

离散数学证明题: 设连通图G有k个奇数度的结点，证明在图G中至少要添加k/2条边才能使其成为欧拉图．

图G是欧拉图的充要条件是图G连通且所有的结点的度数都是偶数，因此要使连通图G成为欧拉图，既是要使所有的结点度数变为偶数。
添加一条边后，可能会出现两种情况：
1、边的两端连接在同一个结点上（环），此时该点的度数加2，奇偶性不变；
2、边的两端连接在两个不同的结点上，此时此两点的度数各加1，两个点改变奇偶性。
如题，图G有k个奇度数的结点，要使该图成为欧拉图，需要改变这k个结点的奇偶性，因此最少需要添加k/2条边。

离散数学在具体领域的应用

你看看这个行不？　【摘要】离散数学是计算机科学基础理论的核心,本文介绍了离散数学在人工智能、数据结构、数据库等方面的应用,显示了离散数学在计算机科学中的重要性。
　　【关键词】人工智能 二叉树的遍历 数据库

　　1 引言
　　离散数学是计算机专业的核心基础课,它在计算机科学中有着重要的应用。它是计算机专业课《数据结构》、《操作系统》、《编译原理》、《数据库系统原理》和《数字逻辑》等课的必备基础,因此离散数学是掌握计算机科学理论基础的重要数学工具。本文正是从这一角度出发,介绍离散数学在计算机科学中的重要应用。
　　2 离散数学在计算机学科中的应用
　　2.1 数理逻辑在人工智能中的应用
　　人工智能是计算机学科中一个非常重要的方向,离散数学在人工智能中的应用主要是数理逻辑部分在人工智能中的应用。数理逻辑包括命题逻辑和谓词逻辑,命题逻辑就是研究以命题为单位进行前提与结论之间的推理,而谓词逻辑就是研究句子内在的联系。大家都知道,人工智能共有两个流派,连接主义流派和符号主义流派。其中在符号主义流派里,他们认为现实世界的各种事物可以用符号的形式表示出来,其中最主要的就是人类的自然语言可以用符号进行表示。语言的符号化就是数理逻辑研究的基本内容,计算机智能化的前提就是将人类的语言符号化成机器可以识别的符号,这样计算机才能进行推理,才能具有智能。由此可见数理逻辑中重要的思想、方法及内容贯穿到人工智能的整个学科。
　　2.2 图论在数据结构中的应用
　　离散数学在数据结构中的应用主要是图论部分在数据结构中的应用,树在图论中占着重要的地位。树是一种非线性数据结构,在现实生活中可以用树来表示某一家族的家谱或某公司的组织结构,也可以用它来表示计算机中文件的组织结构,树中二叉树在计算机科学中有着重要的应用。二叉树共有三种遍历方法:前序遍历法、中序遍历法和后序遍历法。
　　2.2.1 前序遍历法:如果二叉树为空,则返回。否则(1)访问根节点(2)前序遍历左子树(3)前序遍历右子树,得到前序序列。
　　2.2.2 中序遍历法:如果二叉树为空,则返回。否则(1)中序遍历左子树(2)访问根节点(3)中序遍历右子树,得到中序序列。
　　2.2.3 后序遍历法:如果二叉树为空,则返回。否则(1)后序遍历左子树(2)后序遍历右子树(3)访问根节点,得到后序序列。
　　通过访问不同的遍历序列,可以得到不同的节点序列,通常在计算机中利用不同的遍历方法读出代数表达式,以便在计算机中对代数表达式进行操作。
　　2.3 集合论在数据库系统理论中的应用
　　集合论是离散数学中极其重要的一部分,它在数据库中有着广泛的应用。我们可以利用关系理论使数据库从网络型、层次型转变成关系型,这样使数据库中的数据容易表示,并且易于存储和处理,使逻辑结构简单、数据独立性强、数据共享、数据冗余可控和操作简单。当数据库中记录较多时,集合中的笛卡儿积方便了记录的查询、插入、删除和修改。
　　2.4 代数系统在通信方面的应用
　　代数系统在计算机中的应用广泛,例如有限机,开关线路的计数等方面。但最常用的是在纠错码方面的应用。在计算机和数据通信中,经常需要将二进制数字信号进行传递,这种传递常常距离很远,所以难免会出现错误。通常采用纠错码来避免这种错误的发生,而设计的这种纠错码的数学基础就是代数系统。纠错码中的一致校验矩阵就是根据代数系统中的群概念来进行设计的,另外在群码的校正中,也用到了代数系统中的陪集。
　　2.5 离散数学在生物信息学中的应用
　　生物信息学是现代计算机科学中一个崭新的分支,它是计算机科学与生物学相结合的产物。目前,在美国有一个国家实验室Sandia国家实验室,主要进行组合编码理论和密码学的研究,该机构在美国和国际学术界有很高的地位。另外,由于DNA是离散数学中的序列结构,美国科学院院士,近代离散数学的奠基人Rota教授预言,生物学中的组合问题将成为离散数学的一个前沿领域。而且,IBM公司也将成立一个生物信息学研究中心。在1994年美国计算机科学家阿德勒曼公布了DNA计算机的理论,并成功地运用DNA计算机解决了一个有向哈密尔顿路径问题,这一成果迅速在国际产生了巨大的反响,同时也引起了国内学者的关注。DNA计算机的基本思想是:以DNA碱基序列作为信息编码的载体,利用现代分子生物学技术,在试管内控制酶作用下的DNA序列反应,作为实现运算的过程;这样,以反应前DNA序列作为输入的数据,反应后的DNA序列作为运算的结果,DNA计算机几乎能够解决所有的NP完全问题。
　　3 结论
　　现在我国每一所大学的计算机专业都开设离散数学课程,正因为离散数学在计算机科学中的重要应用,可以说没有离散数学就没有计算机理论,也就没有计算机科学。所以,应努力学习离散数学,推动离散数学的研究,使它在计算机中有着更为广泛的应用。
　　参考文献
　　[1] 耿素云,屈婉玲,离散数学[M].北京:高等教育出版社<1998.
　　[2] 左孝凌,李永监,刘永才编著.离散数学[M].上海:上海科学技术文献出版社,2004.
　　[3] 朱一清.离散数学[M].北京:电子工业出版社,2004

离散数学在生活中的应用.

离散数学是一门理论兼实际应用的综合性学科，即具有严备的理论基础，又具备应用科学的特点。它是计算机科学和其他应用科学的基础理论课。 离散数学是一门理论兼实际应用的综合性学科，即具有严备的理论基础，又具备应用科学的特点。它是计算机科学和其他应用科学的基础理论课 一般是解决最优化问题，比如很多有联系的事情，按照如何顺序在做能达到用时最少，效果最好。主要用在工程领域和计算机领域。 定义：离散数学是一门理论兼实际应用的综合性学科，即具有严备的理论基础，又具备应用科学的特点。它是计算机科学和其他应用科学的基础理论课。 应用：逻辑与证明，算法，计算方法与分类原理，循环关系，图论，树，网络模型，布尔代数与组合电路，自动化、语法与语言，计算几何。离散数学课程所涉及的概念、方法和理论，大量地应用在 “ 数字电路 ” 、 “ 编译原理 ” 、 “ 数据结构 ” 、 “ 操作系统 ” 、 “ 数据库系统 ” 、 “ 算法的分析与设计 ” 、 “ 软件工程 ” 、 “ 人工智能 ” 、 “ 多媒体技术 ” 、 “ 计算机网络 ” 等专业课程以及 “ 信息管理 ” 、 “ 信号处理 ” 、 “ 模式识别 ” 、 “ 数据加密 ” 等 参考资料： 给老师正浦靠费的 《离散数学》是理工科高等院校计算机专业的重要基础课程，它不仅为后续课程——数据结构、操作系统、编译原理、数据库原理、人工智能等做必要的理论准备，而且在培养学生的创新思维、创新能力和综合素质方面有其独特的作用。 到20世纪下半叶乃至21世纪，随着电气时代乃至计算机时代的来临。对直接与计算机打交道的越来越多的人群来说，最重要的数学趋势不再是以微积分为代表的连续数学，而是以图论、组合学、数论、代数、概率论、运筹学与控制论、数理逻辑等为核心内容的离散分析，也就是离散数学。因为计算机是“离散地”处理、计算、安排、存储、调拨、配置，用“离散”近似（可做到相当精确）逼近“连续”。从中学到大学，从数学专业到理工科专业，离散数学的课程和内容逐步与传统的突出连续数学的课程及内容分庭抗礼，起着越来越显著的作用。 最实际的应用比如说最短路径问题，就要用到离散的图论知识，在物流方面应用广泛。求商场最佳进货量，随不是直接的离散问题，也要用到离散的思想。此外，凡是涉及计算机、数值分析的地方就少不了离散数学。离散数学已经越来越多的影响着人类的生活。

离散数学如何判断前编码

即上述编码是二进制的前缀码。前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。
　　利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。该编码即为最优前缀码（也称哈夫曼编码）。2． 哈夫曼编码为最优前缀码。这个比较复杂，一般记牢好商品条形码中的前缀码（用来标识国家或地区的），加上对批号的认识就差不多了。
　　 欧莱雅在在法国的前缀码是30-37，表示是 。离散数学前缀码，utf-8 是一种针对unicode的可变长度字符编码，也是一种前缀码。其中第09-20项用于设置需要进行ip路由的市话前缀码(1位或2位)。
　　在系统中设置经济线路接入号码，见系统编程项目03(经济线路接入号)，市话经济线路的指定前缀码见系统编程16项（限制代码b)的09~20项输入，是否设置定时参数，见系统编程项目08(定时参数调整)的参数2。
　　c的一个前缀码编码方案对应于一棵二叉树t。则平均码长定义为：使平均码长达到最的前缀码编码方案称为c的最优前缀码。离散数学前缀码，二叉树t表示字符集c的一个最优前缀码，证明可以对t作适当修改后得到一棵新的二叉树t”，在t”中x和y是最深叶子且为兄弟，同时t”表示的前缀码也是c的最优前缀码。
　　二叉树t表示字符集c的一个最优前缀码，x和y是树t中的两个叶子且为兄弟，z是它们的父亲。f(y)的字符，则树t’=t-{x,y}表示字符集c’=c-{x, y} ∪ { z}的一个最优前缀码。