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

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

2、操作系统、运算机网络等；课程的主要内容1、 集合论部分（集合的基本概念和运算、关系及其性质）；2、 数理规律部分（命题规律、谓词规律）；3、 图论部分（图的基本概念、树及其性质）；学习建议离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理规律和图论）有关基本概念的精确把握，对基本原理及基本运算的运用，并要多做练习；教学要求的层次各章教学要求的层次为明白、懂得和把握；明白即能正确判别有关概念和方法；懂得是能正确表达有关概念和方法的含义；把握是在懂得的基础上加以敏捷应用；一、各章复习要求与重点第一章集合 复习学问点 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含

3、、相等、幂集2、集合的交、 并、差、补等运算及其运算律（交换律、 结合律、 安排律、 吸取律、 De Morgan律等），文氏（ Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明复习要求 学习资料精选名师 优秀名师 - - - - - - - - - -第 1 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考1、懂得集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念；2、把握集合的表示法和集合的交、并、差、补等基本运算；3、把握集合运

4、算基本规律，证明集合等式的方法；4、明白序偶与迪卡尔积的概念，把握迪卡尔积的运算； 本章重点习题 P56， 4、6； P1415，3、6、7； P20，5、7； 疑难解析 1、集合的概念由于集合的概念同学在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以把握，一是把握幂集的构成，一是把握幂集元数为2n；2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的懂得与把握；又可以为第三章命题规律中公式的基本等价式的应用打下良好的基础；实际上，本章做题是一种基本功训练，特别要求同学重视吸取律和重要等价式在ABA B 证明中的特别作用； 例题分析 例 1 设 A ，B 是两个集合

5、， A=1 ，2，3 ，B=1 ，2 ，就 A(B) ；解 A,1, 2, 3, 1,2, 1,3, 2,3, 1,2,3B ,1, 2, 1,2于是 A B 3, 1,3, 2,3, 1,2,3例 2设 Aa, b,a, b ,，试求：(1) Aa, b；2 A；3 A；4a,bA ；5A ； 6A ；解1 Aa, ba ,b ,(2) AA3 Aa,b,a, b4a, bA5A6A例 3试证明A B ABAB A B证明学习资料精选名师 优秀名师 - - - - - - - - - -第 2 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - -

6、 - - - - - - - -学习资料收集于网络，仅供参考A B ABA BA A AA B A BB AB BB A BABAB A B其次章二元关系 复习学问点 1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse）、极大 /小元、最大 /小元、上 /下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 复习要求 1、懂得关系的概念：二元

7、关系、空关系、全关系、恒等关系；把握关系的集合表示、关系矩阵和关系图、关系的运算；2、把握求复合关系与逆关系的方法；3、懂得关系的性质（自反性、对称性、反对称性、传递性），把握其判别方法（定义、矩阵、图）；4、把握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法；5、懂得等价关系和偏序关系的概念，把握等价类的求法和偏序关系做哈斯图的方法，极大/ 小元、最大 /小元、上 /下界、最小上界、最大下界的求法；6、懂得函数概念：函数、函数相等、复合函数和反函数；7、懂得单射、满射、双射等概念，把握其判别方法； 本章重点习题 P25，1； P3233，4， 8， 10； P43，2， 3， 5； P5

8、152， 5，6； P59， 1， 2； P64，学习资料精选名师 优秀名师 - - - - - - - - - -第 3 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考3； P7475， 2， 4，6， 7； P81， 5， 7； P86， 1， 2； 疑难解析 1、关系的概念关系的概念是其次章全章的基础，又是第一章集合概念的应用；因此，同学应当真正懂得并娴熟把握二元关系的概念及关系矩阵、关系图表示；2、关系的性质及其判定关系的性质既是对关系概念的加深懂得与把握，又是关系的闭包、等

9、价关系、半序关系的基础；对于四种性质的判定，可以依据教材中P49 上总结的规律；这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性；如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性；另一点是介绍一种判定传递性的“跟踪法”，即如a1 , a 2R,a2 , a3R,ai1 , aiR ，就 a1 , aiR ；如如a, bR,b, aR ，就有a , aR ，且b,bR ；、关系的闭包在懂得把握关系闭包概念的基础上，主要把握闭包的求法；关键是熟记三个定理的结论：定理2，r RRI A ；定理 3，s R1RR；定理 4，推论t RnRi

10、 ；i 1、半序关系及半序集中特别元素的确定懂得与把握半序关系与半序集概念的关键是哈斯图；哈斯图画法把握了，对于确定任一子集的最大 （小） 元，极大（小） 元也就简洁了； 这里要留意， 最大（小） 元与极大 （小） 元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为全部上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样；、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射；判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，特别是对各种初等函数； 例题分析 例 1 设集合 Aa ,b,

11、c ,d，判定以下关系，哪些是自反的，对称的，反对称的和传递的：学习资料精选名师 优秀名师 - - - - - - - - - -第 4 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考R1a, a , b, aR2a, a , b,c , d ,aR3c, dR4a, a, , b,b , c,cR5a,c , b, d解：均不是自反的； R4 是对称的； R1 ,R2 ,R3 , R4 ,R5 是反对称的； R1 ,R2 ,R 3 , R 4 ,R5 是传递的；例 2 设集合 A1

12、,2,3,4,5， A 上的二元关系R 为R1,1 ,2,2 ,3,3 ,3,4 ,4,4 ,5,3 ,5,4 ,5,5（）写出R 的关系矩阵，画出R 的关系图；（）证明R 是 A 上的半序关系，画出其哈斯图；（） 如 BA，且 B2,3,4,5，求 B 的最大元，最小元，极大元，微小元，最小上界和最大下界；解 （ 1）R 的关系矩阵为100000100000110R 的关系图略0001000111M R（ 2）由于 R 是自反的， 反对称的和传递的，所以 R 是 A 上的半序关系； A,R 为半序集，A,R 的哈斯图如下；4。 1。 3。 2。 5(3) 当 B2,3,4,5， B 的极大元

13、为2，4；微小元为2，5； B 无最大元与最小元；B也无上界与下界，更无最小上界与最大下界；第三章命题规律 复习学问点 、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题、命题公式与说明，真值表，公式分类（恒真、恒假、可满意），公式的等价学习资料精选名师 优秀名师 - - - - - - - - - -第 5 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考、析取范式、合取范式，微小（大）项，主析取范式、主合取范式、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）、

14、公式的蕴涵与规律结果、形式演绎本章重点内容： 命题与联结词、 公式与说明、 析取范式与合取范式、公式恒真性的判定、形式演绎 复习要求 、懂得命题的概念；明白命题联结词的概念；懂得用联结词产生复合命题的方法；、懂得公式与说明的概念；把握求给定公式真值表的方法，用基本等价式化简其他公式，公式在说明下的真值； 、明白析取（合取）范式的概念；懂得极大（小）项的概念和主析取（合取）范式的概念；把握用基本等价式或真值表将公式化为主析取（合取）范式的方法；、把握利用真值表、等值演算法和主析取/合取范式的唯独性判别公式类型和公式等价的方法；、懂得公式蕴涵与规律结果的概念，把握基本蕴涵式；6、把握形式演绎的证明

15、方法； 本章重点习题 P93，1； P98， 2， 3； P104，2， 3； P107， 1， 3； P112， 5； P115， 1， 2， 3； 疑难解析 1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的；详细方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观看真值表的最终一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），如不全为0，就为可满意的；二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G 是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定；这里

16、要求的析取范式中所含有的每个短语不是微小项，肯定要与求主析取范式相区分，对于合取范式也同样；2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式；关键有两点：一是学习资料精选名师 优秀名师 - - - - - - - - - -第 6 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考精确懂得把握定义；另一是奇妙使用基本等价式中的安排律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个；另外，由已经得到的主析取（合取）范式，依据GG1,GG 原理，

17、参阅离散数学学习指导书P71 例 15，可以求得主合取（析取）范式；3、形式演绎法把握形式演绎进行规律推理时，一是要懂得并把握14 个基本蕴涵式，二是会使用三个规章：规章P、规章 Q 和规章 D ，需要进行肯定的练习； 例题分析 例 1 求 GPQRP 的主析取范式与主合取范式；解 （ 1）求主析取范式， 方法 1：利用真值表求解PQRPQPQRG000010001001010010011001100011101001110111111111因此GP PQQR RPQRPQRPQRPQR方法 2：推导法学习资料精选名师 优秀名师 - - - - - - - - - -第 7 页，共 26 页

18、- - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考GPQ RRPPQRP PRQQPQRPPRQRP QRPPPQQRPQRP PQRPQ PQRPPQRPRQRPQRPQR RPQRPQRQRPQRPQR QR（ 2）求主合取范式方法 1：利用上面的真值表PQRP 为 0 的有两行， 它们对应的极大项分别为PQR,PQR因此，PQRPPQRPQR方法 2：利用已求出的主析取范式求主合取范式已用去 6 个微小项，尚有2 个微小项，即PQR 与PQR于是GPQRGGP PQRPPQRQRPQR QR例 2

19、试证明公式GPQQRPR 为恒真公式；证法一：见离散数学学习指导书P60 例 6（ 4）的解答；（真值表法）证法二：G=（P Q）（QR）（P R）=（ PQ）（ QR）P R=（ （ P Q） （ PR）（QQ ） （QR）P）R=（ P QP）（ PRP）（QRP）R=（ 1 （QRP）R=QRP R=1故 G 为恒真公式；例 3 利用形式演绎法证明 P（ QR），S P， Q 蕴涵 SR；学习资料精选名师 优秀名师 - - - - - - - - - -第 8 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - -

20、-学习资料收集于网络，仅供参考证明：（ 1）SP规章 P（ 2） S规章 D（ 3） P规章 Q，依据（ 1），（ 2）（ 4） P（ QR）规章 P（ 5） QR规章 Q，依据（ 3），（ 4）（ 6） Q规章 P（ 7） R规章 Q ，依据（ 5），（6）（ 8） SR规章 D，依据（ 2），（ 7）第四章谓词规律 复习学问点 1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、谓词公式与说明，谓词公式的类型（恒真、恒假、可满意）3、谓词公式的等价和蕴涵4、前束范式本章重点内容：谓词与量词、公式与说明、前束范式 复习要求 1、懂得谓词、量词、个体词、个体域、变元的概念；懂得用谓词

21、、量词、规律联结词描述一个简洁命题；明白命题符号化；2、懂得公式与说明的概念；把握在有限个体域下消去公式量词，求公式在给定说明下真值的方法；明白谓词公式的类型；3、懂得用说明的方法证明等价式和蕴涵式；4、把握求公式前束范式的方法； 本章重点习题 P120， 1， 2； P125126，1， 3； P137， 1； 疑难解析 1、谓词与量词反复懂得谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规章；学习资料精选名师 优秀名师 - - - - - - - - - -第 9 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - -

22、 - - - - - - - - -学习资料收集于网络，仅供参考2、公式与说明能将一阶规律公式表达式中的量词排除，写成与之等价的公式，然后将说明I 中的数值代入公式，求出真值；3、前束范式在充分懂得把握前束范式概念的基础上，利用改名规章、基本等价式与蕴涵式（一阶规律中），将给定公式中量词提到母式之前称为首标； 典型例题 例 1 设 I 是如下一个说明：D2,3F2F3P2P3Q2,2Q2,3Q3,2Q3,332011101求xy P xQ F x , y的真值；解xy P xQ F x , yxP xQ F x ,2P xQF x ,3P 2Q F2 ,2P 2QF 2 ,3P 3QF 3 ,

23、2P 3Q F3 ,300010111111例 2 试将一阶规律公式化成前束范式；解GxyP xyPx, yx, yyQ yR xyQ yR xxyPx, yzQ zR xxyz Px, yQ zR x第五章图论 复习学问点 1、图、完全图、子图、母图、支撑子图、图的同构2、关联矩阵、相邻矩阵3、权图、路、最短路径，迪克斯特拉算法（Dijkstra ）4、树、支撑树、二叉树5、权图中的最小树，克鲁斯卡尔算法（Kruskal ）学习资料精选名师 优秀名师 - - - - - - - - - -第 10 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - -

24、 - - - - - - - - -学习资料收集于网络，仅供参考6、有向图、有向树本章重点内容：权图的最短路、二叉树的遍历、权图中的最优支撑树 复习要求 1、懂得图的有关概念：图、完全图、子图、母图、支撑子图、图的同构；2、把握图的矩阵表示（关联矩阵、相邻矩阵）；3、懂得权图、路的概念，把握用Dijkstra 算法求权图中最短路的方法；4、懂得树、二叉树与支撑树的有关概念；把握二叉树的三种遍历方法，用Kruskal 算法求权图中最小树的方法；5、懂得有向图与有向树的概念； 本章重点习题 P221， 2； P225， 1；P231， 2，3； P239， 5； P242， 1，2； 疑难解析 1

25、.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简洁路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、运算机网络等课程中用到；2、权图中的最短路严格执行迪克斯特拉（Dijkstra ）算法步骤，从起点起，到每一点求出最短路，然后进行认真比较，最终到达终点，算出最小权和；3、权图中的最优支撑树权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔 （ Kruskal ）算法； 典型例题 例1在具有 n 个顶点的完全图K n 中删去多少条边才能得到树？解： n 个顶点的完全图K n 中共有 n （ n-1）/2 条边，n

26、 个顶点的树应有n-1 条边，于是，删去的边有：n （ n-1） /2-（ n-1） =（ n-1）（ n-2） /2例2求下面有限图中点u 到各点间的最短路； （图上数字见教材P231，第 3 题；）学习资料精选名师 优秀名师 - - - - - - - - - -第 11 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考解uu1 ，du, u 1=1,路u, u1uu2 ,du, u 2=9,路 u, u4, u3, u7, u2uu3 ,du, u3 =5,路 u, u4, u3

27、 ,uu4 ,du, u4 =3,路 u, u4 uu5 ,du, u5 =11,路 u, u1, u5 或路u, u4, u3 , u7 , u2 , u5uu6 ,du, u6 =13,路 u, u1, u5, u6uu7 ,du, u7 =8,路 u, u4 , u3 , u7uu8 ,du, u8 =11,路 u, u4, u8 uv,du, v=15,路u, u1, u5 , u6 ,v或路 u, u4 , u3 , u7 , u6 ,v二、考核说明本课程的考核实行形成性考核和终结性考核的形式；形成性考核占总成果的20%，以课程作业的形式进行（共三次， 由中心电大统一布置）的 80%

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

29、约占40%，数理规律约占40%，图论约占20%；详细课程考核情形见课程考核说明；附录：试题类型及规范解答举例 填空题 学习资料精选名师 优秀名师 - - - - - - - - - -第 12 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考1. 设 R是集合 A 上的二元关系，假如关系R 同时具有性、对称性和性，就称 R 是等价关系；2. 命题公式G=（ P Q）R， 就 G 共有个不同的说明；把G 在其全部说明 下所取真值列成一个表，称为G 的；说明（P，Q，R）或（ 0， 1，

30、0）使 G 的真值为；3. 设 G=（ P，L ）是图，假如G 是连通的，并且，就 G 是树；假如根树T的每个点 v 最多有两棵子树，就称T 为； 单项挑选题 （挑选一个正确答案的代号，填入括号中）1. 由集合运算定义，以下各式正确的有（）；A XXYB.XXYC.XXYD.YXY2. 设 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 个顶点组成的完全

31、图，就从G 中删去（）条边可以得到树；A 4B 5C 6D 10 运算题 1. 化简下式：（ ABC）（ AB）C）（ AB C）（ABC）2. 通过求主析取范式判定以下命题公式是否等值；（ 1）（ P Q）（P QR）；（ 2）（ P （ Q R）（ Q（P R） ；3. 求图中 A 到其余各顶点的最短路径，并写出它们的权；B7C12A253D46E1F学习资料精选名师 优秀名师 - - - - - - - - - -第 13 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考 证明题

32、 1. 利用基本等价式证明下面命题公式为恒真公式；（ PQ ）（QR）（ PR）2. 用形式演绎法证明：PQ， RS，PR 蕴涵 QS；试题答案及评分标准 填空题 1、自反；传递2、8；真值表； 13、无回路；二叉树 单项挑选题 （挑选一个正确答案的代号，填入括号中） 1、 A2、 B3、C 运算题 1. 解：（ ABC）（ AB）C）（ AB C）（ABC）=（ ABC）（ ABC）（ ABC ）（ ABC）=（ AB）（ CC）（ AB ）（CC）=（ AB）E）（ AB）E）E 为全集=（ AB）（ AB）=A（ BB）=AE=A2. 解：（P Q）（P QR）（ P Q（RR）（P Q

33、R）（ P QR）（ P QR）（P QR） m6m7m3m3m6m7（P （QR）（ Q（P R）（ P Q）（ Q R）（ PP R）（PQR）（安排律）学习资料精选名师 优秀名师 - - - - - - - - - -第 14 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考（ P Q（RR）（P P）QR） （PQR）（ P QR）（ P QR）（P QR）（P QR）（PQR）m6m7m3m7m3m3m6由此可见m7（PQ） （PQR）（ P （ QR）（ Q（PR）3. 解

34、：A 到 B 的最短路径为AB ，权为 1； A 到 E 的最短路径为ABE ，权为 3；A 到 F 的最短路径为ABEF ，权为 4； A 到 C 的最短路径为ABEFC ，权为 7；A 到 D 的最短路径为ABEFCD ，权为 9； 证明题 1. 证明：（ PQ）（ QR）（PR）（P Q）（QR）（P R）（P Q）（QR）（P R）（ PQ）（ QR）P R（ PQ）P ）（ QR）R）（ 1（QP ）（ QR）1） QP QR（QQ）PR1PR 12. 证明：（ 1）P R规章 P（ 2）RP规章 Q ，依据（ 1）（ 3）PQ规章 P（ 4）RQ规章 Q，依据（ 2）（3）（ 5）

35、QR规章 Q，依据（ 4）（ 6）RS规章 P学习资料精选名师 优秀名师 - - - - - - - - - -第 15 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考（ 7）QS规章 Q，依据（ 5）（ 6）（ 8）QS规章 Q ，依据（ 7）三、综合练习及解答（一）填空题1、集合的表示方法有两种：法和法；请把“大于3而 小 于 或 等 于7的 整 数 集 合 ” 用 任 一 种 集 合 的 表 示 方 法 表 示 出 来A= ；2、 A ，B 是两个集合， A=1 ，2，3， 4

36、 ，B=2 ，3，5 ，就 B-A=， （ B）（ A ） =， （ B）的元素个数为；3、 设 A a ,b,B1,2，就从 A 到 B 的全部映射是；4、 设命题公式GPQR ，就使公式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 是任意两个集合，如序偶的第一个元素是A 的一个元素，其次个元素是B 的一个元素，就全部这样的序偶集合称为集合A 和 B

37、 的，记作 AB，即 AB=；AB 的子集 R 称为 A ， B 上的；8、将几个命题联结起来，形成一个复合命题的规律联结词主要有否定、和等值；9、表达式xyL （ x ， y）中谓词的定义域是a ， b， c ，将其中的量词排除，写成与之等价的命题公式为；10、一个无向图表示为G= （ P， L ），其中 P 是的集合， L 是学习资料精选名师 优秀名师 - - - - - - - - - -第 16 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考的集合，并且要求；（二）单项挑选题

38、（挑选一个正确答案的代号，填入括号中）1.设命题公式 GPPQR) P ，就 G 是（）；A. 恒真的B. 恒假的C.可满意的D. 析取范式2、设集合A a,b , c， A 上的关系 R a ,a , a,b , b, c ，就R2 =（）； A a, a , a,b , a,c;C a, b , a,c, b,b ; B a, b, a, c, b, c; D a, a , a, b, c, c .3、一个公式在等价意义下，下面哪个写法是唯独的（）；A 析取范式B合取范式C主析取范式D以上答案都不对4、设命题公式G=（ PQ ）， H=P（ QP），就 G 与 H 的关系是（）；A GHB

39、 HGCG=HD以上都不是01011100015、已知图G 的相邻矩阵为00011，就 G 有（）；1010111110A.5 点， 8 边B. 6 点， 7 边C. 5 点， 7 边D. 6 点， 8 边6、以下命题正确选项（）；A =B=C aa ， b， cD a ， b， c7、设集合A=a ，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 ） = -x 2+2x-1 ，就是（）；A 单射而非满射B满射而非单射

40、C双射D 既不是单射，也不是满射 9、以下语句中， （）是命题；A 下午有会吗？B 这朵花多好看呀！C 2 是常数；D 请把门关上； 10、下面给出的一阶规律等价式中，（）是错的；A x（A （x ）B（ x） =xA （x ）xB （ x） B AxB （ x ）=x （ AB（ x ）学习资料精选名师 优秀名师 - - - - - - - - - -第 17 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考Cx （ A （ x ）B（ x） = xA （x）xB （ x ） DxA

41、 （ x ） = x （A（ x）（三）运算题1、设 R 和 S 是集合 A1,2,3,4R上的关系，其中S 1,1, 1,3, 2,3, 3,4 1,2, 2,3, 2,4, 4,4，试求：（ 1）写出 R 和 S 的关系矩阵；（ 2）运算R S,RS,R 1 ,S 1R 1 ；2、 设 A=a ，b，c，d ，R1，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），

42、（c， c） ；（ 1）画出 R1 和 R2 的关系图；（ 2）判定它们是否为等价关系，是等价关系的求A 中各元素的等价类；3、 用真值表判定以下公式是恒真？恒假？可满意？（ 1）（ PP）Q（ 2）（ PQ）Q（ 3）（ PQ）（ QR）（PR）4、 设说明 I 为：（ 1）定义域D=-2 ， 3，6 ；（ 2） F（ x ）： x 3； G（ x ）：x5；在说明 I 下求公式x （ F（ x）G（x ）的真值；5、 求下图所示权图中从u 到 v 的最短路，画出最短路并运算它们的权值；学习资料精选名师 优秀名师 - - - - - - - - - -第 18 页，共 26 页 - - - - - - - - - -精品word 名师归纳总结 - - - - - - - - - - - -学习资料收集于网络，仅供参考V 17V 312U253V46V 21V 46、 化简下式：（ ABC）（ AB）（ A（ B C）A ）7、 已知 A=1 ， 2， 3， 4，5 ，B=1 ， 2， 3 ， R 是 A 到 B 的二元关系，并且R= （ x， y）|xA 且 yB 且 2x+y4 ，画出 R 的关系图，并写出关系矩阵；8、 画出下面偏序集（A ， ）的哈斯图，并指出集合A 的最小元、最大元、极大元和微小 元