カルノー図

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

カルノー図(カルノーず、英: Karnaugh map)は論理回路などにおいて論理式を簡単化するための表であり、その方法をカルノー図法という。よく似た概念にベイチ (Veitch) 図と呼ばれる図があり、変数と数字の書き方のみが異なる。

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

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

特に

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

といった論理積の項を論理和した形(積和標準形)の場合に使いやすい。

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

${\displaystyle {\begin{alignedat}{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{alignedat}}}${\displaystyle {\begin{alignedat}{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{alignedat}}}

3変数のカルノー図例

A\BC	00	01	11	10
0	1	1
1	1	1

3変数のベイチ図例

${\displaystyle A}${\displaystyle A}		${\displaystyle {\overline {A}}}${\displaystyle {\overline {A}}}
${\displaystyle B}${\displaystyle B}	1	1
${\displaystyle {\overline {B}}}${\displaystyle {\overline {B}}}	1	1
${\displaystyle {\overline {C}}}${\displaystyle {\overline {C}}}	${\displaystyle C}${\displaystyle C}		${\displaystyle {\overline {C}}}${\displaystyle {\overline {C}}}

---

${\displaystyle {\begin{alignedat}{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{alignedat}}}${\displaystyle {\begin{alignedat}{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{alignedat}}}

4変数のカルノー図例

AB\CD	00	01	11	10
00	1	1	1
01	1	1
11
10	1	1

4変数のベイチ図例

${\displaystyle A}${\displaystyle A}
${\displaystyle B}${\displaystyle B}	1
	1	${\displaystyle D}${\displaystyle D}
1	1		1	1
1
${\displaystyle C}${\displaystyle C}

---

${\displaystyle {\begin{alignedat}{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{alignedat}}}${\displaystyle {\begin{alignedat}{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{alignedat}}}

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

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

論理式

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

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

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

${\displaystyle A\cdot {B}\cdot {C}}${\displaystyle A\cdot {B}\cdot {C}} ,

${\displaystyle A\cdot C}${\displaystyle A\cdot C} ,

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

である。

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

${\displaystyle A\cdot B}${\displaystyle A\cdot B},

${\displaystyle A\cdot C}${\displaystyle A\cdot C}

である。

よって、

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

とわかる。

• 図1
  図1
• 図2
  図2

論理式

${\displaystyle 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}${\displaystyle 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)は、それぞれ

${\displaystyle B\cdot {\overline {C}}\cdot {\overline {D}}}${\displaystyle B\cdot {\overline {C}}\cdot {\overline {D}}},

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

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

${\displaystyle {\overline {A}}\cdot B}${\displaystyle {\overline {A}}\cdot B},

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

である。

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

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

${\displaystyle {\overline {A}}\cdot B}${\displaystyle {\overline {A}}\cdot B},

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

である。

よって、

${\displaystyle 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}${\displaystyle 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}

とわかる。

• 図3
  図3
• 図4
  図4

• ベン図
• クワイン・マクラスキー法(Quine–McCluskey Method)
• 真理値表

「https://ja.wikipedia.org/w/index.php?title=カルノー図&oldid=91224566」から取得

カテゴリ:

• デジタル回路
• 論理学
• ダイアグラム
• 数学に関する記事
• 数学のエポニム

隠しカテゴリ:

• 出典を必要とする記事/2018年4月
• すべてのスタブ記事
• 工学関連のスタブ