TL;DR

• Shannon 扩展是将布尔函数分解为单个 MUX 的公式。
• 协因式是 "将一个变量固定为 0/1 的新函数"，因此 该变量在协因式中消失。
• 布尔差分是一个灵敏度函数，用于计算 "当输入 x 翻转时，输出是否发生变化？
• ∃（存在）量化是 "只需存在一个解决方案 "的公式，它是 SAT 的核心。
• 为什么优化很难：SAT 是关于找到一个解，优化是关于比较所有候选解。

1.问题：当 Karnaugh 映射断裂时

1.1 40 个变量，Karnaugh 图结束

• 2^40 比例→"我能画出来，但写不出来"
• 结论：我们应该将布尔函数视为 数据结构 + 运算符，而不是 手。

1.2 本文涉及的 3 个方面

• 分解（分解）
• 计算（程序可以处理的表示）
• 应用（EDA 中的直接操作）

2.香农辅因子：通过 "固定一个变量 "创建的新函数

2.1 定义：辅助因子是一种替换

• 对于 f 中的输入变量 x，一个
  • 正辅助因子： ( f_{x} = f(x=1) )
  • 负辅助因子： ( f_{~{x}}= f(x=0) )

2.2 关键点："这是一个新函数，x 消失了"

• 我们已经将 x 固定为 0/1，因此 x 不会再出现在结果中。
  • 示例：( f(x,y、z) = xy+x~z+~xyz ）
    • ( f(x=1) = y +\bar{z} ) （可以简化）
    • ( f(x=0) = yz )
• select = x
• data1 = f(x=1)
• data0 = f(x=0)
• output is f
• 当我们沿着 x=0 分支前进时，我们只需查看 f(x=0)
• 当我们沿着 x=1 分支前进时，我们只需查看 f(x=1)
• 1 个变量 → 2 个分支
• 2 个变量 → 4 个分支
• k 个变量 → 2^k 个分支
  • 补充：
    • (~f)x=~(𝑓𝑥)
  • AND/OR/XOR 还允许 "先辅因式→后运算"
    • (𝑓∧𝑔)𝑥=𝑓𝑥∧𝑔𝑥
• XOR 是 "如果不同则为 1"
• 因此，在布尔差值为 1 的输入模式上：
  • 如果 x 从 0→1 或 1→0 变化，则 f 必须变化
• 变频器：f=~x
  • 𝑓(1)=0,𝑓(0)=1⇒∂𝑓/𝑥=1
  • 始终敏感
• AND： ( f=xy )
  • 𝑓(1)=𝑦,𝑓(0)=0⇒∂𝑓/𝑥=𝑦
  • x 的变化仅在 y=1 时影响输出
• OR：( f=x+y )
  • 𝑓(1)=1、𝑓(0)=𝑦 ⇒ ∂ 𝑓/∂𝑥=~𝑦
  • 仅当 y=0 时受影响
• 不等于 "总是没有影响"。
• 它的意思是在某些输入条件下它可能没有影响。
• 找出这些条件就是布尔差分。
• 意思是：在其他輸入固定的情況下，一個好的 x 選擇會導致 f=1 嗎？
• 意思是：无论 x 是什么，f=1 总是真的吗？
• 而 SAT 的核心形式是：∃X：F(X)=1
• 当存在满足条件的 解决方案时结束
• 可以终止（剪枝）
• 要证明有更好的解决方案
  • 您需要不断查看其他分支
• 这就是为什么 EDA 优化在结构上是困难的（这导致了 NP-困难的故事）
• f≡1？
• 关键概念：如果 f 是同义反复 ⇔ f(x=0) 和 f(x=1) 都是同义反复
• 分解为香农辅因子（分支）
• 在正中间终止（强剪枝）
• 最终不是 "枚举 "算法，而是 "快速扔掉能扔掉的东西"
1. cofactor는 substitution이며,在生成的函数中，变量消失
2. 香农展开既是一个公式，也是一个2：1 MUX 模型
3. 布尔差分是一个 函数，它给出了 "x 的变化影响输出的条件"
4. ∃量化将 "只需要一个 "实现为 OR
5. SAT 是一劳永逸的，优化需要更长的时间，因为要进行比较

这看起来像一个 "枚举"，但是 EDA 在这里进行了剪枝。1 MUX
[图 2] 一棵 MUX 树的图解，其中 2 变量扩展创建了四片叶子

4.cofactor 指 "交换操作"：계산이 쉬워지는 이유

4.1 一个非常重要的属性

换句话说，您不是先做一个大表达式，然后再辅因式，而是
先辅因式，使表达式变小，然后再计算。

5.布尔差：作为公式的 "灵敏度"

5.1 定义

∂f/∂x=f(x=1)⊕f(x=0)

5.2 含义："当 x 被翻转时输出发生变化的条件"

5.3 敏感性示例

5.4 正确理解 "x 对 F 没有逻辑影响？"

[图 3]门说明为什么在 AND/OR 中布尔差会变成 y / ȳ

6.量化：“변수 제거”를 목적 함수로 만든 연산

6.1 存在定量（∃）："只需要一個解決方案"

∃xf=f(x=0)∨f(x=1)

6.2 普遍量化（∀）："在所有情况下都必须为真"

∀xf=f(x=0)∧f(x=1)

6.3 1:1 与您说的句子相对应

"您不必全部列出，只需找到任何一年"

这正是您所做的：

∃ 量化

7.SAT 与优化：为什么 "优化 "更严格

7.1 SAT 是 "找到一个就完成"

7.2 优化是 "比较是本质"

[图 4] SAT 在第一次满足时就停止了、Optimisation keeps exploring

다음 강의로 자연스럽게 연결:Tautology와 URP

8.1 同义反复 "总是 1 吗？"

8.2 URP 的直觉

이 글에서 반드시 가져가야 하는 5개

。

如果你忽略了这一点，那么所有后续的布尔差分/量化都会失效。3 （简短示例）

3.香农扩展："布尔函数 = MUX"

3.定理 1（香农扩展定理）

对于任意 f 和任意变量 x：
f=x⋅f(x=1)+~x⋅f(x=0)

3.2 硬件视角：香农扩展 = 2:1 MUX

📌 这就是 "分支 "的意义所在：

3.3 MUX 树 = 递归分解