邏輯代數(shù)化簡的計算機實現(xiàn)

耿 強 黃雪琴

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

0 引言

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

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

1 卡諾圖化簡的基本原理

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

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

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

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

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

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

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

圖2 化簡流程圖

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

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

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

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

3.2 全部質(zhì)蘊涵項程序設(shè)計

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

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

算法2：化簡算法

3.3 求必要質(zhì)蘊涵項

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

3.4 求最小覆蓋

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

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

4 實現(xiàn)計算機邏輯代數(shù)化簡的實現(xiàn)重點

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

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

5 結(jié)束語

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

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

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

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