情報理論 - カルノー図

概要

カルノー図は、行・列それぞれの論理変数の組合せの結果が真となる場合に1、偽となる場合に0を該当セルに記述することにより、論理式を図で表す方法である。

1950年代にモーリス・カルノーによって考案された論理式の簡単化手法である。
ブール代数を視覚的に表現して、複雑な論理回路を最適化するのに非常に効果的なツールとして使用されている。

カルノー図は2次元の表形式で表現され、各セルは特定の入力変数の組み合わせに対応する。
隣接するセルは常にハミング距離が1となるように配置されており、これにより論理式の簡略化が容易になる。

論理式の簡略化は、1が記入されたセルを可能な限り大きなグループにまとめることで行う。
各グループから共通項を抽出して、それらの論理和を取ることにより最終的な簡略化された論理式が得られる。

グループ化

グループ化では、以下に示す3つのルールに従って行う。

• グループ化する全てのセルの値は、1であること。
• グループ化するセルの数は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle 2^n} であること。
• カルノー図の上下の端および左右の端は連続していると考える。

例えば、下図のようなカルノー図のグループ化を行う場合、全ての1を2つのグループで囲むことができる。

カルノー図

AB / CD	00	01	11	10
00	1	0	0	1
01	0	1	1	0
11	0	1	1	0
10	0	0	0	0

グループ化したカルノー図

AB / CD	00	01	11	10
00	1	0	0	1
01	0	1	1	0
11	0	1	1	0
10	0	0	0	0

上表のカルノー図において、赤枠は左端と右端の1を含むグループ ( ${\bar {A}}BC{\bar {D}}$ )、青枠は4つの1を含むグループ ( $BD$ ) を示している。

共通項の取り出し

次にグループごとに共通項を取り出して、その論理積を作る。

• 赤枠で囲ったグループ

  構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} \bar{B} \bar{C} \bar{D}} と 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} \bar{B} C \bar{D}} である。

  したがって、共通項は 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} \bar{B} \bar{D}} 、論理積は 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} \cdot \bar{B} \cdot \bar{D}} となる。

• 青い枠で囲ったグループ

  構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} B \bar{C} D, \quad \bar{A} B C D, \quad A B \bar{C} D, \quad A B C D} である。

  共通項は 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B D} 、論理積は 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot D} になる。

最後に、グループごとに生成した論理積同士の論理和をとることにより、等価な論理式が完成する。

そのため、赤枠のグループの論理積である 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} \cdot \bar{B} \cdot \bar{D}} と 青枠のグループの論理積である 構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle B \cdot D} の論理和をとる。
したがって、論理式は、構文解析に失敗 (SVG (ブラウザーのプラグインで MathML を有効にできます): サーバー「https://wikimedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \bar{A} \cdot \bar{B} \cdot \bar{D} + B \cdot D} となる。