总结离散数学知识点第二章命题逻辑1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假；2.主析取范式：极小项 (m) 之和；主合取范式：极大项(M)之积；3.求极小项时，命题变元的肯定为1，否定为 0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；5.求范式时，为保证编码不错，命题变元最好按P,Q,R 的顺序依次写；6.真值表中值为 1 的项为极小项，值为0 的项为极大项；7.n 个变元共有2n个极小项或极大项，这2n为(0~ 2n -1)刚好为化简完后的主析取加主合取；8.永真式没有主合取范式，永假式没有主析取范式；9.推证蕴含式的方法 (=>) ：真值表法；分析法 (假定前键为真推出后键为真，假定前键为假推出后键也为假)10.命题逻辑的推理演算方法：P 规则， T 规则①真值表法；②直接证法；③归谬法；④附加前提法；第三章谓词逻辑1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质；多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系；2.全称量词用蕴含→，存在量词用合取 ^;3.既有存在又有全称量，先消存在量，再消全称量；第四章集合1.N ，表示自然数集， 1,2,3 ⋯⋯，不包括 0；2.基：集合 A 中不同元素的个数， |A|；3.集：定集合 A，以集合 A 的所有子集元素成的集合，P(A) ；4.若集合 A 有 n 个元素，集 P(A) 有2n个元素， |P(A)|= 2| A| =2n；5.集合的分划： (等价关系 )①每一个分划都是由集合 A 的几个子集构成的集合；② 几个子集相交空，相并全(A)；6.集合的分划与覆盖的比：分划：每个元素均出且出一次在子集中；覆盖：只要求每个元素都出，没有要求只出一次；第五章关系1.若集合 A 有 m 个元素，集合 B 有 n 个元素，笛卡 A×B 的基数mn，A 到B 上可以定2mn种不同的关系；2.若集合 A 有 n 个元素， |A ×A|= n2，A 上有2n2个不同的关系；3.全关系的性：自反性，称性，性；空关系的性：反自反性，反称性，性；全封的性：自反性，称性，反称性，性；4.前域 (domR) ：所有元素 x 成的集合；后域 (ranR) ：所有元素 y 成的集合；5.自反包： r(R)=RU I x ;称包： s(R)=RU R-1 ;包： t(R)=RU R2 U R3 U⋯⋯6.等价关系：集合 A 上的二元关系 R 足自反性，称性和性，R 称等价关系；7.偏序关系：集合 A 上的关系 R 足自反性，反称性和性，称 R 是 A 上的一个偏序关系；8.covA={<x,y>|x,y属于A，y盖住x}；9.极小元：集合 A 中没有比它更小的元素 (若存在可能不唯一 )；极大元：集合 A 中没有比它更大的元素 (若存在可能不唯一 )；最小元：比集合 A 中任何其他元素都小 (若存在就一定唯一 )；最大元：比集合 A 中任何其他元素都大 (若存在就一定唯一 )；10.前提： B 是 A 的子集上界： A 中的某个元素比 B 中任意元素都大，称个元素是 B 的上界 (若存在，可能不唯一 )；下界： A 中的某个元素比 B 中任意元素都小，称个元素是 B 的下界 (若存在，可能不唯一 )；上确界：最小的上界 (若存在就一定唯一 )；下确界：最大的下界 (若存在就一定唯一 )；第六章函数1.若|X|=m,|Y|=n, 则从 X 到 Y 有2mn种不同的关系，有n m种不同的函数；2.在一个有 n 个元素的集合上，可以有2n2种不同的关系，有n n种不同的函数，有 n!种不同的双射；3.若|X|=m,|Y|=n ，且 m<=n ，则从 X 到 Y 有A m n种不同的单射；4.单射： f:X-Y ，对任意x1 , x2属于 X, 且x1≠x2，若 f( x1 )≠f( x2 )；满射： f:X-Y ，对值域中任意一个元素 y 在前域中都有一个或多个元素对应；双射： f:X-Y ，若 f 既是单射又是满射，则 f 是双射；5.复合函数： fog=g(f(x));6.设函数 f:A-B ，g:B-C ，那么①如果 f,g 都是单射，则 fog 也是单射；②如果 f,g 都是满射，则 fog 也是满射；③如果 f,g都是双射，则 fog 也是双射；④如果 fog 是双射，则 f 是单射， g 是满射；第七章代数系统1.二元运算：集合 A 上的二元运算就是A2到A的映射；2.集合 A 上可定义的二元运算个数就是从 A×A 到 A 上的映射的个数，即从从 A×A 到 A 上函数的个数，若 |A|=2, 则集合 A 上的二元运算的个数为 22* 2= 24=16种；3.判断二元运算的性质方法：①封闭性：运算表内只有所给元素；②交换律：主对角线两边元素对称相等；③幂等律：主对角线上每个元素与所在行列表头元素相同；④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同；⑤有零元：元素所对应的行和列的元素都与该元素相同；4.同态映射：<A,*>,<B,^>, 满足 f(a*b)=f(a)^f(b), 则 f 为由 <A,*> 到<B,^>的同态映射；若 f 是双射，则称为同构；第八章群1.广群的性质：封闭性；半群的性质：封闭性，结合律；含幺半群 (独异点 )：封闭性，结合律，有幺元；群的性质：封闭性，结合律，有幺元，有逆元；2.群没有零元；3.阿贝尔群 (交换群 )：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元；5.任何一个循环群必定是阿贝尔群；第十章格与布尔代数1.格：偏序集合 A 中任意两个元素都有上、下确界；2.格的基本性质：1)自反性a≤a对偶: a≥a2)反对称性a≤b ^ b ≥a=> a=b对偶 :a≥b ^ b ≤a=> a=b3)传递性a≤b ^ b ≤c => a≤c对偶 :a≥b ^ b ≥c => a≥c4)最大下界描述之一a^b ≤a对偶avb≥aA^b ≤b对偶avb≥b5）最大下界描述之二c≤a,c≤b => c≤a^b对偶 c≥a,c ≥b => c≥avb6)结合律a^(b^c)=(a^b)^c对偶 av(bvc)=(avb)vc7)等幂律a^a=a对偶ava=a8)吸收律a^(avb)=a 对偶av(a^b)=a9) a≤b <=> a^b=a avb=b10)a≤c,b≤d => a^b ≤c^d avb ≤cvd11)保序性b≤c => a^b≤ a^c avb≤ avc12 ）分配不等式av(b^c) ≤(avb)^(avc)对偶a^(bvc) ≥(a^b)v(a^c)13）模不等式a≤c <=>av(b^c) ≤(avb)^c3.分配格：满足 a^(bvc)=(a^b)v(a^c) 和 av(b^c)=(avb)^(avc) ；4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构；5.链格一定是分配格，分配格必定是模格；6.全上界：集合 A 中的某个元素 a 大于等于该集合中的任何元素，则称 a 为格 <A,<=> 的全上界，记为1；(若存在则唯一 )全下界：集合 A 中的某个元素 b 小于等于该集合中的任何元素，则称 b 为格 <A,<=> 的全下界，记为0；(若存在则唯一 )7.有界格：有全上界和全下界的格称为有界格，即有0 和 1 的格；8.补元：在有界格内，如果a^b=0,avb=1 ，则 a 和 b 互为补元；9.有补格：在有界格内，每个元素都至少有一个补元；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.可达：对于图中的两个节点v i , v j，若存在连接v i到v j的路，则称v i 与 v j相互可达，也称v i与 v j是连通的；在有向图中，若存在v i到 v j的路，则称 v i到v j可达；13.强连通：有向图章任意两节点相互可达；单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必定是单向连通 )14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集；割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点；15.关联矩阵： M(G) ，m ij是v i与e j关联的次数，节点为行，边为列；无向图：点与边无关系关联数为0，有关系为 1，有环为 2；有向图：点与边无关系关联数为0，有关系起点为 1 终点为 -1，关联矩阵的特点：无向图：①行：每个节点关联的边，即节点的度；②列：每条边关联的节点；有向图：③所有的入度 (1)=所有的出度 (0);16.邻接矩阵： A(G) ，a ij是v i邻接到v j的边的数目，点为行，点为列；17.可达矩阵： P(G) ，至少存在一条回路的矩阵，点为行，点为列；P(G)=A(G)+ A2 (G)+ A3 (G)+ A4 (G)可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路；A(G) 中所有数的和：表示图中路径长度为 1 的通路条数；A2(G)中所有数的和：表示图中路径长度为 2 的通路条数；A3(G)中所有数的和：表示图中路径长度为 3 的通路条数；A4(G)中所有数的和：表示中路径度 4 的通路条数；P(G) 中主角所有数的和：表示中的回路条数；18.布矩： B(G) ，v i到v j有路 1，无路 0，点行，点列；19.代价矩：接矩元素 1 的用表示，0 的用无大表示，点自身到自身的0；20.生成：只每个点一次，的点和构成的子；21.构造生成的两种方法：深度先；广度先；深度先：① 定起始点v0；② 一个与v0接且未被的点v1；③从 v1出按接方向，当遇到一个点所有接点均已被，回到点的前一个点，再求未被的接点，直到所有点都被一次；广度先：① 定起始点 v0；② 与 v0接的所有点v1, v2,⋯⋯, v k,些作第一点；③在第一点中定一个点v1起点；④重复②③，直到所有点都被一次；22.最小生成：具有最小(T) 的生成；23.构造最小生成的三种方法：克斯卡方法；管梅谷算法；普利姆算法；（1）克鲁斯卡尔方法①将所有权值按从小到大排列；②先画权值最小的边，然后去掉其边值；重新按小到大排序；③再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序；④重复③，直到所有节点都被访问过一次；（2）管梅谷算法 (破圈法 )①在图中取一回路，去掉回路中最大权值的边得一子图；②在子图中再取一回路，去掉回路中最大权值的边再得一子图；③重复②，直到所有节点都被访问过一次；（3）普利姆算法①在图中任取一点为起点v1，连接边值最小的邻接点v2；②以邻接点 v2为起点，找到v2邻接的最小边值，如果最小边值比v1邻接的所有边值都小(除已连接的边值)，直接连接，否则退回 v1，连接 v1现在的最小边值(除已连接的边值)；③重复操作，直到所有节点都被访问过一次；24.关键路径例2 求 PERT 图中各顶点的最早完成时间 , 最晚完成时间 , 缓冲时间及关键路径 .解：最早完成时间TE(v1)=0TE(v2)=max{0+1}=1TE(v3)=max{0+2,1+0}=2TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6TE(v8)=max{9+1,6+6}=12最晚完成时间TL(v8)=12TL(v7)=min{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2TL(v2)=min{2-0,10-3,6-4}=2TL(v1)=min{2-1,2-2,6-3}=0缓冲时间TS(v1)=0-0=0TS(v2)=2-1=1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v6)=11-9=2TS(v7)=6-6=0TS(v8)=12-12=0关键路径 : v1-v3-v7-v825.欧拉路：经过图中每条边一次且仅一次的通路；欧拉回路：经过图中每条边一次且仅一次的回路；欧拉图：具有欧拉回路的图；单向欧拉路：经过有向图中每条边一次且仅一次的单向路；欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路；26.（1）无向图中存在欧拉路的充要条件：①连通图；②有 0 个或 2 个奇数度节点；（2）无向图中存在欧拉回路的充要条件：①连通图；②所有节点度数均为偶数；（3）连通有向图含有单向欧拉路的充要条件：①除两个节点外，每个节点入度=出度；②这两个节点中，一个节点的入度比出度多1，另一个节点的入；度比出度少 1；（4）连通有向图含有单向欧拉回路的充要条件：图中每个节点的出度 =入度；27.哈密顿路：经过图中每个节点一次且仅一次的通路；哈密顿回路：经过图中每个节点一次且仅一次的回路；哈密顿图：具有哈密顿回路的图；28.判定哈密顿图（没有充要条件）必要条件：任意去掉图中 n 个节点及关联的边后，得到的分图数目小于等于n；充分条件：图中每一对节点的度数之和都大于等于图中的总节点数；29.哈密顿图的应用：安排圆桌会议；方法：将每一个人看做一个节点，将每个人与和他能交流的人连接，找到一条经过每个节点一次且仅一次的回路(哈密顿图 )，即可；30.平面图：将图形的交叉边进行改造后，不会出现边的交叉，则是平面图；31.面次：面的边界回路长度称为该面的次；32.一个有限平面图，面的次数之和等于其边数的两倍；33.欧拉定理：假设一个连通平面图有v 个节点， e 条边， r 个面，则v-e+r=2 ；34.判断是平面图的必要条件：(若不满足，就一定不是平面图)设图 G 是 v 个节点，e 条边的简单连通平面图，若 v>=3 ，则 e<=3v-6 ；35.同胚：对于两个图G1,G2 ，如果它们是同构的，或者通过反复插入和除去 2 度节点可以变成同构的图，则称G1，G2 是同胚的；36.判断 G 是平面图的充要条件：图 G 不含同胚于 K3.3 或 K5 的子图；37.二部图：①无向图的节点集合可以划分为两个子集V1 ，V2；②图中每条边的一个端点在 V1 ，另一个则在 V2 中；完全二部图：二部图中 V1 的每个节点都与 V2 的每个节点邻接；判定无向图 G 为二部图的充要条件：图中每条回路经过边的条数均为偶数；38.树：具有 n 个顶点 n-1 条边的无回路连通无向图；39.节点的层数：从树根到该节点经过的边的条数；40.树高：层数最大的顶点的层数；41.二叉树：①二叉树额基本结构状态有 5 种；②二叉树内节点的度数只考虑出度，不考虑入度；③二叉树内树叶的节点度数为 0，而树内树叶节点度数为 1；④二叉树内节点的度数 =边的总数 (只算出度 )；握手定理“节点数=边的两倍”是在同时计算入度和出度的时成立；⑤二叉树内节点的总数=边的总数 +1；⑥位于二叉树第k 层上的节点，最多有2k 1个(k>=1)；⑦深度为k的二叉树的节点总数最多为2k-1个，最少k 个 (k>=1) ；⑧如果有 n0个叶子， n2个2度节点，则 n0= n2+1；42.二叉树的节点遍历方法：先根顺序（ DLR ）；中根顺序（ LDR ）；后根顺序（ LRD ）；43.哈夫曼树：用哈夫曼算法构造的最优二叉树；44.最优二叉树的构造方法：①将给定的权值按从小到大排序；②取两个最小值分支点的左右子树(左小右大 )，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值；③重复②，直达所有权值构造完毕；45.哈夫曼编码：在最优二叉树上，按照左0 右 1 的规则，用 0 和 1代替所有边的权值；每个节点的编码：从根到该节点经过的0 和 1 组成的一排编码；。