卡諾圖簡(jiǎn)介

　　卡諾圖是邏輯函數(shù)的一種圖形表示。一個(gè)邏輯函數(shù)的卡諾圖就是將此函數(shù)的最小項(xiàng)表達(dá)式中的各最小項(xiàng)相應(yīng)地填入一個(gè)方格圖內(nèi)，此方格圖稱為卡諾圖。

　　卡諾圖的構(gòu)造特點(diǎn)使卡諾圖具有一個(gè)重要性質(zhì)：可以從圖形上直觀地找出相鄰最小項(xiàng)。兩個(gè)相鄰最小項(xiàng)可以合并為一個(gè)與項(xiàng)并消去一個(gè)變量。

　　卡諾圖結(jié)構(gòu)特點(diǎn)

　　卡諾圖中最小項(xiàng)的排列方案不是唯一的，變量的坐標(biāo)值0表示相應(yīng)變量的反變量，1表示相應(yīng)變量的原變量，變量的取值變化規(guī)律按“循環(huán)碼”變化［1］。各小方格依變量順序取坐標(biāo)值，所得二進(jìn)制數(shù)對(duì)應(yīng)的十進(jìn)制數(shù)即相應(yīng)最小項(xiàng)的下標(biāo)i。

　　在五變量卡諾圖中，為了方便省略了符號(hào)“m”，直接標(biāo)出m的下標(biāo)i。

　　歸納起來，卡諾圖在構(gòu)造上具有以下兩個(gè)特點(diǎn)：

　　☆n個(gè)變量的卡諾圖由2^n個(gè)小方格組成，每個(gè)小方格代表一個(gè)最小項(xiàng)；

　　☆卡諾圖上處在相鄰、相對(duì)、相重位置的小方格所代表的最小項(xiàng)為相鄰最小項(xiàng)。

　　可以從圖形上直觀地找出相鄰最小項(xiàng)。兩個(gè)相鄰最小項(xiàng)可以合并為一個(gè)與項(xiàng)并消去一個(gè)變量。

　　卡諾圖化簡(jiǎn)函數(shù)

　　1．幾個(gè)定義

　　蘊(yùn)涵項(xiàng)：在函數(shù)的“與-或”表達(dá)式中，每個(gè)“與”項(xiàng)被稱為該函數(shù)的蘊(yùn)涵項(xiàng)（Implicant）。

　　顯然，在函數(shù)卡諾圖中，任何一個(gè)1方格所對(duì)應(yīng)的最小項(xiàng)或者卡諾圈中的2m個(gè)1方格所對(duì)應(yīng)的“與”項(xiàng)都是函數(shù)的蘊(yùn)涵項(xiàng)。

　　質(zhì)蘊(yùn)涵項(xiàng)：若函數(shù)的一個(gè)蘊(yùn)涵項(xiàng)不是該函數(shù)中其他蘊(yùn)涵項(xiàng)的子集，則此蘊(yùn)涵項(xiàng)稱為質(zhì)蘊(yùn)涵項(xiàng)（PrimeImplicant），簡(jiǎn)稱為質(zhì)項(xiàng)。

　　顯然，在函數(shù)卡諾圖中，按照最小項(xiàng)合并規(guī)律，如果某個(gè)卡諾圈不可能被其他更大的卡諾圈包含，那么，該卡諾圈所對(duì)應(yīng)的“與”項(xiàng)為質(zhì)蘊(yùn)涵項(xiàng)。

　　必要質(zhì)蘊(yùn)涵項(xiàng)：若函數(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)（EssentialPrimeImplicant），簡(jiǎn)稱為必要質(zhì)項(xiàng)。

　　在函數(shù)卡諾圖中，若某個(gè)卡諾圈包含了不可能被任何其他卡諾圈包含的1方格，那么，該卡諾圈所對(duì)應(yīng)的“與”項(xiàng)為必要質(zhì)蘊(yùn)涵項(xiàng)。

　　2．求函數(shù)最簡(jiǎn)“與-或”表達(dá)式

　　（1）一般步驟：第一步：作出函數(shù)的卡諾圖。

　　第二步：在卡諾圖上圈出函數(shù)的全部質(zhì)蘊(yùn)涵項(xiàng)。按照卡諾圖上最小項(xiàng)的合并規(guī)律，對(duì)函數(shù)F卡諾圖中的1方格畫卡諾圈。為了圈出全部質(zhì)蘊(yùn)涵項(xiàng)，畫卡諾圈時(shí)在滿足合并規(guī)律的前提下應(yīng)盡可能大，若卡諾圈不可能被更大的卡諾圈包圍，則對(duì)應(yīng)的“與”項(xiàng)為質(zhì)蘊(yùn)涵項(xiàng)。

　　第三步：從全部質(zhì)蘊(yùn)涵項(xiàng)中找出所有必要質(zhì)蘊(yùn)涵項(xiàng)。在卡諾圖上只被一個(gè)卡諾圈包圍的最小項(xiàng)被稱為必要最小項(xiàng)，包含必要最小項(xiàng)的質(zhì)蘊(yùn)涵項(xiàng)即必要質(zhì)蘊(yùn)涵項(xiàng)。為了保證所得結(jié)果無一遺漏地覆蓋函數(shù)的所有最小項(xiàng)，函數(shù)表達(dá)式中必須包含所有必要質(zhì)蘊(yùn)涵項(xiàng)。

　　第四步：求出函數(shù)的最簡(jiǎn)質(zhì)蘊(yùn)涵項(xiàng)集。若函數(shù)的所有必要質(zhì)蘊(yùn)涵項(xiàng)尚不能覆蓋卡諾圖上的所有1方格，則從剩余質(zhì)蘊(yùn)涵項(xiàng)中找出最簡(jiǎn)的所需質(zhì)蘊(yùn)涵項(xiàng)，使它和必要質(zhì)蘊(yùn)涵項(xiàng)一起構(gòu)成函數(shù)的最小覆蓋。

　　歸納起來，卡諾圖化簡(jiǎn)的原則是：

　　☆在覆蓋函數(shù)中的所有最小項(xiàng)的前提下，卡諾圈的個(gè)數(shù)達(dá)到最少。

　　☆在滿足合并規(guī)律的前提下卡諾圈應(yīng)盡可能大。

　　☆根據(jù)合并的需要，每個(gè)最小項(xiàng)可以被多個(gè)卡諾圈包圍。

　　3.求函數(shù)的最簡(jiǎn)“或-與”表達(dá)式

　　當(dāng)需要求一個(gè)函數(shù)的最簡(jiǎn)“或-與”表達(dá)式時(shí)，可采用“兩次取反法”。

　　具體如下：

　　☆先求出函數(shù)F的反函數(shù)F的最簡(jiǎn)“與-或”表達(dá)（合并卡諾圖上的0方格）；

　　☆然后對(duì)F的最簡(jiǎn)“與-或”表達(dá)式取反，從而得到函數(shù)F的最簡(jiǎn)“或-與”表達(dá)式。

　　卡諾圖化簡(jiǎn)邏輯函數(shù)具有方便、直觀、容易掌握等優(yōu)點(diǎn)。但依然帶有試湊性。尤其當(dāng)變量個(gè)數(shù)大于6時(shí)，畫圖以及對(duì)圖形的識(shí)別都變得相當(dāng)復(fù)雜。

　　卡諾圖化簡(jiǎn)的步驟

　?、艑⑦壿嫼瘮?shù)變換為與-或式。

　?、飘嫵鲞壿嫼瘮?shù)的卡諾圖。

　?、菍?的n次方個(gè)為1的相鄰方格（相鄰項(xiàng)）分別畫包圍圈，每個(gè)包圍圈的公因子作為乘積項(xiàng)。

　　⑷將每個(gè)乘積項(xiàng)項(xiàng)相加，就得到最簡(jiǎn)的與-或表達(dá)式。

　　二變量卡諾位置圖

　　卡諾圖化簡(jiǎn)方法

　　一、邏輯函數(shù)的卡諾圖表示法

　　將n變量的全部最小項(xiàng)各用一個(gè)小方塊表示，并使具有邏輯相鄰性的最小項(xiàng)在幾何位置上也相鄰地排列起來，所得到的圖形稱為n變量最小項(xiàng)的卡諾圖。

　　為了保證圖中幾何位置相鄰地最小項(xiàng)在邏輯上也具有相鄰性，這些數(shù)碼不能按自然二進(jìn)制數(shù)從小到大地順序排列，而必須按圖中的方式排列，以確保相鄰的兩個(gè)最小項(xiàng)僅有一個(gè)變量是不同的。

　　從卡諾圖上可以看到，處在任何一行或一列兩端的最小項(xiàng)也僅有一個(gè)變量不同，所以它們也具有邏輯相鄰性。因此，從幾何位置上應(yīng)當(dāng)將卡諾圖看成是上下、左右閉合的圖形。

　　任何一個(gè)邏輯函數(shù)都能表示為若干最小項(xiàng)之和的形式，自然也可以用卡諾圖來表示任意一個(gè)邏輯函數(shù)。具體做法是：首先將邏輯函數(shù)化為最小項(xiàng)之和的形式，然后在卡諾圖上標(biāo)出與之相對(duì)應(yīng)的最小項(xiàng)，在其余位置上標(biāo)入0，就得到了表示該邏輯函數(shù)的卡諾圖。也就是說，任何一個(gè)邏輯函數(shù)都等于卡諾圖中填入1的那些最小項(xiàng)之和。

　　二、用卡諾圖化解邏輯函數(shù)

　　化簡(jiǎn)時(shí)依據(jù)的基本原理就是具有相鄰性的最小項(xiàng)可以合并，并消去不同的因子。由于在卡諾圖上幾何位置相鄰與邏輯上的相鄰性是一致的，因而從卡諾圖上能直觀的找出那些具有相鄰性的最小項(xiàng)并將其合并化簡(jiǎn)。

　　合并最小項(xiàng)的原則：若兩個(gè)最小項(xiàng)相鄰，則可以合并為一項(xiàng)并消去一對(duì)因子。若四個(gè)最小項(xiàng)相鄰并排列成一個(gè)矩形組，則可合并為一項(xiàng)并消去兩隊(duì)因子。若八個(gè)最小項(xiàng)相鄰并且排列成一個(gè)矩形組，則可以合并成一項(xiàng)并消去三對(duì)因子。合并后的結(jié)果中只剩下公共因子。

　　卡諾圖化簡(jiǎn)法步驟

　?。ㄒ唬⒑瘮?shù)式化為最小項(xiàng)之和的形式；

　　（二）畫出表示該邏輯函數(shù)的卡諾圖；

　　（三）找出可以合并的最小項(xiàng)；

　?。ㄋ模┊嫵霭鼑Σ⑦x取化簡(jiǎn)后的乘積項(xiàng)。

　　在畫包圍圈時(shí)要注意：

　?。ㄒ唬┌鼑υ酱笤胶?；

　?。ǘ┌鼑Φ膫€(gè)數(shù)越少越好；

　?。ㄈ┩粋€(gè)“1”方塊可以被圈多次；

　?。ㄋ模┊嫲鼑r(shí)，可先圈大，再圈小；

　?。ㄎ澹┟總€(gè)圈要有新的成分，如果某一圈中所有的“1”方塊均被別的包圍圈包圍，就可以舍掉這個(gè)包圍圈；

　?。┎灰z漏任何方塊。

　　通常我們都是通過合并卡諾圖中的1來求得化簡(jiǎn)結(jié)果得。但有時(shí)也可以通過合并卡諾圖中的0先求出‘Y的化簡(jiǎn)結(jié)果，然后再將’Y求反而得到Y(jié)。