布林代數(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 的情況。
#離散數學 #布林代數







你可能感興趣的文章

6. Singleton

6. Singleton

Scrapy 和 Redis 分散式crawlers (蘋果日報為例)

Scrapy 和 Redis 分散式crawlers (蘋果日報為例)

DOM 相關筆記

DOM 相關筆記






留言討論