离散数学必备知识点总结.doc

1、总结 离散数学知识点第 2 章 命题逻辑1. ，前键为真，后键为假才为假；，相同为真，不同为假；2.主析取范式：极小项(m) 之和；主合取范式：极大项(M) 之积；3.求极小项时，命题变元的肯定为 1，否定为 0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；5.求范式时，为保证编码不错，命题变元最好按 P,Q,R 的顺序依次写；6.真值表中值为 1 的项为极小项，值为 0 的项为极大项；7.n 个变元共有 个极小项或极大项，这 为(0 -1)刚好为化简完n2n2n后的主析取加主合取；8.永真式没有主合取范式，永假式没

2、有主析取范式；9.推证蕴含式的方法(=)：真值表法；分析法( 假定前键为真推出后键为真，假定前键为假推出后键也为假)10.命题逻辑的推理演算方法：P 规则，T 规则真值表法；直接证法；归谬法；附加前提法；第 3 章 谓词逻辑1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质；多元谓词：谓词有 n 个个体，多元谓词描述个体之间的关系；2.全称量词用蕴含，存在量词用合取;3.既有存在又有全称量词时，先消存在量词，再消全称量词；第 4 章 集合1.N，表示自然数集，1,2,3，不包括 0；2.基：集合 A 中不同元素的个数，|A|；3.幂集：给定集合 A，以集合 A 的所有子集为元素组成的集合，

3、P(A)；4.若集合 A 有 n 个元素，幂集 P(A)有 个元素，|P(A)|= = ；n2|2An5.集合的分划：( 等价关系)每一个分划都是由集合 A 的几个子集构成的集合；这几个子集相交为空，相并为全(A)；6.集合的分划与覆盖的比较：分划：每个元素均应出现且仅出现一次在子集中；覆盖：只要求每个元素都出现，没有要求只出现一次；第 5 章 关系1.若集合 A 有 m 个元素，集合 B 有 n 个元素，则笛卡尔 AB 的基数为 mn，A 到 B 上可以定义 种不同的关系；m22.若集合 A 有 n 个元素，则|AA|= ，A 上有 个不同的关系；22n3.全关系的性质：自反性，对称性，传递

4、性；空关系的性质：反自反性，反对称性，传递性；全封闭环的性质：自反性，对称性，反对称性，传递性；4.前域(domR)：所有元素 x 组成的集合；后域(ranR)：所有元素 y 组成的集合；5.自反闭包：r(R)=RU ;xI对称闭包：s(R)=RU ;1-R传递闭包：t(R)=RU U U236.等价关系：集合 A 上的二元关系 R 满足自反性，对称性和传递性，则 R 称为等价关系；7.偏序关系：集合 A 上的关系 R 满足自反性，反对称性和传递性，则称 R 是 A 上的一个偏序关系；8.covA=|x,y 属于 A，y 盖住 x；9.极小元：集合 A 中没有比它更小的元素(若存在可能不唯一)

5、 ；极大元：集合 A 中没有比它更大的元素(若存在可能不唯一)；最小元：比集合 A 中任何其他元素都小(若存在就一定唯一)；最大元：比集合 A 中任何其他元素都大(若存在就一定唯一)；10.前提： B 是 A 的子集上界：A 中的某个元素比 B 中任意元素都大，称这个元素是 B的上界(若存在，可能不唯一)；下界：A 中的某个元素比 B 中任意元素都小，称这个元素是 B的下界(若存在，可能不唯一)；上确界：最小的上界(若存在就一定唯一) ；下确界：最大的下界(若存在就一定唯一) ；第 6 章 函数1.若 |X|=m,|Y|=n,则从 X 到 Y 有 种不同的关系，有 种不同的函mn2mn数；2.

6、在一个有 n 个元素的集合上，可以有 种不同的关系，有 种不2n n同的函数，有 n!种不同的双射；3.若 |X|=m,|Y|=n，且 m, 满足 f(a*b)=f(a)f(b),则 f 为由 到的同态映射；若 f 是双射，则称为同构；第 8 章 群1.广群的性质：封闭性；半群的性质：封闭性，结合律；含幺半群(独异点) ：封闭性，结合律，有幺元；群的性质：封闭性，结合律，有幺元，有逆元；2.群没有零元；3.阿贝尔群( 交换群)：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元；5.任何一个循环群必定是阿贝尔群；第 10 章 格与布尔代数1.格：偏序集合 A 中任意两个元素都

7、有上、下确界；2.格的基本性质：1) 自反性a a 对偶 : aa2) 反对称性a b ba = a=b对偶:ab ba = a=b3) 传递性a b bc = ac对偶:ab bc = ac 4) 最大下界描述之一aba 对偶 avbaAbb 对偶 avbb5）最大下界描述之二ca,cb = cab对偶 ca,cb = cavb 6) 结合律a(bc)=(ab)c 对偶 av(bvc)=(avb)vc 7) 等幂律aa=a 对偶 ava=a8) 吸收律a(avb)=a 对偶 av(ab)=a9) ab ab=a avb=b10) ac,bd = abcd avbcvd11) 保序性bc =

8、abac avbavc12） 分配不等式av(bc)(avb)(avc)对偶 a(bvc)(ab)v(ac)13）模不等式a c av(bc)(avb)c3.分配格：满足 a(bvc)=(ab)v(ac)和 av(bc)=(avb)(avc)；4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构；5.链格一定是分配格，分配格必定是模格；6.全上界：集合 A 中的某个元素 a 大于等于该集合中的任何元素，则称 a 为格 的全上界，记为 1；( 若存在则唯一 )全下界：集合 A 中的某个元素 b 小于等于该集合中的任何元素，则称 b 为格 的全下界，记为 0；( 若存在则唯一 )7.有界格：

9、有全上界和全下界的格称为有界格，即有 0 和 1 的格；8.补元：在有界格内，如果 ab=0,avb=1，则 a 和 b 互为补元；9.有补格：在有界格内，每个元素都至少有一个补元；10.有补分配格(布尔格)：既是有补格，又是分配格；11.布尔代数：一个有补分配格称为布尔代数；第 11 章 图论1.邻接：两点之间有边连接，则点与点邻接；2.关联：两点之间有边连接，则这两点与边关联；3.平凡图：只有一个孤立点构成的图；4.简单图：不含平行边和环的图；5.无向完全图：n 个节点任意两个节点之间都有边相连的简单无向图；有向完全图:n 个节点任意两个节点之间都有边相连的简单有向图；6.无向完全图有 n

10、(n-1)/2 条边，有向完全图有 n(n-1)条边；7.r-正则图：每个节点度数均为 r 的图；8.握手定理：节点度数的总和等于边的两倍；9.任何图中，度数为奇数的节点个数必定是偶数个；10.任何有向图中，所有节点入度之和等于所有节点的出度之和；11.每个节点的度数至少为 2 的图必定包含一条回路；12.可达：对于图中的两个节点 , ，若存在连接 到 的路，则称ivj ivj与 相互可达，也称 与 是连通的；在有向图中，若存在 到ivj ij iv的路，则称 到 可达；j ivj13.强连通：有向图章任意两节点相互可达；单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必

11、定是单向连通)14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集；割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点；15.关联矩阵：M(G)， 是 与 关联的次数，节点为行，边为列；ijmivje无向图：点与边无关系关联数为 0，有关系为 1，有环为 2；有向图：点与边无关系关联数为 0，有关系起点为 1 终点为-1，关联矩阵的特点：无向图：行：每个节点关联的边，即节点的度；列：每条边关联的节点；有向图： 所有的入度(1)= 所有的出度 (0);16.邻接矩阵：A(G)， 是 邻接到 的边的

12、数目，点为行，点为列；ijaivj17.可达矩阵：P(G)，至少存在一条回路的矩阵，点为行，点为列；P(G)=A(G)+ (G)+ (G)+ (G)2A34A可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路；A(G)中所有数的和：表示图中路径长度为 1 的通路条数；(G)中所有数的和：表示图中路径长度为 2 的通路条数；2A(G)中所有数的和：表示图中路径长度为 3 的通路条数；3(G)中所有数的和：表示图中路径长度为 4 的通路条数；4P(G)中主对角线所有数的和：表示图中的回路条数；18.布尔矩阵：B(G)， 到 有路为 1，无路则为 0，点为行，点为ivj列；19.代价矩阵：邻接矩阵元素为 1 的用权值表示，为 0 的用无穷大表示，节点自身到自身的权值为 0；20.生成树：只访问每个节点一次，经过的节点和边构成的子图；21.构造生成树的两种方法：深度优先；广度优先；深度优先：选定起始点 ；0v选择一个与 邻接且未被访问过的节点 ；1v从 出发按邻接方向继续访问，当遇到一个节点所1v有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次；