布林代数的基本定理证明.ppt

* * * * * * * * * * * * * * * * * * Digital Circuits 數位邏輯與實習 Week 3 曾建勳 2-* 代數結構的假說 2-* 代數結構的假說 2-* 代數結構的假說 實數系與二元運算子( + )及(?)形成實數域。實數域: 它是具有兩個二位元運算的元素集合，每一運算符號各具有上述第1項至第5項的性質，並且這兩個運算符號具有第6項的性質。 實數域是算術以及普通代數的基本。此運算符號及假設具有以下意義： 範例： 2-* 代數結構的假說 2-* 布林代數 (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) 2-* 布林代數中運算元(+)對運算元(?)具有分配律: 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 布林代數 (Boolean Algebra)的結構定義 2-* 二值布林代數 B = {0,1}, operator: (+) 、(-) 運算原則 適用Huntington的假說： 封閉性 ( ) 兩個單位元素 (identity elements)滿足假說2: (1) +: 0是(+)的單位元素 (2)?: 1是(?)的單位元素 AND OR NOT 2-* 交換律 (運算表的對稱性) 分配律: 滿足 a. b. 同理可得 二值布林代數 2-* 補數 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) 二值布林代數 2-* 布林代數的基本定理與性質 對偶性(duality principle): 在任一布林代數表示式中互換運算子與單位元數，表示式(對偶式)仍然成立 E.g.: OR和AND的運算子互換，0與1互換?對偶式(dual) 基本定理（符合對偶原理）： （6定理4假說） (dual) 2-* 定理 1(a): 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-* 定理2 x + 1 = 1 (x + 1) 2(b) = (x + x)(x + 1) 5(a) = x + x 1 4(b) = x + x 2(b)