《离散数学期末复习要点与重点2.docx》由会员分享，可在线阅读，更多相关《离散数学期末复习要点与重点2.docx（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习好资料欢迎下载离散数学期末复习要点与重点离散数学运算机科学与技术专业的一门统设必修学位课程，共 72 学时，开设一学期 该课程的主要内容包括：集合论、图论、代数结构第 6 章集合及其运算复习要点1懂得集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，娴熟把握集合的表示方法具有确定的，可以区分的如干事物的全体称为集合 ，其中的事物叫元素. 集合的表示方法：列举法和描述法.留意：集合的表示中元素不能重复显现，集合中的元素无次序之分把握集合包含子集 、真子集、集合相等等概念留意：元素与集合，集
2、合与子集，子集与幂集，与, 空集与全部集合等的关系.空集，是惟一的，它是任何集合的子集可编辑资料 - - - 欢迎下载精品名师归纳总结集合 A 的幂集 PA x xA ， A 的全部子集构成的集合如A n，就P A=2 n可编辑资料 - - - 欢迎下载精品名师归纳总结2娴熟把握集合A 和 B 的并 AB，交 AB，补集AA 补集总相对于一个全集.差集 A B，对称差， AB A BB A，或 AB AB（ AB）等运算，并会用文氏 图表示把握集合运算律 见教材 运算的性质 . 3把握用集合运算基本规律证明集合恒等式的方法集合的运算问题：其一是进行集合运算。其二是运算式的化简。其三是恒等式证明
3、证明方法有二：1要证明 A B，只需证明AB，又 AB。2 通过运算律进行等式推导重点 ：集合概念，集合的运算，集合恒等式的证明可编辑资料 - - - 欢迎下载精品名师归纳总结复习要点第 7、8 章关系与函数可编辑资料 - - - 欢迎下载精品名师归纳总结1明白有序对和笛卡儿积的概念，把握笛卡儿积的运算有序对就是有次序二元组，如， x, y 的位置是确定的，不能随便放置留意：有序对，以 a, b 为元素的集合 a, b= b, a 。有序对 a, a有意义，而集合 a, a 是单元素集合，应记作 a 集合 A，B 的笛卡儿积A B 是一个集合，规定A BxA,yB ， 是有序对的集合 . 笛卡
4、儿积也可以多个集合合成，A1 A2An2懂得关系的概念：二元关系、空关系、全关系、恒等关系.把握关系的集合表示、关系矩阵和关系图，把握关系的集合运算和求复合关系、逆关系的方法可编辑资料 - - - 欢迎下载精品名师归纳总结二元关系是一个有序对集合，Rx, yxAyB ，记作 xRy可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结关系的表示方法有三种：集合表示法，1ai Rbji1,2., m,可编辑资料 - - - 欢迎下载精品名师归纳总结关系矩阵： RAB，R 的矩阵 M Rrij mn , rij0ai Rb jj.1,2,., n可编辑资料
5、 - - - 欢迎下载精品名师归纳总结关系图： R 是集合上的二元关系，如R，由结点ai 画有向弧到bj 构成的图形空关系是唯独、是任何关系的子集的关系。可编辑资料 - - - 欢迎下载精品名师归纳总结全关系 E Aa, ba, bAAA 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 1 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习好资料欢迎下载可
6、编辑资料 - - - 欢迎下载精品名师归纳总结恒等关系 I Aa, aaA ，恒等关系的矩阵M I 是单位矩阵可编辑资料 - - - 欢迎下载精品名师归纳总结关系的集合运算有并、交、补、差和对称差可编辑资料 - - - 欢迎下载精品名师归纳总结复合关系 RR1R2a, cba, bR1b,cR2 。可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结复合关系矩阵：M RM R1M R2按布尔运算 。可编辑资料 - - - 欢迎下载精品名师归纳总结有结合律： R S TR S T，一般不行交换可编辑资料 - - - 欢迎下载精品名师归纳总结逆关系 R
7、1y, xx, yR 。可编辑资料 - - - 欢迎下载精品名师归纳总结逆关系矩阵满意：M R 1R可编辑资料 - - - 欢迎下载精品名师归纳总结M1。T 1 1复合关系与逆关系存在：R S=SR3懂得关系的性质自反性和反自反性、对称性和反对称性、传递性的定义以及矩阵表示或关系图表示，把握其判别方法利用定义、 矩阵或图， 充分条件 ，知道关系闭包的定义和求法注： 1关系性质的充分必要条件： R 是自反的I AR。 R 是反自反的IAR。1 R 是对称的RR。A R 是反对称的RR 1I 。 R 是传递的R RR.2 IA 具有自反性，对称性、反对称性和传递性EA 具有自反性，对称性和传递性故
8、I A， EA 是等价关系具有反自反性、对称性、反对称性和传递性I A 也是偏序关系4懂得等价关系和偏序关系概念，把握等价类的求法和作偏序集哈斯图的方法知道 极大 小元，最大 小元的概念，会求极大小元、最大 小元、最小上界和最大下界等价关系和偏序关系是具有不同性质的两个关系.可编辑资料 - - - 欢迎下载精品名师归纳总结自反性对称性反对称性传递性等价关系偏序关系可编辑资料 - - - 欢迎下载精品名师归纳总结知道等价关系图的特点和等价类定义，会求等价类一个子集的极大 小 元可以有多个，而最大 小 元如有，就惟一. 且极元、最元只在该子集内。而上界与下界可以在子集之外由哈斯图便于确定任一子集的
9、最大 小 元，极大 小元5懂得函数概念：函数映射 ，函数相等，复合函数和反函数懂得单射、满射和双射等概念，把握其判别方法设 f 是集合 A 到 B 的二元关系，aA，存在惟一bB，使得 f，且 Dom f= A，f 是一个函数 映射 函数是一种特别的关系集合 AB 的任何子集都是关系，但不肯定是函数函数要求对于定义域A 中每一个元素 a， B 中有且仅有一个元素与a 对应，而关系没有这个限制二函数相等是指：定义域相同， 对应关系相同， 而且定义域内的每个元素的对应值都相可编辑资料 - - - 欢迎下载精品名师归纳总结同函数有：单射如a1a2f a1 f a2 。可编辑资料 - - - 欢迎下载
10、精品名师归纳总结满射 fA=B 或yB,xA, 使 得 y=fx。可编辑资料 - - - 欢迎下载精品名师归纳总结双射单射且满射可编辑资料 - - - 欢迎下载精品名师归纳总结复合函数f : AB, g : BC, 就gf : AC ,即 gf xg f x 可编辑资料 - - - 欢迎下载精品名师归纳总结复合成立的条件 是：Ran f Dom g一般gffg，但可编辑资料 - - - 欢迎下载精品名师归纳总结h gf hg f .可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 2 页，共 6 页 - - - - - - - - -
11、 -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习好资料欢迎下载 1反函数如f： AB 是双射，就有反函数f： BA，可编辑资料 - - - 欢迎下载精品名师归纳总结f1b, abB,f ab, aA ， gf 1f1g 1 , f1 1f可编辑资料 - - - 欢迎下载精品名师归纳总结重点 ：关系概念与其性质，等价关系和偏序关系，函数.第 9、10 、11 章 代数结构本章重点 ：代数运算及性质，群的概念，置换和置换群、交换群和循环群.一、重点内容1.代数运算及其性质2二元运算，非空集合A 上的函数 映射 f：A
12、A 就是 A 上的 二元代数运算，就是说二元运算是一个变换对应关系 .代数运算的性质：交换律x,yA，有 xy=yx，在 A 上适合交换律 .结合律x,yA，有 xyz x yz，运算在 A 上适合结合律 .安排律x,y,zA，有 x yz= x yx z 或yz x= y xz x，对适合安排律.幂等律xA，有 xx=x，就运算在 A 上适合 幂等律 .吸取律x,yA, 有 x xy=x, xx y=x，和满意 吸取律 .单位元el, 或 erA，对xA, 有 elx=x xer=x, el或 er是 A 的运算的左单位元xx或右单位元 . e 既是右单位元又是左单位元就是单位元 .可编辑资
13、料 - - - 欢迎下载精品名师归纳总结逆元对 xA，如 x1A, 有 1x=xx1=e， 1 是 x 的逆元 .可编辑资料 - - - 欢迎下载精品名师归纳总结代数系统在非空集合A 上，定义了如干代数运算f 1,f2,fm, A, f1,f2,fm称为代数系统 . 如 BA， f1,f 2,fm 在 B 上成立， B, f 1,f2,fm称为子代数系统.2.群可编辑资料 - - - 欢迎下载精品名师归纳总结代数系统（ G,*）* 具有结合律半群* 存在逆元、单位元群HG H ,* 子群可编辑资料 - - - 欢迎下载精品名师归纳总结留意：由上可见，代数系统、半群、群子群 是一条线下来，条件逐
14、步加强，半群和群是我们争论的重点.可编辑资料 - - - 欢迎下载精品名师归纳总结1 1 1 1 1mnm+nm nmn可编辑资料 - - - 欢迎下载精品名师归纳总结群的性质： 1 a=a; 2 a* b=b* a;3 a* a =a;4 a =a; 5 方程的可可编辑资料 - - - 欢迎下载精品名师归纳总结解性 方程 a*x=b 或 y* a=b 有唯独解。6 消去律 由 a*c=b* c 或 c *a=c* b，可得 a=b3. 特别群交换群， 群 G,* 的二元运算 *满意交换律，G,* 是交换群 阿贝尔群 .循环群，群G 能表成G = ak kZ， aG G 是 循环群 . 记作
15、G， a 是群 G 的生成元 .对称群设 S=1 ，2，,N ， S上的全部n 元置换构成的集合Sn, 对于置换乘法，构成一个群，称为n 元对称群 .置换群 ，n 元集合 S 上的全部n 元置换构成的集合Sn，关于置换乘法构成n 元对换群，它的子群叫置换群.4. 置换，置换， 有限集合S a1,a2,an 上的双射：SS，n 元置换可编辑资料 - - - 欢迎下载精品名师归纳总结a1 a1 a2a1 an a1 可编辑资料 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 3 页，共 6 页 - -
16、 - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习好资料欢迎下载可编辑资料 - - - 欢迎下载精品名师归纳总结置换复合 乘法 ，设a1 a1 a2a2 a1anan ,a2a1 a1 a2a2 anana n 可编辑资料 - - - 欢迎下载精品名师归纳总结*那么a1Ia1单位置换 ，xa2ana2an a1 a2 an 可编辑资料 - - - 欢迎下载精品名师归纳总结 1逆置换 ，=a1 a1a2 a2 an an可编辑资料 - - - 欢迎下载精品名师归纳总结n 元集合 S 上的
17、n 元置换有 n.个，有 n 元置换构成的集合，记作Sn.轮换 ，满意： 1 a1 ）=a2,a2）=a3 ,am）=a1。 2a= a，当 a ak,k=1,2,时. 就是一个长度为m 的 轮换 ，记作 a1,a2,am.重要结论 ：置换有结合律。 不相交的轮换有交换律。Sn 中任一置换都可以唯独的表示m,可编辑资料 - - - 欢迎下载精品名师归纳总结成一系列不相交的轮换之积. 而任何轮换又可以进一步表示成对换之积，所以任何 n 元置换都可以表示成对换之积。5. 同态与同构同态 ，代数系统 G,* 和S, ，f 是从 G 到 S 上的一个映射 .a,bG，有 fa* b= fafb就称 f
18、 是由 G,* 到S, 的一个 同态映射 . 并称 G 与 S 同态 . 假如 f 是满射，就称 G 与 S 是 满同态， 记作 G S。假如 f 是单射，就称G 与 S 是单同态 .fG,称为 G,* 在 f 下的 同态象 .同构 ，代数系统 G,* 到S,，假如 f 是从 G 到 S 的一个双射，就称f 是从 G 到 S 的可编辑资料 - - - 欢迎下载精品名师归纳总结同构 ，群同构 ，设群 G,* 和 S,，存在从 G,* 到 S,的同态双射， 就称群 G,* 与S,同构 .可编辑资料 - - - 欢迎下载精品名师归纳总结6.环与域定义 10.4 设 是环，(1) 如环中乘法适合交换律
19、，就称R 是交换环。(2) 如环中乘法存在单位元，就称R 是含幺环。3如a,b R， ab 0a 0b 0，就称 R 是无零因子环。4如 R 既是交换环、含幺环，也是无零因子环，就称 R 是整环。a定义 12.5 设 R 是整环，且 R 中至少含有两个元素. 如a R* ，其中 R* =R 0 ，都有就称 R 是域 .能判别给定代数系统是环。能判定给定的环是交换环、含幺环、无零因子环与整环。能判定给定的代数系统是域。第 11 章 格与布尔代数偏序集构成格的条件：任意二元子集都有最大下界和最小上界。格作为代数系统的定义。假如格中一个运算对另一个运算是可安排的，称这个格是安排格。 1R，可编辑资料
20、 - - - 欢迎下载精品名师归纳总结可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 4 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资料word 精心总结归纳 - - - - - - - - - - - -学习好资料欢迎下载安排格的两种判别法：不存在与钻石格或五角格同构的子格。对于任意元素a,b,c,有 ab a c 且 a b a cb c。有界格的定义及其实例。格中元素的补元及其性质（安排格中补元的唯独性）。有补格的定义。布尔格或布尔代数的定义：假如一个格是有补安排格，
21、就称它为布尔格或布尔代数。可编辑资料 - - - 欢迎下载精品名师归纳总结复习要点第 14 章图的基本概念可编辑资料 - - - 欢迎下载精品名师归纳总结1懂得图的概念：结点、边、有向图，无向图、简洁图、完全图、结点的度数、边的重数和平行边等.懂得握手定理图是一个有序对，V 是结点集， E 是联结结点的边的集合把握无向边与无向图，有向边与有向图，混合图，零图，平凡图、自回路环，无向平行边，有向平行边等概念简洁图，不含平行边和环自回路 的图、在无向图中，与结点v V关联的边数为结点度数 deg v。在有向图中，以vV为终点的边的条数为入度degv，以vV 为起点的边的条数为出度degv， deg
22、v=deg+ v+deg v可编辑资料 - - - 欢迎下载精品名师归纳总结无向完全图Kn 以其边数E1 nn21 。有向完全图以其边数Enn1 可编辑资料 - - - 欢迎下载精品名师归纳总结明白子图、真子图、补图和生成子图的概念生成子图设图G ，如 EE，就图 是 的生成子图知道图的同构概念，更应知道图同构的必要条件，用其判定图不同构.重要定理 ：可编辑资料 - - - 欢迎下载精品名师归纳总结(1) 握手定理设 G=，有vdegvV2 E 。可编辑资料 - - - 欢迎下载精品名师归纳总结(2) 在有向图D 中，degv V vdegv Vv 。可编辑资料 - - - 欢迎下载精品名师归
23、纳总结(3) 奇数度结点的个数为偶数个2明白通路与回路概念：通路 简洁通路、基本通路和复杂通路，回路 简洁回路、基本回路和复杂回路会求通路和回路的长度基本通路回路 必是简洁通路回路 明白无向图的连通性，会求无向图的连通分支明白点割集、边割集、割点、割边等概念明白有向图的强连通强性。会判别其类型设图 G ，结点与边的交替序列为通路 通路中边的数目就是通路的长度 起点和终点重合的通路为回路边不重复的通路 回路 是简洁通路 回路 。结点不重复的通路 回路 是基本通路 回路 .无向图 G 中，结点 u, v 存在通路， u, v 是连通的， G 中任意结点u, v 连通，G 是连通图PG表示图 G 连
24、通分支的个数在无向图中， 结点集 VV，使得 PG V PG，而任意 VV ,有 P（ G V ）PG ，V 为点割集 . 如 V 是单元集，该结点v 叫割点。边集EE，使得PG V PG ，而任意 EE ，有 P（GE ） PG， E 为边割集如E 是单元集，该边e 叫割边 桥必是必是要知道：强连通单侧连通弱连通，反之不成立3明白邻接矩阵和可达矩阵的概念，把握其构造方法及其应用可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 5 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载精品名师归纳总结资
25、料word 精心总结归纳 - - - - - - - - - - - -学习好资料欢迎下载重点 ：图的概念，握手定理，通路、回路以及图的矩阵表示可编辑资料 - - - 欢迎下载精品名师归纳总结复习要点第 14 章几种特别图可编辑资料 - - - 欢迎下载精品名师归纳总结1懂得欧拉通路 回路 、欧拉图的概念，把握欧拉图的判别方法通过连通图G 的每条边一次且仅一次的通路回路 是欧拉通路 回路 存在欧拉回路的图是欧拉图 .欧拉回路要求边不能重复，结点可以重复笔不离开纸，不重复的走完全部的边，走过全部结点，就是所谓的一笔画欧拉图或通路的判定定理(1) 无向连通图G 是欧拉图G 不含奇数度结点即 G 的
26、全部结点为偶数度。(2) 非平凡连通图G 含有欧拉通路G 最多有两个奇数度的结点。(3) 连通有向图D 含有有向欧拉回路D 中每个结点的入度出度连通有向图D 含有有向欧拉通路D 中除两个结点外，其余每个结点的入度出度，且此两点满意deg u deg v 12懂得汉密尔顿通路回路 、汉密尔顿图的概念，会做简洁判定通过连通图G 的每个结点一次，且仅一次的通路回路 ，是汉密尔顿通路回路 存在汉密尔顿回路的图是汉密尔顿图.汉密尔顿图的充分条件和必要条件可编辑资料 - - - 欢迎下载精品名师归纳总结(1) 在无向简洁图G =中，V3，任意不同结点G 是汉密尔顿图充分条件 u, vG,degudegvV ，就可编辑资料 - - - 欢迎下载精品名师归纳总结(2) 有向完全图D , 如 V3 ，就图 D 是汉密尔顿图 . 充分条件 (3) 设无向图 G=，任意 V1V，就 WG V1V1 必要条件 如此条件不满意，即存在V1V，使得PG V.V1,就 G 肯定不是汉密尔顿图非汉密尔顿图的充分条件3把握图论中常用的证明方法重点 ：欧拉图和哈密顿图、平面图的基本概念及判别可编辑资料 - - - 欢迎下载精品名师归纳总结学习资料 名师精选 - - - - - - - - - -第 6 页，共 6 页 - - - - - - - - - -可编辑资料 - - - 欢迎下载