《离散数学》期末复习提要汇总

1、高散数学期末员习提要课程的主要内容1、集合论部分（集合的基本概念和运算、二元关系和函数）：2、数理逻辑部分（命题逻辑、渭词逻辑）：3、图论部分（图的基本概念、特殊的图，树及其性质）。一. 各章复习要求与重点第一章命题逻辑复习知识点1、命题与联结词（否定、忻取、合取、猿涵、等1介），复合命题2、命题公式与解释，真值表，公式分类（永真、矛盾、可满足），公式的等1介3、忻取范式、合取范式，极小（大）项，主忻取范式、主合取范式4、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）5、全功能集6、推理理论本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、推理理论复

2、习要求1、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。2、理解公式与解释的概念；掌握求给定公式真值表的方法,用基本等价式化简其他公式，公式在解释下 的真值。3、了解忻取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本 等价式或真值表桁公式化为主析取（合取）范式的方法。4、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法.掌握24个重要等值式。5、掌握推理理论,会写出推理的证明，掌握附加前提证明法和归谬发。本章重点习题习题 P31-36： 1.1,1.7-1.9,1.12,1.18,1.19 f 1.15疑

3、难解析1、公式恒真性的判定判定公式的恒真性，包括判定公式是恒真的或是恒假的.具体方法有两种，一是真值表法，对于任 给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1 （或全为0 ）,就可以判定该 公式是否恒真（或恒假），若不全为0,则为可满足的。二是推导法，即利用基本等价式推导出结果为1 , 或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式） 中，每个子句（短语）均至少包含一个原子及其否定.这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范 式也同样。2、范式求范式,包括求析取范式、合取范式、主析取范

4、式和主合取范式.关耀有两点：一是准确理解掌握 定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等靠律，使相同 的短语（或子句）只保留一个。3、推理理论掌握构造证明法,一是要理解并掌握8个推理定理.二是会使用常用的推理规则，附加前提证明法和 归谬法,需要进行一定的练习。例题分析例1求G = （PaQ）vR）t P的主析取范式与主合取范式。解（1）求主忻取范式,方法1:利用真值表求解P Q RPA0(尸八Q)vRG0 0 00100 0 10010 1 00100 1 10011 0 00111 0 10011 1 01111 1 1111因此G = (iP a yQ

5、 a R) v (iP 八 Q a R)v(P ai(2 A -iR)v(P 八yQ 八 R)v(P a Q a >/?) V(P A (2 A /?)方法2 ：推导法G = (P Q)R vR).尸=(P a 0) v) v 尸=(P v ->(2)a R)vP =(尸 a R)v (->0 a R)v P=(P a R) A (。v e)v (Q a R)人(P vP) v(P/(QvQ)a(RvR)=(P Z Q R)V (P A Q A /?) V(P A Q A /?) V (P A Q A /?) v(Pa2a/?)v(Pa(2a -i/?)v (Pa-1(?八

6、R)v(P 八Q aR) =(iP A(2 A/?)V (1P A -1Q A /?)v(P A -1(2 八 R)v(P 八Q 八 R) V(P A (2 A T?) V (尸 A -1。八R)(2 )求主合取范式方法1 :利用上面的真值表(尸八Q)vR)f P为0的有两行,它们对应的极大项分别为PvQvR,因此，(P/Q)vJ?) - P =(P v Q v /?)a(P v -10 v R)方法2 :利用已求出的主析取范式求主合取范式已用去6个极小项，尚有2个极小项，即P a Q a R 与一P a Q 八一R 于是G (P a Q a R) v (P a Q R)G = -1(iG)=

7、 1(P a Q a i/?) v (P a(2 a iR)=(PvQv R)a(P v-iQv R)例2试证明公式G = (p 一 0)八(Q - /?) f (P . R)为恒真公式。证法：G=-n ( (PvQ ) a ( -.QvR ) ) v ( -nPvR )=(Pa-iQ ) V ( Qa-iR ) V-nPvR=(PvQ ) a ( Pv-tR ) a ( -)QvQ ) a ( -nQv-iR ) ) vP ) vR=(PvQv-tP ) A ( PViRv-iP ) A ( -.Qv-iRv-nP ) ) vR=(1a ( -.Qv-Rv-iP ) ) vR=-iQvRvP

8、vR=1故G为恒真公式。例3构造下面的推理证明前提:p->(qvr), "八s结论：q证明：p”前提引入p化简p->(qvr) 醐是引入qvr取言推理s化简s>-»r前提引入0取言推理q折取三段论推理正确。第二章一阶逻辑复习知识点1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）2、一阶逻辑公式与解释，谓词公式的类型（永真、矛盾、可满足）3、一阶逻辑公式等值式4、前束范式本章重点内容：谓词与量词、公式与解释、前束范式复习要求1、理解遣词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题； 了解命题符号化。2、理解公式与

9、解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解 谓词公式的类型。3、证明等值式。4、掌提求公式前束范式的方法.本章重点习题习题 P52-55 : 2.3 , 2.12,2.13,2.14, 2.15疑难解析1、谓词与量词反宴理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的目由性、约束性与换名 规则。2、公式与解释能桁一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后桁解释I中的数值代入公式， 求出真值。3、前束范式在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式(一阶逻辑中)，将 给定公式中量词提到母式之前称为首标。典型例

10、题例1设I是如下一个解释：D = 2,3F F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3)3-20II16 I求 *Dy(P(x)八 Q(F(x), y)的真值。解mxDy(P(x)八 Q(F(x),y)="(P(x)八 Q(F(x),2人(P(x)aQ(F(x),3)=(P(2)八 Q(F(2)2)八(P(2)八 Q(F 3)V (P(3)a Q(F(3),2)A (P(3)a Q(F(3).3)= (OaO)a(Oa1)v(1a1)a(1a1)= Ovl=1例2试将一阶逻辑公式化成前束范式。解G =大缶P(.3)v (孙2(y)v 刈刈)=3

11、A(3yP(x, y)v (吁。(y) v R(x)=3x(3yP(x,y)v Vz->Q(z)v R(x)=3x3yVz(P(x, y)v-)g(z)v R(x)第三章集合的基本概念和运算复习知识点1、隼合、元素、隼合的表示方法、子集、空集、全集、隼合的包含、相等、鬲隼2、隼合的交、并、差、补等运算及其运算律(交换律、结合律、分配律、吸收律、对偶律等)，文氏图3、隼合的计数本章重点内容：隼合的概念、隼合的运算性质、集合恒等式的证明,隼合的计数复习要求1、理解隼合；元素、子集、空集、全集、隼合的包含、相等、黑隼等基本概念。2、掌提集合的表示法和隼合的交、并、差、补等基本运算.3、掌提集合

12、运算基本规律，证明隼合等式的方法.4、掌逞集合的计数。疑难解析1、隼合的概念重点对幕里加以掌握,一是掌握零集的构成,一是掌握募集元数为212、隼合恒等式的证明重视吸收律和重要等价式在力- 8 = A c 8证明中的特殊作用。习题 P71-75： 3.8 , 3.9 f 3.16 , 3.17 , 3.18例题分析例 1 设 A , B 是两个集合，A=1 ,2,3, B=1 , 2,则"(A)-p(B) =。解 0(A) = 。,1,2,3,1,2,1,3,2,3,1,2,3。(8) = 0,1,2,1,2于是"(A) "(8) = 3,1,3,2,3,1,2,3

13、例2设4 = 。力,。力,中,试求：(1)4一力 ; (2)A ；(3)A -;(4)/ A ;一A ;A.解 A-a, = a,Z?.A-=A (3)A - = ,",”(4)。1一从=中(5)一 4 一 A = <D例 3 试证明(A0 8)c( A 0 8)=(Ac8)u( Ac B)证明(A(A A /( /( z( /l =AGC B)2 B)r> B)c B)c A)d( Be A)3(Ac8)kj( Be第四章二元关系和函数复习知识点1、笛卡尔积，关系、关系矩阵2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（目反闭包、对

14、称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、±/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、映射的概念复习要求1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的隼合表示、关系矩阵和关系图、 关系的运算.2、掌提求复合关系与逆关系的方法.3、理解关系的性质（自反性、反目反性,对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、 图）。4、掌提求关系的闭包（目反闭包、对称闭包、传递闭包）的方法。5、理解引介关系和偏

15、序关系的概念，掌提等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/ 小元、上/下界、最小上界、最大下界的求法.6、理解函数概念：函数、函数相等、复合函数和反函数。7、理解单射、满射、双1寸等概念，掌握其判别方法。疑难解析1、关系的概念理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。2、关系的性质及其判定关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等1介关系、偏序关系的基础。要 会判断关系的性质。3、关系的闭包在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：nr（R）=R<j!A ;定理3, s（R）=RuR7 ;定理4,推论 f（H

16、）= |jW。r-i4、半序关系及半序隼中特殊元素的确定14理解与掌握半序关系与半序隼概念的关键是哈斯图.哈斯图画法掌握了，对于确定任一子隼的最大(小)元，极大(小)元也就容易了。这里要注意，最大(小)元与极大(小)元只能在子隼内确定.而 上界与下界可在子隼之外的全里中确定，最小上界为所有上界中最小者，最小上界再小也不小于子里中的 任一元素.可以与某一元素相等,最大下界也同样。5、映射的概念与映射种类的判定映射的种类主韵旨单射、满射、双射与三俸非满射.判定的方法除定义外，可借助于关系图，而实 数隼的子隼上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数.习题 P112-116： 4.4

17、, 4.25例题分析例1设集合A = ,/?,，,，,判定下列关系，哪些是目反的，对称的，反对称的和传递的：凡=(。,4),(4。) R2 = («,«),(Z?,c),(f/,6Z) R、= (C,4) & = (a,a,),(/?,),(c,c) & =(a,c),(b,d)解：均不是目反的；R4是对称的；R1,R2术3, R4,R5是反对称的；心人2人3, 口4求5是传递的.例2、设隼合A = 123,4,4上的关系R = 。,(1，2),(2，1)，(2,3),0,4),求出它的自反闭包， 对称闭包和M专递闭包。解"(/?) = (1,1)

18、, (1,2), (2,1), (2,3), (3,4), (2,2), (3,3), (4,4)s(R)=11,1),(2,3乂3,4),(3,2*4,3)t(R) = (1,1),(12),(2,1),(2,3), (3,4), (1,3),(2,2),(2,4), (1,4)第五-七章图论复习知识点1、无向图、有向图，通路，回路，连通分支2、关联矩阵、邻接矩阵，可达矩阵3、二部国，欧拉图，哈空顿图，平面图本章重点内容：图的基本概念，特殊图的判定复习要求1、理解图的有关概念:图、完全图、子图、图的同构.2、掌握图的矩阵表示（关联矩阵、邻接矩阵）。3、学会判断特殊的图.4、理解无向树与有向树

19、的概念.疑难解析本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图；路、简单路、回路； 连通分支；二部图欧拉图.哈密顿图，平面图；树等。典型例题例1在具有n个顶点的完全图Kn中删去多少条边才能得到树?解：n个顶点的完全图4中共有nx （ n-1） /2条边，n个顶点的树应有nl条边，于是，删去的边有：nx （ n-1） /2- （ n-1） = （ n-1） x （ n-2 ） /2二.考核说明本课程的考核按平时成绩30%期末考试70%的分配进行考核.期末考试实行统一闭卷考核.试卷满分为100.（考试时间为110分钟）.1、试题类型试题类型有选择题（分数占5% ）、填空题（分

20、数占15% ）、计算题（分数占21% ）,证明题（分 数占28% ）和解答题（分数占21% ）.2、考核试卷题量分配试卷题量在各部分的分配是：隼合论约占40% ,数理逻辑约占50% ,图论约占10%.嫁合练习及解答(-)填空题1、请把“大于3而小于或等于7的整数里合用任一种隼合的表示方法表示出来A=2、Af B 是两个集合，A=1 ,2,3,4, B=2 , 3 , 5,则 B-A=f p ( B ) -p ( A )=, p(B)的元素个数为。3、设4 = 0, 8 = 1,2,则从A到B的所有映射.4、设命题公式G = Pf(Q -> R),则使公式G为假的解释是、 和。5、全集 E

21、=1,2,3,4,5 , A=1 , 5 , B=1 ,2,3,4, C=2 , 5,求 AcB=p(A ) np ( C ) =,C=o6、表达式VxaL (xf y)中消词的定义域是a , b , c),将其中的星词消除，写成与之等价的命题公式为 0(二)单项选择题(选择一个正确答案的代号，填入括号中)1.设命题公式G = (PvP)f (QaR)vP),则6是().A.永真的B.永假的C .可满足的D.析取范式2、设隼合4 = 。,/?,。上的关系7? = (。,。),(。,/?),("。)，则店=()。(A) (",4),(4,),(“©(8)(a,A),

22、(a,c),(b,c);(C)(a,b),(a,c),(b,b);(D) (a,a), (a,b), (c,c).3、一个公式在等价意义下，下面哪个写法是唯一的()。A,折取范式 B.合取范式 C.主析取范式D.以上答室都不对4、设命题公式G=( PtQ ) , H=P-> ( Q-P )，则G与H的关系是().A . G=H B,H=G C . G=H D .以上都不是5、下列命题正确的是()。A . g(|)= B g4>=0 C . aea f b r c) D . (|)wa , b , c 6、设隼合 A=a , b , c , A 上的关系 R=( ( a z b )

23、, (a,c) r (b,a) , (brc) r (c,a) , (cb ) , ( c , c ) ,则R具有关系的()性质。A.目反 B .对称 C.传递 D.反对称7、设 R 为实数集，映R , o ( X ) = -2+2XT ,贝 11。是()。A.单射而非满射B.满射而非单射(2,双1寸D.既不是单射，也不是满射&下列语句中，()是命题。A.下午有会吗？ B.这朵花多好看呀！ C.2是常数 D.请把门关上.9、下面给出的一阶逻辑等价式中,()是措的。A . Vx ( A ( X ) vB ( X ) ) =VxA ( X ) vVxB ( X )B . A->VXB ( X ) =VX ( A-B(X)C . 3x ( A ( X ) vB ( x ) ) =3xA ( X ) v3xB ( X )D . -nVxA ( X ) =3x ( M ( X )(三)计算题1、设R和S是隼合A= 1,2,3,4上的关系，其中R = (1,1), (1,3), (2,3), (3,4)S = (1,2), (2,3), (2,4), (4,4)(1写出R和S的关系矩阵；(2)计算 RS, RuS, R-i, S-Lr"。2、设 A=a , b , c , d , & , R2 是 A 上的关系，其中 &= (a,a),(a,b),