离散数学期末复习指导

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

1、1离散数学期末复习指导（专科）离散数学期末复习指导（专科）山东广播电视大学计算机与通信学院 2008 年 6 月离散数学是中央电大计算机应用专业信息管理方向开设的必修统设课。该课程使用新 的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代 数这两章及图论的后三节内容） ，使所学的知识达到必需、够用，更加适合大学专科层次的 教育。目前该课程没有新教材，借用原教材。使用的教材为中央电大出版的离散数学 （刘叙华等编）和离散数学学习指导书 （虞恩蔚等编） 。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽 象思维和逻辑推理能力，为从事计算机的应用

2、提供必要的描述工具和理论基础。其先修课 程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。课程的主要内容课程的主要内容 本课程分为三部分：集合论、数理逻辑和图论。 1、 集合论部分（集合的基本概念和运算、关系及其性质） ； 2、 数理逻辑部分（命题逻辑、谓词逻辑） ； 3、 图论部分（图的基本概念、树及其性质） 。学习建议学习建议 离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻 辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。一、各章复习示例与解析一、各章复习示例与解析第一章第一章 集集 合合 例 1，将“大

3、于 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 a，b，c ；（3） a，b，c ； （4） a，b，c ；（5）a，ba

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

5、、 （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）（AB）=（AB）（AB） 解析证明集合恒等式要熟

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

7、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）3求出了关系 R 的表达式，就可以进一步求出关系矩阵和关系图

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

9、具有自 反性。另一点是介绍一种判定传递性的“跟踪法” ，即若（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, dbcaRccbbaaRdcRadcbaaRabaaR,54

10、321 解：均不是自反的；R4是对称的；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，对称闭包；定理 4 的推论， AIRRr 1RRRs4传递闭包。 UniiRRt1答：r（R1）= R1IA=（a，b） ， （b，c） ， （c，a） ， （a，a） ， （b，b）

11、， （c，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） R13 =（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

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

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

14、的判定：映射的种类主要指单射、满射、双射与非单非满射。 判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系 表示进行，尤其是对各种初等函数。 答：（1） ， （3）是非单非满射；（2）是满射；（4）是双射。第三章第三章 命题逻辑命题逻辑例 1，试证明公式为恒真公式。 RPRQQPG解析 判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种： 一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一 列是否全为 1（或全为 0） ，就可以判定该公式是否恒真（或恒假） ，若不全为 0，则为可满 足的。 二是推导法，即利用基本等价式推导出结果为 1，或者利用恒真（恒假）判定定理： 公式 G 是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短 语）均至少包含一个原子及其否定。 这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别， 对于合取范式也同样。 证明： 证法一：真值表法，见离散数学学习指导书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 为