当前位置：文档之家 › 离散数学知识点总结

离散数学知识点总结

  • 格式：doc
  • 大小：261.00 KB
  • 文档页数：16

离散数学知识点总结 1 / 16 总结 离散数学知识点 第二章 命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法；

第三章 谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 离散数学知识点总结 2 / 16 3.既有存在又有全称量词时，先消存在量词，再消全称量词；

第四章 集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划及覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次；

第五章 关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数为mn，A到B上可以定义mn2种不同的关系； 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 离散数学知识点总结 3 / 16 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x组成的集合； 后域(ranR)：所有元素y组成的集合； 5.自反闭包：r(R)=RUxI; 对称闭包：s(R)=RU1-R; 传递闭包：t(R)=RU2RU3RU…… 6.等价关系：集合A上的二元关系R满足自反性，对称性和传递性，则R称为等价关系； 7.偏序关系：集合A上的关系R满足自反性，反对称性和传递性，则称R是A上的一个偏序关系； 8.covA={|x,y属于A，y盖住x}； 9.极小元：集合A中没有比它更小的元素(若存在可能不唯一)； 极大元：集合A中没有比它更大的元素(若存在可能不唯一)； 最小元：比集合A中任何其他元素都小(若存在就一定唯一)； 最大元：比集合A中任何其他元素都大(若存在就一定唯一)； 10.前提：B是A的子集 上界：A中的某个元素比B中任意元素都大，称这个元素是B的上界(若存在，可能不唯一)； 下界：A中的某个元素比B中任意元素都小，称这个元素是B的下界(若存在，可能不唯一)； 上确界：最小的上界(若存在就一定唯一)； 下确界：最大的下界(若存在就一定唯一)； 离散数学知识点总结 4 / 16 第六章 函数 1.若|X|=m,|Y|=n,则从X到Y有mn2种不同的关系，有mn种不同的函数； 2.在一个有n个元素的集合上，可以有22n种不同的关系，有nn种不同的函数，有n!种不同的双射； 3.若|X|=m,|Y|=n，且m<=n，则从X到Y有Amn种不同的单射； 4.单射：f:X-Y，对任意1x,2x属于X,且1x≠2x，若f(1x)≠f(2x)； 满射：f:X-Y，对值域中任意一个元素y在前域中都有一个或多个元素对应； 双射：f:X-Y，若f既是单射又是满射，则f是双射； 5.复合函数：fºg=g(f(x)); 6.设函数f:A-B，g:B-C，那么 ①如果f,g都是单射，则fºg也是单射； ②如果f,g都是满射，则fºg也是满射； ③如果f,g都是双射，则fºg也是双射； ④如果fºg是双射，则f是单射，g是满射；

第七章 代数系统 1.二元运算：集合A上的二元运算就是2A到A的映射； 2. 集合A上可定义的二元运算个数就是从A×A到A上的映射的个数，离散数学知识点总结 5 / 16 即从从A×A到A上函数的个数，若|A|=2,则集合A上的二元运算的个数为2*22=42=16种； 3. 判断二元运算的性质方法： ①封闭性：运算表内只有所给元素； ②交换律：主对角线两边元素对称相等； ③幂等律：主对角线上每个元素及所在行列表头元素相同； ④有幺元：元素所对应的行和列的元素依次及运算表的行和列相同； ⑤有零元：元素所对应的行和列的元素都及该元素相同； 4.同态映射：,,满足f(a*b)=f(a)^f(b),则f为由到的同态映射；若f是双射，则称为同构；

第八章 群 1.广群的性质：封闭性； 半群的性质：封闭性，结合律； 含幺半群(独异点)：封闭性，结合律，有幺元； 群的性质：封闭性，结合律，有幺元，有逆元； 2.群没有零元； 3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律； 4.循环群中幺元不能是生成元； 5.任何一个循环群必定是阿贝尔群； 离散数学知识点总结 6 / 16 第十章 格及布尔代数 1.格：偏序集合A中任意两个元素都有上、下确界； 2.格的基本性质： 1) 自反性 a≤a 对偶: a≥a 2) 反对称性 a≤b ^ b≥a => a=b 对偶:a≥b ^ b≤a => a=b 3) 传递性 a≤b ^ b≤c => a≤c 对偶:a≥b ^ b≥c => a≥c 4) 最大下界描述之一 a^b≤a 对偶 avb≥a A^b≤b 对偶 avb≥b 5）最大下界描述之二 c≤a,c≤b => c≤a^b 对偶c≥a,c≥b =>c≥avb 6) 结合律 a^(b^c)=(a^b)^c 对偶 av(bvc)=(avb)vc 7) 等幂律 离散数学知识点总结 7 / 16 a^a=a 对偶 ava=a 8) 吸收律 a^(avb)=a 对偶 av(a^b)=a 9) a≤b <=> a^b=a avb=b 10) a≤c,b≤d => a^b≤c^d avb≤cvd 11) 保序性 b≤c => a^b≤a^c avb≤avc 12） 分配不等式 av(b^c)≤(avb)^(avc) 对偶 a^(bvc)≥(a^b)v(a^c) 13）模不等式 a≤c <=> av(b^c)≤(avb)^c 3.分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)； 4.分配格的充要条件：该格没有任何子格及钻石格或五环格同构； 5.链格一定是分配格，分配格必定是模格； 6.全上界：集合A中的某个元素a大于等于该集合中的任何元素，则称a为格的全上界，记为1；(若存在则唯一) 全下界：集合A中的某个元素b小于等于该集合中的任何元素，则称b为格的全下界，记为0；(若存在则唯一) 7.有界格：有全上界和全下界的格称为有界格，即有0和1的格； 8.补元：在有界格内，如果a^b=0,avb=1，则a和b互为补元； 9.有补格：在有界格内，每个元素都至少有一个补元； 离散数学知识点总结 8 / 16 10.有补分配格(布尔格)：既是有补格，又是分配格； 11.布尔代数：一个有补分配格称为布尔代数；

第十一章 图论 1.邻接：两点之间有边连接，则点及点邻接； 2.关联：两点之间有边连接，则这两点及边关联； 3.平凡图：只有一个孤立点构成的图； 4.简单图：不含平行边和环的图； 5.无向完全图：n个节点任意两个节点之间都有边相连的简单无向图； 有向完全图:n个节点任意两个节点之间都有边相连的简单有向图； 6.无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边； 7.r-正则图：每个节点度数均为r的图； 8.握手定理：节点度数的总和等于边的两倍； 9.任何图中，度数为奇数的节点个数必定是偶数个； 10.任何有向图中，所有节点入度之和等于所有节点的出度之和； 11.每个节点的度数至少为2的图必定包含一条回路； 12.可达：对于图中的两个节点iv,jv，若存在连接iv到jv的路，则称iv

及jv相互可达，也称iv及jv是连通的；在有向图中，若存在iv到jv的路，则称iv到jv可达； 13.强连通：有向图章任意两节点相互可达；

合集下载

离散知识点大一

离散知识点大一

离散知识点大一离散数学是计算机科学与信息技术等学科中的一门重要基础课程，对于大一学生而言，熟练掌握离散数学的知识点是非常重要的。

下面将为大家介绍一些大一学习离散数学时需要掌握的知识点。

1. 集合论集合是离散数学中的基本概念，大一学习离散数学时首先需要了解集合的定义、基本运算及其性质。

此外，大一学习离散数学还需要学习并集、交集、差集、补集等集合运算的性质和运算规则。

2. 逻辑逻辑是离散数学的核心内容之一，大一学习离散数学时需要学习命题逻辑和谓词逻辑的基本概念、符号表示以及推理方法。

掌握逻辑运算规则、逻辑等价与蕴含关系的相关知识是进行离散数学证明的基础。

3. 函数与关系函数和关系是离散数学中的重要内容，大一学习离散数学时需要学习函数和关系的定义、性质，了解函数的一一对应关系、映射关系等概念。

此外，掌握集合间的关系、等价关系和偏序关系等概念也是大一学习离散数学的重点。

4. 图论图论是离散数学中的一个分支，大一学习离散数学时需要学习图的基本概念和性质，掌握图的表示方法以及常见的图算法。

了解最小生成树、最短路径、图的着色等图论算法和应用是大一学习离散数学的内容之一。

5. 组合数学组合数学是离散数学中的另一个重要分支，大一学习离散数学时需要学习排列组合、二项式系数、递归关系、生成函数等组合数学的基本概念和方法。

了解组合数学在密码学、编码理论等领域的应用也是大一学习离散数学的内容之一。

6. 预备知识在学习离散数学之前，大一学生需要具备一定的数学基础知识，如集合论、逻辑、数理逻辑等。

此外，对于离散数学中常用的数学符号、标记和记法也需要有一定的了解，以便顺利学习和理解离散数学的相关内容。

通过掌握以上离散数学的知识点，大一学生可以打下坚实的离散数学基础，为将来的学习和科研奠定良好的基础。

离散数学的学习不仅仅是为了应付考试，更重要的是培养大一学生的逻辑思维能力和分析问题的能力，这对于其它学科的学习和日后的科研工作都具有重要意义。

离散图论知识点总结

离散图论知识点总结

离散图论知识点总结一、基本概念图（Graph）是离散数学中的一个重要概念，它由顶点集合V和边集合E组成。

一般用G （V，E）来表示，其中V={v1,v2,…,vn}是有限非空集合，E是V中元素的无序对的集合。

图分为有向图和无向图。

无向图中的边是无序的，有向图中的边是有序的。

图中存在一些特殊的图，比如完全图、树、路径、回路等。

二、图的表示方法1. 邻接矩阵邻接矩阵是一种常见的图的表示方法，它使用一个二维数组来表示图的关系。

对于一个n 个顶点的图，邻接矩阵是一个n*n的矩阵A，其中A[i][j]表示顶点i到顶点j之间是否存在边。

对于无向图，A[i][j]=1表示顶点i与顶点j之间存在边，A[i][j]=0表示不存在。

对于有向图，A[i][j]=1表示i指向j的边存在，A[i][j]=0表示不存在。

2. 邻接表邻接表是另一种常见的图的表示方法。

它将图的信息储存在一个数组中，数组的每个元素与图的一个顶点相对应。

对于每个顶点vi，数组中储存与该顶点邻接的顶点的信息。

邻接表可以用链表或者数组来表示，链表表示的邻接表比较灵活，但是在查找某个边的相邻顶点时需要遍历整个链表。

三、图的性质1. 度图中每个顶点的度是与其相邻的边的数目。

对于无向图，顶点的度等于与其相邻的边的数目；对于有向图，则分为入度和出度。

2. 连通性对于无向图G，若图中任意两个顶点都有路径相连，则称图G是连通的。

对于有向图G，若从任意一个顶点vi到任意一个顶点vj都存在路径，则称G是强连通的。

3. 路径和回路路径是指图中一系列的边，连接图中的两个顶点；回路是指起点与终点相同的路径。

路径的长度是指路径中边的数目。

4. 树和森林一个无向图，如果是连通图且不存在回路，则称为树。

一个无向图，若它不是连通图，则称为森林。

四、图的常见算法1. 深度优先搜索（DFS）深度优先搜索是一种用于图的遍历的算法，它从图的某个顶点vi出发，访问它的所有邻接顶点，再对其中未访问的顶点继续深度优先搜索。

离散数学图论(图、树)常考考点知识点总结

离散数学图论(图、树)常考考点知识点总结

离散数学图论（图、树）常考考点知识点总结图的定义和表示1.图：一个图是一个序偶＜V , E ＞，记为G =< V ，E >，其中：① V ={V1,V2,V3,…, Vn}是有限非空集合，Vi 称为结点，V 称为节点集② E 是有限集合，称为边集，E中的每个元素都有V中的结点对与之对应，称之为边③与边对应的结点对既可以是无序的，也可以是有序的表示方法集合表示法，邻接矩阵法2.邻接矩阵：零图的邻接矩阵全零图中不与任何结点相邻接的结点称为孤立结点，两个端点相同的边称为环或者自回路3.零图：仅有孤立节点组成的图4.平凡图：仅含一个节点的零图无向图和有向图5.无向图：每条边都是无向边的图有向图：每条边都是有向边的图6.多重图：含有平行边的图(无向图中，两结点之间包括结点自身之间的几条边；有向图中同方向的边)7.线图：非多重图8.重数：平行边的条数9..简单图：无环的线图10.子图，真子图，导出子图，生成子图，补图子图：边和结点都是原图的子集，则称该图为原图的子图真子图（该图为原图的子图，但是不跟原图相等）11.生成子图：顶点集跟原图相等，边集是原图的子集12.导出子图：顶点集是原图的子集，边集是由顶点集在原图中构成的所有边构成的图完全图（任何两个节点之间都有边）13.完全图：完全图的邻接矩阵主对角线的元素全为0，其余元素都是114.补图：完全图简单图15.自补图：G与G的补图同构，则称自补图16.正则图：无向图G=<V,E>,如果每个顶点的度数都是k，则图G称作k-正则图17.结点的度数利用邻接矩阵求度数：18.握手定理：图中结点度数的总和等于边数的两倍推论：度数为奇数的结点个数为偶数有向图中，所有结点的入度=出度=边数19.图的度数序列：出度序列+入度序列20.图的同构：通俗来说就是两个图的顶点和边之间有双射关系，并且每条边对应的重数相同（也就是可任意挪动结点的位置，其他皆不变）21.图的连通性及判定条件可达性：对节点vi 和vj 之间存在通路，则称vi 和vj 之间是可达的22.无向图的连通性：图中每两个顶点之间都是互相可达的23..强连通图：有向图G 的任意两个顶点之间是相互可达的判定条件：G 中存在一条经过所有节点至少一次的回路24.单向连通图：有向图G 中任意两个顶点之间至少有一个节点到另一个节点之间是可达的判定条件：有向图G 中存在一条路经过所有节点25.弱连通图：有向图除去方向后的无向图是连通的判定条件：有向图邻接矩阵与转置矩阵的并是全一的矩阵26.点割：设无向图G=<V,E>为联通图，对任意的顶点w  V,若删除w及与w相关联的所有边后，无向图不再联通，则w称为割点；27.点割集：设无向图G=<V,E>为连通图，若存在点集 ，当删除 中所有顶点及与V1顶点相关联的所有边后，图G不再是联通的；而删除了V1的任何真子集 及与V2中顶点先关的所有边后，所得的子图仍是连通图，则称V1是G的一个点割集设无向图G=<V,E>为连通图，任意边e  E,若删除e后无向图不再联通，则称e 为割边，也成为桥28.边割集：欧拉图，哈密顿图，偶图（二分图），平面图29.欧拉通路（回路）：图G 是连通图，并且存在一条经过所有边一次且仅一次的通路（回路）称为拉通路（回路）30.欧拉图：存在欧拉通路和回路的图31.半欧拉图：有通路但没有欧拉回路32.欧拉通路判定：图G 是连通的，并且有且仅有零个或者两个奇度数的节点欧拉回路判定：图G 是连通的，并且所有节点的度数均为偶数有向欧拉图判定：图G 是连通的，并且所有节点的出度等于入度33.哈顿密图：图G 中存在一条回路，经过所有点一次且仅一次34..偶图：图G 中的顶点集被分成两部分子集V1,V2，其中V1nV2= o ,V1UV2= V ，并且图G 中任意一条边的两个端点都是一个在V1中，一个在V2中35.平面图：如果把无向图G 中的点和边画在平面上，不存在任何两条边有不在端点处的交叉点，则称图G 是平面图，否则是非平面图36.图的分类树无向树和有向树无向树：连通而不含回路的无向图称为无向树生成树：图G 的某个生成子图是树有向树：一个有向图，略去所有有向边的方向所得到的无向图是一棵树最小生成树最小生成树：设G -< V . E 是连通赋权图，T 是G 的一个生成树，T 的每个树枝所赋权值之和称为T 的权，记为W ( T . G 中具有最小权的生成树称为G 的最小生成树最优树（哈夫曼树）设有一棵二元树，若对所有的树叶赋以权值w1,w2… wn ，则称之为赋权二元树，若权为wi 的叶的层数为L ( wi )，则称W ( T )= EWixL ( wi ）为该赋权二元树的权，W ）最小的二元树称为最优树。

离散数学知识点总结

离散数学知识点总结

离散数学知识点总结 一、各章复习要求与重点第一章 集 合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。

2、掌握集合的表示法和集合的交、并、差、补等基本运算。

3、掌握集合运算基本规律，证明集合等式的方法。

4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。

[本章重点习题]P5~6，4、6； P14~15，3、6、7； P20，5、7。

[疑难解析] 1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。

2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。

实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~⋂=-证明中的特殊作用。

[例题分析]例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。

解}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A}}2,1{},2{},1{,{)(φρ=B于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ例2 设{}{}Φ=,,,,b a b a A ，试求：(1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。

解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~⋂⋃⋂=⋃⋂⋃ 证明()()()()()()()()()()()()()()()()()()B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~⋂⋃⋂=Φ⋃⋂⋃⋂⋃Φ=⋂⋃⋂⋃⋂⋃⋂=⋂⋃⋃⋂⋃=⋃⋂⋃第二章 二元关系[复习知识点]1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。