如何只使用一个隐层，来实现包含n元输入的任意布尔函数？
此为吴恩达《深度学习》课程中其中一个（不起眼的）知识的拓展。
吴恩达举例说明深度神经网络时，给出了只使用一层隐藏层表示异或逻辑需要$O(2^n)$的隐藏单元。
结论看起来很显然，但该如何证明呢？
包含n元输入的任意布尔函数可以唯一表示为析取范式（Disjunctive Normal Form，DNF）（由有限个简单合取式构成的析取式）的形式。
单个隐结点可以表示任意合取式。考虑任意布尔变量，假设$X_i$，若它 在合取范式中出现的形式为正（$X_i$)，则设权重为1；若出现的形式为非$\overline{X_i}$， 则设权重为−1；若没有在合取式中出现。设权重为0；并且偏置设为合区式中变量的总数取负之后再加1。可以看出，当采用ReLU激活函数之后，当且仅当所有出现的布尔变量均满足条件时，该隐藏单元才会被激活（输出1)，否则输出 0，这与合取范式的定义的相符的。然后，令所有隐藏单元到输出层的参数为1，并设输出单元的偏置为0。这样，当且仅当所有的隐藏单元都未被激活时，才会输出0，否则都将输出一个正数，起到了析取的作用。
由上可知，最多只需一层隐藏层，感知机就能表示任何布尔函数，只需表示为析取范式的形式。任何布尔函数都可以用真值表来表示。
例如:
那隐藏单元什么时候最多呢？异或函数。这时候的真值表如棋盘一样交叉相错。
这时候，隐藏单元为$2^{n-1}$个。
也如吴恩达所提到的，如果不限制隐藏层为单层，则隐藏单元数量可以降低到$O(n)$。
事实上，吴恩达提到的这个异或函数也被称为”n元奇偶校验问题“。文献3中通过引入隐层抑制神经元将隐元数目降至n。
此外，顺便提一下Shannon’theorem,即当n>2时，存在一个n元输入的布尔函数至少需要$\frac{2^n}{n}$的门。
如果我们能找到用一个数量多项式大小的神经网络模型计算所有的布尔函数，则说明了P=NP。
[参考资料：]
2.《百面机器学习》
3.陆阳，杨娟，王强，黄镇谨.二进神经网络表达奇偶校验问题的隐元最小数目上界.中国科学：信息科学,2012
进一步阅读：
4.Setiono, R. (1997). On the solution of the parity problem by a single hidden layer feedforward neural network. Neurocomputing, 16(3), 225–235.