數位邏輯與實習 Week 3 曾建勳

代數結構的假說

代數結構的假說

代數結構的假說 範例： 實數系與二元運算子( + )及(‧)形成實數域。實數域: 它是具有兩個二位元運算的元素集合，每一運算符號各具有上述第1項至第5項的性質，並且這兩個運算符號具有第6項的性質。 實數域是算術以及普通代數的基本。此運算符號及假設具有以下意義：

代數結構的假說

布林代數 (Boolean Algebra)的結構定義 一組元素的集合 B 與兩個二元運算子(+) 與(‧) 滿足E. V. Huntington (1904)假說: 布林代數對於運算元(+)與 (‧)具有封閉性 x, y Î B ' x+y ÎB 布林代數對於運算元(+)與 (‧)具有單位元素 0+x = x+0 = x 1‧x = x‧1= x 布林代數對於運算元(+)與 (‧)具有交換律 x+y = y+x x‧y = y‧x 分配律 布林代數中運算元(‧) 對運算元(+)具有分配律: x‧(y+z)=(x‧y)+(x‧z)

布林代數 (Boolean Algebra)的結構定義 布林代數中運算元(+)對運算元(‧)具有分配律: x+(y‧z)=(x+y)‧(x+z)  x Î B, $ x’Î B (x的補數) ：補數的唯一性 ' x+x’= 1與 x‧x’=0 $ 至少 x, y Î B ' x ≠ y Note： 布林代數的結構未定義（但滿足）結合律 運算元(+)對運算元(‧)的分配律在普通代數裡無此特性 對加法與乘法無反元數無減法與除法 普通代數無補數 實數域內討論的集合是一個無限集合； 布林代數的集合雖有類似實數域集合但其只有包含兩個元數: 0 、1

二值布林代數 B = {0,1}, operator: (+) 、(-) 運算原則 適用Huntington的假說： 封閉性 ( ) 封閉性 ( ) 兩個單位元素 (identity elements)滿足假說2: (1) +: 0是(+)的單位元素 (2)‧: 1是(‧)的單位元素 AND OR NOT

二值布林代數 交換律 (運算表的對稱性) 分配律: 滿足 a. b. 同理可得

二值布林代數 補數 二值布林代數只有兩個固定元素0和1, 其中 0 ≠ 1 註記 x+x'=1: 0+0'=0+1=1; 1+1'=1+0=1 x‧x'=0: 0‧0'=0‧1=0; 1‧1'=1‧0=0 二值布林代數只有兩個固定元素0和1, 其中 0 ≠ 1 註記 二值布林代數是兩個元素的集合 兩個二元運算子 + : OR運算; ‧ : AND運算 一個補數運算子: NOT運算 二值布林代數亦被稱為「二進位元邏輯」(binary logic)

布林代數的基本定理與性質 對偶性(duality principle): 在任一布林代數表示式中互換運算子與單位元數，表示式(對偶式)仍然成立 E.g.: OR和AND的運算子互換，0與1互換對偶式(dual) 基本定理（符合對偶原理）： （6定理4假說） (dual)

布林代數的基本定理證明 定理 1(a): x+x = x 定理1(b): x．x = x x+x = (x+x) 1 由假說: 2(b) = (x+x) (x+x') 5(a) = x+xx' 4(b) = x+0 5(b) = x 2(a) 定理1(b): x．x = x xx = x x + 0 2(a) = xx + xx' 5(b) = x (x + x') 4(a) = x 1 5(a) = x 2(b) DUALITY DUALITY

布林代數的基本定理證明 定理2 定理 3: (x')' = x x + 1 = 1 (x + 1) 2(b) = (x + x')(x + 1) 5(a) = x + x' 1 4(b) = x + x' 2(b) = 1 5(a) x ． 0 = 0 由對偶性 定理 3: (x')' = x 由假說5 定義了 x的補數, x + x‘ = 1 與 x x’ = 0 (補數唯一性) x' 的補數為x， 亦即 (x') ' =x

布林代數的基本定理證明 定理6 法二:利用真值表證明: x + xy = x ． 1 + xy 2(b) = x (1 +y) 4(a) = x ． 1 2(a) = x 2(b) x (x + y) = x 由對偶性 法二:利用真值表證明:

布林代數的基本定理證明 迪摩根定理(使用真值表驗證) (x+y)' = x' y' (x y)' = x' + y'

布林代數的基本定理與性質 運算子之優先順序: 括號； NOT(補數)； AND； OR 範例 x y' + z (x y + z)'

布林函數 布林函數的組成: 範例: 利用真值表來表示 二元變數 二元運算子OR 與AND 單元運算子NOT 括號 結果:1 or 0 F1= x y z' F2 = x + y'z F3 = x' y' z + x' y z + x y' F4 = x y' + x' z

布林函數 函數內變數為 n 個時，其真值表共有 2n 列。 布林函數表示成真值表時只有一種形式，但若是表示成代數形式，則可以用很多種形式來表示 E.g., F3 = F4

布林函數之邏輯電路圖 F2 F3 利用邏輯閘實現 化簡 F3=F4 F4 較為經濟 F4

代數演算 當布林函數利用邏輯閘來實現時，每一個項需要一個閘，而項中的變數即為閘的輸入。我們定義一個文字字元 (literal) 做為: 項:每一項利用一個邏輯閘來實現 藉由縮減布林表示式中之項數、文字數或兩者，通常可以得到一個較簡單的電路。布林代數的演算主要是將一個表示式簡化以得到一個比較簡單的電路。 困難點 (無特定法則可遵循) 例題 2-1: x(x'+y) = xx' + xy = 0+ xy = xy x+x‘y = (x+x’)(x+y) = 1 (x+y) = x+y (可由函數1的對偶性可得) (x+y)(x+y‘) = x+xy+xy’+yy‘ = x(1+y+y’) = x (可由假說4(b)求得)

代數演算 例題 2-1: x'y'z + x'yz + xy' = x'z(y'+y) + xy' = x'z + xy‘ xy + x'z + yz = xy + x'z + yz(x+x') = xy + x'z + yzx + yzx' = xy(1+z) + x'z(1+y) = xy +x'z (x+y)(x‘+z)(y+z) = (x+y)(x’+z) (由函數5的對偶性可得) Note: 函數5及函數6為重合/一致定理(consensus theorem) 增加文字數可得到 簡化的表示式

一個函數的補數 函數 F 的補數為 F'，可以由 F 值中之0換成1，1換成0求得。 一個函數的補數可以利用迪摩根定理而以代數的方式推導出。 E.g.: 3個變數 (A+B+C)' = (A+X)' 令 B+C = X = A'X' 由迪摩根定理 = A'(B+C)' = A'(B'C') 由迪摩根定理 = A'B'C' 結合律 通式 (A+B+C+ ... +F)' = A'B'C' ... F' (ABC ... F)' = A'+ B'+C'+ ... +F‘ E.g.: x'yz' + x'y'z => (x'+y+z') (x'+y'+z) (對偶性) => (x+y'+z)(x+y+z') 求出函數的對偶函數 然後將對偶函數中的 文字取補數

一個函數的補數 範例2-2

一個函數的補數 範例2-3