3.4 布林代數的化簡

布林代數式可以描述一件事成功的途徑及條件,例如圖3.4-1中欲使Y=1的途徑有兩條,一條為開關SW1ASW2B均接通,另一條為開關SW1ASW2B'均接通,布林代數式就為Y=AB+AB',但是我們發現只要開關SW1A接通時,無論開關SW2BB'的位置,Y均等於1,所以Y=AB+AB'=A是絕對成立的,這種代數式的簡化可以更清楚的知道事件成功的關鍵,減少了考慮的項目或變數。因此布林代數的化簡(simplification)是為了消除不必考慮的變數,化簡後邏輯結果不變

401.gif (1400 bytes)

 

3.4-1 利用定理定律化簡

3.4-1-1

試化簡Y =ABC+AB'C+ABC'+AB'C'

Y = AC(B+B')+ AC'(B+B') (∵分配律)

= AC+AC' (B+B'1)

= A(C+C') (∵分配律)

= A (C+C'1)

3.4-1-2

試化簡Y=AB'C+A'B'C+BC

Y= AB'C+A'B'C+BC

= B'C(A+A')+BC

= B'C + BC

= C(B'+B)

= C

3.4-1-3

試化簡Y =A(B+C)A'+D

Y= (AB+AC)A'+D

= (A'AB+A'AC)+D

= (0+0)+D         (A'A00+0=0)

= D

3.4-1-4

試化簡Y = A + A' + B

Y = A +A' + B

= (A + A') +B (結合律)

= 1+ B (A+A'=1)

= 1

3.4-1-5

試化簡Y = AB'+ABC+A'B'C'

Y = AB'C+AB'C'+ABC+A'B'C' (AB'=AB'(C+C'))

= AB'C+ABC+ AB'C'+A'B'C' (交換律)

= AC(B+B')+B'C'(A+A')

= AC+B'C'

3.4-1-6

試化簡Y = AB+A'BC

Y= B(A+A'C)

= B(A+C) (吸收律)

= AB+BC (分配律)

Y = AB+A'BC

= ABC+ABC'+A'BC (AB=AB(C+C')')

= ABC+ABC'+ABC+A'BC (ABC=ABC+ABC)

= AB+BC

 

3.4-2 利用卡諾圖化簡

卡諾圖(Karnaugh map)是化簡布林代數式的工具圖,它利用了A+A'=1的原理將相鄰的兩項得以消除,快速的得到最簡的布林代數式,化簡的方法請跟著例題學習。

3.4-2-1

試化簡Y =AB+A'B

步驟1 繪出兩個變數的卡諾圖

402.gif (983 bytes)

步驟2 Y1的項目先填入卡諾圖,其餘填0

本例Y =AB+A'B中有兩項,ABA'B均可令Y=1

故卡諾圖應為:

403.gif (1739 bytes)

 

步驟3 將相鄰為1的項圈起來。

(注意:所圈之項N的多少除了必須是相鄰為1的項之外,還必須滿足N=2nn為正整數,例如24816)

404.gif (2320 bytes)

步驟4圈起來的項互補變數者視為可消除之變數,再重新列出布林代數式。

本例中AA'互補,亦即Y =AB+A'B=B(A+A')=B,所以今後卡諾圖中相鄰且互補的的變數可以得以消除,因此本例Y=B即為化簡結果。

(注意:圈中有兩個"1",必然可以消去一個變數。)

3.4-2-2

試化簡Y = AB'C+A'B'C+BC

步驟1 繪出三個變數的卡諾圖

(注意:B'C'B'CBCBC'的排列順序,而非B'C'B'CBC'BC,這是為了相鄰的項均有互為補數的變數以利消除化簡。)

405.gif (1505 bytes)

步驟2 Y1的項目先填入卡諾圖,其餘填0

因為Y =AB'C+A'B'C+BC

= AB'C+A'B'C+ABC+A'BC

所以卡諾圖為:

406.gif (1669 bytes)

步驟3 將相鄰為1的項(N)圈起來,且N=4滿足=2nn為正整數2

407.gif (2781 bytes)

步驟4圈起來的項有互補變數者視為被消除之變數,再重新列出布林代數式。

本例中AA'互補、BB'互補,所以Y=C即為化簡結果。

(注意:圈中有四個"1",必然可以消去兩個變數。)

3.4-2-3

試化簡Y = A'B' + AB'C'D'+ AB'CD'

步驟1 繪出四個變數的卡諾圖

408.gif (2371 bytes)

步驟2 Y1的項目先填入卡諾圖,其餘填0

因為A'B'=A'B'C+A'B'C'

=A'B'CD+A'B'CD'+A'B'C'D+A'B'C'D'

所以Y = A'B'CD+A'B'CD'+A'B'C'D+A'B'C'D'+ AB'C'D'+ AB'CD'

則卡諾圖為:

wpe3.jpg (6661 bytes)

步驟3 將相鄰為1的項圈起來。

wpe4.jpg (14266 bytes)

步驟4圈起來的項有互補變數者視為被消除之變數,再重新列出布林代數式。

圈一中C'D'+C'D可消去DC'D+CD可消去C'CD+CD'可消去DCD'+C'D'可消去C,化簡後剩下A'B'

圈二中直的看A'B'+AB'消去A剩下B',橫的看C'D'+CD'消去C剩下D',此圈化簡後為B'D'

Y= A'B'+ B'D' (注意:有幾個圈,化簡後的布林代數式就有幾個項,本例中有兩個圈,所以有A'B'B'D'兩項。)

410.gif (18274 bytes)

 

將為1的項填入卡諾圖後化簡:

411.gif (5304 bytes)

圈一:Y=BA'

圈二:Y=CA'

圈三:Y=DA'

故化簡前有7個為1的輸出項,化簡後為Y=BA'+CA'+DA' ,僅有3個項而且每個項中的變數都減少了兩個。

wpe5.jpg (13316 bytes)