計算機概論 第六章 數位邏輯 陳維魁/陳邦治 旗標出版社

本章重點 電腦的硬體是由邏輯電路所組成 數位邏輯(digital logic)是分析及設計邏輯電路時所必須瞭解的知識 若要瞭解電腦的邏輯電路的原理及設計方式便必須學習數位邏輯

大綱 邏輯運算子及邏輯閘 布林運算的重要定理 通用閘 布林運算式的正規表示法 布林運算式的化簡 組合邏輯 循序邏輯 3 3

邏輯運算子及邏輯閘 因為邏輯運算處理的值是邏輯值，邏輯值也可稱為布林值(即true與false)，所以邏輯運算又稱為布林運算 常用的邏輯運算子有AND、OR、NOT、NAND、NOR、XOR及XNOR等 「NOT」是比較特別的邏輯運算子，它只有一個輸入、一個輸出 其他的邏輯運算子則是有二個輸入、一個輸出 為了簡化表達的方式，通常會用「1」來代替布林值「true」，用「0」來代替布林值「false」

AND運算子 AND運算子輸入與對應輸出的關係是「當二個輸入值皆為true時，輸出值為true；否則輸出值為false」 AND運算子輸入與對應輸出的關係利用真值表(truth table)定義如下

AND運算子 (cont.) 當AND運算子的二個輸入x與y之值皆為1時，對應的輸出值為1，其他輸入狀況對應的輸出值皆為0 通常將「x AND y」的敘述簡化寫成「x‧y」 AND 閘(gate)如下圖

OR 運算子 OR運算子輸入與對應輸出的關係是「當二個輸入值皆為false時，輸出值為false；否則輸出值為true」

OR 運算子 (cont.) 由上表可知當OR運算子的二個輸入x與y之值皆為0時，對應的輸出值為0，其他輸入狀況對應的輸出值皆為1 通常將「x OR y」的敘述簡化寫成「x＋y」 OR 閘如下圖

NOT運算子 NOT運算子輸入與對應輸出的關係是「輸出值為輸入值的『1的補數』」 NOT運算子輸入與對應輸出的關係利用真值表定義如下

NOT運算子 (cont.) 由上表可知當NOT運算子的輸入值為0時，對應的輸出值為1；輸入值為1時，對應的輸出值為0 通常將「NOT x」的敘述簡化寫成 NOT 閘如下圖

範例

解答

NAND運算子 NAND運算子輸入與對應輸出的關係是「當二個輸入值皆為true時，輸出值為false；否則輸出值為true」

NAND運算子 (cont.) 由上表可知當NAND運算子的二個輸入x與y之值皆為1時，對應的輸出值為0，其他輸入狀況對應的輸出值皆為1 輸入x，y與輸出F間之對應關係如下列關係式

範例 下列那一個運算式有誤? (A) 0 NAND 0 = 1 (B) 0 NAND 1 = 1 (C) 1 NAND 0 = 0 (D) 1 NAND 1 = 0 解：C NAND運算子只有在二個運算元之值皆為1 (true)時，結果為0 (false)，其他的情形下結果皆為1

NOR運算子 NOR運算子輸入與對應輸出的關係是「當二個輸入值皆為false時，輸出值為true；否則輸出值為false」

NOR運算子 (cont.) 由上表可知當NOR運算子的二個輸入x與y之值皆為0時，對應的輸出值為1，其他輸入狀況對應的輸出值皆為0 輸入x，y與輸出F間之對應關係如下列關係式如下

範例 下列那一個運算式有誤? (A) 0 NOR 0 = 1 (B) 0 NOR 1 = 0 (C) 1 NOR 0 = 0 (D) 1 NOR 1 = 1。 解：D NOR運算子只有在二個運算元之值皆為0 (false)時，結果為1 (true)，其他的情形下結果皆為0

XOR運算子 XOR運算子輸入與對應輸出的關係是「當二個輸入值不同時，輸出值為true；否則輸出值為false」

XOR運算子 (cont.) 由上表可知當XOR運算子的二個輸入x與y之值為(1, 0)或(0, 1)時，對應的輸出值為1，其他輸入狀況對應的輸出值皆為0 XOR 閘如下圖 輸入x，y與輸出F間之對應關係如下列關係式

範例 (1 XOR 1) XOR (1 XOR 0) XOR (1 XOR 1)的結果為何？ 解： ＝1

XNOR運算子 XNOR運算子輸入與對應輸出的關係是「當二個輸入值相同時，輸出值為true；否則輸出值為false」

XNOR運算子 (cont.) 由上表可知當XNOR運算子的二個輸入x與y之值為(0, 0)或(1, 1)時，對應的輸出值為1，其他輸入狀況對應的輸出值皆為0 XNOR 閘如下圖 輸入x，y與輸出F間之對應關係如下列關係式

範例 下圖之邏輯電路，當 C=0 時 輸出Y 的值為何？

範例 下圖之邏輯電路，當 C=1 時 輸出Y 的值為何？

範例 下圖的輸出值 F 為何？ 解：

範例 有一邏輯電路圖如下： 若A=100101112、 B=110100012，則C=？

範例 兩個8 bits的暫存器X及Y，內容分別為X＝5D16，Y＝AB16。若將X、Y暫存器之內容經過OR之邏輯處理後將其結果存入另一暫存器Z中，則Z的內容應為何？(結果請以16進位表示) 解：FF16

範例 請將NOT 、AND、OR、NAND、NOR、XOR及XNOR共七個邏輯運算子轉換成對等的「if –then-else」結構

NOT對等的「if –then-else」結構 由上表可知當NOT運算子的輸入值為0時(即false)，對應的輸出值為1；當輸入x的值為1時(即true)，輸出值為false。 因此，NOT運算子對等的「if –then-else」結構如下： if (x) then false else true ;

AND對等的「if –then-else」結構 將上述的真值表整理為「以變數x為輸入，F為輸出」之結果如下表

AND對等的「if –then-else」結構 (cont.) 由上表可知，當輸入x的值為1時，輸出值與y值同，當輸入x的值為0時，輸出值為false AND運算子對等的「if –then-else」結構如下： if (x) then y else false ;

OR對等的「if –then-else」結構 將上述的真值表整理為「以變數x為輸入，F為輸出」之結果如下表

OR對等的「if –then-else」結構 (cont.) 由上表可知，當輸入x的值為1時，輸出值為true，當輸入x的值為0時，輸出值與y值同。 OR運算子對等的「if –then-else」結構如下： if (x) then true else y ;

NAND對等的「if –then-else」結構 將上述的真值表整理為「以變數x為輸入，F為輸出」之結果如下表

NAND對等的「if –then-else」結構(cont.) 由上表可知，當輸入x的值為1時，輸出值與(not y)相同，當輸入x的值為0時，輸出值為true。 NAND運算子對等的「if –then-else」結構如下 if (x) then (not y) else true ;

NOR對等的「if –then-else」結構 將上述的真值表整理為「以變數x為輸入，F為輸出」之結果如下表

NOR對等的「if –then-else」結構(cont.) 由上表可知，當輸入x的值為1時，輸出值為false，當輸入x的值為0時，輸出值與(not y)值同。 NOR運算子對等的「if –then-else」結構如下 if (x) then false else (not y) ;

XOR對等的「if –then-else」結構 將上述的真值表整理為「以變數x為輸入，F為輸出」之結果如下表

XOR對等的「if –then-else」結構(cont.) 由上表可知，當輸入x的值為1時，輸出值與(not y)值同，當輸入x的值為0時，輸出值與y值同 XOR運算子對等的「if –then-else」結構如下 if (x) then (not y) else y ;

XNOR對等的「if –then-else」結構 將上述的真值表整理為「以變數x為輸入，F為輸出」之結果如下表

XNOR對等的「if –then-else」結構(cont.) 由上表可知，當輸入x的值為1時，輸出值與y值同，當輸入x的值為0時，輸出值與(not y)值同。 XNOR運算子對等的「if –then-else」結構如下 if (x) then y else (not y) ;

布林運算的重要定理 本節的主要目的是介紹與布林運算有關的重要定理 布林運算的相關定理通常會被使用在布林運算式的化簡用途上

單一律 (Law of Tautology) 單一律是指在布林運算式中僅有單獨一個變數的可能值未確定之前提下，布林運算式的結果值與該變數的關係 下表為單一律的可能情形

結合律 (Associative Law) 結合律是指改變計算的順序，針對「+」及「‧」可滿足結合律之特性

「+」的結合律

「‧」的結合律 X‧(Y‧Z)=(X‧Y)‧Z 證明

分配律 (Distributive Law) 分配律有二類 加對乘的分配律： X+(Y‧Z)=(X+Y)‧(X+Z) 乘對加的分配律： X‧(Y+Z)=(X‧Y)+(X‧Z)

範例

範例

交換律(Commutative Law) 交換律是指改變運算元的順序但運算的結果值不會改變。 「＋」及「‧」二個運算子都滿足交換律，分別介紹如下： (1) X+Y=Y+X (2) X‧Y=Y‧X

吸收律(Absorption Law) (1) X+X‧Y=X (2) X‧(X+Y)=X 證明： X+X‧Y

笛摩根定律(DeMorgan’s Law) 笛摩根定律常用在布林運算式的化簡上，主要分為二類 笛摩根定律可擴充至任意個運算元，假設運算元的個數為n個，則擴充後的笛摩根定律如下

範例 有一邏輯電路如下圖所示，此電路中輸出Z與輸入X，Y的關係式應為：(A) Z＝X．Y (B) Z＝X＋Y (C) Z＝X'＋Y' (D) Z＝(X'．Y')'

範例 下列邏輯電路圖經化簡後結果為何？(A) A+B+C+D (B)A+B'+C+D (C) A+B+C'+D (D) A+B+C+D'

通用閘 「通用閘」(universal gate)是指可被利用來表示所有邏輯電路的邏輯閘 「通用閘」有二種分別是NAND gate與 NOR gate 所有的邏輯電路均可利用AND gate，OR gate與NOT gate三種邏輯閘組成 「通用閘」可取代AND gate，OR gate與NOT gate三種邏輯閘的功能

NAND gate為「通用閘」的理由(1/3) 利用NAND gate取代NOT gate的功能 最少使用1個NAND gate便可取代NOT gate的功能

NAND gate為「通用閘」的理由(2/3) 利用NAND gate 取代AND gate的功能 最少使用2個NAND gate便可取代AND gate的功能

NAND gate為「通用閘」的理由(3/3) 利用NAND gate取代OR gate的功能 最少使用3個NAND gate便可取代OR gate的功能

NOR gate為「通用閘」的理由(1/3) 利用NOR gate取代NOT gate的功能

NOR gate為「通用閘」的理由(2/3) 利用NOR gate取代OR gate的功能

NOR gate為「通用閘」的理由(3/3) 利用NOR gate取代AND gate的功能

範例 下列敘述何者有誤？ 解：C (A)利用NOT 和 OR 邏輯閘可組成任意邏輯電路 (B)利用NOT 和 AND 邏輯閘可組成任意邏輯電路 (C)利用AND 和 OR 邏輯閘可組成任意邏輯電路 (D)利用NOR 邏輯閘可組成任意邏輯電路。 解：C

布林運算式的正規表示法 布林運算式的正規表示法是在執行布林運算式化簡動作時會使用到的基本知識及工具 布林運算式的正規表示法可分為 「最小項的和」(sum of minterms) 「最大項的積」(product of maxterms)

「最小項」(minterm) 「最小項」：包含所有變數且「最小項」變數間的運算子皆為「AND」，也就是「‧」 例如在三個變數情況下(假設變數為X、Y及Z)，「最小項」的可能性有八種，詳列如右表

「最小項」(cont.) 由上表可知「最小項」的「替代符號」之下標恰與(X, Y, Z)二進位值轉換後的10進位值相等 以X‧Y‧Z為例，此時(X, Y, Z)=(1, 1, 1)時，(1, 1, 1)的二進位值為1112，將1112轉換成10進位值結果為710，所以X‧Y‧Z會以m7做為「替代符號」，其他情況可依此類推 「最小項」會包含所有變數的乘積項

「最小項的和」( sum of minterms) 將最小項以「OR」運算子結合，也就是用「＋」運算子結合，便是「最小項的和」 範例

「最大項」(maxterm) 「最大項」：包含所有變數且「最大項」變數間的運算子皆為「OR」，也就是「＋」 在三個變數情況下(假設變數為X、Y及Z)，「最大項」的可能性有八種，詳列如右表：

「最大項」(cont.)

「最大項的積」(product of maxterms) 將最大項以「AND」運算子結合，也就是用「‧」運算子結合，便是「最大項的積」 範例

布林運算式的化簡 對布林運算式執行化簡的目的為希望能減少硬體成本的支出 透過執行布林運算式化簡，通常可減少數位電路所需要的邏輯閘數量，如此一來便可降低硬體成本的支出 布林運算式的化簡法有二種 「定理化簡法」 「卡諾圖(Kamaugh Map)化簡法」

定理化簡法 因為本法是直接利用基本的定理如單一律、交換律或結合律等定理來進行布林運算式的化簡，所以必須對基本的定理相當熟悉，但是某些特殊的問題利用本法困難度將較高 (如範例3)

範例1 請利用定理來化簡以下布林運算式

範例 2

範例 3 本範例若利用基本定理乘進行布林運算式的化簡工作，必須加入額外項『X+』，對於一般人來說困難度較高，因為當題目不同時，必須加入的額外項不同且加入的位置也會不同 最好能有一種方法，可以很簡單的解決在本範例中所遭遇的問題 以下將介紹「卡諾圖化簡法」來解決以上的問題

卡諾圖化簡法 卡諾圖化簡法的特性是作法固定與容易理解。 卡諾圖化簡法的作法分為以下四個步驟 (1)若布林運算式有n個變數，則卡諾圖應有 2n 個方格。 (2)若布林運算式採「最小項的和」表示，則必須在卡諾圖中相對應的方格內填入 1。若採「最大項的積」則填入 0

卡諾圖化簡法(cont.) (3)卡諾圖中相鄰的方格僅有一個位元不同。合併方式如下： a.相鄰的2k個方格可被合併。 b.選擇相鄰方格數最多的方式來簡化。 c.每個被使用的方格皆至少被選用一次，但不限制被選用的次數

卡諾圖型式 -- 二個變數

相鄰方格合併 二個相鄰方格合併，共有四種情況 四個相鄰方格合併，只有一種情況

卡諾圖型式 – 三個變數 由於卡諾圖規定相鄰的方格僅能有一個位元不同，所以第三欄必須調整為「11」，而第四欄則調整為「10」

相鄰方格合併 (1/3) 二個相鄰方格合併，共有十二種情況

相鄰方格合併 (2/3) 四個相鄰方格合併，共有六種情況

相鄰方格合併 (3/3) 八個相鄰方格合併，只有一種情況

範例1

範例2

範例3

範例4

範例5

範例6

組合邏輯(combinational logic) 組合邏輯是一種邏輯電路，組合邏輯電路在某一時刻的輸出值僅與該時刻的輸入值有關，與該時刻之前的輸入值沒有任何關連 組合邏輯的電路結構是由邏輯閘所組成，不得包含以下三種設備 記憶單元 回授(feedback) 線路 時脈(clock)

常見的組合邏輯電路 本節將介紹幾個較常見的組合邏輯電路，內容包含了 半加器 全加器 解碼器 編碼器 多工器

半加器(half adder) 半加器的功能是執行二個輸入位元(x與y)的相加動作，輸出值為輸入值相加後的和(sum；S)及進位(carry；C) 由於半加器只有二個輸入，因此無法處理前一個位元的進位，也就是說半加器處理的並不是完整的加法運算，因此稱之為半加器 半加器之輸出與輸入對應的方塊圖如下

半加器(cont.) 輸出與輸入對應的真值表 輸出結果值 輸出與輸入對應的邏輯電路圖

全加器(full adder) 全加器的功能是執行三個輸入位元(x、y與z)的相加動作，因此除了二個相對應的位元直接相加外，另外，必須加上前一位元的進位部份一併執行加法動作 全加器的輸出值為輸入值相加後的和(sum；S)及進位(carry；C) 全加器之輸出與輸入對應的方塊圖如下

全加器(cont.) 輸出與輸入對應的真值表 輸出結果值 輸出與輸入對應的邏輯電路圖

解碼器(decoder) 解碼器的功能是將n 個輸入對應出2n 個輸出 以2個輸入對應出22＝4 個輸出的解碼器來做為範例說明如下

解碼器(cont.) 輸出與輸入對應的邏輯電路圖

編碼器(encoder) 編碼器的功能是2n個輸入會產生n個輸出 以4個輸入對應出2個輸出的編碼器來做為範例說明如下

編碼器(cont.) 輸出與輸入對應的邏輯電路圖

多工器(multiplexer) 多工器的功能是由多個輸入中選擇一個當作輸出。 以2個輸入對應出1個輸出的多工器來做為範例 利用1條選擇線(S)來選擇2個輸入(x及y)中的1個做為輸出，輸出與輸入對應的真值表如下 上表中當S=0 時代表選擇 x 做為輸出；當S=1 時代表選擇 y 做為輸出

多工器(cont.) 2×1多工器對應的方塊圖 2×1多工器對應的邏輯電路圖

4個輸入對應1個輸出的多工器 利用2條選擇線(S0及S1)來選擇4個輸入(A、B、C及D)中的1個做為輸出，輸出與輸入對應的真值表如下 當(S1,S0)=(0,1) 時，選擇 B 做為輸出 當(S1,S0)=(1,0) 時，選擇 C 做為輸出 當(S1,S0)=(1,1) 時，選擇 D 做為輸出

4個輸入對應1個輸出的多工器 4×1多工器對應的方塊圖 4×1多工器對應的邏輯電路圖 由範例可知，若為 2n×1 的多工器則有 n 條選擇線。如8×1 的多工器有3條選擇線，若為16×1的多工器則有4條選擇線，其他情況可依此類推

循序邏輯 計算機內部執行輸入訊號與記憶體儲存的資料間之邏輯運算是利用組合邏輯電路來完成 但是組合邏輯電路並無法完成某些工作，例如控制ALU之動作 實際上ALU是由循序邏輯(sequential logical)來控制，而ALU的運算工作則是利用組合邏輯來完成

循序邏輯電路結構 組合邏輯的特性是給予一組輸入資料，隨即便可得到對應的輸出。但是若輸出值會與記憶單元目前的狀態和輸入有關時便必須採用循序邏輯 循序邏輯的電路結構必須包括記憶單元與回授線路(feedback circuit)

循序邏輯電路結構 (cont.) 在循序邏輯電路結構中之輸出會與以下二項資料有關 1.輸入。 2.記憶單元內目前的狀態 上圖為循序邏輯電路結構範例。圖中包含一個組合電路與記憶單元，此二者構成一個回授線路，將輸出接回輸入便可構成「回授線路」

R-S正反器 (Reset-Set Flip Flop) 可利用NOR閘或NAND閘來製作

利用NOR閘設計的R-S正反器 內部邏輯電路圖 真值表 精簡真值表

利用NAND閘設計的R-S正反器 內部邏輯電路圖 真值表 精簡真值表

鐘控R-S正反器(Clocked R-S Flip-Flop) 利用NOR閘設計的R-S正反器加上兩個AND 閘及clock所構成 邏輯電路圖 真值表

鐘控R-S正反器(cont.) 特性方程式

鐘控D型正反器(Clocked D Flip-Flop) R-S正反器的變形 邏輯電路圖

鐘控D型正反器(cont.) 真值表 特性方程式

鐘控J-K 正反器 解決鐘控R-S 正反器的可能會有「不穩定」狀態的問題 邏輯電路圖

鐘控J-K 正反器(cont.) 真值表 由上表知當J＝K＝1時，鐘控J-K 正反器的輸出Q(t+1)=，不再是「不穩定」狀態，因此解決了鐘控R-S 正反器的「不穩定」狀態問題 特性方程式

鐘控T型正反器(Clocked T Flip-Flop) 為鐘控J-K正反器的變形 邏輯電路圖

鐘控T型正反器(cont.) 真值表 特性方程式