第十章布林代数与数位逻辑

1、1第十章 布林代數與數位邏輯10-1 布林函數與布林代數10-2 邏輯電路的認識與簡介10-3 組合電路 2電腦硬體元件是許多邏輯電路組合而成，在設計電路時，會以布林函數及布林代數來表達電路的設計方式及電路的功能，透過布林函數及布林代數，可以來達到電路簡化目的，降低硬體成本。使用布林代數來簡化電路的方式外，還有一種更標準化的電路簡化方式卡諾圖，我們也會在本章中一併探討。最後一節，會介紹一些常用的組合電路，包括：多工器、解多工器、半加器、全加器、編碼器、解碼器等，並會說明各種組合電路的功能。310-1布林函數與布林代數布林函數與布林代數 布林代數又稱二值布林代數，只有0及1兩種可能值。布林代數是

2、一些公設及定律組成，公設是指基本假設或定義，定律則是由這些公設推導出來，這些公設與定律常被應用在布林函數的運算及化簡上。布林函數則是指利用布林代數組合成的函數。可以將複雜的問題以布林函數來表示，再利用布林代數的公設與定律將函數化簡，然後設計成程式，交由電腦去執行，以減輕電腦運算資源的負擔。電腦晶片上的電子電路串接就是藉助布林代數來加以表示。另外，一些程式演算法也可以由布林運算來達成。 4符號邏輯符號邏輯 符號邏輯是以邏輯運算子和邏輯運算元組合而成的邏輯運算式。邏輯運算元一般都以英文字母來表示，其可能值為真或假，真以1表示，假則以0表示。5邏輯運算子邏輯運算子 邏輯運算子 ：稱為乘法，代表AND

3、運算，需要兩個變數，且當兩個變數同為1時，運算結果才為1；否則就為0。+：稱為加法，代表OR運算，需要兩個變數，而且只要其中有一個變數為1時，其運算結果就為1；若兩個同為0則結果為0。-：稱為互補，代表NOT運算，只需要一個變數即可。且當變數為1時，其運算結果為0，變數為0時則結果為1 6邏輯運算式邏輯運算式 例如：AB意義是代表A AND B；A + B則代表A OR B，A + 則代表A OR 。以上AB、A + B及A + 皆為邏輯運算式，其中可以省略，故AB又可表示成AB。CCC7布林函數布林函數 布林函數是由函數名稱、等號、二元變數(即該變數值僅有0及1兩種可能)、值為0或1的常數、

4、括號(包括(、)、等括號)及邏輯運算式所組成。F(A,B)=A+B就是一種布林函數的表示方式。在這個布林函數所代表的意義為右邊的邏輯運算子中，只要A=1或B=1則布林函數F(A,B)=1。布林函數還可以更複雜，使用真值表來表達布林函數的所有情況外，能先利用布林代數將布林函數簡化，再以真值表分析。8真值表真值表 真值表就是運用表格的方式來分析布林函數所產生的結果。布林函數中的變數只有真(用1表示)及假(用0表示)兩種值，一個含有n個二元變數的布林函數，其所對應的真值表是由n+1欄(Columns)及2n列(Rows)所組合而成。 9真值表包含了輸入及輸出兩部分 輸入部分 必須考慮到所有輸入變數的

5、可能值之各種組合，因為每一個變數的可能值只有兩個(0及1)。如果有n個變數則會有2n種輸入組合。 輸出部分 指布林運算後所得到的結果。 10底下先以二元變數為例，說明上述三個邏輯運算子的真值表。 AND運算 輸入輸出ABA AND B00001010011111OR運算輸入輸出A BA OR B00001110111112NOT運算請注意，NOT運算只有單一變數。有了兩個變數真值表的概念後，接著，我們再以三個變數為例，列出AND及OR的真值表。 輸入輸出ANOT A011 013AND運算 輸入輸出ABCA AND B AND C00000010010001101000101011001111

6、14OR運算 輸入輸出ABCA OR B OR C0000001101010111100110111101111115布林代數的公設布林代數的公設 布林代數之公設(postulate)定義如下：假設S代表一集合，且集合S中只包含兩個元素0及1單位元素+之單位元素為0，其定義為A + 0 = 0 + A = A之單位元素為1，其定義為A1 = 1A = A封閉性對於兩個屬於集合S的變數A及B，A + B與AB仍屬於集合S互補律亦稱補數定律。代表對於任一元素A屬於集合S，都會存在一個元素A讓A + = 1，A = 0AA16交換律的交換律定義為AB = BA+的交換律定義為A + B = B +

7、A分配律對+的分配律定義為A(B + C) = AB + AC+對的分配律定義為A + (BC) = (A + B)(A + C)結合律是指連乘或連加的邏輯運算式中，將不同的子連乘項或子連加項以括號分組，其結果是相同的。+的結合律定義為A + (B+C) = (A+B)+C的結合律定義為A(BC) = (AB)C 17布林代數的定律布林代數的定律 公設是指基本假設或定義，而定律則是由這些公設推導出來，任何底下列出的布林代數的基本定律，由布林代數的公設或其它基本定律來加以證明。將這些布林代數的定律，應用在布林函數等邏輯運算的簡化。以表格整理的方式，為各位列出重要的布林代數的定律： 18基本定律解

8、釋1.單一律指單一邏輯變數加1或乘0之運算。2.等羃律指進行邏輯運算(AND或OR)的變數為同一個，且運算後的值與未運算前的值相等。3.吸收律指一邏輯變數與另一邏輯運算式進行AND或OR運算後，其結果與該變數未運算前之值相等，其行為如同吸收。19基本定律解釋4.乘方律指一個邏輯變數進行兩次的NOT運算後的值與未運算前的值相等。 5.對偶定律 指一邏輯運算式中，將+與互換，0與1互換後，所得之對偶式仍然成立。 6.狄摩根定律 是因狄摩根發現對一個連乘或連加的邏輯運算式進行NOT運算後，與各個變數的補數進行連加或連乘的結果相等，故稱之。 20以布林代數化簡布林函數以布林代數化簡布林函數 請利用布林

9、代數的公設或定律，簡化下列的布林函數F(A,B)=A+ B 解答： AAAF(A,B) =A+ B (利用分配律可推導出下式) =(A+ )(A+B) (利用互補律可推導出下式) =A+B 21標準型式的布林函數標準型式的布林函數 邏輯運算式所構成的函數即稱為布林函數，布林函數的標準形式又可分為兩種：積之和(Sum of Product, SOP)及和之積(Product of Sum, POS)。 22積之和(Sum of Product, SOP)意指布林函數的各項均包含了所有的輸入變數，並且各項皆為變數連乘之項，簡稱積項，每一個積項又稱為最小項(miniterm)，所謂最小項是指積項的連

10、乘結果與積項變數中之最小值相等 23和之積(Product of Sum, POS)意指布林函數的各項均包含了所有的輸入變數，並且各項皆為變數相加之項，簡稱和項，每一個和項又稱為最大項(Maxterm)，所謂最大項是指和項的相加結果與和項變數中之最大值相等 24SOP和POS布林函數可以互相轉換，每個最小項皆有一個相對應的最大項，下面我們列出二變數布林函數的最大項與最小項的對應表： m3=AB11+B01 B10M0=A+B00最大項最小項BAABABBAABm0=m1=M1=A+m2=AM2=M3=+25求得F(A,B,C) =m(3,5,6,7) =M(0,1,2,4)。 m7=ABC11

11、1 +C011 C101 +B+C001BC110 +C010 C 100M0=A+B+C000最大項最小項CBAABCABCACBABBCABACCABABCm0=m1=M1= A+B+m2=BM2= A+m3=M3= A+m4=AM4= m5=AM5= +B+m6=ABM6= +M7= +C2610-2 邏輯電路的認識與簡化邏輯電路的認識與簡化 在邏輯電路中則是以邏輯閘(Logic Gates)來處理這些二元邏輯運算；也就是說，邏輯閘是邏輯電路組成的最基本電子元件。通常一個邏輯閘具有一個或一個以上的輸入訊號，且包含一個輸出訊號。同時，這些輸入及輸出訊號就是我們前面所介紹的二值布林代數，它只

12、有0及1兩種可能值。 27為了方便表示邏輯電路圖，在邏輯電路中，每一個邏輯閘都有其基本符號，藉由這些基本符號，我們可以很直覺的表示邏輯電路中的各個基本元件，並且可用來推算邏輯電路圖。 28 各式邏輯閘簡介各式邏輯閘簡介 AX = 反向器(Invertor)或閘(OR Gate)X = A + B及閘(AND Gate)X = AB = BA符號說明代數函數29反或閘(NOR Gate)反及閘(NAND Gate)緩衝器(Buffer)X = AABABBA ABX =+X =30反互斥或閘 + AB互斥或閘(XOR)A BABX=AB =B + AX=AB =31邏輯電路與布林函數邏輯電路與布

13、林函數 介紹如何將布林函數繪製成邏輯電路圖，為了驗證邏輯電路圖是否正確，可以將該布林函數的真值表的輸出，並與真實的邏輯電路的輸出結果做比較。下面的表格中筆者舉出二個布林函數，並同時比較每一個布林函數的邏輯電路圖。32下面的表格中筆者舉出二個布林函數，並同時比較每一個布林函數的邏輯電路圖。 + XY邏輯電路圖布林函數XYXF(X,Y) = F(X,Y) = (X)(+ Y)33使用布林化數簡化邏輯電路使用布林化數簡化邏輯電路 設計電路板時，基於降低成本及易於維護之考量，避免電路設計過於複雜，電路簡化是一項重要的工作，簡化即是想辦法將邏輯閘的使用量降到最少，簡化的方法主要可以分成下列兩種： 第一種

14、方式是先將邏輯電路以布林函數表示，再以布林代數的公設及定律進行布林函數的簡化工作，再將經簡化後的布林函數，以相對應的邏輯電路加以表示，而達到簡化的效果。第二種方式仍然先將邏輯電路以布林函數表示，再以卡諾圖方式簡化布林函數，而達到邏輯電路的簡化結果。34使用卡諾圖簡化邏輯電路使用卡諾圖簡化邏輯電路 卡諾圖，是指由最小項(或最大項)所組成的二維矩陣，並在這個矩陣中填入相對應之最小項(或最大項)的值(0或1)，最後經由矩陣中的數值來進行簡化的工作。35兩個變數的卡諾圖 兩個變數的卡諾圖，以最小項表示如下：XY1Y010 Y XXYXYX36三個變數的卡諾圖三個變數的卡諾圖，以最小項表示如下： XYZ

15、 Z1 YZ Z010110100 YZXXYZXYXXZYZYZYXXXY3710-3 組合電路組合電路 組合電路(Combinational Circuits)是由許多邏輯閘組合而成，在組合電路中有n個輸入變數及m個布林函數的輸出，且每一個輸出的布林函數的值是由輸入變數的值所決定，其真值表的欄數為m+n欄，列數為2n列。較常見的組合電路有多工器、解多工器、半加器、全加器、編碼器、解碼器等，底下將配合組合電路圖形的繪製這些常見的組合電路，並說明各組合電路的功能。 38多工器多工器 多工器(Multiplexer)是指一個擁有n個輸入線與1條輸出線的組合電路，並根據訊號線的指示，選擇一個輸入訊號從輸出線輸出，故又稱為資料篩選器。其圖示如下：n條輸入1條輸出39解多工器解多工器 解多工器是指在一個擁有1個輸入線與n條(n 2)輸出線的組合電路，將單一的輸入訊號轉換成n條輸出訊號。其圖示如下：1條輸入n條輸出40半加器半加器 半加器包含兩個輸入(A,B)及兩個輸出(carry及sum)，其功能為處理兩個位元的相加，carry用來代表是否進位，而sum則代表運算後的值，其公式如下:carry = Acarry = AB Bsum = Asum = AB = B + A B = B + A ABABsumcarry000001101010