主項を求める
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/02/10 17:40 UTC 版)
「クワイン・マクラスキー法」の記事における「主項を求める」の解説
以下の真理値表で表されるブール関数を簡単化する。 ABCDfm0 0 0 0 0 0 m1 0 0 0 1 0 m2 0 0 1 0 0 m3 0 0 1 1 0 m4 0 1 0 0 1 m5 0 1 0 1 0 m6 0 1 1 0 0 m7 0 1 1 1 0 m8 1 0 0 0 1 m9 1 0 0 1 x m10 1 0 1 0 1 m11 1 0 1 1 1 m12 1 1 0 0 1 m13 1 1 0 1 0 m14 1 1 1 0 x m15 1 1 1 1 1 X は Don't care を表す。この関数の選言標準形は、最小項の和をとって（Don't care は無視する） f = A ¯ B C ¯ D ¯ + A B ¯ C ¯ D ¯ + A B ¯ C D ¯ + A B ¯ C D + A B C ¯ D ¯ + A B C D {\displaystyle f={\overline {A}}B{\overline {C}}{\overline {D}}+A{\overline {B}}{\overline {C}}{\overline {D}}+A{\overline {B}}C{\overline {D}}+A{\overline {B}}CD+AB{\overline {C}}{\overline {D}}+ABCD} となる。もちろんこれはまだ最簡形ではない。まず、すべての1となる最小項をビット列中の1の数（ハミング重み）ごとに表に列挙する。これはすべての組み合わせを作り、ハミング距離が1のものだけ残すのと等価である。このとき Don't care の項も加える。 1の数最小項ビット列表現1 m4 0100 m8 1000 2 m9 1001 m10 1010 m12 1100 3 m11 1011 m14 1110 4 m15 1111 これで最初の準備が整った。1ビットのみが異なっている（ハミング距離が1となる）最小項の組を見つけて、その2つをまとめる。これをすべての最小項の組み合わせについて確かめる。こうしてできた項を再び1の数ごとにまとめ、同じ操作を再帰的に適用する。それ以上まとめることができない項（もうハミング距離が１となる組み合わせがない項）にしるし（*）をつける。この印を付けた項が主項となる。 1の数最小項ビット列表現1 m4 0100 m8 1000 2 m9 1001 m10 1010 m12 1100 3 m11 1011 m14 1110 4 m15 1111 1回目の比較1 m4,12 -100* m8,9 100- m8,10 10-0 m8,12 1-00 2 m9,11 10-1 m10,11 101- m10,14 1-10 m12,14 11-0 3 m11,15 1-11 m14,15 111- 2回目の比較1 m8,9,10,11 10--* m8,10,12,14 1--0* 2 m10,11,14,15 1-1-*
※この「主項を求める」の解説は、「クワイン・マクラスキー法」の解説の一部です。
「主項を求める」を含む「クワイン・マクラスキー法」の記事については、「クワイン・マクラスキー法」の概要を参照ください。
- 主項を求めるのページへのリンク
