カルノー図ソルバー (K-Map)

カルノー図でブール関数を簡略化する

カルノー図（K-Map）は、1つの変数だけが異なる入力条件を隣り合わせに配置し、ブール関数を視覚的に整理する方法です。

このsolverは2、3、4、5変数に対応しています。K-Mapだけでなく、真理値表、論理式、最小項、最大項から入力することもできます。

どの入力方法も同じ関数を表しています。1か所を変更すると、ほかの表示も同じ内容に更新されます。

0、1、Xの意味

各セルには次の値を設定できます。

• 1 — その入力条件で関数が真。
• 0 — その入力条件で関数が偽。
• X — 出力を固定する必要がない条件。

Xはドントケア条件です。より大きなグループを作って式を簡単にできる場合は利用できますが、必ず使う必要はありません。

真理値表からK-Mapへ

真理値表は、すべての入力組み合わせとそれぞれの出力を一覧で示します。

K-Mapも同じ情報を使いますが、セルはGray code順に配置されます。

そのため、隣接するセルでは1つの変数だけが変化します。

たとえば:

A'B'

A'B

では、変化しているのはBだけです。

この2つは:

A'

に簡略化できます。

グループ内で変化する変数は、簡略化後の項から取り除くことができます。

最小項・最大項・論理式から入力する

問題に最小項の番号が与えられている場合、K-Mapのセルを1つずつ入力する必要はありません。

たとえば:

Σm(1,3,5,7)

は、出力が1になる最小項を示します。

一方:

ΠM(0,2,4,6)

は、出力が0になる最大項を示します。

論理式を直接入力することもできます。

Solverは式を評価し、対応する真理値表、K-Map、最小項、最大項を生成します。

これにより、同じブール関数を複数の表現で比較できます。

K-Mapのグループ化

有効なグループのセル数は2のべき乗になります。

1, 2, 4, 8, 16

通常、大きな有効グループほど、結果に残るリテラル数を減らせます。

カルノー図では反対側の端も隣接しています。

左端と右端、上端と下端は論理的には隣り合っています。

そのため、4つの角のセルが1つのグループになることもあります。

必要であればグループ同士を重ねることもできます。

Solverでは使用されたグループがK-Map上に表示されるため、最終式との対応を確認しやすくなります。

SOPとPOS

SOP (Sum of Products)では、主に出力が1になるセルを使って簡略化します。

例:

A'B + BC

POS (Product of Sums)では、出力が0になるセルを基準にします。

例:

(A + B')(B + C)

SOPが常に短いわけではありません。

関数によってはPOSのほうが項やリテラルを少なくできる場合があります。

問題で形式が指定されていなければ、両方を比較できます。

Quine-McCluskeyとPetrick's Method

小さなK-Mapでは、適切なグループを目で見つけられることが多くあります。

しかし4変数や5変数では、複数の有効な組み合わせが存在する場合があります。

SolverはQuine-McCluskeyを使い、implicantを体系的に調べます。

これ以上大きくできないimplicantがprime implicantです。

その中には、ほかのprime implicantではカバーできない必要な最小項を含むものがあります。

その後も複数のカバー候補が残る場合は、Petrick's Methodで残りの組み合わせを評価します。

これは、図だけを見ても最適なグループがすぐに判断できない関数で特に役立ちます。

2～5変数のカルノー図

2変数K-Mapには4セルがあります。

3変数では8セルになり、反対側の端も隣接していることが分かりやすくなります。

4変数カルノー図は16セルで、デジタル論理の問題でよく使われます。

5変数では入力組み合わせが32通りになります。ドントケアや複数のprime implicantがあると、手作業での確認はより複雑になります。

Solverはどのサイズでも、K-Map、真理値表、論理式、最小項、最大項を同じ関数として同期します。

論理回路とPDF出力

簡略化された結果は、式だけでなく論理回路としても表示できます。

これにより、SOPまたはPOSの結果がAND、OR、NOTゲートにどう対応するかを確認できます。

結果には項数、リテラル数、ゲート数などの情報も表示できます。

解答を残しておきたい場合は、K-Map、グループ、手順、回路図を含むPDFとして出力できます。