書記が物理やるだけ#174 論理関数の簡単化

論理関数を簡単化することで，より単純な回路を設計できるようになる。

問題

説明

ブール代数による変形は複雑な式ほど難しくなる，このような場合はカルノー図やクワイン・マクラスキー法（QM法）などの機械的に解けるような方法が便利である。

解答

同じ項を括ってべき等則を用いることで簡単化できる。

カルノー図を用いることで，視覚的に分かりやすく簡単化できる。指定された表に真理値表の1を埋めて2の冪乗個で構成された四角で括ることで，「同じ項を括ってべき等則を用いる」と同じことができる，

(3)の真理値表では，出力が定義されない入力がいくつかある。これをドントケア項とすることで，普通に簡単化するよりもさらに単純な回路が得られる。

QM法では，まず最小項を列挙する。これを足し上げれば回路を構成できるが，まだ簡単にできる余地はある。

必要な要素を抽出するために，1変数減少できるかを考えて3変数項を作成していく。

これを繰り返すと主項が得られ，確認すると確かに簡単化が完了している。

本記事のもくじはこちら：