# 基礎邏輯電路（上）

[TOC]

歡迎你點入本篇文章，會促成我想做這篇的原因，主要是因為在上計概時，突然浮現很多靈感，跟一大堆的問題（~~教授，為什麼要講的這麼淺白呢？我想知道更多啊啊！~~），為了一次解決我所有的困惑，於是製作本篇文章。

若文章有任何疑點及錯誤的地方歡迎提出。

本篇文章主要作為個人學習用途，撰筆形式概要以筆記形式撰筆。另外本篇文章以入門為導向，若需詳細閱讀相關學門，請搜尋「數位系統導論」或「數位系統設計」。

## 布林代數式（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 | 臺灣東芝電子零組件股份有限公司 | 台灣](https://toshiba.semicon-storage.com/tw/semiconductor/knowledge/e-learning/micro-intro/chapter1/logic-circuit-and-circuit.html)

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$ <br> 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](https://hackylabs.com/blogs/engineering/xor-gate?srsltid=AfmBOorjY5IqpeWkgtIHvw-90vIxWhsrN89eybFBys5UmVP6lLRs3oHS&shpxid=c08ddd86-897d-4a1b-9941-e1eb224acd63)

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和變速箱門](https://www.ic-components.tw/blog/designing-cmos-logic-xor,xnor,and-transmission-gates.jsp)

你會看到 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](https://spinningnumbers.org/a/logic-nand-nor.html)

### 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](https://spinningnumbers.org/a/logic-nand-nor.html)

### 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和變速箱門](https://www.ic-components.tw/blog/designing-cmos-logic-xor,xnor,and-transmission-gates.jsp)

## 布林代數式定律（Theorems / Laws）

1. 同一律（Identity Law）：
- $A + 0 = A$
- $A \cdot 1 = A$
2. 交換律（Commutative Law）：
- $A \cdot B = B \cdot A$
- $A + B = B + A$
3. 結合律（Associative Law）：
- $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
- $(A + B) + C = A + (B + C)$
4. 分配律（Distributive Law）：
- $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
5. 反轉律（Inversion Law）：
- 註：經過兩次 NOT 還是自己。
- $\overline{\overline{A}} = A$
6. 補數律（Complement Law）：
- $A + \overline{A} = 1$
- $A \cdot \overline{A} = 0$
7. 冪等律（Idempotent Law）：
- $A + A = A$
- $A \cdot A = A$
8. 笛摩根定理（De Morgan's Laws）：
- $\overline{A \cdot B} = \overline{A} + \overline{B}$
- $\overline{A + B} = \overline{A} \cdot \overline{B}$

學這要幹嘛？可以簡化布林代數式，也更進一步去改善、精簡電路設計，降低開發成本。

---

補充說明：XOR 定律，基本上與布林代數式定律差不多，但些許地方有差別。

1. 自反律（Self-Inverse Law）：
- $A \oplus A = 0$
2. 交換律（Commutative Law）：
- $A \oplus B = B \oplus A$
3. 結合律（Associative Law）：
- $A \oplus B \oplus C = A \oplus (B \oplus C) = (A \oplus B) \oplus C$
4. 同一律（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）的邏輯運算。

三種基本運算：

1. AND（ $\cdot$ ）：所有輸入為 1，輸出才為 1。
2. OR（ $+$ ）：只要有一個輸入為 1，輸出為 1。
3. 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）

1. 同一律（Identity Law）：
- $A + 0 = A$
- $A \cdot 1 = A$
2. 交換律（Commutative Law）：
- $A \cdot B = B \cdot A$
- $A + B = B + A$
3. 結合律（Associative Law）：
- $(A \cdot B) \cdot C = A \cdot (B \cdot C)$
- $(A + B) + C = A + (B + C)$
4. 分配律（Distributive Law）：
- $A \cdot (B + C) = (A \cdot B) + (A \cdot C)$
5. 反轉律（Inversion Law）：
- 註：經過兩次 NOT 還是自己。
- $\overline{\overline{A}} = A$
6. 補數律（Complement Law）：
- $A + \overline{A} = 1$
- $A \cdot \overline{A} = 0$
7. 冪等律（Idempotent Law）：
- $A + A = A$
- $A \cdot A = A$
8. 笛摩根定理（De Morgan's Laws）：
- $\overline{A \cdot B} = \overline{A} + \overline{B}$
- $\overline{A + B} = \overline{A} \cdot \overline{B}$

### 六、補充 XOR 定律（XOR Laws）

1. 自反律（Self-Inverse Law）：
- $A \oplus A = 0$
2. 交換律（Commutative Law）：
- $A \oplus B = B \oplus A$
3. 結合律（Associative Law）：
- $A \oplus B \oplus C = A \oplus (B \oplus C) = (A \oplus B) \oplus C$
4. 同一律（Identity Law）：
- $A \oplus 0 = A$

### 七、笛摩根定理證明

透過列出各輸入組合可驗證兩條定理的等價性，也就是用真值表去證明即可。

## 參考資料

[Boolean Algebra - GeeksforGeeks](https://www.geeksforgeeks.org/digital-logic/boolean-algebra/)

[Logic Circuit: AND Circuit | 臺灣東芝電子零組件股份有限公司 | 台灣](https://toshiba.semicon-storage.com/tw/semiconductor/knowledge/e-learning/micro-intro/chapter1/logic-circuit-and-circuit.html)

[XOR Gate | Tutorial with examples, truth table,and downloadable assets – Hacky Labs](https://hackylabs.com/blogs/engineering/xor-gate?srsltid=AfmBOorjY5IqpeWkgtIHvw-90vIxWhsrN89eybFBys5UmVP6lLRs3oHS&shpxid=c08ddd86-897d-4a1b-9941-e1eb224acd63)

[設計CMOS邏輯：XOR，XNOR和變速箱門](https://www.ic-components.tw/blog/designing-cmos-logic-xor,xnor,and-transmission-gates.jsp)

[真值表 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E7%9C%9F%E5%80%BC%E8%A1%A8)

[布林代數的基本運算原則-知識百科-三民輔考](https://www.3people.com.tw/%E7%9F%A5%E8%AD%98/%E5%B8%83%E6%9E%97%E4%BB%A3%E6%95%B8%E7%9A%84%E5%9F%BA%E6%9C%AC%E9%81%8B%E7%AE%97%E5%8E%9F%E5%89%87/%E5%B0%B1%E6%A5%AD%E8%80%83%E8%A9%A6-%E5%8F%B0%E5%8C%97%E6%8D%B7%E9%81%8B%E5%85%AC%E5%8F%B8/269a6725-a529-4ad3-99cb-72df9d9bee31)

[Chapter2-數位邏輯-Digital Logical | PinJin's Blog](https://pingjing0628.github.io/2021/04/01/Chapter2-%E6%95%B8%E4%BD%8D%E9%82%8F%E8%BC%AF-Digital-Logical/)

[互斥或閘 - 維基百科，自由的百科全書](https://zh.wikipedia.org/zh-tw/%E5%BC%82%E6%88%96%E9%97%A8)

[3. 布林代數與邏輯閘 - HackMD](https://hackmd.io/@siniu-thesis/DLD-VHDL-kl/https%3A%2F%2Fhackmd.io%2F%40siniu-thesis%2FDLD-VHDL-kl_03)

[利用 XOR 對資料加密的原理淺談 - johnny860726的創作 - 巴哈姆特](https://home.gamer.com.tw/artwork.php?sn=2949476)