电大离散数学期末复习要点与重点考试资料参考答案.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的全部子集组成的集结．若½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）等运算，并会用文氏图示意．
把握集结运算律(赐教材第9～11页)(运算的性质).
3．把握用集结运算根基纪律证明集结恒等式的体例．
集结的运算问题：其一是进行集结运算；其二是运算式的化简；其三是恒等式证明．
证明体例有二：(1)要证明A＝B，只需证明AÍB，又AÊB；
(2)经由过程运算律进行等式推导．
重点：集结概念，集结的运算，集结恒等式的证明．

第2章 关系与函数
复习要点
1．体会有序对和笛卡儿积的概念，把握笛卡儿积的运算．
有序对就是有挨次二元组，如<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．
2．理解关系的概念：二元关系、空关系、全关系、恒等关系.把握关系的集结示意、关系矩阵和关系图，把握关系的集结运算和求复合关系、逆关系的体例．
二元关系是一个有序对换集，，记作xRy．
关系的示意体例有三种：集结示意法，
关系矩阵：RÍA×B，R的矩阵.
关系图：R是集结上的二元关系，若<ai, bj>ÎR，由结点ai画有向弧到bj组成的图形．
空关系Æ是独一、是任何关系的子集的关系；
全关系；
恒等关系，恒等关系的矩阵MI是单元矩阵．
关系的集结运算有并、交、补、差和对称差．
复合关系；
复合关系矩阵：(按布尔运算)；
有连系律：(R·S)·T＝R·(S·T)，一般不成沟通．
逆关系；
逆关系矩阵知足：；
复合关系与逆关系存在：(R·S)－1=S－1·R－1．
3．理解关系的性质(自反性和反自反性、对称性和拒绝称性、传递性的界说以及矩阵示意或关系图示意)，把握其判别体例(操作界说、矩阵或图，充实前提)，知道关系闭包的界说和求法．
注：(1)关系性质的充实需要前提：
① R是自反的ÛIAÍR；
②R是反自反的ÛIAÇR＝Æ；
③R是对称的 ÛR＝R－1；
④R是拒绝称的ÛRÇR－1ÍIA；
⑤R是传递的ÛR·RÍR.
(2)IA具有自反性，对称性、拒绝称性和传递性．EA具有自反性，对称性和传递性．故IA，EA是等价关系．Æ具有反自反性、对称性、拒绝称性和传递性．IA也是偏序关系．
4．理解等价关系和偏序关系概念，把握等价类的求法和作偏序集哈斯图的体例．知道极年夜(小)元，最年夜(小)元的概念，会求极年夜(小)元、最年夜(小)元、最小上界和最年夜下界．
等价关系和偏序关系是具有分歧性质的两个关系.

知道等价关系图的特点和等价类界说，会求等价类．
一个子集的极年夜(小)元可以有多个，而最年夜(小)元若有，则惟一.且极元、最元只在该子集内；而上界与下界可以在子集之外．由哈斯图便于确定任一子集的最年夜(小)元，极年夜(小)元．
5．理解函数概念：函数(映射)，函数相等，复合函数和反函数．理解单射、满射和双射等概念，把握其判别体例．
设f是集结A到B的二元关系，"aÎA，存在惟一bÎB，使得<a, b>Îf，且Dom(f)=A，f是一个函数(映射)．函数是一种非凡的关系．
集结A×B的任何子集都是关系，但不必定是函数．函数要求对于界说域A中每一个元素a，B中有且仅有一个元素与a对应，而关系没有这个限制．
二函数相等是指：界说域不异，对应关系不异，而且界说域内的每个元素的对应值都不异．
函数有：单射——若；
满射——f(A)=B或使得y=f(x)；
双射——单射且满射．
复合函数 即．
复合成立的前提是：．一般，但.
反函数——若f：A®B是双射，则有反函数f－1：B®A，
，
重点：关系概念与其性质，等价关系和偏序关系，函数.

第3章 图的根基概念
复习要点
1．理解图的概念：结点、边、有向图，无向图、简洁图、完全图、结点的度数、边的重数和平行边等.理解握手定理．
图是一个有序对<V，E>，V是结点集，E是联络结点的边的集结．
把握无向边与无向图，有向边与有向图，同化图，零图，通俗图、自回路(环)，无向平行边，有向平行边等概念．
简洁图，不含平行边和环(自回路)的图、
在无向图中，与结点v(ÎV)联系关系的边数为结点度数(v)；在有向图中，以v(ÎV)为终点的边的条数为入度－(v)，以v(ÎV)为起点的边的条数为出度＋(v)，deg(v)=deg+(v) +deg－(v)．
无向完全图Kn以其边数；有向完全图以其边数．
体会子图、真子图、补图和生成子图的概念．
生成子图——设图G＝<V, E>，若E¢ÍE，则图<V, E¢>是<V, E>的生成子图．
知道图的同构概念，更应知道图同构的需要前提，用其判定图分歧构.
主要定理：
(1) 握手定理 设G=<V，E>，有；
(2) 在有向图D＝<V, E>中，；
(3) 奇数度结点的个数为偶数个．
2．体会通路与回路概念：通路(简洁通路、根基通路和简单通路)，回路(简洁回路、根基回路和简单回路)．会求通路和回路的长度．根基通路(回路)必是简洁通路(回路)．
体会无向图的连通性，会求无向图的连通分支．体会点割集、边割集、割点、割边等概念．体会有向图的强连通强性；会判别其类型．
设图G＝<V，E>，结点与边的交替序列为通路．通路中边的数目就是通路的长度．起点和终点重合的通路为回路．边不一再的通路(回路)是简洁通路(回路)；结点不一再的通路(回路)是根基通路(回路).
无向图G中，结点u, v存在通路，u, v是连通的，G中肆意结点u, v连通，G是连通图．P(G)示意图G连通分支的个数．
在无向图中，结点集V¢ÌV，使得P(G－V¢)>P(G)，而肆意V²ÌV¢,有P（G－V²）＝P(G)，V¢为点割集. 若V¢是单元集，该结点v叫割点；边集E¢ÌE，使得P(G－V¢)>P(G)，而肆意E²ÌE¢，有P（G－E²）＝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)＝±1．
2．理解汉密尔顿通路(回路)、汉密尔顿图的概念，会做简洁判定．
经由过程连通图G的每个结点一次，且仅一次的通路(回路)，是汉密尔顿通路(回路)．存在汉密尔顿回路的图是汉密尔顿图.
汉密尔顿图的充实前提和需要前提
(1) 在无向简洁图G=<V，E>中，½V½³3，肆意分歧结点，则G是汉密尔顿图．(充实前提)
(2) 有向完全图D＝<V，E>, 若，则图D是汉密尔顿图. (充实前提)
(3) 设无向图G=<V，E>，肆意V1ÌV，则W(G－V1)£½V1½(需要前提)
若此前提不知足，即存在V1ÌV，使得P(G－V!)>½V1½,则G必定不是汉密尔顿图(非汉密尔顿图的充实前提)．
3．体会平面图概念，平面图、面、鸿沟、面的次数和非平面图．把握欧拉公式的应用．
平面图是指一个图能画在平面上，除结点之外，再没有边与边订交．
面、鸿沟和面的次数等概念．
主要结论：(1)平面图．
(2)欧拉公式：平面图 面数为r，则(结点数与面数之和＝边数＋2)
(3)平面图．
会用界说剖断一个图是不是平面图．
4．理解平面图与对偶图的关系、对偶图在图着色中的浸染，把握求对偶图的体例．
给定平面图G＝〈V，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知足m＝n－1（即边数=极点数-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是永假式Ûm＝2n(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称为可知足式．
在有限个体域下，消弭量词的轨则为：设D＝{a1, a2, …, an}，则

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

精品电年夜复习资料7