卡諾圖化簡法(reduced method of a Karnaugh map)是化簡真值函式的方法之一，它具有幾何直觀性這一明顯的特點，在變元較少(不超過六個)的情況下比較方便，且能得到最簡結果。此法由卡諾(M.Karnaugh)於1953年提出，其具體步驟如下：1.構造卡諾框；2.在卡諾框上做出所給真值函式f的卡諾圖；3.用卡諾圖化簡真值函式，首先把相鄰的1字塊兩兩合成矩形得到一維塊；把22個相鄰的1字塊合成矩形(或正方形)得到二維塊;把23個相鄰的1字塊合成矩形得到三維塊等，合成的各種維塊統稱f的合塊；4.把f的卡諾圖中全部1字塊做成若干個合塊，這樣一組合塊就稱為f的一個覆蓋組，f的一切覆蓋組中所含塊數最小的組即是f的最小覆蓋組；5.在最小覆蓋組中，合塊維數總和最大的組的對應式是f的最簡式。
基本介紹
- 中文名：卡諾圖化簡法
- 外文名：reduced method of a Karnaugh map
- 所屬學科：數學
- 簡介：化簡真值函式的方法之一
- 提出者：卡諾(M.Karnaugh)
基本介紹,卡諾圖的構成,基本原理,構圖,邏輯函式在卡諾圖上的表示,卡諾圖化簡邏輯函式的原理,例題解析,
基本介紹
用代數法化簡邏輯函式，需要依賴經驗和技巧，有些複雜函式還不容易求得最簡形式。卡諾圖化簡法是一種更加系統並有統一規則可循的邏輯函式化簡法。
卡諾圖的構成
基本原理
卡諾圖用方格陣列的形式列出所有的變數組合和每個組合值所對應的輸出。卡諾圖的格數與輸入變數可能的組合數相等，也就是最小項總數2n(n為變數數)，每一個方格表示一個最小項。
變數取值不按二進制數的順序排列，而是按循環碼排列，使相鄰兩個方格只有一個變數不同(一個變數變化)，而其餘變數是相同的。
卡諾圖的特點：在幾何位置上相鄰的最小項小方格在邏輯上也必定是相鄰的，即相鄰兩項中有一個變數是互補的。
構圖
(1)二變數卡諾圖，如圖1所示。
如果將上面左圖中的反變數用0表示，原變數用1表示，它們所代表的十進制數就是上面右圖中的m的下標i的值。
(2)三變數卡諾圖，如圖2所示。
（3）四變數卡諾圖，如下圖所示。
圖3 四變數卡諾圖邏輯函式在卡諾圖上的表示
(1)將邏輯函式變換成標準“與或”式(最小項表達式)；
(2)在表達式中含有最小項所對應的小方格填入“1”，其餘位置則填入“0”，便得到該函式的卡諾圖。
卡諾圖化簡邏輯函式的原理
卡諾圖化簡邏輯函式的基本原理，是依據關係式
，即兩個“與”項中，如果只有一個變數相反，其餘變數均相同，則這兩個“與”項可以合併成一項，消去其中互反的變數。
相鄰最小項用倒角矩形圈(或橢圓形圈)圈起來，稱為卡諾圈。在合併項(卡諾圈)所處位置上，若某變數的代碼有0也有1，則該變數被消去，否則該變數被保留，並按0為反變數，1為原變數的原則寫成乘積項形式的合併項中。
圖4（a）
圖4（b）畫卡諾圈所遵循的規則：
(1)必須包含所有的最小項；
(2)按照“從小到大”順序，先圈孤立的“1”．再圈只能兩個組合的，再圈四個組合的……
(3)圈的圈數要儘可能少(乘積項總數要少)；
(4)圈要儘可能大(乘積項中含的因子最少)。
無論是否與其他圈相重，也要儘可能畫大，相重是指在同一塊區域可以重複圈多次，但每個圈至少要包含一個尚未被圈過的“1”。
例題解析
【例1】
F=(A，B，C，D)=∑m(1，7，12)
分析：即在四變數卡諾圖中對應m1,m7,m12的小方格中填入1，其餘位置為0。卡諾圖如圖5所示。
圖5【例2】用卡諾圖化簡函式F，其中F(A，B，C，D)=∑m(1，5，6，7，11，12，13，15)
分析：先畫出卡諾圖(如下圖所示)，標出上面的“1”的位置，用圈圈定後，再化簡成函式表達式的形式：
圖6