经典线路

阐述

经典线路由门构成，一个门接受一个或两个位的输入，给出一些输出。门的运算由真值表决定。

任何 $n$ 维的二值函数可以用 AND, OR 和 NOT 门组成：

f=\left(x_{1} \wedge f\left(1, x^{\prime}\right)\right) \vee\left(\neg x_{1} \wedge f\left(0, x^{\prime}\right)\right)=\left(x_{1} \wedge f_{1}\left(x^{\prime}\right)\right) \vee\left(\neg x_{1} \wedge f_{0}\left(x^{\prime}\right)\right)

这种构造方式要求 $n$ 维函数最多需要 $2^n$ 数量级的门来构造。