De Morgan 布尔公式

公式不是“一串带括号的符号”这么简单；它的语法树就是计算资源。树形约束禁止共享，迫使每一次复用都付出一份新的叶和门。若子函数 $g$ 同时影响两个分支，一般电路可以先算一次 $g$ 再分叉，公式却要把描述 $g$ 的整棵子树复制。例如选择器 $(g\wedge a)\vee (\mathrm{\neg }g\wedge b)$ 在 DAG 中可让两条支路共用计算 $g$ 的结点；写成 De Morgan 公式时，一支需要 $g$ 的树，另一支需要其否定对偶树。这不是一个下界证明，却把复制成本发生的位置清楚地显出来。这一差异使公式下界可能远强于对一般电路能证明的下界，也解释了为什么平衡语法树会改变深度而未必保留原来的规模。

De Morgan 门集刻意保持朴素：AND 与 OR 表示两种组合方式，输入处的正负文字承担所有否定。这样的正规形让对偶、随机限制和通信博弈都能沿树递归。它不是说真实硬件只能使用这三种门，而是固定一把可比较的尺；换成另一种固定、有限、常扇入的完备门集时，单个门总能用常数大小的公式替换；但替换可能多次使用同一参数，迫使公式复制整个子树，因而不能直接推出总叶数只增加常数倍。先平衡公式再替换，可保留多项式规模这一粗粒度类别；精确叶数和逐门下界仍依赖门基。

二位异或可写成

这棵树有 $4$ 个文字叶、$3$ 个二元门，深度为 $2$。代入 $(x,y)=(1,0)$，左侧合取为 $1$、右侧为 $0$，根输出 $1$；代入 $(1,1)$ 时两个合取都为 $0$。变量 $x$ 与 $y$ 各出现两次，正是树不能让正、负分支共享一次读取的表现。三变量多数函数

在二元括号约定下有 $6$ 个叶；允许一个三扇入 OR 会改变门数与深度，却不改变这里的叶出现次数。

对偶与取否定是两种不同操作。构造对偶公式 $F^{\ast }$ 时，交换每个 AND/OR、交换常量 $0,1$，但保留每个文字的极性，此时 $F^{\ast }(x)=\mathrm{\neg }F(\mathrm{\neg }x)$。例如 $x\wedge y$ 的对偶是 $x\vee y$。若还把每个文字取反，得到的则是 $\mathrm{\neg }F(x)$，例如 $\mathrm{\neg }x\vee \mathrm{\neg }y$；不能把这两个等式混写。

三变量多数公式的对偶为 $(x_1\vee x_2)\wedge (x_1\vee x_3)\wedge (x_2\vee x_3)$，它仍表示至少两位为真，所以多数函数自对偶。相比之下，AND 与 OR 互为对偶，并不自对偶。这些操作都保持树形和叶数。

边界必须说清。公式的语法可以含重复变量，却仍是树；“read-once formula”还额外要求每个变量最多出现一次，不能与普通公式混同。叶出现两次计作两份语法资源，即使两片叶都指向同一个外部输入位；这里衡量的不是从内存读取变量的物理次数。若允许某个内部结点有多个父结点，模型已经变成可共享的电路。若把任意布尔函数当成一个原子门，规模度量也会坍缩。常量、输入是否计入规模、根层是否计入深度都是文献中的局部差异，引用精确数字前必须先固定约定。

De Morgan 公式为布尔公式复杂度公理库布尔公式复杂度Boolean formula complexity · Formula size and depth以最小叶数和最小深度衡量树状布尔公式计算函数所需资源。提供标准对象。规模研究询问最少需要多少文字叶，深度研究询问最长依赖链能有多短；Brent–Spira 深度约简公理库Brent–Spira 公式深度约简Brent depth reduction theorem · Spira theorem · Formula balancing theorem将任意有限扇入布尔公式在多项式规模内平衡到关于原规模的对数深度。说明任意小公式都能在多项式规模内平衡到对数深度。反向地，二元树深度为 $d$ 时至多有 $2^d$ 个叶，这给出规模与深度之间最基本的计数联系。

树递归还可翻译成博弈。Karchmer–Wigderson 博弈公理库Karchmer–Wigderson 博弈Karchmer-Wigderson game · KW game · Karchmer-Wigderson relation让一方持有真输入、另一方持有假输入并寻找分歧坐标的通信搜索关系。把根处选择哪个真或假子式变成双方通信，精确刻画公式深度；公式规模博弈公理库公式规模博弈Formula-size game · Propositional formula-size game · EF_w formula game以正反例集合的左右分割和叶预算精确刻画命题公式的最小叶规模。则以集合分割和叶预算刻画叶数。单调版本去掉负文字，只保留 AND/OR，由单调电路公理库单调布尔电路Monotone circuit · Monotone Boolean circuit只用正输入、AND 与 OR 门计算单调布尔函数的无环电路模型。条目统一讨论其与一般电路的差别。