《离散数学》期末复习大纲(完整版) (含例题和考试说明)

《离散数学》期末复习大纲(完整版)(含例题和考试说明)2、命题公式与赋值(成真、成假)，真值表，公式类型(重言、矛盾、可满足)，公式的基本等值式3、范式：析取范式、合取范式，极大(小)项，主析取范式、主合取范式4、公式类型的判别方法(真值表法、等值演算法、主析取/合取范式法)本章重点内容：命题与联结词、公式与解释、(主)析取范式与(主)合取范式、公式类型的判定、理给定公式真值表的方法，用基本等值式化简其它公式，公式在解释下3、了解析取(合取)范式的概念；理解极大(小)项的概念和主析取(合取)范式的概念；掌握用基本等值式或真值表将公式化为主析取(合取)范式的方法。判别公式类型和公式等价方法。包括判定公式是重言的、矛盾的或是可满足的。具体方法有两种，一是真值表法，二另一是巧妙使用基本等值式中的分配律、同一律和互补律(排中律、矛盾律)，结果的前一步适当使用幂等律，使相同的短语(或子句)只保留一个。掌握逻辑推理时，要理解并掌握12个(除第10，11)推理规则和3种证明法(直接证明法、附加前提(1)P((PQ)^(QP))；(2)P(P(QQR)))PQP(PQ)^(PP)=PQ(1)(P^P)一Q(2)(PQ)^Q(3)((PQ)^(QR))(PR)(1)真值表PQPP^P(P^P)一Q010100001000因此公式(1)为可满足。(2)真值表PQPQ(PQ)(PQ)^Q00010001000因此公式(2)为恒假。(3)真值表PQRPQQRPR((PQ)^(QR))(PR)111100111111011011111101010111因此公式(3)为恒真。3．┐Q^(P→Q)蕴涵┐P①若Q为真，则┐QÙ(P→Q)为假QPQQPQ假((PQ)^(QR))(PR)(1、证明：((PQ)^(QR))(PR)=(P^Q)(Q^R)PR=((P^Q)P)((Q^R)R)R=1PR=1RPQRP(Q^R))(1)PQ(2)PQ(3)QR(4)QR(5)PR(6)RS(7)PS6．用形式演绎法证明：(AB)(C^D),(DF)E蕴涵AE证明：(改(A^B)为(AB),(D^F)为(DF))(1)A规则D(2)A∨B规则Q()1(3)(AB)(C^D)规则P(4)C^D规则Q(2)()3(5)D规则Q()4(6)DF规则Q()5(7)(DF)E规则P (8)E规则Q(6)()7 (9)AE规则Q(1)(8))(1)┐Q∨R(2)┐R(3)┐Q(4)┐(P∧┐Q)(5)┐P∨Q(6)┐P)(1)若甲、乙均未作案，则丙、丁也均未作案；(2)若丙、丁均未作案，则甲、乙也均未作案；(3)若甲与乙同时作案，则丙与丁有一人且只有一人作案；(4)若乙与丙同时作案，则甲与丁同时作案或同未作案。结论是错误的)1、谓词、量词、个体词(一阶逻辑3要素)、个体域、变元(约束出现与自由出现)2、谓词公式与解释，谓词公式的类型(永真、永假、可满足)3、谓词公式的等值式(代换实例、消去量词、量词否定和量词辖域收与扩)和置换规则(置换规则、换词与量词、公式与解释题；念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则(即换名规则和代替规则)。消除，写成与之等价的公式，然后将解释中的数值代入公式，求出包含、相等、幂集及其运算律(交换律、结合律、分配律、吸收律、德摩根律等)，文氏(Venn)图3、复合关系(右复合)与逆关系3、关系的性质(自反性、反自反性、对称性、反对称性、传递性)4、关系的闭包(自反闭包、对称闭包、传递闭包)7、函数及其性质(单射、满射、双射)元关系的概念、关系的性质、关系的闭包、等价关系、偏序关系和映射的概念关系、恒等关系；掌握关系的集合表示、关系矩阵和关系4、理解关系的性质(自反性、反自反性、对称性、反对称性、传递性)，掌握其判别方法(定义、图)。4、掌握求关系的闭包(自反闭包、对称闭包、传递闭包)的方法。等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小概念的加深理解与掌握，又是关系的闭包、等价关系、偏序关系的基础。对于五，的确定理解与掌握偏序关系与偏序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大(小)元，极大(小)元也就容易了。这里要注意，最大(小)元与极大(小)元只能在子集内确定。非单非满射。判定的方法除定义外，可借助于关系图，而实数集1、图的基本概念：无向图与有向图、顶点与边的关联关系、顶点(边)与顶点(边)之间邻接关系、简单图与多重图、顶点度数(度)与握手定理、图的同构、完全图、子(补)图；2、通路与回路、简单通(回)路与初级通(回)路；连通图与非连通图、连通分支、强连通图、单向连通图与弱连通图、二部图；点割集、边割集、点(边)连通度；4、欧拉通(回)路、(半)欧拉图；哈密尔顿通(回)路、(半)哈密尔顿图；法(Kruskal算法)；6、有向树、树根、有序树、二叉树、前缀码、最佳前缀码、霍夫曼(Huffman)算法、带权图的最优二本章重点内容：握手定理、点(边)割集、特殊图(欧拉图与哈密顿图、无(有)向树)3、理解图的矩阵表示(关联矩阵、相邻矩阵)和性质以及熟练掌握用有向图的邻接矩阵及各次幂求图中