卡諾圖

在邏輯代數中，卡諾圖（Karnaugh map）是真值表的變形，它可以將有n個變量的邏輯函數的${\displaystyle 2^{n}}$個最小項組織在給定的長方形表格中，同時為相鄰最小項（相鄰與項）運用鄰接律化簡提供了直觀的圖形工具。但是，如果需要處理的邏輯函數的自變量較多（有五個或更多的時候，此時有些項就很難圈了），那麼卡諾圖的行列數將迅速增加，使圖形更加複雜。^[1]:189

卡諾圖是貝爾實驗室的電信工程師莫里斯·卡諾（Maurice Karnaugh）在1953年發明的。

變量卡諾圖

• 表示各最小項的${\displaystyle 2^{n}}$（n-變量數）個小格，排列呈矩形。
• 小格按「格雷碼」 排列，保證最小項間「幾何相鄰」與「邏輯相鄰性」的統一。（幾何相鄰有「內相鄰」 「外相鄰」和「中心對稱」）

函數卡諾圖

• 最小項（${\displaystyle \sum _{}m}$）：把函數包含的所有最小項，以「1」填入變量卡諾圖對應編號的小格內。
• 最大項（${\displaystyle \prod _{}M}$）：把函數包含的所有最大項，以「0」填入變量卡諾圖對應編號的小格內。

用卡諾圖化簡邏輯函數的步驟

• 如果表達式為最小項表達式，則可直接填入卡諾圖
• 如表達式不是最小項表達式，但是「與—或表達式」，可將其先化成最小項表達式，再填入卡諾圖。也可直接填入。
• 合併相鄰的最小項，即根據下述原則畫圈
  • 儘量畫大圈，但每個圈內只能含有${\displaystyle 2^{n}}$（n=0,1,2,3……）個相鄰項。要特別注意對邊相鄰性和四角相鄰性。
  • 圈的個數儘量少。
  • 卡諾圖中所有取值為1的方格均要被圈過，即不能漏下取值為1的最小項。
  • 在新畫的包圍圈中至少要含有1個未被圈過的1方格，否則該包圍圈是多餘的。
• 寫出化簡後的表達式。每一個圈寫一個最簡與項，規則是，取值為l的變量用原變量表示，取值為0的變量用反變量表示，將這些變量相與。然後將所有與項進行邏輯加，即得最簡與—或表達式。

在進行化簡時，如果用圖中真值為0的項更方便，可以用他們來處理，方法和真值取1時一樣，只是結果要再做一次求反。

範例

範例--2變數卡諾圖

• 
  Σm(0); K = 0
• 
  Σm(1); K = A′B′
• 
  Σm(2); K = AB′
• 
  Σm(3); K = A′B
• 
  Σm(4); K = AB
• 
  Σm(1,2); K = B′
• 
  Σm(1,3); K = A′
• 
  Σm(1,4); K = A′B′ + AB
• 
  Σm(2,3); K = AB′ + A′B
• 
  Σm(2,4); K = A
• 
  Σm(3,4); K = B
• 
  Σm(1,2,3); K = A' + B′
• 
  Σm(1,2,4); K = A + B′
• 
  Σm(1,3,4); K = A′ + B
• 
  Σm(2,3,4); K = A + B
• 
  Σm(1,2,3,4); K = 1

範例--4變數卡諾圖

一個4變量卡諾圖的例子：

某函數的真值表

	A	B	C	D	${\displaystyle f(A,B,C,D)}$
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
3	0	0	1	1	0
4	0	1	0	0	0
5	0	1	0	1	0
6	0	1	1	0	1
7	0	1	1	1	0
8	1	0	0	0	1
9	1	0	0	1	1
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

我們可以用兩個不同的寫法，及四個不同的布爾變量A, B, C, D和他們的相反值，來表示同一個尚未化簡的布爾代數：

• ${\displaystyle f(A,B,C,D)=\sum _{}m_{i},i\in \{6,8,9,10,11,12,13,14\}}$這個${\displaystyle {}m_{i}}$是卡諾圖的最小項（即圈出來的值${\displaystyle i}$在真值表上顯示為1）。
• ${\displaystyle f(A,B,C,D)=\prod _{}M_{i},i\in \{0,1,2,3,4,5,7,15\}}$ 這個 ${\displaystyle M_{i}}$ 是卡諾圖的最大項（即圈出來的值${\displaystyle i}$在真值表上顯示為0）。

某函數的卡諾圖（圈法1）

A B C D	0 0	0 1	1 1	1 0
0　0	0	0	1	1
0　1	0	0	1	1
1　1	0	0	0	1
1　0	0	1	1	1

某函數的卡諾圖（圈法2）

A B C D	0 0	0 1	1 1	1 0
0　0	0	0	1	1
0　1	0	0	1	1
1　1	0	0	0	1
1　0	0	1	1	1

按照上述卡諾圖圈法（不限於上述兩種），可知化簡結果為AC'+AB'C+BCD'或ABC'+AB'+BCD'

參考文獻

引註

1. Stephen Brown, Zvonko Vranesic. Fundamentals of Digital Logic with Verilog Design. McGraw-Hill Education. 2002. ISBN 0-07-283878-7.

來源

期刊文章

• Karnaugh, Maurice. The Map Method for Synthesis of Combinational Logic Circuits. Transactions of American Institute of Electrical Engineers part I. November 1953, 72 (9): 593–599.