カルノー図

カルノー図の最新ニュースをまとめて検索！

カルノー図の例

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

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

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

特に

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

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

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

[編集] 図例

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

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

３変数のベイチ図例
	$A$		$\overline{A}$
$B$	1		1
$\overline{B}$	1		1
	$\overline{C}$	$C$		$\overline{C}$

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

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

４変数のベイチ図例
	$A$
$B$				1
$B$				1	$D$
	1	1	1	1	$D$
				1
		$C$

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

５変数の例
AB＼CDE	000	001	011	111	101	100
00	1	1		1	1	1
01			1	1
11			1	1
10	1	1			1	1

[編集] 例

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

[編集] 例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$