1937-Shannon開關理論#
案件摘要#
1937 年，21 歲的 Claude Shannon 在 MIT 交出碩士論文《繼電器與開關電路的符號分析》。他證明了一件在當時無人看清的事：1850 年代 Boole 的抽象邏輯代數，與電話交換機裡的繼電器電路完全同構。電路的串聯是 AND、並聯是 OR、反接是 NOT——設計電路可以變成解代數題。這樁「數學與機器的聯姻案」是全部 EDA（電子設計自動化）的第一塊地基石：因為邏輯可以被代數表示，邏輯設計才可以被程式化。
前因 -- 為什麼會有這個案子#
- Boole（1854）：《思維法則》把邏輯推理化為代數運算，但百年來只被當作純數學玩具。
- Huntington（1904）：給出布林代數的公理化，使它成為嚴格的代數結構——工具已磨好，缺一個應用場景。
- Vannevar Bush 的微分分析機：Shannon 在 MIT 維護這台機電式電腦，其控制電路用上百個繼電器，設計全靠試錯與直覺，錯一根接線就癱瘓。
- 貝爾實驗室的交換網路：電話撥接電路龐大且重複，工程師苦於無法系統化驗證電路正確性——這是案發現場。
線索與推理 -- 數學式、程式、理論#
線索一：同構的發現#
Shannon 觀察繼電器電路，寫下對應表：
| 布林代數 | 繼電器電路 |
|---|---|
| 變數 \(x \in \{0,1\}\) | 開關 \(x\) 開/閉 |
| \(x \cdot y\) （AND） | \(x, y\) 串聯 |
| \(x + y\) （OR） | \(x, y\) 並聯 |
| \(\bar{x}\) （NOT） | 常閉觸點（反相） |
| 恆等式 \(x + \bar{x} = 1\) | 並聯反相開關必導通 |
兩個系統滿足相同的公理（交換律、分配律、補律），因此布林的定理自動是電路的定理。化簡代數式 \(F = x + x\bar{y}\) 得 \(F = x\) ，就等於省下一顆繼電器。
線索二：形式化定義#
開關函數是映射 \(f : \{0,1\}^n \to \{0,1\}\) ，其合成規則構成自由布林代數。任意函數可用積項之和（SOP）表示：
\[ f(x_1,\dots,x_n) = \bigvee_{i : f(a_i)=1} m_i, \quad m_i = \bigwedge_{j} x_j^{(i)} \]
Shannon 展開定理（MVS 展開）更給出遞迴分解：
\[ f(x_1, \dots, x_n) = \bar{x}_n \cdot f|_{x_n=0} + x_n \cdot f|_{x_n=1} \]
——這條式子正是日後 BDD（1986）、Shannon 樹、多層合成的遞迴核心。
線索三：最省電路的雙面刃#
Shannon 同時指出：找最少閘數的等價電路是極難問題。他在 1949 年進一步證明任意 \(n\) 元開關函數需 \(O(2^n/n)\) 個閘——組合爆炸的陰影從第一天就籠罩這門學問，逼出後世一切啟發式演算法（QM、Espresso、SIS）。
結案 -- 後果與影響#
- 數位設計有了數學：從此電路設計 = 代數運算，「驗證」變成檢查兩個布林式等價，為 EDA 打下可能性。
- 直接催生交換理論學派：貝爾實驗室的 Lee、McCluskey，哈佛的 Aiken 團隊都沿此展開，孕育 1952-56 的 QM 最小化與 1961 的迷宮繞線。
- Shannon 的迷宮老鼠（1950）：他用繼電器造出會學迷宮的機械鼠「Theseus」，正是 1961 年 Lee 演算法的實體預演。
- EDAC 的意識形態起點：「設計應可自動化」的信念自此生根，最終長成 DAC 會議（1964）與整個 EDA 產業。
- Shannon 本人轉向資訊論（1948），留下《通訊的數學理論》——他在兩個領域各埋了一顆種子。
關鍵人物與文獻#
- Claude E. Shannon（1916–2001）：MIT 碩士（1937）、貝爾實驗室，資訊論之父。
- 文獻：
- C. E. Shannon, "A Symbolic Analysis of Relay and Switching Circuits," Trans. AIEE 57, 713 (1938)（1937 論文出版版）。
- C. E. Shannon, "The Synthesis of Two-Terminal Switching Circuits," Bell Syst. Tech. J. 28, 59 (1949)（計數下界 \(O(2^n/n)\) ）。
- G. Boole, An Investigation of the Laws of Thought, 1854.