《离散数学重点（2011离散数学A卷（郑州轻工业学院》由会员分享，可在线阅读，更多相关《离散数学重点（2011离散数学A卷（郑州轻工业学院（7页珍藏版）》请在金锄头文库上搜索。
1、 离散数学重点这个只是离散的重点，有些重点没介绍太多，去课本上找到，好好了解下，题目就是做老 师给的那几套题就够了，通过做题对重点更加理解。有题不会的 QQ 问，不发答案了。按章 节开始。数理逻辑1.，前键为真，后键为假才为假；，相同为真，不同为假；2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；3.求极小项时，命题变元的肯定为 1，否定为 0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真， 求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按 P,Q,R 的顺序依次写；6.真值表中值为 1 的项为极小项，值
2、为 0 的项为极大项； 7.n 个变元共有 n2 个极小项或极大项，这 2n为(0 2n-1)刚好为化简完后的主析取加主合取；8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假 推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 真值表法；直接证法；归谬法；附加前提法； 11.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有 n 个个 体，多元谓词描述个体之间的关系； 2.全称量词用蕴含，存在量词用合取; 12.既有存在又有全称量词时，先消存在量词，再消全称量词； 集合论第
3、六章 集合 1.N，表示自然数集，1,2,3，不包括 0；2.基：集合 A 中不同元素的个数，|A|； 3.幂集：给定集合 A，以集合 A 的所有子集为元素组成的集合，P(A)； 4.若集合 A 有 n 个元素，幂集 P(A)有 2n个元素，|P(A)|= = 2n；5.集合的划分：(等价关系) 每一个分划都是由集合 A 的几个子集构成的集合； 这几个子集相交为空，相并为 全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没 有要求只出现一次；第七章 二元关系 1.若集合 A 有 m 个元素，集合 B 有 n 个元素，则笛卡尔
4、AB 的基数为 mn，A 到 B 上可以定义种不同的关系； 2.若集合 A 有 n 个元素，则|AA|=，A 上有个不同的关系；3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性；4.前域(domR)：所有元素 x 组成的集合； 后域(ranR)：所有元素 y 组成的集合；5. 自反闭包：r(R)=RUIA; 对称闭包：s(R)=RUR1; 传递闭包： 6.等价关系：集合 A 上的二元关系 R 满足自反性，对称性和传递性，则 R 称为等价关系； 7.偏序关系：集合 A 上的关系 R 满足自反性，反对称性和传递
5、性，则称 R 是 A 上的一个偏 序关系；8.covA=|x,y 属于 A，y 盖住 x； 9.极小元：集合 A 中没有比它更小的元素(若存在可能不唯一)； 极大元：集合 A 中没有比 它更大的元素(若存在可能不唯一)； 最小元：比集合 A 中任何其他元素都小(若存在就一 定唯一)； 最大元：比集合 A 中任何其他元素都大(若存在就一定唯一)； 10.前提：B 是 A 的子集 上界：A 中的某个元素比 B 中任意元素都大，称这个元素是 B 的上界(若存在，可能不唯 一)； 下界：A 中的某个元素比 B 中任意元素都小，称这个元素是 B 的下界(若存在，可能不唯 一)； 上确界：最小的上界(若存
6、在就一定唯一)； 下确界：最大的下界(若存在就一定唯一)；第八章 函数 1.若|X|=m,|Y|=n,则从 X 到 Y 有 mn 2 种不同的关系，有 m n 种不同的函数； 2.在一个有 n 个元素的集合上，可以有 2 2n 种不同的关系，有 nn 种不同的函数，有 n!种不同的双射； 3.若|X|=m,|Y|=n，且 m,满足 f(a*b)=f(a)f(b),则 f 为由到的同态映射；若 f 是双 射，则称为同构； 第十章 群 1.广群的性质：封闭性； 半群的性质：封闭性，结合律； 含幺半群(独异点)：封闭性，结合律，有幺元； 群的性质：封闭性，结合律，有幺元， 有逆元； 2.群没有零元；
7、 3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元； 5.任何一个循环群必定是阿贝尔群；第十一章 格与布尔代数 1.格：偏序集合 A 中任意两个元素都有上、下确界； 2.格的基本性质： 1) 自反性 aa 对偶: aa 2) 反对称性 ab ba = a=b 对偶:ab ba = a=b 3) 传递性 ab bc = ac 对偶:ab bc = ac 4) 最大下界描述之一 aba 对偶 avba Abb 对偶 avbb 5）最大下界描述之二 ca,cb = cab 对偶 ca,cb =cavb 6) 结合律 a(bc)=(ab)c 对偶 av(bv
8、c)=(avb)vc 7) 等幂律 aa=a 对偶 ava=a 8) 吸收律 a(avb)=a 对偶 av(ab)=a 9) ab ab=a avb=b 10) ac,bd = abcd avbcvd 11) 保序性 bc = abac avbavc 12） 分配不等式av(bc)(avb)(avc) 对偶 a(bvc)(ab)v(ac) 13）模不等式 ac av(bc)(avb)c 3.分配格：满足 a(bvc)=(ab)v(ac)和 av(bc)=(avb)(avc)；4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构；5.链格一定是分配格，分配格必定是模格； 6.全上界：集合
9、A 中的某个元素 a 大于等于该集合中的任何元素，则称 a 为格的全 上界，记为 1；(若存在则唯一) 全下界：集合 A 中的某个元素 b 小于等于该集合中的任何元素，则称 b 为格的全下 界，记为 0；(若存在则唯一) 7.有界格：有全上界和全下界的格称为有界格，即有 0 和 1 的格； 8.补元：在有界格内，如果 ab=0,avb=1，则 a 和 b 互为补元； 9.有补格：在有界格内，每个元素都至少有一个补元； 10.有补分配格(布尔格)：既是有补格，又是分配格； 11.布尔代数：一个有补分配格称为布尔代数；图论1.邻接：两点之间有边连接，则点与点邻接； 2.关联：两点之间有边连接，则这
10、两点与边关联；3.平凡图：只有一个孤立点构成的图； 4.简单图：不含平行边和环的图； 5.无向完全图：n 个节点任意两个节点之间都有边相连的简单无向图； 有向完全图:n 个节点任意两个节点之间都有边相连的简单有向图； 6.无向完全图有 n(n-1)/2 条边，有向完全图有 n(n-1)条边； 7.r-正则图：每个节点度数均为 r 的图； 8.握手定理：节点度数的总和等于边的两倍；9.任何图中，度数为奇数的节点个数必定是偶数个； 10.任何有向图中，所有节点入度之和等于所有节点的出度之和； 11.每个节点的度数至少为 2 的图必定包含一条回路； 12.可达：对于图中的两个节点 iv,jv，若存在
11、连接 iv 到 jv 的路，则称 iv 与 jv 相互可达，也 称 iv 与 jv 是连通的；在有向图中，若存在 iv 到 jv 的路，则称 iv 到 jv 可达； 13.强连通：有向图章任意两节点相互可达； 单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必定是单向连通) 14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍 是连通的，则这些点组成的集合称为点割集； 割点：如果一个点构成点割集，即删去图 中的一个点后所得子图是不连通的，则该点称为割点； 15.关联矩阵：M(G)，ijm 是 iv 与 je 关联的次数，节点为行，边为列； 无
12、向图：点与边无 关系关联数为 0，有关系为 1，有环为 2； 有向图：点与边无关系关联数为 0，有关系起 点为 1 终点为-1， 关联矩阵的特点： 无向图： 行：每个节点关联的边，即节点的度； 列：每条边关联的节点； 有向图： 所有的入度(1)=所有的出度(0); 16.邻接矩阵：A(G)，ija 是 iv 邻接到 jv 的边的数目，点为行，点为列； 17.可达矩阵：P(G)， 至少存在一条回路的矩阵，点为行，点为列； P(G)=A(G)+2A(G)+3A(G)+4A(G) 可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是 否存在回路； A(G)中所有数的和：表示图
13、中路径长度为 1 的通路条数； 2A(G)中所有数的和：表示图 中路径长度为 2 的通路条数； 3A(G)中所有数的和：表示图中路径长度为 3 的通路条数； A(G)中所有数的和：表示图中路径长度为 4 的通路条数； P(G)中主对角线所有数的和：表示图中的回路条数； 18.布尔矩阵：B(G)，iv 到 jv 有路为 1，无路则为 0，点为行，点为列； 19.代价矩阵：邻 接矩阵元素为 1 的用权值表示，为 0 的用无穷大表示，节点自身到自身的权值为 0； 20.生成树：只访问每个节点一次，经过的节点和边构成的子图； 21.构造生成树的两种方法：深度优先；广度优先； 深度优先： 选定起始点 0
14、v； 选择一个与 0v 邻接且未被访问过的节点 1v； 从 1v 出发按邻接方向继续访问，当遇到一个节点所有邻接点均已被访问时，回 到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次； 广度优先： 选定起始点 0v； 访问与 0v 邻接的所有节点 1v,2v,kv,这些作为第一层节点； 在第一层节点中选定一个节点 1v 为起点； 重复，直到所有节点都被访问过一次； 22.最小生成树：具有最小权值(T)的生成树； 23.构造最小生成树的三种方法： 克鲁斯卡尔方法；管梅谷算法；普利姆算法； （1）克鲁斯卡尔方法 将所有权值按从小到大排列； 先画权值最小的边，然后去掉其边值；重
15、新按小到大排序； 再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去 掉其边值；重新按小到大排序； 重复，直到所有节点都被访问过一次； （2）管梅谷算法(破圈法) 在图中取一回路，去掉回路中最大权值的边得一子图； 在子图中再取一回路，去掉回路中最大权值的边再得一子图； 重复，直到所有节点都被访问过一次； （3）普利姆算法 在图中任取一点为起点 1v，连接边值最小的邻接点 2v；以邻接点 2v 为起点，找到 2v 邻接的最小边值，如果最小边值比 1v 邻接的所有边值 都小(除已连接的边值)，直接连接，否则退回 1v，连接 1v 现在的最小边值(除已连接的边 值)； 重复操作，直到所有节点都被访问过一次； 24.欧拉路：经过图中每条边一次且仅一次的通路； 欧拉回路：经过图中每条边一次且 仅一次的回路； 欧拉图：具有欧拉回路的图； 单向欧拉路：经过有向图中每条边一次且仅一次的单向
