發展歷史
組合電路邏輯關係的圖形表示法可以追溯到英國邏輯學家約翰·維恩(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未被其它圈圈過。
變數
![變數卡諾圖](/img/7/f11/nBnauM3X1QTNzMTM3UTO1IzN0QTMwADMwADMwADMwATMxAzL1kzL1gzLt92YucmbvRWdo5Cd0FmLzE2LvoDc0RHa.jpg)
表示各最小項的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時,畫圖以及對圖形的識別都變得相當複雜。