三峡大学期末计算机专业离散数学考试期末离散复习

1《离散数学》期末复习提要课程的主要内容1、集合论部分（集合的基本概念和运算、二元关系和函数）；2、数理逻辑部分（命题逻辑、谓词逻辑）；3、图论部分（图的基本概念、特殊的图，树及其性质）。一、各章复习要求与重点第一章命题逻辑[复习知识点]１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题２、命题公式与解释，真值表，公式分类（永真、矛盾、可满足），公式的等价３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）５、全功能集６、推理理论本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、推理理论[复习要求]１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。掌握24个重要等值式。2５、掌握推理理论，会写出推理的证明，掌握附加前提证明法和归谬发。[本章重点习题]习题P31-36:1.1,1.7-1.9,1.12,1.18,1.19，1.15[疑难解析]1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。2、范式求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。3、推理理论掌握构造证明法，一是要理解并掌握8个推理定理，二是会使用常用的推理规则，附加前提证明法和归谬法，需要进行一定的练习。[例题分析]例1求PRQPG的主析取范式与主合取范式。解（1）求主析取范式，方法1：利用真值表求解3RQPQPRQPG000001010011100101110111000000111010101101011111因此RQPRQPRQPRQPRQPRQPG方法2：推导法RQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRQPRRQQPPPRQQQRPPRQRPPRQPPRQPPRRQPG（2）求主合取范式方法1：利用上面的真值表PRQP为0的有两行，它们对应的极大项分别为RQPRQP,因此，RQPRQPPRQP方法2：利用已求出的主析取范式求主合取范式已用去6个极小项，尚有2个极小项，即4RQP与RQP于是RQPRQPRQPRQPGGRQPRQPG例2试证明公式RPRQQPG为恒真公式。证法一：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为恒真公式。例3构造下面的推理证明前提：p(q∨r),sr,p∧s结论：q证明：①p∧s前提引入②p①化简③p(q∨r)前提引入④q∨r②③假言推理⑤s①化简⑥sr前提引入5⑦r⑤⑥假言推理⑧q④⑦析取三段论推理正确。第二章一阶逻辑[复习知识点]1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、一阶逻辑公式与解释，谓词公式的类型（永真、矛盾、可满足）3、一阶逻辑公式等值式4、前束范式本章重点内容：谓词与量词、公式与解释、前束范式[复习要求]1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。3、证明等值式。4、掌握求公式前束范式的方法。[本章重点习题]习题P52-55：2.3，2.12,2.13,2.14,2.15[疑难解析]1、谓词与量词6反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与换名规则。2、公式与解释能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I中的数值代入公式，求出真值。3、前束范式在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。[典型例题]例1设I是如下一个解释：3,2DF(2)F(3)P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)32011101求y,xFQxPyx的真值。解110111110003,3FQ3P2,3FQ3P3,2FQ2P2,2FQ2P3,xFQxP2,xFQxPxy,xFQxPyx例2试将一阶逻辑公式化成前束范式。解xRzQyxPzyxxRzQzyxyPxxRyQyyxyPxxRyyQyxyPxG,,,,第三章集合的基本概念和运算7[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、对偶律等），文氏图3、集合的计数本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明，集合的计数[复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。2、掌握集合的表示法和集合的交、并、差、补等基本运算。3、掌握集合运算基本规律，证明集合等式的方法。4、掌握集合的计数。[疑难解析]1、集合的概念重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。2、集合恒等式的证明重视吸收律和重要等价式在BABA~证明中的特殊作用。习题P71-75:3.8，3.9，3.16，3.17，3.18[例题分析]例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8例2设,,,,babaA，试求：(1)baA,；(2)A；(3)A；(4)Aba,；(5)A；(6)A。解(1),,,babaA(2)AA(3)babaA,,,(4)Aba,(5)A(6)A例3试证明BABABABA~~~~证明BABABABABBBAABAABBAABABABA~~~~~~~~~~~~~第四章二元关系和函数[复习知识点]1、笛卡尔积，关系、关系矩阵2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、映射的概念9[复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。2、掌握求复合关系与逆关系的方法。3、理解关系的性质（自反性、反自反性，对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。4、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。6、理解函数概念：函数、函数相等、复合函数和反函数。7、理解单射、满射、双射等概念，掌握其判别方法。[疑难解析]1、关系的概念理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、偏序关系的基础。要会判断关系的性质。３、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：AIRRr；定理3，1RRRs；定理4，推论niiRRt1。４、半序关系及半序集中特殊元素的确定10理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。５、映射的概念与映射种类的判定映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。习题P112-116:4.4，4.25[例题分析]例1设集合dcbaA,,,，判定下列关系，哪些是自反的，对称的，反对称的和传递的：dbcaRccbbaaRdcRadcbaaRabaaR,,,,,,,,,,,,,,,,,,54321解：均不是自反的；R4是对称的；R1,R2,R3,R4,R5是反对称的；R1,R2,R3,R4,R5是传递的。例2、设集合AA,4,3,2,1上的关系4,3,3,2,1,2,2,1,1,1R，求出它的自反闭包，对称闭包和传递闭包。解：4,4,3,3,2,2,4,3,3,2,1,2,2,1,1,1)(Rr3,4,2,3,4,3,3,2,1,2,2,1,1,1)(Rs4,1,4,2,2,2,3,1,4,3,3,2,1,2,2,1,1