論理式の簡単化というやつは厄介である。
そんなこと日常的にはやらんのだが、実験があるからというわけで、
その課題を考えてたのだがすごく難しい。
さてどうしたものか。
どういうことかというと、こんな論理式が与えられたと。
f=A・!B + A・C + B・!C + !D・!B + !A・D + !A・B
本当はBの上にバーを書きたかったけど無理なので !B と書いてる。
実はこの式、簡単化すると1になります。
A、B、C、Dにどんな0と1を入れても、答えは絶対に1になると。
しかし見てもわかりませんね。
これをうまく変形して整理できるそうだ。
まぁ僕もよくわからなかったので、取り扱いに慣れてそうな情報工学科の友人に聞いた。
どうも式をばらしてくっつけるということをするそうだ。
ところで論理式というのは、0と1ばっかり取り扱う式ですね。
それでNOTとANDとORがあるわけだが、
NOTは反転させればいいと。0のNOTは1だし、1のNOTは0、
ANDはどっちも1なら1だ。1と1のANDは1だが、1と0とか0と0のANDは0、
ORはどっちかが1なら1だ。1と0のORは1だが、0と0のORは0となると。
NOTは文字の上にバーを引きますね。ANDは+、ORは・、足し算とかけ算みたいなもんですよ。
論理式というのは何のことかと言えば、計算機の中身を作るのに使うものだよね。
さっきみたいな式の結果を出すようにしたいと。
しかしこの通り作ると金がかかる。だから簡単にしたいと。
そして簡単にしたらどうも結果は1であると。本当に安上がりでいいですね。
さて、f=A・B + A・!B + !A・B などなっていれば、
まず項と項をくっつけて簡単にするということをする。
A・B + A・!B = A・(B + !B)
当然Bか!Bはどっちかが1になるのだから、これは1であると。そしてAだけになると。
これでf=A + !A+Bとなるのですが、さらに簡単にできるんですね。
1と何のORを取っても1になるのでAの項に(1 + B)のANDを取ります。
f = A + !A・B = A・(1 + B) + !A・B = A + A・B + !A・B=A + B
分解して他の式とくっつけるとさらに簡単になると。
というわけでORを1個使えば簡単に作れますねと。めでたしめでたし。
実は上の式もこの変形をひたすら実行すれば1になります。
f=A・!B + A・C + B・!C + !D・!B + !A・D + !A・B
=A・!B・(C + !C) + A・C・(B + !B) + B・!C・(1 + A) + !D・!B・(1 + !A) + !A・D・(!B + B) + !A・B・(!D + D)
=A・(!B・C + !B・!C + C・B + C・!B + B・!C) + B・!C + !D・!B + !A・(!D・!B + D・!B + D・B + B・!D + B・D)
=A・(!B + B) + B・!C + !D・!B + !A・(!D + D)
=A + !A + B・!C + !D・!B = 1 + B・!C + !D・!B = 1
バラして、1をどんどん作ってまとめていくと。
最後にA + !Aの時点で1となったから、あとは何とOR取っても1ですねと。
まぁめんどくさいことこの上ない。
4変数までなら、カルノー図という図を書いて、それでやっていけば簡単かできます。
A、B、C、Dの0・1の組み合わせが並んだ格子状の表でしてね、
ここに1のところは1を書いていくと。こんなに複雑だとそれがめんどくさい。
できたら、一定の規則で四角で囲んでいく。重なってもいい。
結果これと同様の簡単化ができると。しかし4変数までですが。
それ以上はもう手作業では大変すぎるんだとか。
ただコンピュータでやる方法はあるみたい。
だけど変数の数が増えると恐ろしい計算量になるので、まぁ難しいとか。
カルノー図書かずにさっきの簡単化したけど、正直曲芸ですね。
なんかうまく行き過ぎだと思うだろうけど、うまくいった場合を書いてるからですね。
こんなの思いつかないというのはもっともな話ですね。
まぁ3変数までなら割と簡単にできるんじゃないかなと思いますよ。
4変数だと本当に見当が付きませんからね。
今のところはそういう感想ですね。
実験までに簡単な式を作っておこうかなと思った。