电大离散数学期末复习要点与重点考试资料参考答案11994.pdf

《电大离散数学期末复习要点与重点考试资料参考答案11994.pdf》由会员分享，可在线阅读，更多相关《电大离散数学期末复习要点与重点考试资料参考答案11994.pdf（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 电大离散数学期末复习要点与重点考试资料参考答案 F o u r s h o r t w o r d s s u m u p w h a t h a s l i f t e d m o s t s u c c e s s f u l i n d i v i d u a l s a b o v e t h e c r o w d:a l i t t l e b i t m o r e.-a u t h o r -d a t e 5 精品电年夜复习资料1 电年夜离散数学期末复习要点与重点考试资料参考答案 离散数学是中心广播电视年夜学开放教育本科电气信息类计较机科学与手艺专业的一门统设必修学位课程，

2、共 72 学时，开设一学期该课程的首要内容搜罗：集结论、图论、数理规律等 下面按章给出复习要点与重点 第 1章 集结及其运算 复习要点 1理解集结、元素、集结的包含、子集、相等，以及全集、空集和幂集等概念，谙练把握集结的示意体例 具有确定的，可以区分的若干事物的全体称为集结，其中的事物叫元素.集结的示意体例：列举法和描述法.留意：集结的示意中元素不能一再呈现，集结中的元素无挨次之分 把握集结包含(子集)、真子集、集结相等等概念 留意：元素与集结，集结与子集，子集与幂集，与(),空集与全部集结等的关系.空集，是惟一的，它是任何集结的子集 集结 A的幂集 P(A)Axx，A的全部子集组成的集结若A

3、n，则P(A)=2n 2谙练把握集结 A和 B的并 AB，交 AB，补集A(A补集总相对于一个全集).差集 AB，对称差，AB(AB)(BA)，或 AB(AB)（AB）等运算，并会用文氏图示意 把握集结运算律(赐教材第 911 页)(运算的性质).3把握用集结运算根基纪律证明集结恒等式的体例 集结的运算问题：其一是进行集结运算；其二是运算式的化简；其三是恒等式证明 证明体例有二：(1)要证明 AB，只需证明 AB，又 AB；(2)经由过程运算律进行等式推导 重点：集结概念，集结的运算，集结恒等式的证明 第 2章 关系与函数 复习要点 1体会有序对和笛卡儿积的概念，把握笛卡儿积的运算 有序对就是

4、有挨次二元组，如，x,y 的位置是确定的，不能任凭放置 留意：有序对，以 a,b 为元素的集结a,b=b,a；有序对(a,a)有意义，而集结a,a是单元素集结，应记作a 集结 A，B的笛卡儿积 AB是一个集结，划定 ABxA,yB，是有序对的集结.笛卡儿积也可以多个集连系成，A1A2An 2理解关系的概念：二元关系、空关系、全关系、恒等关系.把握关系的集结示意、关系矩阵和关系图，把握关系的集结运算和求复合关系、逆关系的体例 二元关系是一个有序对换集，,ByAxyxR，记作 xRy 关系的示意体例有三种：集结示意法，关系矩阵：RAB，R的矩阵njmibRaRbarrMjijiijnmijR,.,

5、2,1,.,2,101,)(.关系图：R是集结上的二元关系，若 R，由结点ai画有向弧到 bj组成的图形 空关系是独一、是任何关系的子集的关系；全关系,AbabaEAAA；5 精品电年夜复习资料2 恒等关系,AaaaIA，恒等关系的矩阵MI是单元矩阵 关系的集结运算有并、交、补、差和对称差 复合关系),(,2121RcbRbabcaRRR；复合关系矩阵：21RRRMMM(按布尔运算)；有连系律：(RS)TR(ST)，一般不成沟通 逆关系,1RyxxyR；逆关系矩阵知足：TRRMM1；复合关系与逆关系存在：(RS)1=S1R1 3理解关系的性质(自反性和反自反性、对称性和拒绝称性、传递性的界说以

6、及矩阵示意或关系图示意)，把握其判别体例(操作界说、矩阵或图，充实前提)，知道关系闭包的界说和求法 注：(1)关系性质的充实需要前提：R是自反的IAR；R是反自反的IAR；R是对称的 RR1；R是拒绝称的RR1IA；R是传递的RRR.(2)IA具有自反性，对称性、拒绝称性和传递性EA具有自反性，对称性和传递性故 IA，EA是等价关系具有反自反性、对称性、拒绝称性和传递性IA也是偏序关系 4理解等价关系和偏序关系概念，把握等价类的求法和作偏序集哈斯图的体例知道极年夜(小)元，最年夜(小)元的概念，会求极年夜(小)元、最年夜(小)元、最小上界和最年夜下界 等价关系和偏序关系是具有分歧性质的两个关系

7、.偏序关系等价关系传递性反对称性对称性自反性 知道等价关系图的特点和等价类界说，会求等价类 一个子集的极年夜(小)元可以有多个，而最年夜(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外由哈斯图便于确定任一子集的最年夜(小)元，极年夜(小)元 5理解函数概念：函数(映射)，函数相等，复合函数和反函数理解单射、满射和双射等概念，把握其判别体例 设 f 是集结 A到 B的二元关系，aA，存在惟一 bB，使得f，且 Dom(f)=A，f 是一个函数(映射)函数是一种非凡的关系 集结 AB的任何子集都是关系，但不必定是函数函数要求对于界说域 A 中每一个元素 a，B中有且仅有一

8、个元素与 a 对应，而关系没有这个限制 二函数相等是指：界说域不异，对应关系不异，而且界说域内的每个元素的对应值都不异 函数有：单射若)()(2121afafaa；满射f(A)=B 或,AxBy使得 y=f(x)；双射单射且满射 复合函数,:,:,:CAfgCBgBAf则 即)()(xfgxfg 复合成立的前提是：)(Dom)(Rangf 一般gffg，但fghfgh)()(.反函数若 f：AB是双射，则有反函数 f1：BA，,)(,1AabafBbabf，ffgffg11111)(,)(重点：关系概念与其性质，等价关系和偏序关系，函数.5 精品电年夜复习资料3 第 3章 图的根基概念 复习要

9、点 1理解图的概念：结点、边、有向图，无向图、简洁图、完全图、结点的度数、边的重数和平行边等.理解握手定理 图是一个有序对，V是结点集，E是联络结点的边的集结 把握无向边与无向图，有向边与有向图，同化图，零图，通俗图、自回路(环)，无向平行边，有向平行边等概念 简洁图，不含平行边和环(自回路)的图、在无向图中，与结点 v(V)联系关系的边数为结点度数deg(v)；在有向图中，以 v(V)为终点的边的条数为入度deg(v)，以 v(V)为起点的边的条数为出度deg(v)，deg(v)=deg+(v)+deg(v)无向完全图 Kn以其边数)1(21nnE；有向完全图以其边数)1(nnE 体会子图、

10、真子图、补图和生成子图的概念 生成子图设图 G，若 EE，则图是的生成子图 知道图的同构概念，更应知道图同构的需要前提，用其判定图分歧构.主要定理：(1)握手定理 设 G=，有VvEv2)deg(；(2)在有向图 D中，VvVvvv)(deg)(deg；(3)奇数度结点的个数为偶数个 2体会通路与回路概念：通路(简洁通路、根基通路和简单通路)，回路(简洁回路、根基回路和简单回路)会求通路和回路的长度根基通路(回路)必是简洁通路(回路)体会无向图的连通性，会求无向图的连通分支体会点割集、边割集、割点、割边等概念体会有向图的强连通强性；会判别其类型 设图 G，结点与边的交替序列为通路通路中边的数目

11、就是通路的长度起点和终点重合的通路为回路边不一再的通路(回路)是简洁通路(回路)；结点不一再的通路(回路)是根基通路(回路).无向图 G中，结点 u,v 存在通路，u,v是连通的，G中肆意结点 u,v 连通，G是连通图P(G)示意图 G连通分支的个数 在无向图中，结点集 VV，使得 P(GV)P(G)，而肆意 VV,有 P（GV）P(G)，V为点割集.若 V是单元集，该结点 v叫割点；边集 EE，使得 P(GV)P(G)，而肆意 EE，有 P（GE）P(G)，E为边割集若 E是单元集，该边 e叫割边(桥)要知道：强连通 必是单侧连通 必是弱连通，反之不成立 3体会邻接矩阵和可达矩阵的概念，把握

12、其机关体例及其应用 重点：图的概念，握手定理，通路、回路以及图的矩阵示意 第 4章 几种非凡图 复习要点 1理解欧拉通路(回路)、欧拉图的概念，把握欧拉图的判别体例 经由过程连通图 G的每条边一次且仅一次的通路(回路)是欧拉通路(回路)存在欧拉回路的图是欧拉图.欧拉回路要求边不能一再，结点可以一再笔不分开纸，不一再地走完全部的边，走过全部结点，就是所谓的一笔画 5 精品电年夜复习资料4 欧拉图或通路的剖断定理 (1)无向连通图 G是欧拉图G不含奇数度结点(即 G的全部结点为偶数度)；(2)非通俗连通图 G含有欧拉通路G最多有两个奇数度的结点；(3)连通有向图 D含有有向欧拉回路D中每个结点的入

13、度出度 连通有向图 D含有有向欧拉通路D中除两个结点外，其余每个结点的入度出度，且此两点知足 deg(u)deg(v)1 2理解汉密尔顿通路(回路)、汉密尔顿图的概念，会做简洁判定 经由过程连通图 G的每个结点一次，且仅一次的通路(回路)，是汉密尔顿通路(回路)存在汉密尔顿回路的图是汉密尔顿图.汉密尔顿图的充实前提和需要前提 (1)在无向简洁图 G=中，V3，肆意分歧结点VvuGvu)deg()deg(,，则 G是汉密尔顿图(充实前提)(2)有向完全图 D,若3V，则图 D是汉密尔顿图.(充实前提)(3)设无向图 G=，肆意 V1V，则 W(GV1)V1(需要前提)若此前提不知足，即存在 V1

14、V，使得 P(GV!)V1,则 G必定不是汉密尔顿图(非汉密尔顿图的充实前提)3体会平面图概念，平面图、面、鸿沟、面的次数和非平面图把握欧拉公式的应用 平面图是指一个图能画在平面上，除结点之外，再没有边与边订交 面、鸿沟和面的次数)deg(r等概念 主要结论：(1)平面图ereEvVEVGrii2)deg(,1则(2)欧拉公式：平面图,eEvVEVG 面数为 r，则2rev(结点数与面数之和边数2)(3)平面图633,veveEvVEVG，则若 会用界说剖断一个图是不是平面图 4理解平面图与对偶图的关系、对偶图在图着色中的浸染，把握求对偶图的体例 给定平面图GV，E，它有面F1，F2，Fn，若

15、有图G*V*，E*知足下述前提：对于图G的任一个面Fi，内部有且仅有一个结点vi*V*；对于图G的面Fi，Fj的公共边ek，存在且仅存在一条边ek*E*，使ek*(vi*，vj*)，且ek*和ek订交；当且仅当ek只是一个面Fi的鸿沟时，vi*存在一个环ek*和ek订交；则图G*是图G的对偶图 若G*是G的对偶图，则G也是G*的对偶图一个连通平面图的对偶图也必是平面图 5把握图论中常用的证明体例 重点：欧拉图和哈密顿图、平面图的根基概念及判别 第 5章 树及其应用 复习要点 1体会树、树叶、分支点、通俗树、生成树和最小生成树等概念，把握求最小生成树的体例 连通无回路的无向图是树树的判别可以用图

16、 T 是树的充要前提(等价界说)留意：(1)树 T 是连通图；(2)树 T 知足 mn1（即边数=极点数-1）图 G的生成子图是树，该树就是生成树 5 精品电年夜复习资料5 每边指定一正数，称为权，每边带权的图称为带权图 G的生成树 T 的全部边的权之和是生成树 T 的权，记作 W(T)最小生成树是带权最小的生成树 2体会有向树、根树、有序树、二叉树、二叉完全树、正则二叉树和最优二叉树等概念体会带权二叉树、最优二叉树的概念，把握用哈夫曼算法求最优二叉树的体例 有向图删去边的标的目的为树，该图为有向树 对非通俗有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树 每个结

17、点的出度小于或等于 2的根树为二叉树；每个结点的出度等于 0 或 2 的根树为二叉完全树；每个结点的出度等于 2 的根树称为正则二叉树 有关树的求法：(1)生成树的破圈法和避圈法求法；(2)最小生成树的克鲁斯克尔求法；(3)最优二叉树的哈夫曼求法 重点：树与根树的根基概念，最小生成树与最优二叉树的求法.第 6章 命题规律 复习要点 1理解命题概念，会判别语句是不是命题理解五个联络词：否认P、析取、合取、前提、和双前提及其真值表，会将简洁命题符号化 具有确定真假意义的陈述句称为命题 命题必需具备：其一，语句是陈述句；其二，语句有独一确定的真假意义.2体会公式的概念(公式、赋值、成真指派和成假指派

18、)和公式真值表的机关体例能谙练地作公式真值表理解永真式和永假式概念，把握其判别体例 剖断数题公式类型的体例：其一是真值表法，其二是等价演算法.3体会公式等价概念，把握公式的主要等价式和判定两个公式是否等价的有用体例：等价演算法、列真值表法和主范式体例 4理解析取范式和合取范式、极年夜项和微小项、主析取范式和主合取范式的概念，谙练把握它们的求法 命题公式的范式不惟一，但主范式是惟一的 命题公式 A有 n 个命题变元，A的主析取范式有k个微小项，有 m个极年夜项，则 nmk2 于是有(1)A是永真式k=2n(m=0)；(2)A是永假式m2n(k=0)；求命题公式 A的析取(合取)范式的轨范：赐教材

19、第 174 页 求命题公式 A的主析取(合取)范式的轨范：赐教材第 177和 178页 5体会 C 是前提集结A1,A2,Am的有用结论或由 A1,A2,Am 规律地推出 C 的概念要理解并把握推理理论的轨则、重言蕴含式和等价式，把握命题公式的证明体例：真值表法、直接证法、间接证法 重点：命题与联络词，公式与诠释，真值表，公式的类型及剖断，主析取(合取)范式，命题演算的推理理论.第 7章 谓词规律 复习要点 1理解谓词、量词、个体词、个体域，会将简洁命题符号化 5 精品电年夜复习资料6 原子命题分成个体词和谓词，个体词可所以具体事物或抽象的概念，分个体常项和个体变项谓词用来刻划个体词的性质或之

20、间的关系 量词分全称量词，存在量词.命题符号化留意：使用全称量词，特征谓词后用；使用存在量词，特征谓词后用 2体会原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念把握在有限个体域下消去公式的量词和求公式在给定诠释下真值的体例 由原子公式、联络词和量词组成谓词公式谓词公式具有真值时，才是命题 在谓词公式xA或xA 中，x是指导变元，A 是量词的辖域会区分约束变元和自由变元 在非空集结 D(个体域)上谓词公式 A的一个诠释或赋值有 3 个前提 在任何诠释下，谓词公式 A取真值 1，A为规律有用式(永真式)；公式 A 取真值 0，A为永假式；至少有一个诠释使公式 A 取真值 1，A称为可知

21、足式 在有限个体域下，消弭量词的轨则为：设Da1,a2,an，则)(.)()()(21naAaAaAxxA)(.)()()(21naAaAaAxxA 会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名轨则、代入轨则等 把握谓词演算的等价式和重言蕴含式并进行谓词公式的等价演算 3体会前束范式的概念，会求公式的前束范式的体例.若一个谓词公式 F等价地转化成 BxQxQxQkk.2211，那么BxQxQxQkk.2211就是 F的前束范式，其中 Q1，Q2，Qk只能是或，而 x1,x2,xk是个体变元，B是不含量词的谓词公式前束范式仍旧是谓词公式 4体会谓词规律推理的四个轨则会给出推理证明 谓词演算的推理是命题演算推理的推广和扩充，命题演算中根基等价式，重言蕴含式以及P，T，CP轨则在谓词演算中仍旧使用谓词规律的推理演算引入了US 轨则(全称量词指定例则)，UG 轨则(全称量词推广轨则)，ES 轨则(存在量词指定例则)，EG 轨则(存在量词推广轨则)等.重点：谓词与量词，公式与诠释，谓词演算 5 精品电年夜复习资料7