耿 強(qiáng) 黃雪琴

（1.?？诮?jīng)濟(jì)學(xué)院信息工程學(xué)院 海南 海口 570203；2.海南經(jīng)貿(mào)職業(yè)技術(shù)學(xué)院信息系 海南 ?？?571127）

0 引言

在實(shí)際的電路設(shè)計(jì)中,往往要根據(jù)邏輯函數(shù)要求，歸納出表達(dá)式及畫出相應(yīng)的邏輯電路。但直接得出的表達(dá)式往往不是最簡形式,這樣會(huì)使電路復(fù)雜,所需電子元器件也隨之增加。因此需對(duì)邏輯代數(shù)進(jìn)行必要的化簡,使每個(gè)邏輯單元相對(duì)簡單化、合理化。

通常,人們采用代數(shù)法和卡諾圖法化簡。用代數(shù)法化簡需熟練掌握邏輯代數(shù)的基本定律,而且需要一些化簡技巧,特別是每次經(jīng)代數(shù)法化簡后，得到的表達(dá)式是否為最簡式較難掌握?？ㄖZ圖法雖然可以解決上述問題,但卡諾圈易圈漏、圈錯(cuò)或產(chǎn)生邏輯覆蓋。為消除這種人為引起的錯(cuò)誤,本文提出基于卡諾圖原理用計(jì)算機(jī)編程實(shí)現(xiàn)邏輯代數(shù)化簡的方法。而本文著重分析的是其中“化簡邏輯代數(shù)”的部分。它對(duì)于整個(gè)化簡過程有著承上啟下的作用。

1 卡諾圖化簡的基本原理

筆者按照列表法的化簡思路來進(jìn)行分析，而列表法化簡源于卡諾圖法化簡，因而在此介紹一下卡諾圖化簡的原理。

卡諾圖是邏輯函數(shù)的一種圖形表示。一個(gè)邏輯函數(shù)的卡諾圖就是將此函數(shù)的最小項(xiàng)表達(dá)式中的各最小項(xiàng)相應(yīng)地填入一個(gè)方格圖內(nèi)，此方格圖稱為卡諾圖?？ㄖZ圖的構(gòu)造特點(diǎn)使卡諾圖具有一個(gè)重要性質(zhì)：可以從圖形上直觀地找出相鄰最小項(xiàng)。兩個(gè)相鄰最小項(xiàng)可以合并為一個(gè)與項(xiàng)并消去一個(gè)變量。

例如：給定一組待化簡的邏輯函數(shù)F(A,B,C,D)=∑m(0,3,5,6,7,10,11,13,15)，其卡諾圖化簡過程為：

如圖1（1）中所描述的是函數(shù)F中所對(duì)應(yīng)的數(shù)值,其間標(biāo)有“1方格”的項(xiàng)就是函數(shù)中各個(gè)數(shù)值在卡諾圈中的描述；而圖1（2）中有五個(gè)卡諾圈,所描述的就是全部質(zhì)蘊(yùn)涵項(xiàng)；在圖1（3）中標(biāo)有帶有“*”號(hào)的最小項(xiàng)為必要最小項(xiàng)，它們分別是最小項(xiàng) m0，m3，m5，m6，m10，m13。由此可見,卡諾圖上圈出的五個(gè)質(zhì)蘊(yùn)涵項(xiàng)均為必要質(zhì)蘊(yùn)涵項(xiàng)。最后的結(jié)果即為：F(A,B,C,D)=ABCD+ABC+ABC+BD+CD

圖1 函數(shù)F(A,B,C,D)的卡諾圖化簡流程圖

由此可知卡諾圖化簡邏輯函數(shù)的一般步驟為：首先做出函數(shù)的卡諾圖，然后在卡諾圖上圈出函數(shù)的全部質(zhì)蘊(yùn)涵項(xiàng)，接著從全部質(zhì)蘊(yùn)涵項(xiàng)中找出所有必要質(zhì)蘊(yùn)涵項(xiàng)，最后若函數(shù)的所有必要質(zhì)蘊(yùn)涵項(xiàng)尚不能覆蓋卡諾圖上的所有“1方格”，則從剩余質(zhì)蘊(yùn)涵項(xiàng)中找出最簡的所需質(zhì)蘊(yùn)涵項(xiàng)，使它和必要質(zhì)蘊(yùn)涵項(xiàng)一起構(gòu)成函數(shù)的最小覆蓋，即最簡的質(zhì)蘊(yùn)涵項(xiàng)集。

2 系統(tǒng)運(yùn)行(化簡邏輯代數(shù)部分)流程圖

圖2 化簡流程圖

3 計(jì)算機(jī)實(shí)現(xiàn)邏輯代數(shù)化簡的主要流程

3.1 十進(jìn)制表示的最小項(xiàng)轉(zhuǎn)換為二進(jìn)制表示的最小項(xiàng)程序設(shè)計(jì)

在化簡前將給定的邏輯代數(shù)表達(dá)式（一般為十進(jìn)制數(shù)）轉(zhuǎn)換為二進(jìn)制數(shù)。用數(shù)組num[i]來接受輸入的一組十進(jìn)制數(shù),然后由trans()函數(shù)實(shí)現(xiàn)十進(jìn)制到二進(jìn)制的轉(zhuǎn)換，最后輸出。

算法1：十進(jìn)制轉(zhuǎn)換為二進(jìn)制算法

3.2 全部質(zhì)蘊(yùn)涵項(xiàng)程序設(shè)計(jì)

算法思想：逐個(gè)檢查標(biāo)1方格的合并方向,先圈沒有或只有一個(gè)合并方向的標(biāo)1小方格,后圈可能合并方向較少的標(biāo)1小方格,最后圈那些可能合并方向較多的標(biāo)1小方格,這樣所得的卡諾圈都是質(zhì)蘊(yùn)涵項(xiàng)。即畫卡諾圈時(shí)，先畫大圈，再畫小圈，而且大圈中不再有小圈。

在算法2中,Remainder[]存放待處理元素集,Rlength存放待處理元素集長度,Combination[]存放合并結(jié)果集,Clength存放合并集長度,notsingle標(biāo)志有無相鄰項(xiàng)。

算法2：化簡算法

3.3 求必要質(zhì)蘊(yùn)涵項(xiàng)

將每個(gè)素蘊(yùn)涵項(xiàng)中所包含的最小項(xiàng)求出。若某個(gè)素蘊(yùn)涵項(xiàng)所包含的最小項(xiàng)至少有一個(gè)未被其它素蘊(yùn)涵項(xiàng)包括,那么它就是實(shí)質(zhì)素蘊(yùn)涵項(xiàng)；若實(shí)質(zhì)素蘊(yùn)涵項(xiàng)集包含了所有標(biāo)1小方格,那么它就為所求的最小覆蓋,否則就需求最小覆蓋。

3.4 求最小覆蓋

最小覆蓋就是要覆蓋全部最小項(xiàng)，又要使質(zhì)蘊(yùn)涵項(xiàng)數(shù)目達(dá)到最少。這樣必要質(zhì)蘊(yùn)涵項(xiàng)就是必須選用的質(zhì)蘊(yùn)涵項(xiàng)。最終化簡的結(jié)果通常為最簡與或表達(dá)式。

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

4 實(shí)現(xiàn)計(jì)算機(jī)邏輯代數(shù)化簡的實(shí)現(xiàn)重點(diǎn)

在用C++的描述中，多次涉及到數(shù)組，函數(shù)調(diào)用以及For循環(huán)的使用,因而必須有清晰的思路，才能得以程序的實(shí)現(xiàn)。要清晰的知道二進(jìn)制數(shù)在轉(zhuǎn)換過程中各個(gè)位的存儲(chǔ)原理，以及多次循環(huán)賦值的描述，空間的申請(qǐng)與釋放等。

邏輯代數(shù)化簡過程中的實(shí)現(xiàn)：求“全部質(zhì)蘊(yùn)涵項(xiàng)程序的實(shí)現(xiàn)”是一難點(diǎn).根據(jù)列表法的化簡思想，必須將一組二進(jìn)制數(shù)多次分組，多次循環(huán)對(duì)比，然后在對(duì)比的基礎(chǔ)上找出這一組二進(jìn)制數(shù)中有且僅有一位相異的，然后再進(jìn)行相消合并處理。

5 結(jié)束語

利用計(jì)算機(jī)軟件化簡邏輯代數(shù)克服了代數(shù)法和卡諾圖法以及列表法化簡的不足,可適于多個(gè)變量的邏輯代數(shù)化簡,而且對(duì)于化簡結(jié)果不單一的邏輯表達(dá)式,可輸出所有的化簡結(jié)果。使用該方法化簡邏輯代數(shù)結(jié)果準(zhǔn)確、高效。

［1］王玉龍.數(shù)字邏輯[M].北京:高等教育出版社,1987.

［2］毛法堯.數(shù)字邏輯[M].武漢:華中科技大學(xué)出版社,1996.

［3］郭京蕾.軟件法化簡邏輯代數(shù)[J].武漢理工大學(xué)學(xué)報(bào):信息與管理工程版,2003(03).