查看“︁卡诺图”︁的源代码

{{Expand English}}
{{NoteTA
| G1  = Electronics
| G2  = IT
}}
在[[逻辑代数]]中，'''卡诺图'''（Karnaugh map）是[[真值表]]的变形，它可以将有''n''个变量的[[布尔函数|逻辑函数]]的<math>2^n</math>个最小项组织在给定的长方形[[表格]]中，同时为相邻最小项（相邻与项）运用邻接律化简提供了直观的图形工具。但是，如果需要处理的逻辑函数的[[自变量]]较多（有五個或更多的時候，此時有些項就很難圈了），那么卡诺图的行列数将迅速增加，使图形更加复杂。{{R|Stephen|page=189}}

卡诺图是[[贝尔实验室]]的电信工程师[[莫里斯·卡諾]]（Maurice Karnaugh）在1953年发明的。

== 变量卡诺图 ==
* 表示各最小项的<math>2^n</math>（''n''-变量数）个小格，排列呈矩形。
* 小格按“[[格雷码]]” 排列，保证最小项间“几何相邻”与“逻辑相邻性”的统一。（几何相邻有“内相邻” “外相邻”和“中心对称”）

[[File:kanuo1.jpg]]

== 函数卡诺图 ==
* 最小项（<math>\sum_{}m</math>）：把函数包含的所有最小项，以“1”填入变量卡诺图对应编号的小格内。
* 最大项（<math>\prod_{}M</math>）：把函数包含的所有最大项，以“0”填入变量卡诺图对应编号的小格内。

[[File:kanuo2.jpg]]

== 用卡诺图化简逻辑函数的步骤 ==
* 如果表达式为最小项表达式，则可直接填入卡诺图
* 如表达式不是最小项表达式，但是“与—或表达式”，可将其先化成最小项表达式，再填入卡诺图。也可直接填入。
* 合并相邻的最小项，即根据下述原则画圈 
** 尽量画大圈，但每个圈内只能含有<math>2^n</math>（n=0,1,2,3……）个相邻项。要特别注意对边相邻性和四角相邻性。
** 圈的个数尽量少。
** 卡诺图中所有取值为1的方格均要被圈过，即不能漏下取值为1的最小项。
** 在新画的包围圈中至少要含有1个未被圈过的1方格，否则该包围圈是多余的。
* 写出化简后的表达式。每一个圈写一个最简与项，规则是，取值为l的变量用原变量表示，取值为0的变量用反变量表示，将这些变量相与。然后将所有与项进行逻辑加，即得最简与—或表达式。

在进行化简时，如果用图中真值为0的项更方便，可以用他们来处理，方法和真值取1时一样，只是结果要再做一次求反。

== 範例 ==

=== 範例--2變數卡諾圖 ===
<gallery perrow="5">
File:K-map 2x2 none.svg | Σ''m''(0); ''K'' = 0
File:K-map 2x2 1.svg | Σ''m''(1); ''K'' = ''A''′''B''′
File:K-map 2x2 2.svg | Σ''m''(2); ''K'' = ''AB''′
File:K-map 2x2 3.svg | Σ''m''(3); ''K'' = ''A''′''B''
File:K-map 2x2 4.svg | Σ''m''(4); ''K'' = ''AB''
File:K-map 2x2 1,2.svg | Σ''m''(1,2); ''K'' = ''B''′
File:K-map 2x2 1,3.svg | Σ''m''(1,3); ''K'' = ''A''′
File:K-map 2x2 1,4.svg | Σ''m''(1,4); ''K'' = ''A''′''B''′ + ''AB''
File:K-map 2x2 2,3.svg | Σ''m''(2,3); ''K'' = ''AB''′ + ''A''′''B''
File:K-map 2x2 2,4.svg | Σ''m''(2,4); ''K'' = ''A''
File:K-map 2x2 3,4.svg | Σ''m''(3,4); ''K'' = ''B''
File:K-map 2x2 1,2,3.svg | Σ''m''(1,2,3); ''K'' = ''A''' + ''B''′
File:K-map 2x2 1,2,4.svg | Σ''m''(1,2,4); ''K'' = ''A'' + ''B''′
File:K-map 2x2 1,3,4.svg | Σ''m''(1,3,4); ''K'' = ''A''′ + ''B''
File:K-map 2x2 2,3,4.svg | Σ''m''(2,3,4); ''K'' = ''A'' + ''B''
File:K-map 2x2 1,2,3,4.svg | Σ''m''(1,2,3,4); ''K'' = 1
</gallery>

=== 範例--4變數卡諾圖 ===
一个4变量卡诺图的例子：

{| class="wikitable" style="text-align: center"
|+ 某函数的真值表
|-
! &nbsp; !! ''A'' !! ''B'' !! ''C'' !! ''D'' !! {{tmath|f(A, B, C, D)}}
|-
! scope="row" |  0 
| 0 || 0 || 0 || 0 || 0
|-
! scope="row" |  1 
| 0 || 0 || 0 || 1 || 0
|-
! scope="row" |  2 
| 0 || 0 || 1 || 0 || 0
|-
! scope="row" |  3 
| 0 || 0 || 1 || 1 || 0
|-
! scope="row" |  4 
| 0 || 1 || 0 || 0 || 0
|-
! scope="row" |  5 
| 0 || 1 || 0 || 1 || 0
|-
! scope="row" |  6 
| 0 || 1 || 1 || 0 || 1
|-
! scope="row" |  7 
| 0 || 1 || 1 || 1 || 0
|-
! scope="row" |  8 
| 1 || 0 || 0 || 0 || 1
|-
! scope="row" |  9 
| 1 || 0 || 0 || 1 || 1
|-
! scope="row" | 10 
| 1 || 0 || 1 || 0 || 1
|-
! scope="row" | 11 
| 1 || 0 || 1 || 1 || 1
|-
! scope="row" | 12 
| 1 || 1 || 0 || 0 || 1
|-
! scope="row" | 13 
| 1 || 1 || 0 || 1 || 1
|-
! scope="row" | 14 
| 1 || 1 || 1 || 0 || 1
|-
! scope="column" | 15 
| 1 || 1 || 1 || 1 || 0
|}

我们可以用两个不同的写法，及四个不同的布尔变量{{mvar|A}}, {{mvar|B}}, {{mvar|C}}, {{mvar|D}}和他们的相反值，来表示同一个尚未化简的[[布尔代数]]：

* <math>f(A, B, C, D) = \sum_{}m_i, i \in \{6, 8, 9, 10, 11, 12, 13, 14\}</math>这个<math>{}m_i</math>是卡诺图的最小项（即圈出来的值<math>i</math>在真值表上显示为1）。
* <math>f(A, B, C, D) = \prod_{}M_i, i \in \{0, 1, 2, 3, 4, 5, 7, 15\}</math> 这个 <math>M_i</math> 是卡诺图的最大项（即圈出来的值<math>i</math>在真值表上显示为0）。

{| class="wikitable" style="text-align: center"
|+ 某函數的卡諾圖（圈法1）
|-
! style="{{Table slash ltr}}" | 　　''A B''<br />''C D''　　
! 0 0 !! 0 1 !! 1 1 !! 1 0
|-
! 0　0
| 0 || 0 || {{CMain|1}}|| {{CMain|1}}
|-
! 0　1
| 0 || 0 || {{CMain|1}} || {{CMain|1}}
|-
! 1　1
| 0 || 0 || 0 || {{CRecurring|1}}
|-
! 1　0
| 0 || {{CMain|1}} || {{CMain|1}} || {{CRecurring|1}}

|}
{| class="wikitable" style="text-align: center"
|+ 某函數的卡諾圖（圈法2）
|-
! style="{{Table slash ltr}}" | 　　''A B''<br />''C D''　　
! 0 0 !! 0 1 !! 1 1 !! 1 0
|-
! 0　0
| 0 || 0 || {{CMain|1}}|| {{CRecurring|1}}
|-
! 0　1
| 0 || 0 || {{CMain|1}} || {{CRecurring|1}}
|-
! 1　1
| 0 || 0 || 0 || {{CRecurring|1}}
|-
! 1　0
| 0 || {{CMain|1}} || {{CMain|1}} || {{CRecurring|1}}

|}
按照上述卡诺图圈法（不限于上述两种），可知化简结果为AC'+AB'C+BCD'或ABC'+AB'+BCD'

== 参考文献 ==
=== 引註 ===
{{Reflist|refs=
<ref name="Stephen">{{Cite book |author=Stephen Brown, Zvonko Vranesic |title = Fundamentals of Digital Logic with Verilog Design |year=2002 |url=https://archive.org/details/fundamentalsofdi0000brow_t0c5 |publisher=McGraw-Hill Education |ISBN = 0-07-283878-7}}</ref>
}}

=== 来源 ===
; 期刊文章
* {{cite journal |last=Karnaugh |first=Maurice |authorlink = Maurice Karnaugh |title=The Map Method for Synthesis of Combinational Logic Circuits |journal=Transactions of [[American Institute of Electrical Engineers]] part I |volume=72 |issue=9 |pages = 593-599 |date = November 1953}}

{{-}}
{{数字电路}}

[[Category:数字电子|K]]
[[Category:布尔代数|K]]
[[Category:图表]]