离散数学课程设计论文（精选8篇）
姓名：
学号：
班级： 级计科系软件工程（）班
近年来，计算机科学与技术有了飞速发展，在生产与生活的各个领域都发挥着越来越重要的作用。离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程。
一、课程总结
本书的主要内容有数理逻辑、集合论、代数结构、组合数学、图论以及初等数论六部分，而我们主要学习的有第一部分数理逻辑、第二部分集合论以及第五部分图论，第三部分代数结构也学习了一部分。
第一部分：数理逻辑
数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。
1.在命题逻辑的基本概念中学习了命题的真值及真值表、命题与联结词、命题及其分类、联结词与复合命题、命题公式及其赋值。2.在命题逻辑的等值演算中主要学习了等值式与基本的等值式模式、等值演算与置换规则、析取范式与合取范式，极大值和极小值，主析取范式与主合取范式、联结词完备集。
3.在命题逻辑的推理理论中主要学习了推理的正确与错误、推理的形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P中构造证明：直接证明法、附加前提证明法、归谬法。
4.在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、谓词、量词、一阶逻辑公式及其解释、一阶语言、合式公式及合式公式的解释、永真式、矛盾式、可满足式。
5.在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统N及其推理规则。
第二部分：集合论
在集合论中，主要学习了集合代数、二元关系和函数。1.在集合代数中，学习了集合的基本概念：属于、包含、空集、元集、幂集、全集；集合的基本运算：并、交、补相对、对称差等；集合恒等式：集合运算的主要算律、恒等式的证明方法。2.在二元关系中学习了有序对与笛卡儿积、二元关系的定义与表示法、关系的运算、关系的性质、关系的闭包、等价关系与划分、偏序关系。
第三部分：代数结构
在代数结构中，主要学习了代数系统、群与环。
1、在代数系统中学习了二元运算及其性质：一元和二元运算定义及其实例、二元运算的主要性质、代数系统：代数系统定义及其实例、子代数、积代数。
2、在群与环中学习了群的定义与性质：半群、独异点、群、阶。
第五部分：图论
在图论中主要学习了图的基本概念、欧拉图与哈密顿图、树。1.在图的基本概念中学习了图、通路与回路、图的连通性，图的矩阵表示、图的运算。
2.在欧拉图与哈密顿图中学习了欧拉图、哈密顿图。3.在树中学习了无向树及其性质、生成树、根数及其应用。
二、对课程的建议
离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念真正的含义。
另外，离散这门课程我觉得每一个部分之间并没有什么太大的联系，可以说都是独立的，所以我们可以对内容侧重讲解，虽然说这对以后的数据结构有一定的影响。所以更应该对一些有用的内容进行选择性的部分详细讲解。
更重要的一点就是加强实践，因为本书多是概念，我们不能仅仅只是纸上谈兵，例如在数理逻辑中，我们可能对一些命题逻辑公式熟练于心，但是解决实际问题时可能有各种问题。因此我们要加强训练，多做一些证明题，这样才能把理念用于实践之中。后面的图论就更不用说了，只有结合实际的题目才能够掌握和理解。
三、对老师的建议
1 精品课程网站设计
1.1 MVC架构
《离散数学》精品课程网站是基于B/S即浏览器/服务器模式,采用PHP嵌入式语言、MySQL数据库和Dreamweaver设计开发。PHP和MySQL是现如今较为流行的构建动态网页的开放源代码技术,用其开发的系统具有稳定性高和可移植性强等优点。在B/S模式下,用户工作界面是通过WWW浏览器来实现,极少部分事务逻辑在前端(Browser)实现,但是主要事务逻辑在服务器端(Server)实现,形成模型(Model)-视图(View)-控制器(Controller)即MVC三层架构。采用MVC架构,使后续对程序的修改和扩展简化,并且提高代码重用率,提高程序的可维护性,更加有利于团队开发。
1.2 总体框架
本精品课程网站导航栏中有七个部分,包括师资队伍、课程描述、教学成果、网络课程、教学资源、课程评价、师生交流等栏目,提供了完备的网上教学资源。网站层次结构如图1所示。
1.3 数据库设计
系统涉及的数据表有:学生注册表、教师注册表、分类表、论坛主题表、论坛帖子表、用户组表、用户组权限表、论坛头像表、试题类别表、选择题表、问答题表、选择题得分表、问答题得分表、投票系统统计表、文章发布表等。各表详细说明如表1所示。
2 系统模块
2.1 用户模块
2.1.1 用户注册
用户注册就是把所要提交表单中各个文本域的值插入到数据库的学生注册表中。学生填写E-Mail主要是为找回密码而设的关键凭据,设置验证码的目的是为了防止批量注册无用的账户而施压于数据库。
2.1.2 用户登录
系统对用户设置了浏览权限,除了一些基本页面,要想浏览更多的内容必须注册登录后才能访问。
2.1.3 学生管理
学生管理的具体功能有:
(1)个人信息:此页面显示当前登录用户的全部信息。实现方式是在此页面新建一个记录集,此记录集是根据登录用户在浏览器中保存的学生姓名Session值从学生注册表中筛选出来的。
(2)修改个人资料:此页面与个人信息页面基本相同,其不同点在于将记录集中的各个字段绑定到一个可以提交的表单中的相应文本域,在这些文本域中用户可以修改自己的资料,修改完成后点击“更新”即可将数据库中用户注册表的相应字段值改变。
2.1.4 教师管理
教师在系统中拥有最高的权限,当教师登录后可以插入、修改、删除数据库中的记录,能访问更多的内容与功能。具体功能为:
(1)增加学生信息:当教师登录后可以添加学生账号,实现过程与用户注册相同。
(2)修改学生信息:如果学生注册表中的信息与学生真实信息不相吻合,教师能对其进行修改。
(3)教师账号信息:当管理员登录后可以在本页面增加教师账号。
2.2 在线讨论
在线讨论为学生与学生、学生与教师之间提供了一个交流平台,大家可以在此平台自由发言、相互交流等。学生遇到疑难问题可以发布在网上,专业教师会给予解答,教师可以在此平台上发表学习方法供学生参考。
2.3 在线考试
为了检测和提高学生的学习能力,系统提供了在线考试功能,大量试题可供学生作答。在线考试相比于传统的考试形式更加新颖,同时也能大大缩短考试周期,减少教师批改试卷的负担。
在线考试是基于B/S的新型考试模式,服务器对数据库中所记录的试题进行管理,客户端通过浏览器登录进入在线考试。与传统的基于C/S的考试模式相比,更稳定、更适合于在互联网上运行。同时在线考试是基于数据库中的试题操作的,客户端可以自由选择作答的试卷类型,服务器对客户端提交的试卷进行自动评卷,缩短了考试周期,节省资源。
2.4 文章发布
为了学生能够及时了解到本门课程的一些最新动态,本站设计了文章发布功能,另外,教师也可以在此发布一些课程公告,例如上课时间变动、课程学术报告时间等内容。主要包括:
(1)文章列表:文章列表是在其上显示出文章发布表中的所有记录,以供用户阅读。
(2)文章查看:无论是首页文章还是文章列表中的文章标题,都必须添加一个带参数的链接,该链接指向详细的文章查看页面。文章查看页面需要根据链接传递过来的参数建立记录集,根据插入记录集中的数据实现文章查看。
2.5 在线投票
网站投票系统可以让教师方便地了解到学生对于某件事的意见和看法。此功能的建设对网站未来的发展起到了积极、重大的作用。实现的功能主要有:
(1)投票处理:用户在首页的在线投票版块点击投票之后,自动跳转入该页面,对投票页面传递过来的参数进行更新处理,完成后跳转到投票结果查看页面。
(2)投票结果显示:本页是通过统计图来显示投票结果的。建立关于投票系统表的记录集后,将记录集中各字段的百分值绑定为图形的宽度,就可以实现投票结果图形的动态显示。
3 关键技术实现
3.1 页面设计技术
系统所有页面的大体布局采用DIV实现,所有页面的布局位置、颜色、字体等属性则采用CSS样式控制。由于网站涉及页面较多,而很多页面除了主要内容版块之外其他都完全相同,因此采用模板来实现,并将模板完全独立分开。模板采用PHP项目中使用最广泛的Smarty模板引擎。系统支持在线添加模板、修改模板、删除模板、主题变换。此方案的优点在于:缩减代码所占空间、易于更新页面、加快网页制作速度。
3.2 无限分类
栏目支持无限分类,可设置栏目简介、缩略、跳转地址、浏览权限;可自定义该栏目下文档路径;一篇文档可发布到多个栏目。部分实现代码如下:
3.3 权限管理
B/S系统中的权限比C/S中的更显的重要,C/S系统因为具有特殊的客户端,所以访问用户的权限检测可以通过客户端实现或通过客户端与服务器检测实现,而B/S中浏览器是每台计算机都已具备的,如果不建立完整的权限检测,那么“非法用户”可能通过浏览器轻易访问到B/S系统中的所有功能。因此B/S业务系统需要有一个权限管理系统来实现访问权限检测,让经过授权的用户可以正常合法的使用已授权功能,而对那些未经授权的“非法用户”将无法访问。部分实现代码如下:
4 结束语
《离散数学》精品课程网站是对离散数学课程的展示和为学生学习该课程而提供的一个网络平台。为教育教学质量的提高提供了良好的环境与技术平台,随着互联网的日趋发展,这样的课程网站必将成为一项重要的辅助教学方式。使用网络教学方法,也会使学生学习的效率大大提高。因此采用精品课程网站对学校教学将是一种很有效的手段,也将是一种必然的趋势。
摘要：结合《离散数学》教学实际,经过对省级精品课程《离散数学》辅助教学网站的建设作详细的需求分析,设计与并实现了教学信息发布、权限管理、在线讨论、在线考试等主要模块功能,为教育教学质量的提高提供了良好的环境与技术平台。
关键词：离散数学,精品课程,MVC架构,PHP,MYSQL
参考文献
[1]国家精品课程评审指标(2010)[EB/OL].[2010-05-10].http://www.jingpinke.com/xpe/portal/20a4bb00-1188-1000.
[2]张领.Web框架下基于.NET的精品课程网站开发[J].计算机时代,2010(7):65-66.
[3]张钰,章炯民.面向计算机科学的离散数学网站的设计和实现[J].2007(17):1243-1244.
摘 要： 《离散数学》是针对网络和软件专业的学生所开设的专业必修课，该课程的学习有助于培养计算机方面的高科技人才的数学素养，培养学生应用《离散数学》的相关知识解决实际问题的能力。作者主要结合学生的学习反馈、学校的发展及教学实践，对《离散数学》这门课程的教学方法及改革提出了心得体会。
关键词： 教学改革 《离散数学》 现代化教学 讨论组
一、引言
《离散数学》是各高等院校理工科专业（尤其是网络和软件专业）的一门非常重要的必修课，它是现代数学的一个重要分支，该课程的核心内容主要是围绕离散量的有关数据及其的逻辑关系展开的。随着社会的发展及各个学科的不断进步，离散数学这门学科不仅仅为学生提供基础知识，更应该借助这门课程培养学生的逻辑推理能力、自主学习能力和抽象概括能力。从理论知识的角度分析，对于计算机科学与网络技术专业的学生来说，学好离散数学这门课程，可以为往后的专业课学习做铺垫、打基础。因为计算机科学与网络技术专业的学生的专业课程里包括算法与分析、数据库理论、操作系统、数据结构和自动化理论等，而对这些课程的学习理解都要以离散数学为基础。从培养能力的角度分析，学好离散数学这门学科，可以培养学生的逻辑推理能力和缜密概括能力，培养学生发现问题、思考问题和解决问题的能力。随着这些年教学工作的发展，《离散数学》这门学科有所变化，但是很多学生反映这门课程概念太多、内容过于抽象，而且理论性非常强。为了让学生更好地学习这门课程，作者将结合学生的学习反馈、学校的培养方案及教学经验，对《离散数学》这门课程的教学方法及改革给出心得体会。
二、内容体系
结合本校对学生的培养方案，《离散数学》这门学科所讲授的内容主要分为五大部分：数理逻辑、集合论、代数系统、图论和计算机科学中的应用。展开来说，主要讲解的内容有命题逻辑、谓词逻辑、集合与关系、代数结构及图论等。学习这门学科，一方面为软件、网络的学生学习专业课做铺垫，另一方面为了培养计算机方面的高技术人才所必备的基本数学素养。那么对于高校教师而言，如何找到一种有效的教学方法，使学生对《离散数学》这门学科感兴趣并高效学习，对于独立院校来说变得尤为重要。
三、《离散数学》在教育教学工作中存在的问题及相应的改革措施
1.《离散数学》在教育教学工作中存在的问题
《离散数学》的发展已有多年，它不仅在数学领域发挥着非常重要的作用，而且在计算机领域中起着不可替代的作用。近几年来，随着科学技术的发展，《离散数学》在教育教学工作中随之出现一些问题。相关的教学内容、教学计划、教学方法等都存在一些不足有待弥补。（1）传统的教学体制对于现代的学生来讲并不是很适用，它的弊端在于过去的教学主要以课本为主，把知识内容讲授给学生是老师的主要任务，教师的作用更突出一些。但与此同时传统教学也有独特的优点，传统教学主要利用课本、粉笔、黑板等手段将知识讲授给学生，突出言传身教的特点。这种教学方式可以拉近教师和学生之间的距离，教师引导学生学习，启发学生的思维创造力，这些行为不仅有助于促进师生感情，更有利于为学生的身心发展提供有利的条件。（2）随着社会的发展，现代化教学越来越普遍，以多媒体的出现为主要代表，让教学内容更丰富多彩，尤其对于数学这门学科，图画和动画的辅助能够达到非常好的效果。多媒体的出现，不仅让本学科的内容更丰富，而且让学生接触更多与之相关的其他内容。另外，使用多媒体讲课还可以有效地提高教学质量，PPT的使用既可以让丰富的教育教学资源得以共享，又可以促进师生互动。但是，多媒体教学有着局限性，由于多媒体放映过快，很容易使得课程推进过快，学生独立思考的时间减少，这就降低了学生的学习效率。另一方面，多媒体的使用会使得老师的注意力大多在多媒体上，而减少和学生的交流。我校采取的是现代化教学模式（多媒体教学），教材用的是上海科技文献出版的《离散数学》，这本书相对来说比较适合本校学生的基础及教学课时的安排。但是，离散数学这门学科对于大部分高校（尤其是独立学院）的学生来说免不了理论偏重和内容抽象。对于刚走进大学生活的孩子们，遇到理论性较强、内容有比较抽象的学科可能会不知所措，甚至学生都不知道这些跟自己的专业有何联系，经调查发现70%的学生缺乏学习兴趣，几乎50%的学生上课注意力不集中，玩手机现象严重。通过这两年的教学实践，发现对于独立学院要想完成培养应用型人才的任务，单纯地采取多媒体教学还是远远不够的，下面围绕《离散数学》在教育教学工作中存在的问题，谈谈对这些问题采取的改革措施.
2.《离散数学》课程教学改革措施
2.1注重基础教学。对于计算机专业的学生而言，离散数学主要是一门工具课，所以我校在教学的过程中适度淡化理论的推导，尽量将繁难及复杂的问题简单化，多突出基本的概念、技能、方法，涉及的性质和定理，最好以图形或简单的例题加以说明解释。这样既可以提高学生的学习积极性，又可以增强学生应用离散数学的知识解决实际问题的能力。
2.2采取多媒体板书相结合的教学手段。结合计算机专业学生的特点，在具体实施《离散数学》的教学过程中，主要采取多媒体和板书相结合的授课方法。由于讲解这门课程时需要大量的推导和计算，学生需要动手练习和独立思考，为了避免学生对学科细节和环节掌握得不够清晰、明白，不能单一地使用多媒体教学，否则很容易加快推进课程内容，黑板的使用有助于加强对学生的启发。教师使用黑板，既能够吸引学生的注意力，又能够留出时间让学生思考问题、分析问题，甚至解决问题，从而达到预期的教学目的。理论知识（主要是概念、性质和定理）以解释为主，重点放在其应用上。讲解知识和例题的时候，以多媒体为辅助工具，主要借助黑板进行讲解，习题课全部采用黑板教学。
2.3借助网络平台，建立离散数学讨论群。信息时代，手机成为学生们生活当中必不可少的一部分，从最开始只是接听电话到现在非常先进的智能化。让学生迷失了方向。他们把大部分时间和精力留给手机，却忽略他们来到大学校园的初衷。信息化的出现，对人们来说，既有利又有弊，结合学生的特点和心理，在这两个学期里，建立离散数学讨论群，为了提高学生的学习积极性，在群里设立奖惩措施，同时建立这个群不只是为了解决学习上的问题，还可以解决其他生活方面遇到的问题。这样不仅拉近我和学生之间的距离，更重要的是让学生充分利用时间学习。同学之间相互讨论，相互帮助，让他们既学到知识又学会做人。
3.实践成果
（1）教师教学能力和水平提高显著。项目组的教师能将教学当做人生事业追求，在教学各环节中严格要求自己，认真上好每堂课，起到为人师表的典范作用。项目组有青年教师教学竞赛三等奖1人。（2）学生的学习效果。实践表明，通过教学改革极大地调动了学生对离散数学的积极性。学生的出勤率、听课率明显提高，更愿意在老师的带领下好好学习。但由于时间紧张，项目的研究仍有不足之处。
参考文献：
[1]左孝凌.离散数学.上海科学技术文献出版社，1981.
[2]耿素云.离散数学.清华大学出版社.
课程设计题目：离散时间信号与系统的频域分析及其编程实现
初始条件：
1.Matlab6.5以上版本软件；
2.课程设计辅导资料：“Matlab语言基础及使用入门”、“信号与系统”、“数字信号处理原理与实现”、“Matlab及在电子信息课程中的应用”等；
3.先修课程：信号与系统、数字信号处理、Matlab应用实践及信号处理类课程等。
要求完成的主要任务：（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）
1.课程设计时间：1周；
2.课程设计内容：离散时间信号与系统的频域分析及其编程实现，具体包括：离散时间信号的傅里叶
变换、离散傅里叶变换、系统的幅频和相频特性等；
3.本课程设计统一技术要求：研读辅导资料对应章节，对选定的设计题目进行理论分析，针对具体设
计部分的原理分析、建模、必要的推导和可行性分析，画出程序设计框图，编写程序代码（含注释），上机调试运行程序，记录实验结果（含计算结果和图表），并对实验结果进行分析和总结，按要求进行实验演示和答辩等；
4.课程设计说明书按学校“课程设计工作规范”中的“统一书写格式”撰写，具体包括：
① 目录；
② 与设计题目相关的理论分析、归纳和总结；
③ 与设计内容相关的原理分析、建模、推导、可行性分析；
④ 程序设计框图、程序代码（含注释）、程序运行结果和图表、实验结果分析和总结；
⑤ 课程设计的心得体会（至少500字）；
⑥ 参考文献（不少于5篇）；
⑦ 其它必要内容等。
时间安排： 1周（第18周）
附——具体设计内容：
1.已知序列xn=[1 1 1 1 ],试用MATLAB编写程序，计算该序列的离散付里叶变换及逆离散付里叶变
换。
2.取一个周期的正弦信号，作8点采样，求它的连续频谱。然后对该信号进行N个周期延拓，再求
它的连续频谱。把N无限增大，比较分析其结果。
3.一个三阶滤波器由以下的差分方程描述：
y(n)= 0.0211x(n)+ 0.0443x(n-1)+ 0.044x(n-2)+0.0181x(n-3)
+1.76y(n-1)-1.272y(n-2)+ 0.3181y(n-3)
数学语言与证明方法
例1 设E={ x | x是北京某大学学生}, A,B,C,D是E的子集, A= { x | x是北京人}，B= { x | x是走读生}, C= { x | x是数学系学生}，D= { x | x是喜欢听音乐的学生}.试描述下列各集合中学生的特征:
(AD) ~ C={ x | x是北京人或喜欢听音乐,但不是数学系学生} ~ AB={ x | x是外地走读生}(A-B) D={ x | x是北京住校生, 并且喜欢听音乐} ~ D ~ B={ x | x是不喜欢听音乐的住校生} 例3 证明:(1)AB=BA(交换律)证 x
xAB
xAxB
(并的定义)
xBxA
(逻辑演算的交换律)
xBA
(并的定义)(2)A(BC)=(AB)(AC)(分配律)证 x
xA(BC)
xA(xB xC)
(并,交的定义)
(xAxB)(xAxC)
(逻辑演算的分配律)
x(AB)(AC)
(并,交的定义)(3)AE=E(零律)证 x
xAE
xAxE
(并的定义)
xA1
(全集E的定义)
1
(逻辑演算的零律)
xE
(全集E的定义)(4)AE=A(同一律)证 x
xAE
xAxE
(交的定义)
xA1
(全集E的定义)
xA
(逻辑演算的同一律)例4 证明 A(AB)=A（吸收律）证 利用例3证明的4条等式证明
A(AB)
=(AE)(AB)
(同一律)
= A(EB)
(分配律)
= A(BE)
(交换律)
= AE
(零律)
= A
(同一律)例5 证明(A-B)-C=(A-C)-(B-C)证
(A-C)-(B-C)
=(A ~C) ~(B ~C)
(补交转换律)
=(A ~C)(~B ~~C)
(德摩根律)
=(A ~C)(~B C)
(双重否定律)
=(A ~C ~B)(A ~C C)
(分配律)
=(A ~C ~B)(A )
(矛盾律)
= A ~C ~B
(零律,同一律)
=(A ~B) ~C
(交换律,结合律)
=(A – B)– C
(补交转换律)例6 证明(AB)(AC)=(BC)(AC))((AC)A 例7 设A,B为任意集合, 证明:(1)AAB 证 x xA xAxB
(附加律)
xAB
(2)ABA
证 x xAB xAxB
xA
(化简律)(3)A-BA
证 x xA-B xAxB
xA
(化简律)(4)若AB, 则P(A)P(B)证 x xP(A) xA
xB
(已知AB)
xP(B)例8 证明 AB=AB-AB.证
AB=(A~B)(~AB)
=(A~A)(AB)(~B~A)(~BB)
=(AB)(~B~A)
=(AB)~(AB)
=AB-AB 例3 若A-B=A, 则AB=
证 用归谬法, 假设AB, 则存在x,使得
xAB xAxB xA-BxB
(A-B=A)
xAxBxB xBxB，矛盾 例4 证明
是无理数
证
假设
是有理数, 存在正整数n,m, 使得
=m/n,不妨设m/n为既约分数.于是m=n, m2=2n2, m2是偶数, 从而m是偶数.设m=2k, 得(2k)2=2n2, n2=2k2, 这又得到n也 是偶数, 与m/n为既约分数矛盾.例6 对于每个正整数n, 存在n个连续的正合数.证
令x=(n+1)!
则 x+2, x+3,…, x+n+1是n个连续的正合数:
i | x+i，i=2,3,…,n+1 例7 判断下述命题是真是假:
若AB=AC, 则B=C.解
反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有
AB=AC = {a,b} 但BC, 故命题为假.例8 证明:对所有n1, 1+2+ … +n=n(n+1)/2 证
归纳基础.当n=1时, 1=1(1+1)/2, 结论成立.归纳步骤.假设对n1结论成立, 则有
1+2+ … +n +(n+1)=n(n+1)/2 +(n+1)
(归纳假设)
=(n+1)(n+2)/2 得证当n+1时结论也成立.例9 任何大于等于2的整数均可表成素数的乘积 证 归纳基础.对于2, 结论显然成立.归纳步骤.假设对所有的k(2kn)结论成立, 要证结论 对n+1也成立.若n+1是素数, 则结论成立;否则n+1=ab, 2a,b 命题逻辑 例1 下列句子中那些是命题？ (1)北京是中华人民共和国的首都.(2)2 + 5 ＝8.(3)x + 5 ＞ 3.(4)你会开车吗？ (5)2050年元旦北京是晴天.(6)这只兔子跑得真快呀！(7)请关上门！(8)我正在说谎话.(1),(2),(5)是命题,(3),(4),(6)~(8)都不是命题 例2 将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解 (1)p∧q (2)p∧q (3)p∧q(4)记 r:张辉是三好生, s:王丽是三好生，r∧s(5)简单命题，记 t:张辉与王丽是同学 例3 将下列命题符号化(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解 (1)p∨r, 真值:1(2) p∨q, 真值: 1(3)r∨s,真值: 0(4)记t:元元拿一个苹果,u:元元拿一个梨 (t∧u)∨(t∧u)(5)记v:王晓红生于1975年,w:王晓红生于1976年 (v∧w)∨(v∧w)又可形式化为 v∨w 例4 设p:天冷, q:小王穿羽绒服，将下列命题符号化 (1)只要天冷，小王就穿羽绒服.pq(2)因为天冷，所以小王穿羽绒服.pq (3)若小王不穿羽绒服，则天不冷.qp 或 pq(4)只有天冷，小王才穿羽绒服.qp(5)除非天冷，小王才穿羽绒服.qp(6)除非小王穿羽绒服，否则天不冷.pq (7)如果天不冷，则小王不穿羽绒服.pq 或 qp(8)小王穿羽绒服仅当天冷的时候.qp 例5 求下列复合命题的真值 (1)2+2＝4 当且仅当 3+3＝6.(2)2+2＝4 当且仅当 3是偶数.0(3)2+2＝4 当且仅当 太阳从东方升起.(4)2+2＝5 当且仅当 美国位于非洲.(5)f(x)在x0处可导的充要条件是它在 x0处连续.0 例6 公式A=( p1 p2 p3)(p1 p2) 000是成真赋值，001是成假赋值 公式B=(pq)r 000是成假赋值，001是成真赋值 例3 证明 p(qr)(pq)r 证 p(qr) p(qr) （蕴涵等值式） (pq)r （结合律） (pq)r （德摩根律） (pq)r （蕴涵等值式 例4 证明: p(qr) (pq)r 方法一 真值表法（见例2） 方法二 观察法.容易看出000使左边成真, 使右边成假.方法三 先用等值演算化简公式, 再观察.例5 用等值演算法判断下列公式的类型(1)q(pq)解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律）该式为矛盾式.(2)(pq)(qp)解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 该式为重言式.(3)((pq)(pq))r) 解 ((pq)(pq))r) (p(qq))r （分配律） p1r （排中律） pr （同一律） 非重言式的可满足式.如101是它的成真赋值,000是它的 成假赋值.例1 求(pq)r 的析取范式与合取范式 解 (pq)r (pq)r (pq)r 析取范式 (pr)(qr) 合取范式 注意: 公式的析取范式与合取范式不惟一.例1(续)求(pq)r 的主析取范式与主合取范式 解(1)(pq)r (pq)r pq (pq)1 同一律 (pq)(rr) 排中律 (pqr)(pqr) 分配律 m4m5 r (pp)(qq)r 同一律, 排中律 (pqr)(pqr)(pqr)(pqr) m0 m2 m4 m6 得 (pq)r m0 m2 m4 m5 m6 可记作 (0,2,4,5,6)(2)(pq)r (pr)(qr) pr p0r 同一律 p(qq)r 矛盾律 分配律 (pqr)(pqr) 分配律 M1M3 qr (pp)qr 同一律, 矛盾律 (pqr)(pqr) 分配律 M3M7 得 (pq)r M1M3M7 可记作 (1,3,7)例2(1)求 A (pq)(pqr)r的主析取范式 解 用快速求法 (1)pq (pqr)(pqr) m2 m3 pqr m1 r (pqr)(pqr)(pqr)(pqr) m1 m3 m5 m7 得 A m1 m2 m3 m5 m7 (1,2,3,5,7)(2)求 B p(pqr)的主合取范式 解 p (pqr)(pqr)(pqr)(pqr) M4M5M6M7 pqr M1 得 B M1M4M5M6M7 (1,4,5,6,7)例3 用主析取范式判断公式的类型:(1)A (pq)q (2)B p(pq) (3)C(pq)r 解(1)A ( pq)q (pq)q 0 矛盾式(2)B p(pq) 1 m0m1m2m3 重言式(3)C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0m1m3 m5m7 非重言式的可满足式 例4 用主析取范式判断下面2组公式是否等值:(1)p与(pq)(pq)解 p p(qq)(pq)(pq) m2m3 (pq)(pq) (pq)(pq) (pq)(pq) m2m3 故 p (pq)(pq)(2)(pq)r 与 p(qr)解(pq)r (pqr)(pqr) (pqr)(pqr)(pqr)(pqr) m1m3m5 m6m7 p(qr)(pq)(p r) (pqr)(pqr)(pqr)(pqr) m5 m6m7 故 (pq)r p(qr)例5 某单位要从A,B,C三人中选派若干人出国考察, 需满 足下述条件:(1)若A去, 则C必须去;(2)若B去, 则C不能去;(3)A和B必须去一人且只能去一人.问有几种可能的选派方案? 解 记p:派A去, q:派B去, r:派C去 (1)pr，(2)qr，(3)(pq)(pq)求下式的成真赋值 A=(pr)(qr)((pq)(pq))例6 求A=(pqr)(pqr)(pqr)的主合取范式 解 A m1m3m7 M0M2M4M5M6 例1 判断下面推理是否正确:(1)若今天是1号, 则明天是5号.今天是1号.所以, 明天是5号.解 设 p: 今天是1号, q: 明天是5号 推理的形式结构为 (p®q)Ùp®q 证明 用等值演算法 (p®q)Ùp®q Û Ø((ØpÚq)Ùp)Úq Û((pÙØq)ÚØp)Úq Û ØpÚØqÚq Û 1 得证推理正确 (2)若今天是1号, 则明天是5号.明天是5号.所以, 今天是1号.解 设p: 今天是1号, q: 明天是5号.推理的形式结构为 (p®q)Ùq®p 证明 用主析取范式法 (p®q)Ùq®p Û(ØpÚq)Ùq®p Û Ø((ØpÚq)Ùq)Úp Û ØqÚp Û(ØpÙØq)Ú(pÙØq)Ú(pÙØq)Ú(pÙq) Û m0Úm2Úm3 01是成假赋值, 所以推理不正确.例2 在自然推理系统P中构造下面推理的证明: 前提: pÚq, q®r, p®s, Øs 结论: rÙ(pÚq)证明 ① p®s 前提引入 ② Ø s 前提引入 ③ Ø p ①②拒取式 ④ pÚq 前提引入 ⑤ q ③④析取三段论 ⑥ q®r 前提引入 ⑦ r ⑤⑥假言推理 ⑧ rÙ(pÚq) ⑦④合取 推理正确, rÙ(pÚq)是有效结论 例3 构造推理的证明: 若明天是星期一或星期三, 我就有 课.若有课, 今天必需备课.我今天下午没备课.所以, 明天 不是星期一和星期三.解 设 p:明天是星期一, q:明天是星期三，r:我有课，s:我备课 前提:(pÚq)®r, r®s, Øs 结论: ØpÙØq 例4 构造下面推理的证明: 前提: ØpÚq, ØqÚr, r®s 结论: p®s 证明 ① p 附加前提引入 ② ØpÚq 前提引入 ③ q ①②析取三段论 ④ ØqÚr 前提引入 ⑤ r ③④析取三段论 ⑥ r®s 前提引入 ⑦ s ⑤⑥假言推理 推理正确, p®s是有效结论 例5 构造下面推理的证明 前提: Ø(pÙq)Úr, r®s, Øs, p 结论: Øq 证明 用归缪法 ① q 结论否定引入 ② r®s 前提引入 ③ Øs 前提引入 ④ Ør ②③拒取式 ⑤ Ø(pÙq)Úr 前提引入 ⑥ Ø(pÙq) ④⑤析取三段论 ⑦ ØpÚØq ⑥置换 ⑧ Øp ①⑦析取三段论 ⑨ p 前提引入 ⑩ ØpÙp ⑧⑨合取 推理正确, Øq是有效结论 例6 用归结证明法构造下面推理的证明: 前提:(p®q)®r, r®s, Øs 结论:(p®q)®(pÙs)解 (p®q)®r Û Ø(ØpÚq)Úr Û(pÙØq)Úr Û(pÚr)Ù(ØqÚr) r®s Û ØrÚs (p®q)®(pÙs)Û Ø(ØpÚq)Ú(pÙs)Û(pÙØq)Ú(pÙs) Û pÙ(ØqÚs)推理可表成 前提: pÚr, ØqÚr, ØrÚs, Øs 结论: pÙ(ØqÚs) 第3章 一阶逻辑 例1(1)4是偶数 4是个体常项, “是偶数”是谓词常项, 符号化为: F(4)(2)小王和小李同岁 小王, 小李是个体常项, 同岁是谓词常项.记a:小王，b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b)(3)x< y x,y是命题变项, < 是谓词常项, 符号化为: L(x,y)(4)x具有某种性质P x是命题变项, P是谓词变项, 符号化为: P(x)例2 将下述命题用0元谓词符号化, 并讨论它们的真值:(1) 是无理数, 而 是有理数(2)如果2>3，则3<4 解 (1)设F(x): x是无理数, G(x): x是有理数 符号化为 真值为0(2)设 F(x,y): x>y, G(x,y): x 个体域分别取(a)人类集合,(b)全总个体域.解:(a)(1)设F(x): x爱美，符号化为 x F(x) (2)设G(x): x用左手写字，符号化为 x G(x) (b)设M(x): x为人，F(x), G(x)同(a)中 (1)x(M(x)F(x)) (2) x(M(x)G(x))M(x)称作特性谓词 例4 将下列命题符号化, 并讨论其真值:(1)对任意的x, 均有x2-3x+2=(x-1)(x-2)(2)存在x, 使得x+5=3 分别取(a)个体域D1=N,(b)个体域D2=R 解 记F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3(a)(1)x F(x) 真值为1 (2)x G(x) 真值为0(b)(1)x F(x) 真值为1 (2)x G(x) 真值为1 例5 将下面命题符号化:(1)兔子比乌龟跑得快 (2)有的兔子比所有的乌龟跑得快(3)并不是所有的兔子都比乌龟跑得快(4)不存在跑得一样快的兔子和乌龟 解 用全总个体域，令F(x): x是兔子, G(y): y是乌龟，H(x,y): x比y跑得快，L(x,y): x和y跑得一样快(1)xy(F(x)G(y)H(x,y))(2)x(F(x)(y(G(y)H(x,y)))(3) xy(F(x)G(y)H(x,y))(4) xy(F(x)G(y)L(x,y))例6 公式 x(F(x,y)yG(x,y,z))x的辖域:(F(x,y)yG(x,y,z))，指导变元为x y的辖域:G(x,y,z)，指导变元为y x的两次出现均为约束出现 y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现.例7 公式 x(F(x)xG(x))x的辖域:(F(x)xG(x))，指导变元为x x的辖域:G(x)，指导变元为x x的两次出现均为约束出现.但是, 第一次出现的x是x中 的x, 第二次出现的x是x中的x.例8 给定解释I 如下: (a)个体域 D=N (b) (c) (d)谓词 说明下列公式在 I 下的含义, 并讨论其真值 (1)xF(g(x,a),x)x(2x=x) 假命题 (2)xy(F(f(x,a),y)F(f(y,a),x))xy(x+2=yy+2=x) 假命题(3)xyzF(f(x,y),z) xyz(x+y=z) 真命题 (4)xF(f(x,x),g(x,x)) x(2x=x2) 真命题(5)F(f(x,a), g(x,a))x+2=2x 不是命题 (6)x(F(x,y)F(f(x,a), f(y,a)))x(x=yx+2=y+2) 真命题 例8(1)~(4)都是闭式, 在I下全是命题.(5)和(6)不是闭式, 在I下(5)不是命题,(6)是命题 例9 判断下列公式的类型:(1)x(F(x)G(x))取解释I1, D1=R，:x是整数，:x是有理数, 取解释I2, D2=R，:x是整数，:x是自然数, 非永真式的可满足式(2)(xF(x))(xF(x)) 这是 pp 的代换实例, pp是重言式，永真式(3)(xF(x)yG(y)) yG(y)这是(pq)q的代换实例, (pq)q是矛盾式 矛盾式 例1 消去公式中既约束出现、又自由出现的个体变项 真命题 假命题 (1)xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z) 换名规则 uF(u,y,z) vG(x,v,z) 换名规则 或者 xF(x,u,z) yG(x,y,z) 代替规则 xF(x,u,z) yG(v,y,z) 代替规则(2)x(F(x,y) yG(x,y,z)) x(F(x,y) tG(x,t,z)) 换名规则 或者 x(F(x,t) yG(x,y,z)) 代替规则 例2 设个体域D={a,b,c}, 消去下面公式中的量词:(1)x(F(x)G(x))(F(a)G(a))(F(b)G(b))(F(c)G(c))(2)x(F(x)yG(y)) xF(x)yG(y) 量词辖域收缩 (F(a)F(b)F(c))(G(a)G(b)G(c))(3)xyF(x,y) x(F(x,a)F(x,b)F(x,c))(F(a,a)F(a,b)F(a,c))(F(b,a)F(b,b)F(b,c)) (F(c,a)F(c,b)F(c,c))例3 给定解释I:(a)D={2,3},(b) (c) :x是奇数，: x=2 y=2，: x=y.在I下求下列各式的真值:(1)x(F(f(x))G(x, f(x))) 解 (F(f(2))G(2, f(2)))(F(f(3))G(3, f(3)))(11)(01) 1(2)xyL(x,y)解 yL(2,y)yL(3,y)(L(2,2)L(2,3))(L(3,2)L(3,3))(10)(01) 0 例4 证明下列等值式: x(M(x)F(x)) x(M(x) F(x))证 左边 x (M(x)F(x)) 量词否定等值式 x(M(x)F(x)) x(M(x) F(x))例5 求公式的前束范式(1)xF(x)xG(x)解 xF(x)xG(x) 量词否定等值式 x(F(x)G(x)) 量词分配等值式 解2 xF(x)yG(y) 换名规则 xF(x)yG(y) 量词否定等值式 x(F(x)yG(y)) 量词辖域扩张 xy(F(x)G(y)) 量词辖域扩张 第4章 关系 例1 <2,x+5>=<3y4,y>，求 x, y.解 3y4=2, x+5=y y=2, x= 3 例2 A={0, 1}, B={a, b, c} AB={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} BA ={, A = {}, B = P(A)A = {<,>, <{},>} P(A)B = 例3 (1)R={ ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2)C={ R={ |A|=n, |B|=m, |A×B|=nm, A×B 的子集有 个.所以从A到B有 元关系.|A|=n, A上有 不同的二元关系.例如 |A|=3, 则 A上有512个不同的二元关系.例 5A={a, b, c, d}, R={,,, 1110100000000100例1 R={, domR = ranR = fldR = 例2 R={<1,2>, <2,3>, <1,4>, <2,2>} S={<1,1>, <1,3>, <2,3>, <3,2>, <3,3>} R1 = R∘S = S∘R = 个不同的二 例3 设A = {a, b, c, d}, R = {, 0100010001 10101010102M M0001000100 0000000000 例1 A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中 R1 = {, 001010010000010101000000R2自反, R3 反自反, R1既不自反也不反自反.例2 设A＝{a,b,c}, R1, R2, R3和R4都是A上的关系, 其中 R1＝{, R1＝{, R2＝{, R3＝{} R1 和 R3 是A上的传递关系, R2不是A上的传递关系.例4 证明若 IA R，则 R 在 A 上自反.证 任取x，xA 因此 R 在 A 上是自反的.例5 证明若 R=R1 , 则 R 在A上对称.证 任取 因此 R 在 A 上是对称的.例6 证明若 R∩R1IA , 则 R 在 A 上反对称.证 任取 因此 R 在 A 上是反对称的.例7 证明若 R∘RR , 则 R 在 A 上传递.证 任取 因此 R 在 A 上是传递的.例8 判断下图中关系的性质, 并说明理由 (1)不自反也不反自反；对称, 不反对称；不传递.(2)反自反, 不是自反；反对称, 不是对称；传递.(3)自反，不是反自反；反对称，不是对称；不传递.例1 设A={a,b,c,d}, R={, 例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R： R={ x↔A, 有x≡x(mod 3) x,y↔A, 若x≡y(mod 3), 则有y≡x(mod 3) x,y,z↔A, 若x≡y(mod 3), y≡z(mod 3), 则有 x≡z(mod 3)例2 令A={1, 2, …, 8}，A关于模 3 等价关系R 的商集为 A/R = { {1, 4,7}, {2, 5, 8}, {3, 6} } A关于恒等关系和全域关系的商集为： A/IA = { {1},{2}, … ,{8}} A/EA = { {1, 2, … ,8} } 例3 设A＝{a, b, c, d}, 给定 1, 2, 3, 4, 5, 6如下： 1={{a, b, c},{d}}， 2={{a, b},{c},{d}} 3={{a},{a, b, c, d}}， 4={{a, b},{c}} 5={,{a, b},{c, d}}， 6={{a,{a}},{b, c, d}} 则 1和 2是A的划分, 其他都不是A的划分.例4 给出A＝{1,2,3}上所有的等价关系 求解思路：先做出A的所有划分, 然后根据划分写出 对应的等价关系.A上的等价关系与划 分之间的对应： 4对应于全域关系EA 5对应于恒等关系IA 1, 2和 3分别对应于等价关系 R1, R2和R3.其中 R1={<2,3>,<3,2>}∪IA R2={<1,3>,<3,1>}∪IA R3={<1,2>,<2,1>}∪IA 例5 设A={1,2,3,4}，在AA上定义二元关系 R： < AA={<1,1>, <1,2>, <1,3>, <1,4>, <2,1>, <2,2>, <2,3>，<2,4>,<3,1>, <3,2>, <3,3>, <3,4>, <4,1>, <4,2>, <4,3>，<4,4>} 根据有序对 例6 <{ 1, 2, 3, 4, 5, 6, 7, 8, 9 }, R整除> 例7 已知偏序集的哈斯图如下图所示, 试求出集合A和关系R的表达式.A={a, b, c, d, e, f, g, h} R={ 例8 设偏序集如下图所示，求A 的极小元、最小元、极大元、最大元.设B＝{ b, c, d }, 求B 的下界、上界、下 确界、上确界.解：极小元：a, b, c, g；极大元：a, f, h；没有最小元与最大元.B的下界和最大下界都不存在, 上界有d 和 f, 最小上界为 d.第5章 函数 例1 设A = {1, 2, 3}, B = {a, b}, 求BA.解BA = { f0, f1, … , f7 }, 其中 f0={<1,a>,<2,a>,<3,a>} f1={<1,a>,<2,a>,<3,b>} f2={<1,a>,<2,b>,<3,a>} f3={<1,a>,<2,b>,<3,b>} f4={<1,b>,<2,a>,<3,a>} f5={<1,b>,<2,a>,<3,b>} f6={<1,b>,<2,b>,<3,a>} f7={<1,b>,<2,b>,<3,b>} 例2 判断下面函数是否为单射, 满射, 双射的, 为什么?（1）f : R→R, f(x)= x2+2x1（2）f : Z+→R, f(x)=lnx, Z+为正整数集（3）f : R→Z, f(x)=x（4）f : R→R, f(x)=2x+1（5）f : R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集.解(1)f : R→R, f(x)= x2+2x1 在x=1取得极大值0.既不是单射也不是满射的.(2)f : Z+→R, f(x)=lnx 单调上升, 是单射的.但不满射, ranf={ln1, ln2, …}.(3)f : R→Z, f(x)= x 是满射的, 但不是单射的, 例如 f(1.5)=f(1.2)=1.(4)f : R→R, f(x)=2x+1 是满射、单射、双射的, 因为它是单调函数并且ranf=R.(5)f : R+→R+, f(x)=(x2+1)/x 有极小值f(1)=2.该函数既不是单射的也不是满射的.例3 A=P({1,2,3}), B={0,1}{1,2,3} 解 A={,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}.B={ f0, f1, … , f7 }, 其中 f0={<1,0>,<2,0>,<3,0>}，f1={<1,0>,<2,0>,<3,1>}, f2={<1,0>,<2,1>,<3,0>}，f3={<1,0>,<2,1>,<3,1>}，f4={<1,1>,<2,0>,<3,0>}，f5={<1,1>,<2,0>,<3,1>}，f6={<1,1>,<2,1>,<3,0>}，f7={<1,1>,<2,1>,<3,1>}.令 f : A→B，f()=f0, f({1})=f1, f({2})=f2, f({3})=f3，f({1,2})=f4, f({1,3})=f5, f({2,3})=f6, f({1,2,3})=f7 例4 A=[0,1] B=[1/4,1/2] 构造双射 f : A→B解 令 f : [0,1]→[1/4,1/2] f(x)=(x+1)/4 例5 A=Z, B=N，构造双射 f : A→B 将Z中元素以下列顺序排列并与N中元素对应： Z：011 2233 … ↓ ↓ ↓ ↓ ↓ ↓ ↓ N：0 1 2 4 5 6 … 则这种对应所表示的函数是： x02xf:ZN,f(x)2x1x0例1 设 f : R→R, g : R→R x2x3f(x) x32 g(x)x2 求 f ∘g, g∘f.如果 f 和 g 存在反函数, 求出它们的反函数.解 fg:RRx22x3fg(x)x30gf:RR(x2)2gf(x)2x1x1 f : R→R不存在反函数；g : R→R的反函数是 g1: R→R, g1(x)=x2 第6章 图 例1 下述2组数能成为无向图的度数列吗?(1)3,3,3,4;(2)1,2,2,3 解(1)不可能.有奇数个奇数.(2)能 例2 已知图G有10条边, 4个3度顶点, 其余顶点的度数均小 于等于2, 问G至少有多少个顶点? 解 设G有n个顶点.由握手定理，43+2(n-4)210 解得 n8 例3 已知5阶有向图的度数列和出度列分别为3,3,2,3,3和 1,2,1,2,1, 求它的入度列 解 2,1,1,1,2 例4 证明不存在具有奇数个面且每个面都具有奇数条棱的 多面体.证 用反证法.假设存在这样的多面体, 作无向图G= 讨论所有可能的情况.设有a个5度顶点和b个6度顶点(1)a=0, b=9; (2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)~(3)至少5个6度顶点,(4)和(5)至少6个5度顶点 方法二 假设b<5, 则a>9-5=4.由握手定理的推论, a 6 例6 画出4阶3条边的所有非同构的无向简单图 解 总度数为6, 分配给4个顶点, 最大度为3, 且奇度顶点数 为偶数, 有下述3个度数列:(1)1,1,1,3;(2)1,1,2,2;(3)0,2,2,2.1,1,1,3 1,1,2,2 例7 画出3个以1,1,1,2,2,3为度数列的非同构的无向简单图 0,2,2,2 例1 右图有 个面 R1的边界:a R2的边界:bce R3的边界:fg R0的边界:abcdde, fg deg(R1)=1 deg(R2)=3 deg(R3)=2 deg(R0)=8 例2 右边2个图是同一平面图的平面嵌入.R1在(1)中是外部面, 在(2)中是内部面;R2在(1)中是内部面, 在(2)中是外部面.R3 R1 R3 R2(1) R2 R1(2) 说明:(1)一个平面图可以有多个不同形式的平面嵌入, 它们都同构.(2)可以通过变换(测地投影法)把平面图的任何一面作为外部面 例3 证明 K5 和 K3,3不是平面图 证 K5 : n=5, m=10, l=3 K3,3 : n=6, m=9, l=4 不满足定理6.15的条件 例 5证明下面2个图均为非平面图.与K3,3同胚也可收缩到K3,3 与K5同胚也可收缩到K5 例6 画出所有非同构的6阶11条边的简单连通非平面图 解 在K5(5阶10条边)上加一个顶点和一条边 在K3,3(6阶9条边)上加2条边 例1 某中学有3个课外活动小组:数学组, 计算机组和生物组.有赵,钱,孙,李,周5名学生, 问分别在下述3种情况下, 能否选出3人各任一个组的组长?(1)赵, 钱为数学组成员, 赵,孙,李为计算机组成员, 孙,李,周为生物组成员.(2)赵为数学组成员, 钱,孙,李为计算机组成员, 钱,孙,李,周为生物组成员.(3)赵为数学组和计算机组成员, 钱,孙,李,周为生物组成员.解 数 计 生 数 计 生 赵 钱 孙 李 周 赵 钱 孙 李 周 (1(数 计 生 赵 钱 孙 李 周 (3(1),(2)有多种方案,(3)不可能 例2 证明下述各图不是哈密顿图: (a(b(c) (c)中存在哈密顿通路 例3 证明右图不是哈密顿图 证 假设存在一条哈密顿回路, a,f,g是2度顶点, 边(a,c),(f,c)和(g,c)必在这条哈密顿回路上,从而点c出现3次, 矛盾.a b c f d e g 此外, 该图满足定理6.10的条件, 这表明此条件是必要、而不充分的.又, 该图有哈密顿通路.例4 有7个人, A会讲英语, B会讲英语和汉语, C会讲英语、意大利语和俄语, D会讲日语和汉语, E会讲德语和意大利语, F会讲法语、日语和俄语, G会讲法语和德语.问能否将他们沿圆桌安排就坐成一圈, 使得每个人都能与两旁的人交谈? 解 作无向图, 每人是一个顶点, 2人之间有边他们有共同的语言.G F E D A B C 1、集合的运算以及运算律； 2、关系的三种表示方法，以及他们之间的转化； 3、常见关系的定义； 4、哈斯图的画法，以及最大最小元、极大极小元、上下界，上下确界的求法； 5、单射、满射以及双射的证明（尤其是在代数系统中）； 6、代数系统的概念以及代数系统的常用性质，能够证明具体的代数系统的运算律，找出单 位元，零元、以及逆元等； 7、环和格只要记住不同的环和格满足的运算律就好； 8、各种图和树的概念及相关的结论，比如：欧拉图的充要条件，哈密顿图的充分条件、必 要条件、充要条件等； 9、图的矩阵计算； 10、会画一些简单的树； 11、五种联结词的真值表； 12、一些要求记住的命题公式； 13、命题公式的证明； 14、命题公式的析取范式，合取范式，主析取范式和主合取范式的求法。 题型：填空题、证明题和解答题。 友情提醒： 1、周三下午一点半到三点半在逸夫楼519答疑。 2、概念、定理和公式请务必记住，可能会出填空题； 3、考试内容不会超出我们的重点； 关键词：无穷大,无限集合,基数,一一对应 离散数学是信息技术专业的一门必修课程，是研究信息技术科学的有力工具，而集合论又是其重要组成部分，集合论能直接应用到计算机科学的各个部分中去，如程序设计语言、数据结构的研究、编译原理等等，许多教材集合论这部分内容理论性较强，所使用的数学语言描述较为抽象，不够形象化，结构上也不够简洁，轻数学过程和直观意义，学生不易接受。这就需要教材内容和教学方法通俗化，形象化，便于学生对知识的理解和运用，需要改进教学方法和学生的学习方法，扩展学习途径，整合课程内容，以提高学习效果。 （一）学习方法及学习途径 首先，在教学中，要积极调动学生的学习兴趣，引入生动的问题，如理发师问题，直线上点的个数与平面上点的个数的比较问题等，用启发、探究的方式使学生产生深入研究的学习欲望，由此引起学生思考，变被动学习为主动学习，培养学生的创新精神;其次，把演讲艺术引入教学，娓娓讲述康托探讨集合论体系的过程，使学生能够循着大数学家的研究过程对集合论有一个概览，走数学家走过的路，反思其方法，使学生学会探索知识形成过程的规律;第三，使学生明确集合论的起源，发展阶段，所要解决的问题，特别是它的结构，这里，我们用一个简洁的数列描述了它的结构;第四，课堂教学要在一定的理论基础上进行，将基本概念，基本理论讲解透彻，使用数学语言描述这部分内容，把其理论结构逐步展开;最后，课堂教学中要注意精讲多练，并在课堂结束时进行交流。在讲授教材内容时，还要积极引入本课程体系中的新知识，新原理，不断充实本课程的最新研究成果，使学生了解学科前沿，开拓眼界，激发学习兴趣，这就要使学生具备自学能力和查阅资料、搜集信息的能力，这就涉及到学习途径的问题，除了要发挥学校图书馆、资料室等查阅资料的功能以外，更要发挥网络在查阅资料中的强大功能，第一，可以发挥国家精品课程库的功能;第二，利用网上许多信息技术方面的学习网站，下载相关的视频资料;第三，发掘网上的ftp，利用网上的数学书籍图书馆，寻找相关内容书籍;第四，使用校园网论文查询系统查阅相关论文。让学生探讨集合的性质、关系、运算和公理系统。使学生学会利用网络所提供的异常丰富的学习资源，为自己创造更多的学习机会，使自己有更多选择。同时，还可以利用多媒体技术和信息网络技术，丰富教学内容，加强教学信息质量，完善和改进课程教学。 （二）集合论内容及结构 集合是一般数学及离散数学的基础，亦是计算机科学中经常应用的基本概念，集合论是由德国数学家康托创立的。教学中集合论这部分内容主要包括：有限集合和无限集合，可数集合与不可数集合，集合基数的比较这样三部分。集合的基数就是集合所含的元素的个数，基数越大的集合，所含的元素越多。对于给定的两个集合，如何比较它们的基数大小，如果是有限集合，只要数一下它们的元素个数即可，但若是无限集合，此方法就不行了。比较无限集合大小的方法是在无限集合之间建立一一对应，如果存在从一个集合到另一个集合的一一映射，则这两个集合所含的元素一样多，这种方法对有限集合也适用，若在两个有限集合之间存在一一映射，则这两个集合所包含的元素个数相等，由此方法可以给出有限集合和无限集合的概念，即如果一个集合能与其真子集建立起一一映射，则该集合为无限集合，否则为有限集合。有限集合再添加一些元素，得到的集合与原集合相比哪个集合元素多，这个问题答案是显然的。但是无限集合再添一些元素，得到的集合与原集合相比哪个集合元素多，由此引出无限集合基数的问题，首先看可数集合与不可数集合的概念，如果存在一个集合的枚举，就称该集合为可数集合，反之为不可数集合，而枚举是指一个集合中的元素可以按某种顺序排列出来。阿列夫(ℵ)是康托创造出来的，试图把无穷大之间的阶(基数，即无限集合所包含的元素的个数)排列顺序，他发现了几个非常基本的无穷大的阶。首先是阿列夫0(0ℵ)与自然数一一对应，定义一个集合的基数为0ℵ当且仅当其能与自然数集合一一对应，由此自然数集合N和整数集合Z的基数都是0ℵ，因为它们都能与自然数之间建立一一对应关系，利用枚举的方法还可以得到有理数集合Q的基数也是0ℵ，还有没有比ℵ0更小的ℵ存在，这个问题的答案是否定的，即自然数集合是最小的无限集合;实数集合的子集[0,1]不是可数集合，这个问题的证明用的是对角线方法，下面定义集合[0,1]的基数为ℵ1，ℵ1跟自然数不能一一对应，但能跟实数一一对应，故数轴上点的个数是ℵ1，平面上所有的点，点的个数也是无穷个，确切地说也是1ℵ。引入0ℵ、1ℵ之后，康托还定义了它们之间的运算，如：ℵ1×ℵ1=ℵ12(即阿列夫1×阿列夫1=阿列夫12)，平面上点的个数是1ℵ2，这里有ℵ12=ℵ1，而不是ℵ12>ℵ1，因为平面上的点能跟直线上的点建立一一对应，不仅如此，任何一个n维空间的点都能和直线上的点一一对应，也即直线上的点和平面上的点一样多，也和n维空间的中的点一样多。还有比阿列夫1更高的阿列夫，而且有无穷多个比阿列夫1更高的无穷大的阶，康托把它们分别命名为阿列夫2，阿列夫3，……，阿列夫n，……，至此，我们得到了一个数列0ℵ，1ℵ，2ℵ，3ℵ，……，nℵ，……。 康托证明了阿列夫2的存在性，空间中所有的点构成了一个集合，这个集合的基数是1ℵ，这个集合的子集的个数就是阿列夫2，康托用严格的数学证明了这个数目比阿列夫1大，类似的推理，基数是阿列夫2的集合的所有子集的个数比阿列夫2大，记为阿列夫3，依此类推，就有ℵ0<ℵ1<ℵ2<ℵ3 还有一个问题，即连续统假设问题：阿列夫0与阿列夫1之间是否存在其它的无穷大，康托认为这样的无穷大不存在。什么叫连续统问题，因为阿列夫0是无穷大，阿列夫1是无穷大，阿列夫1是否紧挨阿列夫0，如果不存在其它无穷大，相当于阿列夫在此处连续。著名数学家希尔伯特曾经号召全世界的数学家来解决一些数学难题，连续统假设就是其中一个，结果是在公理体系中连续统假设既不能被证明，又不能被否定，这个问题涉及到数学的基础问题，引发了后人对公理系统的进一步探讨。 参考文献 [1]张家龙.数理逻辑发展史——从莱布尼茨到歌德尔[M].北京:社会科学文献出版社,2003. [2]王朝阳.离散数学[M].徐州:中国矿业大学出版社,2001. 摘要：为了激发学生的学习热情，培养其思维能力和应用能力，根据离散数学课程教学的特点，笔者结合课程教学经验，对离散数学教学进行了研究.文章提出一些教学方法和手段的改革，在实际教学中起到了一定的作用，提高了教学质量. 关键词： 离散数学，教学方法，教学手段 【中图分类号】O158-4 On the Teaching "Discrete Mathematics" in Chenxue Gang Zhou Jiquan （North China Electric Power University Mathematics， Beijing， 102206， China） Abstract： In order to stimulate students' enthusiasm for learning， develop their thinking skills and ability， according to the characteristics of Discrete Mathematics Instruction， author of Teaching experience， discrete mathematics teaching were studied. This paper presents some of the reform of teaching methods and means， in the actual teaching has played a certain role in enhancing the quality of teaching. Keywords： discrete mathematics， teaching methods， teaching means 《离散数学》是计算机科学中重要的基础理论课程之一，它不仅是许多计算机专业课的必备基础，而且对培养学生抽象思维能力和逻辑推理能力有着重要的作用.然而采用以往的教学方法，教学效果往往不够理想.一方面，离散数学知识的分散性令许多学生感到无从下手.另一方面，在传统的离散数学教学中，往往采用“纯数学”教学方法，学生不能很好地体会离散数学对计算机科学的重要意义，所以学习积极性不高.因此，通过教学方法和手段的改革来激发和增强学生的学习兴趣，从而培养学生的创新思维和综合能力，是离散数学教学中非常迫切的需求.本文结合作者近年来从事离散数学课程教学的经验，从教学内容、教学方法、教学手段等方面进行了一些初步探讨. 1精选教学内容 《离散数学》教学内容主要包括数理逻辑、集合论、代数结构及图论等几大分支.各分支均有悠久历史.如果这几部分的内容都要详细讲授，时间上来不及，所以在在教学过程中对讲授内容的选择应当有所侧重.比如简单介绍集合论的理论基础，重点是如何利用集台论的方法解决实际应用问题.在二元关系这部分，重点是二元关系的几个与性质相关问题的论证方法的训练.在数理逻辑上通过将一般命题公式和一阶逻辑公式化成范式，达到强化训练学生逻辑演算能力.图论部分重点放在基本概念的理解和实际问题的处理上，通过对相关定理及其证明思路的理解来体会图论的研究方法.代数系统这部分内容重点放在群论上，尤其要在代数系统、群、子群、循环群、变换群、正规子群的概念及相关问题的理解上下功夫. 2 教学方法探讨 2.1 增加讨论课 老师首先选定讨论的课题，学生分组准备查询相关的文献，并形成自己观点.在讨论课上大家共同交流探讨，从而加深对这门课程的认识.最后各小组完成论文的书写.该方法不仅可以提高学生对离散数学重要性的认识，还可以提高学生互相协作的能力以及书写论文的能力. 2.2 增加趣味性，激发学生的学习兴趣. “兴趣是 最好的老师”，只有激发起学生的学习兴趣，他们才有真正自主学习的欲望.在教学过程中，根据具体的知识点，介绍它的发展史或者引入趣味问题，增加了学生学习离散数学的兴趣，拓宽了学生们的知识面，提高了学生对离散数学课程学习的积极性与主动性. 2.3 注重归纳与小结 离散数学的内容虽然多且散，但通过归纳和小结，可以用一条主线贯穿始终.离散数学讨论的内容主要包含系统中涉及到的静态（基本概念）与动态（运算、操作、推理）.如集合论中是元素（静态）及其上的运算（动态）；代数系统中是集合（静态）及运算（动态）；数理逻辑中是公式（静态）和推理（动态）.通过归纳与小结，学生能够理清头绪，提高学习效率. 3 教学手段改革 3.1 教学网站建设 信息技术对提高教学质量具有重要的影响，必须予以高度重视.为了提高教学质量，我们建设了一个教学支撑网站，一方面大力推进信息技术在教学中的实际运用，促进教学手段和教学方法现代化；另一方面以此提高教与学的效率. 3.2 重视学生作业，定时测验 离散数学的知识不经过学生的独立思考和多做练习是无法牢固掌握的，因此一定要给学生留一定数量的课后习题.但大部分学生不可能把课本上的习题全部做完，教师也不可能完全批阅.这就要求教师布置作业要选其精华，选题必须要有一定的深度和广度，要覆盖所学的内容，尽量选有启发性质的习题.对于学生的作业，要认真仔细批改，将作业中暴露出来的普遍问题，要进行课堂讲评.通过讲评作业，帮助学生澄清模糊和错误的认识. 3.3 新的考核方式 传统的考核方法就是试卷考试，考察学生的基本知识和基本技能，以及解难题的能力.我们尝试做了一些考核方法的改革，把原来的试卷考试和平时的考核两部分，改成了三部分成绩的统一， 即添加了一个新的内容：写离散数学的论文.把它的评定结果作为成绩的一个重要部分.所写论文必须要求观点明确、主题鲜明和论述严谨，并且具有一定的创新. 4 结束语 总之，要把离散数学这一门课教好，教师就要不断研究新的教学方法和手段，认真掌握教学规律，借助于现代化教学手段，提倡“启发”式教学.教师只要具有扎实的理论功底，并具有对学生高度负责的精神，就一定能够达到良好的教学效果. 参考文献： [1]赵青杉，孟国艳.关于离散数学教学改革的思考[J].忻州師范学院学报，2005，21（5）：6 . [2]耿素云，屈婉玲.离散数学[M].北京：高等教育出版社，2001. [3]翁梅，刘倩，冯志慧等.“离散数学”课程教学实践与探索[J].计算机教育，2004（12）：62—63. [4]钟敏，时念云.改革课程实验提高离散数学教学质量 [J].计算机教育，2008，18. [5] 张艳华，周雪琴，马新娟，王举辉，张立红. 基于卓越工程师的“离散数学”教学改革探索[J]. 当代教育理论与实践. 2013（12） 【离散数学课程设计论文】推荐阅读： 离散数学期末复习07-17 离散数学模拟试题06-09 离散数学作业答案一06-15 关于离散数学的问题07-19 离散数学考试试题09-11 离散数学自学考试10-12 离散数学第三章总结10-28 离散数学图论练习题11-26 《离散型随机变量及其分布列》数学教学反思07-05 浅谈新课程下高中数学的教学设计论文06-16离散数学复习重点 篇6
离散数学课程设计论文 篇7
浅谈《离散数学》的教学 篇8
