カルノー図
カルノー図（カルノーず、Karnaugh map）は論理回路などにおいて論理式を簡単化するための表であり、その方法をカルノー図法という。
カルノー図は1950年代にベル研究所のモーリス・カルノー(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>
| A＼BC | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 1 | ||
| 1 | 1 | 1 |
| <math>A</math> | <math>\overline{A}</math> | |||
|---|---|---|---|---|
| <math>B</math> | 1 | 1 | ||
| <math>\overline{B}</math> | 1 | 1 | ||
| <math>\overline{C}</math> | <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>
| AB＼CD | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 00 | 1 | 1 | 1 | |
| 01 | 1 | 1 | ||
| 11 | ||||
| 10 | 1 | 1 |
| <math>A</math> | |||||
|---|---|---|---|---|---|
| <math>B</math> | 1 | ||||
| 1 | <math>D</math> | ||||
| 1 | 1 | 1 | 1 | ||
| 1 | |||||
| <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>
| AB＼CDE | 000 | 001 | 011 | 010 | 110 | 111 | 101 | 100 |
|---|---|---|---|---|---|---|---|---|
| 00 | 1 | 1 | 1 | 1 | 1 | |||
| 01 | 1 | 1 | ||||||
| 11 | 1 | 1 | ||||||
| 10 | 1 | 1 | 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>
とわかる。
- Karnaugh1-2.png
図1
- Karnaugh1-3.png
図2
例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> とわかる。
- Karnaugh2-2.png
図3
- Karnaugh2-3.png
図4
関連項目
- ベン図
- クワイン・マクラスキー法(Quine-McCluskey Method)
- 真理値表
