离散数学教学研究
摘要: 离散数学是计算机专业的重要基础课,是学生将来从事理论研究、应用开发、技术管理的理论基础,它在计算机科学及相关的电子通信领域中有广泛的应用,因此,通过激发学生的学习兴趣、优化教学内容、改革教学方法、利用先进的教学手段等措施,提高离散数学的教学质量,对学生后续课程的学习以及进行相关的科学研究具有重要意义。
关键词: 离散数学;教学内容;教学手段;教学方法
0 引言
计算机科学技术的飞速发展对社会的各个领域产生了广泛而深刻的影响。离散数学在计算机科学与技术中的地位,就像微积分在物理学和工程技术中的地位一样为计算机科学技术的发展奠定了坚实的数学基础。
离散数学是为计算机、信息管理、电子通信等专业的学生开设的课程,它的基本思想、概念和方法渗透到计算机相关专业的各个领域,它的基本理论和研究成果深刻地影响并推动着计算机科学和技术的发展。
学习离散数学,有利于培养学生抽象思维能力、逻辑推理能力、分析判断能力和归纳总结能力。该课程中的概念多、理论性强、内容抽象,这使得教师的教学和学生的学习都有一些吃力。因此,要协调好教与学的关系,提高教学质量,就需要从培养学生兴趣入手,对教学内容、教学方法、教学手段等方面进行改进。
1 培养学习兴趣,调动学习积极性
计算机科学的发展与离散数学的数理逻辑、抽象代数和图论等有密切的联系。在学习离散数学时,学生可能看不到它在计算机科学中的具体应用,因而学习兴趣不高,学习效果不理想。所以在上第一堂课时,教师就要给学生讲离散数学的在相关学科中的应用,培养学生的学习兴趣。
另外,在教学中要有意识地引导学生应用所学理论,让学生知道这些理论是“有用的”。例如,在讲根树时,可以将根树与计算机通讯联系起来,讲解如何利用一棵最优树产生一个最佳前缀码[1],使得在传输信息时,能够既准确又节省二进制位,这样学生就了解了最优树在计算机通讯中的作用,从而培养了学习兴趣,并进一步加强了“应用数学”的能力。
2 教学内容的优化
离散数学包括:数理逻辑、集合论、代数系统、图论四大部分,教学内容多而教学课时偏少,所以在教学中对课程内容应有所侧重:
1)集合论的内容只需简要介绍,可以让学生自学一部分,然后老师提出问题,引导学生思考,重点应放在利用集合论解决实际问题上;
2)二元关系的重点是二元关系的五个性质以及相关论证方法、等价关系和偏序关系的原理及应用;
3)数理逻辑中,着重讲解一阶逻辑的范式,强化学生的逻辑演算能力,提高逻辑推理能力;
4)图论部分,在掌握基本概念的基础上,要多与实际问题联系,通过理解定理证明的思路来掌握图论的研究方法及应用;
5)代数系统的重点是群论,要理解并区分代数系统、群、子群、循环群、变换群、正规子群等,要掌握同构和同态的概念及应用,对于其它的代数系统如环、域、格以及布尔代数则可以通过类比法略讲。
在教学过程中,也应补充一些离散数学中的理论在计算机科学中应用的知识点,使学生了解其实用性,增强学习兴趣,进行主动学习。
3 教学方法实践
3.1 理解与研究
离散数学中有很多概念、定理和规则,很多学生习惯用背诵的方式来掌握,容易产生枯燥感。所以在教学中,要教会学生完整理解问题,很多的概念、定理只需理解,就能掌握。如,一阶逻辑中有八个关于量词作用域的扩张与收缩公式,学生刚开始看到这些公式时,可能觉得难记,先要讲证明方法,让学生掌握公式的推导,然后通过对比,记牢公式。实际上这些公式中只有以下两个公式是需要转换量词[2]的:
x(A(x)B)xA(x)B (1)
x(A(x)B)xA(x)B (2)
可以在有限个体域中,利用量词消去法证明其中一个公式,其它的公式留作课后作业,引导学生进行研究性的学习,以加深对公式的理解记忆。
3.2 联系与启发
离散数学的内容难度大且枯燥,特别是课程的结构比较散,内容杂,不易接受。因此,在讲清楚基本概念、定理、证明、计算方法的同时,要多举代表性例子,加深学生的理解,并随时介绍所学知识的应用背景和发展方向,使学生认识这部分知识的作用,提高学习积极性。如在讲格的定义时,可以先回顾偏序关系中“覆盖”的定义以及哈斯图,再细讲格的定义及判别方法,温故而知新,有助于学生快速掌握新的知识点;在讲平面图时,可以给出平面图在印刷电路板、集成电路等方面的应用举例。
另外,在讲课时结合一些轻松的故事引入问题,可以减轻学习的压力,提高学习兴趣。比如,一阶逻辑中著名的苏格拉底三段论、土耳其商人和帽子的故事,图论中的哥尼斯堡七桥问题、周游世界问题、一笔画问题、地图着色问题[3]等等,对这些问题的介绍不能仅停留在故事的趣味性上,而应引导并启发学生积极思考,以便达到良好的教学效果。
4 教学手段
4.1 多媒体教学
多媒体教学具有信息量大、可重复性强、生动有趣等特点,针对离散数学定义、定理、性质多的特点,教师可以充分利用多媒体教学缩短理论教学时间,增加应用内容,同时通过对已学知识的重新展示可以唤醒学生的理解记忆,使新旧知识的过渡更加轻松自然。多媒体教学中,图文并茂有利于激发学生的学习兴趣,提高课堂教学效果;但多媒体教学也有缺点:没有具体的推导过程,学生对定理的证明过程印象不深,所以,在证明重要定理和例题的时候,要附以板书。
4.2 上好习题课
习题课是提高离散数学教学质量的重要环节,习题课不仅能能够帮助学生回顾巩固所学知识,而且也是提高性的教学环节,把每一章的主要概念和重要定理作简洁的总结,用清晰简明的框图把该章的内容联系起来,找出规律,以便于学生理解和应用。如图1:代数系统的知识点框图。
在每章讲完后,都要安排一次习题课,可以采用课堂讨论的方式进行,所选择的习题数量不能太多,要具有综合性、典型性、实际应用性等特点,有一定的深度和广度,每一个题目都要达到一定的目的,讨论要有启发性和思考性,抓住重点关键的问题进行讨论,分析问题的实质。通过习题让学生运用所学知识解决实际问题,提高分析问题、解决问题的能力。
5 总结
图1代数系统知识点框图
综上所述,在离散数学的教学中,首先要让学生了解课程的重要性,培养学生的学习兴趣,教师要提炼优化教学内容、根据学生的学习特点进行启发引导,同时采用先进的教学手段,科学地开发多媒体课件,最后通过习题课帮助学生巩固提高所学知识,提高分析问题、解决问题的能力,很好地完成教学任务。
参考文献:
[1]屈婉玲、耿素云等,离散数学,北京:清华大学出版社,2008.
[2]左孝凌等,离散数学,上海:上海科学技术文献出版社,2006.
[3]邵学才、叶秀明,离散数学,北京:清华大学出版社,2008.
作者简介:
汤丽平(1972-),女,汉族,山东威海人,工学博士,浙江工业大学信息学院讲师。
作者：汤丽平 柴婉芳 汤健斌 杨俊洁
摘要：“离散数学”是计算机和信息类专业中一门重要的专业基础课程，在分析当前数学文化融入离散数学教学现状的基础上，结合离散数学教学实践，从融入的前提、融入的方式和融入度的把握等方面，对课堂教学中如何充分融入数学文化进行探讨。
关键词：离散数学;数学文化;教学改革
离散数学是高等院校信息与计算机专业的一门重要的基础理论课，无论是对学习专业的后继课程，还是对以后参加工作，都具有重要的意义。然而，离散数学课程的高度抽象性和极强的理论性使得许多学生对该课程望而却步，但又不得不学，只好敷衍了事，学习态度极为消极。因此，许多专家学者对该课程的教学进行了积极的探索，提出了不少的方法和措施，如改编教材、改革教学方式和教学手段，等等。笔者在教学实践中，积极探讨如何将数学文化渗透到教学中去，取得了较好的效果。
1数学文化融入离散数学教学的意义
数学文化是人类文化的重要组成部分,也是推动社会发展的动力。学习数学文化有着十分重要意义，通过数学文化的学习，不仅能使我们对数学发展的来龙去脉有一个系统地了解，而且还可以了解和掌握伟大数学家解决问题的方法和思想，了解数学家在追求真理过程中体现出的坚强意志和精神，了解数学思想、数学理性精神在人类社会发展过程中所起的重要作用，同时提高了学生的数学素养以及做人做学问的品格。
离散数学作为一门重要的基础理论课程，它不仅具有数学学科所具有的高度的抽象性，极强的理论性，而且内容较多，涵盖数理逻辑、集合论、代数系统、图论等领域[1]前言，每部分内容都有大量的概念和结论需要理解和掌握，再加之课时紧张，致使教师在授课时基本采取满堂灌的教学方式，无法调动学生学习的积极性。
而数学文化的渗透和穿插，使得学生了解到高度抽象性数学内容后面，存在着一个丰富多彩，奇异美妙的数学文化世界，从而可以激发学生学习的兴趣。再者，与离散数学知识相关联的数学文化内容千姿百态，如何选取、穿插、讲解才能将数学文化渗透到离散数学教学中去?采用何种教学方式才能取得更好的教学效果?如何展示才能让学生更好地了解那奇妙的数学世界和数学人物?这都要求教师要掌握和熟悉与离散数学知识相关的数学文化知识，促使教师不断提高自身的数学休养。
2数学文化融入离散数学教学的实践
2.1教学状况
针对当前离散数学教学中存在的诸多问题，许多专家学者对离散数学教学进行了多方面的尝试，比如，针对不同专业进行有目的的教学改革[2-3]，结合我国著名教育家孔子的思想进行教学[4]，改进教学方式和教学手段[5-6]，优化教学内容，提高教学水平和质量[7-8]，结合应用示例进行教学[9]，等等。与此同时，笔者查阅了《离散数学》(左孝凌等著)、《离散数学教程》(耿素云等著)、《离散数学导论》(徐洁磐著)等25本国内出版的离散数学教材，内容都未提及相关数学家和计算机专家的数学历史背景。
笔者认为，将数学文化融入到离散数学教学的路还很漫长，原因是，许多一线教师和专家学者对数学文化并不重视，甚至没有想过把数学文化融入到离散数学教学中去;另一个原因是，大多数一线教师对数学文化并不了解，或者了解甚少，当然也无法将数学文化融入到离散数学教学中去。
2.2融入的前提——提高教师的数学文化素养
数学文化不仅仅包含一串串抽象的数学概念和定理，还包括伟大的数学思想和方法，数学问题及其形成与发展，数学家进行艰苦创作的过程以及数学家的故事，等等。因此，教师在离散数学教学中贯穿数学文化，自己必须拥有扎实的数学功底，而且要掌握诸如数理逻辑、集合论、图论、代数学等相关数学领域的发展史和思想史，以及其他数学领域丰富的数学文化知识，只有在此基础上，才能在离散数学教学中，根据讲解的概念、方法、结论和定理，随时渗透数学史和数学文化的内容。所以，教师要在平时工作和学习中，厚积薄发，通过不断积累相关数学文化知识，不断提高自身的数学文化素养，才能在离散数学教学中随心所欲地插入相关数学文化知识，做到得心应手。
2.3融入的方式——课堂教学
在课堂教学中可以采用多种方式融入数学文化，提高学生学习的兴趣和学习效率。
2.3.1讲解数学概念时融入数学文化
离散数学中概念极多，如何讲好概念是离散数学教学成功的关键之一。我们在教学中结合数学文化和数学史，强化数学概念的相关历史背景，适时地将概念的来龙去脉展示给学生，使他们从中受到启发，理解更加深刻。
例如，函数是一个非常重要的概念，如何让学生掌握函数的本质，我们结合函数概念的产生发展历史向学生介绍函数的概念。首先，介绍函数概念的发展历史[10];其次，将函数的这些定义进行分类总结，可以大概分为变量说、对应说、关系说三种类型;第三，将这些概念与教材[1]147—155中函数的概念和关系的概念进行对比。通过这样一堂课，学生不仅对整个函数概念的发展历史有了一个全面的认识，也对初高中及大学数学课程中涉及函数的相关知识有了一个深刻的理解和掌握。
再如，“树”的概念是图论的基本概念之一，它不仅对学生继续学习图论的相关理论知识十分重要，而且在实现二叉搜索树、决策树、排序等相关算法过程中也起着重要的作用。因此，帮助学生深刻理解树的概念显得十分重要。事实上，“树”的例子非常多，而我们在教学中列举的关于贝努利家族中数学家 [11]的一个例子(见图1)，不仅从数学文化历史背景方面给学生一个冲击，而且使得学生通过了解贝努利家族中众多数学家，从而牢牢地记住并彻底地理解了“树”的概念。
2.3.2讲解数学命题时融入数学文化
数学问题是数学的心脏，是数学发展的动力，因此整个数学发展史实际上就是解决问题的历史。因此，如何将离散数学中涉及的相关问题的产生、发展、解决的历史与教学结合起来，是特别值得探索的。
比如，图论部分的概念和结论繁多，学生稍有不慎就会出错，因此，如果按照图论的基本概念和结论，抽象地进行讲解，学生不但毫无兴趣，而且极其容易出错。但是，图论中有名的数学问题很多，如哥尼斯堡七桥问题、周游世界问题、四色猜想等，都可以用来作为数学文化的内容融入到教学中去，学生对相关的概念和结论理解就会更加非常深刻。
再如，“五次及五次以上方程根式解”问题是数学历史上一个非常有名的问题[12]，离散数学代数系统中的群论内容就是随着该问题解决而诞生的。而群论内容一直都是教师教学中最为头痛的内容之一，同时大部分学生面对这些内容时也表现得力不从心，并对教师的讲解表示不知所云，甚至出现抵触这部分内容的情况，然而该部分内容却又在计算机科学中有着广泛的应用。为此，我们在教学中把“五次及五次以上方程根式解”问题的历史发展与群论及代数系统内容的教学相结合，收到了意想不到的教学效果。
首先从简单的一元一次、二次方程的根式解讲起，然后给出稍微复杂的一元三次、四次方程的根式解，最后提出一元n(n≥5)次方程是否存在根式解问题。学生对此非常感兴趣。面对学生的热情，我们首先介绍了挪威天才数学家阿贝尔(N.H.Abel，1802—1829)证明五次及五次以上方程根式解不存在的工作，以及阿贝尔虽然贫困但对数学锲而不舍地追求的人生经历。就在学生不时感叹时，我们马上提出了一个新的问题：什么样的特殊方程能够用根式来求解呢?当我们介绍到这个问题被死时不到21岁的极具传奇色彩的法国天才数学家伽罗瓦(E.Galois，1811—1832)所解决时，所有学生都惊呆了，并一致表示愿意了解这位数学家所作的工作。为了帮助学生了解，我们以四次方程x4+px2+q=0为例，向学生简单地介绍了置换以及置换乘积等概念，而四次方程的四个根共有24个可能的置换，它们构成一个集合，这个集合连同置换乘积就构成了一个代数系统，这就是伽罗瓦给出的历史上第一个“群”的定义。而伽罗瓦进一步考虑了这24个置换中的8个特殊的置换，它们也构成了一个“群”即“伽罗瓦群”，伽罗瓦证明了“伽罗瓦群”满足一定条件时，方程才是根式可解的。后来，数学家陆续发现矩阵在乘法下构成群，四元数在加法下构成群，而后又有数学家提出无限变换群，等等。到了19世纪80年代，数学家对这些具体的群进行抽象，从而出现了我们现在教材中让学生接受起来感到非常困难的“群”的概念。在了解了“群”概念产生的历史背景基础上，许多学生表示没有想到这么抽象的概念背后竟有如此丰富的数学文化历史背景，也使得许多学生在学习群及代数系统的相关概念和内容过程中表现得十分积极主动。
当然，其他部分内容也有非常有名的问题可供我们使用，比如，集合论部分的连续统假设问题，自然数集与整数集、有理数集、实数集孰多孰少问题。
2.3.3教学内容融入数学文化
无论数理逻辑和代数系统的内容，还是图论和集合论的知识，大部分内容都是非常抽象的，如何在抽象的内容中融入数学文化，是数学文化融入离散数学教学改革的重中之重，也是教学改革的成败之所在，因此，也是最值得去研究、探讨、设计和实践的。
比如，在讲解基数概念及其相关内容时，我们首先结合两个故事来引导学生理解和掌握基数概念的内涵。第一个故事是[13]，伽利略(Galileo Galilei，1564—1642)在《关于两种新科学的对话》中借用两个人的谈话，谈论到自然数和它的平方数之间可以建立一一对应关系，但明显地是，所有自然数的个数是无限的，平方数的数目是无限的，……平方数的数目既不少于自然数的总数，而后者也不多于前者。第二个故事是希尔伯特旅馆问题[14]。实际上，这两个例子都在说明，在承认实无穷的情况下，若两个无穷集合之间能够建立一一对应关系，则就认为两个无穷集合所含元素个数一样多，并将其元素个数用一个符号来表示，则这个符号就表示这两个无穷集合的基数，当集合是有限集合时，该定义同样适用。然后，将极具传奇色彩的德国著名数学家康托(G.Cantor，1845—1918)的生平事迹和他所做的涉及基数的工作做了一个较为详细地介绍，不仅包括基数概念，还包括可数集合与不可数集合，基数的比较等内容。这些讲解不仅激起了学生强烈的好奇心和求知欲，而且使得学生对康托的工作及取得成就也非常感兴趣。学生正是在为康托的遭遇感到愤愤不平，又为他对数学的执着追求而深受感动的这种氛围中，了解了相关的数学历史背景，也顺利轻松地完成了教学任务。
2.4融入的分寸——融入度问题
“增之一分则太长，减之一分则太短;著粉则太白，施朱则太赤”。如何使用数学文化来为离散数学教学上妆，把握数学文化融入到离散数学教学中去的“度”的问题，实属非易。讲得太少，对学生理解相关内容帮助不大;讲得太过，冲谈了讲课的主题，容易分散学生的注意力，从而不能完成相应的教学任务。
这就需要教师，在把数学文化融入到离散数学教学中时，一定要清醒地认识到，数学文化是一个工具，数学文化的融入在教学中就像做饭添加佐料一样，其目的是让学生在吃离散数学这道大餐时感到更加美味可口。因此教师应该有目的地再现数学历史情景，帮助学生理解和掌握学生的思想和方法，促进学生对所讲授知识的掌握。切记，不可过分渲染，应该自然引出，否则会导致本末倒置，有喧宾夺主之嫌。
3教学效果
笔者在离散数学教学中，坚持将数学文化内容融入到离散数学中去，受到学生的欢迎，取得了非常好的效果。笔者曾对计算机科学技术和网络技术两个方向的两届学生做了一个调查，共有403名学生参加了调查，回收396份调查问卷，结果是387名学生认为穿插数学文化知识对教学效果有积极影响，有300名学生认为介绍的数学文化知识太少，应该加大力度。
参考文献：
[1] 左孝凌,李为鑑,刘永才. 离散数学[M]. 上海:上海科学技术文献出版社,1982.
[2] 徐洁磐. 应用型计算机本科中离散数学课程目标定位与课程改革的探讨[J]. 计算机教育,2010(5):6-9.
[3] 梁吉业,李德玉,吕国英. 服务计算学科的“离散数学”教学方法探讨[J]. 高等理科教育,2009(5):130-132.
[4] 刘冬明. 孔子的教学思想在离散数学中的应用[J]. 计算机教育,2010(6):112-114.
[5] 崔艳荣,陈勇,黄艳娟. 离散数学教学方法与手段探究[J]. 长江大学学报,2009,6(2):373-374.
[6] 徐凤生. “离散数学”课程的教学改革与实践[J]. 高等理科教育,2009(3):44-47.
[7] 廖辉传. 浅谈“离散数学”教学方法与实践[J]. 华东交通大学学报,2006,23(12):149-151.
[8] 文海英,廖瑞华,魏大宽. 离散数学课程教学改革探索与实践[J].计算机教育,2010(6):100-103.
[9] 牛连强,陈欣,邓金鹏. 小议“离散数学"课程中的应用示例与教学[J].高等理科教育,2008(3):35-38.
[10] Dieter Ruthing. 函数概念的一些定义：从Joh. Bernoulli到N.Bourbaki[J].数学译林,1986,5(3):260-263.
[11] E.T.贝尔. 数学大师：从芝诺到庞加莱[M]. 徐源,译.上海:上海科技教育出版社,2004:157-165.
[12] 李文林. 数学史概论[M]. 2版. 北京:高等教育出版社,2002:208-213.
[13] 张顺燕. 数学的源与流[M]. 2版.北京:高等教育出版社,2003:31-33.
[14] G.伽莫夫. 从一到无穷大[M]. 修订版. 暴永宁,译. 北京:科学出版社,2002:14-15.
Research on Infusing Mathematical Culture into Discrete Mathematics Teaching
LIU Weifeng, LIU Lin, WANG Dongxiao, JIANG Ling
(Department of Mathematics and Physics, Zhengzhou Institute of Aeronautical Industry Management, Zhengzhou 450015, China)
Key words: Discrete Mathematics; mathematics culture; teaching reform;
(编辑：彭远红)
作者：刘卫锋,刘林,王东晓,姜凌
摘要：“离散数学”作为计算机专业基础课，它的实践环节往往被忽略。本文对于实践环节的设计、分析、问题及其解决方案进行了研究和实践，获得了感性和理性的理解和认识。
关键词：离散数学;实验;课程安排
“离散数学”作为计算机专业很重要的一门基础课，对于后续课程，如数据结构，数据库原理，编译等课程起到直接的影响，同时对培养学生的逻辑思维能力，抽象思维能力，探讨前沿领域都起着非常重要的作用。根据我校离散数学教学的多年教学，我们在“离散数学”教学的环节中增加了实践环节，考虑课时安排问题，基本都是以课后作业的形式安排，但是在考核中增加分值，以调动学生的积极性。
1“离散数学”实验内容的设计
“离散数学”课程按传统的教学，共分四个部分，数理逻辑，集合论，代数系统，图论。我们共计按两个学期开设课程，每个学期54学时。在第一学期讲授前两部分，第二学期讲授后两部分。根据实际情况，我们设计了如下的实践题目，见表1和表2。
根据学时，我们的实验大部分都安排在业余时间进行。教师利用QQ群等工具进行答疑辅导，我们感觉到学生如果发现老师和他们一样能够使用现代的网络工具，那么他们和老师之间的距离无形中被缩小了。
在实验题目的安排上我们力求精炼，体现课程的难点，增加学生理解的最大化。在实验的组织上，我们采用分组进行，组长负责制，采用小组软件工程的要求，填写实验日志。在实验的指导上，教师利用投影分析流程，训练流程图的使用。在编程语言上我们不加要求，学生可以使用C，C++，Java等。事实表明，由于我们学校在前一学期学习了C语言，所以大多数同学使用C，也有个别同学使用了自学的GUI语言，比如JBuilder等。在实验组的形式上，学生可以给自己的组自由命名，有的组居然命名为“微软第二小组”。通过这个命名，学生的集体意识明显增强了。
对于实验的梯度问题，很多同学的分析能力和解决问题的能力很弱，针对这种情况，我们采取了互相帮助的原则，如果哪个同学对于该组的题目内容无法讲解清楚，无法说明每个人所做的工作，那么一票否决制。这样，即使那些不会编程的同学，也通过这个过程熟悉了如何提出和解决问题。
2实验效果的反馈与评价
在最开始进行实验活动的时候，很多同学不理解，也无法按时完成任务，但是我们对那些完成任务的同学给予及时的鼓励，给予加分奖励，不知不觉中，他们也接受了“自己也应该去完成这样的任务，也应该能够完成任务”的思想，思想一旦启动了，行动就顺理成章的进行了。因此我们感觉，必须让学生从思想上意识到问题的重要性。
通过实验后，学生普遍的感受都是收获很大，无论是在题目的和语言编程上，还是在团队的战斗过程中。在实验后，他们增加了战胜下一个题目的信心，增加了彼此的了解，彼此的信任，取长补短。在2005级同学的实验数据如图1。
我们的评价指标主要包括如下几个方面(1)问题分析透彻，分析报告完整。(2)程序编写的思路清晰，代码编写的规范(3)小组的讨论记录，见图2。
优秀人数的比例大约占到总人数的3-25%之间，良好在40-50%之间。我们从来不吝啬赞美之辞，使得广大同学的积极性非常高涨。
3存在的问题和解决的思路
经过几年的实践，我们发现了如下几个问题：
(1) 学生水平参差不齐，选择计算机专业学习就是要把它放到一定的高度上，有兴趣的同学经常看课外书，经常问老师问题，思考能力明显增强，但是还有很多同学，选择计算机学习后又后悔了，以为计算机就是打打字，使用应用软件那么简单。针对这种情况，我们从职业化和就业的高度教育同学，告诫他们既选择之，就要奋斗之。鼓励而不是消极的讽刺。
(2) 语言基础不够扎实。在学习语言的时候，要对于基本的如数组，结构体，文件等内容有较为熟练的使用。我们的大多数同学都需要翻阅上个学期学习的语言教材，有很多同学甚至都看不懂上个学期学习的内容了。针对这种情况我们专门组织了学习比较好的同学做几次辅导讲座，一方面使讲座同学系统的整理一下，又使其他同学温习了相关知识，向学习好的同学看齐，差距是前进的动力。同时我们和负责语言教学的老师进行沟通，适当加强某些环节课程的教学。
总之，通过几年的实践教学，我们感觉到学生们通过自己的努力，在教师的辅导下，获得了学习的乐趣，增长了学习的动力，提高了学习的自主性。
作者：姜春茂 黄春梅
华南理工大学网络教育学院 2014–2015学第一学期 《 离散数学 》作业 (解答必须手写体上传，否则酌情扣分)
1.设命题公式为 Q (P Q) P。
(1)求此命题公式的真值表; (2)求此命题公式的析取范式; (3)判断该命题公式的类型。
2.用直接证法证明
前提：P Q，P R，Q S 结论：S R
《 离散数学作业 》 第 1 页 (共 7 页)
3.在一阶逻辑中构造下面推理的证明
每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。
《 离散数学作业 》 第 2 页 (共 7 页)
4.用直接证法证明：
前提：(x)(C(x)→ W(x)∧R(x))，(x)(C(x)∧Q(x)) 结论：(x)(Q(x)∧R(x))。
《 离散数学作业 》 第 3 页 (共 7 页)
5.设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。
(1) 给出关系R; (2) 给出COV A
(3) 画出关系R的哈斯图;
(4) 给出关系R的极大、极小元、最大、最小元。
《 离散数学作业 》 第 4 页 (共 7 页)
6.求带权图G的最小生成树，并计算它的权值。
7.给定权为1，9，4，7，3;构造一颗最优二叉树。
《 离散数学作业 》 第 5 页 (共 7 页)
8.给定权为2，6，3，9，4;构造一颗最优二叉树。
9、给定权为2，6，5，9，4，1;构造一颗最优二叉树。
10、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%,b:25%,c:20%，d:10%,e:10%,f:5%。试给出传输这6个字母的最佳前缀码?问传输1000个字符需要多少位二进制位?
《 离散数学作业 》 第 6 页 (共 7 页)
《 离散数学作业 》 第 7 页 (共 7 页)
华南理工大学网络教育学院 2014–2015学第一学期 《 离散数学 》作业 (解答必须手写体上传，否则酌情扣分)
1.设命题公式为 Q (P Q) P。
(1)求此命题公式的真值表; (2)求此命题公式的析取范式; (3)判断该命题公式的类型。
2.用直接证法证明
前提：P Q，P R，Q S 结论：S R
3.在一阶逻辑中构造下面推理的证明
每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 4.用直接证法证明：
前提：(x)(C(x)→ W(x)∧R(x))，(x)(C(x)∧Q(x)) 结论：(x)(Q(x)∧R(x))。
5.设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。
(1) 给出关系R; (2) 给出COV A
(3) 画出关系R的哈斯图;
(4) 给出关系R的极大、极小元、最大、最小元。
6.求带权图G的最小生成树，并计算它的权值。
《 离散数学作业 》 第 1 页 (共 2 页)
7.给定权为1，9，4，7，3;构造一颗最优二叉树。
8.给定权为2，6，3，9，4;构造一颗最优二叉树。
9、给定权为2，6，5，9，4，1;构造一颗最优二叉树。
10、设字母a,b,c,d,e,f在通讯中出现的频率为：a:30%,b:25%,c:20%，d:10%,e:10%,f:5%。试给出传输这6个字母的最佳前缀码?问传输1000个字符需要多少位二进制位?
《 离散数学作业 》 第 2 页 (共 2 页)
离散数学作业题
第一章 命题逻辑
p38 习题一
1、2(1)(3)、3(1)(4)、4(2)(3)、6(2)、7(4)(6)、8(1)(3)(5) 补充题：将PQ化成与之等价的并仅含联结词的公式。
第二章 谓词逻辑
P70 习题二
2(2)(4)、3(1)(3)、4(3)(4)、10(4) 补充题：
1. 谓词符号化：
1) 所有的鱼都生活在水中。 2) 没有大于2的偶素数。 3) 并不是每个人都聪明。
2. 设个体域D={a,b}，将一阶公式(x)(F(x)→(y)G(y))中的量词消除
3. 设个体域为整数集，令P(x,y)：x+y=1;Q(x,y)：xy>0，试求解下列命题的真假。
1) (x) (y)P(x,y).
2) (x) (y)Q(x,y).
4. 求前束范式：
1) (x)F(x)(x)R(x).
2) ((x)P(x)∨(y)Q(y))(x)R(x). 5. 证明：
前提：(x)(A(x) B(x)∧C(x))，(x)(A(x)∧D(x)) 结论：(x)(C(x)∧D(x))
6. 所有的整数均为有理数并且为实数，存在是整数又是奇数的数，因而存在是奇数又是实数的数。
写出上面推理的证明。(用谓词逻辑，写出用谓词表示的前提、结论和证明过程)
第三章 集合、关系与映射 P133 习题三：
7、
9、
11、17 补充题
1. AB，A∈B能否同时成立，说明原因
求集合A={a，{a}}的幂集
2. 证明：若BC，则P(B) P(C) 3. 如果A∪B=A∪C，是否有B=C?
如果A⊕B=A⊕C，是否有B=C?
4. 试求1到10000之间不能被4，5或6整除的整数个数. 5. 列出所有从A={a,b,c}到B={s}的关系，并指出集合A上的恒等关系和从A到B的全域关系. 5. 给出A上的关系及其关系图和矩阵表示.{|0≤x-y<3} A={0，1，2，3，4}
6. 已知S={a,b}. R ={〈x,y〉|x,y∈A∧xy∧A为集合族ρ(S)}.试写出关系R. 7. 已知： A={a,b,c}, R={〈a,b〉,〈a,c〉,〈b,c〉}该关系具有什么性质?
(自反，反自反，对称，反对称，传递性) 8.设A={a,b,c},R={〈a,b〉,〈a,c〉} 计算：r(R)，sr(R)，tr(R)，str(R). 9. 设A是含有4个元素的集合，试求：
(1)在A上可以定义多少种对称关系?
(2)在A上可以定义多少种既是自反的，又是对称的关系?
(3)在A上可以定义多少种既不是自反的，也不是反自反的二元关系?
10. 设集合A={0，1，2，3，4}. R={|x+y=4,x,y∈A} ，S={|y-x=1,x,y∈A}.
试求：R◦S，R◦R，(R◦S)◦R，R◦(S◦R). 11. 证明：R是A上的传递关系R◦RR. 12. A={1,2,3,4,5},R={|x,y∈A∧x-y可被2整除}，试问R是否是A上的等价关系?如果是，求出R的各等价类. 13. A={1,2,3,4,5},A上的划分∏={{1,2},{3,4},{5}}，给出由∏所诱导出的A上的等价关系R的集合表达式. 14. 试给出一个单射但非满射的函数.(对某一集合而言) 15. 设f：N→N×N，f(n)=,则：
(1)说明f是否为单射和满射，并说明理由.
(2) f的反函数是否存在?并说明理由.
(3)求ranf.
16. 已知如果从无限集合A到集合B存在单射f，则B也是无限集合。
设X是无限集合，集合Y≠φ，证明：X与Y的笛卡儿积X×Y是无限集合。
第六章 代数结构
P247 习题六：4(1)(3)、
6、
16、21 补充题：
1. 以下集合和运算是否构成代数系统?如果构成，说明该系统是否满足结合律、交换律?求出该运算的幺元、零元和所有可逆元素的逆元. 1) P(B)关于对称差运算⊕，其中P(B)为幂集.
2) A={a,b,c}，*运算如下表所示：
2. 设集合A={a,b}，那么(1)在A上可以定义多少不同的二元运算?(2)在A上可以定义多少不同的具有交换律的二元运算?
3. 设A={1,2},B是A上的等价关系的集合. 1) 列出B的元素.
2) 给出代数系统V=的运算表. 3) 求出V的幺元、零元和所有可逆元素的逆元. 4) 说明V是否为半群、独异点和群?
4. 设A={a,b,c}，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律. 1) 给出关于*运算的一个运算表.
其中表中?位置可以是a、b、c。 2) *运算是否满足结合律，为什么? 5. 设是一个代数系统。
*是R上的一个二元运算，使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+a·b(·和+为数集上的乘法和加法).
证明：: 是独异点. 6. 如果是半群，且*是可交换的.
证明：如果S中有元素a,b,使得a*a=a和b*b=b，则(a*b)*(a*b)=a*b.
7. 设是一个群,则a,b,c∈S。
试证明： 群G中具有消去律,即成立: 如果a·b=a·c ,b·a=c·a 那么b=c. 8. 设是群，a∈G .
现定义一种新的二元运算⊙：x⊙y=x*a*y，x,y∈G .
证明：也是群 .
9. 试写出模6加法群的每个子群及其相应的左陪集. 的运算表如下所示：
10. 设A={1,2,5,10,11,22,55,110}. 1) A关于整除关系是否构成偏序集?
2) 如果构成偏序集合，画出其对应的哈斯图. 3) 如果构成偏序集，该偏序集合构成哪种格? (分配格、有界格、有补格、布尔格). 第七题
图论
P295 习题七：
2、
9、10 补充题：
1. 是否存在7阶无向简单图G，其度序列为
1、
3、
3、
4、
6、
6、7.给出相应证明. 2. 求下图的补图
3. 1)试画一个具有5个顶点的自补图
2) 是否存在具有6个顶点的自补图，试说明理由。
4. 设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等. 5. 无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。 6. 图G如下图所示：
1) 写出上图的一个生成子图.(不唯一) 2) δ(G)，κ(G)，λ(G).
3) 说明：δ(G)=min{ d(v) | vV } ;κ(G)=min{ |V’| |V’是图G的点割集} ; λ(G)=min{ |E’| |E’是图G的边割集} 7. 在什么条件下无向完全图Kn为欧拉图?
8. 证明：有割边的图不是欧拉图. 9. 证明：有割边的图不是哈密尔顿图. 10. 树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶? 11. 给出全部互不同构的4阶简单无向图的平面图形。
12. 如果G是平面图, 有n个顶点、m条边、f个面，G有k个连通分支。试利用欧拉公式证明:：n-m+f=k+1.
第一章
数学语言与证明方法
例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
由12n-3< n和归纳假设, n-3分邮资可用4分和5分邮票组 成, 再加一张4分邮票即可得到n+1分邮资, 得证结论对n+1 也成立.
第2章
命题逻辑
例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.
1 (2) 2+2=4 当且仅当 3是偶数.
0 (3) 2+2=4 当且仅当 太阳从东方升起.
1 (4) 2+2=5 当且仅当 美国位于非洲.
1 (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={ | x,yN, x+y<3}
={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>}
(2) C={ | x,yR, x2+y2=1}，其中R代表实数集合，
C是直角坐标平面上点的横、纵坐标之间的关系，
C中的所有的点恰好构成坐标平面上的单位圆.
(3)
R={ | x,y,zR, x+2y+z=3}，
R代表了空间直角坐标系中的一个平面. 例4 A={0,1}, B={1,2,3},
R1={<0,2>}, R2=A×B, R3=, R4={<0,1>},
从A到B的关系: R1, R2, R3, R4, A上的关系R3和R4.
计数：
|A|=n, |B|=m, |A×B|=nm, A×B 的子集有
个. 所以从A到B有
元关系. |A|=n, A上有
不同的二元关系. 例如 |A|=3, 则 A上有512个不同的二元关系.
例
5A={a, b, c, d}, R={,,,,}, R的关系矩阵 MR 和关系图 GR 如下：
1110100000000100例1
R={,,<{a},{d}>,}, 则
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 = {,,,}, 求R的各次幂, 分别用矩阵和关系图表示. 解 R与R2的关系矩阵分别为
0100010001 10101010102M M0001000100 0000000000
例1
A = {a, b, c}, R1, R2, R3 是 A上的关系, 其中 R1 = {,} R2 = {,,,} R3 = {}
001010010000010101000000R2自反, R3 反自反, R1既不自反也不反自反. 例2
设A={a,b,c}, R1, R2, R3和R4都是A上的关系, 其中
R1={,}，
R2={,,} R3={,}，
R4={,,} R1 对称、反对称.
R2 对称，不反对称. R3 反对称，不对称.
R4 不对称、也不反对称 例3 设A={a, b, c}, R1, R2, R3是A上的关系, 其中
R1={,}
R2={,}
R3={} R1 和 R3 是A上的传递关系, R2不是A上的传递关系. 例4
证明若 IA R ，则 R 在 A 上自反. 证
任取x,
xA IA R
因此 R 在 A 上是自反的.
例5
证明若 R=R1 , 则 R 在A上对称. 证
任取
R R 1 R
因此 R 在 A 上是对称的.
例6
证明若 R∩R1IA , 则 R 在 A 上反对称.
证
任取
R R R R 1
R∩R 1 IA x=y
因此 R 在 A 上是反对称的.
例7
证明若 R∘RR , 则 R 在 A 上传递.
证
任取，
R R R∘R R
因此 R 在 A 上是传递的.
例8 判断下图中关系的性质, 并说明理由
(1) 不自反也不反自反;对称, 不反对称;不传递. (2) 反自反, 不是自反;反对称, 不是对称;传递. (3) 自反，不是反自反;反对称，不是对称;不传递. 例1 设A={a,b,c,d}, R={,,,,}, R和 r(R), s(R), t(R)的关系图如下图所示. (1) (2) (3)
例1 设 A={1, 2, …, 8}, 如下定义 A上的关系R：
R={| x,y↔A∧x≡y (mod 3)} 其中 x≡y (mod 3) 叫做 x与y 模3相等, 即 x 除以3的余数与 y 除以3的余数相等. 不难验证R为A上的等价关系, 因为
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：
<,>R x+y = u+v， 求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>}
根据有序对的 x+y=2,3,4,5,6,7,8 将AA划分. (AA)/R={{<1,1>}, {<1,2>,<2,1>}, {<1,3>, <2,2>, <3,1>},
{<1,4>, <2,3>, <3,2>, <4,1>}, {<2,4>, <3,3>, <4,2>},
{<3,4>, <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={,,,,,,,,
}∪IA
例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
3 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=, 其中 V={v | v为多面体的面},
E={(u,v) | u,vV u与v有公共的棱 uv}. 根据假设, |V|为奇数且vV, d(v)为奇数. 这与握手定理的推论矛盾. 例5 设9阶无向图的每个顶点的度数为5或6, 证明它至少有 5个6度顶点或者至少有6个5度顶点. 证
讨论所有可能的情况. 设有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 右图有
4 个面 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(
2 数 计 生
赵 钱 孙 李 周
(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
ACEGFDBA是一条哈密顿回路,按此顺序就坐即可.
学习体会
专业：计算机 姓名：范文芳 学号： 成绩： 院校：
离散数学是计算机科学与技术专业的基础核心课程。通过本课程的学习，使学生具有现代数学的观点和方法，并初步掌握处理离散结构所必须的描述工具和方法。同时，也要培养学生抽象思维和慎密概括的能力，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为学生以后学习计算机基础理论与专业课程打下良好的基础。
学习离散数学有两项最基本的任务：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础;其二是在离散数学的学习过程中，培训自学能力、抽象思维能力和逻辑推理能力，以提高专业理论水平。因此学习离散数学对于计算机、通信等专业后续课程的学习和今后从事计算机科学等工作是至关重要的。但是由于离散数学的离散性、知识的分散性和处理问题的特殊性，使部分学生在刚刚接触离散数学时，对其中的一些概念和处理问题的方法往往感到困惑，特别是在做证明题时感到无从下手，找不到正确的解题思路。因此，对离散数学的学习方法给予适当的指导和对学习过程中遇到的一些问题分析是十分必要的。
一、认知离散数学
离散数学是计算机科学基础理论的核心课程之一，是计算机及应用、通信等专业的一门重要的基础课。它以研究量的结构和相互关系为主要目标，其研究对象一般是有限个或可数个元素，充分体现了计算机科学离散性的特点。学习离散数学的目的是为学习计算机、通信等专业各后续课程做好必要的知识准备，进一步提高抽象思维和逻辑推理的能力，为计算机的应用提供必要的描述工具和理论
基础。
1.定义和定理多
离散数学是建立在大量定义、定理之上的逻辑推理学科，因此对概念的理解是学习这门课程的核心。在学习这些概念的基础上，要特别注意概念之间的联系，而描述这些联系的实体则是大量的定理和性质。在考试中有一部分内容是考查学生对定义和定理的识记、理解和运用，因此要真正理解离散数学中所给出的每个基本概念的真正的含义。比如，命题的定义、五个基本联结词、公式的主析取范式和主合取范式、三个推理规则以及反证法;集合的五种运算的定义;关系的定义和关系的四个性质;函数(映射)和几种特殊函数(映射)的定义;图、完全图、简单图、子图、补图的定义;图中简单路、基本路的定义以及两个图同构的定义;树与最小生成树的定义。掌握和理解这些概念对于学好离散数学是至关重要的。 2. 方法性强
在离散数学的学习过程中，一定要注重和掌握离散数学处理问题的方法，在做题时，找到一个合适的解题思路和方法是极为重要的。如果知道了一道题用怎样的方法去做或证明，就能很容易地做或证出来。反之，则事倍功半。在离散数学中，虽然各种各样的题种类繁多，但每类题的解法均有规律可循。所以在听课和平时的复习中，要善于总结和归纳具有规律性的内容。在平时的讲课和复习中，老师会总结各类解题思路和方法。作为学生，首先应该熟悉并且会用这些方法，同时，还要勤于思考，对于一道题，进可能地多探讨几种解法。 3. 抽象性强
离散数学的特点是知识点集中，对抽象思维能力的要求较高。由于这些定义的抽象性，使初学者往往不能在脑海中直接建立起它们与现实世界中客观事物的联系。不管是哪本离散数学教材，都会在每一章中首先列出若干个定义和定理，接着就是这些定义和定理的直接应用，如果没有较好的抽象思维能力，学习离散数学确实具有一定的困难。因此，在离散数学的学习中，要注重抽象思维能力、逻辑推理能力的培养和训练，这种能力的培养对今后从事各种工作都是极其重要的。
在学习离散数学中所遇到的这些困难，可以通过多学、多看、认真分析讲课
中所给出的典型例题的解题过程，再加上多练，从而逐步得到解决。在此特别强调一点：深入地理解和掌握离散数学的基本概念、基本定理和结论，是学好离散数学的重要前提之一。所以，同学们要准确、全面、完整地记忆和理解所有这些基本定义和定理。 4. 内在联系性
离散数学的三大体系虽然来自于不同的学科，但是这三大体系前后贯通，形成一个有机的整体。通过认真的分析可寻找出三大部分之间知识的内在联系性和规律性。如：集合论、函数、关系和图论，其解题思路和证明方法均有相同或相似之处。
二、认知解题规范
一般来说，离散数学的考试要求分为：了解、理解和掌握。了解是能正确判别有关概念和方法;理解是能正确表达有关概念和方法的含义;掌握是在理解的基础上加以灵活应用。为了考核学生对这三部分的理解和掌握的程度，试题类型一般可分为：判断题、填空题、选择题、计算题和证明题。判断题、填空题、选择题主要涉及基本概念、基本理论、重要性质和结论、公式及其简单计算;计算题主要考核学生的基本运用技能和速度，要求写出完整的计算过程和步骤;证明题主要考查应用概念、性质、定理及重要结论进行逻辑推理的能力，要求写出严格的推理和论证过程。
学习离散数学的最大困难是它的抽象性和逻辑推理的严密性。在离散数学中，假设让你解一道题或证明一个命题，你应首先读懂题意，然后寻找解题或证明的思路和方法，当你相信已找到了解题或证明的思路和方法，你必须把它严格地写出来。一个写得很好的解题过程或证明是一系列的陈述，其中每一条陈述都是前面的陈述经过简单的推理而得到的。仔细地写解题过程或证明是很重要的，既能让读者理解它，又能保证解题过程或证明准确无误。一个好的解题过程或证明应该是条理清楚、论据充分、表述简洁的。针对这一要求，在讲课中老师会提供大量的典型例题供同学们参考和学习。
通过离散数学的学习和训练，能使同学们学会在离散数学中处理问题的一般性的规律和方法，一旦掌握了离散数学中这种处理问题的思想方法，学习和掌握离散数学的知识就不再是一件难事了。复习离散数学的整个过程可大致分为三个
阶段。
第一阶段，大量进行知识储备的阶段。
离散数学是建立在大量定义上面的逻辑推理学科。因而对概念的理解是我们学习这门学科的核心。由于这些定义非常抽象，初学者往往不能在脑海中建立起它们与现实世界中客观事物的联系。对于跨专业自学的朋友来说更是如此。这是离散数学学习中的第一个困难。因此，对于第一遍复习，我们提出一个最为重要的要求，即准确、全面、完整地记忆所有的定义和定理。具体做法可以是：在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记，直到能够全部正确地默写出来为止。无须强求一定要理解，记住并能准确复述 各定义定理是此阶段的最高要求。也不需做太多的题(甚至不做课后习题也是可以的，把例题看懂就行)，重心要放在对定义和定理的记忆上。请牢记，这是为未来的向广度和深度扩张作必要的准备。
这一过程视各人情况不同耗时约在一到两个月内。 第二阶段，深入学习，并大量做课后习题的阶段。
这是最漫长的一个阶段，耗时也很难估计，一般来说，若能熟练解出某一章75%以上的课后习题，可以考虑结束该章。
解离散数学的题，方法非常重要，如果拿到一道题，立即能够看出它所属的类型及关联的知识点，就不难选用正确的方法将其解决，反之则事倍功半。例如在命题逻辑部分，无非是这么几种题目：将自然语言表述的命题符号化，等价命题的相互转化(包括化为主合取范式与主析取范式)，以给出的若干命题为前提进行推理和证明。相应的对策也马上就可以提出来。以推理题为例，主要是利用P、T规则，加上蕴涵和等价公式表，由给定的前提出发进行推演，或根据题目特点采用真值表法、CP规则和反证法。由此可见，在平常复习中，要善于总结和归纳，仔细体会题目类型和此类题目的解题套路。如此多作练习，则即使遇到比较陌生的题也可以较快地领悟其本质，从而轻松解出。
“熟读唐诗三百首，不会做诗也会吟。”要是拿到一本习题集，从头到尾做过，甚至背会的话。那么，在考场上就会发现绝大多数题见过或似曾相识。这时，要取得较好的成绩也就不是太难的事情了。这一情况具有普遍性，对许多院校的考试都适用。
第三阶段，进行真题模拟训练，提高整体水平和综合能力的阶段。
这一阶段从第二阶段结束一直持续到考试。
除了我们使用的课本外，应尽可能地弄到报考院校的专业课历年试题。因为每个单位对该科目的侧重点毕竟有不同，从历年试题中可以获取许多有用的信息。这些历年试题此时就有了巨大的作用。
一、单项选择题(本大题共10小题，每小题2分，共20分)
1、设集合M={a，}，N ={{a}，}则MN=( )。 A、 B、{} C、{a} D、{{a}，，a}
2、设关系F={<1，a >，<2，2>，}，G={，，<1，2>}则 FG=(
)。
A、{<1，b>，<1，c>，}
B、{，，<1，b>} C、{，<1，2>}
D、{，<2，2>，<1，b>}
3、设集合H={1，2，3，4}，则H上的关系R={
。 x +y是偶数}具有(
)A、自反性、反对称性和传递性
B、反自反性、反对称性和传递性
C、反自反性、对称性和传递性
D、自反性、对称性和传递性
4、设T是一棵完全二叉树，则T的每个结点都(
)。
A、至少有两个子结点
B、至多有两个子结点
C、恰有两个子结点
D、可以有任意多个子结点
5、设R是实数集，“+，—，A、
，”是实数的四则运算，则下面说法正确的是
>是群
B、是群
>是半群
D、是独异点
6、下面关系中，函数关系是(
)。
A、{，，}
B、{，，<1，x>} C、{<1，y>，<1，x>，}
D、{，，}
7、设是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足(
)。
A、结合律
B、交换律
C、分配律
D、幂等律
8、设Z是整数集，“—”是整数减法，则下列说法正确的是(
)。 A、不是代数系统
B、的单位元是0
C、是代数系统
D、的单位元是1
9、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条(
)。 A、简单通路
B、初级通路
C、简单回路
D、初级回路
10、设G有6个3度点，2个4度点，其余顶点的度数均为0，则G的边数是(
)。 A、10
B、13
C、11
D、6
二、填空题(本大题共8题，共10个空，每空2分，共20分)
1、设关系R={，<2，1>，<2，b>}，则R逆关系R1=_______________________________。
2、在代数系统(Q是有理数集，“+”是有理数加法)中，单位元是______， 2的逆元是___________。
3、设集合M={1，2，3，5}，则M的幂集P(M)包含___________个元素。
4、设T是一棵有n (n2)个顶点的树，则T有_____________条边。
5、设是一个代数系统，是S上的二元运算，若存在S，对任意xS，有x=x=，则称是的_______________。
6、设是一个代数系统，若满足结合律且中有单位元，则称为一个___________________。
7、设D是有向图，若D的基图是连通图，则称D是_________________图
8、既不含________________也不含____________________的无向图称为简单图。
三、计算题(本大题共3小题，每小题10分，共30分)
1、用等值演算法求公式A=(pq)(pr)的主析取范式。
2、求公式x(Q(x)G(x，s))(yP(y)zH(y，z))的前束范式。
3、设集合A={1，2，3，4，5}，关系R={(1)列出R的所有元素;(2)写出R的关系矩阵Mx，y A且x整除y}，要求：
R;
(3)求偏序集的极大元、极小元和最小元。
四、应用题(本大题共2小题，每小题5分，共10分)
1、用命题公式将下列命题符号化： 2和5是偶数，当且仅当5>2。
2、用谓词公式将下列命题符号化：
每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。
五、证明题(本大题共2小题，每小题10分，共20分)
1、在命题逻辑系统中用归结法证明下列推理是有效的： 前提：sq，pq，s 结论：p
2、在谓词逻辑系统中写出下列推理的(形式)证明：
前提：x(M(x)P(x))，x(M(x)G(x))，x(G(x)) 结论：xP(x)
计算题
6. 设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。
7. (9分)设一阶逻辑公式：G = (xP(x)∨yQ(y))→xR(x)，把G化成前束范式. 9. 设R是集合A = {a, b, c, d}. R是A上的二元关系, R = {(a,b), (b,a), (b,c), (c,d)}, (1) 求出r(R), s(R), t(R); (2) 画出r(R), s(R), t(R)的关系图. 11. 通过求主析取范式判断下列命题公式是否等价：
(1) G = (P∧Q)∨(P∧Q∧R)
(2) H = (P∨(Q∧R))∧(Q∨(P∧R)) 13. 设R和S是集合A={a, b, c, d}上的关系，其中R={(a, a),(a, c),(b, c),(c, d)},
S=
{(a, b),(b, c),(b, d),(d, d)}. (1) 试写出R和S的关系矩阵;(2) 计算R•S, R∪S, R1, S1•R1.
-
-
-证明题
1. 利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。 2. 设A,B为任意集合，证明：(A-B)-C = A-(B∪C). 3. (本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。 4. (本题10分)A, B为两个任意集合，求证：
A-(A∩B) = (A∪B)-B . 答案：
1-5
BADBB 6-10 BBABB
1. {<1，a>，<1，2>，} 2. 0， -2 3. 16 4. n-1 5.零元 6.半群 7.弱连通 8.平行边
环 三.
(pq)(pr)(pq)(pr)1. (pqr)(pqr)(pqr)(pqr)m011m010m111m1012.x(Q(x)G(x,s))yz(P(y)H(y,z))
yzx((Q(x)G(x,s))(P(y)H(y,z))3.(1)R{1,1,2,2,3,3,4,4,5,5,1,2,1,3,1,4,1,5,2,4}
12(2)MR345123451111101010
(3)最小元=1 极小元=1 极大元=5 001000001000001四
1.令p表示2是偶数;令q表示5是偶数;r表示5>2;
(pq)r
2.S(x)：x是计算机专业的学生;G(x)：x要学《编译原理》; F(x)：x学经济学;
x(S(x)G(x))x(S(x)F(x))
五 1，(1)
s
前提引入 (2)
sq
前提引入 (3)
qs
置换规则
(4)
q
1,3析取三段论 (5)
pq
前提引入 (6)
p
4,5拒取
(1)
x(M(x)G(x))
前提引入 (2)
M(x)v G(x)
EI规则 (3)
x(G(x))
前提引入 (4)
G(x) (5)
M(x)
AI规则
2,4析取三段论
(6)
x(M(x)P(x))
前提引入 (7)
M(x)→P(x)
AI规则 (8)
P(x)
5,7假言推理 (9)
xP(x)
EG规则
6. G = (P→Q)∨(Q∧(P→R))
= (P∨Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧P)∨(Q∧R) = (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) = (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) = m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7). 7. G = (xP(x)∨yQ(y))→xR(x)
= (xP(x)∨yQ(y))∨xR(x) = (xP(x)∧yQ(y))∨xR(x) = (xP(x)∧yQ(y))∨zR(z) = xyz((P(x)∧Q(y))∨R(z)) 9. (1) r(R)=R∪IA={(a,b), (b,a), (b,c), (c,d), (a,a), (b,b), (c,c), (d,d)}, s(R)=R∪R1={(a,b), (b,a), (b,c), (c,b) (c,d), (d,c)}, -t(R)=R∪R2∪R3∪R4={(a,a), (a,b), (a,c), (a,d), (b,a), (b,b), (b,c), (b,d), (c,d)}; (2)
关系图: abr(R)dcabs(R)dabt(R)dc c
11. G=(P∧Q)∨(P∧Q∧R) =(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) =m6∨m7∨m3 = (3, 6, 7) H = (P∨(Q∧R))∧(Q∨(P∧R)) =(P∧Q)∨(Q∧R))∨(P∧Q∧R) =(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) =(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) =m6∨m3∨m7 = (3, 6, 7) G,H的主析取范式相同，所以G = H. 1013.
(1)MR00000011000000
MS10001000010001 01(2)R•S={(a, b),(c, d)}, R∪S={(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1={(a, a),(c, a),(c, b),(d, c)}, -S1•R1={(b, a),(d, c)}. --四 证明题
1. 证明：{P→Q, R→S, P∨R}蕴涵Q∨S
(1) P∨R
(2) R→P (3) P→Q (4) R→Q (5) Q→R (6) R→S
P Q(1) P Q(2)(3) Q(4) P
(7) Q→S (8) Q∨S Q(5)(6) Q(7) 2. 证明：(A-B)-C = (A∩~B)∩~C
3.
= A∩(~B∩~C) = A∩~(B∪C) = A-(B∪C) 证明：{A∨B, C→B, C→D}蕴涵A→D (1) A D(附加) P (2) A∨B (3) B Q(1)(2) P Q(4) (4) C→B (5) B→C (6) C
Q(3)(5) P (7) C→D (8) D Q(6)(7) D(1)(8) (9) A→D
所以 {A∨B, C→B, C→D}蕴涵A→D. 1. 证明：A-(A∩B)
= A∩~(A∩B) =A∩(~A∪~B) =(A∩~A)∪(A∩~B) =∪(A∩~B) =(A∩~B) =A-B 而 (A∪B)-B = (A∪B)∩~B = (A∩~B)∪(B∩~B) = (A∩~B)∪ = A-B 所以：A-(A∩B) = (A∪B)-B.
推荐阅读：
离散数学作业题截图（共6篇）06-21
北邮离散数学阶段作业（精选6篇）09-05
离散数学课程教学分析01-09
《离散数学》教学现状研究09-13
离散数学论文提纲11-15
离散数学（共8篇）03-24
离散数学a卷魏霞05-14
离散数学论文（推荐5篇）03-21
离散数学集合周记（精选6篇）06-29
离散数学期末考试（通用9篇）12-24
