卡諾圖
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
![]() | 此條目可參照英語維基百科相應條目來擴充。 |
在邏輯代數中,卡諾圖(Karnaugh map)是真值表的變形,它可以將有n個變數的邏輯函數的個最小項組織在給定的長方形表格中,同時為相鄰最小項(相鄰與項)運用鄰接律化簡提供了直觀的圖形工具。但是,如果需要處理的邏輯函數的自變數較多(有五個或更多的時候,此時有些項就很難圈了),那麼卡諾圖的行列數將迅速增加,使圖形更加複雜。[1]:189
卡諾圖是貝爾實驗室的電信工程師莫里斯·卡諾(Maurice Karnaugh)在1953年發明的。
變數卡諾圖
- 表示各最小項的(n-變數數)個小格,排列呈矩形。
- 小格按「格雷碼」 排列,保證最小項間「幾何相鄰」與「邏輯相鄰性」的統一。(幾何相鄰有「內相鄰」 「外相鄰」和「中心對稱」)
函數卡諾圖
- 最小項():把函數包含的所有最小項,以「1」填入變數卡諾圖對應編號的小格內。
- 最大項():把函數包含的所有最大項,以「0」填入變數卡諾圖對應編號的小格內。
用卡諾圖化簡邏輯函數的步驟
- 如果表達式為最小項表達式,則可直接填入卡諾圖
- 如表達式不是最小項表達式,但是「與—或表達式」,可將其先化成最小項表達式,再填入卡諾圖。也可直接填入。
- 合併相鄰的最小項,即根據下述原則畫圈
- 儘量畫大圈,但每個圈內只能含有(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 | ||
---|---|---|---|---|---|
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和他們的相反值,來表示同一個尚未化簡的布林代數:
- 這個是卡諾圖的最小項(即圈出來的值在真值表上顯示為1)。
- 這個 是卡諾圖的最大項(即圈出來的值在真值表上顯示為0)。
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 |
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'
參考文獻
引註
- ^ 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.
|