离散知识点总结

本学期离散课程我们共学习了命题逻辑，一阶逻辑，集合的基本概念，二元关系和函数，图的基本概念，树等六章内容。第一章命题逻辑在读取蕴含式时，如果前件为假，命题逻辑就为真。重要等值式：分配律，德.摩根律，吸收律，蕴含等值式，由有限个简单合取式构成的析取式称为析取范式；由有限个简单析取式构成的合取式称为合取范式。N个命题变项，在简单合取式中每个命题变项与其否定有且仅有一个出现一次，称为极小项。N个命题变项，在简单析取式中每个命题变项与其否定有且仅有一个出现一次，称为极大项。若合取范式中的简单析取式全是极大项，则该合取范式称为主合取范式。任一命题公式都有唯一的主合取范式。最简展开式：包含最少运算。推理定律：附加，化简，假言推理，拒取式，析取三段论，假言三段论，等价三段论，构造性二难构造证明法的技巧：附加前提证明法，归缪法。难点：构造推理的证明。原因：需要有一定的解题技巧性。解决方法：深刻理解推理定律并记住，多加练习。第二章一阶逻辑自由出现和约束出现无自由出现的个体变项简称闭式。换名规则：将一个指导变项及其所在辖域中所有约束出现替换成公式中没有出现的个体变项符号。用谓词公式处处代换命题公式，即代换实例。量词否定等值式，量词辖域收缩与扩张等值式，量词分配等值式。A为一谓词公式，若A具有Q1x1Q2x2・・・.B，则称A是前束范式。难点：前束范式的求取。原因：解题往往要用多个定理和换名规则，较繁琐。解决方法：熟练掌握定理和规则，多做题。第三章集合的基本概念和运算幕等律，结合律，交换律，分配律，同一律，零律，排中律，矛盾律，吸收律，德摩根律双重否定律难点：集合关系的证明，集合的化简

原因：运算较复杂解决方法：掌握算律，特别是德摩根律。第四章二元关系和函数A上二元关系：全域关系EA；恒等关系IA；小于等于关系LA；整除关系DA；4.1~2定义域domR值域ranR过与台雁L={<Vik>|<k如S=|<<z>|3yI定俚勺设E是A上的美卜％I定俚勺设E是A上的美卜％Y虬甜FfA= |sFyAxeA)M歼敝FtAl=van-CFfA)定理z设F,G.H是任意的关系.则⑵gG)土膏为故上的美采，。为台登数，则W的"次霎定*定理z设F,G.H是任意的关系.则⑵gG)土《£，r41=s也r定理1设F是任意的关条，对n<n《F-1EFQC2)dorriF^=ranF?ranF-1=domF4.3~4I设就I设就A上的关系，K)上白反当日仙当％仁骸E)E在A上反白反当且任当日「|1广0《力R在A上对祢当日侃当E次-，oe在冉上反对称当且佃当rn质企⑸晦A上传述当旦任当昨京0白&阮首卮ftuRlX=OE=R-'雇咔小主对南主时由IlTDt全是口括阵是对飘**'毛，州J.-■□志值虹U中期由侵置都是1关IStttli忸个】吏点都设选.是一XI白曲帽庄的之间节边，是-ff-fi也世t无器食 如禀值巨%搓典到虹.妁从调,t曲 特殊的：若R只含有一个有序对，也满足传递关系(前提条件为假)自反闭包r(R)对称闭包s(R)传递闭包t(R)4.5哈斯图：利用偏序自反，反对称，传递性简化的关系图。特点：每个结点没有环，两个连通的结点之间的关系通过结点位置的高低表示。难点：关系的运算，传递性的判定，哈斯图的应用原因：都比较抽象，难以理解。解决方法：多念几遍定义和老师的讲解，做题。第五章图的基本概念5.1~2握手定理：任意无向图和有向图的所有顶点度数之和都等于边数的2倍，并且有向图的所有顶点入度之和等于出度之和等于边数。点割集：定义设无向图G=VV，E＞，Vcv，若(G-V，)＞p(G)且V”CV，P(G-V”)=p(G)，则称V，为G的点割集若(v)为点割集，则称为割点。边割集：定义设无向图G=VV，E＞，E，SE，若p(G-E1)p(G)且VE”CEPCG-E”)=p(G)，则称E，为G的边割集.若(e)为边割集，则称e为割边或桥。5.4最短路径：u,v之间权最小的通路。标号法项目网络图：项目网络图：表示项目的活动之间前后顺序一致的带权有向图，边表示活动，边的权是活动的完成时间，顶点表示事顶(项目的开始和结束、活动的开始和结束).要求：1)有一个始点(入度为D)和一个终点(出度为D).两点之间只能有一条边，可以引入虚活动。没有回路关键路径：项目网络图从始点到终点的最长路径。事项的最早开始时间MAX(ES)事项的最晚完成时间MIN(LF)着色：定义设无向图G无环，对G的每个顶点涂一种颜色使相邻的顶点涂不同的颜色，称为图G的一种点着色，简称着色PS：颜色最多四种。难点：项目网络图的绘制和应用，求最短路径原因：题难度大，做题步骤复杂，一步错步步错。解决方法：看懂网络图，结合实际生活明白数值怎么出来的。第七章树树叶：树中度数为1的顶点。最优二叉树：Huffman算法：给定实数w,w,…，t,作七片树叶，分别以w，w2,…，w为权在所有入度为0的顶点（不一定是树叶）中选出两个权最小的顶点，添加一个新分支点，以这2个顶点为儿子，其权等于这2个儿子的权之和.重复②，直到只有1个入度为0的顶点为止.W（T）等于所有分支点的权之和二元前缀码：只有两个符号的前缀码。设要传输的电文中含有七个字符，字符a出现的