离散数学专科期末复习提要

1、离散数学专科期末复习提要四川电大 孙继荣2004年5月离散数学使用的教材为中央电大出版的离散数学（刘叙华等编）和离散数学学习指导书（虞恩蔚等编）。离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容1、 集合论部分（集合的基本概念和运算、关系及其性质）；2、 数理逻辑部分（命题逻辑、谓词逻辑）；3、 图论部分（图的基本概念、树及其性质）。4、布尔代数（此部分对专科要求不高） 学习建议离散数学是理论性较

2、强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。 教学要求的层次各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。一、各章复习要求与重点第一章 集 合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等），文氏（Venn）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的

3、证明 复习要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。4、 了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 疑难解析1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式

4、在证明中的特殊作用。例题分析例1 设A，B是两个集合，A=1，2，3，B=1，2，则 。解 于是例2 设，试求： (1)； (2)； (3)； (4)； (5)； (6)。解 (1) (2) (3) (4) (5) (6)例3 试证明 证明 第二章 二元关系复习知识点1、关系、关系矩阵与关系图2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系

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

6、疑难解析 1、关系的概念关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若，则。如若，则有，且。、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求

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

8、数。例题分析例1 设集合，判定下列关系，哪些是自反的，对称的，反对称的和传递的：解：均不是自反的；R4是对称的；R1 ,R2 ,R3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5是传递的。例2 设集合，A上的二元关系R为 （）写出R的关系矩阵，画出R的关系图；（）证明R是A上的半序关系，画出其哈斯图；（）若，且，求B的最大元，最小元，极大元，极小元，最小上界和最大下界。解 （1）R的关系矩阵为 R的关系图略 （2）因为R是自反的，反对称的和传递的，所以R是A上的半序关系。(A,R)为半序集， (A,R)的哈斯图如下 。4 。1 。3 。2 。5 (3) 当，B的极大元为2

9、，4；极小元为2，5；B无最大元与最小元；B也无上界与下界，更无最小上界与最大下界。 第三章命题逻辑复习知识点、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价、析取范式、合取范式，极小（大）项，主析取范式、主合取范式 、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）、公式的蕴涵与逻辑结果、形式演绎本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎复习要求、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。、理解公式与解释的概念；掌握求给定公式真值表

10、的方法，用基本等价式化简其他公式，公式在解释下的真值。、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。6、掌握形式演绎的证明方法。 疑难解析1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则

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

12、合取（析取）范式。3、形式演绎法掌握形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则P、规则Q和规则D，需要进行一定的练习。例题分析例1 求的主析取范式与主合取范式。解 （1）求主析取范式， 方法1：利用真值表求解G0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1000000111010101101011111因此 方法2：推导法 （2）求主合取范式方法1：利用上面的真值表为0的有两行，它们对应的极大项分别为因此，方法2：利用已求出的主析取范式求主合取范式已用去6个极小项，尚有2个极小项，即 与 于是 例2 试证明公式为恒真公式

13、。证法一： 见离散数学学习指导书P60例6（4）的解答。（真值表法）证法二 ： G=Ø（ØPÚQ）Ù（ØQÚR）Ú（ØPÚR） =（PÙØQ）Ú（QÙØR）ÚØPÚR =（PÚQ）Ù（PÚØR）Ù（ØQÚQ）Ù（ØQÚØR）ÚØP）ÚR =（PÚQÚØP）&#

14、217;（PÚØRÚØP）Ù（ØQÚØRÚØP）ÚR =（1Ù（ØQÚØRÚØP）ÚR =ØQÚØRÚØPÚR =1故G为恒真公式。例3 利用形式演绎法证明 P®（Q®R），ØSÚP，Q蕴涵S®R。证明：（1）ØSÚP 规则P（2）S 规则D（3）P 规则Q，根据（1），（2） （4）P&

15、#174;（Q®R） 规则P （5）Q®R 规则Q，根据（3），（4） （6）Q 规则P （7）R 规则Q，根据（5），（6） （8）S®R 规则D，根据（2），（7）第四章 谓词逻辑复习知识点 1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）3、谓词公式的等价和蕴涵4、前束范式本章重点内容：谓词与量词、公式与解释、前束范式复习要求1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求

16、公式在给定解释下真值的方法；了解谓词公式的类型。3、理解用解释的方法证明等价式和蕴涵式。4、掌握求公式前束范式的方法。 疑难解析1、谓词与量词反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I中的数值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。典型例题例1 设I是如下一个解释： F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(

17、3,3) 3 2 0 1 1 1 0 1求的真值。解 例2 试将一阶逻辑公式化成前束范式。解 第七章 图论复习知识点1、图、完全图、子图、母图、支撑子图、图的同构2、关联矩阵、相邻矩阵3、权图、路、最短路径，迪克斯特拉算法（Dijkstra）4、树、支撑树、二叉树 5、权图中的最小树，克鲁斯卡尔算法（Kruskal）6、有向图、有向树本章重点内容： 权图的最短路、二叉树的遍历、权图中的最优支撑树复习要求1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。2、掌握图的矩阵表示（关联矩阵、相邻矩阵）。3、理解权图、路的概念，掌握用Dijkstra算法求权图中最短路的方法。4、理解树、

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

19、在具有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题。）解 u®u1 ， 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)=

20、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)u®v, d(u, v)=15, 路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v) 二、考核说明本课程的考核实行形成性考核和终结性考核的形

21、式。形成性考核占总成绩的20%，以课程作业的形式进行（共三次，由四川电大统一布置）；终结性考核即期末考试，占总成绩的80%。总成绩为100分，60分及格。期末考试实行统一闭卷考核，试卷满分为100。由四川电大统一命题，统一评分标准，统一考试时间（考试时间为120分钟）。1、试题类型试题类型有填空题（分数约占15%）、单项选择题（分数约占10%）、判断题（分数约占10），计算简答题（分数约占50%）和证明题（分数约占15%）。填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质

22、、定理及主要结论进行逻辑推理的能力，要求写出推理过程。2、考核试卷题量分配试卷题量在各部分的分配是：集合论约占30%，数理逻辑约占40%，图论约占20%，布尔代数10。具体课程考核情况见课程考核说明。附录：试题类型及规范解答举例填空题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的每

23、个点v最多有两棵子树，则称T为 。单项选择题（选择一个正确答案的代号，填入括号中）1. 由集合运算定义，下列各式正确的有（ ）。A XÍXÈY B.XÊXÈY C.XÍXÇY D.YÍXÇY2. 设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中删去（ ）条边可以得到树。A4 B5 C6

24、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到其余各顶点的最短路径，并写出它们的权。 B 7 C 1 2 A 2 5 3 D4 6 E 1 F证明题1. 利用基本等价式证明下面命题公式为恒真公式。（P®Q）Ù（

25、Q®R）®（P®R）2. 用形式演绎法证明：P®Q， R®S，PÚR 蕴涵QÚS。试题答案及评分标准填空题1、 自反；传递2、 8；真值表；13、 无回路；二叉树单项选择题（选择一个正确答案的代号，填入括号中）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）È（

26、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）

27、Û（PÙQÙØR）Ú（PÙQÙR）Ú（ØPÙQÙR）Û m6Úm7Úm3 Û m3Úm6Úm7 （PÚ（QÙR）Ù（QÚ（ØPÙR）Û（PÙQ） Ú（QÙR）Ú（PÙØPÙR）Ú（ØPÙ Q ÙR） （分配律）Û（PÙQÙ

28、;（ØRÚR） Ú（ØPÚP）ÙQÙR）Ú（ØPÙ Q ÙR）Û（PÙQÙØR） Ú（PÙQÙR） Ú（ØPÙQÙR）Ú（PÙQÙR）Ú（ØPÙ Q ÙR）Û m6Úm7Úm3Úm7Úm3Û m3Úm6Úm7 由此可见 （P

29、17;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的最短路径为ABEFC，权为7；A到D的最短路径为ABEFCD，权为9。证明题1. 证明： （P®Q）Ù（Q®R）®（P®R） Û（ØPÚQ）Ù（ØQÚR）®（ØP

30、8;R） ÛØ（ØPÚQ）Ù（ØQÚR）Ú（ØPÚR）Û（PÙØQ）Ú（QÙØR）ÚØPÚR Û（PÙØQ）ÚØP ）Ú（QÙØR）ÚR）Û（1Ù（ØQÚØP ）Ú（QÚR）Ù1）Û ØQÚØP

31、18;QÚR Û （ØQÚQ） ÚØP ÚRÛ 1 ÚØP ÚRÛ 1 2. 证明：（1） PÚR 规则P （2） ØR®P 规则Q ，根据（1） （3） P®Q 规则P （4） ØR ®Q 规则Q，根据（2）（3） （5） ØQ®R 规则Q，根据（4） （6） R®S 规则P （7） ØQ®S 规则Q，根据（5）（6）（8） QÚS 规则Q ，根据（7）

32、2004补充练习题：请自己完成，此处不提供标准答案一、单项选择题(下列各题，给出的答案中只有一个是正确的，选出正确答案填在题目的括号中。每题2分)1. 下列命题正确的是（ ）。A、a B、aC、Æ D、a,b2. 设个体域为整数，下列公式中真值为1是( )3、设集合A=1,2,3,4,A上的关系R=(1,1),(2,3),(2,4),(3,4),则R具有（ ）。A、自反性 B、传递性C、对称的 D、以上答案都不对l l ll l l 第3题图4、设图G为下图，那么G是 ( )。平面图 完全图 欧拉图 哈密顿图5、如图11所示，其中存在哈密顿回路的图是 ( )。A、h B、h h C、

33、h h D、h h h h h h h h h h h h h h 图116. 设a，b，c各不相同，下面等式中为真的是（ ） (A) a，b，c, Æ =a，b，c (B) a，b，a=a，b (C) a，b=a，b (D) Æ，Æ，a，b=Æ，Æ，a，b7、设命题公式，则G是（ ）。A、永真的 B、永假的 C、可满足的 D、析取范式8. 设个体域为整数，下列公式中真值为1是( )8. 设图G<V,E>，则下列结论成立的是 ( )(A) deg(V)=2½E½ (B) deg(V)=½E½

34、(C) (D) 9. 定义实数集R上的二元运算*为："a,bÎR，a*b=( )，则二元运算*同时满足交换律和结合律，其中，× 是普通加法，减法和乘法。10. 已知集合Aa,b,c上的二元关系R的关系矩阵MR，那么R( )，(A) <a,b>,<b,a>,<b,b>,<a,c> (B) <a,b>,<b,a>,<b,b>,<c,b> (C) <a,b>,<a,a>,<b,b>,<c,a> (D) <a,b>,&

35、lt;b,a>,<b,b>,<c,a> 11. 设P：我将去市里，Q：我有时间。命题“我将去市里，仅当我有时间时”符号化为( )12.设F(x)：x是鸟，G(x)：x会飞翔。则命题“鸟都会飞”符号化为( )13. n阶无向完全图Kn中的边数为（ ）(A) (B) (C) n (D)n(n+1)14. 设A,B,C为任意集合下列命题为真的是( )如果AÈBAÈC，则BC (B) 如果ABÆ，则AB(C) AÅA=A (D) Æ是Æ的子集15、设命题公式，则G是（ ）。A、永真的 B、永假的 C、可满足的 D

36、、析取范式16、设集合A=1,2,3,4,A上的关系R=(1,1),(2,3),(2,4),(3,4),则R具有（ ）。A、自反性 B、传递性C、对称的 D、以上答案都不对17.对任意集合S，SÈÆS，满足( )(A) 幂等律 (B) 零一律 (C) 同一律 (D) 互补律18.设集合A=1,2,3,4, A上的二元关系R的关系矩阵为MR则关系R的表达式是( )(A) <1,1>,<1,4>,<2,1>,<2,3> (B) <1,1>,<1,2>,<1,4>,<2,3> (C)

37、<1,1>,<2,1>,<3,2>,<1,4> (D) <1,1>,<2,1>,<3,2>,<4,1>19. 无向图G是欧拉图，当且仅当( )A.G中所有结点的度数全为偶数 B. G中所有结点的度数全为奇数C.G连通且所有结点的度数全为偶数 D. G连通且所有结点的度数全为奇数20.下列偏序集中是格的为( )(A) ¡ (B) ¡ (C) ¡ (D) ¡ ¡ ¡ ¡ ¡ ¡ ¡ ¡二、填空题

38、(每空2分) 1、设P：天下雨，Q：天刮风，H：我去书店。则将命题“如果天不下雨，而且也不刮风，我就去书店”符号化为 。2、设谓词命题公式的前束范式是 。3、设G<V,E>是有P个结点，s条边的连通图，则从G中删去 条边，才能确定图G的一棵生成树。4、已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 。5、设集合A1，2，3，在A上定义二元运算为：，则的运算表为： 6. 设A、B为有限集，且|A|=m,|B|=n,那末A与B间存在双射，当且仅当 .7. 如果关系R是传递的，则R·RÍ .8. 设(R*,)是代数系统，其中R*R0，

39、二元运算定义为,那么，的逆元是 9.设给定集合Aa,b， P(A) ，那么P(A)上的包含关系Ì集合表达式为 10 已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是 。11. 设给定图G(如第11题图所示)，则图G的 · a · b f · · c e · · d 第11题图点割集是 12. 设N(x)：x是自然数，H(x,y)；y是x的后继数，则谓词命题“每个自然数都有后继数”符号化为 。13. 设命题公式G的主合取范式是，那么G的主析取范式是 14. 设代数系统(G，+，*)，如果 ， 且

40、运算*对+满足分配律，则称代数系统(G，+，*)为环15. 若命题变元P，Q，R赋值为(1,0,1)，则命题公式G的真值是 16. 设G<V,E>是有P个结点，s条边的连通图，则从G中删去 条边，才能确定图G的一棵生成树。17. 设Aa，a,则P(A)= 18. 在布尔代数中，有成立，则其对偶式 一定成立。19、设集合A1，2，3，在A上定义二元运算为：，则的运算表为： 20、设集合Aa,b,c,B=a,b,那么P(A)P(B)= P(B)P(A)= 。三、判断题(每小题1分)1、aÎa； 2、aÍ a，b，c ；3、ÆÎ a，b，c ； 4、ÆÍ a，b，c ；5、a，bÍa，b，c， a，b，c ；6、 一个集合的最大元一定存在而且唯一；7、孤立节点既是极小元又是极大元；8、函数首先是二元关系并且满足一一对应关系。9、如果集合,R(a,a),(b,b),(c,c),(a,c),那么R具有