逻辑电路

概述

逻辑电路（Logic Circuit）是用逻辑门（AND、OR、NOT 等）组合实现的布尔函数计算装置，是布尔代数的物理实现形式，也是计算复杂性理论中电路复杂度类的研究对象。

定义

形式化定义

一个布尔电路（Boolean Circuit） $C$ 是一个有向无环图（DAG），其中：

• 输入节点（input gate）：无入边，标记为布尔变量 $x_1,x_2,\dots ,x_n$ 或常量 0/1
• 逻辑门（logic gate）：每个非输入节点标记为一个布尔运算：
  • AND 门（$\wedge$）：入度为 2，输出 $a\wedge b$
  • OR 门（$\vee$）：入度为 2，输出 $a\vee b$
  • NOT 门（$\neg$）：入度为 1，输出 $\neg a$
• 输出节点（output gate）：一个指定的门，其输出即为电路的计算结果

电路计算布尔函数 $f:\{0,1{\}}^n\to \{0,1\}$。

核心度量

电路大小（Circuit Size）

$\text{size}(C)=\text{电路中逻辑门的总数}$

电路大小衡量了实现该布尔函数所需的硬件资源量。

电路深度（Circuit Depth）

$\text{depth}(C)=\text{从输入到输出的最长路径上的门数}$

电路深度衡量了计算的并行时间——深度为 $d$ 的电路可以在 $d$ 个时间步内完成计算（假设每个门耗时 1 个时间步，且同一层的门可以并行执行）。

电路族（Circuit Family）

对每个输入长度 $n$，一个电路 $C_n$ 计算 $n$ 位输入上的函数。所有 $C_n$ 的集合 $\{C_n{\}}_{n=1}^{\infty }$ 构成一个电路族。

通用门集

以下门集合是通用的（universal），即用它们可以实现任意布尔函数：

• $\{\text{AND, OR, NOT}\}$：标准门集
• $\{\text{NAND}\}$：仅用 NAND 门即可实现所有布尔函数（NAND 是功能完备的）
• $\{\text{NOR}\}$：仅用 NOR 门即可实现所有布尔函数

复杂度类与电路

P/poly

P/poly 复杂度类

语言 $L\in \text{P/poly}$，当且仅当存在多项式大小的电路族 $\{C_n\}$ 判定 $L$。

即：对每个 $n$，存在大小不超过 $n^k$（某常数 $k$）的电路 $C_n$。

P/poly 包含 P（多项式时间可判定的语言），但也可能包含非递归语言（因为电路族不需要一致地构造）。

CIRCUIT-SAT

CIRCUIT-SAT 是 NP 完全的

给定布尔电路 $C$，判定是否存在输入赋值使 $C$ 输出 1。这是 Cook-Levin 定理的电路版本——CIRCUIT-SAT 是第一个被证明为 NP 完全的问题之一。

归约方向：任何 NP 问题都可以在多项式时间内归约为 CIRCUIT-SAT（将非确定型图灵机的计算过程编码为电路）。

应用场景

• 硬件设计：CPU、GPU 等处理器由数十亿个逻辑门组成
• NP 完全性：CIRCUIT-SAT 是 Cook-Levin 定理的基础，证明 SAT 问题的 NP 完全性
• 密码学：密码算法的硬件实现依赖逻辑电路优化
• 程序验证：将程序的正确性条件编码为电路可满足性问题

参见

• 布尔代数