クワイン・マクラスキー法の実装

誰が興味あるのか知らないけど、諸事情によりPythonでクワイン・マクラスキー法を実装したので公開してみるよ。

https://github.com/takada-at/makurasan

クワイン・マクラスキー法とは何か?

論理式を簡単にするアルゴリズムです。詳しくはwikipediaを(日本語の記事わかりにくいけど)。
http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3%E3%83%BB%E3%83%9E%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AD%E3%83%BC%E6%B3%95

偉大な哲学者クワインが昼寝をしている内に思いつきました(嘘です)。
一応クワインの原論文もダウンロードしてみたので暇なときに読むかもしれない。
http://www.jstor.org/stable/2308219
http://www.jstor.org/stable/2307285

どうやって簡単にするのか

すごく適当な解説をつける。

論理式があった時に、とりあえずまず全部を論理和の形にする。これは分配則などを繰り返し適用すればできる。
(1)\overline A \overline B C D + B C D + A B \overline C + A \overline B C D


で、各選言肢に出てくる変数も統一する。以下の変形を利用する。
A B \overline C \equiv A B \overline C D + A B \overline C \overline D
(気持ちとしては、AかつBかつ¬Cと、(AかつBかつ¬CかつD)または(AかつBかつ¬Cかつ¬D)って、Dが真の場合と偽の場合にわけただけなので同じだろという話)。


そうすると以下のようになる。これを最小項標準形という。
(2)\overline A \overline B C D + A B C D + \overline A B C D + A B \overline C D + A B \overline C \overline D + A \overline B C D
ここで、各選言肢が以下のようになっているわけだが、

  1. ~A ~B C D
  2. A B C D
  3. ~A B C D
  4. A B ~C D
  5. A B ~C ~D
  6. A ~B C D

ここで2と3、4と5をペアにして、さっきの変形を逆に適用すると(1)の形に戻る。
A B \overline C D + A B \overline C \overline D \equiv A B \overline C
しかし他にもペアの作り方がある。例えば1と6もペアにできる。
つまり、もとの(1)よりも、簡単になるようなペアの作り方があるかもしれない。それを探そうという話。
で、クワイン・マクラスキー法は、とりあえず作れるペアを全部作って、その中で一番簡単な形の組み合わせを探す。

コードで言うと、この辺から見るとわかりやすいと思う。
https://github.com/takada-at/makurasan/blob/master/makurasan/logic.py#L276