形式陈述

布尔电路是有限有向无环图，输入节点表示变量或常量，内部门计算 AND、OR、NOT 等布尔函数，指定输出门给出整体函数 $C:\{0,1{\}}^n\to \{0,1{\}}^m$。拓扑序保证每个门值能由输入向输出唯一求得。门集合只要函数完备即可表达任意布尔函数；不同基之间通常有常数因子模拟，但对极精细的大小和深度仍须固定扇入与门型。

直觉

电路把一次性计算展开成数据依赖图：相同中间结果可被多个后继门复用，图的宽度体现并行，最长依赖链体现延迟。

例子与边界

半加器用 XOR 与 AND 产生和位与进位；若基础门只有 AND/OR/NOT，XOR 可用常数多个门实现。电路必须无环，否则门值可能没有静态定义；带反馈的硬件应建模为时序电路或状态机。一个固定 $n$ 输入电路只处理该长度，语言复杂性需要电路族。公式是扇出为一的树状电路，可能因无法共享子表达式而更大。

推论与应用

布尔电路是硬件设计、并行算法与非一致复杂性的基础，连接 SAT、逻辑综合、NC、AC 和电路下界。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009，Chs. 1–8。
• Stasys Jukna, Boolean Function Complexity: Advances and Frontiers, Springer, 2012，Chs. 1–6。