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

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

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

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

4、础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在 BABA 证明中的特殊作用。 例题分析 例 1 设 A， B 是两个集合， A=1， 2， 3， B=1， 2，则 )()( BA 。 解 3,2,1,3,2,3,1,2,1,3,2,1,)( A 2,1,2,1,)( B 于是 3,2,1,3,2,3,1,3)()( BA 例 2 设 , babaA ，试求： (1) baA , ； (2) A ； (3) A ； (4) Aba , ； (5) A ； (6) A 。 解 (1) , babaA (2) AA (3) babaA , (4) Aba, (5) A (

5、6) A 例 3 试证明 BABABABA 证明 BABABABABBBAABAABBAABABABA第二章 二元关系 复习知识点 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包） 5、等价关系与等价类 6、偏序关系与哈斯图（ Hasse）、极大 /小元、最大 /小元、上 /下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射） 8、复合函数与反函数 本章重点内容：二元关系的概念、关 系的性质、关系的闭包、等价关系、半序关系、映射的概念 3 复习要求 1、理解关系的概念：二元关系、空关系

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

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

8、握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理 2， AIRRr ；定理 3， 1 RRRs ；定理 4，推论 niiRRt1。 、半序关系及半序集中特殊元素的确定 理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。 、映射的概念与映射种类的判定 映射的种类主要指单射、满射、双射与非单非满射。判定的方法除

9、定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。 例题分析 例 1 设集合 dcbaA , ，判定下列关系，哪些是自反的，对称的，反对称的和传递的： dbcaR ccbbaaRdcRadcbaaRabaaR , ,54321 解：均不是自反的； R4 是对称的； R1 ,R2 ,R3 , R4 ,R5 是反对称的； R1 ,R2 ,R3 , R4 ,R5 是传递的。 4 例 2 设集合 5,4,3,2,1A ， A 上的二元关系 R 为 5,5,4,5,3,5,4,4,4,3,3,3,2,2,1,1R （）写出 R 的关系矩阵，画出 R 的关系

10、图； （）证明 R 是 A 上的半序关系，画出其哈斯图； （）若 AB ，且 5,4,3,2B ，求 B 的最大元，最小元，极大元，极小元，最小上界和最大下界。 解 （ 1） R 的关系矩阵为 1110001000011000001000001RM R 的关系图略 （ 2）因为 R是自反的，反 对称的和传递的，所以 R是 A上的半序关系。 (A,R)为半序集， (A,R)的哈斯图如下 (3) 当 5,4,3,2B ， B 的极大元为 2， 4；极小元为 2， 5； B 无最大元与最小元； B 也无上界与下界，更无最小上界与最大下界。 第三章 命题逻辑 复习知识点 、命题与联结词（否定、析取、合

11、取、蕴涵、等价），复合命题 、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价 、析取范式、合取范式，极小（大）项，主析取范式、主合取范式 、公式类别的判别方法（真值表法、等值演算法、主析取 /合取范式法） 、公式的蕴涵与逻辑结果 、形式演绎 本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎 复习要求 、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。 、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释 下的真值。 、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合

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

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

14、式。 3、形式演绎法 掌握形式演绎进行逻辑推理时，一是要理解并掌握 14 个基本蕴涵式，二是会使用三个规则：规则 P、规则 Q 和规则 D，需要进行一定的练习。 例题分析 例 1 求 PRQPG 的主析取范式与主合取范式。 解 （ 1）求主析取范式， 方法 1： 利用真值表求解 RQP QP RQP G 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 因此 RQP RQPRQPRQPRQPRQPG 方法 2：推导法 6 RQPRQPRQPRQPRQPR

15、QPRQPRQPRQPRQPRQPRQPRQPRQPRRQQPPPRQQQRPPRQRPPRQPPRQPPRRQPG（ 2）求主合取范式 方法 1：利用上面的真值表 PRQP 为 0 的有两行，它们对应的极大项分别为 RQPRQP , 因此， RQPRQPPRQP 方法 2：利用已求出的主析取范式求主合取范式 已用去 6 个极小项，尚有 2 个极小项，即 RQP 与 RQP 于是 RQPRQP RQPRQPGGRQPRQPG 例 2 试证明公式 RPRQQPG 为恒真公式。 证法一： 见离散数学学习指导书 P60 例 6（ 4）的解答。（真值表法） 证法二 ： G=（ PQ） （ QR） （

16、PR） =（ PQ） （ QR） PR =（ PQ） （ PR） （ QQ） （ QR） P） R =（ PQP） （ PRP） （ QRP） R =（ 1（ QRP） R =QRPR =1 故 G 为恒真公式。 例 3 利用形式演绎法证明 P（ QR）， SP， Q蕴涵 SR。 证明： （ 1） SP 规则 P （ 2） S 规则 D （ 3） P 规则 Q，根据（ 1），（ 2） （ 4） P（ QR） 规则 P （ 5） QR 规则 Q，根据（ 3），（ 4） （ 6） Q 规则 P 7 （ 7） R 规则 Q，根据（ 5），（ 6） （ 8） SR 规则 D，根据（ 2），（ 7） 第

17、四章 谓词逻辑 复习知识点 1、谓词、量词、个体词、个体域、变元（约束变元与自由变元） 2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足） 3、谓词公式的等价和蕴涵 4、前束范式 本章重点内容：谓词与量词、公式与解释、前束范式 复习要求 1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。 2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释 下真值的方法；了解谓词公式的类型。 3、理解用解释的方法证明等价式和蕴涵式。 4、掌握求公式前束范式的方法。 疑难解析 1、谓词与量词 反复理解谓词与量词引入的意义，概

18、念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。 2、公式与解释 能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释 I 中的数值代入公式，求出真值。 3、前束范式 在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。 典型例题 例 1 设 I 是如下一个解释： 3,2D F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3) 3 2 0 1 1 1 0 1 求 y,xFQxPyx 的真值。 解 110111110003,3FQ3P2,3FQ3P3,2FQ2

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

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

21、最后到达终点，算出最小权和。 3、 权图中的最优支撑树 权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（ Kruskal）算法。 典型例题 例 1 在具有 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 题。） 解 uu1 ， d(u, u1)=1, 路 (u, u1) 9 u u2 , d(u,

22、 u2)=9, 路 (u, u4, u3, u7, u2) u u3 , d(u, u3)=5, 路 (u, u4, u3 ,) u u4 , d(u, u4)=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) uv, d(u, v)=15, 路 (u, u1, u5 ,

23、u6 ,v) 或路 (u, u4 , u3 , u7 , u6 ,v) 二、考核说明 本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的 20%，以课程作业的形式进行（共三次，由四川电大统一布置）；终结性考核即期末考试，占总成绩的 80%。总成绩为 100 分， 60 分及格。 期末考试实行统一闭卷考核，试卷满分为 100。由四川电大统 一命题，统一评分标准，统一考试时间（考试时间为 120 分钟）。 1、试题类型 试题类型有填空题（分数约占 15%）、单项选择题（分数约占 10%）、判断题（分数约占10），计算简答题（分数约占 50%）和证明题（分数约占 15%）。 填空题和

24、单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。 2、考核试卷题量分配 试卷题量在各部分的分配是：集合论约占 30%，数理逻辑约占 40%，图论约占 20%，布尔代数 10。 具体课程考核情况见课程考核说明。 附录：试题类型及规范解答举例 填空题 1. 设 R 是集合 A 上的二元关系，如果关系 R 同时具有 性、对称性和 性，则称R 是等价关系。 2. 命题公式 G=（ PQ） R，则 G 共有 个不同的解释；把 G 在其所

25、有解释下所取真值列成一个表，称为 G 的 ；解释（ P， Q， R）或（ 0， 1， 0）使 G的真值为 。 3. 设 G=（ P， L）是图，如果 G 是连通的， 并且 ，则 G 是树。如果根树 T 的每个点 v 最多有两棵子树，则称 T 为 。 单项选择题 （选择一个正确答案的代号，填入括号中） 1. 由集合运算定义，下列各式正确的有（ ）。 A XXY B.XXY C.XXY D.YXY 2. 设 R1， R2 是集合 A=a， b， c， d上的两个关系，其中 R1=（ a， a），（ b， b），（ b， c），（ d， d） ， R2=（ a， a），（ b， b），（ b， c）

26、，（ c， b），（ d， d） ，则 R2 是 R1 的 （ ）闭包。 A自反 B对称 C传递 D以上都不是 3. 设 G 是由 5 个顶点组成的完全图，则从 G 中删去（ ）条边可以得到树。 A 4 B 5 C 6 D 10 10 计算题 1. 化简下式： （ ABC） （ AB） C） （ ABC） （ ABC） 2. 通过求主析取范式判断下列命题公式是否等值。 （ 1）（ PQ） （ PQR）； （ 2）（ P（ QR） （ Q（ PR）； 3. 求图中 A 到其余各顶点的最短路径，并写出它们的权。 证明题 1. 利用基本等价式证明下面命题公式为恒真公式。 （ PQ） （ QR） （

27、PR） 2. 用形式演绎 法证明： PQ， RS， PR 蕴涵 QS。 试题答案及评分标准 填空题 1、 自反；传递 2、 8；真值表； 1 3、 无回路；二叉树 单项选择题 （选择一个正确答案的代号，填入括号中） 1、 A 2、 B 3、 C 计算题 1. 解： （ ABC） （ AB） C） （ ABC） （ ABC） =（ ABC） （ ABC） （ ABC） （ ABC） =（ AB） （ CC） （ AB） （ CC） =（ AB） E） （ AB） E） E 为全集 =（ AB） （ AB） = A（ BB） = AE = A 2. 解： （ PQ） （ PQR） （ PQ（ RR） （ PQR） （ PQR） （ PQR） （ PQR） m6m7m3 m3m6m7 （ P（ QR） （ Q（ PR） B 7 C 1 2 A 2 5 3 D 4 6 E 1 F