發展曆史
組合電路邏輯關系的圖形表示法可以追溯到英國邏輯學家約翰·維恩(John Venn)1881年發明的在集合論中處理集合間邏輯關系的文氏圖(Venn diagram),赫爾姆·哈斯(Helmut Hasse)有效地利用Vogt在1895年用過的哈斯圖(Hasse diagram)來表示序理論中的有限偏序集,愛德華·維奇(Edward W. Veitch)在1952年将維恩圖中的圓形改畫成矩形而發明了維奇圖(Veitch diagram)。但這些圖都不如美國貝爾實驗室的電信工程師莫裡斯·卡諾(Maurice Karnaugh)在1953年根據維奇圖改進的卡諾圖(Karnaugh map)或K圖(K-map)在數字邏輯、故障診斷等許多領域中應用廣泛。
化簡法
由于卡諾圖兩個相鄰最小項中,隻有一個變量取值不同,而其餘的取值都相同。所以,合并相鄰最小項,利用公式A+A=1,AB+AB=A,可以消去一個或多個變量,從而使邏輯函數得到簡化。
(1)卡諾圖中最小項合并的規律合并相鄰最小項,可消去變量。合并兩個最小項,可消去一個變量;合并四個最小項,可消去兩個變量;合并八個最小項,可消去三個變量;合并2N個最小項,可消去N個變量。
(2)利用卡諾圖化簡邏輯函數 A.基本步驟: ① 畫出邏輯函數的卡諾圖; ② 合并相鄰最小項(圈組); ③ 從圈組寫出最簡與或表達式。關鍵是能否正确圈組 。 B.正确圈組的原則 ① 必須按2、4、8、2N的規律來圈取值為1的相鄰最小項; ② 每個取值為1的相鄰最小項至少必須圈一次,但可以圈多次; ③ 圈的個數要最少(與項就少),并要盡可能大(消去的變量就越多)。 C.從圈組寫最簡與或表達式的方法: ① 将每個圈用一個與項表示圈内各最小項中互補的因子消去,相同的因子保留,相同取值為1用原變量,相同取值為0用反變量; ② 将各與項相或,便得到最簡與或表達式。圈組技巧(防止多圈組的方法): ① 先圈孤立的1; ② 再圈隻有一種圈法的1; ③ 最後圈大圈; ④檢查:每個圈中至少有一個1未被其它圈圈過。
變量
表示各最小項的2^n(n-變量數)個小格,排列呈矩形。
小格按“循環碼” 排列,保證最小項間“幾何相鄰”與“邏輯相鄰性”的統一。(幾何相鄰有“内相鄰” “外相鄰”和“中心對稱”)
化簡函數
1.幾個定義
蘊涵項:在函數的“與-或”表達式中,每個“與”項被稱為該函數的蘊涵項(Implicant)。
顯然,在函數卡諾圖中,任何一個1方格所對應的最小項或者卡諾圈中的2m個1方格所對應的“與”項都是函數的蘊涵項。
質蘊涵項:若函數的一個蘊涵項不是該函數中其他蘊涵項的子集,則此蘊涵項稱為質蘊涵項(Prime Implicant),簡稱為質項。
顯然,在函數卡諾圖中,按照最小項合并規律,如果某個卡諾圈不可能被其他更大的卡諾圈包含,那麼,該卡諾圈所對應的“與”項為質蘊涵項。
必要質蘊涵項:若函數的一個質蘊涵項包含有不被函數的其他任何質蘊涵項所包含的最小項,則此質蘊涵項被稱為必要質蘊涵項(Essential Prime Implicant),簡稱為必要質項。
在函數卡諾圖中,若某個卡諾圈包含了不可能被任何其他卡諾圈包含的1方格,那麼,該卡諾圈所對應的“與”項為必要質蘊涵項。
2.求函數最簡“與-或”表達式
(1)一般步驟: 第一步:作出函數的卡諾圖。
第二步:在卡諾圖上圈出函數的全部質蘊涵項。按照卡諾圖上最小項的合并規律,對函數F卡諾圖中的1方格畫卡諾圈。為了圈出全部質蘊涵項,畫卡諾圈時在滿足合并規律的前題下應盡可能大,若卡諾圈不可能被更大的卡諾圈包圍,則對應的“與”項為質蘊涵項。
第三步:從全部質蘊涵項中找出所有必要質蘊涵項。在卡諾圖上隻被一個卡諾圈包圍的最小項被稱為必要最小項,包含必要最小項的質蘊涵項即必要質蘊涵項。為了保證所得結果無一遺漏地複蓋函數的所有最小項,函數表達式中必須包含所有必要質蘊涵項。
第四步:求出函數的最簡質蘊涵項集。若函數的所有必要質蘊涵項尚不能複蓋卡諾圖上的所有1方格,則從剩餘質蘊涵項中找出最簡的所需質蘊涵項,使它和必要質蘊涵項一起構成函數的最小複蓋。
歸納起來,卡諾圖化簡的原則是:
☆ 在複蓋函數中的所有最小項的前提下,卡諾圈的個數達到最少。
☆ 在滿足合并規律的前提下卡諾圈應盡可能大。
☆ 根據合并的需要,每個最小項可以被多個卡諾圈包圍。
3.求函數的最簡“或-與”表達式
當需要求一個函數的最簡“或-與”表達式時,可采用“兩次取反法”。
具體如下:
☆ 先求出函數F的反函數F的最簡“與-或”表達(合并卡諾圖上的0方格);
☆ 然後對F的最簡“與-或”表達式取反,從而得到函數F的最簡“或-與”表達式。
卡諾圖化簡邏輯函數具有方便、直觀、容易掌握等優點。但依然帶有試湊性。尤其當變量個數大于6時,畫圖以及對圖形的識别都變得相當複雜。