クワイン・マクラスキー法 オンライン計算ツール

論理式を入力すると、クワイン・マクラスキー法を使って最小積和形（SOP: Sum of Products）に簡単化するオンライン計算ツールです。 授業の確認・手計算の答え合わせ・論理回路実装の検証などに使えます。

#1
$$A \cdot \overline{B} + \overline{A} \cdot C + B \cdot \overline{C}$$
#2
$$\overline{A} \cdot B + A \cdot \overline{C} + \overline{B} \cdot C$$
真理値表ツールを開く同値判定ツールを開く回路図ツールを開く

要望やバグ報告はお問い合わせフォームからどうぞ。

このツールでできること

AND・OR・NOT・XOR を含む論理式を入力すると、内部で等価な積和形に変換し、クワイン・マクラスキー法で最小積和形に簡単化します。 入力には複数の演算子記法を使えます。

内部では、主項（prime implicant）の列挙・必須主項（essential prime implicant）の選択・ペトリック法（Petrick's method）による残りの最小項をカバーする主項の組み合わせ選び、という手順を自動で行っています。

使い方

入力欄に論理式を書いて「計算」ボタンを押すだけです。

結果は数式として表示されます。複数の最簡形がある場合はすべて表示します。

エラーになりやすいケースとしては、以下のようなものがあります。

  • 括弧が対応していない（例: (A+B）
  • 変数名に予約語（AND, OR, NOT, XOR）と混同しやすい文字を使っている
  • 演算子を連続して書いている（例: A++B）

入力できる論理式の書き方

記法はかなり柔軟に認識します。以下はすべて同じ論理式の例です。

(~A * B) + (C ^ D)
(A' & B) | (C XOR D)
(!A * B) + (C ^ D)
(NOT A AND B) OR (C XOR D)

演算子の優先順位は、NOT（および '） > AND（および変数の連結） > XOR > OR です。 迷う場合は括弧を使ってください。

ANDとして認識される文字

AND and & && * . × ∧ ⋂ ⋅

変数を直接つなげてもANDとして認識されます。例えば AB は A*B と同じです。AND、OR、NOT、XOR は演算子として扱われるため、変数名には使えません。

ORとして認識される文字

OR or | || + ∨ ⋃

NOTとして認識される文字

（前方）NOT not ¬ ~ ! -　（後方）'

XORとして認識される文字

XOR xor ^

出力結果の読み方

複数の式が表示される場合は、どれも同等に正しい最小積和形です。 このツールでは、積項数が最も少なく、同数の場合はリテラル数が最も少ない形を最簡形として扱います。 同じコストの最簡形が複数ある場合は、すべて表示します。

計算例

入力欄の初期値 A ^ B + A ^ C は、(A XOR B) OR (A XOR C) という意味です。 XOR は内部で等価な積和形に展開されてから簡単化されます。

シンプルな例として A*B + ~A*B を試してみてください。 これは「AかつB」または「AでなくかつB」で、AがどちらであってもBが真なら全体が真になるため、 最簡形は B だけになります。

もう少し複雑な例として A*B*C + A*B*~C + A*~B*C + A*~B*~C を試してみてください。 B・Cの組み合わせがすべて含まれているため、Aだけに簡単化されます。

クワイン・マクラスキー法とは

クワイン・マクラスキー法（Quine–McCluskey algorithm）は、ブール関数を積和形で簡単化するための表形式のアルゴリズムです。 日本語ではQM法とも略されます。 ウィラード・ヴァン・オーマン・クワインの研究をもとに、エドワード・J・マクラスキーが論理回路設計向けに整理・発展させた方法として知られています。

手順は大きく3段階です。

  • 主項の列挙：積和形の各項を2進数（最小項、minterm）で表し、1の個数でグループ分けする。 隣接グループ間で1ビットだけ異なる項をまとめ（その変数を消去）、まとめられなくなるまで繰り返す。 最終的に残った項が主項（prime implicant）。
  • 必須主項の選択：主項表を作り、特定のmintermを唯一カバーする主項を必須主項（essential prime implicant）とする。 必須主項は必ず最終結果に含まれる。
  • ペトリック法による残余の処理：必須主項でカバーされない最小項が残った場合、 ペトリック法で最小の主項の組み合わせを求めて補う。

カルノー図との違い

論理式の簡単化手法としてはカルノー図（Karnaugh map）が有名ですが、用途が少し異なります。

  • カルノー図：少数変数の論理式向け。マス目を視覚的にグループ化するため、手計算で直感的に分かりやすい。
  • クワイン・マクラスキー法：手順が機械的で、カルノー図よりコンピュータ実装に向いている。ただし、最小形を確実に探すために多くの候補を調べるので、変数数や最小項数が増えると計算時間・メモリ使用量が急増する。

授業でカルノー図を習った場合、答え合わせにこのツールを使えます。 変数が5個以上になるとカルノー図では手計算しにくくなるため、QM法のような機械的な手順が役に立ちます。

現在の制限事項

現在このツールでできることとできないことを整理します。

  • ✓ AND・OR・NOT・XOR を含む論理式を、最小積和形へ簡単化
  • ✓ 最簡形が複数ある場合の全列挙
  • ✗ ドントケア条件（X項、don't care term）の指定には未対応
  • ✓ テキスト形式・TeX形式・Word数式形式でのコピー

関連ツール