Outline 3-1 布林代數 3-2 基本邏輯閘及其特性 3-3 正邏輯與負邏輯表示方式 3-4 函數完全運算集合

Presentation on theme: "Outline 3-1 布林代數 3-2 基本邏輯閘及其特性 3-3 正邏輯與負邏輯表示方式 3-4 函數完全運算集合"— Presentation transcript:

1 Outline 3-1 布林代數 3-2 基本邏輯閘及其特性 3-3 正邏輯與負邏輯表示方式 3-4 函數完全運算集合
3-1 布林代數 3-2 基本邏輯閘及其特性 3-3 正邏輯與負邏輯表示方式 3-4 函數完全運算集合 3-5 布林函數的表示方式 3-6 邏輯閘的基本應用 3-7 布林函數的化簡 3-8 以SSI來設計組合邏輯電路

2 3-1 布林代數 一、布林代數的公理（Axiom） 布林代數是由一群元素的集合N、兩個運算子{＋}與{．}、與一個補數運算子{ ’}所組成的一個代數結構，滿足下列的公理（或公設）： 1.集合N至少包含兩個不相等的元素a、b，即a≠b。 2.具封閉性（closure properties）： 對任意兩個元素而言 (1) (2) 交換律（commutative law） (1) a+b=b+a (2)

3 4. 單位元素 (1) (2) 5.結合律（associative law） (1) (2) 6.分配律（distributive laws） (1) (2) 7.補數元素（complement） (1) (2)

4 8. 對偶原理（principle of duality）：
在布林代數中，將一個成立的敘述中之二元運算子{＋}與{．}交換、0與1交換後，得到的敘述也必然是個成立的敘述。 即：若 為一成立的敘述，則其 對偶函數 也為一成立的敘述。 9.逆轉換原理： 若 為一成立的敘述，則其逆轉換 函數 也為一成立的敘述。 例1：邏輯算式中， 之雙對式（Dual）為 (A) (B) (C) (D) 解：(B) 對偶函數之取法：變數不變，AND變OR，OR變AND，0變1，1變0。

5 2.邊界定理（Boundedness theorem）
二、布林代數之基本定理 1.等冪律（idempotent law） 對於每一個元素 而言 (1) (2) 2.邊界定理（Boundedness theorem） (1) 且　(2) 3.補數的唯一性：在布林代數中，每一個元素a的補數 是唯一的。 且 4.在布林代數中 ， 5.吸收律（absorption laws） (1) 且 (2)

6 7.笛摩根定理（DeMorgan’s Theorem） ，則： (1)
6.結合律（associative law） ，則： (1) 且 (2) 7.笛摩根定理（DeMorgan’s Theorem） ，則： (1) 且 (2) 證明：(1) (2)

7 為 的補數，但 亦為 的補數 補數是唯一的， 同理， ，由對偶原理得證。 8.同等定理（Consensus Theorem） (1) (2) pf：(1) (2)

8 9.簡化定理 (1) (2) 證明：(1) (2) 10.相鄰定理 (1) 證明：(1) (2) 例1：布林函數 等於 (B) X
解：(A)

9 例2：將布林運算式 化簡後之最簡結果為： 解：(C) 令 ，則原布林函數運算式等於 例3：下列布林敘述何者錯誤？ 解：(D) 例4：下列何者之表示式是錯誤的？ 解：(D)

10 例5：下列布林代數何者不正確？ 解：(C)

11 3-2 基本邏輯閘及其特性 一、反閘（Not Gate）（又稱為反相器） 1、符號： 2.真值表： 此處的A為輸入變數，F為輸出。 3.
3-2 基本邏輯閘及其特性 一、反閘（Not Gate）（又稱為反相器） 1、符號： 2.真值表： A F 1 此處的A為輸入變數，F為輸出。 3. （唸成A bar，即A的補數） 4.特性：輸出為輸入的1’s補數。

12 輸出F=AB（當A與B同時成立時，F才有輸出） 4. 特性：當輸入端有一為0，則輸出為0。
二、及閘（AND Gate） 1.符號： (兩輸入的AND閘） 2.真值表： A B F 1 輸出F=AB（當A與B同時成立時，F才有輸出） 4. 特性：當輸入端有一為0，則輸出為0。

13 5.範例： (1) (2) (3) 6.等效電路 A和B兩開關要同時關閉，燈泡才會亮。

14 3.輸出F=A+B（當A或B有一成立時，F才有輸出） 4.特性：當輸入端有一為1時，輸出即為1。
三、或閘（OR Gate） 1.符號： (兩輸入端的 OR Gate) 2.真值表： A B F 1 3.輸出F=A+B（當A或B有一成立時，F才有輸出） 4.特性：當輸入端有一為1時，輸出即為1。

15 5.範例： (1) (2) (3) 6.等效電路： A或B其中一個開關關閉，燈泡就會亮。

16 四、反及閘（NAND Gate） 1.符號： 2.真值表： 3.輸出 4.特性：當輸入端有一為0時，輸出即為1。
（兩輸入的NADN Gate） 2.真值表： A B F 1 3.輸出 4.特性：當輸入端有一為0時，輸出即為1。 相當於：NAND=AND+NOT

17 5. 範例： (1) (2) (3)

18 4.特性：當輸入端都為”0”時，輸出才為”1”， 否則為”0”。
五、反或閘（NOR Gate） 1.符號： （兩輸入端的NOR） 2.真值表： A B F 1 3.輸出 4.特性：當輸入端都為”0”時，輸出才為”1”， 否則為”0”。 5.相當於：NOR=OR+NOT

19 6.範例： (1) (2) (3)

20 六、互斥或閘（XOR Gate） 1.符號： 2.真值表： 3.輸出 4.特性：當輸入端不相同時，輸出為1。
B F 1 3.輸出 4.特性：當輸入端不相同時，輸出為1。 當輸入端有奇數個”1”時，則輸出為1。 用於奇同位元偵錯。

21 5.範例： (1) (2) (3)

22 七、互斥反或閘（XNOR Gate） 1.符號： 2.真值表： 3.輸出 4.特性：當輸入端相同時，輸出為1。
B F 1 3.輸出 ⊙ 4.特性：當輸入端相同時，輸出為1。 當輸入端有偶數個1時，輸出為1， 用於偶同位偵錯

23 5.範例： (1) (2) (3) 例1：假設一邏輯模擬程式（logic simulator）可以接受1,0,U（U表示訊號的　狀態未知）三種邏輯訊號狀態，則下列哪一個真值表（truth table）可以代表兩個輸入之反及閘（NAND）？

24 NAND Gate的特性是當或有一為”0”時，輸出都為”1”，所以只有(D)是正確的。
(B) 1 U (C) (D) 1 U 解：(D) NAND Gate的特性是當或有一為”0”時，輸出都為”1”，所以只有(D)是正確的。

25 解：(C) 例2：依據右圖所示之邏輯電路，下列那一組輸入及輸出值是不對的？ (A) A1=0，A2=1，B=1
(B) A1=0，A2=0，B=0 (C) A1=1，A2=1，B=1 (D) A1=1，A2=0，B=1 解：(C) 當A1與A2不等時，B才為1。 例3：1⊙1⊙1⊙1⊙0⊙0⊙0⊙0等於(A) 0⊙0⊙0⊙ (B)1⊕1⊕1⊕1 (C) 1⊙0⊙0⊙1 (D) 1⊕1⊕0⊕0 解：(C) 1⊙1⊙1⊙1⊙0⊙0⊙0⊙0 = 1 = 1⊙0⊙0⊙1

26 例4：下列脈衝輸入圖中電路後，輸出結果為何？
解： 對互斥或閘而言，若輸入端"1"的數目為奇數，則輸出為"1"，否則為"0"。輸出結果為 。 例5：下列有關閘（gate）之敘述，何者不真？ (A) 輸入均為0時，才輸出為1的閘為NOR Gate。 (B)布林函數 所代表的為兩個輸入的 Exclusive-OR（XOR） Gate。 (C)布林函數 所代表的為有兩個輸入的 Exclusive-NOR Gate。 (D)當輸入同時為1時，NOR Gate以及XOR Gate之輸出不同。

27 解：(D) 當輸入同時為1時，NOR Gate及XOR Gate均輸出為0。
2. ⊙ （XNOR）為偶數函數，當有偶數個交換變數為0時，其值才為1，否則為0。 3. 一般而言，當交換變數的個數是奇數時， XOR=XNOR。當交換函數的個數為偶數時，XOR與XNOR互為補數。

28 3-3 正邏輯與負邏輯表示方式 在實際的數位電路上，一般以0代表低電位，1代表高電位，即L=邏輯0，H=邏輯1，此稱為正邏輯。
3-3 正邏輯與負邏輯表示方式 在實際的數位電路上，一般以0代表低電位，1代表高電位，即L=邏輯0，H=邏輯1，此稱為正邏輯。 反之，若以0代表高電位，1代表低電位，即H=邏輯0，L=邏輯1，則稱為負邏輯。 一、正邏輯的AND Gate=負邏輯的OR Gate A B Z L H

29 二、正邏輯的NAND Gate=負邏輯的NOR Gate
B Z L H 同理，正邏輯的NOR Gate等於負邏輯的AND Gate；正邏輯的NOR Gate等於負邏輯的NAND Gate。 例1：一邏輯電路以負邏輯表示為NOR gate，若以正邏輯表示則為：(A)OR gate (B)NOR gate (C)NAND gate (D)AND gate 解:(C)

30 3-4 函數完全運算集合 1. 若任意一交換函數可由一個集合內的運算子表示時，該集合稱為函數完全運算集合（functionally Complete/Universal Set）。由於交換函數是由AND，OR與NOT等運算子組成的，所以｛AND、OR、NOT｝為一個函數完全運算集合。 2. 依據DeMorgan定理： ，即AND與NOT組合後，可以取代OR，所以｛AND、NOT｝也是函數完全集合。 3. 同理， ，即OR與NOT組合後，可以取代AND運算，所以｛OR、NOT｝也是函數完全運算集合。

31 4. 證明一個運算集合是否為函數完全運算集合的方法：
利用該集合內的運算子產生一個已知為函數完全運算集合內的每一個運算子（例：｛AND、MOT｝或｛OR、NOT｝等）即是。 函數完全運算集合有很多，並且可能只包含一個運算子，例如：｛NOR｝、｛NAND｝等。 例1： 證明｛NOR｝與｛NAND｝為函數完全運算集合。 證明：(a)因為｛NOR｝可以產生函數完全運算集合｛OR,NOT｝內的每一個運算子，即

32 （NOT） （OR） 所以｛NOR｝為一個函數完全運算集合。 (b)因為｛NAND｝可以產生函數完全運算集合｛AND,NOT｝ 內的每一個運算子，即 （NOT） （AND） 所以｛NAND｝為一個函數完全運算集合。

33 例2：證明下列集合為函數完全運算集合： (a)集合{f}而 (b)集合{f,1}而 (c)集合{f,1}而 證明：(a) （NOR） ∴得證 (b) （NOR） （AND) ∴得證 (c) （NOR） （AND） ∴得證

34 3-5 布林函數的表示方式 一、布林代數的表示法： 正規表示法有二： 1. 積之和（Sum of Product）或最小項的和。
3-5 布林函數的表示方式 一、布林代數的表示法： 正規表示法有二： 1. 積之和（Sum of Product）或最小項的和。 2. 和之積（Product of Sum）或最大項的乘積。 分別說明如下： (一)最小項的和或SOP型式： 將布林函數化為乘積項的和，每乘積項稱之為最小項（Minterm），積項中均包含所有的變數。

35 1. 將布林函數化為積之和的型式，步驟： (1) 若布林函數中補數的符號位於數個變數的組合上，則利用狄摩根定理將之拆開，使補數符號只位於單一變數上。 (2) 利用分配律予以展開。 (3) 刪除重覆項、零項等即得。 2. 將積之和（SOP）轉換為最小項的和，步驟： (1) 將所有積項缺少的變數乘上（所缺變數之補數加上所缺變數之補數）。 (2) 利用乘法分配律予以拆開。 (3) 刪除重覆項即得最小項的和。

36 例1：三變數之最小項與最大項 XYZ 最小項 符號 最大項 000 X’Y’Z’ m0 (X+Y+Z) M0 001 X’Y’Z m1
010 X’YZ’ m2 (X+Y’+Z) M2 011 X’YZ m3 (X+Y’+Z’) M3 100 XY’Z’ m4 (X’+Y+Z) M4 101 XY’Z m5 (X’+Y+Z’) M5 110 XYZ’ m6 (X’+Y’+Z) M6 111 m7 (X’+Y’+Z’) M7

37 例2：若 ，則其標準積之和表示方式為： (a) (b) (c) (d) 解：(d)

38 本題也可另解如下： 綜合以上兩項得

39 例3：設F(X,A,B)為邏輯正數，且 則F等於： 解：(C)

40 (二)最大項的乘積（Product of Maxterms）：
將布林函數化為和項的乘積，每個和項稱為最大項，和項中需包含所有的變數。 1. 將布林函數化為和之積（POS）的型式，步驟： (1) 若布林函數中補數的符號位於數個變數的組合上，則利用狄摩根定理將之拆開，使補數符號只位於單一變數上。 (2) 利用加法分配律予以展開。 (3) 刪除重覆項、零項等即得。 2. 將和之積（POS）轉換為最大項的乘積，步驟： (1) 將每一和項所缺的變數加上（所缺變數•所缺變數的補數）。 (3) 刪除重覆項即得最大項的乘積。

41 例4：試將三個變數的布林函數化為最大項的乘積函數。
*加法分配律* (三)SOP與POS的關係： 1. SOP型式著重在描述函數中，函數值為1的部份。 POS型式著重在描述函數中，函數值為0的部份。 2.對某一函數，其SOP與POS恰為互補的關係。

42 例5： 以最小項的和與最大項的積表示。 解： ｜*最小項的和*｜ ｜*最大項的積*｜ 例6：假設 ，則下列何者為非？ (a) (c) ，
(b) (c) (d)

43 解：(b) （AND） （XOR） （AND） （OR）

44 1. 對任意一布林函數f而言，其標準SOP（或POS）型式是唯一的。
四、布林函數的性質： 1. 對任意一布林函數f而言，其標準SOP（或POS）型式是唯一的。 2. 若兩個布林函數的標準SOP（或POS）型式相等時，則該兩個函數為邏輯相等（logically equivalent）。 3. 對於n個布林變數而言，共可組合成個布林函數。 因n個布林變數可組成項SOP型式，而每一項有0與1兩種狀態，故共有 個交換函數組合。

45 例7：設 為邏輯函數，則下列何者為真？ (A) (B) (C) (D) 解：(C)

46 3-6 邏輯閘的基本應用 一、基本邏輯閘在應用上一般用來控制數位信號的流向或改變數位信號的狀態，藉以控制後面的數位系統之動作方式。邏輯閘最常用的方式有四： 1.控制閘（Controlled gate）

47 2.反相控制閘（Inverted Controlled-gate）
C=0 F=1 C=1 F=X’ C=0 F=X’ C=1 F=0 3.控制補數閘（Controlled-inverted gate） C=0 F=X C=1 F=X’ C=0 F=X’ C=1 F=X

48 任何一個布林函數皆可以用下列三種方式之一執行。 1.使用開關（Switch）：如CMOS傳輸閘或相當電路等。
4.真值/補數/－0/1元件： C1 C0 F X’ 1 X 二、布林函數的執行 任何一個布林函數皆可以用下列三種方式之一執行。 1.使用開關（Switch）：如CMOS傳輸閘或相當電路等。 2.使用AND、OR或NOT等基本閘的結合。 3.使用NAND或NOR等通用閘來執行（下節介紹）

49 例1：試以基本邏輯閘執行下列布林函數。 (a) (b) (c) (d) 解：(a)

50 (b) (c) (d)

51 1.從輸入端由左而右逐次寫出各個邏輯閘的輸出，一直到最後一級輸出。
三、由邏輯電路求布林函數 由已知的邏輯電路求布林函數的步驟： 1.從輸入端由左而右逐次寫出各個邏輯閘的輸出，一直到最後一級輸出。 2.將最後一級的輸出利用布林代數的一般定理予以合併或分開，求得最後的標準SOP（或POS）型式。 例8：求出下圖之輸出布林函數

52 解： 由1點得 ，由2點得 由3點得 （狄摩根定理） 例9：列出下圖所示輪出函數的真值表。

53 解： A B F 1 其真值表如下：

54 例10：下圖求(a)其輸出函數f；(b)最簡的積之和型式；(c)最簡的和之積型式；(d)電路圖。

55 解：(a) (b) (c)

56 (d)電路圖如下：

57 例11：根據圖所示的邏輯電路圖，若A=1，B=0，C=1時，則之輸出應為：
(a)(0,0) (b)(0,1) (c)(1,0) (d)(1,1) 解:(b)

58 例12：如下圖所示電路中，假設G2或閘壞掉，而造成其輸出一 直為1。藉由觀察Z輸出值，試問下列哪一組輸入訊號(ABCD)可以偵測此電路錯誤的狀況？
當ABCD=0000時，G1輸出為0，因G3輸出為1，而G2輸出一直為1，造成Z的輸出為1，產生錯誤，故可偵測出G1故障。

59 3-7 布林函數的化簡 布林函數的化簡方法，一般分成三種： 1. 布林函數的定理化簡法 2. 卡諾圖化簡法
3-7 布林函數的化簡 布林函數的化簡方法，一般分成三種： 1. 布林函數的定理化簡法 2. 卡諾圖化簡法 3. 列表法（Quine-McCluskey Method） 茲分別介紹如下：

60 3-7-1、布林函數的定理化簡法 係依據布林代數的一般定理，直接對指定的函數進行化簡動作。其缺點是較無規則可循，有時需靠經驗才能化簡出較複雜的函數。 例1：若 ，則 解： 例2：下列布林函數何者錯誤？ 解:(D)

61 例3：如下圖，輸出P為何？ 解: 例4：如下圖所示電路，其布林函式F為何？

62 解:(C) 例5：布林函數 等效函數是 解:(B) ，

63 例6：下列何者函數與布林函數 不等效。 解:(B)

64 3-7-2、卡諾圖化簡 (一)化簡原理 利用X’Y+XY=Y之基本概念做化簡工作。 (二)化簡原則
1. 若兩項只差一個變數，則稱此兩項相鄰。 2. 圖的上下列、左右行均視為相鄰，可以圈起來（合併）。 3. 每一項可重覆使用，圈起的相鄰項愈多，可消去的變數愈多。圈起的項數必須是2的次方。 4. 圈起相鄰的項時，可消去N個變數，N為1，2，...。 5. 若以SOP型式表示時，則合併卡諾圖中”1”的部份，並以最小的和項方式表示。若以POS型式表示時，則合併卡諾圖中 “0” 的部份，並以最小的積項方式表示。 6. 合併時，為求最簡型式，能合併多項時，不能只取其中一部份合併。

65 (三)二個變數到五個變數的卡諾圖 3.四變數 1.二變數 2.三變數 4.五變數 YZ WX 00 01 11 10 1 3 2 4 5 7
1 3 2 4 5 7 6 12 13 15 14 8 9 Y X 1 2 3 2.三變數 YZ X 00 01 11 10 1 3 2 4 5 7 6 4.五變數 XYZ VW 000 001 011 010 100 101 111 110 00 1 3 2 4 5 7 6 01 8 9 11 10 12 13 15 14 24 25 27 26 28 29 31 30 16 17 19 18 20 21 23 22

66 若布林函數有K個變數，則卡諾圖的方格數需 個。
表示方式：以補數來代表0，以非補數來代表1。例如四變數的卡諾圖，5的位置為 。 (四)卡諾圖的缺點： 變數愈多，卡諾圖愈大，愈難找出關係化簡。 例1：布林函數 ，則F化簡後為 解:

67 例2：求布林函數 之最簡化式 解:(B)

68 例3：簡化布林函數 可得： 解:(D)

69 例4：布林函數 可簡化為： 解:(B)

70 例6：布林函數 可簡化為： 解:(D) CD AB 00 01 11 10 1

71 例7：Obtain the simplified output function in both sum of products and product of sums for the following logic diagram. 解:

72 (1) sum of product 利用卡諾圖化簡如下： 因此， (2) product of sum 利用卡諾圖化簡如下：

73 (五)加入隨意項（Don’t care）：
所謂的 "隨意項" 即是一種不定狀態，對布林函數而言，是一種不可能發生的變數組合或對輸出結果沒有影響的項，其值可為0或1，依實際使用而定。 具有隨意項的卡諾圖化簡步驟： 1. 將具隨意項的布林函數在卡諾圖所對應的方格中填入"ｘ"。 2. 將其餘非隨意項的布林函數值填入卡諾圖對應的方格中(若是最小項則填“1”，最大項則填“0”)。 3. 選擇相鄰方格數最多的方格予以合併化簡，卡諾圖中的"x"可以不被選擇。

74 例8：Simplify F together with is don’t care condition d in (a) sum of product form (sop) and (b) Product of sum form (pos)。 解:(a) sum of product form

75 (b) Product of sum form 例9：A logic circuit implements the following boolean function： It is found that the circuit input combination A=C=1 can never occur. Find a simpler expression for F using the proper don’t care conditions.

76 （don’t care condition）；因此，其真值表及卡諾圖可繪製如下：
(E) none of above 解:(D) 由題意 ，且A = C = 1為一隨意條件 （don’t care condition）；因此，其真值表及卡諾圖可繪製如下： A C D F 1 x

77 經卡諾圖化簡後可得 例10：化簡布林函數 可得？（m代表mintern，d代表don’t care） 解:

78 (六)最簡函數與最簡式 1. 設兩個交換函數 與 ，若當G的值為1時，F的值也必然為1，則稱F包含G，記為 。因此，當F包含G時，函數F在真值表上值為1的每一組合下，函數F的值也必為1。 若函數F包含G，同時函數G也包含F，則函數F與G相等（F=G）。

79 例13：設 ，而 ，則G為F的一個隱含項。 證明： ，G為F的一個隱含項。 2. 設G為交換函數 的乘積項且 ，若當中的任何一個字母變數去掉後，F不再包含G，則G稱為F的質隱項（prime implicant）。 例如：XY為 的一個質隱項。

80 (1) 在卡諾圖中，所有圈起來的格子群，均形成隱含項，即所有可併的項的集合。 (2) 在卡諾圖化簡中，可以形成最簡型式的項，即為質隱項。
3. 卡諾圖上的隱含項與質隱項 (1) 在卡諾圖中，所有圈起來的格子群，均形成隱含項，即所有可併的項的集合。 (2) 在卡諾圖化簡中，可以形成最簡型式的項，即為質隱項。 例如： 在上面的卡諾圖中： 隱含項 質隱項 （少了C與E）

81 4. (1) 一個交換函數F的任何最簡的SOP表示式，均為一個F的質隱項的和。
(2) 任何一個n個交換變數的交換函數 均可等效地表示為該函數的所有質隱項的和；此函數F之所有質隱項之和稱為F完全和（complete sum）。 5. 必要質隱項（Essential prime implicant）： 係指一個質隱項若其所包含的最小項中，至少有一個未被其它質隱項所包含時稱之。由於交換函數中的每一個最小項都必須包含於最簡式中，所以所有必要質隱項皆必須包含於最簡式中。

82 例14：下列交換函數中，那些是質隱項？那些是必要質隱項？
(1) (2) 解: (1) 所有質隱項都為必要質隱項。

83 (2) 所有質隱項 必要質隱項 6. 循環質隱項圖（cyclic prime implicant map）：若每一最小項均被兩個質隱項包含，造成沒有必要質隱項，謂之。

84 例16： 卡諾圖化簡後，可得兩個最簡式： 質隱項 沒有必要質隱項。

85 7. 由上述說明，要獲得一個交換函數的最簡SOP表示式，其程序如下：
(1) 決定所有必要質隱項，並且也含在最簡式中。 (2) 由質隱項中刪除所有被必要質隱項包含的質隱項。 (3) 若步驟 (1) 得到的結果能包含函數F的所有最小項，該結果即為最簡式，否則適當選取質隱項以使函數F能完全被包含，並且質隱項的數目為最少。

86 3-7-3、列表法化簡（Quine-McCluskey Method）
1. 適用範圍：函數中變數數目超過4個以上。 2. 優點：可產生一簡化的標準式，且對多變數，計算機可分享快速處理。 3. 列表法的簡化程序： (1) 找出簡化函數中的質隱項。 (2) 從質隱項中再選出具有最少變數符號的表示式。 4. 簡化步驟： (1) 將指定函數的全及項一一列出，並由所含"1"的個數來分組。

87 (2) 把每一全及項與其它全及項比較，若遇有兩個全及項僅差一個變數時，則消去該變數，形成一缺一變數的新項，以此循環，直到全部全及項比較完畢為止。
(3) 接著對新得的新項進行類似的比較，直到沒有變數可消除為止。 (4) 剩下的各項，以及在以上步驟不能合併的各項，就是列表法中第一部份要找的質隱項。

88 例1：以列表法簡化下列布林函數 依照全及項中所含"1"的數目分組 解: W X Y Z  全及項中含1個“1” 1 2 8 10
 全及項中含1個“1” 1 2 8 10 全及項中含2個“1” 11 全及項中含3個“1” 14 15 全及項中含4個“1”

89 2. 全及項兩兩比較，只要有一個變數相異，就可消去該變數，以"一"代表。
W X Y Z (0,1) － ← 質隱項 (0,2)  注意：只需比較各組之間相差為 之數即可。 (0,8) (2,10) 1 (8,10) (10,11) (10,14) “”代表已合併過的全及項，其不為質隱項。 (11,15) (14,15)

90 3.對所產生的新項，重覆步驟2。 4.未有 "" 處即為質隱項 ∴ W X Y Z (0,2,8,10) － 由步驟2.合併而得。
由步驟2.合併而得。 (0,8,2,10) ← 質隱項 (10,11,14,15) 1 兩項相同，只需寫一項即可。 (10,14,11,15) 4.未有 "" 處即為質隱項 ∴

91 例2：以列表法化簡布林函數 解: 簡化後 每一項均為質隱項 (a) (b) (c) 0001 1 1,9(8)
8,9,10,11(1,2) 0100 4 4,6(2) 1000 8 8,9(1)  8,10(2) 0110 6 1001 9 6,7(1) 1010 10 9,11(2) 10,11(1) 0111 7 1011 11 7,15(8) 11,5(4) 1111 15 簡化後 每一項均為質隱項

92 5. 必要質隱項（Essential prime implicant）的選擇。
 將所有質隱項列表，每一個質隱各佔一列，每一個全及項佔一行。  每列中放置有"x"者表示該質隱項所含的全及項。  選擇最少的質隱項來包含該函數的全部全及項。 以上例為例，質隱項表如下：

93 1 4 6 7 8 9 10 11 15 1,9 × 4,6 6,7 7,15 11,15 8,9,10,11  (1)檢查質隱項表中，僅含一個 “x” 的各行，所選出的質隱項稱為必要質隱項。 與 為必要質隱項。

94 (2)再者，檢查函數各行，是否都已包含在必要質隱項中，若是，則打一 “ˇ”。
從表中： 包含全及項1,9 包含全及項4,6 包含全及項8,9,10,11 除7與15外，函數的所有全及項均包含在必要質隱項中，所以必須把xyz(7,15)選入以得最簡函數

95 例3：試求下列交換函數之最簡表示式 解: 由於求質隱項時，必須把Don’t care項考慮進去，所以相當於求下列函數之質隱項。 (1) W
X Y Z  2 1 8 5 6 9 12 7 13 15

96 (2) W X Y Z (0,2) － (F) (0,8) (E) (2,6) 1 (D) (8,9)  (8,12) (5,7)
－ (F) (0,8) (E) (2,6) 1 (D) (8,9)  (8,12) (5,7) (5,13) (6,7) (C) (9,13) (12,13) (7,15) (13,15)

97 (3) (4)函數f的質隱項表如下： W X Y Z (8,9,12,13) 1 － (B) (5,7,13,15) (A) 2 6 7 8
(B) (5,7,13,15) (A) (4)函數f的質隱項表如下： 2 6 7 8 13 (A) × (B) (C) (D) (E) (F)

98 由於每一最小項均包含於兩個質隱項中，所以沒有必要質隱項。
最小項7,8,13只有A,B,E可以包含它們，但E較B複雜，故只取A與B。其次最小項2,6都可以由D包含，故函數f的最簡式為：

99 3-8 以SSI來設計組合邏輯電路 一、以雙層邏輯電路來設計邏輯電路
1. 雙層的邏輯電路設計是最簡單的設計方式，其基本形式有兩種，即AND-OR（SOP表示方式）與OR-AND（POS表示方式）。 2. 一般也常使用NAND與NOR兩個邏輯閘來設計組合電路，利用這四種邏輯閘的組合，雙層邏輯電路便有下列十六種不同的架構，如表3-2所示，表中有八種退化成單一運算的組合，不能執行任何交換函數，未退化的八種組合，依其性質可分成如表3-3的兩組。

100 表3-2 雙層邏輯電路 組合方式 執行的交換函數 是否退化 AND-AND AND 是 AND-OR 否 AND-NAND NAND
表3-2　雙層邏輯電路 組合方式 執行的交換函數 是否退化 AND-AND AND 是 AND-OR 否 AND-NAND NAND AND-NOR AND-OR-NOT OR-AND OR-OR OR OR-NAND OR-AND-NOT OR-NOR NOR NAND-AND NAND-OR NAND-NAND NANDP-NOR NOR-AND NOR-OR NOR-NAND NOR-NOR

101 表3-3　未退化之雙層邏輯電路之對偶關係 在上表中，SOP型式的一組相當於AND-OR組，而POS型式的一組相當於OR-AND組。同一組中，四種不同型式的轉換很容易，但是在不同組間的轉換就需採對偶關係，才能轉換。

102 例1：將下列交換函數的最簡式表示成雙層邏輯電路的八種型式。
解: 利用卡諾圖化簡得函數之最簡SOP表示式為： (AND-OR型式) (NAND-NAND型式) (OR-NAND型式) (NOR-OR型式)

103 (1) AND-OR (2) NAND-NAND (3) OR-NAND (4) NOR-OR

104 函數F之最簡型式之POS表示如下： (OR-AND型式) (NOR-NOR型式) (AND-NOR型式) (NAND-AND型式)

105 (5) OR-AND (6) NOR-NOR (8)NAND-AND (7) AND-NOR

106 二、NAND-NAND　雙層電路 在前述的七種邏輯閘中，NAND與NOR為通用邏輯電路，為了減低邏輯閘的成本，常將NAND-OR電路轉換為只由NAND或NOR所組成的電路。一般而言，最簡SOP表示式為： 依DeMorgan定理，上式可表示為：

107 例2：試以兩層的NAND閘執行下列交換函數成最簡型式
解: (1) 以卡諾圖化簡： (2)AND-OR電路

108 (3) ∴NAND-NAND電路如下：

109 NOR-NOR雙層電路通常用來表示最簡的POS型式，其轉換方式如下：
（OR-AND電路） 依DeMorgan定理，上式可表示成： （NOR-NOR電路）

110 例3：試以雙層NOR閘執行下列交換函數成最簡型式
解: (1)以卡諾圖化簡： (2)OR-AND電路：

111 (3)NOR-NOR電路：

112 3-9 通用閘與多層邏輯電路 NAND與NOR閘又稱為通用閘，因為它們可以取代其它任何一種的邏輯閘，取代的方式如下： 一、NAND：
3-9 通用閘與多層邏輯電路 NAND與NOR閘又稱為通用閘，因為它們可以取代其它任何一種的邏輯閘，取代的方式如下： 一、NAND： 1. NAND → NOT 2.NAND → AND

113 3. NAND → OR 4. NAND → NOR

114 5. NAND → XOR 或

115 6. NAND → XNOR 二、NOR閘： 1. NOR →NOT

116 2. NOR→AND 3. NOR → NAND

117 4. NOR → OR 5. NOR → XOR 6. NOR → XNOR

118 在邏輯電路中，以同一種邏輯閘來設計線路有以下的好處：
1. 節省成本：目前大部份的邏輯IC中都包含一組以上的邏輯閘，充份利用IC中的每一組邏輯閘不僅可以減少IC使用的種類及數量，硬體成本也可以降低。 2. 縮小體積：所使用的IC數量減少，硬體自然簡單的多了。 3. 提升速度：減少邏輯閘之間的延遲時間，速度可以大大提升。

119 例1：使用NAND閘來畫出下列之布林函數 (1) (2) 解: (1)解題步驟  先畫出原函數的邏輯圖：  對非NAND閘做修改（補入偶數個反相器）

120 其中："。"代表反相器 將相對的邏輯閘轉成NAND閘

121 (2) 解題步驟：  畫出原函數的邏輯圖  對非NAND的邏輯閘輸入輸出補入反向器

122  將相對邏輯閘轉成NAND閘 例2：只使用NOR閘畫出下列的交換函數 (1) (2)

123 解:(1)   

124 (2)  

125 其中："。 "代表反相器 

126 例3： 如下圖所示電路，假設輸入序列為00,10,11,01,11，則其最後輸出之為何？(A)00 (B)01 (C)10 (D)11
 0 0 →  1 0  1 1 0 1  

127 例4：如圖所示電路其布林函式（Boolean function）F為何？
(D) 解:(C) 上圖可等效於下圖