2022年《离散数学》方世昌-的期末复习知识点总结资料.docx

《2022年《离散数学》方世昌-的期末复习知识点总结资料.docx》由会员分享，可在线阅读，更多相关《2022年《离散数学》方世昌-的期末复习知识点总结资料.docx（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -离散数学期末复习提要离散数学是中心电大“ 数学与数学应用专业”（本科）的一 门选修课；该课程使用新的教学大纲,在原有离散数学课程的基础 上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的 后三节内容）,使用的教材为中心电大出版的离散数学（刘叙华 等编）和离散数学学习指导书 （虞恩蔚等编）；离散数学主要讨论离散量结构及相互关系,使同学得到良好的数学训练,提高同学抽象思维和规律推理才能,为从事运算机的应用 供应必要的描述工具和理论基础；其先修课程为：高等数学、线性 代数；后续课程为：数据结构、数据库、操作

2、系统、运算机网络等；课程的主要内容1、集合论部分（集合的基本概念和运算、关系及其性质）；数理规律部分（命题规律、谓词规律） ；2、图论部分（图的基本概念、树及其性质） ；3、学习建议 离散数学是理论性较强的学科, 学习离散数学的关键是对离散数 学（集合论、数理规律和图论）有关基本概念的精确把握,对基本 原理及基本运算的运用,并要多做练习；教学要求的层次 各章教学要求的层次为明白、 懂得和把握； 明白即能正确判别有1 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 -

3、 - - - - - - - - - - - - - -关概念和方法；懂得是能正确表达有关概念和方法的含义；把握是在懂得的基础上加以敏捷应用；一、各章复习要求与重点第一章集合 复习学问点 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分 配律、吸取律、 De Morgan 律等）,文氏（ Venn）图 3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 复习要求 1、懂得集合、元素、子集、空集、全集、集合的包含、相等、幂集 等基本概念；2、把握集合的表示法和集合的交、并、差、补等基本运

4、算；3、把握集合运算基本规律,证明集合等式的方法；4、明白序偶与迪卡尔积的概念,把握迪卡尔积的运算； 本章重点习题 P56,4、6； P1415,3、6、7； P20,5、7； 疑难解析 2 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -1、集合的概念由于集合的概念同学在中学阶段已经学过,这里只多了一个幂集概念,重点对幂集加以把握,一是把握幂集的构成,一是把握幂集元数为 2 n；2、集合恒等式的证明 通过对

5、集合恒等式证明的练习, 既可以加深对集合性质的懂得与把握；又可以为第三章命题规律中公式的基本等价式的应用打下良好的基础；实际上,本章做题是一种基本功训练,特别要求同学重视吸取律和重要等价式在ABAB证明中的特别作用； 例题分析 例 1 设 A,B是两个集合, A=1,2,3 ,B=1,2 ,就AB；ABa,b,a,b解A,1 ,2 ,3 ,12 ,13 ,23 ,12 ,3 B,1 ,2 ,12 于是A B3 ,3,1 ,2 ,3 ,123, 例 2 设Aa,b,a ,b,试求： 1Aa,b； 2A； 3A； 4a,bA； 5A； 6A ；解 1Aa,ba ,b, 2AA 3A 4a,bA 5

6、A 6例 3 试证明ABABABA证明3 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -ABABABAABBAABABABBBAABBABA其次章 二元关系 复习学问点 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类 6、偏序关系与哈斯图（ Hasse）、极大/ 小元、最大 / 小元、上

7、/ 下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 复习要求 1、懂得关系的概念：二元关系、空关系、全关系、恒等关系；把握 关系的集合表示、关系矩阵和关系图、关系的运算；2、把握求复合关系与逆关系的方法；3、懂得关系的性质（自反性、对称性、反对称性、传递性）,把握其判别方法（定义、矩阵、图） ；4 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 -

8、 - - - - - - - - - - - - - -4、把握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法；5、懂得等价关系和偏序关系的概念,把握等价类的求法和偏序关系 做哈斯图的方法,极大 / 小元、最大 / 小元、上 / 下界、最小上界、最 大下界的求法；6、懂得函数概念：函数、函数相等、复合函数和反函数；7、懂得单射、满射、双射等概念,把握其判别方法； 本章重点习题 P25,1；P3233,4,8,10； P43,2,3,5； P5152,5,6；P59,1,2； P64,3； P7475,2,4,6,7； P81,5,7； P86,1,2； 疑难解析 1、关系的概念关系的概念是

9、其次章全章的基础,又是第一章集合概念的应用；因此,同学应当真正懂得并娴熟把握二元关系的概念及关系矩阵、关系图表示； 2、关系的性质及其判定 关系的性质既是对关系概念的加深懂得与把握,又是关系的闭 包、等价关系、半序关系的基础；对于四种性质的判定,可以依据 教材中 P49上总结的规律；这其中对传递性的判定,难度稍大一点,这里要提及两点：一是不破坏传递性定义,可认为具有传递性；如 空关系具有传递性,同时空关系具有对称性与反对称性,但是不具 有自反性；另一点是介绍一种判定传递性的“ 跟踪法”,即如5 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 5 页,

10、共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -a 1,a 2R,a2,a 3R ,ai1,aiR,就a1,aiR；如如a,bR ,b,aR,就有a,aR,且b,bR；、关系的闭包在懂得把握关系闭包概念的基础上,主要把握闭包的求法； 关键是熟记三个定理的结论： 定理 2,rRRIA；定理 3,sRRR1；定理 4,推论tRnRi；i1、半序关系及半序集中特别元素的确定 懂得与把握半序关系与半序集概念的关键是哈斯图；哈斯图画法 把握了,对于确定任一子集的最大（小）元,极大（小）元也就容 易了；这里要留意,最大

11、（小）元与极大（小）元只能在子集内确 定,而上界与下界可在子集之外的全集中确定,最小上界为全部上 界中最小者,最小上界再小也不小于子集中的任一元素,可以与某 一元素相等,最大下界也同样；、映射的概念与映射种类的判定 映射的种类主要指单射、满射、双射与非单非满射；判定的方法 除定义外,可借助于关系图,而实数集的子集上的映射也可以利用 直角坐标系表示进行,特别是对各种初等函数； 例题分析 例 1 设集合Aa,b,c,d,判定以下关系,哪些是自反的,对称的,反对称的和传递的：R 1a ,a,b ,aR 2a ,a,b ,c,d,aR 3c ,dR 4a ,a ,b ,b,c ,cR 5a,c,b ,

12、d6 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -解：均不是自反的；R4是对称的；R1 ,R 2 ,R 3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5 是传递的；例 2 设集合 A 1 2, ,3, 4 , 5,A上的二元关系 R为R 1,1 , 2 , 2 , 3 3, , 3 , 4 , 4 4, , ,5 3 , 5 , 4 , 5 5,（）写出 R的关系矩阵,画出 R的关系

13、图；（）证明 R是 A上的半序关系,画出其哈斯图；（）如BA,且B2 ,3 4,5,求 B的最大元,最小元,极大元,微小元,最小上界和最大下界；解 （1）R的关系矩阵为1 0 0 0 00 1 0 0 0M R 0 0 1 1 0 R 的关系图略0 0 0 1 00 0 1 1 1（2）由于 R是自反的,反对称的和传递的,所以 R是 A上的半序关系； A,R 为半序集, A,R 的哈斯图如下；4 ；1 ；3 ；2 ；5 3 当B,2,34 ,5,B 的极大元为 2,4；微小元为 2,5；B无最大元与最小元； B也无上界与下界,更无最小上界与最大下界；7 细心整理归纳 精选学习资料 - - -

14、- - - - - - - - - - - - 第 7 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -第三章 命题规律 复习学问点 、命题与联结词（否定、析取、合取、蕴涵、等价）,复合命题 、命题公式与说明,真值表,公式分类（恒真、恒假、可满意）,公式的等价 、析取范式、合取范式,微小（大）项,主析取范式、主合取范 式 、公式类别的判别方法（真值表法、等值演算法、主析取 / 合取范 式法）、公式的蕴涵与规律结果 、形式演绎 本章重点内容：命题与联结词、公式与说明、析取范式与合取范 式、公式恒真性的判定

15、、形式演绎 复习要求 、懂得命题的概念；明白命题联结词的概念；懂得用联结词产生 复合命题的方法；、懂得公式与说明的概念；把握求给定公式真值表的方法,用基 本等价式化简其他公式,公式在说明下的真值；、明白析取（合取）范式的概念；懂得极大（小）项的概念和主 析取（合取）范式的概念；把握用基本等价式或真值表将公式化为 主析取（合取）范式的方法；、把握利用真值表、等值演算法和主析取8 / 合取范式的唯独性判别细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - -

16、 - - - - - - - - - -公式类型和公式等价的方法；、懂得公式蕴涵与规律结果的概念,把握基本蕴涵式；6、把握形式演绎的证明方法； 本章重点习题 P93,1； P98,2,3； P104,2,3； P107,1,3； P112,5；P115,1,2,3； 疑难解析 1、公式恒真性的判定 详细方 判定公式的恒真性, 包括判定公式是恒真的或是恒假的；法有两种,一是真值表法,对于任给一个公式,主要列出该公式的真值表,观看真值表的最终一列是否全为1（或全为 0）,就可以判定该公式是否恒真（或恒假） ,如不全为 0,就为可满意的；二是推导法,即利用基本等价式推导出结果为1,或者利用恒真 （恒

17、假）判定定理：公式 G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中,每个子句（短语）均至少包含一个原子及其否定；这里要求的析取范式中所含有的每个短语不是微小项,肯定要与 求主析取范式相区分,对于合取范式也同样；2、范式 求范式,包括求析取范式、 合取范式、主析取范式和主合取范式；关键有两点：一是精确懂得把握定义；另一是奇妙使用基本等价式 中的安排律、同一律和互补律,结果的前一步适当使用等幂律,使 相同的短语（或子句）只保留一个；9 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页,共 38 页 - - - - - - - - -

18、名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -另外,由已经得到的主析取（合取）范式,依据GG,1GG原理,参阅离散数学学习指导书P71例 15,可以求得主合取（析取）范式；3、形式演绎法把握形式演绎进行规律推理时,一是要懂得并把握 14 个基本蕴涵式,二是会使用三个规章：规章 定的练习； 例题分析 P、规章 Q和规章 D,需要进行一例 1 求GPQRP的主析取范式与主合取范式；解 （1）求主析取范式,方法 1：利用真值表求解PQRPQPQRG 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0

19、1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 因此GPQQRPQRPQRPQRPQRPR10 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 10 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -方法 2：推导法GPQRRPPPQRPPPPQRPQRPRQRPPRQQQRPRPQQRRPQRPQRPQPQRPQRPQRRPQRPQRPQRPQQRPQRPQR（2）求主合取范式 方法 1：利用上面的真值表PQR ,RP为 0 的

20、有两行,它们对应的极大项分别为PQPQR因此,PQRPPQRPQR方法 2：利用已求出的主析取范式求主合取范式 已用去 6 个微小项,尚有 2 个微小项,即PQR与PQR于是QRGPQRPQRGGPQRPPQRPQRPR为恒真公式；例 2 试证明公式GPQQRP60例 6（4）的解答；（真值证法一：见离散数学学习指导书表法）证法二：Q R） （P R） G= （P Q） （ = （PQ） （QR）P R 11 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - -

21、 - - - - - - - - - - - - - = （P Q） （PR） （Q Q） （QR）P） R = （P QP） （PRP） （QRP） R = （1 （QRP） R =QRP R =1 故 G为恒真公式；例 3 利用形式演绎法证明 P（Q R）,S P,Q蕴涵 SR；证明：（1）S P R）规章 P （2）S 规章 D （3）P 规章 Q,依据（ 1）,（2）（4）P（Q规章 P （5）Q R 规章 Q,依据（ 3）,（4）（6）Q 规章 P （7）R 规章Q,依据（ 5）,（6）（8）SR 规章 D,依据（ 2）,（7）第四章谓词规律 复习学问点 1、谓词、量词、个体词、个体

22、域、变元（约束变元与自由变元）2、谓词公式与说明,谓词公式的类型（恒真、恒假、可满意）3、谓词公式的等价和蕴涵12 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 12 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -4、前束范式 本章重点内容：谓词与量词、公式与说明、前束范式 复习要求 1、懂得谓词、量词、个体词、个体域、变元的概念；懂得用谓词、量词、规律联结词描述一个简洁命题；明白命题符号化；2、懂得公式与说明的概念；把握在有限个体域下消去公式量词,求 公

23、式在给定说明下真值的方法；明白谓词公式的类型；3、懂得用说明的方法证明等价式和蕴涵式；4、把握求公式前束范式的方法； 本章重点习题 P120,1,2； P125126,1,3； P137,1； 疑难解析 1、谓词与量词反复懂得谓词与量词引入的意义,概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规章；2、公式与说明能将一阶规律公式表达式中的量词排除,写成与之等价的公式,然后将说明 I 中的数值代入公式,求出真值；3、前束范式在充分懂得把握前束范式概念的基础上,利用改名规章、 基本等价式与蕴涵式 （一阶规律中）,将给定公式中量词提到母式之前称为 首标；13 细心整理归纳 精选学习资料 -

24、 - - - - - - - - - - - - - - 第 13 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - - 典型例题 例 1 设 I 是如下一个说明：D23, F2 F3 P2 P3 Q2,2 Q2,3 Q3,2 Q3,3 3 2 0 1 1 1 0 1 求xyPxQFx,y的真值；解xyPxQFx,y0xPxQFx,21PxQFx,3P2QF2,2P2QF2,3P3QF3,2P3QF3,3000111111 例 2 试将一阶规律公式化成前束范式；解GxyPx ,y,yyyQyRxxyPx ,

25、yQyRxxyPx ,yzQzRxxyzPxQzRx第五章图论 复习学问点 1、图、完全图、子图、母图、支撑子图、图的同构 2、关联矩阵、相邻矩阵3、权图、路、最短路径,迪克斯特拉算法（Dijkstra）4、树、支撑树、二叉树 5、权图中的最小树,克鲁斯卡尔算法（Kruskal ）6、有向图、有向树 14 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 14 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -本章重点内容：撑树 复习要求 权图的最短路、 二叉树的

26、遍历、权图中的最优支1、懂得图的有关概念：图、完全图、子图、母图、支撑子图、图的同构；2、把握图的矩阵表示（关联矩阵、相邻矩阵）；3、懂得权图、路的概念,把握用 Dijkstra 算法求权图中最短路的方法；4、懂得树、二叉树与支撑树的有关概念；把握二叉树的三种遍历方法,用 Kruskal 算法求权图中最小树的方法；5、懂得有向图与有向树的概念； 本章重点习题 P221,2；P225,1；P231,2,3；P239,5；P242,1,2； 疑难解析 1. 本章的概念较多,学习时需要认真比较各概念的含义,如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等,这些都是图的基本概

27、念,今后将在数据结构、数据库、运算机网络等课程中用到；2、权图中的最短路严格执行迪克斯特拉（ Dijkstra）算法步骤,从起点起,到每一点求出最短路,然后进行认真比较,最终到达终点,算出最小权和；3、权图中的最优支撑树15 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 15 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -权图中的最优支撑树是图中所带权和最小的支撑树,使用克鲁斯卡尔（ Kruskal ）算法； 典型例题 例1 在具有 n 个顶点的完全图Kn

28、中删去多少条边才能得到树？解：n 个顶点的完全图 Kn 中共有 n （n-1 ）/2 条边,n 个顶点的树应有 n-1 条边,于是,删去的边有： n （n-1 ）/2- （n-1）=（n-1） （n-2 ）/2 例2 求下面有限图中点 P231,第 3 题；）u 到各点间的最短路；（图上数字见教材解 uu1 , du, u1=1, 路u, u1 u u 2 , du, u2=9, 路u, u4, u 3, u 7, u 2 u u 3 , du, u3=5, 路u, u4, u3 , u u4 , du, u4=3, 路u, u4 uu5 , du, u5=11, 路u, u1, u5 或路

29、u, u4, u3 , u7 , u2 , u5 u u 6 , du, u6=13, 路u, u1, u5, u6 16 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 16 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -u u 7 , du, u7=8, 路u, u4 , u3 , u7 u u 8 , du, u8=11, 路u, u4, u8 uv, du, v=15, 路u, u1, u5 , u6 ,v 或路u, u4 , u3 , u7 , u

30、6 ,v 二、考核说明本课程的考核实行形成性考核和终结性考核的形式；形成性考核占总成果的 20%,以课程作业的形式进行 （共三次, 由中心电大统一布置）；终结性考核即期末考试, 占总成果的 80%；总成果为 100 分,60 分及格；期末考试实行全国统一闭卷考核,试卷满分为100；由中心电大统一命题,统一评分标准,统一考试时间（考试时间为 120 分钟）；1、试题类型试题类型有填空题（分数约占 20%）、单项挑选题（分数约占 14%）、运算题（分数约占50%）和证明题（分数约占16%）；填空题和单项挑选题主要涉及基本概念、基本理论,重要性质和结论、公式及其简洁运算；运算题主要考核同学的基本运算

31、技能,要求书写运算、推论过程或理由；证明题主要考查应用概念、性质、定理及主要结论进行规律推理的才能,要求写出推理过程；2、考核试卷题量安排试卷题量在各部分的安排是：集合论约占 40%,图论约占 20%；17 40%,数理规律约占细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 17 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -详细课程考核情形见课程考核说明；附录：试题类型及规范解答举例 填空题 1. 设 R 是集合 A上的二元关系,假如关系 R同时具有 性、

32、对称性和 性,就称 R是等价关系；2. 命题公式 G=（P Q）R,就 G共有 个不同的说明；把 G在其全部说明下所取真值列成一个表,称为 G的；说明（P,Q,R）或（ 0,1,0）使 G的真值为；3. 设 G=（P,L）是图,假如 G是连通的,并且,就 G是树；假如根树 T 的每个点 v 最多有两棵子树,就称 T为； 单项挑选题 （挑选一个正确答案的代号,填入括号中）1. 由集合运算定义,以下各式正确的有（）；AX X Y B.X X Y C.X X Y D.Y X Y 2. 设 R1,R2是集合 A=a,b,c,d 上的两个关系, 其中 R1=（a,a）,（b,b）,（b,c）,（d,d）

33、 ,R2= （a,a）,（b,b）,（b,c）,（c,b）,（d,d） ,就 R2是 R1 的（）闭包；以传递 DA自反 B对称 C上都不是3.设 G是由 5 个顶点组成的完全图,就从G中删去（）条18 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 18 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -边可以得到树；A4 B5 C6 D10 运算题 1. 化简下式：（A B C）（A B）C）（A B C）（A B C）2. 通过求主析取范式判定以下命题公式

34、是否等值；（1）（P Q） （P Q R）；（2）（P （Q R） （Q （P R）；3. 求图中 A到其余各顶点的最短路径,并写出它们的权； B 7 C 1 2 A 2 5 3 D 4 6 E 1 F 证明题 1. 利用基本等价式证明下面命题公式为恒真公式；（P Q） （Q R）（P R）2. 用形式演绎法证明： P Q, R S,P R 蕴涵 Q S；试题答案及评分标准19 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 19 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料 - - - - - - - - - -

35、 - - - - - 填空题 1、自反；传递2、8；真值表； 1 3、无回路；二叉树 单项挑选题 （挑选一个正确答案的代号,填入括号中）1、 A 2、 B 3、C 运算题 1. 解：（A B C）（A B）C）（A B C）（A B C）=（A B C）（A B C）（A B C）（A B C）=（A B）（C C）（A B）（C C）=（A B）E）（A B）E） E 为全集=（A B）（A B）= A（B B）= A E = A 2. 解：（P Q） （P Q R）（P Q （R R） （P Q R）（P Q R） （P Q R） （P Q R） m6 m7 m3 m 3 m6 m7 20 细心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 20 页,共 38 页 - - - - - - - - - 名师归纳总结 精品学习资料