- 積項之和(Sun of Products,SOP)
ABC + ABC
AB + ABC + C D + D
AB + CD + EF + GK + HL
由一個或一個以上的AND項互相OR在一起
所組成
- 和項之積(Product of Sums,POS)
(A+ B +C)(A+C)
(A + B)(C + D)F
(A+C)(B + D)(B +C)
由一個或一個以上的OR項,AND在一
起所構成
英國數學家 George Boole 在 1854 年提出一套數學系統,來解決分析與設計數位電路之方
法,稱為布林代數 (Boolean Algebra)。
為了分析與設計數位系統,德國數學家 C. E. Shannon,在 1938 年發展一套兩值布林代數,
又被稱為交換代數 (Switching Algebra),並證明兩值布林代數,可充分代表數位系統之特性,
因此兩值布林代數已被發展成為數位系統分析與設計之數學基礎。
一、布林代數之性質
布林代數與一般演繹性之代數系統一樣,它亦可用一組基本元素之集合、一組運算子與許多未證明之定理與假設來定義。
布林代數可用下式來表示
B = f (w, x, y,z, ... )
其中 B 為輸出變數w、 x、 y、z等輸入變數之函數,即 B 之值是由w、 x、 y、z
等變數來決定。
構成布林代數之基本元素,僅被允許為 0 與 1 兩個可能元素之一,且所有數位系統之輸入與輸出變數,亦僅被限制為 0 與 1 兩個可能邏輯值之一,而這兩個邏輯值 (0 與 1) 是分別用來代表數位系統之低電位與高電位的電壓位準,故足以說明布林代數與數位系統間之直接對應關係。
二、布林代數之定義
兩值布林代數之輸入與輸出變數僅允許 0 與 1 兩個元素,因組成布林代數為此兩元素,即
B ={0,1}集合,與 AND ( 積;.)、OR ( 和;+ ) 與 NOT ( 反; ) 三個基本二元邏輯運算
子 (Binary Logic Operator) 所組成之代數架構。
布林代數亦應是一套完整之代數系統,故布林代數 B 應為 0 與 1 等兩值所組成之集合,即
B = {0,1},因此對於 B 中之所有元素,應滿足下列六項基本假設:
1. 封閉性(Closure Properties):對集合 B 中的任一個元素而言,經二元運算子運算後所得到
之元素,亦應為集合 B 之元素。
2. 單位元素 (Identity Unit):若集合 B 存在一個 0 或 1 之元素,則經邏輯運算後,會滿足
x ⋅1 = 1⋅ x = x與 x + 0 = 0 + x = x。
3. 交 換 律 (Commutative Law):對任意兩個元素x, y ∈ B 而言,若存在交換律,則應滿足
x ⋅ y = y ⋅ x與 x + y = y + x。
4. 分配律 (Distributive Law):對任意三個元素 x, y,z ∈ B而言,若存在分配律,則應滿足
x ⋅( y + z) = x ⋅ y + x ⋅z與 x + ( y ⋅z) = (x + y)⋅(x + z)。
5. 反元素 (Inverse Element):對集合 B 中的任一個元素而言,若存在x ∈ B,亦存在 x ∈ B。
6. 布林代數 B 至少存在兩個不同之元素x ⋅ y∈ B,且 x ≠ y,即兩值布林代數有兩個元素 1
與 0,且1 ≠ 0。
證明假說(4)之真值表
三、布林代數之基本定理
接著列出許多常用之布林定理,並分為單變數與多變數兩個部分來討論如下:
1. 單變數布林定理
2. 多變數布林定理
狄摩根定律 (DeMorgan’s Theorem) 之變數,亦可適用於 n 個變數之布林代數式,即下面之布林等式亦可成立,即
(a) x + y + ...+ n = x ⋅ y ⋅ ... ⋅n
(b) x ⋅ y ⋅ ... ⋅n = x + y + ... + n