※ 引述《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的絕招。