クワイン・マクラスキーアルゴリズム

{\displaystyle S=\{abc,a{\overline {b}}c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}} — 3変数アルゴリズムの探索グラフのハッセ図。例えば、部分集合が与えられた場合。 $S=\{abc,a{\overline {b}}c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}$ 最下層のノード（薄緑色）のうち、アルゴリズムは最小限のノードセットを計算します（ここでは： $\{{\overline {a}}b,c\}$ （濃い緑色）ちょうど $S$ 。

クワイン・マクラスキーアルゴリズム（QMC ）は、プライムインプリカント法または表計算法としても知られ、ブール関数の最小化に使用される方法で、1952 年にウィラード・V・クワインによって開発され^[¹^]^[²^] 、 1956 年にエドワード・J・マクラスキーによって拡張されました^[³^]。このアプローチの一般原理は、1878 年に論理学者ヒュー・マッコールによって既に実証されており^[⁴^]^[⁵^]^[⁶^]、1937 年にアーチー・ブレイクによって証明され^[⁷^]^[⁸^]^[⁹^]^[⁶^]、1954 年にエドワード・W・サムソンとバートン・E・ミルズによって再発見され^[¹⁰^]^[⁶^]、1955 年にレイモンド・J・ネルソンによって再発見されました^[¹¹^]^[⁶^]。また、1955年には、Paul W. AbrahamsとJohn G. Nordahl ^{[ 12 ]}、Albert A. MullinとWayne G. Kellner ^{[ 13 ]}^{[ 14 ]}^{[ 15 ]}^{[ 16 ]}が、この方法の10進数版を提案した。^{[ 17 ]}^{[ 14 ]}^{[ 15 ]}^{[ 16 ]}^{[ 18 ]}^{[ 19 ]}^{[ 20 ]}^{[ 21 ]}

クワイン・マクラスキーアルゴリズムは、機能的にはカルノー図法と同一ですが、表形式であるためコンピュータアルゴリズムでの使用効率が高く、またブールFの最小形式に到達したことを決定論的に確認する方法も提供します。

クワイン＝マクラスキーアルゴリズムは次のように動作します。

関数のすべての主項を求める。
それらの主インプリカントを主インプリカントチャートで使用して、関数の本質的な主インプリカントと、関数をカバーするために必要なその他の主インプリカントを見つけます。

複雑

4 変数を超える場合、カルノー図よりも実用的ではあるものの、クワイン-マクラスキーアルゴリズムは、解決する問題が NP 完全であるため、使用範囲が限られています。^{[ 22 ]}^{[ 23 ]}^{[ 24 ]}クワイン-マクラスキーアルゴリズムの実行時間は、変数の数に対して指数関数的に増加します。n個の変数を持つ関数の場合、プライムインプリカントの数は最大で次のようになります。 $\displaystyle 3^{n}/{\sqrt {n}}$ ^例えば、^{32個の変数の場合}^、^{534 × 10 12}を超える素因数が存在する可能性があります。多数の変数を持つ関数は、最適ではない可能性のあるヒューリスティック法で最小化する必要があります。1995 年当時、その事実上の標準はEspresso ヒューリスティックロジック最小化ツールでした。^{[ 26 ]}関数の自然なクラスの一つについて $f$ 、すべての主インプリカントを見つける正確な複雑さはよりよく理解されています。Milan Mossé、Harry Sha、およびLi-Yang Tanは、連言標準形の式のすべての主インプリカントを見つけるためのほぼ最適なアルゴリズムを発見しました。^{[ 27 ]}

アルゴリズムのステップ 2 は、集合被覆問題を解くことに相当します。^{[ 28 ]} このアルゴリズムのステップでは、この問題のNP 困難なインスタンスが発生する可能性があります。 ^{[ 29 ]}^{[ 30 ]}

例

入力

この例では、入力は4つの変数を持つブール関数です。 $f:\{0,1\}^{4}\to \{0,1\}$ これは次のように評価されます $1$ 値について $4,8,10,11,12$ そして $15$ 、未知の値に評価されます $9$ そして $14$ 、そして $0$ その他の場所では（これらの整数は入力用にバイナリ形式で解釈されます） $f$ （表記の簡潔さのため）。 $1$ これらは「最小項」と呼ばれます。このすべての情報を次のように記述してエンコードします。

f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,

この式は、最小項に対して出力関数 f が 1 になることを示しています。 $4,8,10,11,12$ そして $15$ （「m」項で示される）出力については気にしない $9$ そして $14$ 組み合わせ（「d」項で示される）。総和記号 $\sum$ これは、合計対象となるすべての項の論理和（論理OR、または論理和）を表します。

ステップ1：主インプリカントの発見

まず、関数を表として記述します（ここで「x」は「気にしない」を表します）。

この表から、関数が1になる最小項（無関係な項を除く）を合計するだけで、標準的な積和の式を簡単に作成できます。

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD。

これは最小値ではありません。そこで最適化するために、まず評価値が 1 になるすべての最小項を最小項テーブルに格納します。また、このテーブルには、最小項と組み合わせることができるように、不確定項 (括弧内の名前) も追加されます。

この時点で、隣接するグループの他の最小項と最小項を組み合わせ始めることができます。つまり、n 番目のグループの最小項を (n+1) 番目のグループと比較します。したがって、1 の数が 1 つだけの m4 最小項については、1 の数が 2 つある m9、m10、m12 と比較します。

2 つの項の差が 1 桁のみの場合、その桁はダッシュに置き換えられ、その桁は重要ではないことを示します。たとえば、1000とは1001と組み合わせることができ100-、これは、両方の最小項が最初の桁がで1、次の 2 桁がであることを意味します0。これ以上組み合わせることができない項には、アスタリスク ( * ) が付けられます。

サイズ 2 からサイズ 4 に変更する場合は、-3 番目のビット値として扱います。-まずを一致させます。項は積を表し、2 つの積項を組み合わせるには、同じ変数を持つ必要があります。一方の項では変数の 1 つが反転され、もう一方の項では反転されていない必要があります。残りの変数は一致する必要があります。したがって、2 つの項を一致させるには-、が揃い、他の桁のうち 1 つを除くすべてが同じである必要があります。たとえば、-110とは-100組み合わせてを得ることができます。-1-0同様に、-110とを組み合わせ-010てを得ることができます--10が、-110とは組み合わせる011-ことができません。は BCD' に対応し、は A'BC に対応します。BCD' + A'BC は積項と同等ではありません。--110011-

注：この例では、サイズ4のインプリカント表の項はこれ以上結合できません。一般に、このプロセスは2のべき乗のサイズ（サイズ8、16など）で、これ以上項を結合できなくなるまで続けられます。

ステップ2：プライムインプリカントチャート

これ以上項を組み合わせることはできないため、この時点で必須の主項インプリカント表を作成します。横には、先ほど生成された主項インプリカント（前のステップで「*」マークが付いているもの）を配置し、上には先に指定した最小項を配置します。不要な項は、入力として必要ではないため、このセクションでは省略し、上には配置しません。

本質的なプライムインプリカントを見つけるには、「✓」が1つだけ付いている列を探します。列に「✓」が1つだけ付いている場合、それは最小項が1つのプライムインプリカントでしかカバーできないことを意味します。このプライムインプリカントが本質的なプライムインプリカントです。

例えば、最初の列の最小項4には「✓」が1つしかありません。これは、m(4,12)が必須であることを意味します（そのため^「# 」でマークされています）。最小項15にも「✓」が1つしかないため、m(10,11,14,15)も必須です。これで、「✓」が1つあるすべての列がカバーされました。最小項m(4,12)とm(10,11,14,15)を含む行は、それらがカバーするすべての列とともに削除できます。

2 番目の主インプリカントは 3 番目と 4 番目で「カバー」でき、3 番目の主インプリカントは 2 番目と 1 番目で「カバー」できるため、どちらも必須ではありません。主インプリカントが必須である場合は、当然のことながら、最小化されたブール方程式にそれを含める必要があります。場合によっては、必須の主インプリカントがすべての最小項をカバーしていないため、チャート削減のための追加の手順を使用できます。最も単純な「追加の手順」は試行錯誤ですが、より体系的な方法はペトリック法です。この例では、必須の主インプリカントがすべての最小項を処理していないため、この場合、必須のインプリカントを 2 つの非必須のインプリカントのいずれかと組み合わせることで、1 つの方程式が得られます。

f _A,B,C,D = BC'D' + AB' + AC ^{[ 31 ]}

または

f _A,B,C,D = BC'D' + AD' + AC

これら2つの最終的な方程式は、元の冗長な方程式と機能的に同等である。

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'C'D + AB'CD' + AB'CD + ABC'D' + ABCD' + ABCD。

アルゴリズム

ステップ1：主インプリカントの発見

以下の擬似コードは、ブール関数の最小項のリストが与えられた場合に、主項を再帰的に計算します。これは、考えられるすべての最小項をマージし、マージ済みの最小項を除外していくことで実現されます。この処理は、これ以上最小項をマージできなくなるまで繰り返され、最終的に関数の主項が求められます。

// 最小項のリストから主項を計算します。 // 各最小項は「1001」、「1010」などの形式で、文字列で表現できます。 関数getPrimeImplicants(list minterms)は primeImplicants ← 空のリスト merges ← minterms の数と同じ長さの新しいブール配列を作成し、それぞれを false に設定します マージ数 ← 0 mergedMinterm、minterm1、minterm2 ← 空の文字列 i = 0からlength(minterms)まで繰り返す c = i + 1からlength(minterms)まで繰り返す minterm1 ← minterms[i] minterm2 ← minterms[c] // 2つの最小項をマージできるかどうかを確認します CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2)の場合、 mergedMinterm ← MergeMinterms(minterm1, minterm2) primeImplicants に mergedMinterm が含まれていない場合、 primeImplicants.Add(mergedMinterm) numberOfMerges ← numberOfMerges + 1 merges[i] ← true マージ[c] ← true // マージされていない最小項を、素項であるためフィルタリングします。また、重複も削除します。 j = 0からlength(minterms)まで繰り返す。もしmerges [j] == false かつ primeImplicants Does Not Contain minterms[j]ならば primeImplicants.Add(minterms[j]) // マージが行われていない場合は、すべての主インプリカントが見つかったので、戻ります。そうでない場合は、 // 最小項をマージし続ける。 numberOfmerges == 0の場合は primeImplicants を返し、そうでない場合は getPrimeImplicants(primeImplicants)を返す。

この例では、CheckDashesAlignおよびCheckMintermDifference関数は、2 つの最小項をマージできるかどうかを判断するために必要なチェックを実行します。関数は、MergeMinterms最小項をマージし、必要に応じてダッシュを追加します。以下のユーティリティ関数は、各最小項が文字列で表現されることを前提としています。

関数MergeMinterms(minterm1, minterm2)は mergedMinterm ← 空の文字列 i = 0からlength(minterm1)まで繰り返す //ビットが異なる場合は、それをダッシュに置き換えます。そうでない場合は、そのビットはマージされた最小項に残ります。 minterm [i] != minterm2[i]ならば mergedMinterm ← mergedMinterm + '-' それ以外 mergedMinterm ← mergedMinterm + minterm1[i] マージされたミニタームを返しますfunction CheckDashesAlign(minterm1, minterm2)は、 i = 0からlength(minterm1)まで実行されます。 // 一方の最小項にダッシュがあり、もう一方にない場合、最小項をマージすることはできません。 minterm1[i] != '-' && minterm2[i] == '-'の場合、 false を 返す。true を返す。 関数CheckMintermDifference(minterm1, minterm2)は // minterm1 と minterm2 は、現在見つかったすべての素インプリカントとマージされた素インプリカントを表す文字列です。 // 最小項。例として「01--」や「10-0」などがあります。 m1、m2 ← minterm1とminterm2の整数表現からハイフンを取り除き、0に置き換えます // ^ ここはビットごとの XOR です res ← m1 ^ m2 return res != 0 && (res & res - 1) == 0

ステップ2：プライムインプリカントチャート

以下の擬似コードは、2つのセクションに分けることができます。

主インプリカントを使用して主インプリカントチャートを作成する
主インプリカント表を読んで、本質的な主インプリカントを見つけます。

主インプリカントチャートの作成

主インプリカントチャートは、各キーが主インプリカントであり、対応する値が空の文字列である辞書で表現できます。この空の文字列は、この手順が完了するとバイナリ文字列を格納します。バイナリ文字列の各ビットは、主インプリカントチャート内の目盛りを表すために使用されます。主インプリカントチャートは、以下の手順で作成できます。

各キー（辞書の主インプリカント）を順に処理します。
主項の各ハイフンを\d文字コードに置き換えます。これにより、各最小項に対して一致するものを検索できる正規表現が作成されます。
各最小項を反復処理し、正規表現を最小項のバイナリ表現と比較します。一致するものがあれば、"1"辞書内の対応する文字列にを追加します。そうでない場合は、を追加します"0"。
すべての主インプリカントについてこの手順を繰り返し、完成した主インプリカント表を作成します。

上記のアルゴリズムを擬似コードで表すと次のようになります。

function CreatePrimeImplicantChart(list primeImplicants, list minterms) primeImplicantChart ← キーが文字列型で値が文字列型の新しい辞書 // 主項をキー、空文字列を値とする空のチャートを作成します。 i = 0からlength(primeImplicants)まで繰り返す // チャートに新しい主インプリカントを追加します。 primeImplicantChart.Add(primeImplicants[i], "") for i = 0 to length(primeImplicantChart.Keys) do primeImplicant ← primeImplicantChart.Keys[i] // "-" を "\d" に変換します。これを使用して、上の目盛りの行を検索できます。 regularExpression ← ConvertToRegularExpression(primeImplicant) j = 0からlength(minterms)まで繰り返す // 正規表現と最小項が一致する場合は 1 を追加し、そうでない場合は 0 を追加します。 regularExpression.matches(minterms [ j])ならば primeImplicantChart[primeImplicant] += "1" それ以外 primeImplicantChart[primeImplicant] += "0" // 主インプリカントチャートが完成したので、完成したチャートを返します。 プライムインプリカントチャートを返す

ユーティリティ関数はConvertToRegularExpression、主インプリカントを正規表現に変換し、インプリカントと最小項との一致をチェックするために使用されます。

function ConvertToRegularExpression(string primeImplicant) 正規表現 ← 新しい文字列 for i = 0 to length(primeImplicant) do if primeImplicant[i] == "-" then // リテラル文字「\d」を追加します。 regularExpression += @"\d" それ以外 regularExpression += primeImplicant[i] 正規表現を返す

本質的な主要含意を見つける

上記で定義した関数を使用するとCreatePrimeImplicantChart、辞書内の値を列ごとに反復処理するだけで、本質的な素インプリカントを見つけることができます"1"。が 1 つ見つかった場合、それは本質的な素インプリカントです。このプロセスは、以下の擬似コードで説明されています。

function getEssentialPrimeImplicants(Dictionary primeImplicantChart, list minterms) essentialPrimeImplicants ← 新しいリスト mintermCoverages ← ディクショナリ内のすべての値を含むリスト i = 0からlength(ticks)まで繰り返す mintermCoverage ← ticks[i] j = 0からlength(mintermCoverage)まで繰り返す。mintermCoverage [j] == "1"の場合、 essentialPrimeImplicants.Add(primeImplicantChart.Keys[i]) essentialPrimeImplicantsを返します

上記のアルゴリズムを使用すると、必須のプライムインプリカントを標準形式（つまり）に変換し、論理ORでインプリカントを分離することで、最小化されたブール式を見つけることができます。擬似コードは、必須のプライムインプリカントがブール式全体を網羅することを前提としています。-100 -> BC'D'

参考文献

↑クワイン、ウィラード・ヴァン・オーマン（1952年10月）。「真理関数の単純化の問題」。アメリカ数学月報。59（8）：521–531。doi ：10.2307/2308219。JSTOR 2308219。
↑クワイン、ウィラード・ヴァン・オーマン（ 1955年11月）。「真理関数を単純化する方法」。アメリカ数学月報。62（9）：627–631。doi：10.2307/2307285。hdl：10338.dmlcz /142789。JSTOR 2307285。
↑ McCluskey, Edward Joseph Jr. (1956 年 11 月). "ブール関数の最小化" . Bell System Technical Journal . 35 (6): 1417– 1444. doi : 10.1002/j.1538-7305.1956.tb03835.x . hdl : 10338.dmlcz/102933 . 2014 年 8 月 24 日取得.
↑ McColl, Hugh (1878-11-14). "The Calculus of Equivalent Statements (Third Paper)" . Proceedings of the London Mathematical Society . s1-10 (1): 16– 28. doi : 10.1112/plms/s1-10.1.16 .
↑ Ladd, Christine (1883). "論理の代数について". Charles Sanders Peirce (編). Studies in Logic . ボストン、アメリカ合衆国: Little, Brown & Company . pp. 17–71 . p. 23: [...] 式を最も単純な形に還元することが明白でない場合は、式の否定形を取り、それを還元し、その後肯定形に戻すことで容易になる場合があります。 [...]
1 2 3 4 Brown, Frank Markham (2010 年 11 月) [2010-10-27]. "McColl と最小化" . History and Philosophy of Logic . 31 (4). Taylor & Francis : 337– 348. doi : 10.1080/01445340.2010.517387 . ISSN 1464-5149 . S2CID 216590641 . 2020-04-15 のオリジナルからアーカイブ済み. 2020-04-15に取得.
↑ Blake, Archie (1938) [1937]. Canonical Expressions in Boolean Algebra (Dissertation) (Lithographed ed.). Chicago, Illinois, USA: University of Chicago Libraries . p. 36. p. 36: [...] この方法は、パースとその弟子たちに知られていた[...] これは、ジョンズ・ホプキンス大学のメンバーによる『Studies in Logic』、1883 年の数箇所で言及されている[...] （ii+60ページ）
↑ブレイク、アーチー (1932 年 11 月)。「ブール代数における標準表現」。アメリカ数学会報。論文要旨: 805。
↑ Blake, Archie (1938 年 6 月) 「ブール代数における標準式の訂正」 . The Journal of Symbolic Logic . 3 (2). Association for Symbolic Logic : 112– 113. doi : 10.2307/2267595 . ISSN 0022-4812 . JSTOR 2267595 . S2CID 5810863 .
↑サムソン、エドワード・ウォルター、ミルズ、バートン・E. (1954 年 4 月)。回路最小化: 新しいブール標準表現のための代数とアルゴリズム。米国マサチューセッツ州ベッドフォード:空軍ケンブリッジ研究センター。技術報告書 AFCRC TR 54-21。
↑ネルソン、レイモンド J. ( 1955 年 6月)。「最も単純な正規真理関数」。記号論理学ジャーナル。20 (2)。記号論理学協会: 105–108。doi : 10.2307 / 2266893。JSTOR 2266893。S2CID 32920372。（4ページ）
↑ 「ジョン・“ジャック”・G・ノーダール（1933年6月14日～2017年11月20日、享年84歳）の追悼ページへようこそ」。ジェリソン葬儀場および火葬サービス。 2020年5月5日にオリジナルからアーカイブ。2020年5月5日に取得。
↑ Mullin, Albert Alkins ; Kellner, Wayne G. (1958). イリノイ大学アーバナ校（米国）およびマサチューセッツ工科大学電気工学科（米国マサチューセッツ州）にて執筆。「ブール関数の剰余判定法」（PDF）。イリノイ州科学アカデミー紀要（教育覚書）。51 （3–4）。スプリングフィールド、イリノイ州、米国：14–19。S2CID 125171479。 2020年5月5日のオリジナルからアーカイブ（PDF）。2020年5月5日取得。 Wayback Machineに2020年8月17日にアーカイブされました（6ページ）（注：カルドウェルは著書の中で、これを1955年11月の教育メモとしています。しかし、マリンは別の著作で彼らの研究を1958年のものとしており、アブラハムズ／ノーダールの授業メモも1955年11月の日付となっているため、これはコピーミスである可能性があります。）
1 2コールドウェル、サミュエル・ホークス(1958年12月1日) [1958年2月]。「5.8. 10進数記号を用いた演算」。米国マサチューセッツ州ウォータータウンにて執筆。スイッチング回路と論理設計。第5版、1963年9月（初版）。米国ニューヨーク：ジョン・ワイリー・アンド・サンズ社。pp . 162–169。ISBN 0-47112969-0. LCCN 58-7896 . p. 166: [...] この論文は、マサチューセッツ工科大学でスイッチング回路を研究していた2人の学生の研究に基づいていることを記すのは喜ばしいことです。彼らは独自にこの方法について議論し、その後協力して授業メモを作成しました。PW AbrahamとJG Nordahl [...] {{cite book}}ISBN / 日付の不一致 (ヘルプ) (xviii+686ページ) (注：本書に収録されている十進法に関する最初の主要な解説は、「コールドウェルの十進表」という誤解を招く名称で呼ばれることがあります。)
1 2 Mullin, Albert Alkins (1960-03-15) [1959-09-19]. 米国イリノイ大学アーバナ校にて執筆。 Fisher, Harvey I.; Ekblaw, George E.; Green, FO; Jones, Reece; Kruidenier, Francis; McGregor, John; Silva, Paul; Thompson, Milton (編)。「初等整数論の2つの応用」（PDF）。イリノイ州科学アカデミー紀要。52 （3–4）。米国イリノイ州スプリングフィールド：102–103。 2020年5月5日のオリジナルからアーカイブ（PDF）。 2020年5月5日取得。Wayback Machineに2020年8月17日にアーカイブされました（2ページ）
1 2 McCluskey, Edward Joseph Jr. (1960 年 6 月) 「Albert A. Mullin と Wayne G. Kellner。ブール関数の剰余判定法。イリノイ州科学アカデミー紀要、第 51 巻、第 3 号および第 4 号、(1958 年)、pp. 14–19」。The Journal of Symbolic Logic (Review)。25 ( 2): 185。doi : 10.2307/2964263。JSTOR 2964263 。S2CID 123530443。p . 185 : [...] この論文の結果は、SH Caldwell によるより入手しやすい書籍に掲載されています [...]。この書籍では、著者は、10 進数の操作の開発についてMullin と Kellnerに功績を認めています。（1ページ）
↑ Abrahams, Paul William; Nordahl, John "Jack" G. (1955年11月).修正クワイン-マクラスキー還元法(講義メモ).マサチューセッツ工科大学電気工学科、マサチューセッツ州、アメリカ合衆国。{{cite book}}: CS1 maint: 場所が不明な出版社 (リンク) (4ページ) (注: 一部の資料では著者が「PW Abraham」と「IG Nordahl 」と記載されており、タイトルは「 Modified McCluskey–Quine Reduction Procedure」とも記載されています。 )
↑ Fielder, Daniel C. (1966 年 12 月). "教室でのブール関数の簡略化". IEEE Transactions on Education . 9 (4). IEEE : 202–205 . Bibcode : 1966ITEdu...9..202F . doi : 10.1109/TE.1966.4321989 . eISSN 1557-9638 . ISSN 0018-9359 .
↑ケメラー、ヴィルヘルム[ドイツ語] (1969 年 5 月)。「I.12. 理論: Minimierung Boolescher Funktionen」。ドイツのイエナで書かれました。フリューハウフでは、ハンス[ドイツ語で] ;ケメラー、ヴィルヘルム。シュレーダー、クルツ。ウィンクラー、ヘルムート (編)。Digitale Automaten – 理論、構造、技術、プログラム。 Elektronisches Rechnen und Regeln (ドイツ語)。 Vol. 5 (1版)。ベルリン、ドイツ: Akademie-Verlag GmbH。 pp. 98、103–104 。ライセンス番号。 202-100/416/69。注文番号4666 ES 20 K 3. p. 98: [...] 1955 年、デジタル化されたシュライブヴァイゼウムゲシュテルト ( PW エイブラハムと IG ノルダール、[コールドウェル])。 [...] （注：1973年版の第2版も存在する。）
↑ Holdsworth, Brian; Woods, Clive (2002). "3.17 ブール代数のクワイン-マクラスキー簡略化への10進法によるアプローチ" .デジタル論理設計（第4版）. Newnes Books / Elsevier Science . pp. 65–67 . ISBN 0-7506-4588-22020年4月19日に取得。{{cite book}}: CS1メンテナンス: ISBNエラーを無視しました (リンク) (519ページ)
↑ Majumder, Alak; Chowdhury, Barnali; Mondal, Abir J.; Jain, Kunj (2015-01-30) [2015-01-09]. Investigation on Quine McCluskey Method: A Decimal Manipulation Based Novel Approach for the Minimization of Boolean Function . 2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), Shillong, India (Conference paper). Department of Electronics & Communication, Engineering National Institute of Technology, Arunachal Pradesh Yupia, India. pp. 18– 22. doi : 10.1109/EDCAV.2015.7060531 . 2020-05-08のオリジナルからアーカイブ済み。2020-05-08 に取得。（注：本稿では、十進法に関する先行技術は引用していません。）（5ページ）
↑ Masek, William J. (1979). Some NP-complete set covering problems . 未発表。
↑ Czort, Sebastian Lukas Arne (1999).分離標準形式の最小化の複雑さ（修士論文）。オーフス大学。
↑ Umans, Christopher ; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (2006-06-05). "2レベル論理最小化の複雑性". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 25 (7): 1230– 1246. Bibcode : 2006ITCAD..25.1230U . doi : 10.1109/TCAD.2005.855944 . S2CID 10187481 .
↑ Chandra, Ashok K.; Markowsky, George (1978). "On the number of prime implicants" . Discrete Mathematics . 24 (1): 7– 11. doi : 10.1016/0012-365X(78)90168-1 .
↑ネルソン、ビクター P.、ネーグル、H. トロイ、キャロル、ビル D.、アーウィン、J. デイビッド(1995).デジタル論理回路解析と設計(第 2版).プレンティスホール. p. 234. ISBN 978-0-13463894-22014年8月26日に取得。
↑ Mossé, Milan; Sha, Harry; Tan, Li-Yang (2022). "充足可能性符号化補題の一般化とその応用" . DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 . Leibniz International Proceedings in Informatics (LIPIcs). 236 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 9:1–9:18. doi : 10.4230/LIPIcs.SAT.2022.9 . ISBN 978-3-95977-242-6。
↑ Feldman, Vitaly (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries" . Journal of Computer and System Sciences . 75 : 13–25 [13–14]. doi : 10.1016/j.jcss.2008.07.007 .
↑ Gimpel, James F. (1965). "任意に指定された素因数表を持つブール関数を生成する方法". IEEE Transactions on Computers . 14 : 485–488 . doi : 10.1109/PGEC.1965.264175 .
↑ポール、ヴォルフガング・ヤコブ[ドイツ語] (1974)。「ブールの最小多項式と超巨大な問題」。Acta Informatica (ドイツ語)。4 (4): 321–336。土井: 10.1007/BF00289615。S2CID 35973949。
↑ロジックフライデープログラム

さらに読む

カーティス、ハーバート・アレン（1962）。「第2.3章マクラスキー法」。『スイッチング回路設計への新しいアプローチ』。ベル研究所シリーズ（第1 版）。米国ニュージャージー州プリンストン：D.ヴァン・ノストランド社。90 ～ 160ページ。ISBN 0-44201794-4OCLC 1036797958 S2CID 57068910 ISBN 978-0-44201794-1. ark:/13960/t56d6st0q。{{cite book}}ISBN /日付の不一致（ヘルプ）（viii+635ページ）（注：本書は1969年にチン・ジによって再版されました。）
Coudert, Olivier (1994 年 10 月)。「2 レベル論理最小化: 概要」(PDF)。Integration , the VLSI Journal。17–2 ( 2 ): 97–140。doi : 10.1016/0167-9260(94)00007-7。ISSN 0167-9260。2020年5月10日にオリジナルからアーカイブ(PDF)。2020年 5 月 10日に取得。（47ページ）
Jadhav, Vitthal; Buchade, Amar (2012-03-08). "改良型Quine-McCluskey法". arXiv : 1203.2289 [ cs.OH ].（4ページ）
クレンショー、ジャック ( 2004-08-19 )。「クワイン＝マクラスキーについて」。embedded.com。2020-05-10のオリジナルからアーカイブ。2020-05-10に取得。
Tomaszewski, Sebastian P.; Celik, Ilgaz U.; Antoniou, George E. (2003 年 12 月) [2003-03-05, 2002-04-09]. "WWW ベースのブール関数最小化" (PDF) . International Journal of Applied Mathematics and Computer Science . 13 (4): 577– 584. 2020-05-10 のオリジナルからアーカイブ(PDF) . 2020-05-10に取得.^{[リンク削除済み]}（7ページ）
Duşa, Adrian (2008-10-01) [2007年9月]. 「ブール最小化問題への数学的アプローチ」. Quality & Quantity . 44 : 99–113 . doi : 10.1007/s11135-008-9183-x . S2CID 123042755.論文番号: 99 (2010). （22ページ）
Duşa, Adrian (2007). "Enhancing Quine-McCluskey" (PDF) .ブカレスト大学. 2020年5月12日のオリジナルからアーカイブ(PDF) . 2020年5月12日取得.（16ページ）（注：

外部リンク

チュートリアルクワイン＝マクラスキーとペトリックの方法に関するチュートリアル。
詳細な例については、次のリンクをご覧ください：http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm

[Quine_1952-1] クワイン、ウィラード・ヴァン・オーマン（1952年10月）。「真理関数の単純化の問題」。アメリカ数学月報。59（8）：521–531。doi ：10.2307/2308219。JSTOR 2308219。

[Quine_1955-2] クワイン、ウィラード・ヴァン・オーマン（ 1955年11月）。「真理関数を単純化する方法」。アメリカ数学月報。62（9）：627–631。doi：10.2307/2307285。hdl：10338.dmlcz /142789。JSTOR 2307285。

[McCluskey_1956-3] McCluskey, Edward Joseph Jr. (1956 年 11 月). "ブール関数の最小化" . Bell System Technical Journal . 35 (6): 1417– 1444. doi : 10.1002/j.1538-7305.1956.tb03835.x . hdl : 10338.dmlcz/102933 . 2014 年 8 月 24 日取得.

[McColl_1878-4] McColl, Hugh (1878-11-14). "The Calculus of Equivalent Statements (Third Paper)" . Proceedings of the London Mathematical Society . s1-10 (1): 16– 28. doi : 10.1112/plms/s1-10.1.16 .

[Ladd_1883-5] Ladd, Christine (1883). "論理の代数について". Charles Sanders Peirce (編). Studies in Logic . ボストン、アメリカ合衆国: Little, Brown & Company . pp. 17–71 . p. 23: [...] 式を最も単純な形に還元することが明白でない場合は、式の否定形を取り、それを還元し、その後肯定形に戻すことで容易になる場合があります。 [...]

[Brown_2010-6] 1 2 3 4 Brown, Frank Markham (2010 年 11 月) [2010-10-27]. "McColl と最小化" . History and Philosophy of Logic . 31 (4). Taylor & Francis : 337– 348. doi : 10.1080/01445340.2010.517387 . ISSN 1464-5149 . S2CID 216590641 . 2020-04-15 のオリジナルからアーカイブ済み. 2020-04-15に取得.

[Blake_1937-7] Blake, Archie (1938) [1937]. Canonical Expressions in Boolean Algebra (Dissertation) (Lithographed ed.). Chicago, Illinois, USA: University of Chicago Libraries . p. 36. p. 36: [...] この方法は、パースとその弟子たちに知られていた[...] これは、ジョンズ・ホプキンス大学のメンバーによる『Studies in Logic』、1883 年の数箇所で言及されている[...] （ii+60ページ）

[Blake_1932-8] ブレイク、アーチー (1932 年 11 月)。「ブール代数における標準表現」。アメリカ数学会報。論文要旨: 805。

[Blake_1938-9] Blake, Archie (1938 年 6 月) 「ブール代数における標準式の訂正」 . The Journal of Symbolic Logic . 3 (2). Association for Symbolic Logic : 112– 113. doi : 10.2307/2267595 . ISSN 0022-4812 . JSTOR 2267595 . S2CID 5810863 .

[Samson_1954-10] サムソン、エドワード・ウォルター、ミルズ、バートン・E. (1954 年 4 月)。回路最小化: 新しいブール標準表現のための代数とアルゴリズム。米国マサチューセッツ州ベッドフォード:空軍ケンブリッジ研究センター。技術報告書 AFCRC TR 54-21。

[Nelson_1955-11] ネルソン、レイモンド J. ( 1955 年 6月)。「最も単純な正規真理関数」。記号論理学ジャーナル。20 (2)。記号論理学協会: 105–108。doi : 10.2307 / 2266893。JSTOR 2266893。S2CID 32920372。（4ページ）

[Nordahl_2017-12] 「ジョン・“ジャック”・G・ノーダール（1933年6月14日～2017年11月20日、享年84歳）の追悼ページへようこそ」。ジェリソン葬儀場および火葬サービス。 2020年5月5日にオリジナルからアーカイブ。2020年5月5日に取得。

[Mullin_Kellner_1958-13] Mullin, Albert Alkins ; Kellner, Wayne G. (1958). イリノイ大学アーバナ校（米国）およびマサチューセッツ工科大学電気工学科（米国マサチューセッツ州）にて執筆。「ブール関数の剰余判定法」（PDF）。イリノイ州科学アカデミー紀要（教育覚書）。51 （3–4）。スプリングフィールド、イリノイ州、米国：14–19。S2CID 125171479。 2020年5月5日のオリジナルからアーカイブ（PDF）。2020年5月5日取得。 Wayback Machineに2020年8月17日にアーカイブされました（6ページ）（注：カルドウェルは著書の中で、これを1955年11月の教育メモとしています。しかし、マリンは別の著作で彼らの研究を1958年のものとしており、アブラハムズ／ノーダールの授業メモも1955年11月の日付となっているため、これはコピーミスである可能性があります。）

[Caldwell_1958-14] 1 2コールドウェル、サミュエル・ホークス(1958年12月1日) [1958年2月]。「5.8. 10進数記号を用いた演算」。米国マサチューセッツ州ウォータータウンにて執筆。スイッチング回路と論理設計。第5版、1963年9月（初版）。米国ニューヨーク：ジョン・ワイリー・アンド・サンズ社。pp . 162–169。ISBN 0-47112969-0. LCCN 58-7896 . p. 166: [...] この論文は、マサチューセッツ工科大学でスイッチング回路を研究していた2人の学生の研究に基づいていることを記すのは喜ばしいことです。彼らは独自にこの方法について議論し、その後協力して授業メモを作成しました。PW AbrahamとJG Nordahl [...] {{cite book}}ISBN / 日付の不一致 (ヘルプ) (xviii+686ページ) (注：本書に収録されている十進法に関する最初の主要な解説は、「コールドウェルの十進表」という誤解を招く名称で呼ばれることがあります。)

[Mullin_1959-15] 1 2 Mullin, Albert Alkins (1960-03-15) [1959-09-19]. 米国イリノイ大学アーバナ校にて執筆。 Fisher, Harvey I.; Ekblaw, George E.; Green, FO; Jones, Reece; Kruidenier, Francis; McGregor, John; Silva, Paul; Thompson, Milton (編)。「初等整数論の2つの応用」（PDF）。イリノイ州科学アカデミー紀要。52 （3–4）。米国イリノイ州スプリングフィールド：102–103。 2020年5月5日のオリジナルからアーカイブ（PDF）。 2020年5月5日取得。Wayback Machineに2020年8月17日にアーカイブされました（2ページ）

[McCluskey_1960-16] 1 2 McCluskey, Edward Joseph Jr. (1960 年 6 月) 「Albert A. Mullin と Wayne G. Kellner。ブール関数の剰余判定法。イリノイ州科学アカデミー紀要、第 51 巻、第 3 号および第 4 号、(1958 年)、pp. 14–19」。The Journal of Symbolic Logic (Review)。25 ( 2): 185。doi : 10.2307/2964263。JSTOR 2964263 。S2CID 123530443。p . 185 : [...] この論文の結果は、SH Caldwell によるより入手しやすい書籍に掲載されています [...]。この書籍では、著者は、10 進数の操作の開発についてMullin と Kellnerに功績を認めています。（1ページ）

[Abrahams_Nordahl_1955-17] Abrahams, Paul William; Nordahl, John "Jack" G. (1955年11月).修正クワイン-マクラスキー還元法(講義メモ).マサチューセッツ工科大学電気工学科、マサチューセッツ州、アメリカ合衆国。{{cite book}}: CS1 maint: 場所が不明な出版社 (リンク) (4ページ) (注: 一部の資料では著者が「PW Abraham」と「IG Nordahl 」と記載されており、タイトルは「 Modified McCluskey–Quine Reduction Procedure」とも記載されています。 )

[Fielder_1966-18] Fielder, Daniel C. (1966 年 12 月). "教室でのブール関数の簡略化". IEEE Transactions on Education . 9 (4). IEEE : 202–205 . Bibcode : 1966ITEdu...9..202F . doi : 10.1109/TE.1966.4321989 . eISSN 1557-9638 . ISSN 0018-9359 .

[Kämmerer_1969-19] ケメラー、ヴィルヘルム[ドイツ語] (1969 年 5 月)。「I.12. 理論: Minimierung Boolescher Funktionen」。ドイツのイエナで書かれました。フリューハウフでは、ハンス[ドイツ語で] ;ケメラー、ヴィルヘルム。シュレーダー、クルツ。ウィンクラー、ヘルムート (編)。Digitale Automaten – 理論、構造、技術、プログラム。 Elektronisches Rechnen und Regeln (ドイツ語)。 Vol. 5 (1版)。ベルリン、ドイツ: Akademie-Verlag GmbH。 pp. 98、103–104 。ライセンス番号。 202-100/416/69。注文番号4666 ES 20 K 3. p. 98: [...] 1955 年、デジタル化されたシュライブヴァイゼウムゲシュテルト ( PW エイブラハムと IG ノルダール、[コールドウェル])。 [...] （注：1973年版の第2版も存在する。）

[Holdsworth_2002-20] Holdsworth, Brian; Woods, Clive (2002). "3.17 ブール代数のクワイン-マクラスキー簡略化への10進法によるアプローチ" .デジタル論理設計（第4版）. Newnes Books / Elsevier Science . pp. 65–67 . ISBN 0-7506-4588-22020年4月19日に取得。{{cite book}}: CS1メンテナンス: ISBNエラーを無視しました (リンク) (519ページ)

[Majumder_2015-21] Majumder, Alak; Chowdhury, Barnali; Mondal, Abir J.; Jain, Kunj (2015-01-30) [2015-01-09]. Investigation on Quine McCluskey Method: A Decimal Manipulation Based Novel Approach for the Minimization of Boolean Function . 2015 International Conference on Electronic Design, Computer Networks & Automated Verification (EDCAV), Shillong, India (Conference paper). Department of Electronics & Communication, Engineering National Institute of Technology, Arunachal Pradesh Yupia, India. pp. 18– 22. doi : 10.1109/EDCAV.2015.7060531 . 2020-05-08のオリジナルからアーカイブ済み。2020-05-08 に取得。（注：本稿では、十進法に関する先行技術は引用していません。）（5ページ）

[Masek_1979-22] Masek, William J. (1979). Some NP-complete set covering problems . 未発表。

[Czort_1999-23] Czort, Sebastian Lukas Arne (1999).分離標準形式の最小化の複雑さ（修士論文）。オーフス大学。

[Umans_2006-24] Umans, Christopher ; Villa, Tiziano; Sangiovanni-Vincentelli, Alberto Luigi (2006-06-05). "2レベル論理最小化の複雑性". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 25 (7): 1230– 1246. Bibcode : 2006ITCAD..25.1230U . doi : 10.1109/TCAD.2005.855944 . S2CID 10187481 .

[ChandraMarkowsky_1978-25] Chandra, Ashok K.; Markowsky, George (1978). "On the number of prime implicants" . Discrete Mathematics . 24 (1): 7– 11. doi : 10.1016/0012-365X(78)90168-1 .

[Nelson_1995-26] ネルソン、ビクター P.、ネーグル、H. トロイ、キャロル、ビル D.、アーウィン、J. デイビッド(1995).デジタル論理回路解析と設計(第 2版).プレンティスホール. p. 234. ISBN 978-0-13463894-22014年8月26日に取得。

[27] Mossé, Milan; Sha, Harry; Tan, Li-Yang (2022). "充足可能性符号化補題の一般化とその応用" . DROPS-IDN/V2/Document/10.4230/LIPIcs.SAT.2022.9 . Leibniz International Proceedings in Informatics (LIPIcs). 236 . Schloss Dagstuhl – Leibniz-Zentrum für Informatik: 9:1–9:18. doi : 10.4230/LIPIcs.SAT.2022.9 . ISBN 978-3-95977-242-6。

[Feldman_2009-28] Feldman, Vitaly (2009). "Hardness of Approximate Two-Level Logic Minimization and PAC Learning with Membership Queries" . Journal of Computer and System Sciences . 75 : 13–25 [13–14]. doi : 10.1016/j.jcss.2008.07.007 .

[Gimpel_1965-29] Gimpel, James F. (1965). "任意に指定された素因数表を持つブール関数を生成する方法". IEEE Transactions on Computers . 14 : 485–488 . doi : 10.1109/PGEC.1965.264175 .

[Paul_1974-30] ポール、ヴォルフガング・ヤコブ[ドイツ語] (1974)。「ブールの最小多項式と超巨大な問題」。Acta Informatica (ドイツ語)。4 (4): 321–336。土井: 10.1007/BF00289615。S2CID 35973949。

[Logic_Friday-31] ロジックフライデープログラム

[

[

[

[

[

[

[

[

[

[

[

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

例えば

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

クワイン・マクラスキーアルゴリズム

複雑

例

入力

ステップ1：主インプリカントの発見

ステップ2：プライムインプリカントチャート

アルゴリズム

ステップ1：主インプリカントの発見

ステップ2：プライムインプリカントチャート

主インプリカントチャートの作成

本質的な主要含意を見つける

関連項目

参考文献

さらに読む

外部リンク

関連するトピック

Hasse diagram

ブール関数

最小化

ウィラード・V・クワイン