カルノー図

出典: フリー百科事典『ウィキペディア（Wikipedia）』

カルノー図（カルノーず、Karnaugh map）は論理回路などにおいて論理式を簡単化するための表であり、その方法をカルノー図法という。

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

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

特に

$A\cdot B\cdot \overline{C}+A\cdot B\cdot C$

といった論理積の項を論理和した形（積和形）の場合に使いやすい。

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

[編集] 例

カルノー図で論理式を簡単にする例をしめす。

[編集] 例1

論理式

$A\cdot B\cdot \overline{C}+A\cdot B\cdot C+A\cdot C$

をカルノー図で簡単にすることを考える。

カルノー図で、この論理式が真となる部分に「1」を記入すると「図1」のようになる。「図1」で(1)(2)(3)は、それぞれ

$A\cdot B\cdot C$ ,

$A\cdot C$ ,

$A\cdot B\cdot \overline{C}$

である。

「図1」で論理式が真となる部分（「1」が記入されている部分）を、まとめると「図2」のようになる。「図2」で(1)(2)は、それぞれ

$A\cdot B$ ,

$A\cdot C$

である。

よって、

$A\cdot B\cdot \overline{C}+A\cdot B\cdot C+A\cdot C=A\cdot B+A\cdot C$

とわかる。

図1

図2

[編集] 例2

論理式

$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$

をカルノー図で簡単にすることを考える。

カルノー図で、この論理式が真となる部分に「1」を記入すると「図3」のようになる。「図3」で(1)(2)(3)(4)(5)は、それぞれ

$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$

である。

「図3」で論理式が真となる部分（「1」が記入されている部分）を、まとめると「図4」のようになる。「図4」で(1)(2)(3)は、それぞれ

$A\cdot\overline{C}\cdot\overline{D}$ ,

$\overline{A}\cdot B$ ,

$\overline{A}\cdot C$ ,

である。

よって、

$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$