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

1、精品文档离散数学（第三版）方世昌 的期末复习知识点总结含例题一、各章复习要求与重点第一章集 合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幕集2、 集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan 律等），文氏（Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明复习要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、幕集等基本概念。2、掌握集合的表示法和集合的交、并、差、补等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运

2、算。疑难解析1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幕集概念，重点对幕集加以掌握，一是掌握幕集的构成，一是掌握幕集元数为2no2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在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、) 3, 1,3, 2,3, 1,2,3 例 2 设 A a,b, a,b , ，试求：(1)A a,b ； (2) A ； (3)A ；(4) a,bA； (5)A； (6) A 。解 (1) A a,ba,b ,(2) AA (3) Aa,b,a,b(4) a,b A(5) A(6)A例 3 试证明 AB A BABA B证明A BABABAA BBAAB A AB B BABABAB A B第二章 二元关系 复习知识点 1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、 偏

4、序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映 射的概念 复习要求 1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系 矩阵和关系图、关系的运算。2、掌握求复合关系与逆关系的方法。3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩 阵、图）。4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。5、理解等价关系和偏序关系的概念， 掌握等价类的求法和偏序关系做哈斯

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、关系的概念 关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正 理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定 关系的性质既是对关系概念的

6、加深理解与掌握，又是关系的闭包、等价关系、半序关 系的基础。对于四种性质的判定，可以依据教材中 P49 上总结的规律。这其中对传递性的 判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如 空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介 绍一种判定传递性的 “跟踪法” ，即若 a1,a2 R, a2,a3 R, , ai 1,ai R ，则 a1, ai R。如若 a, b R, b, a R，则有 a,a R，且 b,b R。3、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结n论：定理 2， r

7、R R IA ；定理 3， s R R R 1；定理 4，推论 t RRi 。i14、半序关系及半序集中特殊元素的确定理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任 一子集的最大 （小）元，极大（小）元也就容易了。 这里要注意， 最大（小）元与极大 （小） 元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同 样。5、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于 关系图，而实数集的子集上的映射也可以利用直角坐

8、标系表示进行，尤其是对各种初等函 数。 例题分析 例1 设集合 A a,b,c,d ，判定下列关系，哪些是自反的，对称的，反对称的和传递的：R1 a,a, b,a R2 a,a , b,c , d,a R3 c,d R4 a,a, b,b , c,cR5 a,c, b,d解：均不是自反的；R4是对称的；R1 ,R2 ,R3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5是传递的。 例2设集合A 1,234,5，A上的二元关系 R为R 1,1 , 2,2 , 3,3 , 3,4, 4,4, 5,3,5,4,5,5(1) 写出R的关系矩阵，画出 R的关系图；(2) 证明R是A上

9、的半序关系，画出其哈斯图；(3) 若B A，且B 2,3,4,5，求B的最大元，最小元，极大元，极小元，最小上界 和最大下界。解(1) R的关系矩阵为1000001000M R 00110R 的关系图略0001000111( 2)因为 R 是自反的， 反对称的和传递的， 所以 R 是 A 上的半序关系。 (A,R) 为半序集，(A,R) 的哈斯图如下。4。1。3。2。5（3）当B 2,3,4,5 , B的极大元为2, 4;极小元为2, 5; B无最大元与最小元；B也无上界与下界，更无最小上界与最大下界。第三章命题逻辑复习知识点1、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题2、命题公

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

11、公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/ 合取范式的唯一性判别公式类型和公式等价的方法。5、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。6、掌握形式演绎的证明方法。本章重点习题P93, 1 ;P98,2,3;P104, 2, 3;P107,1,3;P112, 5;P115,1 ,2,3。疑难解析1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。二是推导法，即利用基

12、本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至 少包含一个原子及其否定。这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区 别，对于合取范式也同样。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是 准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前 一步适当使用等幕律，使相同的短语（或子句）只保留一个。另外，由已经得到的主析取（合取）范式，根据 G G 1,G G原理，参阅离散数学学习指导书P71例15,可以求得主合取

13、（析取）范式。3、形式演绎法掌握形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则 P、规则Q和规则D，需要进行一定的练习。例题分析例1求G P Q RP的主析取范式与主合取范式。解（1 ）求主析取范式，方法1 ：利用真值表求解P Q RP QP QRG0 0 00100 0 10010 1 00100 1 10011 0 00111 0 10011 1 01111 1 1111因此GPQRP QRPQRPQ R P QRP Q R方法2:推导法GPQ RRPP QRPPQ RPPRQRPPRQQQ RPPPQ QRRPQ RPQRPQRPQ RPQ R PQR

14、PQRPQRPQ RPQRPQRP Q RPQRPQR（2）求主合取范式方法1利用上面的真值表P Q R P为0的有两行，它们对应的极大项分别为 P Q R, P Q R因此， PQ R PPQRPQR方法2:利用已求出的主析取范式求主合取范式已用去6个极小项，尚有2个极小项，即PQR与PQR 于:曰是GPQRPQRGGPQRP QRP QRPQR例2试证明公式GPQQRPR为恒真公式。证法一： 见离散数学学习指导书P60例6（ 4）的解答。（真值表法）证法G= （ P Q）（ Q R ） （P R )=( P Q) ( QR）PR=（ P Q） （P R ) (QQ） （Q R ）P) R=

15、（ P Q P）（PRP）（QR P ) R=( 1 ( Q RP）R= Q R P R=1故 G 为恒真公式。例3 利用形式演绎法证明 P（QR），S P，Q 蕴涵S R 。证明：1）SP规则P2）S规则D3）P规则Q，根据（1），（ 2）4）P（ Q R）规则P5）QR规则Q，根据（3），（ 4 ）6）Q规则P7）R规则Q，根据（5），（ 6 ）8）SR规则D，根据（2），（ 7 ）第四章 谓词逻辑 复习知识点 1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）3、谓词公式的等价和蕴涵4、前束范式本章重点内容：谓词与量词、公式

16、与解释、前束范式 复习要求 1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述 一个简单命题；了解命题符号化。2、理解公式与解释的概念； 掌握在有限个体域下消去公式量词， 求公式在给定解释下真值 的方法；了解谓词公式的类型。3、理解用解释的方法证明等价式和蕴涵式。4、掌握求公式前束范式的方法。本章重点习题P120, 1， 2；P125126， 1， 3；P137, 1。疑难解析1、谓词与量词反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、 约束性与改名规则。2、公式与解释I中的数能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后

17、将解释 值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶 逻辑中），将给定公式中量词提到母式之前称为首标。典型例题例1设I是如下一个解释：D 2,3FF(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)3201 1101求x yPxQFx ,y的真值。解x yP xQ F x , yx P xQ F x ,2P xQ F x ,3P 2 QF 2 ,2P 2 QF 2 ,3P3 QF 3 ,2P 3 QF 3 ,30 0 (0 1 11 11例2试将一阶逻辑公式化成前束范式。GxyP x,yyQ yRxxyP x,

18、yy Q yRxxyP x,yz Q zRxxy zP x,yQzRx第五章 图论 复习知识点 1、图、完全图、子图、母图、支撑子图、图的同构2、关联矩阵、相邻矩阵3、权图、路、最短路径，迪克斯特拉算法(Dijkstra )4、树、支撑树、二叉树5、权图中的最小树，克鲁斯卡尔算法(Kruskal )6、有向图、有向树本章重点内容： 权图的最短路、二叉树的遍历、权图中的最优支撑树 复习要求 1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。2、掌握图的矩阵表示(关联矩阵、相邻矩阵)。3、理解权图、路的概念，掌握用Dijkstra 算法求权图中最短路的方法。4、理解树、二叉树与支撑

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

20、中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔(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到各点间的最短路。(图上数字见教材P231，第3题。)解 uU1，d(u, U1)=1,路(U, U1)uU2 ,d(u, U2)=9,路(u, U4, U3, U7, U2)uU3 ,d(u, U3)=5,路(u, U4, U3 ,)uU4 ,d(u, U4)=3

21、,路(U, U4 )uU5 ,d(u, U5)=11,路(U, U1, U5)或路 (U, U4, U3 , U7 , U2 , U5)uU6 ,d(u, U6)=13,路(U, U1, U5, U6)uU7 ,d(u, U7)=8,路(U, U4 , U3 , U7)uU8 ,d(u, U8)=11,路(U, U4, U8)uv,d(u, v)=15,路(U, U1, U5 , U6 ,V)或路(U, U4 , U3 , U7 , U6 ,v)二、考核说明本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的 20%,以课程作业的形式进行(共三次，由中央电大统一布置)；终结性考核

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

23、%，数理逻辑约占40%，图论约占20%。具体课程考核情况见课程考核说明。附录：试题类型及规范解答举例填空题1.设R是集合A上的二元关系，如果关系R同时具有性、对称性和性,则称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.由集合运算定义，下列各式正确的有（）。2.3.B.X X Y C.X X YD.Y X Y设R1

24、, R2是集合A=a , b, c, d上的两个关系，其中c),( d, d) , R2= (a, a),(b, b) ,( b,R2是Ri的（A 自反）闭包。B.对称C .传递R1= (a, a),(b, b) ,(b,c),( c, b),( d, d) ，则D .以上都不是设G是由5个顶点组成的完全图,则从 G中删去（）条边可以得到树。B. 5D. 10计算题1. 化简下式:(ABC)( A B) C)(A B C)(A2. 通过求主析取范式判断下列命题公式是否等值。(1) ( P Q)( P Q R)；(2) ( P (Q R)(Q ( PR)；3. 求图中A到其余各顶点的最短路径，并

25、写出它们的权。B7C1 2E1F证明题1. 利用基本等价式证明下面命题公式为恒真公式。(P Q)(Q R)(P R)2. 用形式演绎法证明：P Q, R S, PR 蕴涵Q试题答案及评分标准填空题1、自反；传递2、8 ;真值表；13、无回路；二叉树单项选择题(选择一个正确答案的代号，填入括号中)1、A2、 B3、C计算题1. 解：(ABC)( A B) C)(A B C)(A=(A B C)(A B C)(A B C)=(A B)( C C)( A B)( CSoB C)(A B C)C)=(A B) E)( A B) E)E为全集=（A B） （ A B）= A （ B B）= AE= A2

26、. 解：P Q ） （ P Q R）P Q （ R R） （ P Q R）P Q R） （ P Q R） （ P Q R）m6 m7 m3m3 m6m7由此可见Q）PQR）P （ Q R）Q （ P R）P（QR） （ Q（ P R）PQ）（ Q R） （P P R ）（P QR）（分配律）PQ（R R ）（ P P）QR）（PQ R）PQR） （ P QR） （ PQR） （PQR） （P Q R ）m3 m6 m7m6 m7m3m7m33. 解：A 到 B 的最短路径为 AB ，权为 1；A 到 E 的最短路径为 ABE ，权为 3 ；A 到 F 的最短路径为 ABEF ，权为 4；A 到

27、 C 的最短路径为 ABEFC ，权为 7；A 到 D 的最短路径为 ABEFCD ，权为 9。证明题1. 证明：（PQ）（QR）（ P R）（P Q）（Q R ）（ P R ）（PQ） （Q R ） （ P R）PQ）（QR）PR（ P Q） P ） （ Q R） R）(1( Q P )Q P Q R(Q Q) PR1 P R12. 证明：(1) P R(2) RP(3) P Q(4) RQ(5) QR(6) R S(7) QS(8) Q S(Q R)1)规则P规则Q ,根据(1)规则P规则Q,根据(2)( 3)规则Q,根据(4)规则P规则Q,根据(5)( 6)规则Q ,根据(7)三、综合练

28、习及解答(一) 填空题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，求 A B=,(A )( C) =, C=。7、设A和B是任意两个集

29、合，若序偶的第一个元素是A的一个元素，第二个元素是B的一个元素，则所有这样的序偶集合称为集合A和B的，记作A B，即A B=。A B的子集R称为A，B上的。&将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、和等值。9、表达式 x yL (x，y)中谓词的定义域是a，b, c，将其中的量词消除，写成与之等 价的命题公式为10、一个无向图表示为 G=( P，L)，其中P是的集合，L是的集合，并且要求。(二) 单项选择题(选择一个正确答案的代号，填入括号中)1. 设命题公式G (P P) (Q R) P)，则G是()。A.恒真的B.恒假的C可满足的D.析取范式22、设集合 A a,b,c

30、，A 上的关系 R (a,a),(a,b),(b,c)，贝U R =()。(A)(a,a),(a,b),(a,c);(B)( a, b), (a, c), (b, c);(C)( a,b),(a,c),(b,b);(D)(a,a),(a,b),(c,c).3、一个公式在等价意义下，下面哪个写法是唯一的()。A 析取范式B .合取范式C.主析取范式D.以上答案都不对4、设命题公式G=(P Q), H=P(QP),贝y G与H的关系是()。A. G HB. H GC.G=HD .以上都不是0 10111 00015、已知图G的相邻矩阵为 00011，则G有()。1 01011 1110A.5点，8

31、边B. 6点，7边C. 5点，7边D. 6点，8边6、下列命题正确的是（）。7、8、9、A. =B. =C a a，b，cD . a , b, c设集合 A=a ，a),( c, b)A 自反设 R 为实数集,b，c , A 上的关系 R= ( a, b),( a,（c, c） ，贝U R具有关系的（B.对称C.传递映射A .单射而非满射列语句中,（A .下午有会吗?c),( b, a),( b, c),( c,）性质。D.反对称=R R,(x) = -x2+2x-1 ,贝B .满射而非单射C.双射是命题。B .这朵花多好看呀！是（）。D .既不是单射,也不是满射C. 2是常数。D .请把门关

32、上。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)D.xA( x) =x( A( x)三）计算题1、设R和S是集合A 1,2,3,4上的关系，其中(1,1),(1,3),(2,3),(3,4)(1,2),(2,3),(2,4),(4,4),试求：（1）写出R和S的关系矩阵;2)计算 R S, R S, R 1, S 1 R 12、设A=a , b, c, d, Ri, R2是A上的关系，其中R1= （ a，a），（ a，b），b，b），（

33、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）画出Ri和R2的关系图；（2） 判断它们是否为等价关系，是等价关系的求A中各元素的等价类。3、用真值表判断下列公式是恒真?恒假?可满足?1)(PP)Q2)(PQ)Q3)(PQ)( Q R)(P R)4、设解释 I 为：(1) 定义域 D=-2 , 3, 6;(2) F (x): x 3;G （x） : x 5。在解释I下求公式x （ F （x） G （x）的真值。5、求下图所示权图中从 u到v的最短路，

34、画出最短路并计算它们的权值。6V44V26、化简下式：（ABC）（AB）（ A （ B C） A）7、 已知 A=1，2，3，4，5，B=1，2，3，R 是 A 到 B 的二元关系，并且 R= （x，y）|x A且y B且2 x+y 4，画出R的关系图，并写出关系矩阵。& 画出下面偏序集（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如下：定义域D=2，3；f （2）

35、f （ 3）F （2，2）F （2，3） F （ 3，2）F （3，3）320011求 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 （ V3，V5，）= 10，w ( V4， V5) =12试求出连接 5 个城市的且造价最低的铁路网。（四）证

36、明题1、证明等价式 （ P （ Q R） （Q R） （P R） R 。R, T 蕴涵 Q。2、 利用形式演绎法证明： P Q, P R, S T, S3、A，B，C 为任意的集合，证明：（ A B） C=A （B C）4、利用一阶逻辑的基本等价式，证明：x y（F（x） G（y） = xF（ x） yG（y）练习解答（一）填空题1、列举；描述； A=4 ，5，6，7或 A=x|3 x 72、5 ；5 ，2，5 ，3，5，2，3，5 ；83、1=（ a， 1），（ b，1） ； 2= (a，2），（ b，2) ； 3=4=（ a， 2），（ b，1）4、（1，0， 1）； （1，1，1）； （

37、1，0，0）5、28；76、5 ； ，5 ； 1，3，4A且y B ；-V* R二元关系7、笛卡尔积（或直乘积）； ( x ， y ) |x8、并且（或合取）；或者（或析取）；蕴涵9、（L（a， a） L（ a，b）L（a，c）（L（b，a）L（b，b）a）L （c，b） L（ c，c）a，1），（ b， 2）；L（ b，c） （L（c，5、C10、A10、点；连接某些不同点对的边；一对不同点之间最多有一条边 （二）单项选择题（选择一个正确答案的代号，填入括号中） 1、C2、 A3、C4、A6、A7、 B8、D9、C（三）计算题1、解：（ 1）1 01001000 0100011MrMs0 00100000 0000001(2)R S=(1,2),(3, 4) R S= (1,1),( 1 , 2),( 1, 3),( 2, 3),( 2, 4),(3, 4),( 4, 4) 1R = (1, 1),( 3, 1),( 3, 2),( 4, 3) S 1 R 1= (2, 1),( 4, 3) 2、解:R1和R2的关系图略。由关系图可知，R1是等价关系。R1不同的等价类有两个，即a , b和c , d。 由于R2不是自反的，所以 R2不是等价关系。3、解：(1)真值表P QPP P(P P) Q0 01010 11001 00011 100