カルノー図

ウィキペディア

カルノー図

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/30 07:32 UTC 版)

カルノー図の例

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

概要

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

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

特に

$A\cdot B\cdot {\overline {C}}+A\cdot B\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$

図3

図4

関連項目

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