カルノー図のソースを表示

{{出典の明記|date=2018年4月}}
[[ファイル:K-map 6,8,9,10,11,12,13,14 anti-race.svg|thumb|カルノー図の例]]
'''カルノー図'''（カルノーず、{{lang-en-short|Karnaugh map}}）は[[論理回路]]などにおいて[[ブール関数|論理式]]を簡単化するための表であり、その方法を'''カルノー図法'''という。よく似た概念にベイチ ({{en|Veitch}}) 図と呼ばれる図があり、変数と数字の書き方のみが異なる。

== 概要 ==
カルノー図は[[1950年代]]に[[ベル研究所]]の[[モーリス・カルノー]]([[:en:Maurice Karnaugh|Maurice Karnaugh]])によって発明された。

論理式を簡略化することにより、[[回路]]に使う[[素子]]を減らすなどのメリットがある。また、[[ブール代数]]の公式などを使って論理式を簡略化するよりも比較的楽にできる場合が多い。これは[[ハミング距離]]が1となるように図が組まれており（図の入力欄の隣同士の真偽値が1つだけ違うように）、感覚的、視覚的な方式で簡略化ができるためである。この入力欄の順序は[[グレイコード]]を生成するアルゴリズムで作成できる。

特に
:<math>A\cdot B\cdot \overline{C}+A\cdot B\cdot C</math>
といった論理積の項を論理和した形（[[選言標準形|積和標準形]]）の場合に使いやすい。

入力を1次元につき2つまでとすれば立体的にカルノー図を考えることで(人間の次元認識能力の見地から)実質6入力まで対応できる。しかし、実際は平面的に考えることが多く、その場合は縦横各2次元の4入力までである。それ以上の入力にはカルノー図は適していない。[[ベン図]]やベイチ図、カルノー図などの図で考える手法では見落とす場合もあるため、[[クワイン・マクラスキー法]]などの機械的な方法がより確実である。

==図例==
<math>
\begin{alignat}{2}
f & = \overline{A} \cdot \overline{B} \cdot C + \overline{A} \cdot B \cdot C + A \cdot \overline{B} \cdot \overline{C} + A \cdot B \cdot \overline{C} \\
 & = \overline{A} \cdot C + A \cdot \overline{C} \\
\end{alignat}
</math>
{| class="wikitable" style="text-align:center; width: 40%"
|+ style="vertical-align: bottom;" | 3変数のカルノー図例
! A＼BC !! 00 !! style="border-right:2px solid #000;" | 01 !! 11 !! 10
|- style="border-bottom:2px solid #000;"
! 0
| || style="border-right:2px solid #000;" | 1 || 1 || 
|-
! 1
| 1 || style="border-right:2px solid #000;" | || || 1
|}



{| class="wikitable" style="text-align: center; width: 40%"
|+ style="vertical-align: bottom;" | 3変数のベイチ図例
! !! colspan="2" | <math>A</math> !! colspan="2" | <math>\overline{A}</math>
|-
! <math>B</math>
| 1 || || 1 || 
|-
! <math>\overline{B}</math>
| 1 || || 1 || 
|-
! !! <math>\overline{C}</math> !! colspan="2" | <math>C</math> !! <math>\overline{C}</math>
|}


----


<math>
\begin{alignat}{2}
f & = \overline{A} \cdot \overline{B} \cdot \overline{C} + \overline{A} \cdot B \cdot \overline{C} + \overline{B} \cdot \overline{C} \cdot D + \overline{B} \cdot C \cdot D \\
 & = \overline{A} \cdot \overline{C} + \overline{B} \cdot D \\
\end{alignat}
</math>
{| class="wikitable" style="text-align:center; width: 40%"
|+ style="vertical-align: bottom;" | 4変数のカルノー図例
! AB＼CD !! 00 !! 01 !! 11 !! 10
|-
! 00
| 1 || 1 || 1 || 
|-
! 01
| 1 || 1 || ||
|-
! 11
| || || ||
|-
! 10
| || 1 || 1 ||
|}



{| class="wikitable" style="text-align: center; width: 40%"
|+ style="vertical-align: bottom;" | 4変数のベイチ図例
! !! colspan="2" | <math>A</math> !! colspan="2" | !!
|-
! rowspan="2" | <math>B</math>
| || || || 1
!
|-
| || || || 1
! rowspan="2" | <math>D</math>
|-
! rowspan="2" | 
| 1 || 1 || 1 || 1
|-
| || || || 1
!
|-
! !! !! colspan="2" | <math>C</math> !! !!
|}


----


<math>
\begin{alignat}{2}
f & = \overline{B} \cdot \overline{C} \cdot \overline{D} + \overline{B} \cdot C \cdot \overline{D} + \overline{A} \cdot B \cdot D \cdot E + A \cdot B \cdot D \cdot E + \overline{A} \cdot \overline{B} \cdot C \cdot E \\
 & = \overline{B} \cdot \overline{D} + B \cdot D \cdot E + 
\begin{cases}
\overline{A} \cdot \overline{B} \cdot C \cdot E \\
\overline{A} \cdot C \cdot D \cdot E
\end{cases}
\end{alignat}
</math>
{| class="wikitable" style="text-align:center; width: 40%"
|+ style="vertical-align: bottom;" | 5変数の例
! AB＼CDE !! 000 !! 001 !! 011 !! style="border-right:2px solid #000" | 010 !! 110 !! 111 !! 101 !! 100
|-
! 00
| 1 || 1 || || style="border-right:2px solid #000" | || || 1 || 1 || 1
|-
! 01
| || || 1 || style="border-right:2px solid #000" | || || 1 || ||
|-
! 11
| || || 1 || style="border-right:2px solid #000" | || || 1 || ||
|-
! 10
| 1 || 1 || || style="border-right:2px solid #000" | || || || 1 || 1
|}

==例==
カルノー図で論理式を簡単にする例をしめす。
===例1===
論理式
:<math>A\cdot B\cdot \overline{C}+A\cdot B\cdot C+A\cdot C</math>
をカルノー図で簡単にすることを考える。

カルノー図で、この論理式が真となる部分に「1」を記入すると「図1」のようになる。「図1」で(1)(2)(3)は、それぞれ
: <math>A \cdot{B} \cdot{C}</math> ,
: <math>A \cdot C</math> ,
: <math>A \cdot B \cdot \overline{C}</math>
である。

「図1」で論理式が真となる部分（「1」が記入されている部分）を、まとめると「図2」のようになる。「図2」で(1)(2)は、それぞれ
:<math>A\cdot B</math>,
:<math>A\cdot C</math>
である。

よって、
:<math>A\cdot B\cdot \overline{C}+A\cdot B\cdot C+A\cdot C=A\cdot B+A\cdot C</math>
とわかる。
<gallery>
ファイル:Karnaugh1-2.png|図1
ファイル:Karnaugh1-3.png|図2
</gallery>

===例2===
論理式
:<math>B\cdot\overline{C}\cdot \overline{D} + A\cdot \overline{B}\cdot\overline{C}\cdot\overline{D} + \overline{A}\cdot B\cdot\overline{C} + \overline{A}\cdot B + \overline{A}\cdot\overline{B}\cdot C</math>
をカルノー図で簡単にすることを考える。

カルノー図で、この論理式が真となる部分に「1」を記入すると「図3」のようになる。「図3」で(1)(2)(3)(4)(5)は、それぞれ
:<math>B\cdot\overline{C}\cdot \overline{D}</math>,
:<math>A\cdot\overline{B}\cdot\overline{C}\cdot\overline{D}</math>,
:<math>\overline{A}\cdot B\cdot\overline{C}</math>,
:<math>\overline{A}\cdot B</math>,
:<math>\overline{A}\cdot\overline{B}\cdot C</math>
である。

「図3」で論理式が真となる部分（「1」が記入されている部分）を、まとめると「図4」のようになる。「図4」で(1)(2)(3)は、それぞれ
:<math>A\cdot\overline{C}\cdot\overline{D}</math>,
:<math>\overline{A}\cdot B</math>,
:<math>\overline{A}\cdot C</math>,
である。

よって、
:<math>B\cdot\overline{C}\cdot \overline{D} + A\cdot \overline{B}\cdot\overline{C}\cdot\overline{D} + \overline{A}\cdot B\cdot\overline{C} + \overline{A}\cdot B + \overline{A}\cdot\overline{B}\cdot C
=A\cdot\overline{C}\cdot\overline{D} + \overline{A}\cdot B + \overline{A}\cdot C</math>
とわかる。
<gallery>
ファイル:Karnaugh2-2.png|図3
ファイル:Karnaugh2-3.png|図4
</gallery>

== 関連項目 ==
* [[ベン図]]
* [[クワイン・マクラスキー法]](Quine–McCluskey Method)
* [[真理値表]]

{{tech-stub}}
{{デフォルトソート:かるのおす}}
[[Category:デジタル回路]]
[[Category:論理学]]
[[Category:ダイアグラム]]
[[Category:数学に関する記事]]
[[Category:数学のエポニム]]