离散数学期末复习要点与重点

1离散数学期末复习要点与重点大纲（复习以课本和笔记为主。文中标红为需重点掌握的，祝大家都能取得好成绩！）第1章命题逻辑复习要点1．理解命题概念，会判别语句是不是命题．理解五个基本联结词：否定P、析取、合取、条件、和双条件及其真值表，理解其他联结词的定义及基本等价式，会将简单命题符号化．具有确定真假意义的陈述句称为命题．命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2．理解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法．能熟练地作公式真值表．理解永真式和永假式概念，掌握其判别方法．判定命题公式类型的方法：其一是真值表法，其二是等价演算法.3．了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价演算法、列真值表法和主范式方法．4．理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法（真值表法和等价推导法）．命题公式的范式不惟一，但主范式是惟一的．命题公式A有n个命题变元，A的主析取范式有k个小项，有m个大项，则nmk2于是有(1)A是永真式k=2n(m=0)；(2)A是永假式m＝2n(k=0)；5．了解C是前提集合{A1,A2,…,Am}的有效结论或由A1,A2,…,Am逻辑地推出C的概念．要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法．重点：命题与联结词，真值表，主析取(合取)范式，命题演算的推理理论.第2章谓词逻辑复习要点1．理解谓词、量词、个体词、个体域，会将简单命题符号化．原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项．谓词用来刻划个体词的性质或之间的关系．量词分全称量词，存在量词.命题符号化注意：使用全称量词，特性谓词后用；使用存在量词，特性谓词后用．2．了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念．掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法．由原子公式、联结词和量词构成谓词公式．谓词公式具有真值时，才是命题．在谓词公式xA或xA中，x是指导变元，A是量词的辖域．会区分约束变元和自由变元．在非空集合D(个体域)上谓词公式A的一个解释或赋值有3个条件．在任何解释下，谓词公式A取真值1，A为逻辑有效式(永真式)；公式A取真值0，A为永假式；至少有一个解释使公式A取真值1，A称为可满足式．在有限个体域下，消除量词的规则为：设D＝{a1,a2,…,an}，则)(...)()()(21naAaAaAxxA)(...)()()(21naAaAaAxxA2会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等．掌握谓词演算的等价式和重言蕴含式．并进行谓词公式的等价演算．3．理解前束范式的概念，掌握求公式的前束范式的方法.若一个谓词公式F等价地转化成BxQxQxQkk...2211，那么BxQxQxQkk...2211就是F的前束范式，其中Q1，Q2，…，Qk只能是或，而x1,x2,…,xk是个体变元，B是不含量词的谓词公式．前束范式仍然是谓词公式．重点：翻译；前束范式．第3章集合与关系复习要点1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法．集合的表示方法：列举法和描述法.注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分．掌握集合包含(子集)、真子集、集合相等等概念．注意：元素与集合，集合与子集，子集与幂集，与(),空集与所有集合等的关系.空集，是惟一的，它是任何集合的子集．集合A的幂集P(A)＝}{Axx，A的所有子集构成的集合．若A＝n，则P(A)=2n．2．熟练掌握集合A和B的并AB，交AB，补集A(A补集总相对于一个全集).差集A－B，对称差，AB＝(A－B)(B－A)，或AB＝(AB)－（AB）等运算．掌握集合运算律(运算的性质).3．掌握用集合运算基本规律证明集合恒等式的方法．集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明．证明方法有二：(1)要证明A＝B，只需证明AB，又AB；(2)通过运算律进行等式推导．4．了解有序对和笛卡尔积的概念，掌握笛卡尔积的运算．有序对就是有顺序二元组，如x,y，x,y的位置是确定的，不能随意放置．注意：有序对a，bb,a，以a,b为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}是单元素集合，应记作{a}．集合A，B的笛卡尔积A×B是一个集合，规定A×B＝{x,yxA,yB}，是有序对的集合.笛卡尔积也可以多个集合合成，A1×A2×…×An．5．理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集合表示、关系矩阵和关系图，掌握关系的集合运算及复合关系、逆关系的性质与求法．二元关系是一个有序对集合，},{ByAxyxR，记作xRy．设A、B是两个集合，且|A|＝m，|B|＝n，则从A到B可产生的不同的二元关系个数为nm2。关系的表示方法有三种：集合表示法，关系矩阵：RA×B，R的矩阵njmibRaRbarrMjijiijnmijR,...,2,1,...,2,101,)(.关系图：R是集合上的二元关系，若ai,bjR，由结点ai画有向弧到bj构成的图形．空关系是唯一、是任何关系的子集的关系；全关系},,{AbabaEAAA；恒等关系},{AaaaIA，恒等关系的矩阵MI是单位矩阵．3关系的集合运算有并、交、补、差和对称差．复合关系}),,(,{2121RcbRbabcaRRR；复合关系矩阵：21RRRMMM(按逻辑运算)；有结合律：(RS)T＝R(ST)，一般不可交换．逆关系},,{1RyxxyR；逆关系矩阵满足：TRRMM1；复合关系与逆关系存在：(RS)－1=S－1R－1．6．理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、矩阵或图，充分条件)，知道关系闭包（自反，对称，传递）的定义和求法．注：(1)关系性质的充分必要条件：①R是自反的IAR；②R是反自反的IAR＝；③R是对称的R＝R－1；④R是反对称的RR－1IA；⑤R是传递的RRR.(2)IA具有自反性，对称性、反对称性和传递性．EA具有自反性，对称性和传递性．具有反自反性、对称性、反对称性和传递性．重点：集合的运算，笛卡尔积，关系的性质，复合关系和逆关系，关系的闭包.第4章函数复习要点1．理解函数概念：函数(映射)，函数相等，复合函数和反函数．理解单射、满射和双射等概念，掌握其判别方法．设f是集合A到B的二元关系，aA，存在惟一bB，使得a,bf，且Dom(f)=A，f是一个函数(映射)．函数是一种特殊的关系（设A、B是两个集合，且|A|＝m，|B|＝n，则从A到B可产生的不同的函数关系个数为mn）．集合A×B的任何子集都是关系，但不一定是函数．函数要求对于定义域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制．二函数相等是指：定义域相同，对应关系相同，且定义域内的每个元素的对应值都相同．函数有：单射——若)()(2121afafaa；满射——f(A)=B或,,AxBy使得y=f(x)；双射——单射且满射．复合函数,:,:,:CAfgCBgBAf则即))(()(xfgxfg．复合成立的条件：)(Dom)(Rangf．一般gffg，但fghfgh)()(.反函数——若f：AB是双射，则有反函数f－1：BA，},)(,,{1AabafBbabf，ffgffg11111)(,)(重点：函数.第5章代数结构复习要点1．掌握代数系统中运算及其性质（自反，对称，传递，等幂），会判断某代数系统具有哪种性质。42.掌握半群，独异点，群，阿贝尔群，循环群的概念及判定方法。半群：封闭+可结合。独异点：封闭+可结合+有幺元。群：封闭+可结合+有幺元+每个元素有逆元。阿贝尔群：群+可交换。循环群：群+有生成元。3.掌握同态与同构的概念，理解同态的相关性质，并熟练掌握同态与同构的证明方法。重点：代数系统的运算性质，群与循环群的证明方法，同构与同态的证明方法。第7章图的基本概念复习要点1．理解图的概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理．图是一个有序对V，E，V是结点集，E是联结结点的边的集合．掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路(环)，无向平行边，有向平行边等概念．简单图，不含平行边和环(自回路)的图、在无向图中，与结点v(V)关联的边数为结点度数deg(v)；在有向图中，以v(V)为终点的边的条数为入度deg－(v)，以v(V)为起点的边的条数为出度deg＋(v)，deg(v)=deg+(v)+deg－(v)．无向完全图Kn及其边数)1(21nnE；有向完全图及其边数)1(nnE．了解子图、真子图、补图的概念．知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构.重要定理：(1)握手定理设G=V，E，有VvEv2)deg(；(2)在有向图D＝V,E中，VvVvvv)(deg)(deg；(3)奇数度结点的个数为偶数个．2．了解路与回路概念．会求路和回路的长度．了解无向图的连通性，会求无向图的连通分支．了解点割集、边割集、割点、割边等概念．了解有向图的强连通强性；会判别其类型．设图G＝V，E，结点与边的交替序列为路．路中边的数目就是路的长度．起点和终点重合的路为回路．边不重复的路是迹；结点不重复的路是通路.无向图G中，结点u,v存在通路，u,v是连通的，G中任意结点u,v连通，G是连通图．P(G)表示图G连通分支的个数．要知道：强连通必是单侧连通必是弱连通，反之不成立．3．掌握邻接矩阵，可达矩阵和距离矩阵的概念，掌握其构造方法及其应用．4．理解欧拉通路(回路)、欧拉图的概念，掌握欧拉图的判别方法．通过连通图G的每条边一次且仅一次的路(回路)是欧拉路(回路)．存在欧拉回路的图是欧拉图.欧拉回路要求边不能重复，结点可以重复．笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画．欧拉图或通路的判定定理5(1)无向连通图G是欧拉图G为连通图且G不含奇数度结点(即G的所有结点为偶数度)；(2)非平凡图G含有欧拉路G为连通图且G最多有两个奇数度的结点；(3)连通有向图D含有有向欧拉回路D中每个结点的入度＝出度．(4)连通有向图D含有有向欧拉路D中除两个结点外，其余每个结点的入度＝出度，且此两点满足一个结点的入度比出度大1，另一个结点的出度比入度大1．5．了解汉密尔顿路(回路)、汉密尔顿图的概念，会做简单判断．通过连通图G的每个结点一次，且仅一次的路(回路)，是汉密尔顿路(回路)．存在汉密尔顿回路的图是汉密尔顿图.汉密尔顿图的充分条件和必要条件(1)在无向简单图G=V，E中，V3，任意不同结点VvuGvu)deg()deg(,,，则G是汉密尔顿图．(充分条件)(2)有向完全图D＝V，E,若3V，则图D是汉密尔顿图.(充分条件)(3)设无向图G=V，E，任意V1V，则W(G－V1)V1(必要条件)若此条件不满足，即存在V1V，使得P(G－V!)V1,则G一定不是汉密尔顿图(非汉密尔顿图的充分条件)．6．了解树、树叶、生成树和最小生成树等概念，掌握求最小生成树的方法．连通无回路的无向图是树．树的判别可以用图T是树的充要条件(