基礎邏輯電路（上）
基礎邏輯電路（上）
歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！），為了一次解決我所有的困惑，於是製作本篇文章。
若文章有任何疑點及錯誤的地方歡迎提出。
本篇文章主要作為個人學習用途，撰筆形式概要以筆記形式撰筆。另外本篇文章以入門為導向，若需詳細閱讀相關學門，請搜尋「數位系統導論」或「數位系統設計」。
布林代數式（Boolean Algebra）
Boolean Algebra 是數學當中的一個分支，專門用來處理 0 跟 1 這種真（True）假（False）值。主要針對二進位變數以及邏輯運算，如最基礎的 AND、OR、NOT。
邏輯運算（Logical Operations）
- AND or Conjunction（關聯）
- OR or Disjunction（無關）
- NOT or Negation（否定）
AND 用布林代數式可表示為 $A \cdot B$ 或是 $A \wedge B$ 。
OR 用布林代數式可表示為 $A + B$ 或是 $A \lor B$ 。
NOT 用布林代數式可表示為 $\rightharpoondown A$ 或 $NOTA$ ，那本系的教授是用一個 bar 來表示 NOT，如 $\overline{A}$ 。
AND 要全部輸入都是 1，輸出才會是 1。
OR 只要其中一個輸入是 1，輸出就會都是 1，要產生 0 的情況，一定要全部輸入都是 0。
NOT 會將狀態反轉，就是 0 變成 1，1 變成 0。
真值表（Truth Table）
真值表（Truth Table）是一種用於邏輯運算的數學表格，主要用來列出所有可能的輸入組合下，布林代數式的結果。
如果有兩個輸入端如 A、B，那麼其輸出的結果會是 $2^2 = 4$ 種可能，三個輸入端就是 $2^3 = 8$ 種可能結果，由此可以推算出他的公式應該是 $2^n$ ，也就是輸出端的可能結果， n 是輸入端的個數。
以下是 AND、OR、NOT 個別的真值表：
AND（ $A \cdot B$ ）：
| A | B | $A \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
OR（ $A + B$ ）：
| A | B | $A + B$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
NOT（ $\overline{A}$ ）：
| A | $\overline{A}$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
邏輯電路與布林代數式之間的轉換
在此之前我們先看看 AND、OR、NOT 在電路上是怎麼表示的：
Image Source：Logic Circuit: AND Circuit | 臺灣東芝電子零組件股份有限公司 | 台灣
AND 是長的很像子彈的那個，OR 長的像是箭頭一樣，NOT 長的像是三明治上插一個竹籤加上綠豆的東西。總之看你怎麼去想像XD。
在上圖中，Y 是輸出端，那這邊就可以用布林代數式給他代進去了：
- AND： $Y = A \cdot B$
- OR： $Y = A + B$
- NOT： $Y = \overline{A}$
反之，想要用布林代數式表示回去電路符號的話，就照上面的圖去畫即可。
範例
e.g. 1 以下圖片是 AND 跟 OR 的邏輯電路圖，要求出 x 的布林代數式。
這邊觀察 $A \cdot B$ 的輸出端連接到 OR 的輸入端，那 OR 另一端輸入端為 C，所以根據前面的布林代數式規則，最後得到結果就是 $x = A \cdot B + C$ 。
e.g. 2 以下圖片為上圖的反例，試求出 x 的布林代數式。
這邊就只是將原來的 AND 改成 OR，後面的 OR 改成 AND，最後可得到 $x = (A + B) \cdot C$ 。
e.g. 3 求出以下 (a) 和 (b) 中 x 的布林代數式。
先看 (a)，可以發現 NOT 出現在 A 輸入端，因此先得到 $\overline{A}$ 。另一端 B 沒有任何變動，最終可輸出 $x = \overline{A} + B$ 。
接下來 (b)，同樣檢查 A、B 上面有沒有東西，沒有，那就看輸出端，發現有一個 NOT，那就表示要將原本要輸出的 $A \cdot B$ 加上 NOT，變成 $x = \overline{A \cdot B}$ 。
布林代數式表格（延伸版）
| Operations | Symbol | Definition |
|---|---|---|
| AND | $\cdot$ or $\wedge$ | 只有當兩個輸入都為真（True）時才回傳真（True）。 |
| OR | $+$ or $\lor$ | 如果至少有一個輸入為真（True），則回傳真（True）。 |
| NOT | $\overline{A}$ or $\rightharpoondown A$ or $\sim$A | 反轉狀態。 |
| XOR | $\oplus$ | 如果剛好奇數個輸入為真（True），則回傳真（True）。 |
| NAND | $\downarrow$ | 只有當兩個輸入都為真（True）時才回傳假（False）。 |
| NOR | $\uparrow$ | 如果至少一個輸入為真（True），則回傳假（False）。 |
| XNOR | $\leftrightarrow$ | 如果兩個輸入相等，則回傳真（True）。 |
XOR
XOR 的 X 為 exclusive，然後以下是他的真值表：
| A | B | $A \oplus B$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
電路圖：
Image Source：XOR Gate | Tutorial with examples, truth table,and downloadable assets – Hacky Labs
XOR 是怎麼來的呢？首先 XOR 的意義是兩個輸入不同才為真，相同為假，由此可推出布林代數式應該是 $x = (\overline{A} \cdot B)+(A+\overline{B})$ 。
兩個輸入其中一個是 1 輸出就是 1，這邊用到 AND 的概念，以 $\overline{A} \cdot B$ 為例，首先可以畫畫看他的真值表：
| A | B | $\overline{A} \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
其中可發現 0、1 輸出 1，其他都是 0，這樣就確保了 XOR 的第一個條件，而 $A+\overline{B}$ 的真值表則是做與他相反的輸入，就會變成 1、0 輸出 1，那這時候再把這兩個輸出結果 OR 起來，最後就會得到 XOR，請看以下的邏輯電路圖：
Image Source：設計CMOS邏輯：XOR，XNOR和變速箱門
你會看到 B 直直對過去會有個小小的圈圈，那個是 NOT 的省略方法，而 A 對到下面的 AND 也是如此，都是表示 $\overline{A}$ 或 $\overline{B}$ 的省略方法。
NAND
NAND 其實就是在 AND 的基礎下，在他的輸出端加上一個 NOT，就變成 NAND 了。
以下是他的真值表（把 AND 的真值表拿過來，然後輸出全部 NOT 一遍就得到了）：
| A | B | $A \downarrow B$ |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
以下圖示說明了 NAND 的由來：
Image Source：NAND and NOR | Spinning Numbers
NOR
NOR 的概念其實也跟 NAND 一樣，都是在輸出端加上 NOT。
以下是他的真值表：
| A | B | $A \uparrow B$ |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 0 |
以下圖示說明了 NOR 的由來：
Image Source：NAND and NOR | Spinning Numbers
XNOR
XNOR 也一樣，就在 XOR 的基礎下，在輸出端後面加上 NOT。
以下是他的真值表：
| A | B | $A \leftrightarrow B$ |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
電路符號就變這樣：
Image Source：設計CMOS邏輯：XOR，XNOR和變速箱門
布林代數式定律（Theorems / Laws）
- 同一律（Identity Law）：
- $A + 0 = A$
- $A \cdot 1 = A$
- 交換律（Commutative Law）：
- $A \cdot B = B \cdot A$
- $A + B = B + A$
- 結合律（Associative Law）：
- $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
- $(A + B) + C = A + (B + C)$
- 分配律（Distributive Law）：
- $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
- 反轉律（Inversion Law）：
- 註：經過兩次 NOT 還是自己。
- $\overline{\overline{A}} = A$
- 補數律（Complement Law）：
- $A + \overline{A} = 1$
- $A \cdot \overline{A} = 0$
- 冪等律（Idempotent Law）：
- $A + A = A$
- $A \cdot A = A$
- 笛摩根定理（De Morgan’s Laws）：
- $\overline{A \cdot B} = \overline{A} + \overline{B}$
- $\overline{A + B} = \overline{A} \cdot \overline{B}$
學這要幹嘛？可以簡化布林代數式，也更進一步去改善、精簡電路設計，降低開發成本。
補充說明：XOR 定律，基本上與布林代數式定律差不多，但些許地方有差別。
- 自反律（Self-Inverse Law）：
- $A \oplus A = 0$
- 交換律（Commutative Law）：
- $A \oplus B = B \oplus A$
- 結合律（Associative Law）：
- $A \oplus B \oplus C = A \oplus (B \oplus C) = (A \oplus B) \oplus C$
- 同一律（Identity Law）：
- $A \oplus 0 = A$
註：XOR 在密碼學領域有相當的用處，透過這些定律可以進行加密解密的動作。
簡易證明笛摩根定理（De Morgan’s Laws）
最簡單的方式就是使用真值表證明。
第一定理： $\overline{A \cdot B} = \overline{A} + \overline{B}$
| $A$ | $B$ | $A \cdot B$ | $\overline{A \cdot B}$ | $\overline{A}$ | $\overline{B}$ | $\overline{A} + \overline{B}$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
第二定理： $\overline{A + B} = \overline{A} \cdot \overline{B}$
| $A$ | $B$ | $A + B$ | $\overline{A + B}$ | $\overline{A}$ | $\overline{B}$ | $\overline{A} \cdot \overline{B}$ |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 |
利用布林代數式定律簡化邏輯電路
e.g. 1 畫出 $Y = AB + B +C$ 的邏輯電路圖。
首先要來簡化電路，之後才好畫圖。先看 $AB + B$ ，這邊可以用分配律化簡成 $B(A + 1)$ ，而 $A + 1$ 是 1，因此 $B(A + 1) = B$ 。
再將得出的結果代回去原式 $Y = B + C$ ，就可得到簡化結果了。
以下是這個範例的邏輯電路圖畫法（畫的稍醜不好意思）：
e.g. 2 簡化電路 $F = A \cdot (A + \overline{A})$ 。
根據補數律的 $A + \overline{A} = 1$ ，可簡化成 $F = A \cdot 1$ ，最終結果就是 $F = A$ 。
e.g. 3 畫出 $G = \overline{A + B} \cdot \overline{C}$ 的邏輯電路圖。
遇到這種題目一定要先簡化，首先 $\overline{A + B}$ 的部分用到笛摩根定理，可得到 $\overline{A} \cdot \overline{B}$ 。最後代回去原式即得 $G = \overline{A} \cdot \overline{B} \cdot \overline{C}$ 。
而以下是該範例的邏輯電路圖畫法：
也可以畫成這樣：
由於篇幅原因，故到此為止，下一節將繼續學習什麼是 Product of Sum、Sum of Product、Adder、Full-Adder、Half-Adder 等等。
總結
一、布林代數（Boolean Algebra）
布林代數是數學的分支，用於處理真（1）與假（0）的邏輯運算。
三種基本運算：
- AND（ $\cdot$ ）：所有輸入為 1，輸出才為 1。
- OR（ $+$ ）：只要有一個輸入為 1，輸出為 1。
- NOT（ $\overline{}$ ）：將輸入反轉，0→1、1→0。
所有的邏輯閘都可以用 AND、OR、NOT 這些邏輯閘所組成。
二、真值表（Truth Table）
真值表列出所有輸入組合的輸出結果。
若輸入數為 $n$ ，則有 $2^n$ 種輸出組合。
以下是 AND、OR、NOT 個別的真值表：
AND（ $A \cdot B$ ）：
| A | B | $A \cdot B$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
OR（ $A + B$ ）：
| A | B | $A + B$ |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 1 |
NOT（ $\overline{A}$ ）：
| A | $\overline{A}$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
三、邏輯電路與布林代數的對應
邏輯電路可直接轉換成布林代數式，反之亦然：
- $AND \rightarrow Y = A \cdot B$
- $OR \rightarrow Y = A + B$
- $NOT \rightarrow Y = \overline{A}$
四、進階邏輯運算
| 運算 | 符號 | 定義 |
|---|---|---|
| XOR | ⊕ | 兩輸入不同為真 |
| NAND | ↓ | AND 輸出後面加上 NOT |
| NOR | ↑ | OR 輸出後面加上 NOT |
| XNOR | ↔ | 兩輸入相同為真 |
五、布林代數基本定律（Laws of Boolean Algebra）
- 同一律（Identity Law）：
- $A + 0 = A$
- $A \cdot 1 = A$
- 交換律（Commutative Law）：
- $A \cdot B = B \cdot A$
- $A + B = B + A$
- 結合律（Associative Law）：
- $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
- $(A + B) + C = A + (B + C)$
- 分配律（Distributive Law）：
- $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
- 反轉律（Inversion Law）：
- 註：經過兩次 NOT 還是自己。
- $\overline{\overline{A}} = A$
- 補數律（Complement Law）：
- $A + \overline{A} = 1$
- $A \cdot \overline{A} = 0$
- 冪等律（Idempotent Law）：
- $A + A = A$
- $A \cdot A = A$
- 笛摩根定理（De Morgan’s Laws）：
- $\overline{A \cdot B} = \overline{A} + \overline{B}$
- $\overline{A + B} = \overline{A} \cdot \overline{B}$
六、補充 XOR 定律（XOR Laws）
- 自反律（Self-Inverse Law）：
- $A \oplus A = 0$
- 交換律（Commutative Law）：
- $A \oplus B = B \oplus A$
- 結合律（Associative Law）：
- $A \oplus B \oplus C = A \oplus (B \oplus C) = (A \oplus B) \oplus C$
- 同一律（Identity Law）：
- $A \oplus 0 = A$
七、笛摩根定理證明
透過列出各輸入組合可驗證兩條定理的等價性，也就是用真值表去證明即可。
參考資料
Boolean Algebra - GeeksforGeeks
Logic Circuit: AND Circuit | 臺灣東芝電子零組件股份有限公司 | 台灣
XOR Gate | Tutorial with examples, truth table,and downloadable assets – Hacky Labs
