离散数学复习.doc

离散数学期末复习指导（专科）中央电大理工部计算机教研室 离散数学是中央电大计算机应用专业信息管理方向开设的必修统设课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使所学的知识达到必需、够用，更加适合大学专科层次的教育。目前该课程没有新教材，借用原教材。使用的教材为中央电大出版的离散数学（刘叙华等编）和离散数学学习指导书（虞恩蔚等编）。离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容本课程分为三部分：集合论、数理逻辑和图论。1、 集合论部分（集合的基本概念和运算、关系及其性质）；2、 数理逻辑部分（命题逻辑、谓词逻辑）；3、 图论部分（图的基本概念、树及其性质）。 学习建议离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。一、各章复习示例与解析第一章 集 合例1，将“大于3而小于或等于7的整数集合”用集合表示出来。解析 集合的表示方法一般有两种，一种称为列举法，一种称为描述法。 列举法将集合的元素按任意顺序逐一列在花括号内，并用逗号分开。“大于3而小于或等于7的整数”有4、5、6、7，用列举法表示为4、5、6、7； 描述法是利用集合中的元素满足某种条件或性质用文字或符号在花括号内竖线后面表示出来。上例用描述法表示为x| xZ并且3x7，其中Z为整数集合。答：4、5、6、7或x| xZ并且35。 在解释I下求公式$x（F（x）G（x）的真值。5、 化简下式：（ABC）（AB）-（A（B-C）A）6、 已知A=1，2，3，4，5，B=1，2，3，R是A到B的二元关系，并且R=（x，y）|xA且yB且2 x+y 4，画出R的关系图，并写出关系矩阵。7、 画出下面偏序集（A，）的哈斯图，并指出集合A的最小元、最大元、极大元和极小元。其中A=a，b，c，d，e，=（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）IA。8、 求命题公式的析取范式与合取范式。9、给定解释I如下： 定义域D=2，3； f（2） f（3） F（2，2） F（2，3） F（3，2） F（3，3） 3 2 0 0 1 1求。10、求下面带权图的最优支撑树，并计算它的权。 4 7 8 20 12 8 9 10 15（四）证明题1、证明等价式。 2、 利用形式演绎法证明：蕴涵Q。3、 A，B，C为任意的集合，证明：4、 利用一阶逻辑的基本等价式，证明： 练习题参考解答（一）填空题1、列举；描述；2、5；5，2，5，3，5，2，3，5；83、s1=（a，1），（b，1）；s2=（a，2），（b，2）；s3=（a，1），（b，2）；s4=（a，2），（b，1）4、（1，0，1）； （1，1，1）； （1，0，0）5、 28； 76、5；f，5；1，3，47、笛卡尔积（或直乘积）；（x，y）|xA且yB；二元关系8、并且（或合取）；或者（或析取）；蕴涵9、（L（a，a）L（a，b）L（a，c）（L（b，a）L（b，b）L（b，c）（L（c，a）L（c，b）L（c，c）10、点；连接某些不同点对的边；一对不同点之间最多有一条边（二）选择题（选择一个正确答案的代号，填入括号中）1、C 2、A 3、C 4、A 5、C6、A 7、B 8、D 9、C 10、A（三）计算题1、解：（1） （2）=（1，2），（3，4） =（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4） =（1，1），（3，1），（3，2），（4，3） =（2，1），（4，3） 2、解： R1和R2的关系图如下： R1的关系图 R2的关系图由关系图可知，R1是等价关系。R1不同的等价类有两个，即a，b和c，d。由于R2不是自反的，所以R2不是等价关系。3、解 ：（1） 真值表P QP PP （PP）Q0 01 0 10 11 0 01 00 0 11 10 0 0 因此公式（1）为可满足。（2） 真值表P QPQ （PQ） （PQ）Q0 01 0 00 11 0 01 00 1 01 11 0 0 因此公式（2）为恒假。 （3） 真值表P Q RPQ QR PR （PQ）（QR）（PR）0 0 0 1 1 1 10 0 1 1 1 1 10 1 0 1 0 1 10 1 1 1 1 1 11 0 0 0 1 0 11 0 1 0 1 1 11 1 0 1 0 0 11 1 1 1 1 1 1 因此公式（3）为恒真。 4、解： $x（F（x）G（x） （F（-2）G（-2）（F（3）G（3）（F（6）G（6） （10）（10）（01） 1 5、解： （ABC）（AB）-（A（B-C）A）=（AB）- A （利用两次吸收律） =（AB） A =（A A）（B A） = f（B A）= B- A 6、解： R=（1，1），（1，2），（1，3），（2，1），（2，2），（3，1） 1 1 2 2 3 34 5 R的关系图为关系矩阵7、解： （A，）的哈斯图为： e b c d a a为A的极小元，也是最小元； e为A的极大元，也是最大元。 8、解： （PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）（PQ）上面结果为合取范式。利用对分配得：（PQ）（PQ） （PP）（PQ）（QP）（QQ） （PQ）（QP）上面结果为析取范式。9、解： xy（F（x，y）F（f（x），f（y） x（F（x，2）F（f（x），f（2）（F（x，3）F（f（x），f（3） （F（2，2）F（f（2），f（2）（F（2，3）F（f（2），f（3）（F（3，2）F（f（3），f（2）（F（3，3）F（f（3），f（3） （01）（01）（10）（10） 0 10、解： 带权图的最优支撑树如下，权和为28。 4 7 8 9（四）证明题1、 证明： 2、证明： （1） 规则P（2） 规则P（3） 规则Q，根据（1）、（2）和基本蕴涵式（12）（4） 规则P（5） 规则Q，根据（3）、（4）和基本蕴涵式（11） （6） 规则P（7） 规则Q，根据（5）、（6）和基本蕴涵式（12）（8） 规则P（9） 规则Q，根据（7）、（8）和基本