カルノー図

出典: フリー百科事典『ウィキペディア(Wikipedia)』
2013年3月22日 (金) 02:13時点におけるAddbot (トーク)による版 (ボット: 言語間リンク 26 件をウィキデータ上の d:q461528 に転記)
(差分) ← 古い版 | 最新版 (差分) | 新しい版 → (差分)
移動先: 案内検索

カルノー図(カルノーず、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>

3変数のカルノー図例
A\BC 00 01 11 10
0 1 1
1 1 1


3変数のベイチ図例
<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>

4変数のカルノー図例
AB\CD 00 01 11 10
00 1 1 1
01 1 1
11
10 1 1


4変数のベイチ図例
<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>

5変数の例
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>

とわかる。

例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> とわかる。

関連項目