# 有证明的下界

> 3 位加法的进位最少要 6 层 NAND：5 层做不出，6 层有现成电路。

## 结论

| 项 | 值 |
|---|---|
| 函数 | A、B 是 3 位无符号数，c 是 1 位进位输入，输出 `[A + B + c ≥ 8]` |
| 输入 | 7 位，共 128 种 |
| 门 | 两输入 NAND，个数不限，可以共用，可以接常数 0 / 1 |
| 下界 | 深度 5 做不出 |
| 上界 | 有一个深度 6 的电路，22 个门 |

只说这一个进位函数。不说完整加法器或乘法器的最小深度。

## 为什么 5 层做不出

1. 列出深度 ≤ d 能做出的全部函数，记作 F_d。F_0 是 7 个输入；每加一层，把上一层任意两个函数 NAND 一下加进去。这样不漏任何电路，不管门数和共用。
2. 实际个数：F_0 = 7，F_1 = 35，F_2 = 540，F_3 = 84,156。
3. 深度 5 的输出 = NAND(两个 F_4 函数)，每个 F_4 函数要么已在 F_3，要么是两个 F_3 函数的 NAND。
4. 输出为 0 的那些输入上，两个操作数都必须是 1。按这个条件筛，合法的 F_3 操作数对有 1,052,195 对，得到 21,787 种不同的乘积，其中 262 种是极大的。
5. 没有任何两个极大乘积能凑出目标函数；更浅的深度也做不出。所以深度 5 不可能。
6. 常数没用：NAND(0, x) 恒为 1，NAND(1, x) 等于 NAND(x, x)，都不会让剩下的电路更浅。

## 两套独立程序核过

- 一套原生程序直接扫全部 F_3 对，用时 2.014 秒。
- 一套独立 Python 程序换一种算法：对每个输出为 0 的输入建候选位集再求交，用时 5.277 秒。
- 两套重建了全部输入真值表和 F_3，每个计数和最后的结论都一致。
- 另外用 SAT 求解器（CaDiCaL、Kissat）解对应的 31 门槽位问题，都返回 UNSAT。主证据是上面的完整枚举，不靠 SAT。

## 深度 6 的电路

- 22 个 NAND，深度正好 6。
- 在全部 128 种输入上和 `A + B + c ≥ 8` 逐个比过，全对。
