离散

2024-07-20

离散（精选8篇）

1.离散篇一

中央电大离散数学试题

月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，{2}，{1，2}}，则下列表述正确的是()．

A．2AB．{1}A

C．1AD．2  A

2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为

()．

A．6B．4C．3D．

53．设无向图G的邻接矩阵为

0111110011100001100111010

则G的边数为()．

A．1B．7C．6D．14 4．设集合A={a}，则A的幂集为()．

A．{{a}}B．{a，{a}}

C．{，{a}}D．{，a}

5．下列公式中()为永真式．

A．AB  ABB．AB  (AB)

C．AB  ABD．AB  (AB)

二、填空题（每小题3分，本题共15分）

6．命题公式PP的真值是

7．若无向树T有5个结点，则T的边数为．

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i

9．设集合A={1，2}上的关系R＝{<1, 1>,<1, 2>}，则在R中仅需加一个元素，就可使新得到的关系为对称的．

10．(x)(A(x)→B(x，z)∨C(y))中的自由变元有．

三、逻辑公式翻译（每小题6分，本题共12分）

11．将语句“今天上课．”翻译成命题公式．

12．将语句“他去操场锻炼，仅当他有时间．”翻译成命题公式．

四、判断说明题（每小题7分，本题共14分）

判断下列各题正误，并说明理由．

13．设集合A={1，2}，B={3，4}，从A到B的关系为f={<1, 3>}，则f是A到B的函数．

14．设G是一个有4个结点10条边的连通图，则G为平面图．

五．计算题（每小题12分，本题共36分）

15．试求出（P∨Q）→（R∨Q）的析取范式．

16．设A={{1}, 1, 2}，B={ 1, {2}}，试计算

（1）（A∩B）（2）（A∪B）（3）A （A∩B）．

17．图G=，其中V={ a, b, c, d }，E={(a, b),(a, c),(a, d),(b, c),(b, d),(c, d)}，对应边的权值依次为1、2、3、1、4及5，试

（1）画出G的图形；

（2）写出G的邻接矩阵；

（3）求出G权最小的生成树及其权值．

六、证明题（本题共8分）

18．试证明：若R与S是集合A上的自反关系，则R∩S也是集合A上的自反关系．

中央电大2010年7月离散数学

试题解答

(供参考)

一、单项选择题（每小题3分，本题共15分）

1．B2．D3．B4．C5．B

二、填空题（每小题3分，本题共15分）

6．假（或F，或0）

7．48．t-

19． <2, 1>

10．z，y

三、逻辑公式翻译（每小题6分，本题共12分）

11．设P：今天上课，（2分）则命题公式为：P．（6分）

12．设 P：他去操场锻炼，Q：他有时间，（2分）则命题公式为：P Q．（6分）

四、判断说明题（每小题7分，本题共14分）

13．错误．（3分）因为A中元素2没有B中元素与之对应，故f不是A到B的函数．（7分）

14．错误．（3分）不满足“设G是一个有v个结点e条边的连通简单平面图，若v≥3，则e≤3v-6．”（7分）

五．计算题（每小题12分，本题共36分）

15．（P∨Q）→（R∨Q） ┐(P∨Q)∨（R∨Q）（4分）

(┐P∧┐Q)∨（R∨Q）（8分）

(┐P∧┐Q)∨R∨Q（析取范式）（12分）

16．（1）（A∩B）={1}（4分）

（2）（A∪B）={1, 2, {1}, {2}}（8分）

（3）A（A∩B）={{1}, 1, 2}（12分）

17．（1）G的图形表示如图一所示：ad1

5b c（3分）图一

（2）邻接矩阵：

01101111（6分）1101

1110

（3）最小的生成树如图二中的粗线所示：

a 3d5

b图二1c

权为：1+1+3=5

六、证明题（本题共8分）

18．证明：设xA，因为R自反，所以x R x，即< x, x>R；

又因为S自反，所以x R x，即< x, x >S．即< x, x>R∩S故R∩S自反．

10分）12分）（4分）（6分）（8分）（（

2.离散篇二

关键词：离散数学,兴趣,课堂教学

离散数学课程与传统的大学数学课程 (如高等数学) 有很大的区别, 高等数学研究的一般是自变量在区间上连续变化的函数, 而离散数学是研究离散变量及其相互关系的学科, 如自然数、真假值等等。这门课程是随着计算机的发展而产生的 (机器语言只有0、1两个离散值) , 因此开设这门课程的专业都是与计算机关系密切的专业, 如信息与计算科学、计算机科学与技术、信息管理、电子商务、物联网等。

众所周知, 高等数学有大家公认的经典和传统的教材, 即使版本不同, 内容也大同小异, 而离散数学一般是学校根据自己专业的培养目标和方向自行定制教材, 内容的侧重点也不尽相同, 但无论哪一种教材, 都会包括四部分内容:数理逻辑、集合论、代数系统和图论, 这其实是数学专业需要分开学习的四门课程, 相对比较枯燥, 离散数学教材将这些放在一起, 每一部分都介绍了与计算机技术相关的内容, 不像数学专业学的深入, 但涉及的面很广, 对学生而言非常困难。和高等数学比较, 由于学生从中学开始就接触函数, 因此高等数学课程的入门相对容易, 课程前后的内容联系紧密, 开始学习时学生感觉不会太困难。但离散数学不同, 学生以前基本没有接触过相关的知识, 并且内容前后之间又没有必然的联系 (充分体现了离散性) , 学习后面的经常忘记前面的, 这就给学生的学习制造了很多的麻烦, 他们普遍认为离散数学不好学, 甚至有个别学生最后只能放弃。俗话说, 兴趣是最好的老师, 鉴于以上这些原因, 本文根据这四部分内容, 谈谈如何在课堂教学中提高学生的学习兴趣。

1 数理逻辑之趣

逻辑学简单地讲, 就是研究推理的学科, 数理逻辑也不例外, 它是运用一套符号体系加上一些规则, 研究我们生活中的一切与推理有关的问题, 这不就让课堂生动起来了吗?比如生活中有这样的叙述:“情况并非如此, 如果他不来, 那么我也不去。”这句话如果说给外国人听, 他们一定会觉得云山雾罩的, 即便是中国人自己, 能够理解清楚也不是很容易吧, 到底是他来或不来, 我去还是不去呢?现在我们用数理逻辑的理论去研究, 看看到底说的什么意思?设P表示“他来”, Q表示“我去”, 这句话翻译成逻辑语言是:┐ (┐P→┐Q) , 利用推理规则得到与之等价的命题┐P∧Q, 再将其还原回生活语言就是“他没来, 但我去了”, 如此之简单, 学生恍然大悟, 马上会兴趣倍增的。再有, 课堂上如果让学生分析下面这段程序, 结果会怎样呢?“If A then if B then X else Y else if B then X else Y”, 就是对计算机专业的学生而言, 理解程序的条件和结论也不容易吧, 但程序肯定是正确的, 计算机也是可以执行的, 现在让我们用数理逻辑理论化简一下吧。执行X的条件: (A∧B) ∨ (┐A∧B) , 化简后等价于B;执行Y的条件: (A∧┐B) ∨ (┐A∧┐B) , 化简后等价于┐B, 结果出乎人们的意料, A在程序中根本没起作用, 纯属捣乱而已, 此程序实际可以简化为:“If B then X else Y”。如此好玩的问题, 与日常生活和学生的专业又有密切的联系, 我们可以想象一下, 学生学习起来会多么高兴, 又怎么会在课堂上睡觉呢?

2 集合关系之趣

在生活中, 存在着各式各样的关系, 如父子关系、夫妻关系、朋友关系、上下级关系等等, 这些关系看起来各不相同, 但很多关系却可以用数学思想抽象出它们共同的性质。离散数学集合论部分涉及到的就是研究各种各样的关系, 如等价关系、序关系等等, 研究这些关系, 也是非常有趣的事情。比如利用“同姓”关系, 可以将人群分类:{张}、{王}、{李}、{欧阳}、{诸葛}……等等, 如果要研究同一姓氏的人有什么共同特征时, 可以分别从不同的姓氏集合中, 任取一个人进行研究, 这个人可以作为每一类姓氏人群的代表, 他有的特征和他同类的人都有;再比如平常说的“家族”关系, 可以理解为集合中的复合关系, 如果R是“父子”关系, S是“兄弟”关系, 那么R○R表示“祖孙”关系、S○R表示“伯侄”关系等等, 只要将条件设计好, 红楼梦中的林黛玉和王熙凤之间的关系也可以用数学语言表示出来。事实上, 生活中的所有关系都是可以用数学符号描绘出来的, 这方面可以引导学生自己去探索, 以便提高他们的学习兴趣。

3 代数系统之趣

代数系统是离散数学中最抽象的一部分, 它在数学学科中属于抽象代数的内容, 怎样用生活中有趣的例子解释、描述抽象的概念, 是课堂教学需要认真研究的问题之一。事实上, 在集合中定义运算, 是构成代数系统的关键, 而运算就是函数, 比如一台自动售货机, 它接受人民币, 吐出各种商品, “两个一元对应一瓶橙汁, 一个一元和一个二元对应一瓶可乐, 两个二元对应一个冰淇淋”等等, 这就是运算, 如果再对运算要求具有封闭性, 就构成了代数系统。再如定义代数系统的幺元和零元时, 可以用“洗衣”的例子说明, 用洗衣机洗衣服时, 浅色和浅色混洗后, 衣服还是浅色;浅色和深色混洗后, 衣服变成了深色;深色和深色混洗后, 衣服还是深色, 可以令S={浅色, 深色}, “*”代表“洗衣”这种运算, 那么对于代数系统<S, *>而言, “浅色”是系统的幺元;、“深色”是系统的零元, 让学生想象浅色和深色的特征, 就可以充分理解幺元和零元的概念了。还有, 群的概念在代数系统中非常典型和重要, 不了解群就等于没有学过代数系统, 那么群到底有什么, 换句话说, 我们熟悉的什么样的事物可以是群呢?从群的概念考虑, 群中对所定义的运算要有幺元, 每一个元素还要有逆元, 假设定义的运算是“加法”, 幺元一定是0, 那么每个元素的逆元应该是其相反数, 也就是说, 它的相反数也必须是集合中的元素, 故集合必须是关于0对称的 (对加法运算) , 由此得到, 整数集合上定义加法运算构成群;实数集合上定义加法运算也构成群;但非负有理数上定义加法运算就不会构成群了, 一句话, 构成群的集合一定是对称的 (关于运算) , 这时可以提问:如果换成乘法运算, 什么样的集合对乘法运算构成群呢?这样的分析一环扣一环, 让学生跟着教师的思路去思考, 既有趣又有成就感, 而且又将概念讲解的非常到位, 学生怎么会不喜欢这样的课堂呢?

4 图论之趣

位于波罗的海海岸的美丽小城———格尼斯堡, 在图论的起源和发展中占有绝对重要的地位, 由著名的“格尼斯堡七桥”问题, 数学家欧拉创立了一个重要的数学分支———图论。“格尼斯堡七桥”问题实际是一个“一笔画”问题, 应用欧拉的理论, 对任何一个图形, 都可以很快知道它是否可以一笔画出, 这是一件多么了不起的工作啊!图论帮我们解决了很多现实问题, 如环游世界问题、匹配问题、最优化问题等等, 尤其是“树”的概念的引进, 在日常生活和计算机理论中, 应用相当的广泛。比如百姓的“家谱”就是一棵“根树”, 树根是“祖宗”, 平行边是“兄弟”, 上下相邻的两个顶点分别表示“父亲”和“儿子”, 看到一颗“家谱树”, 马上就清楚了谁是谁的“祖先”, 谁又是谁的“后裔”, 一目了然。再如“购买接线板的问题”, 寝室有28盏电灯, 要共用一个电源插座, 需要购买多少个具有四孔的接线板?这是图论中“完全四叉树求分支点”的问题, 让学生带着问题去思考, 自己解决, 既生动又实用, 何乐而不为呢?

兴趣是最好的老师, 不论一门课程多么抽象、复杂, 首先要求教师深刻地理解课程内容, 要用通俗易懂的语言讲授给学生, 同时要调动学生学习的积极性, 让学生有“我要学”的冲动, 那么这门课就一定可以学好。S

参考文献

[1]左孝凌, 等.离散数学[M].上海:上海科技文献出版社, 1982.

3.离散分配式存储管理篇三

【关键词】分页式存储管理；物理地址；逻辑地址；地址重定位；页表；快表

【Abstract】This paper proposes a way to allocate memory discrete - page memory management， and discusses its basic ideas and address translation. Finally， the shortcomings of the storage management.

【Key words】Page memory management；Physical address；Logical address；The relocation；Page table；Fast table

存储管理是操作系统五大功能之一，是操作系统的重要课题。在存储管理中，连续分配方式会产生许多“碎片”，而这些“碎片”空间很小，无法容纳相关作业。通常通过“紧凑”方法，移动程序可以将许多“碎片”拼接成可用的大块空间，但是通过“紧凑”方法，移动程序增加了系统的开销。如果允许将作业直接分散地装入到许多不相邻、不连续的分区中，则无须再进行“紧凑”。基于这一思想而产生了离散分配方式，分页式存储管理就是其中的一种。

1. 分页式存储管理的基本思想

物理地址是内存储器中的实际有效地址，逻辑地址用是户程序中使用的地址，也就是访内指令给出的地址叫逻辑地址。

1.1 分页存储管理允许把一个作业存放到若干不相邻、不连续的分区中，这样既可免去移动信息所造成的系统开销，又可尽量减少内存产生碎片，其基本思想是：

（1）把物理地址空间分成大小相等的许多分区，每个分区称为“块”或“帧”，每个块有一个编号，从“0”开始编号，块是存储分配的单元；

（2）按块的大小把逻辑地址空间分成许多“页”，从“0”开始编号；

（3）逻辑地址形式：作业的逻辑地址与一个数对（页号，页内位移）一一对应；

（4）采用分页式存储管理，作业一次性全部装入内存，作业进入内存时其连续的页面可以装入内存中不相邻、不连续的块中，只要内存有空闲块，作业的某一页可以放到内存任一空闲块。

1.2 例如：用户作业A的大小为3KB，内存块的大小为1KB，当作业提交给系统后被分成了3页，如图1（a）所示，根据图1（c）页表（页与块的对应关系），作业A被装进了内存不相邻、不连续块中，如图1（b）所示。

2. 页面的大小

在分页存储管理中的页面的大小要适中。页面如果太小，虽然可以使内存碎片减小，减少了内存碎片的总空间，有利于提高内存利用率，但也会使每个作业占用较多的页面，从而导致作业的页表过长，占用大量内存，此外，还会降低页面换进换出的效率；页面如果较大，虽然可以减少页表的长度，提高页面换进换出的速度，但却又会使页内碎片增大，降低内存利用率（分页存储管理的实现见图1）。

3. 分页式存储管理的地址转换

3.1 页表与快表。

（1）分页系统中，将作业的各个页面离散地存储在内存不连续的物理块中，系统应能保证进程的正确运行，即能在内存中找到每个页面所对应的物理块。为此，系统为每个作业建立了一张页面映像表，简称页表。配置了页表后，作业执行时，通过查找页表，找到每页在内存中的物理块号。页表的作用是实现从页号到物理块号的地址映射。

（2）由于页表是存放在内存中，CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内位移拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据（或向此地址中写入数据）。因此，采用这种方式将降低CPU访问速度，增加了系统在存储上的开销。为了提高地址变换速度，可在地址变换机构中增设一个具有并行查寻能力的特殊高速缓冲寄存器，又称为“联想寄存器”（Associative Memory），或称为“快表”，地址变换过程是：在CPU给出有效地址后，由地址变换机构自动地将页号送入高速缓冲寄存器，并将此页号与高速缓存中的所有页号进行比较，若其中有与此相匹配的页号，便表示所要访问的页表项在快表中。于是，可直接从快表中读出该页所对应的物理块号，并送到物理地址寄存器中。如在块表中未找到对应的页表项，则还须再访问内存中的页表，找到后，把从页表项中读出的物理块号送地址寄存器，同时，再将此页表项存入快表的一个寄存器单元中，重新修改快表。

3.2 地址重定位。

地址重定位指把目标程序中的逻辑地址转换成主存空间的物理地址，分页式存储管理采用的是动态重定位，程序在执行时过程中动态完成地址重定位，需要硬件的支持，地址转换过程如下：

（1）作业的逻辑地址转换成页号，页内位移两部分，页号=逻辑地址/块尺寸，页内位移=逻辑地址%块尺寸（“/”是整除运算符，“%”是求余运算符）；

（2）以页号为索引去检索页表，在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，表示本次所访问的地址已超越作业的地址空间，系统将产生一个地址越界中断，如果没有出现越界错误，通过查找页表，找到页号对应的块号；

（3）块号*块尺寸+页内位移得到物理地址，这样完成从逻辑地址到物理地址的变换。

3.3 举例分析。

3.3.1 分页系统中内存被划分成4块，每块4KB，某作业的逻辑地址空间共划分成4个页面，当前页与块对应关系表（页表）如表1所示，试求出对应于下列逻辑地址的物理地址：（a）4100（b）8300。（见表1）

3.3.2 解：（a）逻辑地址4100对应的页号是：4100/4096=1 ，对应的页内位移是：4100%4096=4，用1去查页表，知道第1页现在存放在内存的第1块，第1块的起始地址为4096（4KB），因此，逻辑地址4100所对应的物理地址是：4096+4=4100；

（b）虚拟地址8300对应的页号是：8300/4096=2，对应的页内位移是：8300%4096=108，用2去查页表，知道第2页现在存放在内存的第6块，第6块的起始地址为6×4K=24576，因此，逻辑地址8300所对应的物理地址是24576+108=24684。

4. 分页式存储管理的缺点

（1）分页式存储管理中，作业的最后一页大小可能与内存块大小不吻合，会产生内部碎片，浪费内存空间；

（2）分页式存储管理中，作业需要一次性全部装入内存，当作业尺寸大于内存剩余空间时，作业无法进入内存运行，因此，分页式存储管理不具备虚拟存储技术。

参考文献

[1] 宗大华，宗涛，陈吉人. 操作系统[M].3版.北京：人民邮电出版社， 2011： 57～66.

[2] 张尧学，史美林.计算机操作系统教程[M]. 北京：清华大学出版社， 1993.

4.《离散数学》课程总结篇四

转眼之间，这学期要结束了。我们的离散数学，这门课程的学习也即将接近尾声。下面就是我对这门课一些认识及自己的学习心得。

首先我们这门课程离散数学到底包含了哪几大部分？每部分具体又有什么内？这门课程在计算机科学中有什么地位？这门课程在我们以后的学习生活中，以及在将来的工作中有什么帮助？下面我将以上几个方面具体谈一谈并将总结一下自己本人在这门课程学习过程中遇到的一些问题和心得体会。

这门课程有数理逻辑，集合论，代数系统和图论四部分。这四大部分通常被称为离散数学的四大体系。其中每一部分都是一个独立的学科，内容丰富。而我们离散数学中的内容是其中最基本，最重要且和计算机科学最密切相关的内容吸收到离散数学中来，并使它们前后贯通，形成一个有机整体。这门课的主要内容有命题逻辑、谓词逻辑，属于数理逻辑部分，集合论中有集合、二元关系、函数，代数系统包含代数系统基础、群、环、域以及格和布尔代数的知识（这部分我们没有涉及）。

那么这门课程在计算机科学中有着什么样的地位呢，这门课程是计算机科学专业中重要的专业基础课程，核心课程，可以这么说，离散数学，既是一门专业基础课，是一门工具性学科。这门课讲授的内容，与后续专学习业密切相关。在这门课里我们讲授了大量的计算机学科专业必要的基本概念，基本理论和基本方法。为我们以后的学习，工作打下良好基础。在算法设计，人工智能，计算机网络，神经网络，智能计算等学科中有着重要的作用。在计算机科学中有着广泛的应用。通过这门课可以对我们计算机算法的理解和逻辑思维得到提高。

那么我们具体学了什么内容呢？

（一）首先集合论是整个数学的基础，（不管是离散数学还是连续数学）如果没有专门学过，那么出现在离散数学中还是很合适的。至于由集合论引出的二元关系，函数的内容，也是理所应当的。

数理逻辑是一个让人眼前一亮的东西。我第一次发现，原来有些复杂的推理问题是可以通过“计算”的方法解决的。

数理逻辑，又叫符号逻辑。就是依靠专门的数学符号去推导过程对的科学。在推导过程中，我们探索出一套完整的规则。这个规格就是我们的推理规则。竟然为了确保这套规则的，准确性。防止二义性，以至于可以将公理理论公式化，依据各项规则，证得论证的有效性。

这一章里，我们首先学习了，命题逻辑的基本概念。并和一些逻辑连接词。包括真值连接词的否定，真值连接词合取，析取。我们可以用，符号形式写出各种命题，并利用真值表来判断命题的真假。用真值表来判断，命题是十分有效方便的。所以，对于真值表的记忆是十分重要的。命题公式的表示，也是用符号话的需要来给出的。随后我们学习了永真式和永假式，对于永真式和永假式的证明，用制表技术可以方便的给出。对于永真式，因为原子命题变元，不论表示什么命题，是真的还是假的，它总是真的。所以它反映的是命题逻辑的逻辑规律。所以我们着重研究永真式。下面，在一个公式中，如果用另外的是替换其中某个或某些原子命题变元，就会得到全新的公式，这个全新的公式，和原公式什么关系呢？进而引出了我们的代入规则和替换规则。为了更方便的证明各种命题，我们学习了，等价和蕴涵的各种定理，还有范式和范式的判定问题，其中主要是主析取范式和合取范式的概念，定理，证明。证明过程我们在课上都已经证明过了。在这一章还学习了三段式的证明，此证明方法在以后的学习过程中经常使用。

谓词逻辑就是对命题和推理做深一步的研究的学习。在谓词演算中，原子命题分为谓词和个体两部分。谓词逻辑就是将命题的内涵，通过个体和谓词中的表现出来，把同一类命题，用命题函数表示，增强其表达能力。在这里要注意的是，命题还是不是命题，因为其没有确定的真假异议，但是可以将一个命题函数转化为问题，方法有二，（1）用个体域中的特定个体去替换个体变元；（2）这个体域上，将命题函数量化。所谓量化，就是用量词的命题函数中的个体变元进行约束，由此引入了量词的概念。量词分为全称，量词与存在量词，量词反映了个体域与量词间的真假关系。此外，在谓词逻辑中，个体的个体域也是很重要的。将一个命题用谓词，逻辑符号化时，通常经以下步骤（1）确定特性谓词及其他谓词。（2）确定量词。（3）量词与逻辑连接词的搭配。有了量词的概念后，谓词逻辑表达能力就让广泛了，它所刻画的语句也也更为普遍，更为深刻。

代数系统，在计算机科学中也非常重要。在计算机科学中带出系统科，用作研究，抽象数据结构的性能及操作，也是程序设计语言的理论基础。

图论这一章里，我们学习的图并不是几何学中的图形。而是客观世界中某些事物具体联系的一个数学抽象。用点代表事物，用边表示各事物间的二元关系。这一章刚开始学的概念很多，让我感觉有些乱。所以在课后要自己多下功夫了。

然后就是我在学习中出现的一些问题及解决方法了，今天，在学习数理逻辑的时候，觉得离散数学这门课程很简单。但是随着学习的进一步深入，我发现我的想法是错误的。对于后面的一些推理论证，自己缺乏思路。虽然，老师在课上也教给了我们推理的方法，但是，还是忍不住去看书上的证明。这一点在随后的学习中，我一般尽量克服，也是在老师的帮助下，在证明时尽量自己想，憋自己一下，让自己的思维得到训练，自己的推理论证能力得到提高。进而使综合素质，都要提高。

再说一下李勇老师的讲课吧，讲的非常棒。首先它会对每一部分的内容，及，基本概念给大家进行讲解。然后就是强调自己的推理能力。每节课都会让我们自己推理，验证定理。从基础出发，从小定理验证到大定理，由特殊推广到一般。一般都会让我们从两三个开始验证，逐步得到结论，发现规律。一次，李勇老师对，课堂教学有着自己深刻的理解，对这门课的教学方法，教学模式有着独特的看法。还有就是李勇老师，朋辈式的教学方法，在教学过程中，我们共同进步，教学相长，这样是非常好的。

5.离散数学论文篇五

摘要：

离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。

关键字：离散数学、电路设计、软件技术、应用

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】离散数学耿素云、屈婉玲、张立昂编著清华大学出版社

6.离散数学考试大纲篇六

一、考试要求共济

要求考生系统地掌握离散数学的基本概念、基本定理和方法，具有较强的逻辑思维和抽象思维能力，能够灵活运用所学的内容和方法解决实际问题。考

二、考试内容济

1、数理逻辑济

1)命题和联结词，谓词与量词，合适公式，赋值，解释与指派，范式共

2)命题形式化，等价式与对偶式，蕴含式，推理与证明

3)证明方法3

4)数学归纳法

2、集合论院

1)集合代数，笛卡尔乘积，关系与函数，关系的性质与运算

2)等价关系，划分共济

3)偏序关系与偏序集，格辅导

3、计数336260 37

1)排列与组合，容斥原理，鸽巢原理共

2)离散概率正门

3)函数的增长与递推关系院

4、图论共济网

1)欧拉图与哈密顿图，平面图与对偶图，二部图与匹配，图的着色021-

2)树，树的遍历，最小生成树正门

3)最短路经，最大流量

5、形式语言与自动机院

1)语言与文法，正则表达式与正则集

2)有限状态自动机，自动机与正则语言

6、代数系统

1)二元运算，群与半群，积群与商群，同态与同构

2)群与编码

3)格与布尔代数，环与域

三、试卷结构

1、考试时间为3小时，满分100分。

2、题目类型：计算题、简答题和证明题。

参考书

1．离散数学，胡新启，武汉大学出版社，2007年。

2．离散数学，尹宝林、何自强、许光汉、檀凤琴等，高等教育出版社，1998年。

7.《离散数学》教学方法探讨篇七

合理调整、安排教学内容

由于高校的持续扩招, 生源的素质和基础已是今非昔比。《离散数学》的教学内容多且抽象, 其教授过程即使在学生情况很好的时候一般也要花100左右学时。为了给学生减负, 目前课时已被压缩到了64学时, 加之大班化教学、时间又是安排在一年级第二学期, 其结果就可想而知了。

鉴于以上原因, 笔者根据实际情况对教学内容进行了取舍, 力争让学生在较少的学时内, 实实在在地掌握《离散数学》的基本理论和思想方法, 而不再过分拘泥于具体的内容。在这64学时内, 只安排了数理逻辑、集合论、关系和图论等基本内容, 满足了绝大部分学生的实际条件和需要, 学生反映非常不错。对于更加抽象的代数系统、格和布尔代数等内容则放在了三年级时作为选修课开设, 并定为32学时。那些有进一步学习要求、特别是有考研愿望的学生可以参加选修。如此一来, 分散了教学的难度, 使得教师在各个阶段都比较容易掌控教学进程, 既保证了相关后续课程的学习不受影响、又不会给大部分同学造成不必要的负担, 同时还保证了有兴趣和能力的同学有深入学习的机会, 可算是三全其美。

采用形式多样的教学方法

概念多、内容抽象是《离散数学》固有的特点, 如果完全使用传统的、单调呆板的课堂教学方法, 很难唤起学生的学习兴趣和热情, 必须更新教学观念, 改进教学方法, 激发学生学习的兴趣, 这样才能改善教学效果。

1. 认真重视课堂教学。

由于课堂教学是全日制本科教学的最主要的形式, 也是《离散数学》教学的最重要的环节, 所以必须结合课程特点、充分利用好课堂内的时间, 以达到最好的效果。

2. 讲解速度快慢得当。

对于刚刚接触《离散数学》的学生来说, 课程中的一系列思考问题、处理问题的方式和方法同他们以前接触的数学方法是很不同的, 此时如果按照正常的教学进度进行的话, 势必造成绝大部分学生疲于应付, 一般达不到非常好的教学效果。

为此, 笔者在具体讲授时, 基本是依据知识的难易程度和学生对该类知识的熟悉程度来分配时间。比如“命题逻辑”开头的内容其实并不很难, 但由于学生是初次接触这类知识, 接受速度不会太快, 而这些基本的概念对于此章以及“谓词逻辑”的学习有着非常重要的意义, 所以我们安排了比较多的时间, 做了细致的讲解, 使学生对相关基本概念有了很好的掌握。又如“集合论”基本内容是学生已经熟知的, 因此只花较少时间复习了一下重点概念, 基本没有影响后续内容的学习。

3. 提高课堂教学表现力。

教书是艺术, 讲台就是舞台, 教师是导演和演员, 备课内容是剧本, 讲台下的学生则是观众。演出效果的好坏与剧本的选择、导演操控能力以及演员的表演才能都有着非常大的关系。由于初学时大部分学生认识不到《离散数学》对计算机专业的重要性, 加上课程内容本身较难, 上课容易开小差, 教师授课时采用了具有感染力的讲授方式来吸引学生的注意力, 充分发挥了教师的主导作用, 驾驭好课堂时间, 增强了课堂教学效果。

4. 培养学生的学习兴趣。

兴趣是学习最有效的动力, 兴趣可以使学习从被动转为主动。在具体讲解时, 我们将《离散数学》知识的应用场景都解释清楚, 让学生充分认识到这门课程在计算机科学中的重要性。同时, 将计算机学科中最基本研究思路及研究方法传授给了学生, 着力培养学生的抽象思维能力, 增强他们对《离散数学》在计算机专业的地位的认识, 从而提高了他们学习的主动性和自觉性。

5. 注重师生间互动和双向交流。

课堂上我们注重了师生间的互动, 多采用提问式、疑问式、反问式的语句。同时, 为了随时检验课堂内容的教学效果, 在课堂教学过程中, 也适当地请学生上黑板上来做题, 并且由其它学生对该同学在黑板上做出的结果进行批改, 以此充分调动学生的学习积极性, 实现双向交流, 提高了学生的听课效率。

6. 适时小结。

《离散数学》内容多、前后依赖性强, 学生一节课的疏忽可能就会影响之后的听课兴趣, 因此必须经常进行小结。《离散数学》一般都会安排两节课连续上, 第一节课开始会对上一次课的内容进行小结, 第二节课开课前会对第一节课的内容进行小结。每节、每章讲完后也适当进行小结, 总结了应该掌握的知识点, 给同学们一个总的印象, 让同学们在小结中进行自我评价、自我提高。

7. 重视习题和习题课的安排。

在课堂上学习的知识要通过一定的练习来巩固, 《离散数学》课程的作业尤其重要。每次课后都会安排一些习题, 并强调独立完成, 反复申明练习是一个双向检查的过程, 不光是在检查学生学习的情况, 也是检查教师教学效果, 学生有责任真实地反映实际的情况。

在认真批改学生作业的基础上, 我们不断总结课堂教学情况, 对于错误比较多的题目, 及时进行了讲解, 必要时还选择重讲相关内容。另外, 在计划教学进度时适当地设置一些时间给习题课, 并灵活安排在恰当的时候, 一方面总结阶段学习的情况, 另一方面解决习题中集中出现的严重问题。此外, 还准备一些综合性的习题给学生练习, 让学生的认识有更进一步的提高。

合理运用多媒体教学手段

《离散数学》的相关专题都是建立在大量的定义、定理基础上的, 我们采取了多媒体的手段制作课件, 这样既能用更加生动直观的图、表来表达内容, 又可以让老师从大量的板书中摆脱出来, 有更多机会与学生进行互动和交流。另外, 对于有些章节, 如“图论”部分, 使用了动画制作技巧后, 可以非常简单、生动地将图形的变化过程描述清楚, 而以往则需要老师口干舌燥地解释半天, 也未必能达到理想的效果。

充分利用网络教学手段

当今时代, 网络上视频教学材料、教案、习题等各种教学资源应有尽有, 我们充分地利用这些资源, 提高了自身的业务素质, 从而能更好地进行离散数学的教学组织活动及教学改革实践。此外, 我们还积极引导学生主动利用这些网络资源, 并学会在网络环境中与老师、学长以及其他网友进行有关问题的交流, 解决自己的疑难问题。

8.离散篇八

例1 （2016·江苏盐城）甲、乙两位同学参加数学综合素质测试，各项成绩如下（单位：分）：

如果数与代数、空间与图形、统计与概率、综合与实践的成绩按3：3：2：2计算，那么甲、乙的数学综合素质成绩分别为多少分？

【解析】运用加权平均数的计算公式进行计算：甲的数学综合素质成绩为[90×3+93×3+89×2+90×23+3+2+2]=90.7（分），乙的数学综合素质成绩为[94×3+92×3+94×2+86×23+3+2+2]=91.8（分）.

【点评】在实际生活中，一组数据中各个数据的重要程度并不总是相同的，有时有些数据比其他数据更重要.所以，我们在计算这组数据的平均数时，往往根据其重要程度，分别给每个数据一个“权”.一般地，对于n个数x1， x2，…， xn，它们的权依次为w1 ， w2 ，…，wn，则称 [x1w1+x2w2 +…+xnwnw1+w2 +…+wn]为这组数据的加权平均数.

二、求中位数和众数

例2 （2016·江苏苏州）根据国家发改委实施“阶梯水价”的有关文件要求，某市结合地方实际，决定从2016年1月1日起对居民生活用水按照新的“阶梯水价”标准收费，某中学研究性学习小组的同学们在社会实践活动中调查了30户家庭某月的用水量，如下表所示：

则这30户家庭该月用水量的众数和中位数分别是（）.

A.25 ，27.5 B.25，25

C.30 ，27.5 D.30，25

【解析】由统计表可知，这组数据一共有30个数据，分别是3个15，6个20，7个25，9个30和5个35，其中30出现的次数最多，达9次，因此所求众数为30；同时可以将这30个数据理解成是从小到大排列的，中位数是第15、16个数据的平均数，由于第15、16个数据都是25，因此所求中位数为25.故选D.

【点评】众数是一组数据中出现次数最多的数据.中位数是将一组数据按大小顺序排列，处于最中间位置的一个数，或者是处于最中间位置上的两个数的平均数.也就是说：如果一组数据共有n个，那么按照大小顺序排列后，当n为奇数时，中位数就是第[n+12]个数，当n为偶数时，中位数就是第[n2]、（ [n2][+1]）个数的平均数.

例3 （2016·山东威海）某电脑公司销售部为了定制下个月的销售计划，对20位销售员本月的销售量进行了统计，绘制成如图所示的统计图，则这20位销售人员本月销售量的平均数、中位数、众数分别是（）.

A. 19，20，14 B. 19，20，20

C. 18.4，20，20 D. 18.4，25，20

【解析】由扇形统计图可知：销售12台的人数是20×20%=4（人），销售14台的人数是20×25%=5（人），销售20台的人数是20×40%=8（人），销售30台的人数是20×15%=3（人），所以这20位销售人员本月销售量的平均数为[12×4+14×5+20×8+30×320]=18.4（台）；把这些数从小到大排列，第10、11个数均为20，所以中位数为20；销售20台的人数最多，所以众数为20.故答案选C.

【点评】扇形统计图中的信息，还可以直接理解成“12台”的权为“20%”，“14台”的权为“25%”，“20台”的权为“40%”，“30台”的权为“15%”，所以这组数据的平均数为12×20%+14×25%+20×40%+30×15%=18.4（台）；扇形统计图中，从“12台”起顺时针方向排列可以看成是将数据从小到大排列，累计第50%、51%的位置都对应“20台”，所以中位数为20；“20台”的权重最大，达“40%”，所以众数为20.这样一种理解，既简单，也更趋于本质.

三、求方差

例4 （2016·四川达州）已知一组数据0，1，2，2，x，3的平均数是2，则这组数据的方差是 .

【解析】由“这组数据的平均数是2”易求得x=4，然后运用方差公式求出这组数据的方差为=[16][（0-2）2+（1-2）2+（2-2）2+（2-2）2+（4-2）2+（3-2）2]=[53].故答案为[53].

【点评】描述一组数据的离散程度的方差是指这组数据与它们的平均数的差的平方的平均数，如果一组数据x1、 x2、…、xn 的平均数为[x]，那么它的方差可表示为s2=[1n][（x1-[x]）2+（x2-[x]）2+…+（xn -[x]）2].

四、数据集中趋势的灵活应用

例5 （2016·湖南怀化）某校进行书法比赛，有39名同学参加预赛，只能有19名同学参加决赛，他们预赛的成绩各不相同，其中一名同学想知道自己能否进入决赛，不仅要了解自己的预赛成绩，还要了解这39名同学预赛成绩的（）.

A. 平均数 B. 中位数

C. 方差 D. 众数

【解析】39个不同的成绩按大小顺序排列后，中位数之前的共有19个数，所以只要知道自己的成绩和中位数就可以知道是否进入决赛.故答案选B.

【点评】当一组数据中个别数据与其他数据的大小差异很大时，通常用中位数来描述这组数据的集中程度.中位数从“中等水平”的角度（位置处于“最中间”）描述一组数据的集中趋势，克服了极端值对“平均水平”的影响.

例6 （2015·浙江宁波）在端午节到来之前，学校食堂推荐了A，B，C三家粽子专卖店，对全校师生爱吃哪家店的粽子作调查，以决定最终向哪家店采购.下面的统计量中，最值得关注的是（）.

A. 方差 B. 平均数 C. 中位数 D. 众数