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

离散数学期末复习提要离散数学期末复习提要离散数学是中央电大“数学与数学应用专业”（本科)的一门选修课.该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容(主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的离散数学（刘叙华等编）和离散数学学习指导书（虞恩蔚等编）.离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练,提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。课程的主要内容课程的主要内容1、集合论部分(集合的基本概念和运算、关系及其性质）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本概念、树及其性质）。学习建议学习建议离散数学是理论性较强的学科，学习离散数学的关键是对离散数学(集合论、数理逻辑和图论）有关基本概念的准确掌握,对基本原理及基本运算的运用，并要多做练习。教学要求的层次教学要求的层次各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。一、各章复习要求与重点一、各章复习要求与重点第一章第一章 集集合合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan律等），文氏（Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明复习要求11、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念.2、掌握集合的表示法和集合的交、并、差、补等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。本章重点习题P56，4、6；P1415，3、6、7;P20，5、7.疑难解析1、集合的概念因为集合的概念学生在中学阶段已经学过,这里只多了一个幂集概念，重点对幂集加以掌握,一是掌握幂集的构成，一是掌握幂集元数为2n。2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在A B A B证明中的特殊作用.例题分析例 1 设 A，B 是两个集合，A=1，2，3,B=1，2，则(A)(B)。解(A),1,2,3,1,2,1,3,2,3,1,2,3(B),1,2,1,2于是(A)(B)3,1,3,2,3,1,2,3例 2设A a,b,a,b,试求：(1）Aa,b；(2）A；（3)A；（4）a,b A;(5）A;(6）A。解(1)Aa,b a,b,（2)A A(3)Aa,b,a,b(4)a,b A （5）A （6）A 例 3试证明A B A BA B A B证明2A B A BA B AA B BA A B AA B B B A BA BA B A B第二章第二章 二元关系二元关系复习知识点1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念复习要求1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算.2、掌握求复合关系与逆关系的方法。3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法(定义、矩阵、图)。4、掌握求关系的闭包(自反闭包、对称闭包、传递闭包)的方法。5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。6、理解函数概念:函数、函数相等、复合函数和反函数。7、理解单射、满射、双射等概念，掌握其判别方法.本章重点习题P25，1；P3233，4，8，10；P43，2,3,5；P5152，5，6；P59，1，2；P64，3；3P7475,2，4，6，7；P81,5，7；P86，1，2.疑难解析1、关系的概念关系的概念是第二章全章的基础,又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49 上总结的规律。这其中对传递性的判定,难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性,但是不具有自反性.另一点是介绍一种判定传递性的“跟踪法”,即若a1,a2 R,a2,a3 R,ai1,ai R，则a1,ai R。如若a,bR,b,aR，则有a,aR，且b,b R.、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论:定理 2，rR R IA；定理 3，sR R R;定理 4，推论tR1Ri1ni。、半序关系及半序集中特殊元素的确定理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小)元也就容易了。这里要注意,最大（小)元与极大(小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。例题分析例 1 设集合A a,b,c,d，判定下列关系,哪些是自反的，对称的，反对称的和传递的：R1 a,a,b,aR5 a,c,b,dR2 a,a,b,c,d,aR3 c,dR4 a,a,b,b,c,c4解：均不是自反的;R4是对称的;R1,R2,R3，R4，R5是反对称的;R1,R2，R3,R4，R5是传递的。1,2,3,4,5，A 上的二元关系 R 为例 2 设集合AR1,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 的关系矩阵为10MR000000010000110R 的关系图略00100111(2）因为 R 是自反的，反对称的和传递的,所以 R 是 A 上的半序关系。（A,R)为半序集，（A,R）的哈斯图如下。4。1。3.2。5（3）当B2,3,4,5,B 的极大元为 2,4；极小元为 2，5；B 无最大元与最小元；B也无上界与下界，更无最小上界与最大下界。第三章第三章命题逻辑命题逻辑复习知识点、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题、命题公式与解释,真值表，公式分类（恒真、恒假、可满足)，公式的等价、析取范式、合取范式，极小（大）项，主析取范式、主合取范式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、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前6一步适当使用等幂律，使相同的短语（或子句）只保留一个。另外,由已经得到的主析取（合取）范式，根据G G 1,G G原理，参阅离散数学学习指导书P71 例 15，可以求得主合取(析取）范式.3、形式演绎法掌握形式演绎进行逻辑推理时，一是要理解并掌握 14 个基本蕴涵式，二是会使用三个规则：规则 P、规则 Q 和规则 D,需要进行一定的练习。例题分析例 1 求G P Q R P的主析取范式与主合取范式。解（1）求主析取范式，方法 1:利用真值表求解PQR000001010011100101110111因此P Q00000011P Q R10101011G01011111G P Q RP Q RP Q RP Q RP Q RP Q R方法 2：推导法7G P QR R P P Q R PP Q R P P RQ R PP RQ QQ RP PP Q QR RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q RP Q R（2）求主合取范式方法 1:利用上面的真值表P Q R P为 0 的有两行,它们对应的极大项分别为P Q R,因此，P Q R P P Q RP Q R方法 2：利用已求出的主析取范式求主合取范式已用去 6 个极小项，尚有2 个极小项，即P Q R与P Q R于是G P Q RP Q RG G P Q RP Q RPQ RP Q R例 2 试证明公式G P QQ RP R为恒真公式。证法一：见离散数学学习指导书P60 例 6（4)的解答.（真值表法）证法二：G=（PQ）(QR）（PR）=（PQ）(QR）PR=（PQ）(PR）（QQ）（QR）P）R=（PQP）（PRP）(QRP)）R=（1（QRP）R=QRPR=1故 G 为恒真公式。例 3 利用形式演绎法证明 P(QR），SP,Q蕴涵 SR。8P Q R证明：（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、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型.3、理解用解释的方法证明等价式和蕴涵式.4、掌握求公式前束范式的方法.本章重点习题P120,1，2；P125126,1，3；P137，1。疑难解析1、谓词与量词反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。92、公式与解释能将一阶逻辑公式表达式中的量词消除,写成与之等价的公式，然后将解释I 中的数值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标.典型例题例 1 设 I 是如下一个解释：D 2,3F（2)F(3)P(2）P(3）Q（2，2)Q（2,3)Q（3,2）32011101求xyPxQFx,y的真值.解xyPxQFx,y xPxQFx,2PxQFx,3P2QF2,2P2QF2,3P3QF3,2P3QF3,300011111 011例 2 试将一阶逻辑公式化成前束范式。解G xyPx,yyQy Rx xyPx,yyQy Rx xyPx,yzQz Rx xyzPx,y Qz Rx第五章第五章 图论图论复习知识点1、图、完全图、子图、母图、支撑子图、图的同构2、关联矩阵、相邻矩阵3、权图、路、最短路径，迪克斯特拉算法(Dijkstra）4、树、支撑树、二叉树5、权图中的最小树,克鲁斯卡尔算法(Kruskal）10Q（3，3)6、有向图、有向树本章重点内容：权图的最短路、二叉树的遍历、权图中的最优支撑树复习要求1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。2、掌握图的矩阵表示（关联矩阵、相邻矩阵）.3、理解权图、路的概念，掌握用Dijkstra 算法求权图中最短路的方法。4、理解树、二叉树与支撑树的有关概念；掌握二叉树的三种遍历方法，用Kruskal 算法求权图中最小树的方法.5、理解有向图与有向树的概念.本章重点习题P221，2；P225,1；P231,2，3；P239，5;P242,1，2.疑难解析1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。2、权图中的最短路严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点,算出最小权和。3、权图中的最优支撑树权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal)算法.典型例题例1在具有 n 个顶点的完全图Kn中删去多少条边才能得到树?解:n 个顶点的完全图 Kn中共有 n（n-1）/2 条边,n 个顶点的树应有 n-1 条边，于是，删去的边有：n（n-1)/2（n1)=（n-1）（n2）/2例2求下面有限图中点 u 到各点间的最短路。(图上数字见教材 P231，第 3 题。)11解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)u u5，d（u，u5）=11,路(u，u1,u5)或路（u,u4,u3，u7,u2，u5）u u6,d(u,u6）=13，路(u,u1，u5,u6）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。总成绩为 100 分，60 分及格.期末考试实行全国统一闭卷考核，试卷满分为 100。由中央电大统一命题，统一评分标准，统一考试时间(考试时间为 120 分钟）.1、试题类型试题类型有填空题（分数约占20）、单项选择题(分数约占 14）、计算题(分数约占50）和证明题（分数约占16）。填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由.证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。2、考核试卷题量分配试卷题量在各部分的分配是：集合论约占40%，数理逻辑约占40，图论约占20%。具体课程考核情况见课程考核说明。附录：试题类型及规范解答举例附录：试题类型及规范解答举例填空题121.设 R是集合 A 上的二元关系，如果关系 R 同时具有性、对称性和性，则称 R 是等价关系.2.命题公式 G=(PQ）R，则 G 共有个不同的解释；把 G 在其所有解释下所取真值列成一个表,称为 G 的；解释（P，Q，R）或（0，1，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 个顶点组成的完全图,则从 G 中删去（）条边可以得到树.A4B5C6D10计算题1.化简下式：（ABC）（AB)C)（ABC）（ABC）2.通过求主析取范式判断下列命题公式是否等值。（1)（PQ）（PQR);(2)（P（QR）)（Q（PR）)；3.求图中 A 到其余各顶点的最短路径，并写出它们的权。B7C12A253D4E1F136证明题1.利用基本等价式证明下面命题公式为恒真公式。（PQ）（QR）(PR）2.用形式演绎法证明:PQ，RS，PR 蕴涵 QS。试题答案及评分标准试题答案及评分标准填空题1、自反；传递2、8；真值表；13、无回路；二叉树单项选择题（选择一个正确答案的代号，填入括号中）1、A2、B3、C计算题1.解：（ABC）（(AB）C)（ABC）(ABC)=（ABC)（ABC）(ABC）（ABC）=(AB）（CC）(（AB）（CC）=（AB）E）（AB）E）E 为全集=（AB）（AB）=A（BB）=AE=A2.解:（PQ）（PQR)(PQ（RR）(PQR）（PQR)（PQR）(PQR）m6m7m3m3m6m7（P（QR）(Q（PR）（PQ）(QR）（PPR）（P Q R）（PQ（RR）（PP）QR）(P Q R）14(分配律）(PQR）(PQR)(PQR）(PQR）（P Q R）m6m7m3m7m3m3m6m7由此可见（PQ)（PQR）（P（QR）（Q（PR）3.解：A 到 B 的最短路径为 AB，权为 1；A 到 E 的最短路径为 ABE，权为 3；A 到 F 的最短路径为 ABEF,权为 4；A 到 C 的最短路径为 ABEFC，权为 7；A 到 D 的最短路径为 ABEFCD，权为 9.证明题1.证明：（(PQ）(QR）（PR）（PQ）(QR）（PR)(（PQ)（QR）（PR）（PQ）（QR）PR（PQ）P）(（QR)R）（1(QP)）（QR）1)QPQR（QQ）P R1 P R12.证明：（1）PR规则 P（2）RP规则 Q,根据（1）（3）PQ规则 P（4）R Q规则 Q,根据（2）（3)（5）QR规则 Q,根据(4）（6）RS规则 P（7）QS规则 Q,根据（5)（6)15（8）QS规则 Q，根据（7）三、三、综合练习及解答综合练习及解答（一（一)填空题填空题1、集合的表示方法有两种:法和法。请把“大于3 而小 于 或 等 于7 的 整 数 集 合”用 任 一 种 集 合 的 表 示 方 法 表 示 出 来A=。2、A，B 是两个集合，A=1，2，3，4，B=2，3,5，则 B-A=,（B)（A）=，（B）的元素个数为。3、设A a,b,B 1,2,则从 A 到 B 的所有映射是。4、设命题公式G P (Q R)，则使公式 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 的，记作 AB,即 AB=。AB 的子集 R 称为 A，B 上的.8、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、和等值.9、表达式xyL（x，y）中谓词的定义域是a，b，c，将其中的量词消除，写成与之等价的命题公式为。10、一个无向图表示为G=（P，L)，其中 P 是的集合，L 是的集合,并且要求16。（二）单项选择题（二）单项选择题(选择一个正确答案的代号，填入括号中）选择一个正确答案的代号，填入括号中）1.设命题公式G (PP)(Q R)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 的关系是（）。AGHBHGCG=HD以上都不是015、已知图 G 的相邻矩阵为011101100010011,则 G 有（）.01011110A。5 点，8 边B.6 点,7 边C.5 点,7 边D.6 点，8 边6、下列命题正确的是（）。A=B=C aa，b，cDa，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）=x2+2x-1，则是（）。A单射而非满射B满射而非单射C双射D既不是单射，也不是满射9、下列语句中，（)是命题.A下午有会吗？B这朵花多好看呀！C2 是常数.D请把门关上。10、下面给出的一阶逻辑等价式中，（)是错的。A x（A(x）B（x)）=xA（x）xB（x）B AxB（x）=x（AB（x）C x（A(x）B（x）=xA（x）xB（x）17D xA（x）=x（A（x)(三）计算题三）计算题1、设R和S是集合A 1,2,3,4上的关系,其中写出 R 和 S 的关系矩阵；（2)计算RS,R(1,1),(1,3),(2,3),(3,4),试求：（1）S(1,2),(2,3),(2,4),(4,4)RS,R1,S1R1。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），（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):x3；G(x）:x5.在解释 I 下求公式x（F(x)G（x）)的真值。5、求下图所示权图中从 u 到 v 的最短路，画出最短路并计算它们的权值。V17V312U253V4V21V46186、化简下式：（ABC）（AB）（A（BC）)A）7、已知 A=1,2，3，4,5，B=1，2,3,R 是 A 到 B 的二元关系，并且 R=（x，y）xA 且 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、求命题公式(PQ）（PQ)的析取范式与合取范式。10、给定解释 I 如下：定义域 D=2,3；f（2）f（3)F(2,2）F(2，3）F（3，2)F(3，3)320011求xy（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(v3，v5，)=10，w（v4,v5）=12试求出连接 5 个城市的且造价最低的铁路网。(四）证明题四）证明题1、证明等价式(P(Q R)(Q R)(P R)R。2、利用形式演绎法证明：PQ,3、A，B,C 为任意的集合，证明：（AB）C=A(BC）4、利用一阶逻辑的基本等价式，证明:xy（F（x）G（y)）=xF(x）yG（y)练习解答练习解答（一（一)填空题填空题1、列举;描述；A=4,5，6,7或 A=x3x719P R,S T,S R,T蕴涵 Q.2、5；5，2，5，3，5，2，3，5 ；83、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；76、5；，5；1，3,47、笛卡尔积(或直乘积）；（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)L（c,b）L（c,c）10、点；连接某些不同点对的边；一对不同点之间最多有一条边（二（二)单项选择题（选择一个正确答案的代号，填入括号中单项选择题（选择一个正确答案的代号，填入括号中)1、C2、A3、C4、A5、C6、A7、B8、D9、C10、A（三）计算题（三）计算题1、解：（1）10MR00010010,00100000MS00100011000001（2)RS=(1,2），（3，4)RS=（1，1)，（1,2），（1，3），(2，3），(2，4），（3，4），(4，4）R=（1,1），（3，1），（3，2）,（4，3）S2、解：R1和 R2的关系图略。由关系图可知，R1是等价关系。R1不同的等价类有两个，即a，b和c，d。由于 R2不是自反的，所以R2不是等价关系。3、解：2011R1=（2，1），（4，3）（1）真值表PQ00011011PPP（PP）Q101100001000因此公式（1)为可满足。（2）真值表PQ00011011PQ(PQ)（PQ）Q100100010100因此公式（2）为恒假。（3）真值表PQR000001010011100101110111PQQRPR（PQ)（QR）(PR）11111111101111110101011110011111因此公式（3）为恒真。4.解:x（F(x）G（x）)（F（2）G（2）(F(3）G（3）（F（6）G（6)）（10）（10）（01）2115.解：V1V312U 2 3 V V2 1 V4从 U 到 V 的最短路为 UV1V2V4V3V。最短路权值为 9。图中圆圈中的数字为使用迪克斯特拉算法添加边的次序.6、解：(（ABC）（AB)）(（A（BC）)A）=（AB)A(利用两次吸收律)=（AB)A=(A A）（B A)=（B A）=B A7、解:R=(1,1),(1,2）,(1,3），（2，1)，（2，2），（3，1）R 的关系图为11223345关系矩阵 MR=111110221000000001、解：（A，）的哈斯图为：ebcdaa 为 A 的极小元，也是最小元；e 为 A 的极大元，也是最大元。9、解：（PQ）(PQ）(（PQ）（PQ)）（PQ）（PQ）（PQ)（PQ)）（PQ）(PQ）)（PQ)（PQ）上面结果为合取范式。利用对分配得：(PQ）（PQ）(PP）(PQ）（QP）（QQ）（PQ）（QP）上面结果为析取范式。10、解：xy（F（x,y）F（f（x），f（y）x（F（x,2）F（f（x），f(2)）（F（x，3）F（f（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）23 011、解：首先将本题用权图来描述,于是求解此题便成为求权图中的最优支撑树问题，按克鲁斯卡尔算法,下图为求解最优支撑树的过程:（a）(b)（c)(d）(e）连接 5 个城市的造价最低的铁路网总造价为24(百万元）。(四）证明题四）证明题1、证明：(P(Q R)(Q R)(P R)(P(Q R)(Q P)R)(PQ)R)(Q P)R)(PQ)(Q P)R(PQ)(PQ)R1 R R2、证明：（1）S T规则 P（2）T规则 P（3)S规则 Q，根据（1）、（2）和基本蕴涵式（12）24(4）S R规则 P（5）R规则 Q，根据(3）、(4)和基本蕴涵式（11）（6）P R规则 P（7）P规则 Q,根据（5）、(6）和基本蕴涵式（12）（8）PQ规则 P（9)Q规则 Q，根据（7）、（8）和基本蕴涵式（10）3、证明:（AB）C=（AB)C=A(BC）=A（BC）=A（BC)4、证明:xy（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）25