离散数学期末复习指导经典

《离散数学期末复习指导经典》由会员分享，可在线阅读，更多相关《离散数学期末复习指导经典（12页珍藏版）》请在金锄头文库上搜索。

1、1一、各章复习示例与解析一、各章复习示例与解析第一章第一章 集集 合合例 1，将“大于 3 而小于或等于 7 的整数集合”用集合表示出来。解析集合的表示方法一般有两种，一种称为列举法，一种称为描述法。列举法将集合的元素按任意顺序逐一列在花括号内，并用逗号分开。 “大于 3 而小于或等于 7 的整数”有 4、5、6、7，用列举法表示为4、5、6、7；描述法是利用集合中的元素满足某种条件或性质用文字或符号在花括号内竖线后面表示出来。上例用描述法表示为x| xZ 并且 3x7，其中 Z 为整数集合。答：4、5、6、7或x| xZ 并且 3x7。例 2，判定下列各题的正确与错误：（1）aa； （2）a

2、 a，b，c ；（3） a，b，c ； （4） a，b，c ；（5）a，ba，b，c， a，b，c ；（6）a，1，3，4a，3，4，1；（7）a，ba，b， a，b ；（8）如果 AB=B，则 A=E。解析此题涉及到集合中子集的概念，集合的包含关系，空集与集合的关系。解题时要注意区分两个集合之间的关系以及集合中元素与集合之间的关系的不同。集合之间的关系分为包含关系（子集、真子集） 、相等关系、幂集等，判断时要准确理解这些概念，才能正确地运用这些知识。集合与它的元素之间的关系有两种：一个元素 a 属于一个集合 A，记为 aA；一个元素 A 不属于一个集合 A，记为 aA。要注意符号的记法（）与

3、集合包含符号记法（，）的不同。答：正确的是（2） 、 （4） 、 （5） 、 （7） ；其余的都是错误的。例 3，设 A，B 是两个集合，A=1，2，3，B=1，2，请计算（A）（B） 。解析集合的概念一般在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，由集合 A 的所有子集组成的集合，称为 A的幂集，记作（A）或 2A；一是掌握幂集元数为 2n，n 为集合 A 的元数。集合的基本运算有交、并、差、补。答：（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例 4，试证明（AB）（A

4、B）=（AB）（AB）解析证明集合恒等式要熟练运用教材 15 页集合的 10 个基本运算。一般来说，欲证 P=Q，即证 PQ 并且 QP，也就是要证明，对于任意的 x，有下式成立。xP x Q 和 xQ x P证明集合恒等式的另一种方法是利用已知的恒等式来代入。本题就是用的这个方法。通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在 AB=AB 证明中的特殊作用。证明： BABABABABBBAABAABBAABABABA2第二章第二章 关系与映射关系

5、与映射例 1，设集合 A=1，2，3，4，5，试求 A 上的模 2 同余关系 R 的关系矩阵和关系图。解析关系的概念是第二章的基础，又是第一章集合概念的应用。因此应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。这道题要把 R 表示出来，先要清楚“模 2 同余关系”的概念，如果 x，y 模 2 同余，就是指 x，y 除以 2 的余数相同。于是，R=（1，1） ， （1，3） ， （1，5） ， （2，2） ， （2，4） ， （3，1） ， （3，3） ， （3，5） ， （4，2） ， （4，4） ， （5，1） ， （5，3） ， （5，5）求出了关系 R 的表达式，就可以进一步

6、求出关系矩阵和关系图了。答：R 的关系矩阵为：1010101010101010101010101RMR 的关系图为：例 2，设集合 A=1，2，3，10，A 上的关系 R=（x，y）|x，yA，且 x+y=10，试判断 R 具有哪几种性质？解析关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质（自反性、对称性、反对称性、传递性）的判定，可以依据其定义，也可以依据教材中 49 页上总结的关于关系矩阵和关系图的规律。对于传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性

7、，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法” ，即若（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。先写出 R 的关系式，R=（1，9） ， （2，8） ， （3，7） ， （4，6） ， （5，5） ， （6，4） ， （7，3） ， （8，2） ， （9，1），并在此基础上判断 R 是否具有四种关系的性质。答：R 只具有关系的对称性。例 3，设集合，判定下列关系，哪些是自反的，对称的，反对称的和传递的：dcbaA,解：均不是自反的；R4是对称 dbcaRccbbaaRdcRa

8、dcbaaRabaaR,54321 的；R1，R2，R3，R4，R5是反对称的；R1，R2，R3，R4，R5是传递的。例 4，设集合 A=a，b，c，d，R1，R2都是 A 上的二元关系，R1=（a，b） ， （b，c） ， （c，a），R2=，试求 R1和 R2的自反闭包，对称闭包和传递闭包。解析在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理 2，自反闭包；定理 3，对称闭包 AIRRr；定理 4 的推论，传递闭包。 1RRRs UniiRRt1答：r（R1）= R1IA=（a，b） ， （b，c） ， （c，a） ， （a，a） ， （b，b） ， （c

9、，c）s（R1）= R1 R1-1 =（a，b） ， （b，c） ， （c，a） ， （b，a） ， （c，b） ， （a，c）R12 =（a，c） ， （b，a） ， （c，b）3R13 =（a，a） ， （b，b） ， （c，c）t（R1）= R1 R12 R13 =（a，b） ， （b，c） ， （c，a） ， （a，c） ， （b，a） ， （c，b） ， （a，a） ， （b，b） ， （c，c）空关系 R2的自反闭包，对称闭包和传递闭包均为。例 5，设集合，A 上的二元关系 R 为：5 , 4 , 3 , 2 , 1A 5 , 5,4 , 5,3 , 5,4 , 4,4 , 3,3

10、 , 3,2 , 2,1 , 1R（）写出 R 的关系矩阵，画出 R 的关系图；（）证明 R 是 A 上的半序关系，画出其哈斯图；（）若，且，求 B 的最大元，最小元，极大元，极小元，最小上界和最大下界。AB 5 , 4 , 3 , 2B解析理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。解：（1）R 的关系矩阵为R 的关系图为1

11、110001000011000001000001RM（2）因为 R 是自反的，反对称的和传递的，所以 R 是 A 上的半序关系。 （A，R）为半序集， （A，R）的哈斯图如下：（3）当 B=2，3，4，5，B 的极大元为 2，4；极小元为 2，5；B 无最大元与最小元；B 也无上界与下界，更无最小上界与最大下界。例 6，下列映射中哪些是满射，哪些是单射，哪些是双射？（1）是偶数是奇数nnnNN21)(,:11（2）是偶数是奇数，nnnN01)(,10:22（3）1|2|)(,:33aaNZ（4）62)(,:44aaRR解析映射的概念与映射种类的判定：映射的种类主要指单射、满射、双射与非单非满射

12、。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。答：（1） ， （3）是非单非满射；（2）是满射；（4）是双射。第三章第三章 命题逻辑命题逻辑例 1，试证明公式为恒真公式。 RPRQQPG解析判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种：一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为 1（或全为 0） ，就可以判定该公式是否恒真（或恒假） ，若不全为 0，则为可满足的。二是推导法，即利用基本等价式推导出结果为 1，或者利用恒真（恒假）判定定理：公式 G 是恒真的（恒假的）当

13、且仅当等价于它的合取范式（析取范式）4 13 254中，每个子句（短语）均至少包含一个原子及其否定。这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。证明：证法一：真值表法，见离散数学学习指导书60 页例 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 为恒真公式。例 2，求的主析取范式与主合取范式。PRQPG解析求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确

14、理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。另外，由已经得到的主析取（合取）范式，根据原理，参阅离散数学学习指导书71 页例 15，也可以求得主合取（析取）范式。GGGG, 1解：（1）求主析取范式，方法 1 利用真值表求解 RQPQP RQPG0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 10 0 0 0 0 0 1 11 0 1 0 1 0 1 10 1 0 1 1 1 1 1因此方法 2 推导法 765431mmmmmmRQPRQPRQPRQPRQPRQPG 467513mmmmmmRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRRQQPPPRQQQRPPRQRPPRQPP