回来重新看——发现图片全寄掉了——乐，有机会重写吧

离散数学

[TOC]

数理逻辑

命题逻辑

命题

（1）原子命题（不包含任何联结词）；（2）复合命题；

命题标识符

（A，Ai，[12]）（1）确定—>命题常量；（2）不确定—>命题变元（不是命题）（标题原子命题，可称为原子变元）；

联结词

联结词
合取（可兼或）	∧	析取	∨
否定	¬	（一元运算）
条件（前件/前提，后件）	⇒	双条件	↔/iff
不可间或/异或	⊽
条件否定
与非		或非

优先顺序：否定，合取，析取，条件，双条件；

表1-4.8

命题定律	表达式	序号
对合律	¬¬P⇔P	1
幂等律	P∨P⇔P,P∧P⇔P	2
结合律	(P∨Q)∨R⇔P∨(Q∨R)	3
交换律	P∨Q⇔Q∨P	4
分配律	P∨(Q∧R)⇔(P∨Q)∧(P∨R)	5
吸收律	(P∨Q)∧P⇔P;(P∧Q)∨P⇔P	6
德摩根律	¬(P∨Q)⇔¬P∧¬Q	7
同一律	P∨F⇔P	8
零律	P∨T⇔T	9
否定律	P∨¬P⇔T;P∧¬P⇔F	10

命题公式：

重言式/永真式；矛盾式/永假式；可满足式；

判断方法：（1）真值表；（2）等值演算法；

蕴含式（⇒）：

要证P⇒Q，即证P—>Q是重言式，或证其逆反式是重言式即可。

对偶式：

反过来

泛式：（合取范式，析取范式，主范式（小项/布尔合取）（主析取范式）（大项）（主合取范式））

谓词逻辑

客体/个体：

可以独立存在的具体事务或抽象概念

客体常元：

表示具体或特定的客体abc

客体变元：

表示抽象或泛指的客体xyz

谓词

谓词表达式

个体域（在命题函数中，命题变元的论述范围）

全总个体域（个体域综合在一起，作为论述范围的域，称为全总个体域）

量词（全称，特称

特性谓词（

谓词公式：

变元约束（指导变元/作用变元，作用域/量词辖域，约束变元，自由变元，代入规则

约束换辖域，自由全代换

谓词演算等价式与蕴含式

量词辖域的扩张和收缩

量词与命题联结词之间的一些等价式

前束范式

前束合取范式

前束析取范式

谓词演算的推理理论

在谓词逻辑中，如果A1∧A2∧…∧An→B是逻辑有效式，则称B是A1, A2, …，An的有效结论，记作A1∧A2∧…∧AnBAB 当且仅当 AB是重言式

集合论

集合与关系

集合分类

集合悖论与公理：

外延公理（相等），空集存在公理，子集公理模式

交集，并集，差运算（相对补），绝对补运算，对称差运算，幂运算，

证明：

二元关系

序偶

笛卡尔积

空关系，全域关系，恒等关系

关系运算：

dom定义域，ran值域，fld=dom U ran域；

逆运算

每个序偶交换位置，逆关系

交叉划分与加细

等价关系，商集

等价：对称

偏序：反对称性

盖住：2，4，8，8没盖住2

全序关系

函数

代数系统

代数结构

闭运算：运算结果在原来的集合R种

n元运算：从A^n到B的映射

代数系统：一个非空集合A连同若干个定义在该集合上的运算所组成的系统就称为一个代数系统，记作：<A,f1,…fk>.

吸收律

运算等幂：如果对于任意的x属于A，都有x*x=x，则称运算*是等幂的或称满足等幂律。

幺元，零元：（幺元e，零元；幺元不一定是1，也可能是0；

逆元：b*a=e

且每个元素的逆元是唯一的

难以理解：

类群：（广群》半群》独异点》群）

广群：（非空，二元，封闭）

半群：封闭、可结合、eg：

子半群：<S,*>是半群，<B,*>是半群，且B属于S，则后者为前者的子半群

独异点：含有幺元的半群称为独异点（封闭、可结合、有幺元）

含有独异点的运算表种任何两行或者两列都是不相同的

群：封闭、可结合、幺元e、每个元素都存在它的逆元

不可能有零元，唯一等幂元-幺元e、满足消去律、a*x=b、每行/列都是G的置换

有限群、无限群：

置换：一一对应

等幂元： 代数系统<G,*>中，a属于G，a*a=a，称a为等幂元；

群中除幺元e外，不可能有任何别的等幂元

平凡子群：S={e}或者S=G

阿贝尔群/交换群：

循环群：设<G,*>若在G中存在一个元素a **使得G中的任意元素都由a的幂组成，则称该群为循环群，元素a称为循环群G生成元.

群中元素的阶：设a为群G的一个元素，使得a^n=e的最小正整数n，叫做元素a的阶

如果这样 的n不存在，则称a的阶为无限/称是0；

元素a的阶常用|a|表示

有限群中每个元素的阶均有限

任何一个循环群必是阿贝尔群；****

陪集


看不懂！

关系是序偶的集合。

序偶：

次序不能随意调换

关系及其表示：

关系是序偶得集合，xRy，xRy

另外

质数阶群必是循环群

证明循环群： - 定义 - 生成一个 - 同构思想

格与布尔代数

图论

概念：

无向图，有向图；点，边，特殊的图；顶点的度；补图与自补图；子图，生成子图和导出子图；图的同构

路：

• 回路，长度；
• 边不同 - 迹；结点不同 - 通路/圈
• 两点间的最短路的长度：两点间的距离
• 图中任意两点间的距离的最大值 ，称为图的直径

无向图连通性：

两结点连通关系是一个等价关系（自反对称，传递

可以划分出若干个等价类

每个等价类中的结点中都是互相连通的，而等价类之间的结点互不连通

每一个等价类的点导出子图，称为原图的一个连通分支，图的连通分支数记为W（G）

只有一个连通分支的图，称为连通图

连通程度：

点割集 割点

点连通度（或连通度）

• G不完全图，min{|V1||V1是G的点割集}；
• G完全图：p-1；
• G不连通，k=0；

边割集 割边（桥

边连通度

• 非平凡图，min
• 平凡图 0
• 不连通，0

割点每条路都得经过

有向图的连通性

可达 相互可达

弱连通 基图为连通图

单连通 任意两点可达

强连通：任意两点相互可达

强连通分支 弱连通分支 （子图们）

连通性计算：割点的应用及求法

结构洞（割点是结构洞的典型情况）

Tarjan算法

index = 0          // 全局索引计数器
stack = []         // 存储当前访问路径上的所有节点
scc_list = []      // 存储所有强连通分量

function tarjan(u):
    u.index = index        // 为当前节点设置全局索引
    u.lowlink = index      // 初始时，当前节点的 lowlink 值等于索引值
    index = index + 1      // 索引值自增

    stack.push(u)          // 将当前节点压入栈中

    for each v in neighbors of u:
        if v.index is undefined:       // 如果 v 还没有被访问过
            tarjan(v)                  // 递归访问 v
            u.lowlink = min(u.lowlink, v.lowlink)   // 更新当前节点的 lowlink 值
        else if v is in stack:         // 如果 v 在当前访问路径上
            u.lowlink = min(u.lowlink, v.index)     // 更新当前节点的 lowlink 值

    if u.lowlink == u.index:          // 如果当前节点是强连通分量的根节点
        scc = []                      // 新建一个强连通分量
        while True:
            v = stack.pop()           // 从栈中弹出节点
            scc.add(v)                // 将节点加入当前强连通分量
            if v == u:
                break               // 找到当前强连通分量中的所有节点
        scc_list.add(scc)            // 将当前强连通分量加入列表中

领接矩阵：

求n步从a到b的方法数（求指定长度的路的数目

关联矩阵

关联矩阵的应用：结点的合并（边收缩）

r阶连通图的关联矩阵的秩为r-1

欧拉图

欧拉路：通过途中所有边一次且仅一次的迹

半欧拉图：具有欧拉路而无欧拉回路的图

欧拉回路：通过途中所有边一次且仅一次的闭迹

欧拉图：具有欧拉回路的图

判断：

• 所有顶点的度数都是偶数（边不重复
• 有且仅有两个奇度结点（一个出度大一一个入度大一）
• 由若干个不重边的圈组成
• Fleury算法：
  • 任取一个起点v
  • 设已经过的边的集合为E‘，则按照以下原则选择下一条边e：

哈密顿图

哈密尔顿路：一条经过G的每一个结点恰好一次的路

半哈密尔顿图：具有哈密尔顿路的图

哈密尔顿回路：一条经过图G的每一个结点恰好一次的回路

哈密尔顿图：具有哈密尔顿回路的图

• 若G具有哈密尔顿回路，则对于结点集V的每一个非空子集S均有W（G-S）<=|S|成立，其中W（G-S）是G-S中连通分支数
• 哈密尔顿图的必要条件
• 逆否命题是判断非哈密尔顿图的充分条件
• 半哈密尔顿图充分条件：对于n阶图，如果G的每一对结点的度数之和都不小于n-1,那么G中有一条哈密尔顿通路
• 哈密尔顿图充分条件：对于n阶图，如果G的每一对结点的度数之和不小于n，那么G为一哈密尔顿图

平面图：

• 所有面的次数之和为边数的二倍
• v-e+r=p+1（vertex，edge，面，连通分支数）
• v>=3,e<=3v-6;

同胚：

插入 删除

库拉图斯基定理

图的着色：

对偶图

韦尔奇着色法

对于v个结点，e条边的简单连通平面图，若v>=3，则e<=3v-6

G为至少3个结点的连通平面图，G中必有一个结点u，deg（u）<=5

树

数，森林，平凡树，树叶，分支点，

生成树，树枝，弦

• 生成树：破圈法，避圈法

• 找到所有生成树：利用关联矩阵穷举连通图中的生成树

• Kruskal算法

二叉树：中序遍历，前序遍历，后序遍历

中缀，前缀（波兰）后缀（逆波兰）

Huffman算法

重点：（代数系统后面）