クワイン・マクラスキー法の最簡形を求める方法について
最簡形を求める方法について質問です。
丁度良い例が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ベストアンサー
- 回答日時:
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の意味を間違えて認識していました。
ただ、考え方を変えてくれた素晴らしい解説なのですが
私の中でまだ消化しきれていません。
もしかしたら、その理解するまでの過程で追加質問を「補足」で
投稿させていただくかもしれませんので
お時間のあるときにでも再び覗いて頂けると幸いです。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
中古でジョイコンなしの代わり...
-
フロースイッチ異常の警報発報...
-
マザー
-
シロッコファンの強弱スイッチ...
-
文書作成したいだけなのですが…
-
マリオがPSで出ない理由
-
断路器のDSをLSと書くのは何か...
-
電気の取っ手が落ちたまま戻らない
-
壁スイッチの修理料金
-
batファイルを作成してoutlook...
-
ニンテンドースイッチのソフト...
-
電磁波の音・モスキート音が聞...
-
windows11で任天堂switchのSDカ...
-
中古のスイッチのソフトの裏側...
-
任天堂3DSについてです。 3DSを...
-
ゲームボーイミクロの液晶輝度調整
-
3路スイッチと4路スイッチの...
-
任天堂swithスプラトゥーン
-
スイッチのAPEXのデータを新し...
-
電子工作などに使われるスイッ...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
フロースイッチ異常の警報発報...
-
中古でジョイコンなしの代わり...
-
断路器のDSをLSと書くのは何か...
-
スイッチの ・1P ・3W ・4W こ...
-
マザー
-
文書作成したいだけなのですが…
-
近接センサと近接スイッチって...
-
エレベーターの扉を手で抑えて...
-
任天堂スイッチのSDカードにつ...
-
蛍光灯の紐が抜けました(中の...
-
batファイルを作成してoutlook...
-
スイッチのAPEXのデータを新し...
-
Word差し込み 時間が秒やAMPM...
-
マリオがPSで出ない理由
-
ゲームボーイミクロの液晶輝度調整
-
親にWi-Fiを切られ、スマホが使...
-
三路スイッチのスイッチ傾き方...
-
電気の取っ手が落ちたまま戻らない
-
自作PCケースの前面の「リセ...
-
本体の裏にある電源ボタンの意味
おすすめ情報