2022年2022年离散数学期末复习要点与重点 .pdf

《2022年2022年离散数学期末复习要点与重点 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年离散数学期末复习要点与重点 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 离散数学期末复习要点与重点大纲（复习以课本和笔记为主。 文中标红为需重点掌握的， 祝大家都能取得好成绩！ ）第 1 章命题逻辑复习要点1理解命题概念，会判别语句是不是命题理解五个基本联结词：否定P、析取、合取、条件、和双条件及其 真值表 ，理解其他联结词的定义及基本等价式，会将简单命题符号化具有确定真假意义的陈述句称为命题命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 2理解公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的构造方法能熟练地作公式真值表理解永真式和永假式概念，掌握其判别方法判定命题公式类型的方法：其一是真值表法，其二是等价演算法. 3了解公式等价

2、概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价演算法、列真值表法和主范式方法4理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法（真值表法和等价推导法）命题公式的范式不惟一，但主范式是惟一 的命题公式 A 有 n 个命题变元， A 的主析取范式有k 个小项，有m 个大项，则nmk2于是有(1) A 是永真式k=2n(m=0)；(2) A 是永假式m2n(k=0)；5了解 C 是前提集合 A1,A2,Am的有效结论或由A1, A2, , Am逻辑地推出C 的概念要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法

3、、直接证法、间接证法重点 ：命题与联结词 ，真值表 ，主析取 (合取)范式 ，命题演算的推理理论. 第 2 章谓词逻辑复习要点1理解谓词、量词、个体词、个体域，会将简单命题符号化原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项谓词用来刻划个体词的性质或之间的关系量词分全称量词，存在量词. 命题符号化注意：使用全称量词，特性谓词后用；使用存在量词，特性谓词后用2了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法由原子公式、联结词和量词构成谓词公式谓词公式具有真值时，才是命题在谓词公式xA 或

4、 xA 中，x 是指导变元， A 是量词的辖域会区分约束变元和自由变元在非空集合D(个体域 )上谓词公式A 的一个解释或赋值有3 个条件在任何解释下，谓词公式A 取真值 1，A 为逻辑有效式 (永真式 )；公式A 取真值0，A为永假式；至少有一个解释使公式A 取真值 1，A 称为可满足式在有限个体域下，消除量词的规则为：设Da1, a2, , an，则)(.)()()(21naAaAaAxxA)(.)()()(21naAaAaAxxA名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1

5、 页，共 5 页 - - - - - - - - - 2 会求谓词公式的真值，量词的辖域， 自由变元、 约束变元， 以及换名规则、 代入规则等掌握谓词演算的等价式和重言蕴含式并进行谓词公式的等价演算3理解前束范式的概念，掌握求公式的前束范式的方法.若一个谓词公式F 等价地转化成BxQxQxQkk.2211，那么BxQxQxQkk.2211就是F的前束范式，其中Q1，Q2，Qk只能是或 ，而 x1, x2, , xk是个体变元， B 是不含量词的谓词公式前束范式仍然是谓词公式重点 ：翻译；前束范式第 3 章集合与关系复习要点1理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟

6、练掌握集合的表示方法集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分掌握集合包含(子集 )、真子集、集合相等等概念注意：元素与集合，集合与子集，子集与幂集，与(), 空集与所有集合等的关系.空集，是惟一的，它是任何集合的子集集合 A 的幂集 P(A)Axx， A 的所有子集构成的集合若A n，则P(A) =2n2熟练掌握集合A 和 B 的并 AB，交 AB，补集A( A 补集总相对于一个全集).差集AB，对称差， AB(AB)(BA)，或 AB(AB)（A B）等运算 掌握集合运算律( 运算的性质 ). 3掌握用集合运算基本规律证明集合恒等式的方法集

7、合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明证明方法有二：(1)要证明 AB，只需证明AB，又 A B；(2)通过运算律进行等式推导4了解有序对和笛卡尔积的概念，掌握笛卡尔积的运算有序对就是有顺序二元组，如，x, y 的位置是确定的，不能随意放置注意：有序对 ，以 a, b 为元素的集合 a, b= b, a；有序对 (a, a)有意义，而集合 a, a 是单元素集合，应记作 a集合 A，B 的笛卡尔积AB 是一个集合，规定AB x A,yB，是有序对的集合 . 笛卡尔积也可以多个集合合成，A1A2An5理解关系的概念：二元关系、空关系、全关系、恒等关系.掌握关系的集

8、合表示、关系矩阵 和关系图，掌握关系的集合运算及复合关系、逆关系的性质与求法二元关系是一个有序对集合，,ByAxyxR，记作 xRy设 A、 B是两个集合，且|A| m ，|B| n，则从A到 B可产生的不同的二元关系个数为nm2。关系的表示方法有三种：集合表示法，关系矩阵： RAB，R 的矩阵njmibRaRbarrMjijiijnmijR,.,2, 1,.,2, 101,)(. 关系图： R 是集合上的二元关系，若R，由结点ai画有向弧到bj构成的图形空关系是唯一、是任何关系的子集的关系；全关系,AbabaEAAA；恒等关系,AaaaIA，恒等关系的矩阵MI是单位矩阵名师资料总结 - -

9、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 3 关系的集合运算有并、交、补、差和对称差复合关系 ),(,2121RcbRbabcaRRR；复合关系矩阵：21RRRMMM(按逻辑运算 )；有结合律： (RS)TR(S T)，一般不可交换逆关系,1RyxxyR；逆关系矩阵满足：TRRMM1；复合关系与逆关系存在：(RS)1=S1R16理解关系的性质(自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示)，掌握其判别方法(利用定义、

10、 矩阵或图， 充分条件 )，知道 关系闭包 （自反，对称，传递）的定义和求法注：(1)关系性质的充分必要条件： R 是自反的IAR；R 是反自反的IAR；R 是对称的RR1；R 是反对称的RR1IA；R 是传递的RRR. (2)IA具有自反性，对称性、反对称性和传递性EA具有自反性，对称性和传递性具有反自反性、对称性、反对称性和传递性重点 ：集合的运算，笛卡尔积，关系的性质，复合关系和逆关系，关系的闭包.第 4 章函数复习要点1理解函数概念：函数(映射 )，函数相等，复合函数和反函数理解单射、满射和双射等概念，掌握其判别方法设 f 是集合 A 到 B 的二元关系，aA，存在惟一b B，使得 f

11、，且 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)(

12、Rangf一般gffg， 但fghfgh)()(. 反函数若f：AB 是双射，则有反函数f1：BA，,)(,1AabafBbabf，ffgffg11111)(,)(重点 ：函数 . 第 5 章代数结构复习要点1掌握代数系统中运算及其性质（自反，对称，传递，等幂），会判断某代数系统具有哪种性质。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 4 2. 掌握半群，独异点，群，阿贝尔群，循环群的概念及判定方法。半群：封闭 +可结合。独

13、异点：封闭+可结合 +有幺元。群：封闭 +可结合 +有幺元 +每个元素有逆元。阿贝尔群：群+可交换。循环群：群 +有生成元。3. 掌握同态与同构的概念，理解同态的相关性质，并熟练掌握同态与同构的证明方法。重点 ：代数系统的运算性质，群与循环群的证明方法，同构与同态的证明方法。第 7 章图的基本概念复习要点1理解图的概念：结点、边、有向图，无向图、简单图、完全图、结点的度数、边的重数和平行边等.理解握手定理图是一个有序对，V 是结点集， E 是联结结点的边的集合掌握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路(环)，无向平行边，有向平行边等概念简单图，不含平行边和环(自回路 )的

14、图、在无向图中，与结点v(V)关联的边数为结点度数deg(v)；在有向图中，以v(V)为终点的边的条数为入度deg(v)，以v(V)为起点的边的条数为出度deg(v)，deg(v)=deg+(v) +deg(v)无向完全图Kn及其边数) 1(21nnE；有向完全图及其边数) 1(nnE了解子图、真子图、补图的概念知道图的同构概念，更应知道图同构的必要条件，用其判断图不同构.重要定理 ：(1) 握手定理设 G=，有VvEv2)deg(；(2) 在有向图D中，VvVvvv)(deg)(deg；(3) 奇数度结点的个数为偶数个2了解路与回路概念会求路和回路的长度了解无向图的连通性，会求无向图的连通分

15、支了解点割集、边割集、割点、割边等概念了解有向图的强连通强性；会判别其类型设图 G，结点与边的交替序列为路路中边的数目就是路的长度 起点和终点重合的路为回路边不重复的路是迹；结点不重复的路是通路. 无向图 G 中， 结点 u, v存在通路，u, v是连通的，G 中任意结点u, v连通，G 是连通图P(G)表示图 G 连通分支的个数要知道：强连通必是单侧连通必是弱连通，反之不成立3掌握邻接矩阵，可达矩阵和距离矩阵的概念，掌握其构造方法及其应用4理解欧拉通路 (回路)、欧拉图的概念，掌握欧拉图的判别方法通过连通图G 的每条边一次且仅一次的路(回路 )是欧拉路 (回路 )存在欧拉回路的图是欧拉图 .

16、 欧拉回路要求边不能重复，结点可以重复笔不离开纸，不重复地走完所有的边，走过所有结点，就是所谓的一笔画欧拉图或通路的判定定理名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 5 (1) 无向连通图G 是欧拉图G 为连通图且G 不含奇数度结点(即 G 的所有结点为偶数度)；(2) 非平凡图 G 含有欧拉路G 为连通图且G 最多有两个奇数度的结点；(3) 连通有向图D 含有有向欧拉回路D 中每个结点的入度出度(4) 连通有向图D 含有

17、有向欧拉路D 中除两个结点外，其余每个结点的入度出度，且此两点满足一个结点的入度比出度大1，另一个结点的出度比入度大15了解汉密尔顿路(回路 )、汉密尔顿图的概念，会做简单判断通过连通图G 的每个结点一次，且仅一次的路(回路 )，是汉密尔顿路(回路 )存在汉密尔顿回路的图是汉密尔顿图. 汉密尔顿图的充分条件和必要条件(1) 在无向简单图G=中，V3，任意不同结点VvuGvu)deg()deg(,，则G 是汉密尔顿图(充分条件 ) (2) 有向完全图D, 若3V，则图 D 是汉密尔顿图 . (充分条件 ) (3) 设无向图 G=，任意 V1V，则 W(GV1)V1(必要条件 ) 若此条件不满足，

18、即存在V1V，使得 P(GV!) V1,则 G 一定不是汉密尔顿图(非汉密尔顿图的充分条件)6了解树、树叶、生成树和最小生成树等概念，掌握求最小生成树的方法连通无回路的无向图是树树的判别可以用图T 是树的充要条件(等价定义 )注意： (1) 树 T 是连通图；(2)树 T 满足 mn1（即边数 =顶点数 -1）图 G 的生成子图是树，该树就是生成树每边指定一正数，称为权， 每边带权的图称为带权图G 的生成树T 的所有边的权之和是生成树 T 的权，记作W(T)最小生成树是带权最小的生成树7了解有向树、根树等概念有向图删去边的方向为树，该图为有向树对非平凡有向树，恰有一个结点的入度为0(该结点为 树根 )，其余结点的入度为1，该树为 根树 有关树的求法 ：(1)生成树的破圈法和避圈法求法；(2)最小生成树的克鲁斯克尔求法；重点 ：图的概念， 握手定理 ，路、回路以及 图的矩阵表示 ，欧拉图 和哈密顿图的基本概念及判别，树与根树的基本概念，最小生成树的求法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -