相容關(guān)系模型及其在邏輯優(yōu)化中的應(yīng)用*

王好為，閆繼雄，柴 晶，陳澤華

太原理工大學(xué) 信息工程學(xué)院，太原 030024

1 引言

邏輯表達(dá)式化簡技術(shù)[1]是數(shù)字電路中的一個(gè)重要內(nèi)容，其作用是能在保證原電路功能不變的情況下，減少輸入電路中門電路的個(gè)數(shù)，使得電路更簡潔、更安全。

傳統(tǒng)的邏輯表達(dá)式化簡方法有公式法[2]、卡諾圖法[2]、Q-M算法[3]和立方體法[4]等。其中公式法不僅需要熟練使用邏輯代數(shù)的相關(guān)知識(shí)，而且不易編程；卡諾圖法是一種直觀的邏輯表達(dá)式化簡方法，但是當(dāng)輸入變量個(gè)數(shù)超過6時(shí)，難以表達(dá)；Q-M算法是基于卡諾圖法的一種改進(jìn)算法，但是算法復(fù)雜度依舊很高；立方體法具有較低的時(shí)間復(fù)雜度，但是對(duì)于多變量表達(dá)式，其計(jì)算過程不易理解。

近年來，有很多學(xué)者在邏輯表達(dá)式化簡方面進(jìn)行了研究，并取得了較大的進(jìn)展。他們對(duì)傳統(tǒng)方法進(jìn)行了改進(jìn)，包含對(duì)卡諾圖法的改進(jìn)算法[5-6]和對(duì)Q-M算法的改進(jìn)算法[7-8]。Gómez等人[9]依據(jù)邏輯表達(dá)式的拓?fù)浜徒y(tǒng)計(jì)特性提取了其中的質(zhì)蘊(yùn)涵項(xiàng)，將表達(dá)式的化簡過程轉(zhuǎn)化為最小項(xiàng)的化簡過程，從而降低了計(jì)算的復(fù)雜性；Chowdhury等人[10]基于MZI（Mach-Zehnder interferometer）的模式匹配方案將邏輯表達(dá)式轉(zhuǎn)化為邏輯電路，根據(jù)去除電路的輔助線達(dá)到約簡的目的，但該方法依賴于硬件電路的實(shí)驗(yàn)結(jié)果，并且實(shí)驗(yàn)成本較高，不具有實(shí)用性；陳澤華等人[11]基于粗糙集的等價(jià)關(guān)系模型實(shí)現(xiàn)了普通真值表的快速并行約簡，但是該方法處理邏輯表達(dá)式時(shí)需要將其展開為最小項(xiàng)，并轉(zhuǎn)化為完整輸入狀態(tài)的真值表，轉(zhuǎn)化過程較為繁瑣，也會(huì)增加額外的空間復(fù)雜度。

粒計(jì)算是一種處理具有不確定性的大量復(fù)雜信息的方法論，它通過把復(fù)雜問題抽象、劃分，從而轉(zhuǎn)化為若干較為簡單的問題，有助于更好地分析和解決問題。根據(jù)數(shù)字電路相關(guān)知識(shí)，邏輯表達(dá)式的與或式均可以轉(zhuǎn)化為特殊的不完備決策表。近年來，眾多學(xué)者基于粒計(jì)算對(duì)不完備決策表的研究取得了較大的進(jìn)展。邵明文等人[12]基于粗糙集理論重新定義了上下近似的概念，然后計(jì)算不完備決策表的分辨矩陣，提取決策表中的有效規(guī)則；楊習(xí)貝[13]和吳偉志[14]等人針對(duì)多尺度信息系統(tǒng)提出了各自的規(guī)則提取算法，為粗糙集帶來新的生機(jī)[13]；官禮和等人[15]基于粒計(jì)算的屬性重要度理論，對(duì)決策表的屬性進(jìn)行排序，依次加入屬性值，從而提取得到規(guī)則，該算法在由粗到細(xì)的粒度空間下進(jìn)行分析，降低了算法的時(shí)間復(fù)雜度，但是得到的規(guī)則集不能保證為最簡。

本文基于相容關(guān)系，針對(duì)數(shù)字電路中任意的邏輯表達(dá)式，提出了一種快速的邏輯表達(dá)式化簡算法。該算法首先將任意的邏輯表達(dá)式轉(zhuǎn)化為與或式，并表示為本文定義的不完備真值表；然后在多粒度空間下，分別計(jì)算相容邏輯信息系統(tǒng)中每個(gè)屬性集合的相容矩陣和邏輯關(guān)系矩陣，根據(jù)邏輯關(guān)系矩陣的性質(zhì)判斷該屬性集是否可以得到新的規(guī)則；最后將提取的規(guī)則轉(zhuǎn)化成表達(dá)式，該表達(dá)式即為最簡邏輯表達(dá)式。本文通過設(shè)定算法終止條件從而加快算法收斂，并通過定理證明和實(shí)例分析驗(yàn)證了本文算法的正確性。

2 預(yù)備知識(shí)

2.1 邏輯表達(dá)式化簡相關(guān)概念

數(shù)字電路是用數(shù)字信號(hào)完成對(duì)數(shù)字量進(jìn)行邏輯運(yùn)算的電路，其處理的信號(hào)均為數(shù)字量的信號(hào)，且均可以用0和1組成的二進(jìn)制數(shù)來表示信號(hào)的大小。下面介紹本文用到的一些數(shù)字電路的基本知識(shí)。

定義1[1]（邏輯表達(dá)式、與或表達(dá)式、最小項(xiàng)、最簡與或表達(dá)式）邏輯表達(dá)式是用邏輯運(yùn)算符將關(guān)系表達(dá)式或邏輯量連接起來的有意義的式子；與或表達(dá)式是將邏輯表達(dá)式轉(zhuǎn)化為若干個(gè)只含與、非運(yùn)算的單項(xiàng)式，并用或運(yùn)算進(jìn)行連接的式子；最小項(xiàng)是所有輸入變量的乘積，每個(gè)變量都以它的原變量或反變量的形式在乘積中出現(xiàn)且僅出現(xiàn)一次；與或表達(dá)式中的任意一個(gè)單項(xiàng)式均可以轉(zhuǎn)化為若干個(gè)最小項(xiàng)的和；邏輯表達(dá)式化簡就是要消去與或表達(dá)式中冗余的乘積項(xiàng)及每個(gè)乘積項(xiàng)中冗余的變量，以得到邏輯表達(dá)式的最簡與或表達(dá)式。

邏輯表達(dá)式化簡遵循如下邏輯代數(shù)基本定律。

（1）0-1律

（2）結(jié)合律、交換律、分配律

（3）反演律（摩根定理）

本文通過例1說明上述幾種表達(dá)式的表現(xiàn)形式，并根據(jù)計(jì)算實(shí)現(xiàn)表達(dá)式之間的轉(zhuǎn)換。

例1一個(gè)數(shù)字電路的邏輯表達(dá)式為：

將其轉(zhuǎn)化為與或表達(dá)式為：

對(duì)于四輸入的邏輯電路，單項(xiàng)式A可轉(zhuǎn)化為8個(gè)最小項(xiàng)之和：

將與或表達(dá)式轉(zhuǎn)化為最簡與或表達(dá)式為（卡諾圖法[2]）：

2.2 不完備決策表與不完備真值表

決策表是粗糙集中重要研究內(nèi)容，其定義如下。

定義2[12]（決策表）決策表可以用一個(gè)四元組DT=(U,A,V,f)來表示。其中U表示對(duì)象的非空有限集合，稱為論域；A=C?D表示屬性集合且C?D=?，C表示條件屬性集，D表示決策屬性集；V=表示屬性a的值域；f:U×A→V表示決策表中的一種映射關(guān)系，它為每個(gè)對(duì)象在每個(gè)屬性上賦予了一個(gè)信息值，即?a∈A,x∈U,f(x,a)∈Va。若存在a∈A,x∈U使得f(x,a)未知（記作f(x,a)=*），則稱決策表是不完備的，否則稱決策表是完備的。

相容關(guān)系是處理不完備決策表的重要理論工具，Kryszkiewicz最初對(duì)其進(jìn)行了數(shù)學(xué)定義。

定義3[12]（不完備決策表）設(shè)DT=(U,A,V,f)為一個(gè)不完備決策表，對(duì)于任意的屬性集合P?A，定義U上的一種相容關(guān)系SIM(P)為：

對(duì)于任意的對(duì)象x∈U，定義集合SP(x)={y|(x,y)∈SIM(P)}，表示論域中x的相容類的集合；基于此相容類集合再定義集合U/SIM(P)={SP(x)|x∈U}={X1,X2,…,Xk}表示U關(guān)于P的覆蓋，即滿足且存在Xi,Xj∈U/SIM(P)使得Xi?Xj≠ ? 。

真值表是用來表征邏輯事件輸入和輸出之間全部可能狀態(tài)的表格，表示了電路中的邏輯因果關(guān)系。把組合電路中各輸入變量的所有可能取值與相應(yīng)的輸出值，以表格形式一一列舉出來，這種表格就稱為真值表。

由2.1節(jié)的相關(guān)知識(shí)，若將與或表達(dá)式中的每一項(xiàng)看作一條邏輯規(guī)則，則邏輯表達(dá)式可表示為不完備決策表，其中每一項(xiàng)缺失的屬性可看作不完備決策表中缺失項(xiàng)“*”。與一般不完備決策表不同的是，由與或表達(dá)式轉(zhuǎn)化的決策表中其決策值均為“1”，且條件屬性中的缺失項(xiàng)“*”可且只可取值為“0”或“1”，因此是一種特殊形式的不完備決策表。本文將這種決策表定義為不完備真值表。

定義4（不完備真值表）真值表可以用一個(gè)四元組T=(U,R,V,f)來表示。其中U為論域，表示電路所有可能的狀態(tài)；R=X?Y表示所有輸入輸出邏輯變量，X={X1,X2,…,Xm}表示所有輸入邏輯變量，m為輸入變量的個(gè)數(shù)，Y={Y1,Y2,…,Yn}表示所有輸出邏輯變量，n為輸出變量的個(gè)數(shù)；V表示電路的所有邏輯變量值；f:U×R→V是一個(gè)信息函數(shù)，它指定U中每一個(gè)對(duì)象、R中每一個(gè)邏輯變量所對(duì)應(yīng)的邏輯值。若存在a∈R,x∈U使得f(x,a)未知（記作f(x,a)=*），則稱該真值表為不完備真值表。

一般情況下，若真值表中不含有無關(guān)項(xiàng)，即V∈{0,1}，每一行的所有輸入值便可以組成一個(gè)最小項(xiàng)。但是由與或表達(dá)式轉(zhuǎn)化的不完備真值表中，輸入值中含有無關(guān)項(xiàng)，即V∈{0,1,?}（“*”表示無關(guān)項(xiàng)），此時(shí)真值表中每一行變量值乘積后便不是最小項(xiàng)，而是一般的與或式。

例2沿用例1，將與或表達(dá)式轉(zhuǎn)化為真值表，如表1所示。

Table 1 Incomplete truth table for corresponding logical function表1 邏輯函數(shù)對(duì)應(yīng)的不完備真值表

不完備真值表為T={U,X?Y,V,f}，其中U={1,2,3,4,5,6,7,8},X={A,B,C,D},Y={Y}。

3 邏輯關(guān)系矩陣

以下主要介紹邏輯關(guān)系矩陣的計(jì)算方法，并給出相應(yīng)定理說明邏輯關(guān)系矩陣的意義。

定義5（相容矩陣）在不完備真值表T={U,X?Y,V,f}中，U={u1,u2,…,ul}(l=|U|)，對(duì)于任意的屬性集則定義P的相容矩陣為：

其中，aij的計(jì)算公式如下：

設(shè)(X-P)為屬性空間X下除去P的剩余屬性集合，同樣可求得(X-P)的相容矩陣XX-P。

定義6（邏輯關(guān)系矩陣）在不完備真值表T={U,X?Y,V,f}中，對(duì)于P?X，定義P的邏輯關(guān)系矩陣為：

邏輯關(guān)系矩陣是本文提出的用于判別是否可以提取約簡規(guī)則的判斷依據(jù)，滿足如下定理。

定理1若YP的第i行（1≤i≤k）的值均不為“0”，則相容類Xi必然可以得到一條確定性最簡規(guī)則。

證明由式（4）得YP=XPXTX-P，則YP的第i行、第j列元素的計(jì)算公式為：

若cij≠0 ，說明Xi中的“1”與Xj中的“1”對(duì)應(yīng)相乘，即屬性P的第i種取值與剩余屬性的第j種取值可以合成最小項(xiàng)；若對(duì)所有的1≤j≤q均有cij≠0，則屬性x的第i種取值可以與剩余屬性的任意取值合成最小項(xiàng)，即覆蓋剩余屬性的所有取值情況。根據(jù)邏輯函數(shù)基本定律，屬性P的第i種取值必是一條輸出規(guī)則；由于粒度是從粗變細(xì)，在較粗粒度下沒有辨識(shí)的規(guī)則，在細(xì)粒度下一定會(huì)辨識(shí)出最簡規(guī)則，即輸出的規(guī)則為最簡規(guī)則。

4 基于相容關(guān)系的邏輯表達(dá)式化簡算法

4.1 啟發(fā)式算子

為了使本文算法更加快速地收斂，需計(jì)算出不完備真值表中所含的所有規(guī)則數(shù)，而在算法計(jì)算過程中已經(jīng)被尋到的規(guī)則數(shù)可以作為啟發(fā)式算子加快算法的效率。

定義7（總規(guī)則數(shù)）在不完備真值表T={U,X?Y,V,f}中，記表中的總規(guī)則數(shù)為N，由于有無關(guān)項(xiàng)的存在(?∈{0,1})，且每一行的i個(gè)無關(guān)項(xiàng)有2i種組合，N的計(jì)算公式為：其中，g(j)表示真值表中第j行無關(guān)項(xiàng)“*”的個(gè)數(shù)。

在算法計(jì)算過程中，已尋到的規(guī)則數(shù)n是不斷更新的，并且已尋到的規(guī)則不能重復(fù)被計(jì)算為規(guī)則數(shù)，因此有如下定義。

定義8（最小項(xiàng)集合）已尋到的規(guī)則的輸入項(xiàng)均可以轉(zhuǎn)化為最小項(xiàng)，這些最小項(xiàng)放置在同一集合即為最小項(xiàng)集合。

定義尋到的最小項(xiàng)的集合為NR，用來判斷新找出的規(guī)則中是否已包含已尋到的規(guī)則。

本文為了避免對(duì)規(guī)則冗余性的判斷，利用邏輯關(guān)系矩陣提出如下定理。

定理2在T={U,X?Y,V,f}中，已知邏輯關(guān)系矩陣YP(P?X)的第Row行全不為0元素，且第Col列與第Row行所組合的規(guī)則并未被尋到（Row與Col均為集合），即該規(guī)則的輸入項(xiàng)轉(zhuǎn)化成的最小項(xiàng)不存在于NR中，則屬性集合P尋到的規(guī)則數(shù)為：

其中，yij表示YP中第i行、第j列的元素。

證明假設(shè)在屬性集合P下按二進(jìn)制順序排列得到的邏輯關(guān)系矩陣YP存在全不為“0”的行，找出該行位置記為Row，則其行數(shù)為U關(guān)于P的相容類類別數(shù)，YP中元素的列數(shù)則代表U關(guān)于(X-P)的相容類類別數(shù)，而等價(jià)類是由屬性值得到的，便可得到對(duì)應(yīng)屬性的取值，據(jù)此便可得到找尋到的規(guī)則NR。令新規(guī)則與集合R相減即NR-R（即存在于NR且不存在于R的規(guī)則），得到還未被找到的規(guī)則，該規(guī)則下在YP中對(duì)應(yīng)的列記為Col。

推論已尋到的規(guī)則數(shù)n等于所有屬性集合尋到的規(guī)則數(shù)的總和，即

規(guī)則數(shù)n和原規(guī)則數(shù)N存在如下定理，可加速算法的收斂。

定理3當(dāng)已尋到的規(guī)則數(shù)n和真值表的總規(guī)則數(shù)N滿足條件n=N時(shí)，算法即收斂。

4.2 算法描述

本文基于多粒度的思想，提出了基于相容關(guān)系的邏輯表達(dá)式化簡算法，該算法的計(jì)算步驟如下：

算法1基于相容關(guān)系的邏輯表達(dá)式化簡算法

輸入：任意邏輯表達(dá)式Y(jié)=f(A,B,C,D,…)。

輸出：最簡邏輯表達(dá)式。

1.將一般邏輯表達(dá)式轉(zhuǎn)化為析取范式，并轉(zhuǎn)化為真值表；

2.計(jì)算N，初始化ω=1，n=0，R=?，rl=?；

3.計(jì)算輸入屬性子集P在粒度ω下(即滿足||P=ω)的邏輯關(guān)系矩陣YP；

4.找出YP中全不為0的行，并找出對(duì)應(yīng)規(guī)則，計(jì)算nx，判斷nx是否大于0；

5.若nx＞0，則依次記錄{NR-R}至R，所得規(guī)則記錄至rl，并更新n值；

6.若nx=0，則轉(zhuǎn)至步驟7；

7.判斷是否滿足n=N，若不滿足轉(zhuǎn)至8，否則轉(zhuǎn)至9；

8.判斷ω是否達(dá)到最大值（ω最大為|X|），若沒有達(dá)到，則ω=ω+1，返回步驟3繼續(xù)計(jì)算，否則轉(zhuǎn)至步驟9；

9.將rl中的規(guī)則轉(zhuǎn)化為邏輯表達(dá)式，輸出邏輯規(guī)則。

4.3 復(fù)雜度分析

對(duì)于真值表T={U,X?Y,V,f}，由算法步驟可知，步驟1、2的復(fù)雜度均為O(1)，步驟3中，在第ω次迭代情況下，計(jì)算所有屬性子集的相容矩陣復(fù)雜度為，而計(jì)算所有剩余屬性集的相容矩陣的復(fù)雜度，因此計(jì)算邏輯關(guān)系矩陣的復(fù)雜度為O(2×步驟4～7為規(guī)則提取過程，其復(fù)雜度為O(1)。由算法步驟可知，步驟3～8為迭代過程，每次迭代的算法復(fù)雜度為，其迭代次數(shù)在最壞的情況下為|X|次，因此總復(fù)雜度為實(shí)際上，對(duì)于在第ω次迭代情況下求得的所有邏輯關(guān)系矩陣，實(shí)際為在第|X|-ω次迭代情況下求得的所有邏輯關(guān)系矩陣的轉(zhuǎn)置，不用重復(fù)求取，因此算法1在最壞的情況下，其實(shí)際復(fù)雜度為O(2|X|+1/2)=O(2|X|)。

5 實(shí)驗(yàn)與分析

5.1 實(shí)例說明

例3沿用例2，不完備真值表為T={U,X?Y,V,f}，其中U={1,2,3,4,5,6,7,8},X={A,B,C,D},Y={Y}。

置R,rl={?}，根據(jù)式（5）可知，22+…+20=25，置n=0，ω=1。

在ω=1的粒度下，每種屬性集合即為{{A},{B},{C},{D}}，其屬性空間內(nèi)剩余屬性的集合為{{B,C,D},{A,C,D},{A,B,D},{A,B,C}}，根據(jù)定義3可以計(jì)算得到：

根據(jù)式（3）、式（4），分別計(jì)算每個(gè)屬性集合P的相容矩陣，可得：

同理，屬性集合(X-P)的相容矩陣也皆可求得：

再根據(jù)式（4），計(jì)算各屬性集合的邏輯關(guān)系矩陣，得：

接下來需要判斷邏輯關(guān)系矩陣中是否存在全不為“0”的行。由以上計(jì)算結(jié)果可知YA的第二行全不為“0”，從而得知U/SIM(A)的第二個(gè)相容類可以得到新規(guī)則，即NR={m8,m9,m10,m11,m12,m13,m14,m15}。新規(guī)則在YA的位置為：

根據(jù)式（8）可計(jì)算得到：

由nA＞0，則將{NR-R}存入R，即R=NR，把最簡規(guī)則rl1={A=1→Y=1}存入rl。因?yàn)閚=n+nA=所以需要在粒度更細(xì)的空間下繼續(xù)計(jì)算。

在ω=ω+1=2的情況下，每種屬性集合為{{A,B},{A,C},{A,D},{B,C},{B,D},{C,D}}，其屬性空間內(nèi)剩余屬性的集合為{{C,D},{B,D},{B,C},{A,D},{A,C},{A,B}},同樣可計(jì)算得出：

由于已經(jīng)區(qū)分出屬性A下取值為“1”的規(guī)則，無需判斷YAB、YAC、YAD的第3、4行（相容類中A取值為1），該邏輯關(guān)系矩陣不能提取新規(guī)則。

根據(jù)YBC的值，可以判斷出屬性{BC}在取值為“00”和“11”的情況下可以獲得新規(guī)則，即NR={m0,m1,m8,m9,m6,m7,m14,m15},NR-R={m0,m1,m6,m7}。因此新規(guī)則的位置為Row={1,4},Col={1,2}，可得nBC=1+1+1+1=4＞0，將 {NR-R}存入R可得R={m0,m1,m6,m7,m8～m15}，把最簡規(guī)則rl2={B=0∧C=0→Y=1},rl3={B=1∧C=1→Y=1}存入rl。由于n=n+nBC=24＜N，需要繼續(xù)計(jì)算。

根據(jù)YBD的值，可以判斷屬性{BD}在取值“11”的情況下可以獲得新規(guī)則，即NR={m5,m7,m13,m15}，而NR-R={m5}，因此新規(guī)則的位置為Row={4},Col={1}，可得nBD=1＞0。將 {NR-R}存入R得R={m0～m1,m5,m6～m15}，最簡規(guī)則rl4={B=1∧D=1→Y=1}存入rl。由于n=n+nBD=25=N，計(jì)算結(jié)束。

最終得到該算例的4條最簡規(guī)則（在集合rl中），將規(guī)則表示為邏輯表達(dá)式，即算法輸出為Y=A+BC+BˉCˉ+BD，與卡諾圖法結(jié)果一致（見例1）。

5.2 算法正確性分析

卡諾圖法是公認(rèn)的簡單、正確的邏輯表達(dá)式化簡算法，算法1與卡諾圖法等價(jià)，證明如下。

卡諾圖法：設(shè)一個(gè)普通的真值表具有m個(gè)邏輯輸入，K為真值表所對(duì)應(yīng)的卡諾圖[1,3]。K中任意一個(gè)依照規(guī)則得到的圈Ωi由2k個(gè)取值為1的最小項(xiàng)組成(0≤k≤m)，Ω={Ωi|Ωi∈K}。Θi={com(Ωi)}表示Ωi中的公共因子。根據(jù)卡諾圖化簡原則，Θi是Ωi的約簡，構(gòu)成卡諾圖的化簡結(jié)果。令中最小項(xiàng)個(gè)數(shù)，中公共因子的變量個(gè)數(shù)，即約簡后輸入變量的個(gè)數(shù)。存在如下關(guān)系

在算法1中，設(shè)在第ω次迭代情況下，根據(jù)輸入屬性集合P求得的某個(gè)邏輯關(guān)系矩陣為YP，且其維度為2|P|×2|X-P|。根據(jù)邏輯關(guān)系矩陣的定義，可知其每一個(gè)元素均表示P的相容類與(X-P)的相容類的相交項(xiàng)，即為最小項(xiàng)的矩陣表示。若YP中存在某行元素全為非0元素，根據(jù)定理2，可知P的某個(gè)相容類可以覆蓋(X-P)的所有相容類，即在該相容類下存在2|X-P|個(gè)取值為1的最小項(xiàng)。設(shè)P在該相容類下的取值為因此，根據(jù)YP可以得到卡諾圖的一個(gè)圈Ωi。由此可知，算法1與卡諾圖原理一致，即滿足等價(jià)性。

在例3中，YA的第二行全為非0元素，則在A=1的相容類下，存在2|X-P|=8個(gè)最小項(xiàng)，分別為ABCD、此時(shí)根據(jù)YA可得到卡諾圖一個(gè)圈Ω1，如圖1所示。

Fig.1 Sketch map for Karnaugh map reduction圖1 卡諾圖化簡示意圖

同理，在第二次迭代運(yùn)算時(shí)，可得到卡諾圖中另外的3個(gè)圈Ω2、Ω3、Ω4，如圖1。由于已覆蓋卡諾圖中的全部“1”元素（對(duì)應(yīng)于算法1中判斷n是否等于N），算法輸出為

等價(jià)性證明則保證了算法1的正確性。

6 結(jié)束語

本文針對(duì)數(shù)字電路中邏輯表達(dá)式化簡問題，提出了基于相容關(guān)系的邏輯表達(dá)式化簡算法。算法首先將一般邏輯表達(dá)式轉(zhuǎn)化為與或表達(dá)式，輸入項(xiàng)中含有無關(guān)項(xiàng)的真值表，然后在不同粒度空間下分析真值表中隱含的最簡邏輯規(guī)則，最后將所有邏輯規(guī)則再轉(zhuǎn)化為邏輯表達(dá)式，實(shí)現(xiàn)邏輯表達(dá)式的快速化簡。本文算法有以下特點(diǎn)：（1）相比于傳統(tǒng)算法，本文從多粒度的角度出發(fā)，使規(guī)則提取變得直觀，并且保證了提取規(guī)則的完整性；（2）在粒度為ω的粒度空間下，能同時(shí)計(jì)算屬性子集個(gè)數(shù)為ω和個(gè)數(shù)為的相容矩陣，避免了在粒度為的粒度空間下重新計(jì)算各屬性子集的相容矩陣，降低了算法復(fù)雜度；（3）通過定義已尋到的規(guī)則數(shù)n來判斷是否可以跳出循環(huán)輸出結(jié)果，加速了算法的收斂，提高了效率；（4）通過算法正確性分析可知本文算法與卡諾圖法等價(jià)，且本文算法沒有輸入變量個(gè)數(shù)的限制，更具有一般性。本文算法的不足之處在于，雖然在一定程度上降低了算法的運(yùn)算復(fù)雜性，但是在最壞情況下仍沒有突破指數(shù)階的算法復(fù)雜度。因此，如何解決復(fù)雜度為指數(shù)階的NP問題仍是亟待思考的問題，相關(guān)工作仍在繼續(xù)。

[1]Yu Mengchang.Concise course of digital electronic technology[M].Beijing:Higher Education Press,2006.

[2]Kang Huaguang.Fundamentals of electronic technology—digital part[M].Beijing:Higher Education Press,2006.

[3]Quine W V.The problem of simplifying truth functions[J].American Mathematical Monthly,1952,59(8):521-531.

[4]Bian Jinian,Xue Hongxi,Su Ming,et al.Digital system design automation[M].Beijing:Tsinghua University Press,2005.

[5]Khalid A T M S,Ahmed F,Karim M A.A composite mapping technique for simplification of multi-variable Boolean expressions[C]//Proceedings of the IEEE 1995 NationalAerospace and Electronics Conference,Dayton,May 22-26,1995.Piscataway:IEEE,1995:256-262.

[6]Solairaju A,Periyasamy R.Optimal Boolean function simplification through K-map using object-oriented algorithm[J].International Journal of Computer Applications,2011,15(7):28-32.

[7]Tomaszewski S P,Celik I U,Antoniou G E.WWW-based Boolean function minimization[J].International Journal of Applied Mathematics&Computer Science,2003,13(4):577-583.

[8]Huang Jiangbo.Programing implementation of the Quine-McCluskey method for minimization of Boolean expression[J/OL].arXiv:1410.1059.

[9]Gómez L,Gómez R,Garcia B.Some simplifications of Boolean expressions using their topological and statistical properties[J].International Journal of Electronics,1981,51(2):145-155.

[10]Chowdhury R R,Bandyopadhyay C,Dutta P,et al.A Boolean expression based template matching technique for optical circuit generation[C]//Proceedings of the 2016 International Conference on Advances in Information Communication Technology&Computing,Bikaner,Aug 12-13,2016.New York:ACM,2016:36.

[11]Chen Zehua,Ma He.Granular matrix based rapid parallel reduction algorithm for MIMO truth table[J].Journal of Electronics and Information Technology,2015,37(5):1260-1265.

[12]Shao Mingwen,Zhang Wenxiu.Dominance relation and rules in an incomplete ordered information system[J].International Journal of Intelligent Systems,2005,20(1):13-27.

[13]Yang Xibei,Qi Yong,Yu Dongjun,et al.Rough set approach to incomplete multiscale information system[J].Scientific World Journal,2014,1:538968.

[14]Wu Weizhi,Qian Yuhua,Li Tongjun,et al.On rule acquisition in incomplete multi-scale decision tables[J].Information Sciences,2017,378(C):282-302.

[15]Guan Lihe,Hu Feng,Han Fengqing.A rule induction algorithm in incomplete decision table based on attribute order[J].Journal of Intelligent&Fuzzy Systems,2016,30(2):961-969.

附中文參考文獻(xiàn)：

[1]余孟嘗.數(shù)字電子技術(shù)基礎(chǔ)簡明教程[M].北京:高等教育出版社,2006.

[2]康華光.電子技術(shù)基礎(chǔ)數(shù)字部分[M].北京:高等教育出版社,2006.

[4]邊計(jì)年,薛紅熙,蘇明,等.數(shù)字系統(tǒng)設(shè)計(jì)自動(dòng)化[M].北京:清華大學(xué)出版社,2005.

[11]陳澤華,馬賀.基于粒矩陣的多輸入多輸出真值表快速并行約簡算法[J].電子與信息學(xué)報(bào),2015,37(5):1260-1265.