※ 引述《ping870224 (爱萱萱)》之铭言：
: 刚刚点开google首页发现几个熟悉的逻辑闸AND,XOR,OR,NOT原来是布林代数，点
: 进去发现原来是数位逻辑学大师-布尔的冥诞200年。现在能用PTT发废文都要归他
: 的功劳，念EE和CS都知道1和0有多么重要，有没有布林代数的八卦?
本鲁的朋友告诉本鲁，以前有一个叫做Shannon的大大，曾经研究过：随机的函数
需要多大的电路才能计算呢？
举个例子，如果一个函数会把00对应到1、01对应到0、10对应到0、11对应到0，那
它就可以被以下电路计算：
x y
| |
NOT NOT
\ /
\ /
AND
|
输出
当x和y都是0的时候，经过NOT逻辑闸（NOT逻辑闸会把0变1、1变0），两条线都会
送1下来，而AND逻辑闸则在其两条输入都是1时才输出1，所以此时AND逻辑闸输出1。
如果x和y分别是0和1时，y经过NOT逻辑闸，会送0下来，然后AND不管左边接收到什
么，都会输出0。当输入为10或11时，也可以用类似方法得知输出会是什么。
如果把目标函数改成输入为n bits、输出1个bit的随机函数，那至少要多少逻辑闸
才能计算该函数呢？这是Shannon研究过的问题。
首先，n个bits有2的n次方种可能，就好像刚刚2个bits有00、01、10、11四种，就
是2的2次方种，每种n个bits的组合都可以对应到0或1，有两种可能，所以所有要考
虑的函数总数是2乘以2乘以2乘以 ... 乘以2，总共有2的n次方个2乘在一起，也就
是共有
n
2
2
个函数。
接下来计算拥有s个逻辑闸的电路有几个呢？每个逻辑闸充其量有两条输入（例如上
面AND逻辑闸就有两条输入），第一条输入有顶多s种可能（看是接收哪个逻辑闸的输
出），第二条输入也顶多s种可能（同样看是接收哪个逻辑闸的输出），乘起来就是
s平方种可能，又因为逻辑闸总数为s，所以所有可能性有
s平方 乘以 s平方 乘以 ... 乘以 s平方
种，以上总共s项，算出来是s的(2s)次方。
以上的计算还没完，每个逻辑闸可以是AND逻辑闸、OR逻辑闸、NOT逻辑闸、接收第一
个bit输入的逻辑闸、接收第二个bit输入的逻辑闸、...、接收第n个bit输入的逻辑
闸，以上总共(n+3)种可能。
所以所有逻辑闸所属种类，还有(n+3)乘以(n+3)乘以 ... 乘以(n+3)种可能性，共s
个(n+3)乘在一起，算出来是(n+3)的s次方。
最后还要指定一个逻辑闸的输出为整个电路的输出，这又有s种选法。
综合以上，s个逻辑闸的电路总数顶多
s的(2s)次方 乘以 (n+3)的s次方 乘以 s。
这个量即使在s很大时（例如s = 2的n次方 除以 (2n)），都还是远小于前面算过的
输入为n bits、输出为1 bit的函数个数（也就是2的2的n次方）。由于一个电路只
能计算一种函数，所以这表示绝大部份的函数，都是不能被大小为s（这里取
s = 2的n次方 除以 (2n)）的电路计算的！换言之，大部份的函数都需要很大的电
路才能计算！
更好一点的估计Google会有。
这是Shannon的绝招。