淺談在卡諾圖中實現對偶律的方法

姜書艷 張優 盧有亮 劉科 張博

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

關鍵詞：邏輯代數;對偶律;卡諾圖;反碼

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

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

文獻1僅給出了公式法對卡諾圖實現對偶律的問題的解決，較為煩瑣。文獻2中提出了新的概念“對偶卡諾圖”，并應用它來化簡最大項相與的邏輯表達式。該方法是將對偶律應用在了整個卡諾圖化簡的所有步驟中，對直接化簡最大項相與的邏輯表達式較為有用。然而我們對最大項相與的邏輯表達式可以先對偶為最小項相或的邏輯表達式，然后使用傳統方法進行化簡，這樣更為簡單?；谝陨衔墨I的啟發，本文給出卡諾圖法實現對偶律的方法。

一、對偶規則

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

二、在卡諾圖中實現對偶律

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

（一）定義法

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

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

（二）公式法

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

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

（三）反碼法

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

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

三、結論

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

參考文獻：

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

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

[3]姜書艷.數字邏輯設計及應用[M].電子科技大學出版社，2014.

[4]王詩兵，黃正杰.關于卡諾圖法實現邏輯函數變換的研究[J].安徽職業技術學院學報，2005，（4）：5-7.

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

[6]羅嘉慶，周世杰，徐潔.原碼、反碼和補碼的教學探討[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