离散数学复习提纲.doc

1、离散数学期末复习大纲（完整版）（含例题和考试说明）一、命题逻辑复习知识点1、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题2、命题公式与赋值（成真、成假），真值表，公式类型（重言、矛盾、可满足），公式的基本等值式3、范式：析取范式、合取范式，极大（小）项，主析取范式、主合取范式 4、公式类型的判别方法（真值表法、等值演算法、主析取/合取范式法）5、命题逻辑的推理理论本章重点内容：命题与联结词、公式与解释、（主）析取范式与（主）合取范式、公式类型的判定、命题逻辑的推理复习要求1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、理解公式与赋值的概念；掌握求给定公式

2、真值表的方法，用基本等值式化简其它公式，公式在解释下的真值。3、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等值式或真值表将公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价方法。5、掌握命题逻辑的推理理论。疑难解析1、公式类型的判定判定公式的类型，包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二是等值演算法。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等值式中的分配律、同一律和互补律（排中

3、律、矛盾律），结果的前一步适当使用幂等律，使相同的短语（或子句）只保留一个。3、逻辑推理掌握逻辑推理时，要理解并掌握12个（除第10，11）推理规则和3种证明法（直接证明法、附加前提证明法和归谬法）。例1.试求下列公式的主析取范式：（1）；（2）（ ）2用真值表判断下列公式是恒真？恒假？可满足？（1）（PP）Q（2）（PQ）Q（3）（PQ）（QR）（PR） 解： （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

4、 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）为恒真。3Q（PQ）蕴涵 P（an: 法1：真值表法2：若Q（PQ）为真，则 Q，PQ为真， 所以Q为假，P为假，所以P为真。 法3：若P为假，则P为真，再分二种情况： 若Q为真，则Q（PQ）为假 若Q为假，则PQ为假，则Q（PQ）为假根据 ，所以 Q（PQ）蕴涵 P。）4利

5、用基本等价式证明下列命题公式为恒真公式。（PQ）（QR）（PR）（PQ）（P（QR）（PQ）（PR）（1、证明： （PQ）（QR）（PR） =（PQ）（QR）（PR） =（PQ）（QR）（PR）=（PQ）（QR）PR =（PQ）P ）（QR）R）=（1（QP ）（QR）1）= QPQR =（QQ） P R= 1 P R= 1 （PQ）（P（QR）（PQ）（PR） =（PQ）（P（QR）（P（QR） =（P（Q QR）（P（QR） =（P（QR）（P（QR） =1）5用形式演绎法证明：蕴涵证明： （1） 规则P （2） 规则Q （1） （3） 规则P （4） 规则Q（3） （5） 规则Q（2）（

6、4） （6）RS 规则P （7）PS 规则Q（5）（6） )6用形式演绎法证明：（蕴涵A证明：(改()（1）A 规则D（2）AB 规则Q（1）（3） 规则P（4） 规则Q（2）（3）（5）D 规则Q（4）（6） 规则Q（5）（7） 规则P （8）E 规则Q（6）（7）（9） 规则Q（1）（8）7（PQ），QR，R 蕴涵 P（1）QR（2）R（3）Q（4）（PQ）（5）PQ（6）P）8某案涉及甲、乙、丙、丁四个，根据已有线索，已知：（1） 若甲、乙均未作案，则丙、丁也均未作案；（2） 若丙、丁均未作案，则甲、乙也均未作案；（3） 若甲与乙同时作案，则丙与丁有一人且只有一人作案；（4） 若乙与丙同

7、时作案，则甲与丁同时作案或同未作案。办案人员由此得出结论：甲是作案者。这个结论是否正确？为什么？ 解：对问题中的四个简单命题用P1，P2，P3，P4分别表示甲，乙，丙，丁作案，则办案人员的推理如下：前提：1) P1P2P3P42) P3P4P1P23) P1P2(P3P4)(P3P4)4) P3P4(P1P2)(P1P2)结论：P1。(P1P2P3P4) (P3P4P1P2) ( P1P2(P3P4)(P3P4) ( P3P4(P1P2)(P1P2) P1不是永真式，比如：P1取假，P2取真，P3取假，P4取真时，上式为假所以P1不是前提的有效结论，所以甲是作案者的结论是错误的)二、 谓词逻辑

8、复习知识点 1、谓词、量词、个体词（一阶逻辑3要素）、个体域、变元（约束出现与自由出现）2、谓词公式与解释，谓词公式的类型（永真、永假、可满足）3、谓词公式的等值式（代换实例、消去量词、量词否定和量词辖域收与扩）和置换规则（置换规则、换名规则和代替规则）本章重点内容：谓词与量词、公式与解释复习要求1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。 疑难解析1、谓词与量词理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量

9、的自由性、约束性与改名规则（即换名规则和代替规则）。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释中的数值代入公式，求出真值。三、 集 合复习知识点1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补以及对称差等运算及其运算律（交换律、结合律、分配律、吸收律、 德摩根律等），文氏（Venn）图本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明。复习要求1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补、对称差等基本运算。3、掌握集合运算基本规律，

10、证明集合等式的方法。 疑难解析1、集合的概念重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。2、集合恒等式的证明对集合恒等式证明的练习，加深对集合性质的理解与掌握。四、 二元关系复习知识点1、序偶、迪卡尔积，迪卡尔积的运算。2、关系表达式、关系矩阵与关系图3、复合关系（右复合）与逆关系 3、关系的性质（自反性、反自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图、极大/小元、最大/小元7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、偏序

11、关系和映射的概念复习要求1、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。2、理解关系的概念：二元关系、空关系、全域关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。3、掌握求复合关系与逆关系的方法。4、理解关系的性质（自反性、反自反性、对称性、反对称性、传递性），掌握其判别方法（定义、图）。4、掌握求关系的闭包 （自反闭包、对称闭包、传递闭包）的方法。5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元的求法。6、理解函数概念：函数、函数相等、A到B的函数、复合函数和反函数。7、理解单射、满射、双射等概念，掌握其判别方法。疑难解析

12、1、关系的概念熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、偏序关系的基础。对于五种性质的判定，可以依据教材上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。3、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记定理7.10和7.114、偏序关系及偏序集中特殊元素的确定理解与掌握偏序关系与偏序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）

13、元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定。5、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。五、 图论复习知识点1、 图的基本概念：无向图与有向图、顶点与边的关联关系、顶点（边）与顶点（边）之间邻接关系、简单图与多重图、顶点度数（度）与握手定理、图的同构、完全图、子（补）图；2、 通路与回路、简单通（回）路与初级通（回）路；连通图与非连通图、连通分支、强连通图、单向连通图与弱连通图、二部图；点割集、边割集、点（边）连通

14、度；3、 图的矩阵表示：邻接矩阵、关联矩阵、可达矩阵；4、 欧拉通（回）路、（半）欧拉图；哈密尔顿通（回）路、（半）哈密尔顿图；5、 无向树、生成树、带权树、最小生成树，基本回路、基本回路系统、基本割集、基本割集系统、避圈法（Kruskal算法）；6、 有向树、树根、有序树、二叉树、前缀码、最佳前缀码、霍夫曼（Huffman）算法、带权图的最优二分树、二叉树的周游；本章重点内容： 握手定理、点（边）割集、特殊图（欧拉图与哈密顿图、无（有）向树）复习要求1、理解图的有关概念：图、完全图、子图、母图、生成子图、图的同构等。2、深刻理解握手定理及其推论的内容，并能熟练地应用它们。3、理解图的矩阵表示

15、（关联矩阵、相邻矩阵）和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中通路与回路数的方法。4、深刻理解欧拉图、哈密顿图的定义及判别定理，对于给定的图，应用各定理准确判断；会用破坏哈密顿图应满足的某些必要条件的方法判断某些图不是哈密顿图；会用满足哈密顿的充分条件的方法判断某些图是哈密顿图。5、深刻理解无向树的定义，熟练掌握无向树的主要性质，并能灵活应用它们。6、深刻理解生成树的有关概念与性质；理解基本回路、基本回路系统、基本割集、基本割集系统；用Kruskal算法求权图中最小生成树的方法。7、深刻理解有向树、根树、二叉树和前缀码的有关概念；掌握用霍夫曼（Huffman）算法求带权图的最优二分树

16、，掌握求最佳前缀码方法，二叉树的中序和前序行遍法。考试说明考核方式1、期末笔试为120分钟的闭卷考试，占总评成绩的70。2、平时成绩根据作业完成情况、半期考成绩、出勤情况和课堂表现确定，占总评成绩30。各章比例数理逻辑 30分 集合30 分 图论 40 分考题类型单项选择题16 分 填空题 18 分 证明题 12 分 计算分析（包括综合分析）题 54 分 大题详细分析1. 命题逻辑自然推理证明，综合分析题或证明题；2. 用等值演算法求解主析取范式或主合取范式，并用真值表法验证，计算分析题；3. 集合恒等式的证明或化简，证明题或计算分析题；4. 集合中有穷集的计数；5. 偏序关系与哈斯图及极大、极小元、最大、最小元；计算分析题；6. 基本回路系统、基本割集系统或邻接矩阵及各次幂的运算；计算分析题；7. 利用握手定理和树的性质求解图或树的顶点数；8. 最优二叉树产生的最佳前缀码（根树的应用）；综合分析题。