コンテンツにスキップ
Wikipedia

「クワイン・マクラスキー法」の版間の差分

出典: フリー百科事典『ウィキペディア(Wikipedia)』
削除された内容 追加された内容
→‎例: 誤って削除した物を戻した
タグ: モバイル編集 モバイルウェブ編集
編集の要約なし
タグ: モバイル編集 モバイルウェブ編集
9行目: 9行目:
クワイン・マクラスキー方法
クワイン・マクラスキー方法
== 例 ==
=== 主項を求める ===
以下の[[真理値表]]で表されるブール関数を簡単化する。
{| class="wikitable"
|-
! !! A !! B !! C !! D !! !! f
|-
| m<sub>0</sub> || 0 || 0 || 0 || 0 || || 0
|-
| m<sub>1</sub> || 0 || 0 || 0 || 1 || || 0
|-
| m<sub>2</sub> || 0 || 0 || 1 || 0 || || 0
|-
| m<sub>3</sub> || 0 || 0 || 1 || 1 || || 0
|-
| m<sub>4</sub> || 0 || 1 || 0 || 0 || || 1
|-
| m<sub>5</sub> || 0 || 1 || 0 || 1 || || 0
|-
| m<sub>6</sub> || 0 || 1 || 1 || 0 || || 0
|-
| m<sub>7</sub> || 0 || 1 || 1 || 1 || || 0
|-
| m<sub>8</sub> || 1 || 0 || 0 || 0 || || 1
|-
| m<sub>9</sub> || 1 || 0 || 0 || 1 || || x
|-
| m<sub>10</sub> || 1 || 0 || 1 || 0 || || 1
|-
| m<sub>11</sub> || 1 || 0 || 1 || 1 || || 1
|-
| m<sub>12</sub> || 1 || 1 || 0 || 0 || || 1
|-
| m<sub>13</sub> || 1 || 1 || 0 || 1 || || 0
|-
| m<sub>14</sub> || 1 || 1 || 1 || 0 || || x
|-
| m<sub>15</sub> || 1 || 1 || 1 || 1 || || 1
|}
X は Don't care を表す。
この関数の[[選言標準形]]は、最小項の和をとって(Don't care は無視する)
:<math>f = \overline{A} B \overline{C} \overline{D} + A \overline{B} \overline{C} \overline{D} + A \overline{B} C \overline{D}
+ A \overline{B} C D + A B \overline{C} \overline{D} + A B C D</math>
となる。
もちろんこれはまだ最簡形ではない。まず、すべての1となる最小項をビット列中の1の数([[ハミング重み]])ごとに表に列挙する。また Don't care の項も加える。
{| class="wikitable"
|-
! 1の数 !! 最小項 !! ビット列表現
|-
| rowspan="2" | 1
| m<sub>4</sub> || 0100
|-
| m<sub>8</sub> || 1000
|-
| rowspan="3" | 2
| m<sub>9</sub> || 1001
|-
| m<sub>10</sub> || 1010
|-
| m<sub>12</sub> || 1100
|-
| rowspan="2" | 3
| m<sub>11</sub> || 1011
|-
| m<sub>14</sub> || 1110
|-
|| 4
| m<sub>15</sub> || 1111
|}
これで最初の準備が整った。1ビットのみが異なっている([[ハミング距離]]が1となる)最小項の組を見つけて、その2つをまとめる。これをすべての最小項の組み合わせについて確かめる。こうしてできた項を再び1の数ごとにまとめ、同じ操作を再帰的に適用する。それ以上まとめることができない項にはしるし(*)をつける。この印を付けた項が主項となる。
{| width="100%"
|width="33%"|
{| class="wikitable" width="100%"
!1の数
!最小項!!ビット列表現
|-
|rowspan="2"|1
|m<sub>4</sub>||0100
|-
|m<sub>8</sub>||1000
|-
|rowspan="3"|2
|m<sub>9</sub>||1001
|-
|m<sub>10</sub>||1010
|-
|m<sub>12</sub>||1100
|-
|rowspan="2"|3
|m<sub>11</sub>||1011
|-
|m<sub>14</sub>||1110
|-
|4
|m<sub>15</sub>||1111
|}
|width="33%"|
{| class="wikitable" width="100%"
!colspan="3"|1回目の比較
|-
|rowspan="4"|1
|m<sub>4,12</sub>||-100 *
|-
|m<sub>8,9</sub>||100-
|-
|m<sub>8,10</sub>||10-0
|-
|m<sub>8,12</sub>||1-00
|-
|rowspan="4"|2
|m<sub>9,11</sub>||10-1
|-
|m<sub>10,11</sub>||101-
|-
|m<sub>10,14</sub>||1-10
|-
|m<sub>12,14</sub>||11-0
|-
|rowspan="2"|3
|m<sub>11,15</sub>||1-11
|-
|m<sub>14,15</sub>||111-
|}
|width="33%"|
{| class="wikitable" width="100%"
!colspan="2"|2回目の比較
|-
|m<sub>8,9,10,11</sub>||10-- *
|-
|m<sub>8,10,12,14</sub>||1--0 *
|-
|m<sub>10,11,14,15</sub>||1-1- *
|}
|}
=== 必須項を求める ===
主項のなかから必須項をみつける。横軸に最小項(Don't care でないもの)、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし(X)を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。




=== 必須項を求める ===
主項のなかから必須項をみつける。横軸に最小項(Don't care でないもの)、縦軸に求めた主項を書いた表を作る。主項がカバーする最小項の欄にしるし(X)を書く。ある最小項をカバーする主項が1つしかないとき、その主項を必須項という。

{| class="wikitable"
|&nbsp;
|| 4 || 8 || 10 || 11 || 12 || 15 ||
|-
|m<sub>4,12</sub> *
| X || || || || X || || -100
|-
|m<sub>8,9,10,11</sub>
| || X || X || X || || || 10--
|-
|m<sub>8,10,12,14</sub>
| || X || X || || X || || 1--0
|-
|m<sub>10,11,14,15</sub> *
| || || X || X || || X || 1-1-
|}
例では2つ必須項が求まった。表中でしるし(*)をつけてある。必須項はその名のとおり、簡単化した関数に必ず含まれていなければならない項である。

=== 最簡形を求める ===
必須項だけでは全ての最小項をカバーできていないので、更なる作業が必要になる。最もシンプルな方法は、試行錯誤して最簡形を見つけることであるが、より系統的な方法として、ペトリック法([[:en:Petrick's method]])がある。このケースでは、次の最簡形を得る。

:<math>\begin{align}
f & = B \overline{C} \overline{D} + A \overline{D} + A C\\
& = B \overline{C} \overline{D} + A \overline{B} + A C
\end{align}</math>

== 計算量 ==
== 計算量 ==
4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。[[充足可能性問題]]という[[NP困難]]な問題を対象としているため、実行時間が入力長の[[指数関数]]的に増加してしまうのである。n変数関数における主項の数の上限は3<sup>n</sup>となる。n = 32とおくと、主項の数は6.5 &times; 10<sup>15</sup>を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。
4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。[[充足可能性問題]]という[[NP困難]]な問題を対象としているため、実行時間が入力長の[[指数関数]]的に増加してしまうのである。n変数関数における主項の数の上限は3<sup>n</sup>となる。n = 32とおくと、主項の数は6.5 &times; 10<sup>15</sup>を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。

2015年9月17日 (木) 01:44時点における版

クワイン・マクラスキー法(—ほう; Quine-McCluskey algorithm/略:QM法)はブール関数を簡単化するための方法である。カルノー図と同様の目的で使われるが、コンピュータによる自動化に適しており、またブール関数が最簡形かどうか決定的に求めることができる。W・V・クワインが提案し、E・J・マクラスキーが発展させた方法なのでこの名がある。

クワイン・マクラスキー法は3段階からなる。

  1. 関数の主項をすべて求める
  2. 求めた主項を表にまとめ、必須項を求める
  3. 最簡形を求める

例

クワイン・マクラスキー方法

計算量

4変数以上のブール関数を扱う際にはカルノー図よりも実用的であるが、クワイン・マクラスキー法が使える範囲にも限りがある。充足可能性問題というNP困難な問題を対象としているため、実行時間が入力長の指数関数的に増加してしまうのである。n変数関数における主項の数の上限は3nとなる。n = 32とおくと、主項の数は6.5 × 1015を超えることもある。変数の多い関数の簡単化においては最適解を保証しないヒューリスティックな方法が必要になる。

関連項目

参考文献

  • 田丸 啓吉『論理回路の基礎(改訂版)』工学図書株式会社、1989年。ISBN 4-7692-0204-0。 

外部リンク

AltStyle によって変換されたページ (->オリジナル) /