.*
离散数学期末复习指导（专科）
中央电大理工部计算机教研室
离散数学是中央电大计算机应用专业信息管理方向开设的必修统设课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使所学的知识达到必需、够用，更加适合大学专科层次的教育。目前该课程没有新教材，借用原教材。使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。
离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容
本课程分为三部分：集合论、数理逻辑和图论。
1、 集合论部分（集合的基本概念和运算、关系及其性质）； 2、 数理逻辑部分（命题逻辑、谓词逻辑）； 3、 图论部分（图的基本概念、树及其性质）。 学习建议
离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。
一、各章复习示例与解析
第一章 集 合
例1，将“大于3而小于或等于7的整数集合”用集合表示出来。 [解析]
集合的表示方法一般有两种，一种称为列举法，一种称为描述法。 列举法将集合的元素按任意顺序逐一列在花括号内，并用逗号分开。“大于3而小于或等于7的整数”有4、5、6、7，用列举法表示为{4、5、6、7}；
描述法是利用集合中的元素满足某种条件或性质用文字或符号在花括号内竖线后面表示出来。上例用描述法表示为{x| x?Z并且3?x?7}，其中Z为整数集合。 答：{4、5、6、7}或{x| x?Z并且3?x?7}。
例2，判定下列各题的正确与错误： （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）{{a}，1，3，4}?{{a}，3，4，1}； （7）{a，b}?{a，b，{ a，b }}； （8）如果A?B=B，则A=E。 [解析]
此题涉及到集合中子集的概念，集合的包含关系，空集与集合的关系。解题时要注意
.*
区分两个集合之间的关系以及集合中元素与集合之间的关系的不同。 集合之间的关系分为包含关系（子集、真子集）、相等关系、幂集等，判断时要准确理解这些概念，才能正确地运用这些知识。
集合与它的元素之间的关系有两种：一个元素a属于一个集合A，记为a?A；一个元素A不属于一个集合A，记为a?A。要注意符号的记法（?）与集合包含符号记法（?，?）的不同。
答：正确的是（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，试证明（A?~B）?（~A?B）=（A?B）?（~A?~B） [解析]
证明集合恒等式要熟练运用教材15页集合的10个基本运算。一般来说，欲证P=Q，即证P?Q并且Q?P，也就是要证明，对于任意的x，有下式成立。
x?P? x ?Q 和 x?Q? x ?P
证明集合恒等式的另一种方法是利用已知的恒等式来代入。本题就是用的这个方法。 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在A–B=A?~B证明中的特殊作用。 证明：
?A?~B???~A?B????A?~B??~A????A?~B??B????A?~A???~B?~A?????A?B???~B?B??
?????~A?~B?????A?B??????A?B???~A?~B?
第二章 关系与映射
例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的表达式，就可以进一步求出关系矩阵和关系图了。
.*
?1??0答：R的关系矩阵为：MR??1??0?1?0101??1010?0101?
?1010?0101??R的关系图为：
例2，设集合A={1，2，3，?，10}，A上的关系R={（x，y）|x，y?A，且x+y=10}，试判断R具有哪几种性质？ [解析]
关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质（自反性、对称性、反对称性、传递性）的判定，可以依据其定义，也可以依据教材中49页上总结的关于关系矩阵和关系图的规律。
对于传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若（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，设集合A??a,b,c,d?，判定下列关系，哪些是自反的，对称的，反对称的和传递的：
R1???a,a?,?b,a??R5???a,c?,?b,d??R2???a,a?,?b,c?,?d,a??R3???c,d??R4???a,a?,?b,b?,?c,c??解：均不是自反的；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，自反闭包r?R??R?IA；定理3，对称闭包s?R??R?R；定理4的推论，
?1.*
传递闭包t?R???Ri?1ni。
答：r（R1）= R1?IA={（a，b），（b，c），（c，a），（a，a），（b，b），（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的自反闭包，对称闭包和传递闭包均为?。
1,2,3,4,5?，A上的二元关系R为： 例5，设集合A?? R???1,1?,?2,2?,?3,3?,?3,4?,?4,4?,?5,3?,?5,4?,?5,5?? （１）写出R的关系矩阵，画出R的关系图；
（２）证明R是A上的半序关系，画出其哈斯图；
（３）若B?A，且B??2,3,4,5?，求B的最大元，最小元，极大元，极小元，最小上界和最大下界。 [解析]
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。 解：（1）R的关系矩阵为
?1??0 MR??0??0?0?0000??1000?0110? R的关系图为
?0010?0111?? （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也无上界与下界，更无最小上界与最大下界。
.*
例6，下列映射中哪些是满射，哪些是单射，哪些是双射？ （1）?1:N?N,?1(n)???1n是奇数
?2n是偶数?1n是奇数
0n是偶数? （2）?2:N?{0，1},?2(n)?? （3）?3:Z?N,?3(a)?|2a|?1 （4）?4:R?R,?4(a)?2a?6
[解析]
映射的概念与映射种类的判定：映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 答：（1），（3）是非单非满射；（2）是满射；（4）是双射。
第三章 命题逻辑 例1，试证明公式G???P?Q???Q?R????P?R?为恒真公式。
[解析]
判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种：
一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。
二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。
这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。 证明：
证法一：真值表法，见《离散数学学习指导书》60页例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）?（P??R??P）?（?Q??R??P））?R =（1?（?Q??R??P））?R =?Q??R??P?R =1
故G为恒真公式。
例2，求G???P?Q???R??P的主析取范式与主合取范式。
离散数学期末复习资料指导(专科)
