卞維新，徐德琴

（安徽師范大學(xué)計(jì)算機(jī)與信息學(xué)院，安徽蕪湖241002）

在數(shù)字電路教學(xué)過程中，邏輯函數(shù)的化簡是重要的教學(xué)環(huán)節(jié)[1-3]。邏輯函數(shù)化簡的結(jié)果將直接影響后續(xù)電路分析和設(shè)計(jì)的準(zhǔn)確性和可靠性。邏輯函數(shù)的化簡通常有兩種方法：公式法和卡諾圖法。公式法化簡邏輯函數(shù)除了要求學(xué)生必須熟練掌握邏輯代數(shù)的運(yùn)算法則和基本公式以外，還要求學(xué)生具備一定的化簡技巧，而且化簡結(jié)果是否最簡判斷困難，難度較高。在數(shù)字電路中，邏輯函數(shù)通常表示為邏輯變量最小項(xiàng)之和的形式?？ㄖZ圖（Karnaugh Map）[4]是由美國貝爾實(shí)驗(yàn)室的莫里斯·卡諾在1953年提出的，將邏輯函數(shù)中對應(yīng)的最小項(xiàng)填入卡諾圖中即可表示出對應(yīng)的邏輯函數(shù)。卡諾圖法形象直觀，容易被學(xué)生掌握，且化簡結(jié)果是否最簡較易判斷，缺點(diǎn)是化簡變量個(gè)數(shù)不宜超過6個(gè)，否則化簡將變得非常復(fù)雜，而在實(shí)際應(yīng)用和教學(xué)中大多數(shù)邏輯函數(shù)的變量較少，卡諾圖法基本可以滿足要求。

1 卡諾圖的構(gòu)成

將邏輯函數(shù)中的邏輯變量分為兩組，每一組邏輯變量按格雷碼編碼規(guī)則排列構(gòu)成卡諾圖，圖中的每一個(gè)方格表示一個(gè)邏輯變量的最小項(xiàng)。格雷碼本質(zhì)上是一種二進(jìn)制編碼，在一組格雷碼中，任意兩個(gè)相鄰的代碼只有一位二進(jìn)制數(shù)不同，具有反射和循環(huán)特性。由格雷碼構(gòu)成的卡諾圖中的兩個(gè)相鄰最小項(xiàng)僅有一位變量取值不同（相反），因此可以很方便地消去不同的那個(gè)邏輯變量，從而達(dá)到化簡的目的，這正是邏輯函數(shù)卡諾圖化簡的基本原理。

為了準(zhǔn)確畫出卡諾圖，掌握自然二進(jìn)制碼到格雷碼之間的相互轉(zhuǎn)換是非常重要的。這不僅能夠幫助學(xué)生掌握格雷碼的特性，而且有助于學(xué)生更深入地理解卡諾圖化簡邏輯函數(shù)的原理。令Bn-1…B2B1B0為n位自然二進(jìn)制數(shù)，Gn-1…G2G1G0為其對應(yīng)的格雷碼。

自然二進(jìn)制碼轉(zhuǎn)換為格雷碼：保留自然二進(jìn)制碼的最高位Bn-1作為格雷碼的最高位Gn-1，次高位格雷碼Gn-2為自然二進(jìn)制碼的最高位Bn-1與次高位Bn-2的異或，依次類推，由下面的遞推式可得對應(yīng)的格雷碼：

格雷碼轉(zhuǎn)換為自然二進(jìn)制碼：保留格雷碼的最高位Gn-1作為自然二進(jìn)制碼的最高位Bn-1，次高位自然二進(jìn)制碼Bn-2為自然二進(jìn)制碼的最高位Bn-1與次高位格雷碼Gn-2的異或，依次類推，由下面的遞推式可得對應(yīng)的格雷碼：

圖1，圖2給出了一個(gè)三位自然二進(jìn)制碼與格雷碼之間相互轉(zhuǎn)換的示意圖，可以幫助學(xué)生更直觀地理解二者的轉(zhuǎn)換過程。

圖1 三位自然二進(jìn)制碼轉(zhuǎn)換為對應(yīng)的格雷碼示意圖

圖2 三位格雷碼轉(zhuǎn)換為對應(yīng)的自然二進(jìn)制碼示意圖

2 卡諾圖的構(gòu)建

為了化簡邏輯函數(shù)，首先必須掌握如何將邏輯函數(shù)中的最小項(xiàng)填入卡諾圖中準(zhǔn)確的位置，即準(zhǔn)確構(gòu)建卡諾圖?？ㄖZ圖的構(gòu)建過程就是將n變量邏輯函數(shù)對應(yīng)的全部最小項(xiàng)填入卡諾圖中對應(yīng)方格的過程。為了遵循構(gòu)建過程的嚴(yán)謹(jǐn)性和科學(xué)性，在構(gòu)建卡諾圖時(shí)一般都是將邏輯函數(shù)中的最小項(xiàng)用邏輯值“1”填入，沒有出現(xiàn)的最小項(xiàng)對應(yīng)的方格填入邏輯值“0”或保持為空[5]。例如下面的邏輯函數(shù)，

對應(yīng)的卡諾圖如圖3（a）所示。由于圖3（a）所示卡諾圖中填入的最小項(xiàng)都是用“1”表示，因此在課堂討論中我們無法清晰區(qū)分填入的最小項(xiàng)，從而導(dǎo)致師生不能快速看出邏輯函數(shù)最小項(xiàng)和卡諾圖中填入項(xiàng)的對應(yīng)關(guān)系[6]，進(jìn)而無法就一些疑問進(jìn)行順暢的討論。在實(shí)際課堂教學(xué)過程中，尤其是剛剛開始卡諾圖構(gòu)建的教學(xué)時(shí)，學(xué)生往往會對某些填入項(xiàng)有疑問，因而需要老師在課堂教學(xué)中進(jìn)行答疑。如果在課堂教學(xué)過程中學(xué)生對某個(gè)填入項(xiàng)有疑問，這樣構(gòu)建的卡諾圖將導(dǎo)致學(xué)生很難把問題表達(dá)清楚，教師也很難快速、清晰地判斷學(xué)生的問題。為了便于討論卡諾圖的構(gòu)建過程，在課堂教學(xué)實(shí)踐中，可為邏輯函數(shù)最小項(xiàng)設(shè)置一個(gè)唯一的身份標(biāo)識（Identifier，ID），將其填入對應(yīng)的卡諾圖方格中，這樣不僅使二者之間的一一對應(yīng)關(guān)系清晰可見，而且也有助于初學(xué)者加深對邏輯函數(shù)最小項(xiàng)填入卡諾圖過程的理解。這里為邏輯函數(shù)最小項(xiàng)綁定一小寫字母的ID，改寫（3）式的邏輯函數(shù)表達(dá)式如下：

對應(yīng)的卡諾圖如圖3(b)所示。顯然，此時(shí)再討論某個(gè)填入項(xiàng)將會非常便利，也不會存在交流障礙。

圖3 卡諾圖構(gòu)建實(shí)例

3 邏輯函數(shù)化簡

卡諾圖化簡邏輯函數(shù)的過程就是畫卡諾圈的過程。如何正確畫出邏輯函數(shù)的卡諾圈是卡諾圖化簡邏輯函數(shù)的核心問題[7-8]。

3.1 幾個(gè)定義

定義1 在邏輯函數(shù)F中，如果包含有“與”項(xiàng)，則每個(gè)“與”項(xiàng)都被稱為F的蘊(yùn)含項(xiàng)。

顯然，由標(biāo)準(zhǔn)與或式構(gòu)成的邏輯函數(shù)F中，每一個(gè)最小項(xiàng)自然是F的蘊(yùn)含項(xiàng)，反映在F的卡諾圖中，任何一個(gè)“1”項(xiàng)都是F的蘊(yùn)含項(xiàng)。特別地，任意一個(gè)卡諾圈也是蘊(yùn)含項(xiàng)。

定義2 若p 和q 分別為一邏輯函數(shù)F 的兩個(gè)“與”項(xiàng)，如果p 中出現(xiàn)的所有邏輯變量在q 中一定出現(xiàn)，則稱p為q的子項(xiàng)。

例如，令p=AB，q=ABC，由于出現(xiàn)在p中的邏輯變量A、B都出現(xiàn)在q中，因此p為q的子項(xiàng)。

定義3 令p是邏輯函數(shù)F的一個(gè)蘊(yùn)含項(xiàng)，如果F中不存在除p外的蘊(yùn)含項(xiàng)q是p的子項(xiàng)，則稱p為F的質(zhì)蘊(yùn)含項(xiàng)，簡稱為質(zhì)項(xiàng)。

按照最小項(xiàng)合并規(guī)律，在函數(shù)卡諾圖中，如果某個(gè)卡諾圈不可能被其他更大的卡諾圈包含，那么，該卡諾圈所對應(yīng)的蘊(yùn)含項(xiàng)為質(zhì)蘊(yùn)含項(xiàng)。圖4 給出了一個(gè)例子，在F 的卡諾圖中，卡諾圈p1=BCˉ和卡諾圈p2=BCˉDˉ都是F的蘊(yùn)含項(xiàng)，但是由于p1是p2的子項(xiàng)，因此p2不是F的質(zhì)蘊(yùn)含項(xiàng)。對于簡單的邏輯函數(shù)，函數(shù)的最簡式就等于所有質(zhì)蘊(yùn)含項(xiàng)之和，圖5給出了一個(gè)實(shí)例，即G =p1+p2。但對于復(fù)雜的邏輯函數(shù)，找到所有的質(zhì)蘊(yùn)含項(xiàng)未必能得到函數(shù)最簡式。圖6給出了一個(gè)實(shí)例，其中p1,p2,…,p5是邏輯函數(shù)F的所有質(zhì)蘊(yùn)含項(xiàng)，但顯然F ≠p1+p2+p3+p4+p5。因此為了準(zhǔn)確表述函數(shù)的最簡式，則有定義4。

圖4 質(zhì)蘊(yùn)含項(xiàng)示例

圖5 質(zhì)蘊(yùn)含項(xiàng)等價(jià)于函數(shù)最簡式實(shí)例

圖6 質(zhì)蘊(yùn)含項(xiàng)不等價(jià)于函數(shù)最簡式實(shí)例

定義4 若邏輯函數(shù)的一個(gè)質(zhì)蘊(yùn)含項(xiàng)包含有不被函數(shù)的其他任何質(zhì)蘊(yùn)含項(xiàng)所包含的最小項(xiàng)，則此質(zhì)蘊(yùn)含項(xiàng)被稱為必要質(zhì)蘊(yùn)含項(xiàng)，簡稱為必要質(zhì)項(xiàng)。

定義4反映在函數(shù)卡諾圖中可描述為：若某個(gè)卡諾圈包含了不可能被任何其他卡諾圈包含的1個(gè)方格，那么，該卡諾圈所對應(yīng)的“與”項(xiàng)為必要質(zhì)蘊(yùn)含項(xiàng)。顯然，邏輯函數(shù)的最簡式等價(jià)于所有必要質(zhì)蘊(yùn)含項(xiàng)之和。

3.2 邏輯函數(shù)化簡

基于卡諾圖中最小項(xiàng)邏輯相鄰的事實(shí)可知，相鄰的兩個(gè)最小項(xiàng)可以合并為一項(xiàng)，同時(shí)消去一個(gè)邏輯變量；相鄰的4個(gè)最小項(xiàng)可以合并為一項(xiàng)，同時(shí)消去兩個(gè)邏輯變量；同理，相鄰的2n個(gè)最小項(xiàng)可以合并為一項(xiàng)，可以消去n個(gè)邏輯變量。這也是卡諾圖化簡法畫卡諾圈的原則?？ㄖZ圖化簡邏輯函數(shù)的過程就是畫卡諾圈及求解必要質(zhì)蘊(yùn)含項(xiàng)的過程。為了便于課堂教學(xué)和討論，首先采用第2節(jié)提出的構(gòu)建卡諾圖方法構(gòu)建卡諾圖；然后畫卡諾圈，找出所有質(zhì)蘊(yùn)含項(xiàng)；最后檢查所有質(zhì)蘊(yùn)含項(xiàng)，找出所有必要質(zhì)蘊(yùn)含項(xiàng)，寫出邏輯函數(shù)最簡式。下面以一個(gè)邏輯函數(shù)化簡的例子講述本文提出的方法。

例1 用卡諾圖化簡（3）式對應(yīng)的4變量邏輯函數(shù)。

解 （1）為每一個(gè)最小項(xiàng)設(shè)置唯一標(biāo)識ID，改寫邏輯函數(shù)形式如上面（4）式所示；

（2）構(gòu)建邏輯函數(shù)卡諾圖，對應(yīng)最小項(xiàng)用ID填入，如上圖3（b）所示；

（3）畫出卡諾圖中所有質(zhì)蘊(yùn)含項(xiàng)對應(yīng)的卡諾圈，得到邏輯函數(shù)的所有質(zhì)蘊(yùn)含項(xiàng)。

帶有身份標(biāo)識ID的卡諾圖非常有利于課堂教學(xué)和討論。例如，在講授卡諾圈時(shí)，如果學(xué)生對某個(gè)卡諾圈有疑問，他能夠快速、清晰地描述自己的問題：“b”和“d”為何能構(gòu)成卡諾圈？“g”和“f”構(gòu)成的卡諾圈為何不是質(zhì)蘊(yùn)含項(xiàng)？諸如此類的問題都能夠順暢地和老師在課堂上溝通，其他同學(xué)也能很快融入他的問題。顯然，如果用傳統(tǒng)的卡諾圖（圖6），老師講授或?qū)W生提問都會有障礙，不利于課堂教學(xué)和討論。

圖7畫出了卡諾圖中所有質(zhì)蘊(yùn)含項(xiàng)對應(yīng)的卡諾圈。依據(jù)對應(yīng)的卡諾圈，可得邏輯函數(shù)對應(yīng)質(zhì)蘊(yùn)含項(xiàng)分別為p1=，p2=A，p3=D，p4=，p5=ABD。

（4）檢查所有質(zhì)蘊(yùn)含項(xiàng)，剔除冗余質(zhì)蘊(yùn)含項(xiàng)，找出所有必要質(zhì)蘊(yùn)含項(xiàng)，寫出邏輯函數(shù)最簡式。

對于復(fù)雜邏輯函數(shù)，檢查質(zhì)蘊(yùn)含項(xiàng)是否是必要質(zhì)蘊(yùn)含項(xiàng)是比較困難的，一不小心就會出錯。本文借鑒卡諾圖構(gòu)建過程中為最小項(xiàng)設(shè)置唯一ID的做法，通過為質(zhì)蘊(yùn)含項(xiàng)設(shè)置唯一ID（這里用一大寫字母表示）來簡化這一過程，使得這一過程更加直觀、簡單，也能夠使學(xué)生更加容易理解和掌握。

在圖7所示的卡諾圖中，令卡諾圈p1-p5對應(yīng)的ID分別為V、W、X、Y和Z，將各ID分別填入對應(yīng)卡諾圈，改畫卡諾圖如圖8所示。此時(shí)只要檢查每一個(gè)大寫字母是否會單獨(dú)出現(xiàn)即可：如果某一個(gè)大寫字母沒有單獨(dú)出現(xiàn)，則其對應(yīng)的卡諾圈必為冗余質(zhì)蘊(yùn)含項(xiàng)，可以剔除；如果有單獨(dú)出現(xiàn)，則其必為必要質(zhì)蘊(yùn)含項(xiàng)。由圖8可以很容易看出，V沒有單獨(dú)出現(xiàn)，因此其對應(yīng)的質(zhì)蘊(yùn)含項(xiàng)不是必要質(zhì)蘊(yùn)含項(xiàng)，為冗余質(zhì)蘊(yùn)含項(xiàng)，將其剔除，可得該邏輯函數(shù)對應(yīng)的所有必要質(zhì)蘊(yùn)含項(xiàng)為：p2=A，p3=D，p4=ˉ，p5=ABD。進(jìn)而可得邏輯函數(shù)F的最簡式為：F=A+D++ABD。

圖7 帶有身份標(biāo)識的邏輯函數(shù)卡諾圖

圖8 帶有身份標(biāo)識的邏輯函數(shù)卡諾圈

當(dāng)然，對于比較簡單的邏輯函數(shù)卡諾圈可以直接看出結(jié)果，就不必非要使用該方法。對于比較復(fù)雜的邏輯函數(shù)，該方法不僅能夠使得剔除冗余質(zhì)蘊(yùn)含項(xiàng)直觀、簡單，而且不容易出錯。另外，在剛開始講授這一部分內(nèi)容時(shí)，此方法也能夠幫助學(xué)生快速理解從質(zhì)蘊(yùn)含項(xiàng)到必要質(zhì)蘊(yùn)含項(xiàng)的原理，掌握卡諾圖化簡邏輯函數(shù)的技巧。

4 結(jié)束語

卡諾圖化簡邏輯函數(shù)的優(yōu)點(diǎn)是簡單、直觀，有一套容易操作的化簡步驟，且容易化簡到最簡并不易出錯。這使得卡諾圖化簡在整個(gè)“數(shù)字電子技術(shù)”課程的教學(xué)中占據(jù)了重要地位，貫穿了整個(gè)課程的教學(xué)過程。如何在教學(xué)過程中使學(xué)生快速、準(zhǔn)確地理解卡諾圖化簡的原理、方法和技巧是課程教學(xué)的重點(diǎn)和難點(diǎn)。本文基于教學(xué)實(shí)踐經(jīng)驗(yàn)，探討了卡諾圖化簡邏輯函數(shù)的一些課堂教學(xué)方法，從卡諾圖化簡的原理出發(fā)，對化簡方法和技巧的教學(xué)進(jìn)行了有益的嘗試，希望能夠?yàn)閷W(xué)生提高卡諾圖的學(xué)習(xí)效率提供一定的幫助。