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

1、  用卡諾圖化簡邏輯函數(shù)的研究     摘 要   給出了用卡諾圖法化簡邏輯函數(shù)的可行原則，并用具體事例詮釋了該原則。    關(guān)鍵詞可行原則卡諾圖化簡邏輯函數(shù)  key wordsdoable principlekarnaugh chartreducelogistic function熟知，數(shù)字 電子 技術(shù)的功能是通過邏輯函數(shù)來實(shí)現(xiàn)的，而邏輯函數(shù)一般是基本邏輯或、與、非的復(fù)合表達(dá)，實(shí)現(xiàn)某種復(fù)合邏輯

2、的最簡數(shù)學(xué)表達(dá)意味著對(duì)應(yīng)的技術(shù)成本較低；所以化簡邏輯函數(shù)既具有 理論 價(jià)值，也具有現(xiàn)實(shí)意義?；嗊壿嫼瘮?shù)的 方法 大體有兩類：一是公式化簡法，二是卡諾圖化簡法。迄今，用卡諾圖化簡邏輯函數(shù)的 研究 尚不完善，本文專論用卡諾圖化簡邏輯函數(shù)的可行原則。一、 問題 的提出閻石教授在面向二十一世紀(jì)課程教材數(shù)字電子技術(shù)基礎(chǔ)中給出了一個(gè)事例1：用卡諾圖化簡法化簡以下邏輯函數(shù)y=ac+ac+bc+bc（1）由于y=ac+ac+bc+bc=a（b+b）c+a（b+b）c+（a+a）bc+（a+a）bc=abc+abc+abc+abc+abc+abc+abc+abc=abc+abc+abc+abc+abc+abc

3、所以，閻石教授畫出了表示邏輯函數(shù)y的如下卡諾圖然后，閻石教授對(duì)卡諾圖中為1的相鄰元素進(jìn)行不同方案的合并，分別得到y(tǒng)=ab+ac+bc（2）y=ac+bc+ab（3）據(jù)此，閻石教授認(rèn)為，“有時(shí)一個(gè)邏輯函數(shù)的化簡結(jié)果不是唯一的”。遺憾的是，閻石教授沒有追問，這是為什么？其實(shí)，一個(gè)邏輯函數(shù)利用卡諾圖化簡的結(jié)果不唯一，只表明函數(shù)的化簡還可繼續(xù)！為論證我們的推斷，且從基本概念開始討論。二、基本概念1、n個(gè)邏輯變量組成的最小項(xiàng)。n個(gè)邏輯變量組成的最小項(xiàng)可以定義如下：由n個(gè)邏輯變量或其非組成的n個(gè)不同元素的連續(xù)與叫這些自變量的最小項(xiàng)。例如：abcd，abcd等等。這個(gè)定義較之以往的陳述2更簡潔、也更準(zhǔn)確。2

4、、n個(gè)邏輯變量組成的最大項(xiàng)。n個(gè)自變量組成的最大項(xiàng)可以定義如下：由n個(gè)自變量或其非組成的n個(gè)不同元素的連續(xù)或叫這些自變量的最大項(xiàng)。例如：a+b+c+d，a+b+c+d等等。這個(gè)定義也較以往的陳述2更簡潔、更準(zhǔn)確。3、邏輯相鄰性。由n個(gè)自變量組成的兩個(gè)最小項(xiàng)（或最大項(xiàng)），只有一個(gè)因子不同（即互反），這兩個(gè)最小項(xiàng)（或最大項(xiàng)）就具有邏輯相鄰性。例如：兩個(gè)最小項(xiàng)abcd與abcd具有邏輯相鄰性；兩個(gè)最大項(xiàng)a+b+c+d，a+b+c+d也具有邏輯相鄰性。=a+b+c+d4、卡諾圖。在邏輯代數(shù)中，由于任何一個(gè)邏輯函數(shù)總可以表成最小項(xiàng)的連續(xù)或，也總可以表成最大項(xiàng)的連續(xù)與；所以卡諾圖應(yīng)當(dāng)有兩種：一是關(guān)于最小項(xiàng)

5、的卡諾圖，二是關(guān)于最大項(xiàng)的卡諾圖。不過，一個(gè)邏輯函數(shù)之最小項(xiàng)的表達(dá)形式恰好是這個(gè)邏輯函數(shù)組成元素之非的最大項(xiàng)的非；例如：abcd=a+b+c+d，abcd=a+b+c+d。據(jù)此可知，一個(gè)邏輯函數(shù)之最小項(xiàng)的卡諾圖與這個(gè)邏輯函數(shù)之最大項(xiàng)的卡諾圖是同一表達(dá)的兩種形式。鑒于n個(gè)邏輯變量組成的最小項(xiàng)書寫起來比這n個(gè)邏輯變量組成的最大項(xiàng)簡潔，因而，通常只討論最小項(xiàng)的卡諾圖。最小項(xiàng)的卡諾圖就是把所有具有邏輯相鄰性的n個(gè)邏輯變量組成的最小項(xiàng)相鄰地排布起來，當(dāng)n為偶數(shù)時(shí)，排成2n 2×2n 2方陣；當(dāng)n為奇數(shù)時(shí)，排成2n-1 2×2n+1 2陣列；這類

6、陣列就是n個(gè)自變量組成的最小項(xiàng)卡諾圖。三、用卡諾圖化簡邏輯函數(shù)的可行原則用卡諾圖化簡邏輯函數(shù)，先得將一個(gè)邏輯函數(shù)化為最小項(xiàng)的連續(xù)或（抑或最大項(xiàng)的連續(xù)與）的表達(dá)形式，并據(jù)此表達(dá)在對(duì)應(yīng)卡諾圖中存在某最小項(xiàng)（抑或最大項(xiàng)）的位置記1，不存在該最小項(xiàng)（抑或最大項(xiàng)）的位置記0，排布出2n 2×2n 2抑或2n-1 2×2n+1 2卡諾圖陳列。然后，依據(jù)卡諾圖，按以下基本原則化簡邏輯函數(shù)：1、為簡便起見，卡諾圖中為1的元素少于為0的元素，宜將諸為1的元素合并化簡邏輯函數(shù)，給出邏輯函數(shù)的表達(dá)式y(tǒng)；反之，若卡諾圖中為1的元素多于為0的元素，宜將諸為0的

7、元素合并化簡邏輯函數(shù)，給出邏輯函數(shù)的非的表達(dá)式y(tǒng)tx-；容易證明兩種化簡邏輯函數(shù)的途徑對(duì)于同一卡諾圖是等價(jià)的。2、卡諾圖中有2n個(gè)為1（抑或0）的元素在一行（抑或一列）內(nèi)連續(xù)相鄰，抑或2n個(gè)為1（抑或0）的元素構(gòu)成一個(gè)連續(xù)相鄰的矩形陣列，則可化簡消去n對(duì)元素。3、若一個(gè)邏輯函數(shù)對(duì)應(yīng)的卡諾圖中，任何為1（抑或?yàn)?）的最小項(xiàng)（抑或最大項(xiàng)）均無邏輯相鄰性的同為1（抑或?yàn)?）的項(xiàng)，則此邏輯函數(shù)不能再用卡諾圖化簡。下面用具體事例展示用卡諾圖化簡邏輯函數(shù)的上述原則。仍用閻石教授給出的上例1：實(shí)際上，閻石教授對(duì)邏輯函數(shù)y=ac+ac+bc+bc的化簡沒有遵從我們上面給出的原則，從而導(dǎo)致了邏輯函數(shù)化簡過程的復(fù)

8、雜化。顯然，上面列出的邏輯函數(shù)y=ac+ac+bc+bc對(duì)應(yīng)的卡諾圖中，有六個(gè)1、兩個(gè)0，所以據(jù)基本原則1、3兩條，“宜將諸為0的元素合并化簡邏輯函數(shù)”，給出y=abc+abc（4）而不應(yīng)當(dāng)像閻石教授那樣，采用不同方案“將諸為1的元素合并化簡邏輯函數(shù)”，分別得出（2）式和（3）式。事實(shí)上，由（2）式進(jìn)一步化簡，有y=ab+ac+bc=abacbc=(a+b)(a+c)(b+c)=a b c+abc（5）同樣地，由（3）式進(jìn)一步化簡，有y=ac+bc+ab=acbcab=(a+c)(b+c)(a+b)=a b c+abc（6）（5）式和（6）式表明，（2）式和（3）式其實(shí)是唯一結(jié)果（4）式的不同中間表達(dá)，閻石教授關(guān)于“有時(shí)一個(gè)邏輯函數(shù)的化簡結(jié)果不是唯一的”