离散数学图算法总结

1 / 48 离散数学图算法总结 离散数学课程总结 一、 对该课程的理解： 离散数学是现代数学的一个重要分支，是计算机科学专业的专业主干课之一，课程结合计算科学的特 点研究离散对象和相互关系，对提高学生的抽象思维与逻辑推理能力有很重要的作用。它以研究离散量的结构和相互关系为主要目标，在计算机科学的数据结构、操作系统等有广泛的应用。它是许多数学科目的统称。它的内容包括了数理逻辑、集合论、抽象代数、图论、排列组合、形式语言及自动机等。该门课概念较多、论性较强，定理比较多，学习起来难免有点枯燥乏味。同时也因为概念比较多所以课程连接比较混乱，概念不清，张冠李戴等问题屡屡出现。 第一章主要是介绍命题逻辑的基本概念。其中包括命题与联结词；命题公式及其赋值。这张可以说是基础中的基础，为后面打下基础。通过各种联结词将命题连接起来构成推理，从而可以判断其真假。 2 / 48 第二章主要是介绍命题逻辑等值演算。其中包括等值式；析取范式与合取范式；联结词的完备集；可满足性问题与消解集。学习完了第一章的命题逻辑之后，就开始在此基础上扩充知识点。在这章中重点有运用等值演算法或者真值表法去求解析取范式和合取范式以及等值式。 26个等值式中我们要特别需要记住的有分配 律，德摩根律，蕴涵等值式，等价等值式，这些等值式贯穿于后面几章的知识。其后就是求主析取范式和主合取范式了 第三章主要是介绍命题逻辑的推理理论。其中包括推理的形式结构和自然推理系统 P。这张将又会介绍更多的等值式。当然，学以致用在本章得以诠释，同时这也是考试的一个重点。 第四章的知识点逐渐深入，由浅及深，主要是介绍一阶逻辑基本概念。也就是一阶逻辑命题符号化，一阶逻辑公式及其解释。 第五 章与第四章息息相关，主要是介绍一阶逻辑等值演算与推理。包括一阶逻辑等值式与置换规则，前束范式，推理理3 / 48 论。运用等值式及各种规则求一阶逻辑的翻译或者符号化。 第六章主要是介绍集合代数。包括有集合的基本概念，集合的运算，集合恒等式。这章主要是围绕集合而展开学习的，内容简单易懂。 第七章主要 是介绍二元关系。其中包括有序对与笛卡尔积，二元关系，关系的运算，关系的性质，关系的闭包，等价关系与划分，偏序关系。这章内容比较重要，特别是后面的五种关系及闭包。了解了有序对知识点后，在此基础上继续学习五种关系：自反性，反自反性，对称性，反对称性，传递性，并且熟悉他们的证明过程。关系的闭包， 等价关系，偏序关系是考试的另一个重点，需重点掌握。 第八章主要是介绍函数。包括函数的定义和性质的掌握以及复合函数，反函数。 第九章和第十章主要是介绍代数系统及群与环。可以这样总结：二元运算及其性质 -?代数系统 -?半群 -?独异点-?群。与此同时，我们也要掌握群，半群的 相关证明。 4 / 48 第十四章和第十五章主要是介绍图的基本概念以及欧拉图，哈密顿图。在第十四章中，我们初步学习图的相关知识，同时还有图的矩阵表示和运算。这也是一重点。至于欧拉图及哈密顿图，我们要学习如何判断是否为欧拉图及哈密顿图，要求不是很多，了解就好。 二、对课程的意见和建议： 可以适当的多添加几节离散数学课，老师也可以在课堂上适当的添加一些在其他计算机学科中应用的知识点。对离散数学中的一些富有历史趣味的有关离散的历史故事也可以提一提，增加课堂气氛，减少课堂的乏味。 三 、 对老师德意见和建议： 就我们的离散老师而言是非常的一个老师，她在课堂上总是充满热情，时不时的穿插一些笑话缓和课堂气氛。而且每次上课她都是面带微笑，让人产生一种亲切感，我认为对这样 的老师实在是没有什么意见和建议了，如果说有，那就是希望她以后可以多开一些习题课来巩固我们学习过的知识。 5 / 48 总结 离散数学知识点 第二章 命题逻辑 1. ，前键为真，后键为假才为假；，相同为真，不同为假； 2.主析取范式：极小项 (m)之和；主合取范式：极大项 (M)之积； 3.求极小项时，命题变元的肯定为 1，否定为 0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按 P,Q,R的顺序依次写； 6.真值表中值为 1 的项为极小项，值为 0 的项为极大项； 个变元共有 2n个极小项或极大项，这 2n为 (02n-1)刚好为化简完后的主析取加主合取； 6 / 48 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法 (=)：真值表法；分析法 (假定前键为真 推出后键为真，假定前键为假推出后键也为假 ) 10.命题逻辑的推理演算方法： P规则， T规则 真值表法； 直接证法； 归谬法； 附加前提法； 第三章 谓词逻辑 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章 集合 ，表示自然数集， 1,2,3?，不包括 0； 2.基：集合 A中不同元素的个数， |A|； 3.幂集：给定集合 A，以集合 A 的所有子集为元素组成的集合， P(A)； 7 / 48 4.若集合 A 有 n 个元素，幂集 P(A)有 2 个元素，|P(A)|=2|A|=2； 5.集合的分划： (等价关系 ) 每一个分划都是由集合 A的几个子集构成的集合； 这几个子集相交为空，相并为全 (A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章 关系 1.若集合 A有 m个元素，集合 B有 n 个元素，则笛卡尔 AB的基数为 mn， A到 B 上可以定义 2 种不同的关系； 2.若集合 A 有 n 个元素，则 |AA|=n2 ， A 上有 2n 个不同的8 / 48 关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递 性； 2nnmn 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域 (domR)：所有元素 x组成的集合； 后域 (ranR)：所有元素 y 组成的集合； 5.自反闭包： r(R)=RUIx; 对称闭包： s(R)=RUR-1; 传递 闭包： t(R)=RURURU? 6.等价关系：集合 A 上的二元关系 R 满足自反性，对称性和传递性，则 R称为等价关系； 7.偏序关系：集合 A 上的关系 R满足自反性，反对称性和传9 / 48 递性，则称 R 是 A 上的一个偏序关系； =|x,y 属于 A， y 盖住 x； 9.极小元：集合 A 中没有比它更小的元素 (若存在可能不唯一 )； 极大元：集合 A 中没有比它更大的元素 (若存在可能不唯一 )； 最小元：比集合 A 中任何其他元素都小 (若存在就一定唯一 )； 最大元：比集合 A中任何其他元素都大 (若存在就一定唯一 )； 10.前提： B 是 A的子集 上界： A 中的某个元素比 B 中任意元素都大，称这个元素是B 的上界 (若存在，可能不唯一 )； 下界： A 中的某个元素比 B 中任意元素都小，称这个元素是B 的下界 (若存在，可能不唯一 )； 上确界：最小的上界 (若存在就一定唯一 )； 下确界：最大的下界 (若存在就一定唯一 )； 23 10 / 48 第六章 函数 1.若 |X|=m,|Y|=n,则从 X到 Y 有 2种不同的关系，有 n 种不同的函数； 2.在一个有 n 个元素的集合上，可以有 2n 种不同的关系，有 nn种不同的函数，有 n!种不同的双射； 3.若 |X|=m,|Y|=n，且 m 4.单射： f:X-Y，对任意 x1,x2属于 X,且 x1x2 ，若 f(x1)f(x2) ； 满射： f:X-Y，对值域中任意一个元素 y 在前域中都有一个或多个元素对应； 双射： f:X-Y，若 f 既是单射又是满射，则 f是双射； 5.复合函数： fog=g(f(x); 6.设函数 f:A-B， g:B-C，那么 如果 f,g都是单射，则 fog也是单射； 11 / 48 如果 f,g都是满射，则 fog也是满射； 如果 f,g都是双射，则 fog也是双射； 如果 fog是双射，则 f 是单射， g 是满射； 第七章 代数系统 1.二元运算：集合 A 上的二元运算就是 A2到 A的映射； 2. 集合 A上可定义的二元运算个数就是从 AA 到 A上的映射的个数，即从从 AA 到 A 上函数的个数，若 |A|=2,则集合 A 上的二元运算的 m2mnm 个数为 22*2=24=16 种； 3. 判断二元运算的性质方法： 封闭性：运算表内只有所给元素； 交换律：主对角线两边元素对称相等； 12 / 48 幂等律：主对角线上每个元素与所在行列表头元素相同； 有幺元 ：元素所对应的行和列的元素依次与运算表的行和列相同； 有 零 元 ： 元 素 所 对 应 的 行 和 列 的 元 1.广群的性质：封闭性； 半群的性质：封闭性，结合律； 含幺半群 (独异点 )：封闭性，结合律，有幺元； 群的性质：封闭性，结合律，有幺元，有逆元； 2.群没有零元； 3.阿贝尔群 (交换群 )：封闭性，结合律，有幺元，有逆元，交换律； 4.循环群中幺元不能是生成元； 5.任何一个循环群必定是阿贝尔群； 命题：称能判断真假的陈述句为命题。 命题公式：若在复13 / 48 合命题中， p、 q、 r 等不仅可以代表命题常项，还可以代表命题变项，这样的复 合命题形式称为命题公式。 命题的赋值：设 A 为一命题公式， p ,p ,p 为出现在 A 中的所有命题变项。给 p ,p ,p 指定一组真值，称为对 A 的一个赋值或解释。若指定的一组值使 A 的值为真，则称成真赋值。 真 值 表 ： 含 n 个 命 题 变 项 的 命 题 公 式 ， 共 有 214 / 48 组赋值。将命题公式 A在所有赋值下的取值情况列成表，称为 A 的真值表。 命题公式的类型：若 A 在它的各种赋值下均取值为真，则称 A 为重言式或永真式。 若 A 在它的赋值下取值均为假，则称 A为矛盾式或永假式。 若 A 至少存在一组赋值是成真赋值，则 A 是可满足式。 主析取范式：设命题公式 A 中含 n个命题变项，如果 A 得析取范式中的简单合取式全是极小项，则称该析取范式为 A的主析取范式。 主合取范式：设命题公式 A中含 n个命题变项，如果 A得析取范式中的简单合析式全是极大项，则称该析取范式为 A 的主析取范式。 命题的等值式：设 A、 B为两命题公式，若等价式 A?B是重言式，则 称 A 与 B是等值的，记作AB。 约束变元和自由变元：在合式公式 ?x A 和 ?x A 中，称 x 为指导变项，称 A 为相应量词的辖域， x称为约束变元，x 的出现称为约束出现， A 中其他出现称为自由出现。 一阶逻辑等值式：设 A， B 是一阶逻辑中任意的两公式，若 A?B为逻辑有效式，则称 A 与 B 是等值的，记作 AB，称 AB 为等值式。 前束范式：设 A 为一谓词公式，若 A 具有如下形式Q1x1Q2x2QkxkB ，称 A为前束范式。 集合的基本运算：并、 交、差、相对补和对称差运算。 笛卡尔积：设 A 和 B 为集合，用 A 中元素为第一元素，用 B 中元素为 第二元素构成有15 / 48 序对组成的集合称为 A 和 B 的笛卡尔积，记为 AB 。 二元关系：如果一个集合 R为空集或者它的元素都是有序对，则称集合 R 是一个二元关系。 特殊关系：、空关系： 全域关系： EA= | xA yA = AA 恒等关系： IA= | xA 小于等于关系： LA=| x, yAxyA ,A ? R 整除关系： R? =| x， y x ? y , 是集合族 二元关系的运算：设 R 是二元关系， R中所有有序对的第一元素构成的集合称为 R的定义域 domR = x | ?y R 中所有有序对的第二元素构成的集合称为 R的值域 ranR = y | ?x R 的定义域和值域的并集称为 R的域 fldR= domR ranR 二元关系的性质：自反性，反自反性，对称性，反对称性，传递性。 等价关系：如果集合 A 上的二元关系 R 是自反的，对称的和传递的，那么称 R是等价关系。设 R 是 A 上的等价16 / 48 关系， x , y 是 A 的任意元素，记 作 x y。 等价类：设 R是 A 上的等价关系，对任意的 ?xA ，令 xR= y | yA x R y ，称 xR为 x 关于 R的等价类。 偏序关系：设 R是集合 A上的二元关系，如果 R是自反的，反对称的和传递的，那么称 R 为 A 上的偏序，记作 ；称序偶为偏序集合。 函数的性质：设 f: A?B， 若 ranf = B，则称 f 是满射的。 若 ?y? ranf 都存在唯一的 x ?A 使得 f(x)=y,则称 f 是单射的。 若 f 既是满射又是单射的，则称 f 是双射的。 无向图：是一个有序的二元组，记作 G，其中： (1) V? 称为顶点集，其元素称为顶点或结点。 (2) E 为边集，它是无序积 V&V 的多重子集，其元素称为无向边，简称边。 有向图：是一个有序的二元组 ,记作 D,其中 (1) V同无向图。 (2) E为边集，它是笛卡尔积 V?V 的多重17 / 48 子集，其元素称为有向边。 设 G=是一个无向图或有向图。 有限图：若 V, E是有限集，则称 G为有限图。 ：若 | V |=n，称 G 为 n阶图。 零图：若 | E |=0，称 G 为零图 ,当 | V |=1 时，称 G 为平凡图。 基图：将有向图变为无向图得到的新图，称为有向图的基图。 图的同构：在用图形表示图时 ，由于顶点的位置不同，边的形状不同，同一个事物之间的关系可以用不同的图表示，这样的图称为图同构。 带权图：在处理有关图的实际问题时，往往有值的存在，一般这个值成为权值，带权值的图称为带权图或赋权图。 连通图：若无向图是平凡图，或图中任意两个顶点都是连通的，则称 G 是连通图。否则称为非连通图。设 D 是一个有向图，如果 D 的基图是连通图，则称 D是弱连通图，若 D 中任意两个顶点至少一个可达另一个，则称 D 是单向连通图。若 D中任意两个顶点是相互可达的，则称 D 是强连通图。 欧拉图：通过图中所有边一次且仅一次并且通过所有定点的 通路，称为欧拉通路。存在欧拉回路的图称为欧拉图。 哈密顿图：经过图中每个顶点一次且仅一次的通路，称为哈密顿通路，存在哈密顿回路的图称为哈密顿图。 平面图：一个图 G 如果能以这样的方式画在平面上：出定点处外没有变交叉出现，则称 G 为平面图。画出的没有边交叉出现的图称为 G的一个平面嵌入。 二部图：若无向图 G= V, E的18 / 48 顶点集合 V可以划分成两个子集 V1和 V 2，使 G中的任何一条边的两个端点分别属于 V1 和 V2，则称 G 为二部图。二部图可记为 G = , V1 和 V 2称为互补顶点子集。 树的定义：连通无回路的无向图称为 无向树，简称树，常用 T 表示树。平凡图称为平凡树。若无向图 G至少有两个连通分支，每个连通都是树，则称 G 为森林。在无向图中，悬挂顶点称为树叶，度数大于或等于 2的顶点称为分支点。 树的性质：性质 1、设 G=是 n阶 m 条边的无向图，则下面各命题是等价的： G是树 G中任意两个顶点之间存在唯一的路径 G中无回路且m=n-1. G 是连通的且 m=n-1. G 是连通的且 G 中任何边均为桥。 G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 性质 2、设 T 是 n 阶非平凡的无向树，则 T中至少有两片树叶。 证：设 T 有 x 片树叶，由握手定理及性质 1 可知，2(n-1)=d(vi)x+2(n -x)由上式解出 x2. 最小生成树：设 T 是无向图 G 的子图并且为树，则称 T 为 G 的树。若T 是 G 的树且为生成子图，则称 T 是 G 的生成树。设 T 是 G的生成树。 eE(G) ，若 eE(T) ，则称 e 为 T的树枝，否则19 / 48 称 e 为 T 的弦。并称导出子图 GE(G)-E(T)为 T的余树，记作 T。 最优二元树：设 2 叉树 T有 t 片树叶 v1,v2,vt ，权分别为 w1,w2,wt ，称 W(t)=wil(vi)为 T的权，其中 l(vi)是 vi 的层数。在所有有 t 片树叶，带权 w1,w2,wt 的 2叉树中，权最小的 2 叉树称为最优 2 叉树。 最佳前缀码：利用 Huffman算法求最优 2叉树，由最优 2叉树产生的前缀码称为最佳前 缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。 蕴含式推理 集合恒等式： P61 幂等律： AA=A ； AA=A 结合律： (AB)C=A(BC) ； (AB)C=A(BC) 交换律： AB=BA ； AB=BA 分配律： A(BC)=(AB)(AC) ；A(BC)=(AB)(AC) 20 / 48 同一律： A? =A ； AE=A 零 律： AE =A ； A? = ? 排中律： AA=E 矛盾律： AA =? 吸收律： A(AB)=A ； A (AB)=A 德 摩 根 定 律 ： A-(BC)=(A -B)(A -C) ；A-(BC)=(A -B)(A -C) (BC)= BC ； (BC)= BC ； ?=E； E=? 双重否定律： d 无向 图的关联矩阵：设无向图 G=, V=v1,v2,vn, E=e1,e2,em ，令 mij为顶点 vi与边的关联次数，则称 n? m为 G的关联矩阵。记为 M(G)。 有向图的关联矩阵：设无向图 D=, V=v1,v2,vn, E=e1,e2,em ， 21 / 48 1, vi 是 ej的始点 mij = 0, vi 与 ej不关联 -1， vi是 ej的终点 则称 n? m 为 D的关联矩阵。记为 M(D) 。 第一章 1、只有努力学习，认真复习，才能取得好成绩。 解： P ： 努力学习。 Q ：认真复习。 R：取得好成绩。 ?R =?R = R 2、范式 22 / 48 例：求公式 ）的和取范式 原式 = ） ） = = = 第二章 1、公理 证明 ） 公理 用 代入 ） ） 公理 23 / 48 ） ） ） ） ） 对 用分离规则 证明 ） 3、例 证明 公理 14 P 用 ? P， Q用 ?代入 ? ? P P 公理 15 加头规则用 式得 传递规则 P ? ? P 定理 Q ? ? Q P 用 Q 代入 24 / 48 加头规则用 式得 传递规则 4.假设法 例 证明 ） R ） P 假设 P Q 假设 P 公理 8 Q 公理 9 P 分离规则 Q 分离规则 Q R 分离规则 25 / 48 R 分离规则 由假设推理过程的定义知 P ， P Q R 由推理定理知 ） R ） 第三章 1、谓词演算公式 例：把下列语句翻译为谓词演算公式 注意： ?x 后的主联结词用 ； ?x后的主联结词用 。 并非 “ 人不为己，天诛地灭 ” 26 / 48 我为人人，人人为我。 有些学生喜欢所有的老师。 有些作家没写过小说。 令表示为人；集合名词 表示为； 表示诛； 表示灭； 表示天，表示地； 则原句译为： ? ?x ? ） ） 27 / 48 我为人人，人人为我。 令表示为人；集合名词 表示为； a 表示我； 则原句译为： ?x ） ） 有些学生喜欢所有的老师。 令 S 表示为学生；集合名词 L 表示喜欢； T 表示 e为老师；集合名词 则原句译为： 28 / 48 ?x表示为作家；集合名词 W 表示写； N 表示 e为小说；集合名词 则原句译为： ?x (?zY(z) Z(x) ) ?x ?y ?z(X(x,y,z) (?uY(u,x) ?xW(y,x) ? ?x ? ） ） 解： 消去 “” 、 “?” ?x (?zY(z) Z(x) ) 29 / 48 否定深入 ?x (?zY(z) Z(x) ) 前移量词 ?x ?y ?z (Y(z) Z(x) ) 化为 SKOLEM标准形 ?y (Y(f(y) Z(a) ) 解： 消去 “” 、 “?” ?x ?y ?z(X(x,y,z) (?(?uY(u,x) ?xW(y,x) 否定深入 ?x ?y ?z(X(x,y,z) ( ? u ? Y(u,x) ?xW(y,x) 30 / 48 改名 ?x ?y ?z(X(x,y,z) ( ? u ? Y(u,x) ?vW(y,v) 前移量词 ?x ?y ?z ? u ?v(X(x,y,z) (? Y(u,x)W(y,v) 化为 SKOLEM标准形 ?y ?z ? u (X(a,y,z) (? Y(u,a)W(y,f(y,z,u) 第四章 1、例：已知知识： 桌子上的每本书均是杰作； 写出杰作的人是天才； 某个不出名的人写了桌上某本书。 31 / 48 结论 某个不出名的人是天才。 解：先把知识翻译为符号公式： 令 A(e)表示 “e 为书 ” ； B(e)表示 “e 为杰作 ” ； C(e)表示 “e 为天才 ” ； D(e)表示 “e 出名 ” ； P(e)表示 “e 为人 ” ； W(e1,e2)表示 “e1 写了 e2” 。 ?x (A(x) B(x) ?x ?y(P(x) B(y ) W(x,y) C(x) 32 / 48 ?x ?y(P(x) A(y) ?D(x) W(x,y) 结论： ?x (P(x) ?D(x) C(x) 1.归 结法 ? A(x1) B(x1) ? P(x2) ? B(y) ? W(x2,y) C(x2) P(a) A(b) ?D(a) W(a,b) ? P(x3) D(x3) ? C(x 3) 结论的否定 ? P(a) ? C(a) a/x3 33 / 48 归结 ? C(a) 归结 ? P(a) ? B(y) ? W(a,y) a/x2 归结 ? B(y) ? W(a,y) 归结 ? A(y) ? W(a,y) y/x1 归结 ? W(a,b) b/y 归结 归结 2.假设推理法 34 / 48 ?x (A(x) B(x) 假设 ?x ?y(P( x) B(y) W(x,y) C(x) 假设 ?x ?y(P(x) A(y) ?D(x) W(x,y) 假设 P(a) A(b) ?D(a) W(a,b) 额外假设 (P(a) ?D(a) ) (A(b)W(a,b) (P(a) ?D(a) 公理 8 (P(a) ?D(a) ) (A(b)W(a,b) (A(b) W(a,b) 公理 9 P(a) ?D(a) 分离 (4)(5) 35 / 48 A(b) W(a,b) 分离 (4)(6) (P(a) ?D(a) P(a) 公理 8 (A(b)W(a,b) A(b) 公理 8 (A(b)W(a,b) W(a,b) 公理 9 P(a) 分离 (7)(9) A(b) 分离 (8)(10) W(a,b) 分离 (8)(11) A(b) B(b) 全称量词消去规则 (1) A(b) B(b) 全称量词消去规则 (1) B(b) 分离 (1)(15) 36 / 48 P(a) (B(b) (P(a) B(b) ) 公理 10 B(b) (P(a) B(b ) ) 分 离 (12)(17) P(a) B(b) 分离 (16)(18) (P(a) B(b) ( W(a,b) (P(a) B(b) ) W(a,b) ) 公理 10 (21) W(a,b) (P(a) B(b) ) W(a,b) 分离 (19)(20) (22) (P(a) B(b) ) W(a,b) 分离 (14)(21) 37 / 48 (23) (P(a) B(b) ) W(a,b) C(a) 全称量词消去规则 (2) (24) C(a) 分离 (22)(23) (25) (P(a) ?D(a) ) (C(a) (P(a) ?D(a) ) C(a) ) 公理 10 (26) C(a) (P(a) ?D(a) ) C(a) ) 分离 (7)(25) (27) P(a) ?D(a) C(a) 分离 (24)(26) (28) P(a) ?D(a) C(a) ?x (P(x) ?D(x) C(x) ) 公理 21 (29) ?x (P(x) ?D(x) C(x) ) 分离 38 / 48 (27)(28) 由存在推理定理得 : ?x (A(x) B(x) ;?x ?y(P(x) B(y) W(x,y) C(x) ; ?x ?y(P(x) A(y) ?D(x) W(x,y) ?x (P(x) ?D(x) C(x) ) 由假设推理定理得： ?x (P(x) ?D(x) C(x) ) 3.霍恩子句逻辑程序 B(x1) A(x1) C(x) (P(x) B(y) W(x,y) P(a) 39 / 48 离散数学章节总结 第一章 命题逻 辑 1.逻辑运算 1.否定 :Negation ? NOT 2.交 :Conjunction ? AND 3.并 :Disjunction ? OR 4.蕴含 :Implication ? IMPLIES 5. Biconditional ? IFF ? XOR 2.逆 /否 /逆否 40 / 48 1.逆 :converse 2.否 :inverse 3.逆否 :conytrapositive 3.问题的一致性 逻辑等价 q 等价于 ?p?q 等价于 ? q?p 2. p?q 等价于 ?pq p?q 等价于 ?( p?q) 3.(pq) ? (pr) 等价于 p(q?r) (pr) ? (qr) 等价于 (p?q)r (pr) ? (qr) 等价于 (p?q) r 41 / 48 4.证明等 价 : 真值表 逻辑符号证明 找反例 (假设 左为假 右必为假 假设右为假 左必为假 ) 谓词逻辑 1.量词 ?存在 ?任意 量词顺序不能随机改变 不全为真 :?(p1?p2?pn) ? (?p1?p2?pn) ? ?x P(x ) ? ?x ?P(x ) 没有一个为真 :?(p1?p2?pn) ? (?p1?p2?pn) ? ?x P(x ) ? ?x ?P(x ) 推理 42 / 48 证明 1.证明方法 :直接证明 间接证明 反证 列举 证明 (列举所有情况 ) 构造证明 (构造出满足结论的元素 ) 2.证明步骤 :正向证明 反向证明 第二章 集合及运算 1.特殊集合 : R Q Z 无穷 /有限集 2.集合表述方法 : 列举法 描述法 图表法 3.集合运算 : 交 /并 /补 /差 /取子集 P(S)/元素数 |S|/乘积PQ/ A?B?A?B?A?A?A?Aiii?1nnA?Xi?1A?X 4.证明集合相等 :1.证明互为子集 2.从属表 3.逻辑证明 43 / 48 函数 ?1.函数的定义 2.术语：定义域，值域，象，原象，范围， (a)/f(A) 第五章 序、归纳 1.序：在某种关系下存在最小元素则为 well-ordered 2.第一数学归纳法： basic step P(C)成立 and inductive step