淺析卡諾圖的降維

1、第6卷第卷第3期湖北職業(yè)技術(shù)學(xué)院學(xué)報(bào)No.3Vol.620032003年9月JournalJournalofofHubeiHubeiVocationalTechnicalVocationalTechnicalCollegeCollegeSep.Sep.20032003[收稿日期收稿日期]20032003―0606―1818[作者簡(jiǎn)介作者簡(jiǎn)介]萬(wàn)學(xué)斌（萬(wàn)學(xué)斌（19631963－）－），男，湖北孝感人，湖北職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系講師

2、，主要研究電工、電子、，男，湖北孝感人，湖北職業(yè)技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系講師，主要研究電工、電子、數(shù)字邏輯電路。數(shù)字邏輯電路。67[文章編號(hào)文章編號(hào)]167181782003167181782003（0303）－）－00670067－0404淺析卡淺析卡諾圖諾圖的降的降維萬(wàn)學(xué)斌萬(wàn)學(xué)斌（湖北職業(yè)技術(shù)學(xué)院，湖北（湖北職業(yè)技術(shù)學(xué)院，湖北孝感孝感432000432000）[摘要]文章提出了一種多文章提出了一種多變量邏輯邏輯函數(shù)化函數(shù)化簡(jiǎn)的卡的

3、卡諾圖諾圖法降維卡諾圖諾圖法，從而有效法，從而有效擴(kuò)展了卡展了卡諾圖化簡(jiǎn)的適用范的適用范圍。[關(guān)鍵詞關(guān)鍵詞]卡諾變諾變量；降量；降維變維變量；卡量；卡諾圖諾圖；降；降維卡諾圖諾圖[中圖分類(lèi)號(hào)中圖分類(lèi)號(hào)]TP331.2TP331.2[文獻(xiàn)標(biāo)識(shí)碼文獻(xiàn)標(biāo)識(shí)碼]A在數(shù)字邏輯電路中，化簡(jiǎn)邏輯函數(shù)是分析和在數(shù)字邏輯電路中，化簡(jiǎn)邏輯函數(shù)是分析和設(shè)計(jì)數(shù)字邏輯電路的重要理論基礎(chǔ)和基本技能。設(shè)計(jì)數(shù)字邏輯電路的重要理論基礎(chǔ)和基本技能。我們知道，邏輯化簡(jiǎn)有兩種

4、方法：一種是代數(shù)法我們知道，邏輯化簡(jiǎn)有兩種方法：一種是代數(shù)法化簡(jiǎn)；另一種是卡諾圖化簡(jiǎn)。前者化簡(jiǎn)過(guò)程技巧化簡(jiǎn)；另一種是卡諾圖化簡(jiǎn)。前者化簡(jiǎn)過(guò)程技巧性強(qiáng)，結(jié)果是否為最簡(jiǎn)還不太容易確定，而后一性強(qiáng)，結(jié)果是否為最簡(jiǎn)還不太容易確定，而后一種方法卻克服了前者的不足，使化簡(jiǎn)變得更加可種方法卻克服了前者的不足，使化簡(jiǎn)變得更加可操作，更重要的是它還可以化簡(jiǎn)具有隨意項(xiàng)的邏操作，更重要的是它還可以化簡(jiǎn)具有隨意項(xiàng)的邏輯函數(shù)，這是代數(shù)法化簡(jiǎn)無(wú)能為力的，但是卡諾輯

5、函數(shù)，這是代數(shù)法化簡(jiǎn)無(wú)能為力的，但是卡諾圖法化簡(jiǎn)受邏輯變量個(gè)數(shù)限制，當(dāng)邏輯變量個(gè)數(shù)圖法化簡(jiǎn)受邏輯變量個(gè)數(shù)限制，當(dāng)邏輯變量個(gè)數(shù)多于多于5時(shí)，卡諾圖化簡(jiǎn)就顯得有些麻煩，如果使時(shí)，卡諾圖化簡(jiǎn)就顯得有些麻煩，如果使用引入變量的卡諾圖化簡(jiǎn)，就會(huì)使多變量函數(shù)化用引入變量的卡諾圖化簡(jiǎn)，就會(huì)使多變量函數(shù)化簡(jiǎn)變得簡(jiǎn)單簡(jiǎn)變得簡(jiǎn)單[1][1]，下面介紹引入變量的卡諾圖化簡(jiǎn)，下面介紹引入變量的卡諾圖化簡(jiǎn)問(wèn)題。問(wèn)題。一卡諾化簡(jiǎn)的依據(jù)和概念卡諾化簡(jiǎn)的依據(jù)和概念卡諾

6、圖法化簡(jiǎn)是利用格雷碼表，直觀(guān)地反映卡諾圖法化簡(jiǎn)是利用格雷碼表，直觀(guān)地反映邏輯函數(shù)最小項(xiàng)之間邏輯相鄰關(guān)系的方格圖，它邏輯函數(shù)最小項(xiàng)之間邏輯相鄰關(guān)系的方格圖，它不僅是表達(dá)邏輯函數(shù)的一種方式，而且也是化簡(jiǎn)不僅是表達(dá)邏輯函數(shù)的一種方式，而且也是化簡(jiǎn)邏輯函數(shù)的一種工具。在卡諾圖上把邏輯相鄰項(xiàng)邏輯函數(shù)的一種工具。在卡諾圖上把邏輯相鄰項(xiàng)安排在幾何相鄰位置，使相鄰項(xiàng)能簡(jiǎn)化為一個(gè)與安排在幾何相鄰位置，使相鄰項(xiàng)能簡(jiǎn)化為一個(gè)與項(xiàng)，同時(shí)也使邏輯變量個(gè)數(shù)減少。當(dāng)

7、變量個(gè)數(shù)多項(xiàng)，同時(shí)也使邏輯變量個(gè)數(shù)減少。當(dāng)變量個(gè)數(shù)多于五個(gè)時(shí)，卡諾化簡(jiǎn)就顯得有些麻煩，可以使用于五個(gè)時(shí)，卡諾化簡(jiǎn)就顯得有些麻煩，可以使用引入變量的卡諾圖化簡(jiǎn)，這樣一來(lái)就使得卡諾圖引入變量的卡諾圖化簡(jiǎn)，這樣一來(lái)就使得卡諾圖中的變量數(shù)中的變量數(shù)n和邏輯變量數(shù)和邏輯變量數(shù)m不再相等（不再相等（mnmn），為討論方便，定義以下概念：為討論方便，定義以下概念：1、引入變量的卡諾圖稱(chēng)為降維卡諾圖。、引入變量的卡諾圖稱(chēng)為降維卡諾圖。2、k=mk=m－

8、n為卡諾圖降維階數(shù)，為卡諾圖降維階數(shù)，k為降維變量為降維變量數(shù)，數(shù)，m為邏輯變量數(shù)，為邏輯變量數(shù)，n為卡諾變量數(shù)。為卡諾變量數(shù)。3、k=1k=1為一階降維卡諾圖，為一階降維卡諾圖，k≥2為高階降維為高階降維卡諾圖?？ㄖZ圖。當(dāng)k=0k=0時(shí)，每一個(gè)小方格代表一個(gè)最小項(xiàng)，時(shí)，每一個(gè)小方格代表一個(gè)最小項(xiàng)，小方格中只能是小方格中只能是1（表示該最小項(xiàng)存在）和（表示該最小項(xiàng)存在）和0（表（表示該最小項(xiàng)不存在）或者是隨意項(xiàng)。示該最小項(xiàng)不存在）或者是

9、隨意項(xiàng)。當(dāng)k≠0，使得降維卡諾圖面積表示只有原卡，使得降維卡諾圖面積表示只有原卡諾圖表面積的諾圖表面積的1212k，它的每個(gè)小方格實(shí)際上是原，它的每個(gè)小方格實(shí)際上是原卡諾圖卡諾圖2k個(gè)最小項(xiàng)的集合。為此，小方格的填寫(xiě)個(gè)最小項(xiàng)的集合。為此，小方格的填寫(xiě)就有四種可能的情形：就有四種可能的情形：⑴、填寫(xiě)、填寫(xiě)1，表示函數(shù)包含有，表示函數(shù)包含有2k個(gè)最小項(xiàng)，個(gè)最小項(xiàng)，即該最小項(xiàng)中只包含有卡諾變量而不包含降維變即該最小項(xiàng)中只包含有卡諾變量而不包含

10、降維變量。量。⑵、填寫(xiě)、填寫(xiě)0，表示一個(gè)最小項(xiàng)也不包含，即卡，表示一個(gè)最小項(xiàng)也不包含，即卡諾變量和降維變量都不包含。諾變量和降維變量都不包含。⑶、填寫(xiě)降維變量函數(shù)，表示、填寫(xiě)降維變量函數(shù)，表示2k最小項(xiàng)中的最小項(xiàng)中的部分最小項(xiàng)之和。部分最小項(xiàng)之和。⑷、填寫(xiě)隨意項(xiàng)。、填寫(xiě)隨意項(xiàng)。湖北職業(yè)技術(shù)學(xué)院學(xué)報(bào)湖北職業(yè)技術(shù)學(xué)院學(xué)報(bào)2003年第年第3期第6卷第卷第3期69只有卡諾變量，而不含降維變量。只有卡諾變量，而不含降維變量。2、然后對(duì)降維卡諾圖中

11、降維變量的小方格進(jìn)行合并，合并原則也和對(duì)“1”的合并原則相似，不過(guò)不過(guò)這時(shí)這時(shí)“1”的小方格可視為含有任意項(xiàng)的方格，的小方格可視為含有任意項(xiàng)的方格，得到卡諾變量的與項(xiàng)必須再與上降維變量項(xiàng)。得到卡諾變量的與項(xiàng)必須再與上降維變量項(xiàng)。例3：以例：以例2為例化簡(jiǎn)一階降維函數(shù)為例化簡(jiǎn)一階降維函數(shù)F解：根據(jù)降維卡諾圖解：根據(jù)降維卡諾圖4，據(jù)化簡(jiǎn)原則，，據(jù)化簡(jiǎn)原則，BCBCAOOOOO1O111111O1OO111D1DD11圖4F的化簡(jiǎn)的化簡(jiǎn)由圖由

12、圖4得：得：BCDABBAF????此題化簡(jiǎn)也可以把此題化簡(jiǎn)也可以把m1和m3合并為合并為，則：，則：CACADABBAF????例4：用二階降維卡諾圖化簡(jiǎn)邏輯函數(shù)：用二階降維卡諾圖化簡(jiǎn)邏輯函數(shù)BCDDBAABF????解：選取解：選取A、B為卡諾變量，為卡諾變量，C、D為降維變?yōu)榻稻S變量，則量，則F的二階降維卡諾圖為圖的二階降維卡諾圖為圖5。AB=AB=∑m(3)m(3)=∑m(0)m(0)DDBABC=BC=∑m(1m(1，3)3)

13、C=∑m(0m(0，1，2，3)3)DDBAO1ODDD（0）CCD（1）1D（2）11CCD（3）圖5填寫(xiě)填寫(xiě)F的二階降維卡諾圖的二階降維卡諾圖圖5運(yùn)算后為圖運(yùn)算后為圖6，BAO1O1CCD1D1圖6F二階降維卡諾圖二階降維卡諾圖由圖由圖6化簡(jiǎn)得：化簡(jiǎn)得：BCDABBAF????化簡(jiǎn)后的結(jié)果與前面講的一階降維卡諾圖法化簡(jiǎn)后的結(jié)果與前面講的一階降維卡諾圖法化簡(jiǎn)的結(jié)果完全相同，實(shí)際上也可用四變量卡諾化簡(jiǎn)的結(jié)果完全相同，實(shí)際上也可用四變量卡

14、諾圖化簡(jiǎn)來(lái)驗(yàn)證例圖化簡(jiǎn)來(lái)驗(yàn)證例3和例和例4結(jié)果，從而證明降維卡結(jié)果，從而證明降維卡諾圖法的正確性。諾圖法的正確性。四含有隨意項(xiàng)的降維卡諾圖的化簡(jiǎn)含有隨意項(xiàng)的降維卡諾圖的化簡(jiǎn)[3][3]邏輯函數(shù)中隨意項(xiàng)是指邏輯變量組合不會(huì)出現(xiàn)，邏輯函數(shù)值隨意；或者邏輯變量組合出現(xiàn)后，邏輯函數(shù)值隨意。隨意項(xiàng)邏輯函數(shù)值可視為0或者1[1]。為了把隨意項(xiàng)和確定項(xiàng)區(qū)分開(kāi)來(lái)，隨意項(xiàng)函數(shù)值填入卡諾圖小方格時(shí)用括號(hào)括起來(lái)，由于其邏輯函數(shù)值可為1或?yàn)?，因而在合并時(shí)視邏

15、輯化簡(jiǎn)的需要選定，充分地利用好隨意項(xiàng)，以便把邏輯函數(shù)化簡(jiǎn)到最簡(jiǎn)形式。其填寫(xiě)原則和化簡(jiǎn)原則與不含隨意項(xiàng)的情況相似，首先化簡(jiǎn)小方格中的“1”項(xiàng)，然后化簡(jiǎn)含降維變量的項(xiàng)。這里僅舉一例，不再贅述。例5：用一階降維卡諾圖法化簡(jiǎn)具有隨意項(xiàng)的：用一階降維卡諾圖法化簡(jiǎn)具有隨意項(xiàng)的邏輯函數(shù)邏輯函數(shù)F（A、B、C、D）=∑m（0，1，5，7，8，1111，1414）∑d（3，4，9，1515）解：選取解：選取A為降維變量，為降維變量，B、C、D為卡諾變?yōu)榭?/p>