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

Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date电大离散数学期末复习要点与重点考试资料参考答案5电年夜离散数学期末复习要点与重点考试资料参考答案离散数学是中心广播电视年夜学开放教育本科电气信息类计较机科学与手艺专业的一门统设必修学位课程，共72学时，开设一学期该课程的首要内容搜罗：集结论、图论、数理规律等下面按章给出复习要点与重点第1章 集结及其运算复习要点1理解集结、元素、集结的包含、子集、相等，以及全集、空集和幂集等概念，谙练把握集结的示意体例具有确定的，可以区分的若干事物的全体称为集结，其中的事物叫元素.集结的示意体例：列举法和描述法. 留意：集结的示意中元素不能一再呈现，集结中的元素无挨次之分把握集结包含(子集)、真子集、集结相等等概念留意：元素与集结，集结与子集，子集与幂集，与(),空集与全部集结等的关系.空集，是惟一的，它是任何集结的子集集结A的幂集P(A)， A的全部子集组成的集结若An，则P(A)=2n2谙练把握集结A和B的并AB，交AB，补集A(A补集总相对于一个全集).差集AB，对称差，AB(AB)(BA)，或AB(AB)（AB）等运算，并会用文氏图示意把握集结运算律(赐教材第911页)(运算的性质).3把握用集结运算根基纪律证明集结恒等式的体例集结的运算问题：其一是进行集结运算；其二是运算式的化简；其三是恒等式证明证明体例有二：(1)要证明AB，只需证明AB，又AB；(2)经由过程运算律进行等式推导重点：集结概念，集结的运算，集结恒等式的证明第2章 关系与函数复习要点1体会有序对和笛卡儿积的概念，把握笛卡儿积的运算有序对就是有挨次二元组，如，x, y 的位置是确定的，不能任凭放置 留意：有序对，以a, b为元素的集结a, b=b, a；有序对(a, a)有意义，而集结a, a是单元素集结，应记作a集结A，B的笛卡儿积AB是一个集结，划定ABxA,yB，是有序对的集结.笛卡儿积也可以多个集连系成，A1A2An 2理解关系的概念：二元关系、空关系、全关系、恒等关系.把握关系的集结示意、关系矩阵和关系图，把握关系的集结运算和求复合关系、逆关系的体例二元关系是一个有序对换集，记作xRy 关系的示意体例有三种：集结示意法， 关系矩阵：RAB，R的矩阵. 关系图：R是集结上的二元关系，若R，由结点ai画有向弧到bj组成的图形空关系是独一、是任何关系的子集的关系；全关系；恒等关系，恒等关系的矩阵MI是单元矩阵关系的集结运算有并、交、补、差和对称差复合关系；复合关系矩阵：(按布尔运算)； 有连系律：(RS)TR(ST)，一般不成沟通逆关系；逆关系矩阵知足：；复合关系与逆关系存在：(RS)1=S1R13理解关系的性质(自反性和反自反性、对称性和拒绝称性、传递性的界说以及矩阵示意或关系图示意)，把握其判别体例(操作界说、矩阵或图，充实前提)，知道关系闭包的界说和求法注：(1)关系性质的充实需要前提： R是自反的IAR；R是反自反的IAR；R是对称的 RR1；R是拒绝称的RR1IA；R是传递的RRR. (2)IA具有自反性，对称性、拒绝称性和传递性EA具有自反性，对称性和传递性故IA，EA是等价关系具有反自反性、对称性、拒绝称性和传递性IA也是偏序关系4理解等价关系和偏序关系概念，把握等价类的求法和作偏序集哈斯图的体例知道极年夜(小)元，最年夜(小)元的概念，会求极年夜(小)元、最年夜(小)元、最小上界和最年夜下界等价关系和偏序关系是具有分歧性质的两个关系. 知道等价关系图的特点和等价类界说，会求等价类一个子集的极年夜(小)元可以有多个，而最年夜(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外由哈斯图便于确定任一子集的最年夜(小)元，极年夜(小)元5理解函数概念：函数(映射)，函数相等，复合函数和反函数理解单射、满射和双射等概念，把握其判别体例设f是集结A到B的二元关系，aA，存在惟一bB，使得f，且Dom(f)=A，f是一个函数(映射)函数是一种非凡的关系集结AB的任何子集都是关系，但不必定是函数函数要求对于界说域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制 二函数相等是指：界说域不异，对应关系不异，而且界说域内的每个元素的对应值都不异 函数有：单射若；满射f(A)=B或使得y=f(x)；双射单射且满射 复合函数 即复合成立的前提是：一般，但.反函数若f：AB是双射，则有反函数f1：BA，重点：关系概念与其性质，等价关系和偏序关系，函数. 第3章 图的根基概念复习要点1理解图的概念：结点、边、有向图，无向图、简洁图、完全图、结点的度数、边的重数和平行边等.理解握手定理图是一个有序对，V是结点集，E是联络结点的边的集结把握无向边与无向图，有向边与有向图，同化图，零图，通俗图、自回路(环)，无向平行边，有向平行边等概念简洁图，不含平行边和环(自回路)的图、 在无向图中，与结点v(V)联系关系的边数为结点度数(v)；在有向图中，以v(V)为终点的边的条数为入度(v)，以v(V)为起点的边的条数为出度(v)，deg(v)=deg+(v) +deg(v)无向完全图Kn以其边数；有向完全图以其边数体会子图、真子图、补图和生成子图的概念生成子图设图G，若EE，则图是的生成子图 知道图的同构概念，更应知道图同构的需要前提，用其判定图分歧构.主要定理：(1) 握手定理 设G=，有；(2) 在有向图D中，；(3) 奇数度结点的个数为偶数个 2体会通路与回路概念：通路(简洁通路、根基通路和简单通路)，回路(简洁回路、根基回路和简单回路)会求通路和回路的长度根基通路(回路)必是简洁通路(回路) 体会无向图的连通性，会求无向图的连通分支体会点割集、边割集、割点、割边等概念体会有向图的强连通强性；会判别其类型设图G，结点与边的交替序列为通路通路中边的数目就是通路的长度起点和终点重合的通路为回路边不一再的通路(回路)是简洁通路(回路)；结点不一再的通路(回路)是根基通路(回路). 无向图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体会邻接矩阵和可达矩阵的概念，把握其机关体例及其应用重点：图的概念，握手定理，通路、回路以及图的矩阵示意 第4章 几种非凡图复习要点1理解欧拉通路(回路)、欧拉图的概念，把握欧拉图的判别体例经由过程连通图G的每条边一次且仅一次的通路(回路)是欧拉通路(回路)存在欧拉回路的图是欧拉图. 欧拉回路要求边不能一再，结点可以一再笔不分开纸，不一再地走完全部的边，走过全部结点，就是所谓的一笔画欧拉图或通路的剖断定理(1) 无向连通图G是欧拉图G不含奇数度结点(即G的全部结点为偶数度)；(2) 非通俗连通图G含有欧拉通路G最多有两个奇数度的结点；(3) 连通有向图D含有有向欧拉回路D中每个结点的入度出度连通有向图D含有有向欧拉通路D中除两个结点外，其余每个结点的入度出度，且此两点知足deg(u)deg(v)12理解汉密尔顿通路(回路)、汉密尔顿图的概念，会做简洁判定经由过程连通图G的每个结点一次，且仅一次的通路(回路)，是汉密尔顿通路(回路)存在汉密尔顿回路的图是汉密尔顿图. 汉密尔顿图的充实前提和需要前提 (1) 在无向简洁图G=中，V3，肆意分歧结点，则G是汉密尔顿图(充实前提)(2) 有向完全图D, 若，则图D是汉密尔顿图. (充实前提)(3) 设无向图G=，肆意V1V，则W(GV1)V1(需要前提)若此前提不知足，即存在V1V，使得P(GV!)V1,则G必定不是汉密尔顿图(非汉密尔顿图的充实前提)3体会平面图概念，平面图、面、鸿沟、面的次数和非平面图把握欧拉公式的应用平面图是指一个图能画在平面上，除结点之外，再没有边与边订交 面、鸿沟和面的次数等概念主要结论：(1)平面图(2)欧拉公式：平面图 面数为r，则(结点数与面数之和边数2)(3)平面图 会用界说剖断一个图是不是平面图 4理解平面图与对偶图的关系、对偶图在图着色中的浸染，把握求对偶图的体例给定平面图GV，E，它有面F1，F2，Fn，若有图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体会树、树叶、分支点、通俗树、生成树和最小生成树等概念，把握求最小生成树的体例连通无回路的无向图是树树的判别可以用图T是树的充要前提(等价界说)留意：(1) 树T是连通图； (2)树T知足mn1（即边数=极点数-1）图G的生成子图是树，该树就是生成树每边指定一正数，称为权，每边带权的图称为带权图G的生成树T的全部边的权之和是生成树T的权，记作W(T)最小生成树是带权最小的生成树2体会有向树、根树、有序树、二叉树、二叉完全树、正则二叉树和最优二叉树等概念体会带权二叉树、最优二叉树的概念，把握用哈夫曼算法求最优二叉树的体例有向图删去边的标的目的为树，该图为有向树 对非通俗有向树，恰有一个结点的入度为0(该结点为树根)，其余结点的入度为1，该树为根树 每个结点的出度小于或等于2的根树为二叉树；每个结点的出度等于0或2的根树为二叉完全树；每个结点的出度等于2的根树称为正则二叉树有关树的求法：(1)生成树的破圈法和避圈法求法；(2)最小生成树的克鲁斯克尔求法；(3) 最优二叉树的哈夫曼求法重点：树与根树的根基概念，最小生成树与最优二叉树的求法.第6章 命题规律复习要点1理解命题概念，会判别语句是不是命题理解五个联络词：否认P、析取、合取、前提、和双前提及其真值表，会将简洁命题符号化具有确定真假意义的陈述句称为命题命题必需具备：其一，语句是陈述句；其二，语句有独一确定的真假意义.2体会公式的概念(公式、赋值、成真指派和成假指派)和公式真值表的机关体例能谙练地作公式真值表理解永真式和永假式概念，把握其判别体例剖断数题公式类型的体例：其一是真值表法，其二是等价演算法.3体会公式等价概念，把握公式的主要等价式和判定两个公式是否等价的有用体例：等价演算法、列真值表法和主范式体例4理解析取范式和合取范式、极年夜项和微小项、主析取范式和主合取范式的概念，谙练把握它们的求法命题公式的范式不惟一，但主范式是惟一的 命题公式A有n个命题变元，A的主析取范式有k个微小项，有m个极年夜项，则于是有(1) A是永真式k=2n(m=0)； (2) A是永假式m2n(k=0)；求命题公式A的析取(合取)范式的轨范：赐教材第174页求命题公式A的主析取(合取)范式的轨范：赐教材第177和178页5体会C是前提集结A1,A2,Am的有用结论或由A1, A2, , Am 规律地推出C的概念要理解并把握推理理论的轨则、重言蕴含式和等价式，把握命题公式的证明体例：真值表法、直接证法、间接证法重点：命题与联络词，公式与诠释，真值表，公式的类型及剖断，主析取(合取)范式，命题演算的推理理论.第7章 谓词规律复习要点1理解谓词、量词、个体词、个体域，会将简洁命题符号化原子命题分成个体词和谓词，个体词可所以具体事物或抽象的概念，分个体常项和个体变项谓词用来刻划个体词的性质或之间的关系量词分全称量词，存在量词$.命题符号化留意：使用全称量词，特征谓词后用；使用存在量词$，特征谓词后用2体会原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念把握在有限个体域下消去公式的量词和求公式在给定诠释下真值的体例由原子公式、联络词和量词组成谓词公式谓词公式具有真值时，才是命题在谓词公式xA或$xA中，x是指导变元，A是量词的辖域会区分约束变元和自由变元在非空集结D(个体域)上谓词公式A的一个诠释或赋值有3个前提在任何诠释下，谓词公式A取真值1，A为规律有用式(永真式)；公式A取真值0，A为永假式；至少有一个诠释使公式A取真值1，A称为可知足式在有限个体域下，消弭量词的轨则为：设Da1, a2, , an，则会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名轨则、代入轨则等把握谓词演算的等价式和重言蕴含式并进行谓词公式的等价演算3体会前束范式的概念，会求公式的前束范式的体例.若一个谓词公式F等价地转化成，那么就是F的前束范式，其中Q1，Q2，Qk只能是或$，而x1, x2, , xk是个体变元，B是不含量词的谓词公式前束范式仍旧是谓词公式 4体会谓词规律推理的四个轨则会给出推理证明谓词演算的推理是命题演算推理的推广和扩充，命题演算中根基等价式，重言蕴含式以及P，T，CP轨则在谓词演算中仍旧使用谓词规律的推理演算引入了US轨则(全称量词指定例则)，UG轨则(全称量词推广轨则)，ES轨则(存在量词指定例则)，EG轨则(存在量词推广轨则)等.重点：谓词与量词，公式与诠释，谓词演算精品电年夜复习资料7