淺談在卡諾圖中實現(xiàn)對偶律的方法

姜書艷 張優(yōu) 盧有亮 劉科 張博

摘要：應(yīng)用卡諾圖來處理邏輯函數(shù)可以方便快速地使函數(shù)化簡或變形。本文基于邏輯代數(shù)中的對偶律和卡諾圖的化簡方法，提出了在卡諾圖中實現(xiàn)對偶律的方法：定義法，公式法，反碼法。不同方法簡單程度不同，反碼法最為簡便。

關(guān)鍵詞：邏輯代數(shù);對偶律;卡諾圖;反碼

中圖分類號：G642.0? ? ?文獻標志碼：A? ? ?文章編號：1674-9324（2019）12-0219-02

對偶律在邏輯代數(shù)中有著非常廣泛的應(yīng)用。任何一個邏輯函數(shù)，都有它對應(yīng)的對偶式。邏輯代數(shù)中的公式都是成對出現(xiàn)的，每個公式的對偶式都是成立的。這使得我們在學(xué)習(xí)邏輯代數(shù)時，只需掌握一半的公式即可用對偶律得到另一半公式，大大減少了我們的工作量。在實際應(yīng)用中，正邏輯約定和負邏輯約定互為對偶關(guān)系，所以對偶律在邏輯電路中也有著很大作用。

文獻1僅給出了公式法對卡諾圖實現(xiàn)對偶律的問題的解決，較為煩瑣。文獻2中提出了新的概念“對偶卡諾圖”，并應(yīng)用它來化簡最大項相與的邏輯表達式。該方法是將對偶律應(yīng)用在了整個卡諾圖化簡的所有步驟中，對直接化簡最大項相與的邏輯表達式較為有用。然而我們對最大項相與的邏輯表達式可以先對偶為最小項相或的邏輯表達式，然后使用傳統(tǒng)方法進行化簡，這樣更為簡單。基于以上文獻的啟發(fā)，本文給出卡諾圖法實現(xiàn)對偶律的方法。

一、對偶規(guī)則

對偶規(guī)則：對于任何邏輯函數(shù)表達式Y(jié)，如果將式中所有的符號“·”換成“+”，“+”換成“·”，“1”換成“0”，“0”換成“1”，并不改變原來的運算次序，則得新的邏輯函數(shù)式Y(jié)D，YD是Y的對偶式。同樣，Y也是YD的對偶式。例如，F(xiàn)=（A+B+C）（A+B+C）（A+B+C）的對偶式為FD=ABC+ABC+ABC。該對偶規(guī)則可對公式進行化簡。

二、在卡諾圖中實現(xiàn)對偶律

下面討論在卡諾圖中如何實現(xiàn)畫出原函數(shù)的對偶函數(shù)。例如，我們對圖1所示的卡諾圖表示的邏輯函數(shù)求對偶式，則得到圖2所示的邏輯函數(shù)。以下給出三種方法。

（一）定義法

根據(jù)對偶規(guī)則，將原函數(shù)的對偶式寫出，再按照最小項填1、最大項填0的規(guī)則填寫卡諾圖，即得對偶函數(shù)的卡諾圖。該方法最為原始，耗時較長，容易出錯。然后進行圈“0”格的操作，即可寫出對偶函數(shù)的最簡“先或再與”表達式。（這一步為利用卡諾圖化簡對偶式，與本文討論的方法無關(guān)，以下兩方法中不再重復(fù)。）

在上例中，我們寫出F的邏輯表達式，F(xiàn)=ABC+ABC+ABC+ABC，用卡諾圖化簡后為F=BC+AC，寫出原函數(shù)的對偶式，為FD=（A+B+C）（A+B+C）（A+B+C）（A+B+C）。其中（A+B+C）在真值表中對應(yīng)101，所以在卡諾圖中ABC對應(yīng)101的格子填0，其他最大項的填法以此類推，即得圖2所示的卡諾圖，用卡諾圖化簡表達式后FD=（B+C）（A+C）。

（二）公式法

首先，由原函數(shù)的卡諾圖獲得其全部最小項編號（即原函數(shù)卡諾圖中的1格所對應(yīng)編號）。用（2n-1）減去這些編號（n為函數(shù)變量個數(shù)），由此獲得對偶式的全部最大項的編號，填出對應(yīng)的卡諾圖即可。此方法即為文獻1所提到的方法，對于每一項的編號都需要進行一次運算，其間還要進行二進制與十進制的轉(zhuǎn)換，較為煩瑣。該方法原理如下：一個n變量函數(shù)的最小項mi，其對偶為：（mi）d=（*）那么對偶式中的最大項與原函數(shù)中的最小項一一對應(yīng)，其關(guān)系為：若原函數(shù)中最小項編號為i，則對偶函數(shù)中有編號為（2n-1）-i的最大項（n為函數(shù)變量個數(shù)）。

在上例中，我們寫出F的邏輯表達式，F(xiàn)=ABC+ABC+ABC+ABC，用最小項之和表示為FD=（A+B+C）（A+B+C）（A+B+C）（A+B+C），用卡諾圖化簡后為FD=（B+C）（A+C）。

（三）反碼法

不難注意到，公式法中公式（*）的下標之和為2n-1，這與我們求反碼的方法極為相像。我們只要將卡諾圖中每一個方格所對應(yīng)的二進制數(shù)取反碼，在對應(yīng)的格子中填入相應(yīng)的邏輯值，原來是0的對應(yīng)的填1，原來是1的對應(yīng)的填0即可。例如，原函數(shù)中000對應(yīng)的格子填的是0，那么我們應(yīng)該在對偶式中111對應(yīng)的格子中填1。其他格子的填法以此類推。此方法最為簡便。該方法原理如下：在用二進制表達最小項時，我們把原變量寫為1，反變量寫為0。比如對于ABC這樣的最小項，我們用二進制表達為101，它在卡諾圖中對應(yīng)的二進制也為101。而在用二進制表達最大項時，我們把原變量寫為0，反變量寫為1，與最小項的表達就是反碼關(guān)系。比如，對于ABC的對偶A+B+C這樣的最大項，我們用二進制表達為010，恰恰與原式的101形成反碼關(guān)系。

在上例中，我們寫出F的邏輯表達式，F(xiàn)=ABC+ABC+ABC+ABC，它的最小項用二進制原碼表示為001，010，011，110。對每一項取反碼之后，得到110，101，100，001，在它的對偶式的卡諾圖中對應(yīng)的填上0，得到對偶函數(shù)為FD=（A+B+C）（A+B+C）（A+B+C）（A+B+C），用卡諾圖化簡后為FD=（B+C）（A+C）。

三、結(jié)論

本文提出的三種方法都可以在卡諾圖中實現(xiàn)對偶律，不同方法簡單程度不同。定義法直接按照對偶規(guī)則寫出對偶式再填卡諾圖，最為原始，耗時較長，容易出錯。公式法利用原函數(shù)的最小項和對偶式的最大項之間的和不變關(guān)系，對于每一項的編號都需要進行一次運算，其間還要進行二進制與十進制的轉(zhuǎn)換，較為復(fù)雜。反碼法只需對填1的格子對應(yīng)的二維碼取反碼，并在新圖中填0即可。相比之下反碼法最為簡便。

參考文獻：

[1]徐兵，朱鵬遠.基于卡諾圖在處理邏輯函數(shù)方面的應(yīng)用研究[J].昌吉學(xué)院學(xué)報，2010，（3）：96-98.

[2]張迎.反演卡諾圖和對偶卡諾圖[J].湖州師專學(xué)報，1996，（6）：31-35.

[3]姜書艷.數(shù)字邏輯設(shè)計及應(yīng)用[M].電子科技大學(xué)出版社，2014.

[4]王詩兵，黃正杰.關(guān)于卡諾圖法實現(xiàn)邏輯函數(shù)變換的研究[J].安徽職業(yè)技術(shù)學(xué)院學(xué)報，2005，（4）：5-7.

[5]陳小芳.邏輯函數(shù)的卡諾圖化簡法[J].計算機時代，2010，（8）：49-51.

[6]羅嘉慶，周世杰，徐潔.原碼、反碼和補碼的教學(xué)探討[J].計算機教育，2015，（10）：42-45.

The Methods to Apply Duality Theorem in Karnaugh Map

JIANG Shu-yan，ZHANG You，LU You-liang，LIU Ke，ZHANG Bo

（University of Electronic Science and Technology of China，Chengdu，Sichuan 611731，China）

Abstract：Using Karnaugh map to deal with logic functions can simplify and transform logic functions fast and conveniently.The paper presents some methods to apply Duality Theorem in Karnaugh map，based on Duality Theorem in Logic Algebra and simplification method of Karnaugh map.The level of complexity varies from methods to methods.Among definition method，formula method，ones'- complement method，ones'- complement method is the simplest and most convenient one.

Key words：logic algebra;duality theorem;Karnaugh map;ones'- complement