2.1 综合的数学语言：布尔代数与逻辑表示

2.1 综合的数学语言：布尔代数与逻辑表示

本节摘要：综合引擎里"优化"的对象是逻辑函数的某种机内表示。本节沿真值表、两级逻辑、布尔网络、BDD 的顺序，讲清每种表示的表达能力与规模代价，解释为什么工业引擎最终收敛到布尔网络与 AIG，而 BDD 退守等价性检查与验证领域。本节的语言是全章的地基，2.3 节的重构算法将直接在这些表示上操作。

先把问题摆上桌

承接第 1 章：自动化接管设计的第一个前提，是"功能相同"这四个字可以被机器判定。两个电路长得完全不一样，凭什么说它们等价？答案是：只要它们对每组输入产生相同的输出序列，就等价。要把这句话变成算法，必须先把电路装进一种数学表示里——这种表示既要能精确刻画功能，又要小到算得动。表示的选择直接决定了后续一切算法的上限：同一逻辑功能，用真值表表示可能需要 2 的 64 次方行，用因式分解后的表达式可能只需要十几个门。

这就是本节的核心矛盾：表示的规范性与紧凑性不可兼得。规范性（canonical form）意味着一个功能只有一种写法，等价性检查退化成比较两个对象是否相等，这是天大的便利；但规范性通常要付出指数规模的代价。紧凑表示省空间，却让"判断等价"变成一个难解问题（NP 难）。综合引擎和验证工具对这对矛盾给出了不同的取舍，理解取舍的原因比记住结论重要。

真值表与两级逻辑：教学的起点，工业的边界

真值表是最直白的表示：n 个输入列全组合，输出列写结果。它规范、易查，但规模是 2 的 n 次方——64 位加法器的真值表超过 10 的 19 次方行，宇宙中所有原子存储不下。真值表的教学价值在于引出两级逻辑：乘积项之和（SOP）。每个输出为 1 的行对应一个乘积项，全部求和即得函数。卡诺图化简做的事情是在相邻的 1 之间找最大的合并圈，每个圈就是一个含更少变量的乘积项。

两级逻辑的工程巅峰是 Espresso 算法：不求最优、求"接近最优的快速启发式"，对几十个输入的函数在秒级给出精简的两级实现。但两级结构有一个物理上限：一个乘积项对应一个大规模与门，扇入随变量数增长，深亚微米工艺下高扇入门的延迟和功耗都不可接受。所以工业实践走向多级逻辑——布尔网络。

布尔网络：综合引擎的工作表示

布尔网络是一个有向无环图，每个节点存一个布尔函数（通常是简单门），边表示信号依赖。RTL 综合的第一步就是把描述翻译成这种网络，之后所有的结构变换——提取公因式、消去中间节点、代入化简——都在网络上操作。两个经典的代数操作值得单独记住：提取（把多个节点共享的子表达式抽成一个公共节点，面积随之下降）与代入（用已有节点的函数替换网络中出现的等价表达式）。代数方法只利用结构信息，速度快；布尔方法进一步利用"函数值相等"这个更强的条件，优化空间更大但代价更高。

现代引擎把布尔网络进一步简化成单一门类型：AIG（与-非图），每个节点就是一个二输入与门，取反用边上的小圆圈标记。所有其他逻辑门都可以由与门加取反组合出来。这个看似粗暴的简化带来巨大好处：网络结构极简，缓存、哈希、结构哈希（structural hashing，合并重复子图）都变成简单操作，重构算法只需要处理一种节点。2.3 节会展开 AIG 的全部细节。

// Shannon 展开：把函数按变量 x 分解成两个子函数
// f = x' * f0 + x * f1，其中 f0 = f(x=0), f1 = f(x=1)
// 这是 BDD 构建与许多布尔算法的原子操作
Node cofactor_decompose(Func f, Var x) {
    Func f0 = f.eval(x = 0);          // 负相余因子
    Func f1 = f.eval(x = 1);          // 正相余因子
    if (f0 == f1) return f0;          // x 不影响结果，直接消去变量
    return OR(NOT(x) AND f0, x AND f1);
}
​

BDD：规范性买来的验证能力

BDD（二叉决策图）把 Shannon 展开递归到底，再把同构子图合并，得到一个有根有向无环图。固定变量顺序后，BDD 是规范的：功能相同则图相同，等价性检查就是比较两个指针是否指向同一个节点。布尔代数里最难的等价判定，在 BDD 世界里退化成一次指针比较——这是表示论意义上的胜利。1986 年 Bryant 的论文让 BDD 成为验证领域的支柱，至今形式化工具（第 6 章会用到）仍在内部依赖它。

代价同样来自规范性：BDD 的规模对变量顺序极端敏感。同样一个 n 位乘法器，顺序选好时节点数是多项式级，选差时是指数级；而寻找最优变量顺序本身是 NP 难问题。更糟的是某些常用函数（如整数乘法）对任何顺序都是指数规模。工程上只能用动态重排序（如 Rudell 的 sifting 算法）在运行中调整顺序缓解。这些经验告诉综合研究者：规范性太贵，优化引擎需要更轻的表示——这是 AIG 最终胜出的历史逻辑。

易错点：等价与最优的边界

初学者常把两件事混为一谈。其一，"两个电路等价"与"两个电路结构相同"完全是两回事，结构哈希只能抓结构重复，功能等价要靠 SAT 或 BDD。其二，两级逻辑的"最优化简"（最小乘积项覆盖）是 NP 难问题，卡诺图只能在六变量以内手工作业，这不是工具不行而是问题本身的复杂度等级。理解了这两条，就能看懂为什么工业综合器全部是"启发式 + 事后验证"的架构：优化阶段大胆用不保等价的结构变换，最后用等价性检查兜底，错了就回退。这套"大胆变换、严格验证"的双层架构，是所有 EDA 算法的通用模式，第 3 章的物理实现与第 6 章的验证体系都会再见到它。

本节要点回顾

• 表示决定算法上限：规范性与紧凑性不可兼得，综合与验证工具因此走向不同表示。
• 真值表与两级逻辑：规模 2 的 n 次方，Espresso 是两级化简的工程终点，物理扇入限制使其退出主流。
• 布尔网络：综合引擎的工作表示，提取与代入是面积优化的两个基本代数操作。
• AIG：单一与门加取反边，结构与哈希操作极简，是现代综合的底座。
• BDD：定序后规范，等价检查退化成指针比较，但规模对变量顺序敏感、乘法类函数必然指数。
• 工业架构：启发式优化不保等价，SAT 等价性检查兜底回退——EDA 算法的通用双层模式。