基礎邏輯電路（上）

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

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

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

布林代數式（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）

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

Logic Circuit: AND Circuit | 臺灣東芝電子零組件股份有限公司 | 台灣

XOR Gate | Tutorial with examples, truth table,and downloadable assets – Hacky Labs

設計CMOS邏輯：XOR，XNOR和變速箱門

真值表 - 維基百科，自由的百科全書

布林代數的基本運算原則-知識百科-三民輔考

Chapter2-數位邏輯-Digital Logical | PinJin’s Blog

互斥或閘 - 維基百科，自由的百科全書

3. 布林代數與邏輯閘 - HackMD

利用 XOR 對資料加密的原理淺談 - johnny860726的創作 - 巴哈姆特