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

《2022年《离散数学》方世昌-的期末复习知识点总结资料》由会员分享，可在线阅读，更多相关《2022年《离散数学》方世昌-的期末复习知识点总结资料（38页珍藏版）》请在装配图网上搜索。

1、1 离散数学期末复习提要离散数学是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的离散数学（刘叙华等编）和离散数学学习指导书 （虞恩蔚等编）。离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。课程的主要内容1、集合论部分（集合的基本概念和运算、关系及其性质）；2、数理

2、逻辑部分（命题逻辑、谓词逻辑） ；3、图论部分（图的基本概念、树及其性质） 。学习建议离散数学是理论性较强的学科， 学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。教学要求的层次各章教学要求的层次为了解、 理解和掌握。 了解即能正确判别有名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1 页，共 38 页 - - - - - - - - - 2 关概念和方法；理解是能正确表达有关概念和方法的含

3、义；掌握是在理解的基础上加以灵活应用。一、各章复习要求与重点第一章集合 复习知识点 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等） ，文氏（ Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 复习要求 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 本章重

4、点习题 P56 ，4、6； P1415，3、6、7； P20，5、7。 疑难解析 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 2 页，共 38 页 - - - - - - - - - 3 1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为 2n。2、集合恒等式的证明通过对集合恒等式证明的练习， 既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良

5、好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在BABA证明中的特殊作用。 例题分析 例 1 设 A，B是两个集合， A=1，2，3 ，B=1，2，则)()(BA。解3,2, 1,3, 2,3, 1,2, 1,3,2,1 ,)(A2, 1,2,1 ,)(B于是3 ,2, 1,3,2,3 , 1,3)()(BA例 2 设,babaA，试求： (1)baA,； (2)A； (3)A； (4)Aba,； (5)A； (6)A。解 (1),babaA (2)AA (3)babaA, (4)Aba, (5)A (6)A例 3 试证明BABABABA证明名师归纳总结 精品学

6、习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3 页，共 38 页 - - - - - - - - - 4 BABABABABBBAABAABBAABABABA第二章 二元关系 复习知识点 1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（ Hasse） 、极大/ 小元、最大 /小元、上 / 下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）

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

8、系的闭包（自反闭包、对称闭包、传递闭包）的方法。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 页，

10、共 38 页 - - - - - - - - - 6 RaaRaaRaaii,13221，则Raai,1。如若RabRba,，则有Raa,，且Rbb,。、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。 关键是熟记三个定理的结论： 定理 2，AIRRr； 定理 3，1RRRs；定理 4，推论niiRRt1。、半序关系及半序集中特殊元素的确定理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最

11、小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 例题分析 例 1 设集合dcbaA,，判定下列关系，哪些是自反的，对称的，反对称的和传递的：dbcaRccbbaaRdcRadcbaaRabaaR, ,54321名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6

12、 页，共 38 页 - - - - - - - - - 7 解： 均不是自反的；R4是对称的；R1 ,R2,R3 , R4 ,R5是反对称的；R1 ,R2,R3 , R4 ,R5是传递的。例 2 设集合5,4, 3 ,2 ,1A，A上的二元关系 R为5 ,5,4,5,3, 5,4 ,4,4,3,3 ,3,2,2,1 , 1R（）写出 R的关系矩阵，画出R的关系图；（）证明 R是 A上的半序关系，画出其哈斯图；（）若AB，且5 ,4 ,3,2B，求 B的最大元，最小元，极大元，极小元，最小上界和最大下界。解 （1）R的关系矩阵为1110001000011000001000001RM R的关系图略

13、（2）因为 R是自反的，反对称的和传递的，所以R是 A上的半序关系。 (A,R) 为半序集， (A,R)的哈斯图如下 (3) 当5,4, 3, 2B，B的极大元为 2，4；极小元为 2，5；B无最大元与最小元； B也无上界与下界，更无最小上界与最大下界。4 。1 。3 。2 。5 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 38 页 - - - - - - - - - 8 第三章命题逻辑 复习知识点 、命题与联结词（否定、析取、合取、蕴涵、等价），复

14、合命题、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价、析取范式、合取范式，极小（大）项，主析取范式、主合取范式、公式类别的判别方法（真值表法、等值演算法、主析取/ 合取范式法）、公式的蕴涵与逻辑结果、形式演绎本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎 复习要求 、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值

15、表将公式化为主析取（合取）范式的方法。、掌握利用真值表、等值演算法和主析取/ 合取范式的唯一性判别名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页，共 38 页 - - - - - - - - - 9 公式类型和公式等价的方法。、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。6、掌握形式演绎的证明方法。 本章重点习题 P93 ，1； P98，2，3； P104，2，3； P107，1，3； P112，5；P115，1，2，3。 疑难解析 1、公式恒真性的判定判

16、定公式的恒真性， 包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为 0） ，就可以判定该公式是否恒真（或恒假） ，若不全为 0，则为可满足的。二是推导法，即利用基本等价式推导出结果为1，或者利用恒真 （恒假）判定定理：公式 G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。2、范式求范式，包括求析取范式、 合取范式、主析取范式和主合取范式。关键有两点：

17、一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 9 页，共 38 页 - - - - - - - - - 10 另外，由已经得到的主析取（合取）范式，根据GGGG, 1原理，参阅离散数学学习指导书P71例 15，可以求得主合取（析取）范式。3、形式演绎法掌握形式演绎进行逻辑推理时，一是要理解并掌握14 个基本蕴涵式，二是会使用三个规

18、则：规则P、规则 Q和规则 D，需要进行一定的练习。 例题分析 例 1 求PRQPG的主析取范式与主合取范式。解 （1）求主析取范式，方法 1：利用真值表求解RQPQPRQPG 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 因此RQPRQPRQPRQPRQPRQPG名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 10 页，

19、共 38 页 - - - - - - - - - 11 方法 2：推导法RQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRRQQPPPRQQQRPPRQRPPRQPPRQPPRRQPG（2）求主合取范式方法 1：利用上面的真值表PRQP为 0 的有两行，它们对应的极大项分别为RQPRQP,因此，RQPRQPPRQP方法 2：利用已求出的主析取范式求主合取范式已用去 6 个极小项，尚有 2 个极小项，即RQP与RQP于是RQPRQPRQPRQPGGRQPRQPG例 2 试证明公式RPRQQPG为恒真公式。证法一：见离散数学学习指导书P60例 6（4）的解答。（

20、真值表法）证法二： G= （ （P Q ） （Q R） ） （P R ） = （PQ ） （QR）P R 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 11 页，共 38 页 - - - - - - - - - 12 = （ （ （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蕴

21、涵 SR。证明：（1）S P 规则 P （2）S 规则 D （3）P 规则 Q ，根据（ 1） ， （2）（4）P（QR）规则 P （5）Q R 规则 Q ，根据（ 3） ， （4）（6）Q 规则 P （7）R 规则Q ，根据（ 5） ， （6）（8）SR 规则 D，根据（ 2） ， （7）第四章谓词逻辑 复习知识点 1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）3、谓词公式的等价和蕴涵名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - -

22、- - - - - - - - 第 12 页，共 38 页 - - - - - - - - - 13 4、前束范式本章重点内容：谓词与量词、公式与解释、前束范式 复习要求 1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。3、理解用解释的方法证明等价式和蕴涵式。4、掌握求公式前束范式的方法。 本章重点习题 P120，1，2； P125126，1，3； P137，1。 疑难解析 1、谓词与量词反复理解谓词与量词引入的意义，概念的含

23、义及在谓词与量词作用下变量的自由性、约束性与改名规则。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释 I 中的数值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基础上，利用改名规则、 基本等价式与蕴涵式 （一阶逻辑中），将给定公式中量词提到母式之前称为首标。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 13 页，共 38 页 - - - - - - - - - 14 典型例题 例 1 设 I 是如下一个解释：3 ,2

24、D F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1 求y,xFQxPyx的真值。解110111110003,3FQ3P2,3FQ3P3,2FQ2P2,2FQ2P3,xFQxP2,xFQxPxy,xFQxPyx例 2 试将一阶逻辑公式化成前束范式。解xRzQyxPzyxxRzQzyxyPxxRyQyyxyPxxRyyQyxyPxG,第五章图论 复习知识点 1、图、完全图、子图、母图、支撑子图、图的同构2、关联矩阵、相邻矩阵3、权图、路、最短路径，迪克斯特拉算法（Dijkstra）4、树、支撑树、二叉树5、权图中的最小

25、树，克鲁斯卡尔算法（Kruskal ）6、有向图、有向树名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 14 页，共 38 页 - - - - - - - - - 15 本章重点内容：权图的最短路、 二叉树的遍历、权图中的最优支撑树 复习要求 1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。2、掌握图的矩阵表示（关联矩阵、相邻矩阵）。3、理解权图、路的概念，掌握用Dijkstra算法求权图中最短路的方法。4、理解树、二叉树与支撑树的有关概念；掌握二

26、叉树的三种遍历方法，用 Kruskal 算法求权图中最小树的方法。5、理解有向图与有向树的概念。 本章重点习题 P221，2；P225，1；P231，2，3；P239，5；P242，1，2。 疑难解析 1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。2、权图中的最短路严格执行迪克斯特拉（ Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。3、权图中的最优支撑树名师归纳总结 精品学习资料 -

27、- - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 15 页，共 38 页 - - - - - - - - - 16 权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（ Kruskal ）算法。 典型例题 例1 在具有 n 个顶点的完全图Kn中删去多少条边才能得到树？解：n 个顶点的完全图Kn中共有 n （n-1）/2 条边，n 个顶点的树应有 n-1 条边，于是，删去的边有： n （n-1）/2- （n-1）=（n-1） （n-2）/2 例2 求下面有限图中点u 到各点间的最短路。（图上

28、数字见教材P231，第 3 题。 ）解 uu1 ， d(u, u1)=1, 路(u, u1) u u2 , d(u, u2)=9, 路(u, u4, u3, u7, u2) u u3 , d(u, u3)=5, 路(u, u4, u3 ,) u u4 , d(u, u4)=3, 路(u, u4 ) uu5 , d(u, u5)=11, 路(u, u1, u5) 或路 (u, u4, u3 , u7 , u2 , u5) u u6 , d(u, u6)=13, 路(u, u1, u5, u6) 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精

29、选学习资料 - - - - - - - - - - - - - - - 第 16 页，共 38 页 - - - - - - - - - 17 u u7 , d(u, u7)=8, 路(u, u4 , u3 , u7) u u8 , d(u, u8)=11, 路(u, u4, u8) uv, d(u, v)=15, 路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v) 二、考核说明本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的 20% ，以课程作业的形式进行 （共三次，由中央电大统一布置） ；终结性考核即期末考试， 占总成绩的 80

30、% 。总成绩为 100分，60 分及格。期末考试实行全国统一闭卷考核，试卷满分为100。由中央电大统一命题，统一评分标准，统一考试时间（考试时间为120分钟） 。1、试题类型试题类型有填空题（分数约占 20% ） 、 单项选择题（分数约占 14% ） 、计算题（分数约占50% ）和证明题（分数约占16% ） 。填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。2、考核试卷题量分配试卷题量在各部分的分配是：集合论约占40%

31、 ，数理逻辑约占40% ，图论约占 20% 。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 17 页，共 38 页 - - - - - - - - - 18 具体课程考核情况见课程考核说明。附录：试题类型及规范解答举例 填空题 1.设 R 是集合 A上的二元关系，如果关系R同时具有性、对称性和性，则称 R是等价关系。2.命题公式 G= （P Q ）R ，则 G共有个不同的解释；把 G在其所有解释下所取真值列成一个表，称为G的；解释（P，Q ，R）或（0，1，0）使

32、 G的真值为。3.设 G= （P，L）是图，如果 G是连通的，并且，则 G是树。如果根树T的每个点 v 最多有两棵子树，则称T为。 单项选择题 （选择一个正确答案的代号，填入括号中）1.由集合运算定义，下列各式正确的有（） 。AX X Y B.XX Y C.XX Y D.YX Y 2.设 R1，R2是集合 A=a，b，c，d 上的两个关系， 其中 R1=（a，a） ，（b，b） ， （b，c） ， （d，d） ，R2=（a，a） ， （b，b） ， （b，c） ，（c，b） ， （d，d） ，则 R2是 R1的（）闭包。A自反 B对称 C传递 D以上都不是3.设 G是由 5 个顶点组成的完全图

33、，则从G中删去（）条名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 18 页，共 38 页 - - - - - - - - - 19 边可以得到树。A4 B5 C6 D10 计算题 1.化简下式：（A B C）（ （A B）C）（A B C）（A B C）2.通过求主析取范式判断下列命题公式是否等值。（1） （P Q ） （P Q R） ；（2） （P （Q R） ） （Q （P R ） ） ；3.求图中 A到其余各顶点的最短路径，并写出它们的权。 证明题 1.利用

34、基本等价式证明下面命题公式为恒真公式。（ （PQ ） （Q R） ）（PR）2.用形式演绎法证明： PQ ， RS，P R 蕴涵 Q S。试题答案及评分标准 B 7 C 1 2 A 2 5 3 D 46 E 1 F 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 19 页，共 38 页 - - - - - - - - - 20 填空题 1、自反；传递2、8；真值表； 1 3、无回路；二叉树 单项选择题 （选择一个正确答案的代号，填入括号中）1、 A 2、 B 3、C

35、 计算题 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）= AE = A 2.解：（P Q ） （P Q R）（P Q （R R） ） （P Q R）（P QR） （P Q R） （P Q R） m6m7m3 m3m6m7 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - -

36、- - - - - - - - 第 20 页，共 38 页 - - - - - - - - - 21 （P （Q R） ） （Q （P R） ）（P Q ） （Q R）（PP R ）（PQ R）（分配律）（P Q （R R） ）（ （P P） Q R） （P Q R）（P QR）（P Q R）（P Q R ） （P Q R） （P Q R） m6m7m3m7m3 m3m6m7 由此可见 （P Q ） （P Q R）（P （Q R） ） （Q（P R） ）3.解：A到 B的最短路径为 AB ，权为 1；A到 E的最短路径为 ABE ，权为 3；A到 F的最短路径为 ABEF ，权为 4；A到 C

37、的最短路径为 ABEFC ，权为 7；A到 D的最短路径为 ABEFCD，权为 9。 证明题 1.证明：（ （PQ ） （QR） ）（PR）（ （P Q ） （Q R） ）（P R ）（ （P Q ） （Q R） ） （P R）（PQ ） （QR）P R （ （PQ ）P ） （ （QR ） R）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 21 页，共 38 页 - - - - - - - - - 22 （1 （QP ） ） （ （Q R ） 1）QP Q R

38、（Q Q ）P R 1 P R 1 2.证明：（1）P R 规则 P （2）RP 规则 Q ，根据（ 1）（3）PQ 规则 P （4）R Q 规则 Q ，根据（ 2） （3）（5）Q R 规则 Q ，根据（ 4）（6）RS 规则 P （7）Q S 规则 Q ，根据（ 5） （6）（8）Q S 规则 Q ，根据（ 7）三、综合练习及解答（一）填空题1、集合的表示方法有两种：法和法。请把“大于 3 而小于或等于 7 的整数集合”用任一种集合的表示方法表示出来A= 。2、A，B是两个集合， A=1，2，3，4，B=2，3，5，则B-A= ， （B）（A）= ，名师归纳总结 精品学习资料 - - -

39、- - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 22 页，共 38 页 - - - - - - - - - 23 （B）的元素个数为。3、设 2, 1,BbaA，则从 A到 B的所有映射是。4、设命题公式)(RQPG，则使公式 G为假的解释是、和。5、设 G是完全二叉树， G有 15 个点，其中 8 个叶结点， 则 G的总度数为，分枝点数为。6、全集 E=1，2，3，4，5，A=1，5 ，B=1，2，3，4 ，C=2，5 ， 求 AB= ， （A）（C）= ，C= 。7、 设 A和 B是任意两个集合，若序

40、偶的第一个元素是A的一个元素，第二个元素是 B的一个元素，则所有这样的序偶集合称为集合A和 B的，记作 A B，即A B= 。A B的子集R称为 A，B上的。8、将几个命题联结起来， 形成一个复合命题的逻辑联结词主要有否名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 23 页，共 38 页 - - - - - - - - - 24 定、和等值。9、表达式x yL（x，y）中谓词的定义域是 a，b，c ，将其中的量词消除，写成与之等价的命题公式为。10、一个无向图表示

41、为G= （P，L） ，其中 P是的集合， L 是的集合，并且要求。（二）单项选择题（选择一个正确答案的代号，填入括号中）1.设命题公式)()(PRQPPG，则 G是（）。A.恒真的 B.恒假的 C.可满足的 D.析取范式2、设集合,cbaA，A上的关系),(),(),(cbbaaaR，则2R=（）。).,(),(),()();,(),(),()();,(),(),()();,(),(),()(ccbaaaDbbcabaCcbcabaBcabaaaA3、一个公式在等价意义下，下面哪个写法是唯一的（） 。A析取范式 B合取范式 C主析取范式 D以上答案都不对4、 设命题公式 G=（PQ ） ， H

42、=P（QP） ， 则 G与 H的关系是 （） 。AGH BHG CG=H D以上都名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 24 页，共 38 页 - - - - - - - - - 25 不是5、已知图 G的相邻矩阵为0111110101110001000111010，则 G有（） 。 A.5点， 8边 B. 6点， 7边 C. 5点， 7边 D. 6 点，8 边6、下列命题正确的是（） 。A = B = Caa ，b，c Da ，b，c 7、设集合 A=a

43、，b，c ，A上的关系 R=（a，b） ， （a，c） ， （b，a） ，（b，c） ， （c，a） ， （c，b） ， （c，c），则 R具有关系的（）性质。A 自反 B 对称 C 传递 D 反对称8、设 R为实数集，映射=RR， （x）= -x2+2x-1，则 是（） 。A单射而非满射 B 满射而非单射 C 双射 D既不是单射，也不是满射9、下列语句中，（）是命题。A 下午有会吗？ B 这朵花多好看呀！ C 2 是常数。 D 请把门关上。10、下面给出的一阶逻辑等价式中， （）是错的。Ax（A（x） B（x） ）= xA（x）xB（x）名师归纳总结 精品学习资料 - - - - - - -

44、 - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 25 页，共 38 页 - - - - - - - - - 26 BAxB（x）= x （AB（x） ）Cx（A（x） B（x） ）= xA（x）xB（x）DxA（x）= x（A（x） ）（三）计算题1、设 R和 S是集合4,3 ,2 ,1A上的关系，其中)4 ,4(),4,2(),3 ,2(),2, 1()4, 3(),3 ,2(),3 ,1 (),1 , 1(SR，试求：（1）写出 R和 S 的关系矩阵；（2）计算111,RSRSRSR。2、设 A=a，b，c，d，R

45、1，R2是 A上的关系，其中 R1=（a，a） ，（a，b） ， （b，a） ， （b，b） ， （c，c） ， （c，d） ， （d，c） ， （d，d），R2=（a，b） ， （b，a） ， （a，c） ， （c，a） ， （b，c） ， （c，b） ， （a，a） ， （b，b） ， （c，c）。（1） 画出 R1和 R2的关系图；（2） 判断它们是否为等价关系， 是等价关系的求 A中各元素的等价类。3、用真值表判断下列公式是恒真？恒假？可满足？（1） （PP）Q （2）（PQ ） Q （3） （ （PQ ） （Q R） ）（PR）4、设解释 I 为：（1） 定义域 D=-2，3，6；（

46、2） F（x） ：x 3；G （x） ：x 5。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 26 页，共 38 页 - - - - - - - - - 27 在解释 I 下求公式x（F（x） G （x） ）的真值。5、求下图所示权图中从u 到 v 的最短路，画出最短路并计算它们的权值。6、化简下式：（ （A B C）（A B） ） （ （A （B C） ）A）7、已知 A=1，2，3，4，5，B=1，2，3，R是 A到 B的二元关系，并且 R=（x，y）|xA且

47、 yB且 2 x+y 4，画出 R的关系图，并写出关系矩阵。8、画出下面偏序集（ A， ）的哈斯图，并指出集合A的最小元、最大元、极大元和极小元。 其中 A=a，b，c，d，e ， =（a，b） ，（a，c） ， （a，d） ， （a，e） ， （b，e） ， （c，e） ， （d，e）IA。9、求命题公式（P Q ）（P Q ）的析取范式与合取范式。10、给定解释 I 如下： V1 7 V3 12 U 2 5 3 V 46 V2 1 V4 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - -

48、- - - - - 第 27 页，共 38 页 - - - - - - - - - 28 定义域 D=2，3； f（2） f （3） F （2，2） F （2，3） F （3，2） F（3，3） 3 2 0 0 1 1 求x y（F（x，y）F（f （x） ，f （y） ） ） 。11、设有 5 个城市 v1，v2，v3，v4，v5，任意两城市之间铁路造价如下： （以百万元为单位）w（v1，v2）=4， w （v1，v3）=7， w （v1，v4）=16， w （v1，v5）=10， w （v2，v3）=13， w （v2，v4）=8， w （v2，v5）=17，w（v3，v4）=3， w （

49、v3，v5， ）=10， w （v4，v5）=12 试求出连接 5 个城市的且造价最低的铁路网。（四）证明题1、证明等价式RRPRQRQP)()()(。2、利用形式演绎法证明：,TRSTSRPQP蕴涵 Q 。3、A，B，C为任意的集合，证明：（A B） C=A （B C）4、利用一阶逻辑的基本等价式，证明：xy（F（x）G （y） ）= xF（x）yG （y）练习解答名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 28 页，共 38 页 - - - - - - -

50、- - 29 （一）填空题1、列举；描述； A=4，5，6，7或 A=x|3x 7 2、5 ；5 ，2，5 ，3 ，5 ，2 ，3，5 ；8 3、1=（a，1） ， （b，1） ；2=（a，2） ， （b，2）；3=（a，1） ，（b，2） ；4=（a，2） ， （b，1） 4、 （1，0，1） ； （1，1，1） ； （1，0，0）5、28； 7 6、5 ；，5 ；1 ，3，4 7、笛卡尔积（或直乘积） ；（x，y）|xA且 yB；二元关系8、并且（或合取）；或者（或析取）；蕴涵9、 （L（a，a） L（a，b） L（a，c） ） （L（b，a） L（b，b） L（b，c） ） （L（c，a

51、） L（c，b） L（c，c） ）10、点；连接某些不同点对的边；一对不同点之间最多有一条边（二）单项选择题（选择一个正确答案的代号，填入括号中）1、C 2、A 3、C 4、A 5、C 6、A 7、B 8、D 9、C 10、A （三）计算题1、解： （1）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 29 页，共 38 页 - - - - - - - - - 30 1000000011000010,0000100001000101SRMM（2）SR=（1，2），（

52、 3，4） SR=（1，1），（1，2），（1，3），（2，3），（2，4），（3，4），（ 4，4） 1R=（1，1），（3，1），（ 3，2），（4，3） 11RS=（2，1），（ 4，3） 2、解： R1和 R2的关系图略。由关系图可知， R1是等价关系。 R1不同的等价类有两个，即a，b和c ，d。由于 R2不是自反的，所以R2不是等价关系。3、解 ：（1） 真值表P Q P PP （PP）Q 0 0 1 0 1 0 1 1 0 0 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - -

53、- - - - - 第 30 页，共 38 页 - - - - - - - - - 31 1 0 0 0 1 1 1 0 0 0 因此公式（ 1）为可满足。（2） 真值表P Q PQ （PQ ）（PQ ）Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 因此公式（ 2）为恒假。（3） 真值表P Q R PQ QR PR （ （PQ ）（Q R） ）（PR）0 0 0 1 1 1 1 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 3

54、1 页，共 38 页 - - - - - - - - - 32 0 0 1 1 1 1 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 1 1 因此公式（ 3）为恒真。4.解：x（F（x） G （x） ）（F（-2） G （-2 ） ） （F（3） G （3） ） （F（6） G （6） ）（1 0） （1 0） （0 1） 1 5.解：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - -

55、 - - - - - - - 第 32 页，共 38 页 - - - - - - - - - 33 从 U到 V的最短路为 UV1V2V4V3V。最短路权值为9。图中圆圈中的数字为使用迪克斯特拉算法添加边的次序。6、解：（ （A B C）（A B） ） （ （A （B C） ）A）=（A B） A （利用两次吸收律）=（A B） A =（A A）（B A）= （B A）= B A 7、解：R=（1，1） ， （1，2） ， （1，3） ， （2，1） ， （2，2） ， （3，1） R的关系图为V1V3 12 U 2 3 V V2 1 V4名师归纳总结 精品学习资料 - - - - - - -

56、 - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 33 页，共 38 页 - - - - - - - - - 34 关系矩阵 MR= 1 1 1 11 0 10 0 0 0 0 0 0 0 1、解：（A， ）的哈斯图为： 1 1 2 2 33 4 5 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 34 页，共 38 页 - - - - - - - - - 35 a 为 A的极小元，也是最小元

57、；e 为 A的极大元，也是最大元。9、解：（P Q ）（P Q ）（P Q ）（P Q ） ） （ （P Q ）（P Q ） ）（ （P Q ） （P Q ） ） （ （PQ ） （PQ ） ） ）（P Q ） （PQ ）上面结果为合取范式。利用对 分配得： （P Q ） （PQ ）（PP） （PQ ） （QP） （QQ ）（PQ ） （QP）上面结果为析取范式。10、解：x y（F（x，y）F（f（x） ，f （y） ） ）x（ （F（x，2）F（f （x） ，f （2） ） ） （F（x，3）F（f e b c d a 名师归纳总结 精品学习资料 - - - - - - - - - - -

58、 - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 35 页，共 38 页 - - - - - - - - - 36 （x） ，f （3） ） ） ）（F（2，2）F（f（2） ，f（2） ） ） （F（2，3）F（f（2） ，f （3） ） ） （F（3，2）F（f（3） ，f （2） ） ） （F（3，3）F（f（3） ，f （3） ） ）（01） （01） （10） （10） 0 11、解：首先将本题用权图来描述，于是求解此题便成为求权图中的最优支撑树问题，按克鲁斯卡尔算法，下图为求解最优支撑树的过程：（a）（b）（c）（d）（e）

59、连接 5 个城市的造价最低的铁路网总造价为24（百万元）。名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 36 页，共 38 页 - - - - - - - - - 37 （四）证明题1、证明：RRRQPQPRPQQPRPQRQPRPQRQPRPRQRQP1)()()()()()()()()()()(2、证明：（1）TS规则 P （2）T规则 P （3）S规则 Q ，根据（ 1）、（ 2）和基本蕴涵式（ 12）（4）RS规则 P （5）R规则 Q ，根据（ 3）、（

60、 4）和基本蕴涵式（ 11）（6）RP规则 P （7）P规则 Q ，根据（ 5）、（ 6）和基本蕴涵式（ 12）（8）QP规则 P （9）Q规则 Q ，根据（ 7）、（ 8）和基本蕴涵式（ 10）3、证明：名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 37 页，共 38 页 - - - - - - - - - 38 （A B） C= （A B ）C = A（B C ） = A（B C） = A（B C）4、证明：x y（F（x）G （y） ）= x（F（x）y G（y） ） = x（F（x）y G（y） ） = x（F（x） ）y G（y） = xF（x）y G（y） = xF（x）yG（y）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 38 页，共 38 页 - - - - - - - - -