卡諾圖化簡(jiǎn)數(shù)學(xué)新方法

葉 騰，朱桂英

（1.上海交通大學(xué)安泰經(jīng)濟(jì)與管理學(xué)院，上海 200240；2.河北工程大學(xué)裝備制造學(xué)院，河北邯鄲 056029）

卡諾圖化簡(jiǎn)數(shù)學(xué)新方法

葉 騰1，朱桂英2

（1.上海交通大學(xué)安泰經(jīng)濟(jì)與管理學(xué)院，上海 200240；2.河北工程大學(xué)裝備制造學(xué)院，河北邯鄲 056029）

提出了卡諾圖化簡(jiǎn)中獲得卡諾圈合并結(jié)果的數(shù)學(xué)方法。根據(jù)卡諾圖制圖原理，這種數(shù)學(xué)計(jì)算方法的要點(diǎn)在于：用2個(gè)最小項(xiàng)對(duì)應(yīng)的十進(jìn)制數(shù)之差找到消去變量；從卡諾圈的某個(gè)最小項(xiàng)中去掉相應(yīng)消去變量得到合并結(jié)果。該方法在卡諾圖（尤其變量數(shù)較多的）化簡(jiǎn)中，能更準(zhǔn)確、更迅速地獲得卡諾圈合并結(jié)果，并可應(yīng)用于計(jì)算機(jī)輔助卡諾圖化簡(jiǎn)邏輯函數(shù)。

卡諾圖；應(yīng)用數(shù)學(xué)方法；簡(jiǎn)化法

邏輯函數(shù)化簡(jiǎn)是數(shù)字邏輯和數(shù)字電路分析中的重要內(nèi)容，目前主要有代數(shù)化簡(jiǎn)法、表格化簡(jiǎn)法和卡諾圖化簡(jiǎn)法。代數(shù)方法是基于布爾代數(shù)基本運(yùn)算公式進(jìn)行化簡(jiǎn)的方法，這種方法要求操作者掌握一定的技巧，并對(duì)最簡(jiǎn)結(jié)果有一定的判斷能力?？ㄖZ圖化簡(jiǎn)法是6個(gè)以下變量邏輯函數(shù)化簡(jiǎn)最簡(jiǎn)便而常用的方法。

近年來(lái)，人們對(duì)卡諾圖進(jìn)行了多方面的研究和拓展，包括卡諾圖鏡像畫(huà)圈法［1］、最小項(xiàng)使用的重復(fù)次數(shù)識(shí)別技巧［2］、填圖技巧［3］、卡諾圖降維簡(jiǎn)化法［4］、卡諾圖的計(jì)算機(jī)輔助實(shí)現(xiàn)［5］等方法，對(duì)如何快速、準(zhǔn)確地確定卡諾圈合并項(xiàng)結(jié)果卻沒(méi)有很好的解決方法，導(dǎo)致在實(shí)際應(yīng)用（尤其是在四變量、五變量、六變量卡諾圖中）時(shí)，人們?nèi)菀谆煜兞课恢茫灾抡`讀最小項(xiàng)合并結(jié)果。筆者提出的卡諾圖化簡(jiǎn)數(shù)學(xué)方法可解決上述問(wèn)題。

1 基本步驟

1.1 畫(huà)卡諾圖

在“與 －或”表達(dá)式的基礎(chǔ)上，畫(huà)出邏輯函數(shù)的卡諾圖，步驟如下［6］：

1）畫(huà)出函數(shù)變量的卡諾圖。

2）在圖中標(biāo)示每一個(gè)乘積項(xiàng)所包含的最小項(xiàng)，就得到邏輯函數(shù)的卡諾圖。

其中，如果乘積項(xiàng)為最小項(xiàng)，則可直接轉(zhuǎn)換成數(shù)字代碼對(duì)應(yīng)填入卡諾圖。在二進(jìn)制對(duì)應(yīng)數(shù)中，原變量代表該位為1，反變量代表該位是0。這樣將乘積項(xiàng)（即最小項(xiàng)）轉(zhuǎn)化為二進(jìn)制對(duì)應(yīng)數(shù)，再將二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)，填入對(duì)應(yīng)編號(hào)的小方格中。如，AB′C＝101＝5，所以填入m5。如表達(dá)式不是最小項(xiàng)表達(dá)式，但是“與－或”表達(dá)式可將其先轉(zhuǎn)化成最小項(xiàng)表達(dá)式，再填入卡諾圖，再按上述規(guī)則填入。也可根據(jù)乘積項(xiàng)是最小項(xiàng)的公因子這一特點(diǎn)直接觀察填入。

1.2 畫(huà)卡諾圈

畫(huà)圈規(guī)則與傳統(tǒng)卡諾圈規(guī)則相似，具體規(guī)則如下［7］：

在標(biāo)示出的相鄰最小項(xiàng)中畫(huà)圈，盡量畫(huà)大圈，但每個(gè)圈內(nèi)只能含有2n（n＝0，1，2，…）個(gè)相鄰項(xiàng)。要特別注意對(duì)邊相鄰性和四角相鄰性。

圈的個(gè)數(shù)盡量少。在新畫(huà)的包圍圈中至少要含有1個(gè)未被圈過(guò)的標(biāo)識(shí)方格，否則該包圍圈是多余的?？ㄖZ圖中所有標(biāo)示過(guò)的方格均要被圈過(guò)，即不能漏下標(biāo)示過(guò)的最小項(xiàng)。

1.3 合并卡諾圈中的最小項(xiàng)

任意選取卡諾圈中的最小項(xiàng)，寫(xiě)出由變量組成的邏輯式（由于系數(shù)小的最小項(xiàng)邏輯式相對(duì)容易寫(xiě)，所以一般選取卡諾圈中系數(shù)最小的最小項(xiàng)）。然后找出卡諾圈中系數(shù)之差為2n的所有差值，從邏輯式中消去所有差值對(duì)應(yīng)位的變量。如miniterm1＝x1，miniterm2＝x2，w＝log2｜x1－x2｜＋1，則消去從右至左第w位的變量。將所有差值對(duì)應(yīng)變量消去后的邏輯式即為卡諾圈合并結(jié)果。

1）對(duì)包含2n個(gè)最小項(xiàng)的卡諾圈來(lái)說(shuō)，只需要找到n種不同的2n的差，如1，2，4，8等，然后將這些差所代表的變量從卡諾圈中系數(shù)較小的最小項(xiàng)中去掉，即為該圈的最終合并結(jié)果。

2）找差技巧：①將左上角的數(shù)，先分別和它右相鄰數(shù)、下相鄰數(shù)作差，再分別和圈中首行行尾、首列列尾數(shù)作差，這5個(gè)位置一般就可以把差找全；②將圈中最大數(shù)減去最小數(shù)，并將差表示成若干個(gè)2n的和，每一個(gè)2n必定是一種兩項(xiàng)差。

1.4 寫(xiě)出最簡(jiǎn)“與 －或”表達(dá)式

將所有卡諾圈的計(jì)算結(jié)果相與（用加號(hào)相連），即為最終合并結(jié)果。

2 實(shí)例展示

圖1 四變量卡諾圖Fig.1 Four－variable map

例1［8］化簡(jiǎn)F（A，B，C，D）＝∑（0，1，2，6，8，9，10）。

解 傳統(tǒng)方法如下：

第1步，畫(huà)出四變量卡諾圖，見(jiàn)圖1。

第2步，畫(huà)出傳統(tǒng)卡諾圖，見(jiàn)圖2，觀察對(duì)應(yīng)變量，計(jì)算邏輯函數(shù)結(jié)果。

新算法見(jiàn)圖3，其中A為8，B為4，C為2，D為1，圖中有以下3個(gè)卡諾圈。

卡諾圈1（見(jiàn)圖4）：min｛0，2，8，10｝＝0＝A′B′C′D′，該卡諾圈包含4個(gè)最小項(xiàng)，4＝22，因此需要找2個(gè)不同的2的冪的差。8－0＝8，所以消掉的變量是A；2－0＝2，所以消掉的變量是C。消掉A，C，為B′D′。

卡諾圈2（見(jiàn)圖5）：min｛0，1，8，9｝＝0＝A′B′C′D′，該卡諾圈包含4個(gè)最小項(xiàng)，4＝22，因此需要找2個(gè)不同的2的冪的差。1－0＝1，所以消掉的變量是D；8－0＝8，所以消掉的變量是A；A′B′C′D′中消掉A，D，為B′C′。

卡諾圈3（見(jiàn)圖6）：6－2＝4所以消掉的變量是B，min｛2，6｝＝2＝A′B′CD′，消掉B為A′CD′。所以原函數(shù)結(jié)果是F（A，B，C）＝∑（0，1，2，6，8，9，10）＝B′C′＋B′D′＋A′CD′。

例2 化簡(jiǎn)F（A，B，C，D，E）＝∑（4，5，6，7，9，11，13，15，16，24，27，31）。

解 傳統(tǒng)方法如下.

第1步，畫(huà)出五變量卡諾圖，見(jiàn)圖7。

第2步，畫(huà)出對(duì)應(yīng)函數(shù)的傳統(tǒng)卡諾圖見(jiàn)圖8。可見(jiàn)五變量用傳統(tǒng)的卡諾圖已經(jīng)很難快速分辨合并后的結(jié)果。

卡諾圖化簡(jiǎn)新方法計(jì)算如下（見(jiàn)圖9）。

變量對(duì)應(yīng)十進(jìn)制數(shù)為A：16，B：8，C：4，D：2，E：1；圖中共4個(gè)卡諾圈。

卡諾圈1（見(jiàn)圖10）：min｛4，5，6，7｝＝4＝A′B′CD′E′。該卡諾圈包含4個(gè)最小項(xiàng)，4＝22，因此需要找2個(gè)不同的2的冪的差。5－4＝1，消掉的變量是E；6－4＝2，消掉的變量是D；A′B′CD′E′消掉D，E，即A′B′C。

卡諾圈2（見(jiàn)圖11）：min｛9，11，13，15｝＝9＝A′BC′D′E。該卡諾圈包含4個(gè)最小項(xiàng)，同理需要找2個(gè)不同的2的冪的差。13－9＝4，消掉的變量是C；15－13＝2，消掉的變量是D；消掉變量C，D，即A′BE。

卡諾圈3（見(jiàn)圖12）：min｛15，31，11，27｝＝11＝A′BC′DE。該卡諾圈包含4個(gè)最小項(xiàng)，同理需要找2個(gè)不同的2的冪的差。15－11＝4，消掉的變量是C；31－15＝16，消掉的變量是A；消掉A，C，即BDE。

卡諾圈4（見(jiàn)圖13）：24－16＝8，所以消掉的是C。min｛16，24｝＝16＝AB′C′D′E′，消掉C，即AB′D′E′。

圖7 五變量卡諾圖Fig.7 Five－variable map

3 結(jié) 論

本文提出的卡諾圖化簡(jiǎn)新方法是通過(guò)找到卡諾圈中系數(shù)較小的最小項(xiàng)并結(jié)合作差消元法確定卡諾圈中各項(xiàng)的合并結(jié)果，進(jìn)而最終確定邏輯函數(shù)合并結(jié)果的邏輯函數(shù)簡(jiǎn)化法。該方法具有以下優(yōu)點(diǎn)：

1）不需通過(guò)肉眼查找變量就能確定卡諾圈合并結(jié)果的簡(jiǎn)單易行的數(shù)學(xué)方法。即通過(guò)卡諾圈中最小項(xiàng)對(duì)應(yīng)十進(jìn)制數(shù)作差確定消去變量，再結(jié)合卡諾圈中系數(shù)最小的最小項(xiàng)最終合并結(jié)果。

2）普通卡諾圖總共需畫(huà)2張圖，1張對(duì)應(yīng)變量數(shù)的基本卡諾圖，1張只包含0或1的函數(shù)卡諾圖，填圖需要先將最小項(xiàng)所對(duì)應(yīng)的十進(jìn)制表格標(biāo)出，再另畫(huà)1張圖并在相應(yīng)位置標(biāo)0或1。而筆者提出的新方法只需畫(huà)1張圖，省略了另畫(huà)圖標(biāo)0或1的步驟，可直接在十進(jìn)制表格上操作。節(jié)省了1個(gè)步驟，可以使效率進(jìn)一步提高。

3）由于這種方法基于作差與大小比較這2種數(shù)學(xué)運(yùn)算，故可以在卡諾圖的計(jì)算機(jī)輔助化簡(jiǎn)中大大簡(jiǎn)化邏輯運(yùn)算。

［1］ 宋海聲.化簡(jiǎn)邏輯函數(shù)的新方法［J］.西北師范大學(xué)學(xué)報(bào)（自然科學(xué)版）（Journal of Northwest Normal University（Natural Science）），2002，38（3）：37－41.

［2］ 韓建華.卡諾圖化簡(jiǎn)多函數(shù)的簡(jiǎn)便方法［J］.華東地質(zhì)學(xué)院學(xué)報(bào)（Journal of East China Geological Institute），1998，21（4）：392－395.

［3］ 江素云.使用卡諾圖的技巧［J］.科協(xié)論壇（Science ＆Technology Association Forum），2009（12）：104－105.

［4］ 郭煥銀.談降維卡諾圖化簡(jiǎn)邏輯函數(shù)的方法［J］.淮南師范學(xué)院學(xué)報(bào)（Journal of Huainan Teachers College），2001，3（2）：5－6.

［5］ 喻國(guó)平.邏輯函數(shù)的計(jì)算機(jī)輔助卡諾圖化簡(jiǎn)［J］.南昌大學(xué)學(xué)報(bào)（工科版）（Journal of Nanchang University（Natural Science）），1996，18（3）：51－53.

［6］ 朱定華.數(shù)字電路與邏輯設(shè)計(jì)［M］.北京：清華大學(xué)出版社，2011.

［7］ 吳繼娟.數(shù)字邏輯［M］.北京：人民郵電出版社，2008.

［8］ MORRIS M M.Computer System Architecture［M］.3rd ed.London：Prentice－Hall International，2002.

New mathomatical simplification method of Karnaugh map

YE Teng1，ZHU Gui－ying2
（1.Antai College of Economics and Management，Shanghai Jiaotong University，Shanghai 200240，China；2.Equipment Manufacturing College，Hebei University of Engineering，Handan Hebei 056029，China）

A mathematical method is provided to get the combination solution of variables in the encircling of Karnaugh map.Based on the basic theory of K－map，two key points of the method are：Ascertaining the complementary variables by the differences of the corresponding decimal indexes of the two miniterms；Eliminating the complementary variables from the corresponding miniterm in the encircling and qetting get the combination results.The method provides more efficient and accurate way to simplify logic functions based on K－map.It can also be applied to Karnaugh map of any number of variables and to simplification by K－map with computer assistance.

Karnaugh map；mathematical method；simplification method

O142

A

1008－1542（2012）03－0202－05

2012－02－17；責(zé)任編輯：張 軍

葉 騰（1990－），女，河北大城人，主要從事信息系統(tǒng)及管理方面的研究。

朱桂英副教授。E－mail：Zhu0gui0ying＠163.com