王波 徐州師范大學計算機科學與技術(shù)學院 221116

基于蘊涵法的求解多變量邏輯函數(shù)本原蘊涵項的程序流程

王波 徐州師范大學計算機科學與技術(shù)學院 221116

基于邏輯函數(shù)蘊涵化簡法的基本理論，構(gòu)造比較合并數(shù)組，設(shè)計求解多變量邏輯函數(shù)本原蘊涵項的結(jié)構(gòu)化程序流程，使邏輯函數(shù)的化簡工作在降低了復(fù)雜度的同時提高了可靠性。

蘊涵化簡法；本原蘊涵項；邏輯相鄰項；結(jié)構(gòu)化流程

引言

通過化簡實現(xiàn)邏輯函數(shù)的最小化是數(shù)字邏輯系統(tǒng)設(shè)計過程中非常重要的一個步驟，但諸如公式法、卡諾圖法等常用的化簡方法僅適用于簡單的邏輯函數(shù)，對于復(fù)雜的多變量（5變量以上）邏輯函數(shù)的化簡則可使用蘊涵化簡法。

蘊涵法又叫制表法，是由奎恩（Quine）提出，并經(jīng)由麥克拉斯基（McCluskey）改進和完善的一種邏輯函數(shù)系統(tǒng)化簡法，故又稱為Q－M化簡法。雖然與卡諾圖法一樣也是以公式為基本理論依據(jù)，但蘊涵法又有著化簡步驟規(guī)律性強的優(yōu)點，應(yīng)用于多變量邏輯函數(shù)的化簡，雖然工作量大，但操作可以按部就班地進行，適合于計算機處理[1]。

上述特點，在蘊涵法化簡邏輯函數(shù)的第一個步驟即求本原蘊涵項的過程中表現(xiàn)得尤為突出。所謂本原蘊涵項就是不含多余變量的乘積項，即其已不能再通過同其它乘積項合并而減少變量了[2]。本文以5變量邏輯函數(shù)為例，應(yīng)用蘊涵法進行計算機輔助設(shè)計，給出求解多變量邏輯函數(shù)本原蘊涵項的結(jié)構(gòu)化程序流程。

1.程序流程

1.1 初始化

初始化操作除了定義程序運行所需的多個相關(guān)變量外，最主要的工作就是定義如下兩個數(shù)組。

1.1.1 二維數(shù)組m[3][212]

m數(shù)組的每個數(shù)組元素為一個字節(jié)，同一列的三個數(shù)組元素構(gòu)成一個數(shù)據(jù)單元，數(shù)組元素的列號即為數(shù)據(jù)單元的序號，如圖1所示，數(shù)據(jù)單元是存儲邏輯函數(shù)標準與或式中包含的最小項或操作過程中產(chǎn)生的一般乘積項的基本單位。

數(shù)據(jù)單元中標記“×”的位沒有定義（用“0”填充），其余位根據(jù)不同的存儲對象有著不同的定義和使用方法。

（1）存儲最小項

按照使最小項、數(shù)據(jù)單元的序號對應(yīng)相等的方法，將邏輯函數(shù)包含的最小項mi存儲于m數(shù)組的第i（=0～31）個數(shù)據(jù)單元并由輸入程序作相應(yīng)設(shè)置。

1）m[2][i].7位為“1”，表示邏輯函數(shù)包含最小項mi，此時，數(shù)據(jù)單元的其它各位定義如下。

①m[2][i].6位為“0”，表示mi尚未被消去任何變量，一旦mi參與化簡，此位將被置“1”；

②m[0][i].4～m[0][i].0位組存儲mi的序號i對應(yīng)的5位二進制數(shù)，其中“1”對應(yīng)mi中的原變量，而“0”對應(yīng)反變量；

③m[1][i].4～m[1][i].0位組存儲5個連續(xù)的二進制“1”表示mi包含所有邏輯變量；

④m[2][i].2～m[2][i].0位組用于存儲3位二進制值，表示位組m[0][i].4～m[0][i]. 0中“1”的個數(shù)，即mi中原變量的個數(shù)。

圖1（a）為一個特例，描述最小項m2尚未參與化簡合并時的存儲狀態(tài)。

2）m[2][i].7位為“0”表示邏輯函數(shù)不包含最小項mi，此數(shù)據(jù)單元的其它位皆不被定義使用。

（2）存儲一般乘積項

在求解本原蘊涵項過程中，一般會產(chǎn)生被消去若干個變量的一般乘積項，它們將被依次存儲于m數(shù)組中序號大于或等于32的數(shù)據(jù)單元中,除以下兩點外，各數(shù)據(jù)位取“0”、“1”狀態(tài)的含義與存儲最小項時基本相同。

1）一個一般乘積項在m數(shù)組中的具體存儲位置由被處理的邏輯函數(shù)的結(jié)構(gòu)決定；

2）m[1][i].4～m[1][i].0位組中的某位為“0”，表明其對應(yīng)的變量已被從乘積項中消去，其在m[0][i].4～m[0][i].0位組中對應(yīng)位的狀態(tài)也失去意義。

圖1（b）為另一個特例，描述了一個一般乘積項的存儲狀態(tài)，此一般乘積項由邏輯函數(shù)F（在后文的實現(xiàn)實例部分中詳細說明）包含的兩個最小項m9、m11合并得到，其所在數(shù)據(jù)單元的序號為36，尚需進一步化簡。

（3）m數(shù)組中數(shù)據(jù)單元數(shù)目的定義問題

對于m數(shù)組，實際所需的數(shù)據(jù)單元的數(shù)目由被處理的邏輯函數(shù)決定，隨邏輯函數(shù)包含的最小項數(shù)目及最小項分布情況不同而變化。在此，對5變量邏輯函數(shù)，設(shè)定數(shù)據(jù)單元的個數(shù)為212，即m數(shù)組的列號范圍為0～211,這是一個存儲單元數(shù)目極端大的選擇，對應(yīng)邏輯函數(shù)的標準與或式中共包含31個最小項的情況。

1.1.2 二維比較合并數(shù)組comp[6][10]

為了比較、合并邏輯相鄰的最小項，根據(jù)蘊涵法理論定義6行10列的二維字節(jié)數(shù)組comp，并依據(jù)表1（最小項比較合并表）的結(jié)構(gòu)和內(nèi)容將comp數(shù)組初始化，comp數(shù)組具有如下特征。

（1）內(nèi)容非“-1”的數(shù)組元素共32個，分別對應(yīng)被處理邏輯函數(shù)可能包含的序號為0～31的32個最小項，而內(nèi)容為“-1”的數(shù)組元素不對應(yīng)最小項。每行的第一個內(nèi)容為“-1”的數(shù)組元素用于控制某一輪尋找、比較與合并最小項的循環(huán)過程的結(jié)束。

（2）同一行數(shù)組元素對應(yīng)的最小項擁有相同個數(shù)的原變量，并且原變量的個數(shù)等于行號。

（3）某行一個數(shù)組元素對應(yīng)的最小項與相鄰上一行另一個數(shù)組元素對應(yīng)的最小項相比較，原變量個數(shù)多1，如果這種關(guān)系是由于邏輯函數(shù)的同一個變量在兩個最小項中分別取原、反變量狀態(tài)引起的，則相應(yīng)的兩個最小項即為一對邏輯相鄰項。

1.2 邏輯函數(shù)輸入

輸入程序依據(jù)前述要求設(shè)置m數(shù)組的相關(guān)數(shù)組元素。特別地，對于邏輯函數(shù)包含所有最小項（邏輯函數(shù)值恒為1）和邏輯函數(shù)不包含任何最小項（邏輯函數(shù)值恒為0）兩種情況要在輸入流程中直接進行處理說明，而不必進入后續(xù)的求解本原蘊涵項流程。

1.3 求解本原蘊涵項流程

求解本原蘊涵項操作的程序流程結(jié)構(gòu)為一個整體，為描述方便，將其分為主體和子模塊兩個部分。

1.3.1 主體部分

圖2以N-S圖的形式給出主體部分的結(jié)構(gòu)化流程。

這一部分的核心流程是一個嚴格遵循蘊涵法基本步驟設(shè)計的，分別以i1、j1和k1為外、中和內(nèi)層循環(huán)控制變量的三重嵌套循環(huán)結(jié)構(gòu)。借助于comp數(shù)組為主要的控制依托，通過此循環(huán)結(jié)構(gòu)正常運行，可實現(xiàn)主體部分的基本功能，即進行邏輯相鄰最小項的尋找、比較與合并操作，得到因消去一個變量而擁有4個變量的所有一般乘積項，并依次存儲于m數(shù)組中相應(yīng)位置的數(shù)據(jù)單元中。

當?shù)玫降?變量一般乘積項的個數(shù)大于或等于2時，求解本原蘊涵項的操作過程就需要繼續(xù)進行，流程進而由此部分結(jié)束處的二重嵌套選擇結(jié)構(gòu)的最左端分支進入子模塊部分，否則，本原蘊涵項已經(jīng)求出，整個流程結(jié)束。

1.3.2 子模塊部分

圖3以N-S圖的形式給出子模塊部分的結(jié)構(gòu)化流程。

子模塊部分實現(xiàn)的功能是：針對主體部分求得的兩個或兩個以上的4變量一般乘積項，繼續(xù)進行邏輯相鄰的一般乘積項的尋找、比較與合并操作。

這一部分程序流程整體上為一個四重嵌套的循環(huán)結(jié)構(gòu)。以r為循環(huán)控制變量的外層循環(huán)最多可能執(zhí)行3次，先后求得可能存在的由3、2或1個邏輯變量組成的一般乘積項；i2、j2控制中間兩層循環(huán)，實施求解這些一般乘積項的具體操作；而k2控制的最內(nèi)層循環(huán)則用于防止同一個一般乘積項在m數(shù)組中的重復(fù)存儲。

1.4 本原蘊涵項的輸出

上述相關(guān)流程執(zhí)行完畢后，化簡得到的所有本原蘊涵項都被存儲在m數(shù)組中，假設(shè)某個本原蘊涵項所在數(shù)據(jù)單元的序號為i，則有：

（1）i的范圍為0～PointEnd；

（2）m[2][i].7～m[2][i].6位組的內(nèi)容為“10”（此為本原蘊涵項的標志）；

（3）m[1][i].4～m[1][i].0位組中內(nèi)容為“1”的位對應(yīng)的變量被保留在本原蘊涵項中；

（4）本原蘊涵項中一個被保留變量的原、反狀態(tài)由m[0][i].4～m[0][i].0位組中此變量對應(yīng)位的取值確定，“1”對應(yīng)原變量，“0”對應(yīng)反變量。

根據(jù)上述特征，可設(shè)計相應(yīng)的程序流程對所有本原蘊涵項進行依次輸出。

2.實現(xiàn)實例

用蘊涵法化簡邏輯函數(shù)F（A、B、C、D、E）=∑m（0,2,4,6,9,11,13,15,17, 21,25,27,29,31），求全部本原蘊涵項[3]。用C語言實現(xiàn)上述流程，程序運行的結(jié)果是在m數(shù)組中得到3個存儲著本原蘊涵項的數(shù)據(jù)單元，它們是：

①m[0][51]=00000000、m[1][51]=00011001、m[2][51]=1000000；

②m[0][55]=00010001、m[1][55]=00010011、m[2][55]=1000010；

③m[0][59]=00001001、m[1][59]=00001001、m[2][59]=1000010。

3.結(jié)束語

本文介紹的求解多變量邏輯函數(shù)本原蘊涵項的方法嚴格遵循蘊涵法理論，設(shè)計的程序流程清晰、準確，符合結(jié)構(gòu)化標準，用C、VB等高級編程工具很容易實現(xiàn)。對于6變量以上的邏輯函數(shù)，也僅僅需要對m數(shù)組的列數(shù)、comp數(shù)組的結(jié)構(gòu)和內(nèi)容及部分循環(huán)結(jié)構(gòu)的循環(huán)次數(shù)進行簡單的修改即可。實踐表明，通過上述流程對邏輯函數(shù)進行處理的結(jié)果，與用公式法、卡諾圖法等手工方法進行處理的結(jié)果完全一致，但在提高可靠性、減小復(fù)雜度和降低工作成本等方面優(yōu)點是明顯的。

[1]朱勇，高曉清，曾西洋．數(shù)字邏輯第一版．北京：中國鐵道出版社．2007；49

[2，3]韓振振，李亞伯．數(shù)字電路邏輯設(shè)計[M]．第一版．大連：大連理工大學出版社．1987；105－116

10.3969/j.issn.1001-8972.2010.24.014

王波，男，漢族，現(xiàn)任教于徐州師范大學計算機科學與技術(shù)學院，主要研究方向：數(shù)字系統(tǒng)設(shè)計，單片機及嵌入式系統(tǒng)。