邏輯代數化簡的計算機實現

耿 強 黃雪琴

（1.海口經濟學院信息工程學院 海南 ?？?570203；2.海南經貿職業技術學院信息系 海南 ?？?571127）

0 引言

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

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

1 卡諾圖化簡的基本原理

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

卡諾圖是邏輯函數的一種圖形表示。一個邏輯函數的卡諾圖就是將此函數的最小項表達式中的各最小項相應地填入一個方格圖內，此方格圖稱為卡諾圖。卡諾圖的構造特點使卡諾圖具有一個重要性質：可以從圖形上直觀地找出相鄰最小項。兩個相鄰最小項可以合并為一個與項并消去一個變量。

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

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

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

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

2 系統運行(化簡邏輯代數部分)流程圖

圖2 化簡流程圖

3 計算機實現邏輯代數化簡的主要流程

3.1 十進制表示的最小項轉換為二進制表示的最小項程序設計

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

算法1：十進制轉換為二進制算法

3.2 全部質蘊涵項程序設計

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

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

算法2：化簡算法

3.3 求必要質蘊涵項

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

3.4 求最小覆蓋

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

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

4 實現計算機邏輯代數化簡的實現重點

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

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

5 結束語

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

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

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

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