5个联结词的优先级顺序

1. 合式公式 (命题公式, 公式)

2. 24个基本等值式 等值演算

3. 公式A的析取范式 & 公式A的合取范式

   求析取范式 & 合取范式:
   主要就是将其中的蕴含和等值全部化掉就好!
   而后找到其中的析取范式 & 合取范式的组合!

4. 1. 先求析取范式（合取范式）

   2. 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若幹个极小项的析 取（极大项的合取）
      注意这里是单独拿出来化, 通常要使用无中生友大法

   3. 极小项（极大项）用名称mi（Mi）表示并按角标从小箌大顺序排序.

5. 推理定律是一定正确的推理, 就这么来理解!

6. 3种不同的证明方法, 需要明确要如何证明:

命题逻辑与一阶逻辑的区别, 就是一阶逻辑将命题逻辑中的个体域谓词分开来, 仅此而已

1. 合式公式(谓词公式 或 公式)

? 命题的两种形式符号化:
? 即用两种不同的两次修饰的命题
? 通常是根據题目推出其中一种, 而后在使用上头的辖域收缩&扩张来转化为另一种

这里说明一下 蕴含 & 合取 的区别:
蕴含: 就和前头的推理一样, 是如果A则B
合取: A苴B , 和蕴含完全不一样
所以这里通常是先推出蕴含 , 而后在转化为合取

1. 注意这里的i的取值范围

   注意: 蕴含 & 等价 中的个体变项不是同一个, 即使他们嘚符号相同

1. 限制: 相当于限制的定义域
   

2. 自反, 反自反, 对称, 反对称, 传递

   注意: 没有体现出定义中的内容的也算, 只要不违反定义的都算!:
   

3. x关于R的等价类(等价类)
   

4. 满射 & 单射 & 双射 的判定

   构造从A 到 B的双射函数
   

   各种和高数中相同的函数:
   

5. 反函数 & 单射双射满射

   函数复合与反函数的计算

1. 满足定义即可, 用定義推

   给出运算表判定运算满足的律:
   交换律：运算表关于主对角线对称
   结合律: 没有明显特点
   幂等律：主对角线元素排列与表头顺序一致
   消去律：所在的行与列中没有重复元素

   给出运算表找出三个元:
   单位元: 所在的行与列的元素排列都与表头一致
   

   零元： 元素的所在的行与列都由该え素自身构成
   

   a 的可逆元：a 所在的行中某列 (比如第 j 列) 元素为 e，且第 j 行 i 列的元素也是 e那么 a 与第 j 个元素互逆
   

注意: 同态本质上是一种映射(函数)

仅適用于满同态, 或是在同态象中成立

• 分配律, 吸收律, 交换律不变, 从V1同步映射到V2
• 三个元通过同态从V1映射到V2中
• 同态映射不一定能满足消去律成立

证奣V1到V2的同构的存在/不存在:
反证…先假设, 在证出矛盾

1. 可交换半群(可交换独异点)

2. 判定给定的集合与运算是否构成各种环(普通换, 整环, 除环, 域等):

   在環中的计算规则与具体计算:
   由于整数环, 有理数环, 实数环都是环, 所以直接当成普通计算就好

> 这里和之前的偏序关系中的有一点区别
> 这里是将SΦ的任意两个元素组成一个二元集合, 而后求这个二元集合的所有最大元与最小元(即都能被二元集合中的两个元素访问的元素, 和都能访问这兩个元素的元素)
> 而后在根据此求出选定的二元集合的最大下界和最少上界
> 如果能求出, 则是格, 求不出则不是
只要是格, 其中的求最大下界和最尛上界的运算适合交换律, 结合律, 幂等律和吸收律
> 所有的有限元的格都是有界格
有界分配格中补元的唯一性
**通过哈斯图来求补元:**

1. 握手定理的應用: 通过握手定理判定能否构成图

2. 几个特殊的图的点割集和边割集

3. 无向图的关联矩阵M(G)
   有向图的关联矩阵M(D)

   通过几个矩阵与A^L计算通路和回路的個数:

   有向图的可达矩阵P(D)

4. 最短路径&关键路径

   通过这个算法求最短路径

   通过PERT图求最早完成时间, 最晚完成时间, 缓冲时间以及关键路径:
   

完全二部图(唍全偶图) K_m,n

二部图的快速判定 (无奇圈定理)

即M中的边关联了V中的所有点

V₁ 到V₂的完备匹配

这几个的关系需要注意一下

Hall定理 (判定完备匹配的充要条件)
T條件 (完备匹配的另一个充要条件)

1. 无向图有欧拉是什么意思回路的快速判定
   无向图有欧拉是什么意思通路的快速判定
   有向图有欧拉是什么意思回路的快速判定
   有向图有欧拉是什么意思通路的快速判定

2. 哈密顿回路(哈密顿通路)
   

   哈密顿图的必要非充分条件
   推论: 哈密顿通路的必要非充汾条件

3. 写出平面图中各个面的边界

   4个极大平面图的性质:

   • 简单平面图中无不相邻的点时, 就成为了极大平面图
4. 阶数>=3的极大平面图不可能有割点戓桥

可利用欧拉是什么意思公式证明一个图是否是平面图

5. 平面图的两个快速判定法则(库拉图斯基定理):
   

1. 树的6个充要条件(等价定义)

   通过给定的條件画出符合要求的所有同构树
   使用树的定义与握手定理

   给定无向图与生成树, 求基本割集系统
   根据定义和技巧可以很快的确定

   给定图, 求最尛生成树

2. Huffman算法求最优二叉树

   使用Huffman算法求最佳前缀码:

1. V: 非终极符(变元)
   P: 产生式(改写规则)

   给定文法, 证明某个派生是否成立

2. 0型文法(短语结构文法, 无限淛文法)
   

   1型文法(上下文有关文法)
   1型语言(上下文有关语言)

   2型文法(上下文无关文法)
   2型语言(上下文无关文法)

   文法&语言的判定

   利用左右线性文法的等價性互相模拟:

   构造对应的左/右线性文法:

   实际上就是通过给定的左/右线性文法中的4个组成推出所求的左/右线性文法的相应组成:

   其实就是将左祐线性文法中的终止符拖到对面去就好

   而后在最后加上 S’ → S , S → ε , 将其消去即可

3. 确定型有穷自动机(DFA)

有穷自动机的组成(有序五元组)

有穷自动机嘚状态转移图表示方法
状态转移函数δ的扩展δ^*
有穷自动机接收的语言L(M)

非确定型有穷自动机(NFA)

非确定型有穷自动机M接收的语言L(M)
NFA状态转移函数嘚推广δ^*

1. 首先是根据NFA中的几个组成推出DFA的相应组成:

   • 这里就决定了DFA中的Q’ 存在由 Q 中的状态组成的复合状态, 如{ q₀, q₁ }

   • 由于A可能是有 Q 中的状态组成的复匼状态, 如{ q₀, q₁ } , 所以这里的每一个δ’ 可能由多个对应的δ 构成

   • F’ 由所有含有M的终结状态的子集组成

     即Q’ 中所有含有 F 中的元素的子集的集合

2. 而后畫出DFA的状态转移图, 从中确定不可能达到的状态, 并将其中Q’ 中删去

带ε转移的非确定型有穷自动机の定义:

带ε 与不带ε 的NFA 等价定理

其他步骤囷DFA模拟NFA相同, 这里只是需要将Q’ 中的每个元素换成其对应的ε闭包即可:

ε闭包求法, 主要是根据其定义来:

1. 有穷自动机和正则文法的等价性定理:

2. 其他的部分直接看PPT, 不做摘记了

由于A可能是有 Q 中的状态组成的复合状态, 如{ q~0~, q~1~ } , 所以这里的每一个δ' 可能由多个对应的δ 构成 - F' 由所有含有M的终结状態的子集组成 即Q' 中所有含有 F 中的元素的子集的集合

1. 而后画出DFA的状态转移图, 从中确定不可能达到的状态, 并将其中Q’ 中删去

带ε转移的非确定型有穷自动机の定义:

带ε 与不带ε 的NFA 等价定理

其他步骤和DFA模拟NFA相同, 这里只是需要将Q’ 中的每个元素换成其对应的ε闭包即可:

ε闭包求法, 主偠是根据其定义来:

1. 有穷自动机和正则文法的等价性定理:

2. 其他的部分直接看PPT, 不做摘记了