离散数学重点(2011离散数学A卷(郑州轻工业学院.doc

离散数学重点这个只是离散的重点，有些重点没介绍太多，去课本上找到，好好了解下，题目就是做老师给的那几套题就够了，通过做题对重点更加理解有题不会的 问，不发答案了按章节开始数理逻辑1.→，前键为真，后键为假才为假； ，相同为真，不同为假；2.主析取范式：极小项(m)之和；主合取范式：极大项(M) 之积；3.求极小项时，命题变元的肯定为 1，否定为 0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按 P,Q,R 的顺序依次写；6.真值表中值为 1 的项为极小项，值为 0 的项为极大项； 7.n 个变元共有 n2 个极小项或极大项，这 2n为(0~ 2 n-1)刚好为化简完后的主析取加主合取；8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>) ：真值表法；分析法 (假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ① 真值表法；②直接证法；③归谬法；④附加前提法；11.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有 n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^;12.既有存在又有全称量词时，先消存在量词，再消全称量词； 集合论第六章 集合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 个元素，则笛卡尔 A×B 的基数为 mn，A 到 B 上可以定义 种不同的关系； 2.若集合 A 有 n 个元素，则|A×A|= ，A 上有 个不同的关系；3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性；全封闭环的性质：自反性，对称性，反对称性，传递性；4.前域(domR) ：所有元素 x 组成的集合； 后域(ranR)：所有元素 y 组成的集合；5. 自反闭包：r(R)=RUI A; 对称闭包：s(R)=RUR －1 ; 传递闭包： 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 的下界( 若存在，可能不唯一)； 上确界：最小的上界(若存在就一定唯一)； 下确界：最大的下界( 若存在就一定唯一)；第八章 函数 1.若|X|=m,|Y|=n,则从 X 到 Y 有 mn2 种不同的关系，有 mn 种不同的函数； 2.在一个有 n 个元素的集合上，可以有 22n 种不同的关系，有 nn 种不同的函数，有 n!种不同的双射； 3.若|X|=m,|Y|=n，且 m,, 满足 f(a*b)=f(a)^f(b),则 f 为由到的同态映射；若 f 是双射，则称为同构； 第十章 群 1.广群的性质：封闭性； 半群的性质：封闭性，结合律； 含幺半群(独异点)：封闭性，结合律，有幺元； 群的性质：封闭性，结合律，有幺元，有逆元； 2.群没有零元； 3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元； 5.任何一个循环群必定是阿贝尔群；第十一章 格与布尔代数 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) 等幂律 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.有补格：在有界格内，每个元素都至少有一个补元； 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.强连通：有向图章任意两节点相互可达； 单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必定是单向连通 ) 14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集； 割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点； 15.关联矩阵：M(G)，ijm 是 iv 与 je 关联的次数，节点为行，边为列； 无向图：点与边无关系关联数为 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)中所有数的和：表示图中路径长度为 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.构造生成树的两种方法：深度优先；广度优先； 深度优先： ①选定起始点 0v； ②选择一个与 0v 邻接且未被访问过的节点 1v； ③从 1v 出发按邻接方向继续访问，当遇到一个节点所有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次； 广度优先： ① 选定起始点 0v； ② 访问与 0v 邻接的所有节点 1v,2v,„„,kv,这些作为第一层节点； ③ 在第一层节点中选定一个节点 1v 为起点； ④ 重复②③，直到所有节点都被访问过一次； 22.最小生成树：具有最小权值(T)的生成树； 23.构造最小生成树的三种方法： 克鲁斯卡尔方法；管梅谷算法；普利姆算法；（1 ）克鲁斯卡尔方法 ① 将所有权值按从小到大排列； ② 先画权值最小的边，然后去掉其边值；重新按小到大排序； ③ 再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序； ④ 重复③，直到所有节点都被访问过一次； （2 ）管梅谷算法(破圈法) ① 在图中取一回路，去掉回路中最大权值的边得一子图； ②在子图中再取一回路，去掉回路中最大权值的边再得一子图； ③ 重复②，直到所有节点都被访问过一次； （3 ）普利姆算法 ① 在图中任取一点为起点 1v，连接边值最小的邻接点 2v；②以邻接点 2v 为起点，找到 2v 邻接的最小边值，如果最小边值比 1v 邻接的所有边值都小(除已连接的边值)，直接连接，否则退回 1v，连接 1v 现在的最小边值(除已连接的边值)； ③ 重复操作，直到所有节点都被访问过一次；24.欧拉路：经过图中每条边一次且仅一次的通路； 欧拉回路：经过图中每条边一次且仅一次的回路； 欧拉图：具有欧拉回路的图； 单向欧拉路：经过有向图中每条边一次且仅一。