《离散数学(第三版)》方世昌的期末复习知识点总结.doc

该【《离散数学(第三版)》方世昌的期末复习知识点总结 】是由【莫比乌斯】上传分享，文档一共【25】页，该文档可以免费在线阅读，需要了解更多关于【《离散数学(第三版)》方世昌的期末复习知识点总结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。《离散数学》期末复习提要
《离散数学》是中央电大“数学与数学应用专业”(本科)的一门选修课。该课程使用新的教学大纲,在原有离散数学课程的基础上削减了教学内容(主要是群与环、格与布尔代数这两章及图论的后三节内容),使用的教材为中央电大出版的《离散数学》(刘叙华等编)和《离散数学学习指导书》(虞恩蔚等编)。
离散数学主要研究离散量结构及相互关系,使学生得到良好的数学训练,提高学生抽象思维和逻辑推理能力,为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为:高等数学、线性代数;后续课程为:数据结构、数据库、操作系统、计算机网络等。
课程的主要内容
集合论部分(集合的基本概念和运算、关系及其性质);
数理逻辑部分(命题逻辑、谓词逻辑);
图论部分(图的基本概念、树及其性质)。
学习建议
离散数学是理论性较强的学科,学习离散数学的关键是对离散数学(集合论、数理逻辑和图论)有关基本概念的准确掌握,对基本原理及基本运算的运用,并要多做练习。
教学要求的层次
各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法;理解是能正确表达有关概念和方法的含义;掌握是在理解的基础上加以灵活应用。
一、各章复习要求与重点
第一章集合
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律(交换律、结合律、分配律、吸收律、DeMorgan律等),文氏(Venn)图
3、序偶与迪卡尔积
本章重点内容:集合的概念、集合的运算性质、集合恒等式的证明
[复习要求]
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律,证明集合等式的方法。
4、了解序偶与迪卡尔积的概念,掌握迪卡尔积的运算。
[本章重点习题]
P5~6,4、6;P14~15,3、6、7;P20,5、7。
[疑难解析]
1、集合的概念
因为集合的概念学生在中学阶段已经学过,这里只多了一个幂集概念,重点对幂集加以掌握,一是掌握幂集的构成,一是掌握幂集元数为2n。
2、集合恒等式的证明
通过对集合恒等式证明的练习,既可以加深对集合性质的理解与掌握;又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上,本章做题是一种基本功训练,尤其要求学生重视吸收律和重要等价式在证明中的特殊作用。
[例题分析]
例1设A,B是两个集合,A={1,2,3},B={1,2},则。
解
于是
例2设,试求:
(1);(2);(3);
(4);(5);(6)。
解(1)(2)(3)
(4)(5)(6)
例3试证明
证明
第二章二元关系
[复习知识点]
1、关系、关系矩阵与关系图
2、复合关系与逆关系
3、关系的性质(自反性、对称性、反对称性、传递性)
4、关系的闭包(自反闭包、对称闭包、传递闭包)
5、等价关系与等价类
6、偏序关系与哈斯图(Hasse)、极大/小元、最大/小元、上/下界、最小上界、最大下界
7、函数及其性质(单射、满射、双射)
8、复合函数与反函数
本章重点内容:二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念
[复习要求]
1、理解关系的概念:二元关系、空关系、全关系、恒等关系;掌握关系的集合表示、关系矩阵和关系图、关系的运算。
2、掌握求复合关系与逆关系的方法。
3、理解关系的性质(自反性、对称性、反对称性、传递性),掌握其判别方法(定义、矩阵、图)。
4、掌握求关系的闭包(自反闭包、对称闭包、传递闭包)的方法。
5、理解等价关系和偏序关系的概念,掌握等价类的求法和偏序关系做哈斯图的方法,极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。
6、理解函数概念:函数、函数相等、复合函数和反函数。
7、理解单射、满射、双射等概念,掌握其判别方法。
[本章重点习题]
P25,1;P32~33,4,8,10;P43,2,3,5;P51~52,5,6;P59,1,2;P64,3;P74~75,2,4,6,7;P81,5,7;P86,1,2。
[疑难解析]
1、关系的概念
关系的概念是第二章全章的基础,又是第一章集合概念的应用。因此,学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。
2、关系的性质及其判定
关系的性质既是对关系概念的加深理解与掌握,又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定,可以依据教材中P49上总结的规律。这其中对传递性的判定,难度稍大一点,这里要提及两点:一是不破坏传递性定义,可认为具有传递性。如空关系具有传递性,同时空关系具有对称性与反对称性,但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”,即若,则。如若,则有,且。
3、关系的闭包
在理解掌握关系闭包概念的基础上,主要掌握闭包的求法。关键是熟记三个定理的结论:定理2,;定理3,;定理4,推论。
4、半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了,对于确定任一子集的最大(小)元,极大(小)元也就容易了。这里要注意,最大(小)元与极大(小)元只能在子集内确定,而上界与下界可在子集之外的全集中确定,最小上界为所有上界中最小者,最小上界再小也不小于子集中的任一元素,可以与某一元素相等,最大下界也同样。
5、映射的概念与映射种类的判定
映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外,可借助于关系图,而实数集的子集上的映射也可以利用直角坐标系表示进行,尤其是对各种初等函数。
[例题分析]
例1设集合,判定下列关系,哪些是自反的,对称的,反对称的和传递的:
解:均不是自反的;R4是对称的;R1,R2,R3,R4,R5是反对称的;R1,R2,R3,R4,R5是传递的。
例2设集合,A上的二元关系R为
(1)写出R的关系矩阵,画出R的关系图;
(2)证明R是A上的半序关系,画出其哈斯图;
(3)若,且,求B的最大元,最小元,极大元,极小元,最小上界和最大下界。
解(1)R的关系矩阵为
R的关系图略
(2)因为R是自反的,反对称的和传递的,所以R是A上的半序关系。(A,R)为半序集,(A,R)的哈斯图如下
。4
。1
。3
。2
。5
(3)当,B的极大元为2,4;极小元为2,5;B无最大元与最小元;B也无上界与下界,更无最小上界与最大下界。
第三章 命题逻辑
[复习知识点]
1、命题与联结词(否定、析取、合取、蕴涵、等价),复合命题
2、命题公式与解释,真值表,公式分类(恒真、恒假、可满足),公式的等价
3、析取范式、合取范式,极小(大)项,主析取范式、主合取范式
4、公式类别的判别方法(真值表法、等值演算法、主析取/合取范式法)
5、公式的蕴涵与逻辑结果
6、形式演绎
本章重点内容:命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎
[复习要求]
1、理解命题的概念;了解命题联结词的概念;理解用联结词产生复合命题的方法。
2、理解公式与解释的概念;掌握求给定公式真值表的方法,用基本等价式化简其他公式,公式在解释下的真值。
3、了解析取(合取)范式的概念;理解极大(小)项的概念和主析取(合取)范式的概念;掌握用基本等价式或真值表将公式化为主析取(合取)范式的方法。
4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。
5、理解公式蕴涵与逻辑结果的概念,掌握基本蕴涵式。
6、掌握形式演绎的证明方法。
[本章重点习题]
P93,1;P98,2,3;P104,2,3;P107,1,3;P112,5;P115,1,2,3。
[疑难解析]
1、公式恒真性的判定
判定公式的恒真性,包括判定公式是恒真的或是恒假的。具体方法有两种,一是真值表法,对于任给一个公式,主要列出该公式的真值表,观察真值表的最后一列是否全为1(或全为0),就可以判定该公式是否恒真(或恒假),若不全为0,则为可满足的。二是推导法,即利用基本等价式推导出结果为1,或者利用恒真(恒假)判定定理:公式G是恒真的(恒假的)当且仅当等价于它的合取范式(析取范式)中,每个子句(短语)均至少包含一个原子及其否定。
这里要求的析取范式中所含有的每个短语不是极小项,一定要与求主析取范式相区别,对于合取范式也同样。
2、范式
求范式,包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点:一是准确理解掌握定义;另一是巧妙使用基本等价式中的分配律、同一律和互补律,结果的前一步适当使用等幂律,使相同的短语(或子句)只保留一个。
另外,由已经得到的主析取(合取)范式,根据原理,参阅《离散数学学习指导书》P71例15,可以求得主合取(析取)范式。
3、形式演绎法
掌握形式演绎进行逻辑推理时,一是要理解并掌握14个基本蕴涵式,二是会使用三个规则:规则P、规则Q和规则D,需要进行一定的练习。
[例题分析]
例1求的主析取范式与主合取范式。
解(1)求主析取范式,
方法1:利用真值表求解
G
000
001
010
011
100
101
110
111
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
0
1
0
1
1
1
1
1
因此
方法2:推导法
(2)求主合取范式
方法1:利用上面的真值表
为0的有两行,它们对应的极大项分别为
因此,
方法2:利用已求出的主析取范式求主合取范式
已用去6个极小项,尚有2个极小项,即
与于是
例2试证明公式为恒真公式。
证法一:见〈离散数学学习指导书〉P60例6(4)的解答。(真值表法)
证法二:
G=Ø((ØPÚQ)Ù(ØQÚR))Ú(ØPÚR)
=(PÙØQ)Ú(QÙØR)ÚØPÚR
=(((PÚQ)Ù(PÚØR)Ù(ØQÚQ)Ù(ØQÚØR))ÚØP)ÚR
=((PÚQÚØP)Ù(PÚØRÚØP)Ù(ØQÚØRÚØP))ÚR
=(1Ù(ØQÚØRÚØP))ÚR
=ØQÚØRÚØPÚR
=1
故G为恒真公式。
例3利用形式演绎法证明{P®(Q®R),ØSÚP,Q}蕴涵S®R。
证明:
(1)ØSÚP规则P
(2)S规则D
(3)P规则Q,根据(1),(2)
(4)P®(Q®R)规则P
(5)Q®R规则Q,根据(3),(4)
(6)Q规则P
(7)R规则 Q,根据(5),(6)
(8)S®R规则D,根据(2),(7)
第四章谓词逻辑
[复习知识点]
1、谓词、量词、个体词、个体域、变元(约束变元与自由变元)
2、谓词公式与解释,谓词公式的类型(恒真、恒假、可满足)
3、谓词公式的等价和蕴涵
4、前束范式
本章重点内容:谓词与量词、公式与解释、前束范式
[复习要求]
1、理解谓词、量词、个体词、个体域、变元的概念;理解用谓词、量词、逻辑联结词描述一个简单命题;了解命题符号化。
2、理解公式与解释的概念;掌握在有限个体域下消去公式量词,求公式在给定解释下真值的方法;了解谓词公式的类型。
3、理解用解释的方法证明等价式和蕴涵式。
4、掌握求公式前束范式的方法。
[本章重点习题]
P120,1,2;P125~126,1,3;P137,1。
[疑难解析]
1、谓词与量词
反复理解谓词与量词引入的意义,概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。
2、公式与解释
能将一阶逻辑公式表达式中的量词消除,写成与之等价的公式,然后将解释I中的数值代入公式,求出真值。
3、前束范式
在充分理解掌握前束范式概念的基础上,利用改名规则、基本等价式与蕴涵式(一阶逻辑中),将给定公式中量词提到母式之前称为首标。
[典型例题]
例1设I是如下一个解释:
F(2)F(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)
32011101
求的真值。
解
例2试将一阶逻辑公式化成前束范式。
解
第五章图论
[复习知识点]
1、图、完全图、子图、母图、支撑子图、图的同构
2、关联矩阵、相邻矩阵
3、权图、路、最短路径,迪克斯特拉算法(Dijkstra)
4、树、支撑树、二叉树
5、权图中的最小树,克鲁斯卡尔算法(Kruskal)
6、有向图、有向树
本章重点内容:权图的最短路、二叉树的遍历、权图中的最优支撑树
[复习要求]
1、理解图的有关概念:图、完全图、子图、母图、支撑子图、图的同构。
2、掌握图的矩阵表示(关联矩阵、相邻矩阵)。
3、理解权图、路的概念,掌握用Dijkstra算法求权图中最短路的方法。
4、理解树、二叉树与支撑树的有关概念;掌握二叉树的三种遍历方法,用Kruskal算法求权图中最小树的方法。