布林代數（Boolean Algebra）

布林代數（boolean algebra）

布林代數是基於布林值「0／1」進行的運算，可代表電腦中央處理器（CPU）的運作邏輯，了解布林代數有助於設計出更好的電路。

基本規則

布林運算的規則與「邏輯運算」及「集合運算」皆十分相似，可互相對照。

數值

布林運算的狀態數值僅有「1」、「0」兩個，可分別與邏輯運算的「真（T）」、「假（F）」對照：

運算元

一元運算元包含「非（NOT／'）」，表示一集合的「補集」。

二元運算元包含「或（OR／∨）」、「且（AND／∧）」及「互斥或（XOR／⊕、⊻）」，分別可對應集合中的「聯集（∪）」、「交集（∩）」與「對稱差集（Δ）」，運算符號各自以「+」、「·」、「⊕」表示。

性質

布林運算包含下列七項性質：

其中的「本體性」與「互補性」的運算規則較不直觀，可以對照右方欄的邏輯運算規則理解。

電路圖（circuit diagram）

在理解布林運算的規則與性質後，可以將其概念應用至電路圖，布林值的「1」在圖中代表通電狀態、「0」代表未通電狀態，再搭配不同的邏輯閘（logic gate），即可在電路圖中實現布林運算。

反閘／反向器（NOT gate / inverter）

輸出電平恆與輸入電平相反。

及閘（AND gate）

所有輸入電平均為「1」時，才會輸出「1」；若輸入端電平有為「0」者，則輸出「0」。

或閘（OR gate）

只要有任何輸入電平為「1」，就會輸出「1」；僅在所有輸入端電平均為「0」時，才輸出「0」。

互斥或閘（XOR gate）

輸入電平值不同時才會輸出「1」。

反及閘（NAND gate）

所有輸入電平均為「1」時，才會輸出「0」；若輸入端電平有為「0」者，則輸出「1」。

反或閘（NOR gate）

所有輸入電平均為「0」時，才會輸出「1」；若輸入端電平有為「1」者，則輸出「0」。

反互斥或閘（XNOR gate）

輸入電平值相同時才會輸出「1」。

真值表回推布林代數：DNF & CNF

將布林代數轉為真值表時，可以透過電路圖得知不同輸入組合的輸出結果。例如有下列布林代數：

若要轉為真值表，可以先繪製成下列電路圖：

兩輸入電平的不同組合可形成不同的輸出結果如下：

依照上述電路圖結果，可得下列真值表：

但若要從真值表回推布林代數呢？共有「析取範式（DNF）」與「合取範式（CNF）」兩種方法。

析取範式（disjunctive normal form, DNF / sum of products）

觀察對象為輸出值為「1」者，以上述真值表為例，共會觀察下表中標黃底的兩列：

從標黃底的兩列可求得下列布林代數：

從上式應不難理解為何 DNF 又被稱為「積之和（sum of products）」。

若要進一步化簡，可以將 x₂ 提出，改為下式：

根據布林代數的「互補性（complement property）」，括弧中的值為 1，可再化簡為下式：

由此可看出，僅有 x₂ 會影響輸出結果。

合取範式（conjunctive normal form, CNF / product of sums）

跟 DNF 相反，CNF 觀察的是輸出值為「0」者，故改為觀察下表中標藍底的兩列：

從標藍底的兩列可求得下列布林代數：

根據「迪摩根定律」，可將等號兩邊否定如下：

等號右側變成單純的輸出值，等號左側可再進行運算如下：

從上式應不難理解為何 CNF 又被稱為「和之積（product of sums）」。

若要進一步化簡，可以將 +x₂ 提出，並套用交換律，如下式：

根據布林代數的「互補性（complement property）」，小括弧中的值為 1，可再化簡為下式：

最後發現輸出值僅與 x₂ 有關，跟 DNF 求得的結果相同。

邏輯電路設計

有了上述邏輯閘與布林代數觀念，我們就可以設計邏輯電路，幫助我們完成運算。

加法器（adder）

在數位電路中，「加法器」用以進行加法運算，主要以二進制（binary）運行，逢二進一位，十進制中的 1~10 與之對照如下：

為什麼要用二進制呢？因為在電路中，只能判斷「有」通電、還是「沒有通電」，用「1」代表通電、「0」代表沒有通電，如此才能用電協助我們進行運算，現今的電子計算結構多半都以這個原理為基礎。

半加器（half adder）

現假設一電路有 x1 與 x₂ 兩輸入值，可能的輸出結果如下表：

二進制結果可以再拆成表格最右方的輸出值 c 與 s，c 代表進位（carry）、s 代表和（sum），如下表：

用電路圖表示如下：

究竟中間的「某種電路」要怎麼組成，才能夠跑出我們想要的結果呢？我們可以把輸出值 c 與 s 分開討論。

輸出值 c 的結果如下表：

因為輸出值只有一個為 1，可以使用 DNF 求出布林代數如下：

用電路圖表示如下：

再來看輸出值 s 的結果如下表：

輸出值 0、1 各半，用 DNF 或 CNF 都可以求布林代數。現假設用 DNF，求得的布林代數如下：

電路圖如下：

最後把 c 跟 s 的電路組合起來，就是「半加器」如下：

用「AND 閘」與「OR 閘」組成的半加器

依序檢查不同 x1 與 x2 的值，可發現其輸出的 c 跟 s 皆符合預期結果。

如果將 s 改用「XOR 閘」，可簡化電路圖如下：

一樣可以檢查不同 x1 與 x2 的值，可發現其輸出的 c 跟 s 依然皆符合預期結果。

全加器（full adder）

半加器能夠處理兩個一位元的二進制加法，也就是輸入值 x1 與 x2 都只有一位數，但如果輸入值有超過一位數，要如何運算呢？

現假設輸入值有兩位元，如 x1=11、x2=11，則 x1+x2 的結果如下：

如果輸入值有三位元，如 x1=111、x2=111 呢？

只要有進位，則前一個位元的 c 會與該位元的 s 相加，圖示如下，可留意每個算式下方的灰框處，當中代表每位元運算結果的來源：

在設計電路圖時，用相同的概念，將每個位元的 s 與前一個位元的 c 透過另一個半加器輸出，就形成可供多位元二進制運算的「全加器」。

藍框的範圍就是一位元的全加器，亦可用下列圖示表示：

與半加器最大的差別是，除了既有的兩個輸入值，另有前一位元的一個輸入值「ci-1」。

若要進行多位元的運算，全加器當中需有更多半加器組合。

最小化（minimization）

接下來的目標是要簡化電路，讓邏輯閘更少、電路更簡單，使 CPU 可以在維持相同的效能下，耗費更少電力、也佔用更少硬體空間。

卡諾圖（K-map /Karnaugh map / KM）

卡諾圖是真值表的變形，可以協助我們用圖示簡化布林運算，但元素數量若大於 5，複雜度也會大幅上升。

繪製卡諾圖共有下列四項規則：

1. 將所有相鄰的「1」圈起來。
2. 圈起「1」的個數以 2ⁿ 為單位，如 1、2、4 個。
3. 單一圈越大越好、圈的數量越少越好。
4. 圈的範圍可超出卡諾圖範圍。

現假設有下列真值表：

現在有 A、B、C 三個輸入值，可以先將 A、B 視為一體，與 C 比較，得下表：

接著將相鄰的 1 以 2ⁿ 為單位圈選起來：

將同顏色的區塊視為一組，可發現下列兩規則：

1. 黃色區塊：不論 A 的值為何，只要 B 為 1、C 為 0，則必為 1
2. 藍色區塊：不論 C 的值為何，只要 A 為 0、B 為 0，則必為 1

統整上述觀察，可知其電路可化簡如下：

如果改為將 B、C 視為一體，與 A 比較，可得下表：

再將所有相鄰的 1 以 2ⁿ 為單位圈選起來：

將同顏色的區塊視為一組，可發現下列兩規則：

1. 粉紅色區塊：不論 C 的值為何，只要 A 為 0、B 為 0，則必為 1
2. 綠色區塊：不論 A 的值為何，只要 B 為 1、C 為 0，則必為 1

統整上述觀察，可知其電路可化簡如下：

經過交換率，可發現結果與上述「將 A、B 視為一體」時相同。

小結

1. 布林代數數值：「1」代表「真（T）」、「0」代表「假（F）」。
2. 布林代數一元運算元：非（'）。
3. 布林代數二元運算元：或（+）、且（·）、互斥或（⊕）。
4. 布林代數性質：交換率、結合率、分配率、本體性、互補性、雙重否定、笛摩根定律。
5. 反閘（NOT gate）：輸出電平與輸入電平相反。
6. 及閘（AND gate）：所有輸入電平皆為 1 時，輸出 1。
7. 或閘（OR gate）：有任一輸入電平為 1 時，輸出 1。
8. 互斥或閘（XOR gate）：兩輸入電平不同時，輸出 1。
9. 反及閘（NAND gate）：輸入電平有 0 時，輸出 1。
10. 反或閘（NOR gate）：輸入電平均為 0 時，輸出 1。
11. 反互斥或閘（XNOR gate）：輸入電平皆相同時，輸出 1。
12. 析取範式（DNF）：觀察真值表中輸出值為 1 者，回推布林代數。
13. 合取範式（CNF）：觀察真值表中輸出值為 0 者，回推布林代數。
14. 半加器：處理兩個一位元變量的二進制運算器，輸出包含 s 與 c。
15. 全加器：處理多位元變量的二進制運算器，由多個半加器組成。
16. 最小化：將電路最簡化，使 CPU 效能為最高。
17. 卡諾圖（K-map）：利用圖實現電路最小化，適用元素個數 <5 的情況。