离散数学课件作业

离散数学课件作业（推荐9篇）

离散数学课件作业篇1

作业一

一、单项选择题（共 8 道试题，共 80 分。）

1.本课程的教学内容分为三个单元，其中第三单元的名称是（A）． A.数理逻辑 B.集合论 C.图论 D.谓词逻辑

满分：10 分

2.本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（D）． A.函数

B.关系的概念及其运算 C.关系的性质与闭包运算 D.几个重要关系

满分：10 分

3.本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（B）讲． A.18 B.20 C.19 D.17 满分：10 分

4.本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（C）． A.集合恒等式与等价关系的判定 B.图论部分书面作业 C.集合论部分书面作业 D.网上学习问答

满分：10 分

5.课程学习的平台左侧第1个版块名称是：（C）． A.课程导学 B.课程公告 C.课程信息 D.使用帮助

满分：10 分

6.课程学习的平台右侧第5个版块名称是：（A）．

A.典型例题 B.视频课堂 C.VOD点播 D.常见问题

满分：10 分

7.“教学活动资料”版块是课程学习的平台右侧的第（C）个版块． A.6 B.7 C.8 D.9 满分：10 分

8.课程学习的平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（D）． A.复习指导 B.视频 C.课件 D.自测

离散数学是计算机科学与技术专业的一门必修课，是学习其它课程的的一门基础专业课，学好这门课对今后学习其他的专业课非常重要。我对学习的安排如下： 1 在学习过程中准备按三个阶段完成学习：（1）分章节，共七个内容，集合及其运算、关系与函数、图的基本概念与性质、几种特殊图、树及其应用、命题逻辑、谓词逻辑，分别掌（2）看网上论坛及相关资料进行知识再现及巩固；（3）通过习题进行自测。

在学习形式上，合理利用一切资源：（1）VOD点播、视频课堂、典型例题、常见问题、课程拓展、及网上论坛等进行初步学习；（2）利用课本上练习题进行自测学习等；（3）求教在线老师；（4）与同学进行讨论。做到反复练习并勤于思考，熟练记忆基本定理、结论及公式，掌握理论的基本应用，做好课后习题，认真及时地完成在线和离线课程形成性作业，掌握基本的解题方法。对教学要求的重点内容和题型反复练习。

作业二

一、单项选择题（共 10 道试题，共 100 分。）

1.设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为(D)． A.8、2、8、2 B.8、1、6、1 C.6、2、6、2 D.无、2、无、2

满分：10 分

2.集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, yA}，则R的性质为（B）． A.自反的 B.对称的 C.传递且对称的 D.反自反且传递的满分：10 分

3.若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是(C)． A.{a，{a}}A B.{1，2}A C.{a}A D.A

满分：10 分

4.设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={, }，R2={, , }，R3={, }，则（A）不是从A到B的函数． A.R2 B.R3 C.R1和R2 D.R1和R3

满分：10 分

5.集合A={1, 2, 3, 4}上的关系R={|x=y且x, yA}，则R的性质为（B）． A.不是自反的 B.不是对称的 C.传递的 D.反自反

满分：10 分

6.如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（B）个． A.0 B.2 C.1 D.3

满分：10 分

7.设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为

． A.2 B.3 C.6 D.8

满分：10 分

8.设集合A = {1, 2, 3, 4, 5}上的偏序关系的哈斯图如右图所示，若A的子集B = {3, 4, 5}，则元素3为B的（B）． A.下界 B.最小上界 C.最大下界 D.最小元

满分：10 分

9.若集合A的元素个数为10，则其幂集的元素个数为（A）． A.1024 B.10 C.100 D.1

满分：10 分

10.设集合A = {1, a }，则P(A)=(D)． A.{{1}, {a}} B.{,{1}, {a}} C.{{1}, {a}, {1, a }} D.{,{1}, {a}, {1, a }}

离散数学课件作业篇2

关键词：任务指派,离散制造,评价,层次分析法 (AHP) ,作业人员

1 引言

随着现代制造业的深刻变革, 市场需求的变化, 生产任务常随客户需求变化进行调整, 新的生产任务被随机指派给作业人员的情况时有发生。在离散型制造行业 (如机械加工, 焊接结构生产等) , 这种情况尤为频繁和突出。本项研究之所以限定在离散制造行业, 其原因主要是在该类行业中, 作业人员参与劳动的密集程度较高, 人的因素对制造系统性影响较大, 作业人员自身的差异特点对生产指标影响的敏感性要比流程行业高得多[1]。因此, 研究离散制造行业作业人员任务指派, 具有重要的现实意义和较高的研究价值。

任务指派是一项复杂的决策过程, 简单地说, 是针对某一岗位或工种, 在某个时间段确定最佳作业人选的过程[2]。研究对象是在离散制造生产车间中, 对同一工种的多位作业人员, 他们均具有对同一作业操作的资格或能力, 确定选择哪位或哪几位来执行随机新增的生产任务。对该问题决策的实质是对作业人员相对应于其决策目标准则的综合评价过程。

目前, 在离散制造行业中, 对作业人员生产任务的指派主要依赖于生产一线管理人员的主观指定, 缺乏客观有效的分析, 决策往往具有主观臆断性或效率低下, 难以实现作业的最佳人员配置。不合理的任务指派是造成工期延误或质量问题的重要原因之一, 其直接后果会给企业造成较大的经济损失, 并严重影响了企业信誉及形象。面对复杂多变的市场环境, 合理有效地进行任务指派, 对于顺利完成生产任务起到至关重要的作用。

据我们所知, 目前国内外尚未见综合考虑离散车间作业人员多项准则及生产任务特点进行任务指派的专题研究或报道。本文利用层次分析法[3]处理定性定量问题的优势, 将其应用于作业人员任务指派问题。在确定评价作业人员的评价准则时, 为避免庞大繁杂的人的具体因素分析, 仅考虑与生产性能指标直接相关的作业人员人的性能作为分析评价准则。这样, 将人的因素引入了生产制造系统, 有利于得到更为合理的分析结果和更优的指派方案;同时, 还可避免指派决策失误造成的损失, 切实有效地提高企业经济效益及信誉。

2 作业人员评价

对生产任务指派, 首先要对具有从事该项作业资格和能力的作业人员进行评价。其过程一般为选择评价方法, 评价准则, 得出评价结果, 为任务指派提供决策支持。

2.1 层次分析法

层次分析法 (AHP) 是美国著名运筹学家, 匹兹堡大学教授T.L.Saaty于70年代中期提出的方法。它采取相对测度的形式, 具有适应环境变化的灵活性, 充分利用人的经验和判断, 能够对测度不一致性及其后果进行估计。测度的最终结果以方案相对重要性的权重表示[3]。这种方法的特点是在对复杂的决策问题的本质、影响因素及其内在关系等进行深入分析的基础上, 利用较少的定量信息使决策的思维过程数学化, 从而为多目标、多准则或无结构特性的复杂决策问题提供简便的决策方法。层次分析法较为成熟, 为避免赘述, 其详细过程及具体计算步骤作者可参考文献[4]等。

2.2 评价准则确定

不同的决策目标, 对选择作业人员的准则一般也应不同。即使在同一个评价目标下, 不同的企业、车间, 甚至同一车间同样作业人员在不同时期的评价准则都可能不同。本文作者通过对某一离散制造车间的现场调查并结合文献[5]和[6], 拟从作业人员工作效率、质量保证能力、人员成本 (分固定工, 临时工, 熟练工, 特种工等时的成本) 三个方面建立生产人员作业的评价准则。这些准则在评价人员作业能力方面虽具有一定的普遍性, 但仅为实际评价提供参考, 其目的旨在介绍该评价方法及应用。具体应用实施要根据具体情况及环境制定评价准则, 才可能得到客观有效的评价结果。生产人员作业的工作效率和质量保证能力来自于车间的近期历史统计数据, 衡量标准可以采用最能反映该项能力的指标, 如单位时间的工件量、合格品率等。其获取方式可从相关管理人员中取得, 或是在信息化程度高的制造企业中由系统自动生成的相应实时数据。

3 应用实例

今有一项生产任务, 设目标A为选择最佳作业人选。评价准则以B1表示生产效率;B2表示质量保证能力, B3表示人员成本。具有操作该项作业能力且现阶段仍能承担该任务负荷的作业人员为四人, 分别记为:C1, C2, C3, C4。由专家的调查结果得到相应判断矩阵及相应计算结果如表1～表4所示。

以上各表中的相关符号说明如下:λmax表示特征向量的最大值;C.I.表示一致性指标;C.R.表示一致性比率。

当一致性比率C.R.<0.1时, 不一致性将非常小, 所得到的计算结果是可以接受的, 否则需要对判断矩阵进行调整[3,4]。因此, 表1～表4中的计算结果均符合要求。

若用上标i表示第i层元素, 由表1得到第2层元素权重:

w (2) = (0.3458 0.5970 0.0572) T (1)

由表2～表4, 得到方案层元素权重矩阵U (3) :

$U^{(3)} = [\begin{matrix} 0.3253 & 0.5497 & 0.0846 \\ 0.1003 & 0.2715 & 0.1665 \\ 0.0468 & 0.0628 & 0.5509 \\ 0.5276 & 0.1160 & 0.1980 \end{matrix}] (2)$

方案层各元素对总目标A的合成权重向量按式 (3) 计算

w (3) =U (3) ·w (2) (3)

于是合成权重向量为:

w (3) = (0.4455 0.2063 0.0852 0.263) T (4)

由式 (4) 得到了方案层各元素相对于总目标A的相对权重, 相应得到这四位作业人员的评价结果。按其优先顺序排序为C1>C4>C2>C3。故针对总目标A, 最佳作业人选为C1, 即C1是满足同时综合考虑工作效率、质量保证能力及人员成本三个目标时的最合适人选;其次为作业人员C4和C2, 且C4略优于C2;最不合适作业人选为C3。

通过这个实例, 我们可以获得以下几点启示:

(1) 当被评价的作业人员有所调整时, 例如当被评价人员数量增减时, 只需对方案层的关系比较矩阵进行构造和计算, 其余层判断矩阵及计算结果无需改动。

(2) 当生产任务特点发生变化时, 例如在临时增加的任务中, 这些任务是对质量要求极高, 而对工期要求不是很紧时, 只需构建准则层的两两比较判断矩阵, 得到准则层对目标层的相应权值。即其余层判断矩阵不必改变, 则可获得在此情况下较为合理的决策。其它变化情况也是作类似的处理。对作业人员动态任务调度提供决策依据, 有利于快速响应市场需求变化。

(3) 上例中权重的确定还可通过专家的群组决策方法, 其详细方法及步骤见文献[4]。

(4) 该方法可以扩展到生产班组的情况, 即这时考察对象为作业班组。同样, 对这些班组要求对某一作业也均具有同样的生产资格或能力。因此, 增强了该方法的适用范围。

4 结论

针对目前离散制造行业任务指派存在的问题, 阐述了对作业人员进行任务指派研究的必要性、紧迫性及价值。根据离散制造行业的特点, 提出采用层次分析法综合考虑作业人员因素及生产任务特点来确定任务指派方案, 有效减少指派决策失误造成的损失, 切实有效地提高企业经济效益及信誉。提出了对其评价准则的选取应符合具体生产情况与环境的思想, 以便得到合理的指派结果。通过实例说明了该方法在任务指派活动中的具体实施过程。由此引出的几点启示, 并对车间作业人员动态任务调度提供决策依据, 提高快速响应市场需求变化的能力。

进一步的工作将使指派决策过程程序化, 加快决策速度, 并将采集数据实时更新, 有望实现辅助动态决策过程。对于影响工作效能可能的人的因素体系不断地归类、比较、总结, 为进一步分析评价结果中涉及的可能人的因素提供选择。

参考文献

[1].Buzacott J A.The impact of worker differences on pro-duction system output.International Journal of Production Eco-nomics[J].2002, (1)

[2].Golec A.and Kahya E.A fuzzy model for competency-based employee evaluation and selection[J].Computers&Industrial Engineering, 2007, (1)

[3].许树柏.层次分析法原理[M].天津:天津大学出版社, 1988

[4].吴祈宗, 侯福均, 朱心想.运筹学与最优化方法[M].北京:机械工业出版社, 2003

[5].Shikdar A A, Das B.The relationship between workersatisfaction and productivity in a repetitive industrial task[J].Applied Ergonomics, 2003, (6)

浅谈如何上好《离散数学》课篇3

【关键词】离散数学学生自主性教学方法

【中图分类号】G642.0【文献标识码】A【文章编号】1673-8209(2010)05-0-01

离散数学课程是计算机科学与技术系各专业的一门重要的基础课程,也是计算机科学基础理论的核心课程。本课程介绍计算机科学与技术系各专业所需要的离散数学基础知识,为进一步学习计算机科学的基本理论和方法、学好专业课奠定基础,内容包括数理逻辑、集合论、代数结构与布尔代数、图论和在计算机中的应用共五部分。该课程是培养学生抽象思维能力、逻辑推理能力、缜密概括能力以及分析和解决实际问题能力的主干课程,对学习其他诸多课程,具有重要的指导作用。离散数学教学内容具有知识点多、散、抽象等特点,加之许多学生不能认识到该课程的重要性,缺乏学习兴趣和学习主动性,不仅忽视该课程的学习,甚至害怕这门课程。因此,创新教学方法,提高学生自主学习的积极性,对提高学生的能力、提升教学质量和水平,具有重要的意义。作者在离散数学教学和实践中,积累了若干经验和做法,仅供大家参考。

1 引导学生提高对离散数学课程应用性的认识,激发学生学习的兴趣和爱好,增强汲取知识的自主性

离散数学课程是一门基础性课程,由于许多学生并不能认识到离散数学课程对后续诸多主干课程的指导性作用,看不到该课程的实际应用价值,加上该课程知识比较难而且抽象,很多学生对该课程缺乏学习兴趣和学习主动性,对该门课程只是应付,甚至根本不愿意去学习。

学习离散数学课程对学生今后的学习和工作,具有重要的作用,例如,对数据结构、操作系统、数据库、编译原理、软件工程等后续课程学习的指导作用;培养学生的抽象思维能力和缜密的逻辑推理能力,并为学生今后处理离散信息,提高专业理论水平,从事计算机的实际工作提供必备的数学工具;通过学习,可以掌握数理逻辑,集合论,代数结构和图论的基本概念和原理,并会运用离散数学的方法,分析和解决计算机理论和应用中的一些问题等。学习主动性是学生的力量之源,因此,引导学生充分认识学习离散数学课程的作用,能够激发学生学习的爱好和热情,提升学生学习的积极性和主动性,从而使学生学有成效。

2 认真备课,合理准备教学内容和安排教学环节,优化教学方式方法

备好课是教学取得预期效果的前提和基础,针对学生学习具体情况,合理准备教学内容和安排教学环节,使用恰当的教学方法,在教学中可以起到事半功倍的效果。

(1)合理地准备教学内容。根据课程教学大纲和离散数学课程定理定义比较多、知识比较抽象的特点以及学生的实际情况,准备深度和广度适合学生特点的教学内容。

(2)合理地讲解课程内容,重难点突出讲解,注意轻重缓急。对于离散数学中比较重要、比较抽象的概念和定理,如逻辑的推理理论、关系的性质、群、图等,认真分析,用多种方式和方法深入讲解,可以使用解析法、图示法、矩阵法举实例等多种方法讲解,例如对关系的对称性质的讲解中,可以使用矩阵法进行讲解,判断一个关系是否对称,只需观察它的关系矩阵是否对称即可,再如对关系的传递性质的讲解中,可以使用关系图进行讲解,判断一个关系是否传递,只需观察在关系图中,当x到y有一条路径时,x与y是否有关系即可。对于比较容易理解和掌握的内容,可以一笔带过。这样,学生对所学内容就会有重点地学习,主次分明,学生不仅可以对所学内容掌握透彻,更能熟练把握离散数学中分析问题和解决问题的思路、方式和方法。

(3)启发式教学和教师讲授相结合。很多人认为,大学教学课时紧,内容多,关键靠学生自主学习,所以,大学教学以教师的讲授为主,不需要通过提问、讨论等方式进行教学互动。笔者认为这是不全面的。如果教师不顾学生的理解情况,只顾在讲台上讲授知识,课堂氛围会很沉闷,很多同学不能专注于该门课程的学习,经常走神,教学很难达到预期的效果。因此,有针对性地提问和展开讨论,不仅能够培养学生的思考能力,更能调动学生学习的兴趣和积极性,从而使教学达到最佳效果。

然而,由于离散数学课程在教学难度、课堂教学时间等方面的原因,很多学校都出现师生、学生之间的交流较少,致使学生对该门课程缺乏兴趣,教学效果不佳。所以,教师有必要针对课程中的主要问题或疑难问题适时地提问或者让学生展开讨论,鼓励他们进行独立思考,各抒己见,引导他们逐步深入地对问题进行实质性地分析,必要时,教师对其进行引导,及时总结,使教学达到预期效果。

3 合理布置作业,认真批改作业,有针对性地安排习题课和课后答疑

为了强化学生能力的训练,培养学生的抽象思维能力、逻辑推理能力、实际问题的解决能力等,在保证作业数量的同时,更要提高布置作业的质量,增加典型简答题、讨论题、推理题、实际应用题等习题在作业中的分量,使学生在掌握各种基本知识和基本技能的同时,提高自身的综合能力。当然,布置作业是一回事,学生能否认真完成作业,是预期目标能否实现的关键所在,认真检查和批改作业,是督促学生学习的主要途径,也是教师了解学生理解和掌握所学课程情况的主渠道。必要时,教师可以批改一部分作业,其他作业让同学们之间互相检查和批改,不仅可以督促学生学习,更能让学生在批改其他同学作业时逐步认识到自身的缺陷和不足,以备今后更有针对性地学习。

教师在作业检查和批改过程中发现的主要问题和疑难以及学生提出的有代表性的问题,有必要安排习题课进行讲解,帮助学生对解决疑难,加深对所知识的理解。对于学生比较争论的问题,可以展开讨论,鼓励学生大胆发言,培养学生探索未知的精神和创造性解决实际问题的能力。

因此,上好离散数学课,关键是根据学生具体实际,有针对性地安排教学内容,合理使用教学方式方法,最大限度地激发学生的学习兴趣,充分发挥教师的主导作用和学生的主体作用,达到教与学和谐。

参考文献

[1] 屈婉玲,耿素云,张立昂.离散数学[M].北京:高等教育出版社.2008.

[2] 黄巍,金国祥.”离散数学”课程教学改革的探讨[J].中国电力教育,2009(8):82-83.

[3] 周小燕,胡丰华.对提高离散数学教学质量的探讨[J].浙江科技学院学报,2007,19(2):156-158.

[4] 龙浩,张佳佳.怎样教好《离散数学》课[J].贵阳学院学报,2007,2(1):53-57.

离散数学课程总结篇4

姓名：

学号：

班级：级计科系软件工程（）班

近年来，计算机科学与技术有了飞速发展，在生产与生活的各个领域都发挥着越来越重要的作用。离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程。

一、课程总结

本书的主要内容有数理逻辑、集合论、代数结构、组合数学、图论以及初等数论六部分，而我们主要学习的有第一部分数理逻辑、第二部分集合论以及第五部分图论，第三部分代数结构也学习了一部分。

第一部分：数理逻辑

数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。

1.在命题逻辑的基本概念中学习了命题的真值及真值表、命题与联结词、命题及其分类、联结词与复合命题、命题公式及其赋值。2.在命题逻辑的等值演算中主要学习了等值式与基本的等值式模式、等值演算与置换规则、析取范式与合取范式，极大值和极小值，主析取范式与主合取范式、联结词完备集。

3.在命题逻辑的推理理论中主要学习了推理的正确与错误、推理的形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P中构造证明：直接证明法、附加前提证明法、归谬法。

4.在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、谓词、量词、一阶逻辑公式及其解释、一阶语言、合式公式及合式公式的解释、永真式、矛盾式、可满足式。

5.在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统N及其推理规则。

第二部分：集合论

在集合论中，主要学习了集合代数、二元关系和函数。1.在集合代数中，学习了集合的基本概念：属于、包含、空集、元集、幂集、全集；集合的基本运算：并、交、补相对、对称差等；集合恒等式：集合运算的主要算律、恒等式的证明方法。2.在二元关系中学习了有序对与笛卡儿积、二元关系的定义与表示法、关系的运算、关系的性质、关系的闭包、等价关系与划分、偏序关系。

第三部分：代数结构

在代数结构中，主要学习了代数系统、群与环。

1、在代数系统中学习了二元运算及其性质：一元和二元运算定义及其实例、二元运算的主要性质、代数系统：代数系统定义及其实例、子代数、积代数。

2、在群与环中学习了群的定义与性质：半群、独异点、群、阶。

第五部分：图论

在图论中主要学习了图的基本概念、欧拉图与哈密顿图、树。1.在图的基本概念中学习了图、通路与回路、图的连通性，图的矩阵表示、图的运算。

2.在欧拉图与哈密顿图中学习了欧拉图、哈密顿图。3.在树中学习了无向树及其性质、生成树、根数及其应用。

二、对课程的建议

离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念真正的含义。

另外，离散这门课程我觉得每一个部分之间并没有什么太大的联系，可以说都是独立的，所以我们可以对内容侧重讲解，虽然说这对以后的数据结构有一定的影响。所以更应该对一些有用的内容进行选择性的部分详细讲解。

更重要的一点就是加强实践，因为本书多是概念，我们不能仅仅只是纸上谈兵，例如在数理逻辑中，我们可能对一些命题逻辑公式熟练于心，但是解决实际问题时可能有各种问题。因此我们要加强训练，多做一些证明题，这样才能把理念用于实践之中。后面的图论就更不用说了，只有结合实际的题目才能够掌握和理解。

三、对老师的建议

离散数学证明题篇5

证明设a,b均是链A的元素，因为链中任意两个元素均可比较，即有a≤b或a≤b，如果a≤b，则a,b的最大下界是a,最小上界是b，如果b≤a，则a,b的最大下界是b,最小上界是a，故链一定是格,下面证明分配律成立即可,对A中任意元素a,b,c分下面两种情况讨论:

⑴b≤a或c≤a

⑵a≤b且a≤c

如果是第⑴种情况,则a∪(b∩c)=a=(a∪b)∩(a∪c)

如果是第⑵种情况,则a∪(b∩c)=b∩c=(a∪b)∩(a∪c)

无论那种情况分配律均成立,故A是分配格.一.线性插值(一次插值)

已知函数f(x)在区间的端点上的函数值yk=f(xk),yk+1=f(xk+1),求一个一次函数y=p1(x)使得yk=f(xk),yk+1=f(xk+1),其几何意义是已知平面上两点(xk,yk),(xk+1,yk+1),求一条直线过该已知两点。

1.插值函数和插值基函数

由直线的点斜式公式可知：

把此式按照yk和yk+1写成两项:

记

并称它们为一次插值基函数。该基函数的特点如下表：

从而

p1(x)=yklk(x)+yk+1lk+1(x)

此形式称之为拉格朗日型插值多项式。其中,插值基函数与yk、yk+1无关，而由插值结点xk、xk+1所决定。一次插值多项式是插值基函数的线性组合,相应的组合系数是该点的函数值yk、yk+1.例1:已知lg10=1,lg20=1.3010,利用插值一次多项式求lg12的近似值。

解:f(x)=lgx,f(10)=1,f(20)=1.3010,设

x0=10,x1=20,y0=1,y1=1.3010

则插值基函数为：

于是,拉格朗日型一次插值多项式为:

故:

即lg12由lg10和lg20两个值的线性插值得到,且具有两位有效数字(精确值lg12=1.0792).二.二次插值多项式

已知函数y=f(x)在点xk-1,xk,xk+1上的函数值yk-1=f(xk-1),yk=f(xk),yk+1=f(xk+1),求一个次数不超过二次的多项式p2(x),使其满足,p2(xk-1)=yk-1,p2(xk)=yk,p2(xk+1)=yk+1.其几何意义为:已知平面上的三个点

(xk-1,yk-1),(xk,yk),(xk+1,yk+1),求一个二次抛物线,使得该抛物线经过这三点。

1.插值基本多项式

有三个插值结点xk-1,xk,xk+1构造三个插值基本多项式，要求满足：

(1)基本多项式为二次多项式;(2)它们的函数值满足下表：

因为lk-1(xk)=0,lk-1(xk+1)=0,故有因子(x-xk)(x-xk+1),而其已经是一个二次多项式,仅相差一个常数倍,可设

lk-1(x)=a(x-xk)(x-xk+1),又因为

lk-1(xk-1)=1==>a(xk-1-xk)(xk-1-xk+1)=

1得

从而

同理得

基本二次多项式见右上图(点击按钮“显示Li”)。

2.拉格朗日型二次插值多项式

由前述,拉格朗日型二次插值多项式:

p2(x)=yk-1lk-1(x)+yklk(x)+yk+1lk+1(x),p2(x)

是三个二次插值多项式的线性组合,因而其是次数不超过二次的多项式,且满足:

p2(xi)=yi,(i=k-1,k,k+1)。

例2已知：

xi101520

yi=lgxi11.17611.3010

利用此三值的二次插值多项式求lg12的近似值。

解：设x0=10,x1=15,x2=20,则:

故:

所以

7利用三个点进行抛物插值得到lg12的值,与精确值lg12=1.0792相比,具有3位有效数字,精度提高了。

三、拉格朗日型n次插值多项式

已知函数y=f(x)在n+1个不同的点x0,x1,…,x2上的函数值分别为

y0,y1,…,yn,求一个次数不超过n的多项式pn(x),使其满足:

pn(xi)=yi,(i=0,1,…,n),即n+1个不同的点可以唯一决定一个n次多项式。

1.插值基函数

过n+1个不同的点分别决定n+1个n次插值基函数

l0(x),l1(x),…,ln(X)

每个插值基本多项式li(x)满足：

(1)li(x)是n次多项式;

(2)li(xi)=1,而在其它n个li(xk)=0,(k≠i)。

由于li(xk)=0,(k≠i),故有因子:

(x-x0)…(x-xi-1)(x-xi+1)…(x-xn)

因其已经是n次多项式，故而仅相差一个常数因子。令:

li(x)=a(x-x0)…(x-xi-1)(x-xi+1)…(x-xn)

由li(xi)=1,可以定出a,进而得到：

2.n次拉格朗日型插值多项式pn(x)

pn(x)是n+1个n次插值基本多项式l0(x),l1(x),…,ln(X)的线性组合,相应的组合系数是y0,y1,…,yn。即:

pn(x)=y0l0(x)+y1l1(x)+…+ynln(x),从而pn(x)是一个次数不超过n的多项式,且满足

pn(xi)=yi,(i=0,1,2,…,n).例3求过点(2,0),(4,3),(6,5),(8,4),(10,1)的拉格朗日型插值多项式。

解用4次插值多项式对5个点插值。

所以

四、拉格朗日插值多项式的截断误差

我们在上用多项式pn(x)来近似代替函数f(x),其截断误差记作

Rn(x)=f(x)-pn(x)

当x在插值结点xi上时Rn(xi)=f(xi)-pn(xi)=0,下面来估计截断误差：

定理1：设函数y=f(x)的n阶导数y(n)=f(n)(x)在上连续，y(n+1)=f(n+1)(x)

在(a,b)上存在;插值结点为:

a≤x0

pn(x)是n次拉格朗日插值多项式;则对任意x∈有：

其中ξ∈(a,b),ξ依赖于x：ωn+1(x)=(x-x0)(x-x1)…(x-xn)

证明：由插值多项式的要求：

Rn(xi)=f(xi)-pn(xi)=0，(i=0,1,2,…,n);

设

Rn(x)=K(x)(x-x0)(x-x1)…(x-xn)=K(x)ωn+1(x)

其中K(x)是待定系数;固定x∈且x≠xk，k=0,1,2,…,n;作函数

H(t)=f(t)-pn(t)-K(x)(t-x0)(t-x1)…(t-xn)

则H(xk)=0，(k=0,1,2,…,n),且H(x)=f(x)-pn(x)-Rn(x)=0,所以，H(t)在上有n+2个零点，反复使用罗尔中值定理:存在ξ∈(a,b),使;因pn(x)是n次多项式，故p(n+1)(ξ)=0,而

ωn+1(t)=(t-x0)(t-x1)…(t-xn)

是首项系数为1的n+1次多项式，故有

于是

H(n+1)(ξ)=f(n+1)(ξ)-(n+1)!K(x)

得：

所以

设,则：

易知，线性插值的截断误差为:

二次插值的截断误差为:

下面来分析前面两个例子(例1，例2)中计算lg12的截断误差：

在例1中，用lg10和lg20计算lg12,p1(12)=1.0602,lg12=1.0792

e=|1.0792-1.0602|=0.0190;

离散数学论文篇6

姓名：王文军班级：数学与应用数学（2）班学号：092014020049

摘要：离散数学是研究散量的结构及其相互关系的数学学科，是现代数学的重要分支，通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为以后续课创造条件而且可以提高抽象思维和逻辑推理能力，为将来参加与创新性的研究和开发工作打下坚实基础。离散从字面上理解好像是一门很散的学科，但我觉得离散字面散而其内神不散。

正文：在中学我们学习了一些简单逻辑，那些都是一些与生活有关或是学习中一些常识就可判断命题真假的命题。这些简单逻辑对学生的思维逻辑推理能力有一定的训练作用，但中学中的简单逻辑没有严格的证明和公式的推导。一些问题都是凭借日常生活经验或学习中的一些常识就能把命题的正确性作出判断。数理逻辑是以散量为主要载体，通过一系列逻辑连接词来演绎命题并用一定公式判断命题的正确性。数理逻辑对公式有严格的证明，并把命题符号化，使得推理更有序，更可靠。数理逻辑是简单逻辑的提高和精神的升华。数理逻辑提出简单逻辑并未有的散量及一系列公式。数理逻辑为解决简单逻辑的解法提出多样化，为简单逻辑提供更严谨有效的解题途径。

数理逻辑是数学的一个分支，也是逻辑学的分支。是用数学方法研究逻辑式形式逻辑的学科。其研究对象是对证明和计算这两个直观慨念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。数理逻辑是离散数学的主要组成部分，也是现代科学理论的重要组成部分。现代的电子计算机大多是以散量为基数以数理逻辑的方法而运行的，数理逻辑对计算机技术的发展起到举足轻重的作用，不仅如此，在日常生活中人们学习数理逻辑会对人们在生活中分析一些事物形成独特见解。数理逻辑可以提高抽象思维和逻辑推理能力，为将来参与创新性的研究和开发工作打下结实基础。

一阶逻辑等值演算与推理，是数理逻辑的重要组成部分，在一阶逻辑中引入了个体词、谓词和量词的一阶逻辑命题符号化的三个基本要素。这在数理逻辑前几章的学习中都是未提到的，然而有了这些基本要素就把数理逻辑所研究的内容加以拓宽，思维的要求也有所提高。一些逻辑等值演算与推理也大大的增加了数理逻辑的推理方式，为数理逻辑在科学理论中的应用添上了浓墨重彩的一笔。对于一阶逻辑等值演算是数理逻辑前几章的延伸，也是前几章的提高。一阶逻辑为以后续课打下了各方面的条件，使得数理逻辑更加完美。

图论是以图为基本元素，而图的定义是：人们常用点表示事物，用点与点之间是否有某种关系，这样构成的图形就是图论中的图。从这种定义可把数理逻辑的每一个章节的推理公式分为不同的点，而每一章就相当于图论中的图。数理逻辑的各章间的关系就是图与图之间的关系，形成图论的基本要素。从点与点的紧密联系，图与图之间的各项关系，可以看出离散数学是一门严谨的学科，虽然离散字面散而其内神不散。

参考文献：屈婉玲、耿素云、张立昂编《离散数学》。

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

合理调整、安排教学内容

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

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

采用形式多样的教学方法

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

1. 认真重视课堂教学。

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

2. 讲解速度快慢得当。

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

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

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

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

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

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

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

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

6. 适时小结。

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

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

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

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

合理运用多媒体教学手段

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

充分利用网络教学手段

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

离散数学课件作业篇8

关键词：离散数学启发式教学多媒体教学

离散数学是计算机专业一门重要基础课,搞好本课程的教学,不但能为学生学好后续课程奠定坚实的数学理论基础,而且有利于培养学生的计算机数学思维,并且在进一步的学习和工作中适应本学科专业的发展。

由于離散数学内容多，抽象难懂，逻辑性较强，学习它需要有一定的抽象思维能力、演绎推理能力和归纳总结能力。但是，高职学生抽象思维水平不高,认知结构具有不稳定性,对离散数学这种内容的抽象性和逻辑推理中的形式化证明缺乏必要的思维和心理准备, 这些问题导致学生学习兴趣不足，不会学,导致学不会,因而也就不愿意学。怎样提高高职计算机专业《离散数学》课程的教学质量已经成为我们迫切需要解决的问题。为协调好教与学的双边关系，使学生对这门课的学习发生兴趣，从而调动学生的学习积极性，使其由被动接受变为主动参与，就要在教学内容、教学方法、教学手段等方面进行相应的改革。

一、精选教学内容，突出其应用性

1．1 精心安排讲授内容，以“够用”为主

离散数学课程不仅内容多，而且繁又难，针对高职学生这一特定的对象和学时的限制，我们必须精选讲授内容，不能面面俱到、不分主次，而要突出重点，以学生“够用”为准，选择内容时应考虑到它是否能覆盖计算机科学所需的理论基础，强化基本概念的描述，注重基本方法的讲解。如对于离散数学中的纵多的定理证明，我们作了有针对性的、精心的处理；对于一些有利于加深对基本概念的理解，或者可以提高解决问题能力的定理的证明，都给予了详细的介绍；而另一些定理则仅给出一些描述性的说明，省略了完整的证明，其目的是突出要点，突出理论在实际中的应用。

1．2以实用性培养学生的学习兴趣和主动性

离散数学知识在计算机专业中的应用或“分散”或“隐含”,无处不在,但作为基础课程的离散数学教学在内容与形式上缺乏对本专业的直接针对性。在教学过程中，应注重让学生了解所学离散数学知识与相关学科之间的联系，要有意识地引导学生运用所学理论去联系实际问题，提高离散数学课对专业课的针对性和适用性，使学生学了以后感到“有用”。比如，在讲授图论中通路与回路概念时，给出它们在研究操作系统是否存在死锁，程序设计语言中一个过程是否递归等方面的应用。在讲授平面图时，给出它们在印刷电路板、集成电路等方面的应用。这样使学生感受《离散数学》的实用价值，提高学生学习的积极性、主动性

二、改革方法，激发学生学习兴趣，提高教学质量

离散数学基本概念、定理、方法特别多，单纯的讲授教学，枯燥乏味，很难激发学生的学习兴趣。我们采用了多种教学方法,以提高学生学习的积极性、主动性，提高教学质量。具体如下:

2.1 注重理论的理解、注重学习的过程

离散数学课程中有很多定义、定理、规则,对学生而言,几乎每一节课堂上均要接受数十个新的术语或定理,这显然是有很大的难度,而且很容易产生枯燥甚至畏难情绪。因此,新课伊始,我们就告诉学生,不用记忆,只需要理解,注重学习过程。我们认为,宁愿少讲授部分内容,也要学生对于讲授的理论知识能够真正理解掌握。在整体上分析之后,对部分知识删节,不用在课堂上讲授,而是作为学生的课外作业去完成。在课堂讲授中,我们注重对于问题的完整理解过程,而不是只告诉学生结论,也正因如此,尽管常常在一个课时中,可能仅仅完成一个问题的讲授而显得课时紧张,但我们认为这是完全值得的,事实上,也取得了好的效果。

2.2 抽象与具体相结合

离散数学中,有许多定义、定理、规则,教科书上对其描述很精练,学生常常感到很抽象, 如果直接给出定义，学生往往感到很难理解，所以在讲解这些概念时，先给出具体例子，再抽象出基本概念，使得学生对这些概念有更深刻的理解，加深学生对概念的印象。例如“代数系统”就是一个抽象的概念，在讲解时，笔者先给出学生比较熟悉的非空集(如整数集I)，并结合其上的运算(如加法运算)，再得出运算在非空集上封闭，逐步引出代数系统的定义，这样学生就不感到抽象、难理解了。

2.3采用启发式教学方法,联系高等数学知识，讲清离散数学中的难点

虽然离散数学的理论较为抽象，方法也较难，但它归根到底总是一门数学学科，它和大学生所学的高等数学中的一些知识总有一定的联系，因此，我们牢牢地抓住这个特点，采用启发式教学方法，促使学生回忆以往学过的知识，再和现在所学的联系起来，从而加深学生对基本概念的理解和掌握。例如在学习命题和谓词的时候，部分学生对命题与谓词的关系，特别是加上量词的谓词的理解不深刻。我们在讲解的时候启发学生回忆以前学习过的常数和函数及定积分的概念，然后指出，谓词就是一个命题函数，命题在这里可借助于常数的概念来理解，而带量词的谓词可借助于函数加上定积分后变成什么来理解，通过这样的启发，学生就很容易知识命题是谓词的特例，谓词是命题的推广的关系。当然，类似的例子在离散数学的教学中还有很多。

2.4上好习题课，调动学生积极性

习题讨论课不仅是帮助学生巩固所学知识的一种重要方式，还是属于提高性的教学环节。每章学完后，安排一次习题讨论课,所选习题要具有典型性、实际应用性等特点，让学生自己动脑、动手、动口，学会独立分析问题和解决问题，检查自己对知识的理解及掌握程度。通过让学生运用所学知识解决一些实际问题，可以训练其思维能力及分析问题、解决问题的能力, 激发学生学习离散数学的积极性。例如,在讲完根树这一章后，可安排这样一次习题讨论课。首先,让学生回忆课堂上讲过的有序二元树的树叶集合可生成前缀码的知识,再让学生分析怎样把一个前缀码用有序二元树表达出来,最后让学生讨论如何利用一棵最优树产生一个最佳前缀码，使得在传送信息时，既准确无误，又能节省二进制位。这样通过课堂讨论，既让学生巩固和完善所学的知识内容，又了解离散数学在计算机中的重要作用，同时也训练学生思维能力及分析问题、解决问题的能力，激发了学生学习离散数学的积极性。

三、改变教学手段，充分利用多媒体教学

离散数学课的一个特点是定义、定理、性质特别多，利用多媒体教学，教师不必再象过去那样一黑板、一黑板地去抄写，这为缩短理论授课时间，增强应用内容提供了保证。利用多媒体教学，有利于新旧知识的联结。在讲授某一新知识点时，常常要涉及到前面的内容，比如，在进行数理逻辑的推理时，就要用到前面的一些推理定律，而通过展示幻灯片，重新唤醒学生对这些定律的认识后，就会较容易使学生从已有的知识顺利过渡到新的知识点上来，轻松自然地获取新知识。

参考文献：

[1]贾振华. 《离散数学》[M]．北京.水利水电出版社，2004,2.

离散数学习题及答案篇9

一、（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

(1)若A去，则C和D中要去1个人；

(2)B和C不能都去；

(3)若C去，则D留下。

解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T

故有三种派法：B∧D，A∧C，A∧D。

二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。

解：论域：所有人的集合。S(x)：x是专家；W(x)：x是工人；Y(x)：x是青年人；则推理化形式为：

x(S(x)∧W(x))，xY(x)x(S(x)∧Y(x))

下面给出证明：

(1)xY(x)P

(2)Y(c)T(1)，ES

(3)x(S(x)∧W(x))P

(4)S(c)∧W(c)T(3)，US

(5)S(c)T(4)，I

(6)S(c)∧Y(c)T(2)(5)，I

(7)x(S(x)∧Y(x))T(6)，EG

三、（10分）设A、B和C是三个集合，则AB(BA)。

证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA)

x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB)

(x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A))

(BA)。

四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。

解r(R)＝R∪IA＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>}

s(R)＝R∪R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}

R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}

R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R

t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，i14232－

15>}。

五、（10分）R是非空集合A上的二元关系，若R是对称的，则r(R)和t(R)是对称的。

证明对任意的x、y∈A，若xr(R)y，则由r(R)＝R∪IA得，xRy或xIAy。因R与IA对称，所以有yRx或yIAx，于是yr(R)x。所以r(R)是对称的。

下证对任意正整数n，R对称。

因R对称，则有xRyz(xRz∧zRy)z(zRx∧yRz)yRx，所以R对称。若Rn对称，则xRn1yz(xRnz∧zRy)z(zRnx∧yRz)yRn1x，所以Rn1对称。因此，对任意正整数n，Rn对称。对任意的x、y∈A，若xt(R)y，则存在m使得xRy，于是有yRx，即有yt(R)x。因此，t(R)是对称的。

六、（10分）若f：A→B是双射，则f：B→A是双射。

证明因为f：A→B是双射，则f是B到A的函数。下证f是双射。

对任意x∈A，必存在y∈B使f(x)＝y，从而f(y)＝x，所以f是满射。

对任意的y1、y2∈B，若f(y1)＝f(y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B是函数，则y1＝y2。所以f是单射。

综上可得，f：B→A是双射。

七、（10分）设是一个半群，如果S是有限集，则必存在a∈S，使得a*a＝a。

证明因为是一个半群，对任意的b∈S，由*的封闭性可知，b＝b*b∈S，b＝b*b∈S，…，bn∈S，…。

因为S是有限集，所以必存在j＞i，使得bi＝bj。令p＝j－i，则bj＝bp*bj。所以对q≥i，有bq＝bp*bq。

因为p≥1，所以总可找到k≥1，使得kp≥i。对于bkp∈S，有bkp＝bp*bkp＝bp*(bp*bkp)＝…＝232－1－1－1－1－1－1－1－1－1mm222nbkp*bkp。

令a＝bkp，则a∈S且a*a＝a。

八、（20分）（1）若G是连通的平面图，且G的每个面的次数至少为l(l≥3)，则G的边数m与结点数n有如下关系：

m≤

rl(n－2)。l2l证明设G有r个面，则2m＝

2)。d(f)≥lr。由欧拉公式得，n－m＋r＝2。于是，m≤l2(n－ii

1（2）设平面图G＝是自对偶图，则| E|＝2(|V|－1)。

证明设G＝是连通平面图G＝的对偶图，则G G，于是|F|＝|V*|＝|V|，将其代入欧拉公式|V|－|E|＋|F|＝2得，|E|＝2(|V|－1)。**

离散数学考试试题（B卷及答案）

一、（10分）证明(P∨Q)∧(PR)∧(QS)S∨R

证明因为S∨RRS，所以，即要证(P∨Q)∧(PR)∧(QS)RS。

(1)R附加前提

(2)PRP

(3)PT(1)(2)，I

(4)P∨QP

(5)QT(3)(4)，I

(6)QSP

(7)ST(5)(6)，I

(8)RSCP

(9)S∨RT(8)，E

二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。

设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))x(P(x)∧B(x))。

(1)x(P(x)Q(x))P

(2)x(P(x)∨Q(x))T(1)，E

(3)x(P(x)∧Q(x))T(2)，E

(4)P(a)∧Q(a)T(3)，ES

(5)P(a)T(4)，I

(6)Q(a)T(4)，I

(7)x(P(x)(A(x)∨B(x))P

(8)P(a)(A(a)∨B(a))T(7)，US

(9)A(a)∨B(a)T(8)(5)，I

(10)x(A(x)Q(x))P

(11)A(a)Q(a)T(10)，US

(12)A(a)T(11)(6)，I

(13)B(a)T(12)(9)，I

(14)P(a)∧B(a)T(5)(13)，I

(15)x(P(x)∧B(x))T(14)，EG

三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。

解设A、B、C分别表示会打排球、网球和篮球的学生集合。则：

|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。

因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩

B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|ABC|＝25－20＝5。故，不会打这三种球的共5人。

四、（10分）设A1、A2和A3是全集U的子集，则形如Ai(Ai为Ai或Ai)的集合称为由A1、A2和

i1

3A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。

证明小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。

对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai为包含元素a的Ai或Ai，则a∈Ai，i13即有a∈si，于是Usi。又显然有siU，所以U＝si。

i1i1i1i1rrrr

任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝。综上可知，{s1，s2，…，sr}是U的一个划分。

五、（15分）设R是A上的二元关系，则：R是传递的R*RR。

证明(5)若R是传递的，则∈R*Rz(xRz∧zSy)xRc∧cSy，由R是传递的得xRy，即有∈R，所以R*RR。

反之，若R*RR，则对任意的x、y、z∈A，如果xRz且zRy，则∈R*R，于是有∈R，即有xRy，所以R是传递的。

六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。证明对G的边数m作归纳法。

当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。

假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。

设e是G的一条边，从G中删去e后得到的图记为G，并设其结点数、边数和面数分别为n、m和r。对e分为下列情况来讨论：

若e为割边，则G有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n＝n，m1＋m2＝m＝m－1，r1＋r2＝r＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。

若e不为割边，则n＝n，m＝m－1，r＝r－1，由归纳假设有n－m＋r＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。

由数学归纳法知，结论成立。

七、（10分）设函数g：A→B，f：B→C，则：

(1)fg是A到C的函数；

(2)对任意的x∈A，有fg(x)＝f(g(x))。

证明(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使∈g。对于y∈B，因f：B→C是函数，则存在z∈C使∈f。根据复合关系的定义，由∈g和∈f得∈g*f，即∈fg。所以Dfg＝A。

对任意的x∈A，若存在y1、y2∈C，使得、∈fg＝g*f，则存在t1使得∈g且∈f，存在t2使得∈g且∈f。因为g：A→B是函数，则t1＝t2。又因f：B→C是函数，则y1＝y2。所以A中的每个元素对应C中惟一的元素。

综上可知，fg是A到C的函数。

(2)对任意的x∈A，由g：A→B是函数，有∈g且g(x)∈B，又由f：B→C是函数，得∈f，于是∈g*f＝fg。又因fg是A到C的函数，则可写为fg(x)＝f(g(x))。

八、（15分）设是的子群，定义R＝{|a、b∈G且a1*b∈H}，则R是G中的－

一个等价关系，且[a]R＝aH。

证明对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。－－