本学期离散课程我们共学习了命题逻辑,一阶逻辑,集合的基本概念,二元关系和函数,图的基本概念,树等六章内容。
第一章命题逻辑
在读取蕴含式时,如果前件为假,命题逻辑就为真。
重要等值式:分配律,德.摩根律,吸收律,蕴含等值式,
由有限个简单合取式构成的析取式称为析取范式;
由有限个简单析取式构成的合取式称为合取范式。
N个命题变项,在简单合取式中每个命题变项与其否定有且仅有一个出现一次,称为极小项。
N个命题变项,在简单析取式中每个命题变项与其否定有且仅有一个出现一次,称为极大项。
若合取范式中的简单析取式全是极大项,则该合取范式称为主合取范式。
任一命题公式都有唯一的主合取范式。
最简展开式:包含最少运算。
推理定律:附加,化简,假言推理,拒取式,析取三段论,假言三段论,等价三段论,构造性二难
构造证明法的技巧:附加前提证明法,归缪法。
难点:构造推理的证明。
原因:需要有一定的解题技巧性。
解决方法:深刻理解推理定律并记住,多加练习。
第二章一阶逻辑
自由出现和约束出现
无自由出现的个体变项简称闭式。
换名规则:将一个指导变项及其所在辖域中所有约束出现替换成公式中没有出现的个体变项符号。
用谓词公式处处代换命题公式,即代换实例。
量词否定等值式,量词辖域收缩与扩张等值式,量词分配等值式。
A为一谓词公式,若A具有Q1x1Q2x2….B,则称A是前束范式。
难点:前束范式的求取。
原因:解题往往要用多个定理和换名规则,较繁琐。
解决方法:熟练掌握定理和规则,多做题。
第三章集合的基本概念和运算
幂等律,结合律,交换律,分配律,同一律,零律,排中律,矛盾律,吸收律,德摩根律双重否定律
难点:集合关系的证明,集合的化简
原因:运算较复杂
解决方法:掌握算律,特别是德摩根律。
第四章二元关系和函数
A上二元关系:全域关系EA;恒等关系IA;小于等于关系LA;整除关系DA;
4.1~2
定义域dom R 值域ran R
4.3~4
特殊的:若R只含有一个有序对,也满足传递关系(前提条件为假)
自反闭包r(R) 对称闭包s(R) 传递闭包t(R)
4.5
哈斯图:利用偏序自反,反对称,传递性简化的关系图。
特点:每个结点没有环,两个连通的结点之间的关系通过结点位置的高低表示。
难点:关系的运算,传递性的判定,哈斯图的应用
原因:都比较抽象,难以理解。
解决方法:多念几遍定义和老师的讲解,做题。
第五章图的基本概念
5.1~2
握手定理:任意无向图和有向图的所有顶点度数之和都等于边数的2倍,并且有向图的所有顶点入度之和等于出度之和等于边数。
点割集:定义设无向图G=<V, E>, V'cv,若(G-V ')>p(G)且V"CV,P(G-V")=p(G),则称V'为G的点割集若(v)为点割集,则称为割点。
边割集:定义设无向图G=<V, E>, E 'SE,若p(G-E 1)p(G)且VE"CEPCG-E ")=p(G),则称E'为G的边割集.若(e)为边割集,则称e为割边或桥。
5.4
最短路径:u, v 之间权最小的通路。
标号法
项目网络图:项目网络图:表示项目的活动之间前后顺序一致的带权有向图,边表示活动,边的权是活动的完成时间,顶点表示事顶(项目的开始和结束、活动的开始和结束).要求:1)有一个始点(入度为D)和一个终点(出度为D).
(2)两点之间只能有一条边,可以引入虚活动。
(3)没有回路
关键路径:项目网络图从始点到终点的最长路径。
事项的最早开始时间MAX(ES)
事项的最晚完成时间MIN(LF)
着色:定义设无向图G无环,对G的每个顶点涂一种颜色使相邻的顶点涂不同的颜色,称为图G的一种点着色,简称着色
PS:颜色最多四种。
难点:项目网络图的绘制和应用,求最短路径
原因:题难度大,做题步骤复杂,一步错步步错。
解决方法:看懂网络图,结合实际生活明白数值怎么出来的。
第七章树
树叶:树中度数为1的顶点。
最优二叉树:Huffman算法:
给定实数w, w,…, t,
②作七片树叶,分别以w, w2,…,w为权
③在所有入度为 0的顶点(不一定是树叶)中选出两个权最小的顶点,添加一个新分支
点,以这2个顶点为儿子,其权等于这2个儿子的权之和.
④重复②,直到只有 1个入度为 0的顶点为止.W(T)等于所有分支点的权之和
二元前缀码:只有两个符号的前缀码。
设要传输的电文中含有七个字符,字符a出现的频率为p,它的编码的长度为1,那么100个字符的电文的编码的期望长度是1001p .称编码期望长度最小
的2元前缀码为最佳2元前缀码
难点:最优二叉树的求解,算二元前缀码
原因:以前从没接触过,没有相关概念。
解决方法:了解它,掌握它,战胜它。