相容關系模型及其在邏輯優化中的應用*

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

太原理工大學 信息工程學院，太原 030024

1 引言

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

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

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

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

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

2 預備知識

2.1 邏輯表達式化簡相關概念

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

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

邏輯表達式化簡遵循如下邏輯代數基本定律。

（1）0-1律

（2）結合律、交換律、分配律

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

本文通過例1說明上述幾種表達式的表現形式，并根據計算實現表達式之間的轉換。

例1一個數字電路的邏輯表達式為：

將其轉化為與或表達式為：

對于四輸入的邏輯電路，單項式A可轉化為8個最小項之和：

將與或表達式轉化為最簡與或表達式為（卡諾圖法[2]）：

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

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

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

相容關系是處理不完備決策表的重要理論工具，Kryszkiewicz最初對其進行了數學定義。

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

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

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

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

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

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

例2沿用例1，將與或表達式轉化為真值表，如表1所示。

Table 1 Incomplete truth table for corresponding logical function表1 邏輯函數對應的不完備真值表

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

3 邏輯關系矩陣

以下主要介紹邏輯關系矩陣的計算方法，并給出相應定理說明邏輯關系矩陣的意義。

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

其中，aij的計算公式如下：

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

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

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

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

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

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

4 基于相容關系的邏輯表達式化簡算法

4.1 啟發式算子

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

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

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

定義8（最小項集合）已尋到的規則的輸入項均可以轉化為最小項，這些最小項放置在同一集合即為最小項集合。

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

本文為了避免對規則冗余性的判斷，利用邏輯關系矩陣提出如下定理。

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

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

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

推論已尋到的規則數n等于所有屬性集合尋到的規則數的總和，即

規則數n和原規則數N存在如下定理，可加速算法的收斂。

定理3當已尋到的規則數n和真值表的總規則數N滿足條件n=N時，算法即收斂。

4.2 算法描述

本文基于多粒度的思想，提出了基于相容關系的邏輯表達式化簡算法，該算法的計算步驟如下：

算法1基于相容關系的邏輯表達式化簡算法

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

輸出：最簡邏輯表達式。

1.將一般邏輯表達式轉化為析取范式，并轉化為真值表；

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

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

4.找出YP中全不為0的行，并找出對應規則，計算nx，判斷nx是否大于0；

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

6.若nx=0，則轉至步驟7；

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

8.判斷ω是否達到最大值（ω最大為|X|），若沒有達到，則ω=ω+1，返回步驟3繼續計算，否則轉至步驟9；

9.將rl中的規則轉化為邏輯表達式，輸出邏輯規則。

4.3 復雜度分析

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

5 實驗與分析

5.1 實例說明

例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={?}，根據式（5）可知，22+…+20=25，置n=0，ω=1。

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

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

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

再根據式（4），計算各屬性集合的邏輯關系矩陣，得：

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

根據式（8）可計算得到：

由nA＞0，則將{NR-R}存入R，即R=NR，把最簡規則rl1={A=1→Y=1}存入rl。因為n=n+nA=所以需要在粒度更細的空間下繼續計算。

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

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

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

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

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

5.2 算法正確性分析

卡諾圖法是公認的簡單、正確的邏輯表達式化簡算法，算法1與卡諾圖法等價，證明如下。

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

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

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

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

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

等價性證明則保證了算法1的正確性。

6 結束語

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

[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.

附中文參考文獻：

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

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

[4]邊計年,薛紅熙,蘇明,等.數字系統設計自動化[M].北京:清華大學出版社,2005.

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