Microsoft PowerPoint - 4＿布林代數與邏輯簡化_1_UNANS

邏輯設計 布林代數與邏輯簡化 王宏祺講師 Department of Computer and Communication Kun San University Tainan, Taiwan, R.O.C. Mar. 30, 2011 1

4-1 布林運算與表示式 4-2 布林代數的定律與法則 4-3 狄摩根定理 4-4 邏輯電路的布林分析法 4-5 利用布林代數來做簡化 4-6 布林表示式的標準形式 4-7 布林表示式與真值表 4-8 卡諾圖 4-9 SOP 卡諾圖簡化 4-10 POS 卡諾圖的簡化 4-11 數位系統應用實例 2

布林加法運算 布林加法運算與 OR 運算等效, 其基本法則與 OR 閘的 關係圖示如下 : 邏輯電路中, 和項是由 OR 運算所產生的, 不含 AND 運算 3

布林乘法運算 布林乘法和 AND 運算等效, 其基本法則與 AND 閘的 關係圖示如下 : 邏輯電路裡, 積項是由 AND 運算所產生的, 不含 OR 運算 4

4-2 布林代數的定律與法則 應用加法與乘法的交換律 應用加法與乘法的結合律 應用分配律 應用布林代數的 12 項基本運算法則 5

布林代數定律 結合律三個變數的加法結合律寫法如下 : A + (B + C) = (A + B) + C 三變數乘法結合律的寫法如下 : A(BC) = (AB)C 6

布林代數的運算法則 布林代數的基本法則 1. A 0 A 7. A A A 2. A 1 1 8. A A 0 3. A 0 0 9. A A 4. A 1 A 10. A AB A 5. A A A 11. A AB A B 6. A A 1 12. (A B)(A C) A BC A B 或 C 可代表單變數或組合變數 定律 (1) 交換律 : a. A+B = B+A b. A.B = B.A 定律 (2) 結合律 : a. (A+B)+C=A+(B+C) b. (A.B).C=A.(B.C) 定律 (3) 分配律 : a. A.(B+C)=AB+AC b. A+(B.C)=(A+B).(A+C) c. (D+A).(B+C)=DB+DC+AB+AC 定律 (4) 吸收律 : a. A+AB=A b. A+A'B=A+B 7

布林代數的運算法則 3. A 0 0 4. A 1 A 8

布林代數的運算法則 7. A A = A 8. A A 0 9

布林代數的運算法則 11. A AB A B 表 4-3 10

4-3 狄摩根定理 狄摩根定理以數學方式證明了 NAND 和輸入反相的 OR 閘以及 NOR 閘和輸入反相的 AND 閘之間的等效性 11

4-3 狄摩根定理 12

4-3 狄摩根定理 4-4 理 解 : 在表示式 WXYZ 和 W X Y Z 中應用狄摩根定 WXYZ W X Y Z W X Y Z W X Y Z 例題一在表示式中應用狄摩根定理 WXYZ 13

4-5 應用狄摩根定理 在下列各表示式中應用狄摩根定理 : (a) ( A B C) D (b) ABC DEF (c) AB CD EF 解 : (a) 設 A + B + C = X, D = Y 表示式 XY X Y 的形式, 可以寫成 : ( A B C) D 屬於 接著在 ( A B C) D A B C D A B C 部分使用狄摩根定理 A B C D ABC D 14

應用狄摩根定理 例 4-5 ( 續 ) (b) 設 ABC = X,DEF = Y 表示式 ABC DEF 屬於 X Y X Y 的形式, 可寫成 : ABC DEF ( ABC)( DEF) 接著, 在 ABC 和 DEF 兩項應用狄摩根定理 ( ABC)( DEF) ( A B C)( D E F) 15

應用狄摩根定理 例 4-5 ( 續 ) (c) 設 AB X, CD Y, EF = Z 表示式屬於 X Y Z X Y Z AB CD EF 的形式, 可寫成 : 接著, 在 AB CD EF ( AB)( CD)( EF),, 各項應用狄摩根定理 AB CD EF ( AB)( CD)( EF) ( A B)( C D)( E F) 16

例題一 1. 在下列各表示式中應用狄摩根定理 : 17

應用狄摩根定理 4-7 AB 以這個式子為起 點, 利用狄摩根定理和其它適用法則, 推導出 XNOR 閘 的表示式 解 : 解 XOR 閘的布林表示式為 AB 由取 XOR 閘表示式的補數開始, 再如下應用狄摩 根定理 : AB AB ( AB)( AB) ( A B)( A B) ( A B)( A B) 接著, 應用分配律和法則 8( A A 0) ) ( A B)( A B) AA AB AB BB AB AB 18

4-4 邏輯電路的布林表示式 例題二. 寫出下圖各邏輯電路的布林表示式 19

4-5 利用布林代數來做簡化 4-8 利用布林代數化簡這項表示式 : AB + A(B + C) + B(B + C) 解 : 下列步驟並非唯一方法 步驟 1. 表示式的第 2 和第 3 項使用分配律, 如下 : AB + AB + AC + BB + BC 步驟 2. 第 4 項應用法則 7 (BB = B) AB + AB + AC + B + BC 步驟 3. 前兩項應用法則 5 (AB + AB = AB) AB + AC + B + BC 20

4-5 利用布林代數來做簡化 例 4-8 ( 續 ) 步驟 4. 後兩項應用法則 10 (B + BC = B) AB + AC + B 步驟 5. 第 1 和第 3 項應用法則 10 (AB + B = B) B + AC 到這裡, 表示式已經盡可能的簡化了 一旦學得應用布林代數的經驗, 您就可以將數個步驟一併處理 21

例題二 2. 利用布林代數, 將下列表示式化簡 : 22

4-5 利用布林代數來做簡化 4-11 化簡下列布林表示式 : 解 : AB AC ABC 步驟 1. 第 1 項應用狄摩根定理 ( AB)( AC) ABC 步驟 2. 兩小括弧內項應用狄摩根定理 ( A B)( A C) ABC 步驟 3. 兩小括弧內項應用分配律 A A AC AB BC ABC 23

4-5 利用布林代數來做簡化 例 4-11 ( 續 ) 步驟 4. 第 1 項應用法則 7( A A A) 用法則 10 [ A B ABC AB(1 C) AB], 第 3 項和最後一項應 步驟 5. 第 1 項和第 2 項應用法則 10 [ A AC A(1 C) A] A AB BC 步驟 6. 第 1 項和第 2 項應用法則 10 [ A AB A(1 B) A] A BC 24

4-5 利用布林代數來做簡化 4-9 化簡下列布林表示式 : 注意, 中括弧和小括弧是一樣的 : 括弧內項要與括弧 外項相乘 ( 做 AND 運算 ) 解 : [ AB( C BD) ABC ] 步驟 1. 中括弧內項應用分配律 ( ABC ABBD A B) C 步驟 2. 小括弧內第 2 項應用法則 8 ( BB 0) ( ABC A 0 D A B) C 25

4-5 利用布林代數來做簡化 例 4-9 ( 續 ) 步驟 3. 小括弧內第 2 項應用法則 3 (A 0 D = 0) 步驟 4. 小括弧內應用法則 1 ( 除去 0) 步驟 5. 應用分配律 ( ABC 0 A B) C ( ABC A B) C ABCC A BC 步驟 6. 第 1 項應用法則 7 (CC = C) ABC A BC 26

4-5 利用布林代數來做簡化 例 4-9 ( 續 ) 步驟 7. 因式分解出 BC BC( A A) 步驟 8. 應用法則 6( A A 1) BC 1 步驟 9. 應用法則 4 ( 消去 1) BC 27

例題三 3. 利用布林代數, 將下列表示式化簡 : 28

積之和形式 (SOP) 積項為由字母 ( 變數或其補數 ) 乘積 ( 布林乘法運算 ) 所組成的項 當兩個以上的積項以布林加法運算執行加法時, 所得的表示式就是積之和 (sum-of-products, SOP) 如下列各式 : AB ABC ABC CDE BC D AB ABC AC 29

布林表示式的範圍 積之和形式 (SOP) 一般布林表示式的集合是指表示式中 所包含, 不管是補數或非補數形式的變數組 例如, 表示 式 AB ABC ABC CDE BCD 實現 SOP 表示式 的範圍合就是變數 A B C, 而表示式 的範圍就是 A B C D E 等變數 30

4-12 一般表示式轉換成 SOP 形成 將下列布林表示式轉換成 SOP 形式 : (a)ab + B(CD + EF) (b)(a + B)(B + C + D) (c) 解 : (a)ab + B(CD + EF) = AB + BCD + BEF (b)(a + B)(B + C + D) = AB + AC + AD + BB + BC + BD (c) ( A B) C ( A B) C ( A B) C ( A B) C AC BC 31

例題四 4. 將下列表示式轉換成積之和 (SOP) 的形式 : 32

標準 SOP 形式 將積項轉換成標準 SOP SOP 表示式中的每個積項未必包含範圍集合內所有變數, 這些積項可以擴充成每個都包含所有集合內變數或其補數的標準形式 33

標準 SOP 形式 4-13 將下列布林表示式轉換成標準 SOP 形式 : 解 : 此 SOP 表示式之範圍為 A B C D 一次處理一項 第一項中少了變數 D 或 D, 所以將第一項乘上 D D, 如下 : 這樣就產生了兩個標準積項 第二項, A B, 缺少了變數 C 或 C 和 D 或 D, 所以先如下 將第二項乘上 C C: ABC A B ABCD ABC ABC ( D D) ABCD ABC D A B AB( C C) ABC ABC 34 ABC

標準 SOP 形式 例 4-13 ( 續 ) 得到的兩個積項仍少了變數 D 或 D D, 如下 : D, 所以將這兩項分別乘上 這樣就得到四個標準積項 第三項, ABCD, 已經是標準形式了 原表示式的標準 SOP 形式如下 : A B ABC ABC ABC( D D) ABC( D D) ABCD ABCD ABCD ABCD ABC AB ABCD ABCD ABCD ABCD ABCD ABCD ABCD ABCD 35

例題五 5. 將問題 22 中的各 SOP 表示式轉換成標準 SOP 形式 ( a) AB CD ( b) ABD ( c) A BD 36

標準 SOP 形式 4-14 解 : 求出使下列標準 SOP 表示式等於 1 的二進位值 : ABCD ABCD ABCD 在 A = 1, B = 1, C = 1 且 D = 1 時,ABCD 項會等於 1 ABCD = 1 1 1 1 = 1 在 A = 1, B 1, C 1, D = 1 時, ABCD項等於 1 AB CD 10 01 1111 1 37

標準 SOP 形式 例 4-14 ( 續 ) 在 A 1, B 1, C 1, D 1時, A BCD項等於 1 這三個積項任一項或全部等於 1 時,SOP 表示式就等於 1 38

和之積形式 和項為由字母和 ( 布林加法 ) 所組成的項 兩個以上的和項相乘時, 所得的表示式就是和之積 (product-ofsum, POS) 下列為其實例: ( A B)( A B C) ( A B C)( C D E)( B C D) ( A B)( A B C)( A C) 39

標準 POS 形式 標準 POS 表示式是指範圍集合內的所有變數都會出現 在表示式的各個和項中 例如, ( A B C D)( A B C D)( A B C D) 就是個標準 POS 表示式 40

標準 POS 形式 4-15 將下列布林表示式轉換成標準 POS 形式 : 解 : 此 POS 表示式範圍為 A B C D 的集合 一次處理一 項 第一項 A B C少了變數 D 或 D, 所以加入 DD並應 用法則 12, 如下 : 第二項 B C D 少了變數 A 或, 所以加入並應用準則 12, 如下 : ( A B C)( B C D)( A B C D) A B C A B C DD ( A B C D)( A B C D) B C D B C D AA ( A B C D)( A B C D) 41

標準 POS 形式 例 4-15 ( 續 ) 第三項 A B C D 的標準 POS 形式如下 : ( A B C)( B C D)( A B C D) 已經是標準形式了 故原表示式 ( A B C D)( A B C D)( A B C D)( A B C D)( A B C D) 42

標準 POS 形式 4-16 解 : 求出使下列標準 POS 表示式等於 0 的二進位變數值 ( A B C D)( A B C D)( A B C D) 在 A = 0, B = 0, C = 0, D = 0 時,A + B + C + D 等於 0 A + B + C + D = 0 + 0 + 0 + 0 = 0 在 A = 0, B 0, C 0, D = 0 時, A B C D 0 A B C D 0 1 1 0 0 0 0 0 0 43

標準 POS 形式 例 4-16 ( 續 ) A B C D 在 A = 1, B = 1, C = 1, D = 1 時, A B C D 1 1 1 1 0 0 0 0 0 上述三項中任一項等於 0, 就會使此 POS 表示式等於 0 0 44

4-17 將標準 SOP 轉換成標準 POS 將下列 SOP 表示式轉換成等效的 POS 表示式 : A B C ABC ABC ABC ABC 解 : 估算方式如下 : 000 + 010 + 011 + 101 + 111 3 此表示式的範圍集合含有三個變數, 所以總共有 8 種 (2 ) 可能的組合 這個 SOP 表示式含有其中的 5 種, 所以 POS 必定含有其它 3 種, 即 001,100, 和 110 記住, 這些就是使和項為 0 的二進位值 其等效 POS 表示式為 : ( A B C)( A B C)( A B C) 45

例題六 6. 將下面各標準 SOP 表示式轉換成標準 POS 形式 ( aabc ) ABC ABC ABC ( babc ) ABC ABC () c ABC ABC ABC 46

4-18 解 : 將 SOP 表示式轉換成真值表格式 建立標準 SOP 表示式 A BC AB C ABC 的真值表 此表示式有三個變數, 所以變數的二進位值共有 8 種可能組合, 見表 4-6 左邊三個欄位 使表示式各積項等 於 1 的二進位值分別為 : A BC: 001; A BC : 100;ABC : 111 如表所示, 在這幾個二進位值組合的輸出欄位中 填入 1 其餘二進位組合的輸出欄位中則填入 0 47

將 SOP 表示式轉換成真值表格式 例 4-18 ( 續 ) 表 4-6 輸入端輸出端 A B C X 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 48

例題七 7. 做出下列各 SOP 表示式的真值表 : 49

由真值表求出標準表示式 4-20 由表 4-8 的真值表求出標準 SOP 表示式, 及其等效的 標準 POS 表示式 表 4-8 輸入端輸出端 A B C X 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 1 1 1 50

由真值表求出標準表示式 例 4-20 ( 續 ) 解 : 輸出欄位中共有四個 1, 其對應的二進位數為 011,100,110, 和 111 將這些二進位數如下轉換成積項 : 011 ABC 100 ABC 110 111 ABC ABC 得到輸出 X 的標準 SOP 表示式為 : X ABC ABC ABC ABC 51

由真值表求出標準表示式 例 4-20 ( 續 ) 至於 POS 表示式, 則看輸出為 0 的二進位數 000,001, 010, 和 101 將這些二進位數如下轉換成和項: 000 A B C 001 A B C 010 A B C 101 A B C 得到輸出 X 的標準 POS 表示式為 : X ( A B C)( A B C)( A B C)( A B C) 52

4-8 卡諾圖 卡諾圖是有系統的簡化布林表示式的方法 做出 3 4 個變數的卡諾圖 求出卡諾圖中各單位的二進位值 求出卡諾圖中各單位所代表的標準積項 53

4 個變數的卡諾圖 4 個變數的卡諾圖是由 16 個小單位排列而成的 54

4-9 SOP 卡諾圖簡化 卡諾圖用於簡化布林表示式至其最簡形式 最小 SOP 表示式含有最少數目之積項, 每項中之變數亦為最少 55

標準 SOP 表示式轉換至卡諾圖 4-21 解 : 將下列標準 SOP 表示式轉換成卡諾圖 : A BC ABC ABC ABC 將表示式如下換成二進位值 在圖 4-24 的 3 變數卡 諾圖中, 代表表示式中各標準積項的方格內填入 1 A BC ABC ABC ABC 0 01 010 110 111 56

標準 SOP 表示式轉換至卡諾圖 例 4-21 ( 續 ) 圖 4-24 57

4-23 解 : 將非標準 SOP 表示式轉換成卡諾圖 將下列 SOP 表示式做成卡諾圖 : A AB ABC 很明顯, 此 SOP 表示式並非標準形式, 因為並非各 積項都有三個變數 第一項中少了兩個變數, 第二項中 少了一個變數, 第三項則是標準形式 先將各積項展開 成數字 : A AB ABC 000 100 110 001 1 01 010 011 58

將非標準 SOP 表示式轉換成卡諾圖 例 4-23 ( 續 ) 對照所得的各個二進位數, 在圖 4-26 之 3 變數卡諾圖 的適當方格內填入 1 圖 4-26 59

SOP 表示式的卡諾圖化簡法 將填 1 的項目分組用圈出含有 1 的相鄰方格的方法, 在卡諾圖上將填有 1 的項目分組 此步驟的目的是要使同一組的規模變大, 使組數變少 由卡諾圖求出最小的 SOP 表示式當代表表示式中各標準積項的 1 都適當的填於卡諾圖中, 再經過分組後, 就可以開始進入求最小 SOP 表示式的步驟 60

SOP 表示式的卡諾圖化簡法 4-27 求出圖 4-31 各卡諾圖的積項, 並寫出所得的最小 SOP 表示式 解 : 圖 4-31 中已顯示出各組的最小積項 此圖中各卡諾圖的最小 SOP 表示式分別為 : (a) (c) AB BC ABC (b) B AC AC AB AC ABD (d) D ABC BC 61

SOP 表示式的卡諾圖化簡法 例 4-23 ( 續 ) 62

4-29 SOP 表示式的卡諾圖化簡法 利用卡諾圖將下列 SOP 表示式最小化 : BC D ABC D ABC D ABCD ABCD ABCD ABCD ABCD ABCD 解 : 第一項 BCD 必須擴展成 ABCD和 A BCD, 形成標 準 SOP 表示式, 才能做成卡諾圖, 將圖中含 1 的方格分組, 如圖 4-33 所示 圖 4-33 63

SOP 表示式的卡諾圖化簡法 例 4-29 ( 續 ) 注意所得兩組都有包捲式鄰接的情形 因為卡諾圖的最外兩行中的方格相鄰接而形成 8 方格的一組 因為最上和最下層方格相鄰, 將其餘的兩個 1 拼湊起來便形成 4 方格的一組 各組的積項都標示在圖上了, 所得的最小 SOP 表示式為 : D BC 記住, 最小表示式和原標準表示式是等效的 64

例題八 8. 利用卡諾圖找出各表示式的最小 SOP 形式 : (a) (d) A BC ABC ABC AC( B C) A( BC BC) A( BC BC) A BC ABC ABC ABC (b) (c) 65

4-10 POS 卡諾圖的簡化 這一節的重點是放在 POS 表示式 POS 表示式卡諾圖 的方格內填的是代表標準和項的 0 66

4-30 解 : 將標準 POS 表示式做成卡諾圖 將下列標準 POS 表示式做成卡諾圖 : ( A B C D)( A B C D)( A B C D)( A B C D)( A B C D) 如下將表示式各和項的二進位數算出, 再將 0 填入 圖 4-37 的 4 變數卡諾圖中 ( A B C D)( A B C D)( A B C D)( A B C D)( A B C D) 1100 1011 0010 1111 0011 67

將標準 POS 表示式做成卡諾圖 例 4-30 ( 續 ) 圖 4-37 68

4-32 解 : POS 表示式的卡諾圖簡化法 利用卡諾圖將下列 POS 表示式最小化 : ( B C D)( A B C D)( A B C D)( A B C D)( A B C D) 第一項必須先擴展成 和 A + B + C + D 形成 標準 POS 表示式 接著便做出卡諾圖, 並對方格分組, 如圖 4-39 所示 圖中已顯示出各組和項, 最後得到的最小 POS 表 示式為 A B C D ( C D)( A B D)( A B C) 記住, 最小 POS 表示式與原標準 POS 表示式是等效的 69

POS 表示式的卡諾圖簡化法 例 4-32 ( 續 ) 圖 4-39 70

例題九 9. 利用卡諾圖找出下列各表示式的最小 POS 形式 : (a) (b) (c) ( A B C)( A B C)( A B C) ( X Y)( X Z)( X Y Z)( X Y Z) A( B C)( A C)( A B C)( A B C) 71

4-11 數位系統應用實例 計數與控制系統中就用到七段顯示器 這些顯示器和 解 BCD 碼的邏輯電路併用, 將適當的數字顯示在顯示器上 72

顯示段解碼邏輯 顯示段可用來表示不同的十進位數字, 表 4-9 表 4-9 各個十進位數字所要運作的顯示段數字要顯示的段 0 a, b, c, d, e, f 1 b, c 2 a, b, d, e, g 3 a, b, c, d, g 4 b, c, f, g 5 a, c, d, f, g 6 a, c, d, e, f, g 7 a, b, c 8 a, b, c, d, e, f, g 9 a, b, c, d, f, g 73

顯示段解碼邏輯 表 4-10 七段邏輯電路的真值表 十進位輸入段輸出數字 D C B A a b c d e f g 0 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 0 0 2 0 0 1 0 1 1 0 1 1 0 1 3 0 0 1 1 1 1 1 1 0 0 1 4 0 1 0 0 0 1 1 0 0 1 1 5 0 1 0 1 1 0 1 1 0 1 1 6 0 1 1 0 1 0 1 1 1 1 1 7 0 1 1 1 1 1 1 0 0 0 0 8 1 0 0 0 1 1 1 1 1 1 1 9 1 0 0 1 1 1 1 1 0 1 1 10 1 0 1 0 X X X X X X X 11 1 0 1 1 X X X X X X X 12 1 1 0 0 X X X X X X X 13 1 1 0 1 X X X X X X X 14 1 1 1 0 X X X X X X X 15 1 1 1 1 X X X X X X X 輸出 1 表示該段啟動 (on) 輸出 0 表示該段不啟動 (off) 輸出 X 表示 隨意項 " 74

顯示段解碼邏輯 顯示段邏輯電路的布林表示式 利用真值表, 便能寫出 各顯示段的標準 SOP 或 POS 表示式 例如,a 段的標準 SOP 表示式為 : a DC B A DCBA DCBA DCBA DCBA DCBA DC B A DC BA e 段的標準 SOP 表示式為 : e DC B A DCBA DCBA DC B A 75

顯示段解碼邏輯 多輸出邏輯閘的進一步簡化 76