クワイン・マクラスキー法の最簡形を求める方法について

質問

クワイン・マクラスキー法の最簡形を求める方法について

最簡形を求める方法について質問です。

丁度良い例がWikipadiaにありましたので、その内容で質問します。
＃Wikipediaで「クワイン・マクラスキー法」で検索すれば見つかります。
＃著作権保護のため一部のみ質問で掲載します。

クライン・マクラスキー法のページの項目「最簡形を求める」が質問箇所です。

下記の式で登場する*は論理積、+は論理和を表します。

全ての最小項を含む条件は
e1 * (e1+e2) * e4 * (e2+e3+e4) * (e3+e4) * (e2+e3)
= (e1*e2*e3*e4) + (e1*e2*e4) + (e1*e3+e4)　　【※A】
となり、この内、最も簡単なのはe1*e2*e4、または、e1*e3+e4になります。

結果として最簡形の関数fは
f = e1 + e2 + e4
または
f = e1 + e3 + e4
になります。

ここで質問なのですが、最小項を含む条件が【※A】のようになるのは
何となく納得できました。

しかし、もっとも簡単なモノのひとつが「e1*e2*e4」だから
関数fがe1、e2、e4の論理和になるというのが理解できません。
「e1*e2*e4」は論理積の形なのに、突然「e1+e2+e4」とう論理和の形で
表してしまうというのうが、受け入れられません。

Wikipediaにある参考文献の教科書も購入して読んだのですが
理解できない状態です。

全ての最小項を含むための条件【※A】から、最簡形の関数fを導くまでの
考え方を詳しく教えてもらえないでしょうか？

回答No.1

mtaka2 · ベストアンサー

e1～e4の意味を取り違えているかと思います。

e1は、加法形式に項「B*~C*~D」を含めるかどうか(注: ~C は、Cの否定を表してます)
e2は、加法形式に項「A*~D」を含めるかどうか
e3は、加法形式に項「A*~B」を含めるかどうか
e4は、加法形式に項「A*C」を含めるかどうか
を意味します。

入力0100の時に出力が1になるためには、項「B*~C*~D」を含む必要があります。つまり、e1=1 である必要があります。
入力1100の時に出力が1になるためには、項「B*~C*~D」か項「A*~D」を含む必要があります。つまり、(e1*e2)=1 である必要があります。
(略)
入力1000の時に出力が1になるためには、項「A*~D」か項「A*~B」を含む必要があります。つまり、(e2*e3)=1 である必要があります。

この全ての条件を満たす、すなわち「出力が1になるべき全ての入力の組合せに対して、出力が1になる」ようにするということは、

e1(e1 + e2)e4(e2 + e3 + e4)(e3 + e4)(e2 + e3) = 1

になる必要がある、ということになります。

この式を満たすようなe1～e4の値組合せを選び、それに対応して、1になっている変数に対応する項を加法形式に入れれば、
そうやって出来た関数は、関数fの条件を満たす、ということになります。

この式は、
e1e2e3e4+e1e2e4+e1e3e4=1
と変形できますから、e1～e4の値が、「e1=1, e2=1, e3=1, e4=1」「e1=1, e2=1, e3=0, e4=1」「e1=1, e2=0, e3=1, e4=1」のどれかであればよいということになります。

で、「e1=1, e2=1, e3=0, e4=1」であるとは、
加法形式に項「B*~C*~D」「A*~D」「A*C」を含める、
ということですから、
f'=B*~C*~D + A*~D + A*C
とした関数f' は、与えられた関数f と一致する、ということになります。

お礼

詳しい解説をありがとうございます。

必須項を見つける表(縦軸が主項、横軸が最小項の表)の
横軸にある最小項を入力として考えると良いのですね。

私は縦軸の主項を中心に考えていたため、仰るとおり
e1～e4の意味を間違えて認識していました。

ただ、考え方を変えてくれた素晴らしい解説なのですが
私の中でまだ消化しきれていません。

もしかしたら、その理解するまでの過程で追加質問を「補足」で
投稿させていただくかもしれませんので
お時間のあるときにでも再び覗いて頂けると幸いです。