中文教材-卡諾圖

7.3.3邏輯函數(shù)的卡諾圖化簡法卡諾圖是按一定規(guī)則畫出來的方框圖，也是邏輯函數(shù)的一種表示方法。它可以直觀而方便地化簡邏輯函數(shù)。

1.邏輯函數(shù)最小項的概念

1）最小項的定義在邏輯函數(shù)中，設有n個邏輯變量，由這n個邏輯變量所組成的乘積項（與項）中的每個變量只是以原變量或反變量的形式出現(xiàn)一次，且僅出現(xiàn)一次，那么我們把這個乘積項稱為n個變量的一個最小項。對于三個變量A、B、C來講，由它們組成的八個乘積項都符合最小項的定義，因此我們把這八個乘積項稱為三個變量A、B、C的最小項。除此之外

等項就不是最小項。

n變量的邏輯函數(shù)，有2n個最小項。若n=2,2n=4,二變量的邏輯函數(shù)就有4個最小項，若n=4,24=16,四變量的邏輯函數(shù)就有16個最小項……依此類推。

2）最小項的性質(zhì)為了分析最小項的性質(zhì)，列出三變量所有最小項的真值表,如表7.12所示。由表7.12可知，最小項具有下列性質(zhì)：

(1)對于任意一個最小項，有且僅有一組變量的取值使它的值等于1；

(2)任意兩個不同最小項的乘積恒為0；

(3)n變量的所有最小項之和恒為1。

ABC0001000000000101000000010001000000110001000010000001000101000001001100000001011100000001

表7.12三變量最小項真值表

3）最小項編號

n個變量有2n個最小項。為了敘述和書寫方便，通常對最小項進行編號。最小項用“mi”表示，并按如下方法確定下標“i”的值：把最小項取值為1所對應的那一組變量取值的組合當成二進制數(shù)，與其相應的十進制數(shù)就是i的值。例如，三變量A、B、C相應的最小項C，使其值為1的變量ABC取值為001，對應的十進制數(shù)為1，則它的最小項的編號記作“m1”。同理，AB的編號為“m6”。2.邏輯函數(shù)的標準式——最小項表達式任何一個邏輯函數(shù)都可以表示成若干個最小項之和的形式，這樣的表達式就是最小項表達式。而且這種形式是唯一的。從任何一個邏輯函數(shù)表達式轉化為最小項表達式的方法如下：

1）由真值表求得最小項表達式例如，已知Y的真值表如表7.13所示。由真值表寫出最小項表達式的方法是：使函數(shù)Y=1的變量取值組合有001、010、110三項，與其對應的最小項是

,則邏輯函數(shù)Y的最小項表達式為

表7.13真值表

ABCY00000011010101101000101011011110

2）由一般邏輯函數(shù)式求得最小項表達式首先利用公式將表達式變換成一般與或式，再采用配項法，將每個乘積項（與項）都變?yōu)樽钚№棥?.卡諾圖

1）卡諾圖的組成及特點卡諾圖是邏輯函數(shù)的一種表示方式，是根據(jù)真值表按一定的規(guī)則畫出來的一種方塊圖。此規(guī)則就是使邏輯相鄰的關系表現(xiàn)為幾何位置上的相鄰,利用卡諾圖使化簡工作變得直觀。

所謂邏輯相鄰，是指兩個最小項中除了一個變量取值不同外，其余的都相同，那么這兩個最小項具有邏輯上的相鄰性。例如，m3=BC和m7=ABC是邏輯相鄰。又如,m3和m1=C、m2=也是邏輯相鄰。所謂幾何相鄰，是指在卡諾圖中排列位置相鄰的那些最小項。要把邏輯相鄰用幾何相鄰實現(xiàn)，在排列卡諾圖上輸入變量的取值順序時，就不要按自然二進制順序排列，而應對排列順序進行適當調(diào)整。對行或列是兩個變量的情況，自變量取值按00，01，11，10排列；對行或列是三個變量的情況，自變量取值按000，001，011，010，110，111，101，100排列。

n個變量的邏輯函數(shù)，具有2n個最小項，對應的卡諾圖也應有2n個小方塊。二變量的最小項有22=4個，其對應的二變量卡諾圖由4個小方塊組成,并對應表示4個最小項m0~m3。如圖7.14所示。

圖7.14二變量卡諾圖

三變量的最小項有23=8個，對應的三變量卡諾圖由8個小方塊組成,并對應表示8個最小項，如圖7.15所示。四變量最小項的個數(shù)為24=16個，對應的四變量卡諾圖由16個小方塊組成,并相應表示16個最小項,如圖7.16所示。

圖7.15三變量卡諾圖

圖7.15三變量卡諾圖

圖7.15三變量卡諾圖

圖7.16四變量卡諾圖

由卡諾圖的組成可知，卡諾圖具有如下特點：

(1)n變量的卡諾圖具有2n個小方塊，分別表示2n個最小項。每個原變量和反變量總是各占整個卡諾圖區(qū)域的一半。

(2)在卡諾圖中，任意相鄰小方塊所表示的最小項都僅有一個變量不同，即這兩個最小項具有“相鄰性”。相鄰的小方塊數(shù)等于變量個數(shù)n。2)用卡諾圖表示邏輯函數(shù)一個邏輯函數(shù)Y不僅可以用邏輯表達式、真值表、邏輯圖來表示，而且還可以用卡諾圖表示。其基本方法是：根據(jù)給定邏輯函數(shù)畫出對應的卡諾圖框，按構成邏輯函數(shù)最小項的下標在相應的方格中填寫“1”，其余的方格填寫“0”，便得到相應邏輯函數(shù)的卡諾圖。

由已知邏輯函數(shù)畫卡諾圖時，通常有下列三種情況：（1）給出的是邏輯函數(shù)的真值表。具體畫法是先畫與給定函數(shù)變量數(shù)相同的卡諾圖，然后根據(jù)真值表來填寫每一個方塊的值，也就是在相應的變量取值組合的每一小方格中，函數(shù)值為1的填上“1”，為0的填上“0”，就可以得到函數(shù)的卡諾圖。[例7.11]

已知邏輯函數(shù)Y的真值表如表7.14所示，畫出Y的卡諾圖。

解先畫出A、B、C三變量的卡諾圖，然后按每一小方塊所代表的變量取值，將真值表相同變量取值時的對應函數(shù)值填入小方塊中，即得函數(shù)Y的卡諾圖，如圖7.17所示。

表7.14真值表

ABCY00000011010101111000101011001111

圖7.17例7.11的卡諾圖

（2）給出的是邏輯函數(shù)最小項表達式。把邏輯函數(shù)的最小項填入相應變量的卡諾圖中，也就是將表達式中所包含的最小項在對應的小方格中填入“1”，其它的小方格填入“0”，這樣所得到的圖形就是邏輯函數(shù)的卡諾圖。

[例7.12]試畫出函數(shù)Y(A，B，C，D)=∑m（0,1,3,5,6,8,10,11,15）的卡諾圖。

解：先畫出四變量卡諾圖，然后在對應于m0、m1、m3、m5、m6、m8、m10、m11、m15的小方格中填入“1”，其它的小方格填入“0”,如圖7.18所示。

圖7.18例7.12的卡諾圖（3）給出的是一般邏輯函數(shù)表達式。先將一般邏輯函數(shù)表達式變換為與或表達式，然后再變換為最小項表達式,則可得到相應的卡諾圖。實際上，我們在根據(jù)一般邏輯表達式畫卡諾圖時，常?？梢詮囊话闩c或式直接畫卡諾圖。其方法是：把每一個乘積項所包含的那些最小項所對應的小方格都填上“1”，其余的填“0”，就可以直接得到函數(shù)的卡諾圖。[例7.13]

畫出Y（A，B，C）=AB+B+的卡諾圖。

解：

AB這個乘積項包含了A=1，B=1的所有最小項，即AB和ABC。B這個乘積項包含了B=1，C=0的所有最小項,即AB和B。這個乘積項包含了A=0，C=0的所有最小項，即B和。最后畫出卡諾圖如圖7.19所示。需要指出的是:①在填寫“1”時,有些小方格出現(xiàn)重復,根據(jù)1+1=1的原則,只保留一個“1”即可；②在卡諾圖中，只要填入函數(shù)值為“1”的小方格,函數(shù)值為“0”的可以不填；③上面畫的是函數(shù)Y的卡諾圖。若要畫的卡諾圖是Y的反，則要將Y中的各個最小項用“0”填寫，其余填寫“1”。

圖7.19例7.13的卡諾圖

4.利用卡諾圖化簡邏輯函數(shù)

1）合并最小項的規(guī)律利用卡諾圖合并最小項，實質(zhì)上就是反復運用公式AB+A=A，消去相異的變量，從而得到最簡的“與或”式：（1）當2個（21）相鄰小方格的最小項合并時，消去1個互反變量；（2）當4個（22）相鄰小方格的最小項合并時，消去2個互反變量；（3）當8個（23）相鄰小方格的最小項合并時，消去3個互反變量；（4）當2n個相鄰小方格的最小項合并時，消去n個互反變量。n為正整數(shù)。

圖7.20、圖7.21、圖7.22分別畫出了相鄰2個小方格的最小項、相鄰4個小方格的最小項、相鄰8個小方格的最小項合并的情況。

2)利用卡諾圖化簡邏輯函數(shù)一般按以下三個步驟進行：

(1)畫出邏輯函數(shù)的卡諾圖；

(2)按合并最小項的規(guī)律合并最小項,將可以合并的最小項分別用包圍圈(復合圈)圈出來；

(3)將每個包圍圈所得的乘積項相加,就可得到邏輯函數(shù)最簡“與或”表達式。圖7.202個最小項的合并

圖7.202個最小項的合并

圖7.202個最小項的合并

圖7.214個最小項的合并

圖7.214個最小項的合并

圖7.214個最小項的合并

圖7.228個最小項的合并

圖7.228個最小項的合并

圖7.228個最小項的合并

圖7.228個最小項的合并

例7.14

用卡諾圖化簡邏輯函數(shù)

Y（A,B,C,D）=∑m（0,2,3,5,7,8,10,11,15）解第一步，畫出Y的卡諾圖,如圖7.23所示；第二步，按合并最小項的規(guī)律畫出相應的包圍圈；第三步，將每個包圍圈的結果相加，得

圖7.23例7.14的卡諾圖

例7.15化簡

Y（A,B,C,D）=∑m(3,4,5,7,9,13,14,15)。

解首先畫出Y的卡諾圖，如圖7.24所示。然后合并最小項。圖7.24(a)、(b)是兩種不同的圈法,圖(a)是最簡的；圖(b)不是最簡的,因為只注意對1畫包圍圈應盡可能大,但沒注意復合圈的個數(shù)應盡可能少,實際上包含4個最小項的復合圈是多余的。

圖7.24例7.15的卡諾圖(a)最簡；(b)非最簡圖7.24例7.15的卡諾圖(a)最簡；(b)非最簡最后寫出最簡與或式為從上述例題可知，利用卡諾圖化簡邏輯函數(shù)，對最小項畫包圍圈是比較重要的。圈的最小項越多，消去的變量就越多；圈的數(shù)量越少，化簡后所得到的乘積項就越少。綜上所述，復合最小項應遵循的原則是：

①按合并最小項的規(guī)律，對函數(shù)所有的最小項畫包圍圈；

②包圍圈的個數(shù)要最少，使得函數(shù)化簡后的乘積項最少；

③一般情況下，應使每個包圍圈盡可能大，則每個乘積項中變量的個數(shù)最少；

④最小項可以被重復使用，但每一個包圍圈至少要有一個新的最小項（尚未被圈過）。

需要指出的是：用卡諾圖化簡邏輯函數(shù)時，由于對最小項畫包圍圈的方式不同，得到的最簡與或式也往往不同?？ㄖZ圖法化簡邏輯函數(shù)的優(yōu)點是簡單、直觀，容易掌握，但不適用于五變量以上邏輯函數(shù)的化簡。

5.具有“約束”的邏輯函數(shù)的化簡

1）什么是“約束”在前面所討論的邏輯函數(shù)中，我們認為邏輯變量的取值是獨立的，不受其它變量取值的制約。但是，在某些實際問題的邏輯關系中，變量和變量之間存在一定的制約關系。這種相互“制約”的關系就是約束。

例如，在數(shù)字系統(tǒng)中，用A、B、C三個變量分別表示加、乘、除三種操作，而且規(guī)定在同一時間只能進行其中的一種操作。因此，A、B、C三個變量只可能出現(xiàn)000、001、010、100四種取值，而011、101、110、111四種取值是不允許出現(xiàn)的。這就說明三個變量A、B、C之間存在著“約束”的關系。我們稱A、B、C是一組有約束的變量，而不允許出現(xiàn)的四組變量取值組合所對應的最小項稱為“約束項”（或稱為“任意項”、“禁止項”、“無關項”），由約束項相加起來的邏輯表達式叫做“約束條件”。在本例中，約束條件可寫為要使表達式（7-19）成立,每個最小項的值必須恒為0。約束條件的性質(zhì)：約束項的值永遠不會為1。既然認定約束項對應的變量取值的組合不會出現(xiàn)，那么，談論與它相對應的函數(shù)值是1還是0是沒有意義的。也就是說，對應約束項的變量取值時，其函數(shù)值可以是任意的，既可以取0，也可以取1，這完全視需要而定，通常把相對應的函數(shù)值記作“×”或“”。

（7-19）

2)具有“約束”的邏輯函數(shù)的化簡對于具有“約束”的邏輯函數(shù)，可以利用約束項進行化簡，使得表達式簡化。例7.16設輸入A、B、C、D是十進制數(shù)X的二進制編碼，當X≥5時，輸入Y為1，否則為0，求Y的最簡“與或”表達式。

解（1）根據(jù)題意列真值表，如表7.15所示。

表7.15真值表XABCDY000000100010200100300110401000501011601101701111

表7.15真值表（續(xù)）XABCDY