离散数学自学指导书

1、离散数学自学指导书一、课程编码及适用专业课程编码：总学时：面授学时：自学学时：适用专业 ：计算机科学专业（函授）二、课程性质离散数学是以研究离散量的结构和相互间的关系为主要目标，因此，它充分描述了计算机科学离散性特点，其基本思想、概念和方法广泛地渗透到计算机科学与技术的各个领域，是计算机专业学生必须具备的基本理论知识。本课程作为计算机专业基础课，既为后续专业课打基础，也为学生在抽象思维和严密推理能力方面提供必要的基本训练。三、本课程的地位和作用离散数学课是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。通过本课程的学习，要使学生具有现代数学的观点和方法；同时，培养学生抽象思维和慎密概

2、括的能力，使学生初步了解和掌握如何从多种多样的具体对象抽象出一般共性并加以形式化；同时，使学生具有良好的开拓专业理论的素质和使用所学知识，分析和解决实际问题的能力，为进一步学习计算机科学与技术的各门课程打下坚实的理论基础。四、学习目的与要求本课程主要有数理逻辑、集合论、图论、代数系统，是一门理论性较强，应用性较广的课程。因此，通过本课程的学习，使学生能够较系统掌握基本概念和基本理论，基本计算和逻辑推理的技能及基本证明和验证方法的基础上，会初步运用这些知识处理一些简单的实际问题。进一步提高抽象思维和逻辑推理的能力。五、本课程的学习方法为了学好本课程，首先要具有正确的学习目的和态度。在学习中要刻苦

3、钻研、踏踏实实、虚心求教、持之以恒。在学习时要抓住基本概念、基本理论；要理解问题是如何提出和引申的，又是怎样解决和应用的；要注意各部分内容之间的联系，前后是如何呼应的；要重在理解，能提出问题，积极思考，不要死记；通过习题可以巩固和加深对所学理论的理解，并培养分析能力和运算能力，所以应按要求完成布置的作业题。解题前，要对所学内容基本掌握；解题时，要看懂题意，注意分析，熟练应用各种理论和公式。除学习规定教材外，应参阅相关的参考书。通过各个学习环节，培养分析和解决问题的能力和创新精神。解决问题不是仅仅照着书本上的例题作练习题，而是要求使用已有的知识对提出的要求和论据能理解和领悟，并能提出自己的思路和

4、解决问题的方案，这是一个创新过程。六、自学内容与指导第一章 命题逻辑（一）自学内容1能判断真假的陈述句称为命题。因此要理解命题概念，会判断语句是否为命题； 2. 要将命题符号化必须掌握五个联结词的真值表； 3. 判断命题是否等价必须掌握命题的基本等价公式，并熟练掌握对合式公式进行等价变换的方法；4. 理解重言式、蕴含式与逻辑结论的概念；5. 掌握用主析取范式判断两个公式是否等价的方法；6. 掌握命题逻辑的推理演算方法。（二）本章重点1命题的概念；2如何求主析取范式；3命题逻辑的推理演算方法。（三）本章难点1主析取范式的求法；2命题逻辑的推理演算方法。（四）本章考点1命题的判断；2求公式的主析取

5、范式；3证明结论的有效性。（五）学习指导判断是否为命题时注意首先要看是否为陈述句，其次要看是否能判断真假。将命题正确符号化的基础是灵活运用联结词。判断公式的等价主要记清基本的等价式；求公式的主析取范式主要有真值表法与推导法；证明结论的有效性主要有真值表法、推导法、反证法，针对特别的情况可以用cp规则，要区分不同的情况应用不同的方法。第二章 谓词逻辑（一）自学内容为了刻划命题内部的逻辑结构，就需要研究谓词逻辑，因此就需要1.理解谓词、量词、变元、个体域等概念； 2.掌握用谓词、量词、联结词构造谓词逻辑公式的方法； 3.掌握谓词公式在给定解释下求真值的方法； 4.会将谓词公式逻辑化为前束范式； 5

6、.会将命题符号化，并能用推理规则进行逻辑证明。（二）本章重点1.理解谓词、量词、变元、个体域等概念；2.将谓词逻辑化为前束范式；3.将命题符号化，并能用推理规则进行逻辑证明。（三）本章难点1.将谓词公式逻辑化为前束范式；2.将命题符号化，并能用推理规则进行逻辑证明。（四）本章考点1.将谓词公式逻辑化为前束范式；2.将命题符号化，并能用推理规则进行逻辑证明。（五）学习指导对谓词的理解首先要找好谓词，其次要分清是几元谓词；对量词的理解要分清是全称量词还是存在量词，在此还要注意特性谓词；在命题逻辑等价式与蕴含式的基础上学习谓词演算的等价式与蕴含式；在第一章的基础上学习求前束范式、谓词演算的推理理论；

7、第三章 集合与关系（一）自学内容在复习学过的集合知识的基础上学习以下内容：1.掌握集合的两种表示法，理解集合的包含与相等、幂集等基本概念； 2.熟练掌握集合的交、并、补、差、对称差等运算，并通过文氏图加深理解；3.会做笛卡儿积的运算； 4.理解二元关系的概念及其性质；5.掌握二元关系的关系矩阵和关系图；6.掌握划分与覆盖的概念；7.理解等价关系和偏序关系的有关概念。（二）本章重点1二元关系的概念及其性质；2划分与覆盖的概念；3等价关系和偏序关系的有关概念。（三）本章难点等价关系和偏序关系（四）本章考点二元关系的性质、划分与覆盖、等价关系、偏序关系。（五）学习指导在以前所学集合的基础上学习笛卡儿

8、积，在学习关系时注意关系是笛卡儿积的子集；对于关系的性质要分清与理解各个性质的定义；求特殊的关系要记清公式；对于集合的划分与覆盖的区分要看看集合之间是否相交的；要牢记等价关系是具有自反、对称、传递的关系；要注意等价类也是集合；在偏序关系的学习中要注意学习里面特殊的元素即最大元、最小元、极大元、极小元、上界、下界、上确界、下确界。第四章 函数（一）自学内容1.理解函数、单射、满射和双射的概念，并掌握其判定方法；2.掌握逆函数与复合函数；3.了解基数的概念，可数集与不可数集。（二）本章重点1单射、满射和双射；2基数的概念，可数集与不可数集。（三）本章难点集合等势的判定。（四）本章考点判定两集合等势

9、。（五）学习指导在学习函数、单射、满射和双射时要从关系的角度去理解；着重理解基数等势的概念；在判断两集合等势时首先考虑找到一双射，如果找不到双射就考虑找到两个单射，如若找到就可以证明两集合等势。第五章 代数结构（一）自学内容1.掌握运算及其性质；2.理解广群、半群、独异点、群、阿贝尔群、循环群的概念、性质； 3.知道陪集的概念，掌握拉格朗日定理； 4.知道同态、同构的概念；5.理解环、域的概念。（二）本章重点1半群、独异点、群、阿贝尔群、循环群的概念、性质；2拉格朗日定理；3同态、同构的证明。（三）本章难点1半群、独异点、群、阿贝尔群、循环群的证明；2拉格朗日定理的应用；3同态、同构的证明。（

10、四）本章考点1半群、独异点、群、阿贝尔群、循环群的证明；2拉格朗日定理的应用；3同态、同构的证明。（五）学习指导在学习广群、半群、独异点、群时注意各自的性质，同时注意群独异点半群广群；阿贝尔群、循环群是特殊的群要注意各自的性质；在理解陪集的概念与拉格朗日定理基础上，着重拉格朗日定理的应用，这要通过做题来体会其应用；对于同态、同构的证明主要考虑到函数与群的综合应用；对于环与域只要分清哪些为环，哪些为域。第六章 格与布尔代数（一）自学内容了解格、分配格、有补格及布尔代数的概念并会进行判断。（二）本章重点格、分配格、有补格的判断。（三）本章难点格、分配格、有补格的判断。（四）本章考点格、分配格、有补

11、格的判断。（五）学习指导正确理解格、分配格、有补格及布尔代数的概念是作出正确判断的前提，其次对其各自的性质也要有很好的了解。第七章 图论（一）自学内容1.掌握图的概念及几种特殊图；2.理解路、回路的定义；3.了解图的几种矩阵表示； 4.理解欧拉图的定义，了解相关定理及应用；5.理解哈密顿图的定义，知道相关定理及应用；6.理解对偶图定义，知道它的应用 7.了解平面图及相关定理；8.理解树的等价定义，会求最小生成树；9.掌握根树、有序树。会求哈夫曼树。（二）本章重点1欧拉图的应用；2哈密顿图的应用；3平面图及相关定理；4最小生成树的求法；5哈夫曼树的求法。（三）本章难点1欧拉图的应用；2哈密顿图的

12、应用；3平面图相关定理的理解；4最小生成树的求法；5哈夫曼树的求法。（四）本章考点1欧拉图的应用；2哈密顿图的应用；3平面图的相关定理的应用；4求最小生成树；5求哈夫曼树。（五）学习指导图论是挺有意思的一部分，在学习时首先要理解好概念，其次要多看多想一些有趣的游戏并用数学的方法去解决它。在求最小生成树、哈夫曼树时要牢记书中提到的算法，否则求不出最小生成树、求哈夫曼树。七、自学进度及各章节学时安排自学周数15周，每周保证4学时，总计60学时。在自学过程中，除了保证时间外一定要做练习，独立完成布置的作业分两次寄回学校。最好将各章后面的有关习题及所介绍参考书上的有关习题也做一下。只有通过练习才能达到

13、对所学内容理解、消化的目的，进而掌握它。各章节学时安排如下（不包括作业学时）。自学进度表周次学时内 容学 习 要 求作 业12命题及其表示法、联结词、命题公式与翻译理解命题含义、联结词命题公式；掌握等价公式、蕴含式p8(5)p19(7) a)、b)p23(1) b)2真值表与等价公式、重言式与蕴含式其他联结词22对偶与范式掌握主析取范式、合取范式，推理理论、个体谓词p39(3) d)p47(2) c),(4)a)2推理理论、谓词的概念32命题函数与量词谓词公式与翻译掌握量词、谓词公式等价公式、蕴含式p60(2)a)-f)p62(3)p72(2)a)、b)2谓词演算的等价式与蕴含式、前束范式42

14、谓词演算的推理理论、集合的概念、运算掌握谓词演算的推理理论，关系的性质p79(3)a)、b)p109(2)、p113(1)2序偶与笛卡尔积、关系及其表示、关系的性质52复合关系和逆关系、关系的闭包运算集合的划分与覆盖掌握集合的划分等价关系与等价类p118(1)、p127(1)p130(1)p134(2)、(3)2等价关系与等价类、相容关系62序关系掌握序关系各种映射p146(6)2函数的概念72基数的概念了解基数的概念掌握运算及性质、半群p185(2)p190(3)2代数系统的运算及性质、半群82群与子群 掌握群、子群阿贝尔群、循环群p197(3)、(4)p200(4)2阿贝尔群与循环群92陪集与拉格朗日定理掌握拉格朗日定理同态与同构p211(2)p211(4)2同态与同构102环与域了解环与域p229(7)2群的理论探讨112格的概念了解格的特点各种格的特点p242(1)2分配格、有补格122布尔代数、布尔表达式了解布尔代数概念掌握图的基本概念p252