SATソルバを使うためにCNFを作る - soutaroブログSATソルバっていうのは，充足可能性問題（SATisfiability problem）を解いてくれるソフトウェアのことで，SATソルバで数独を解くとか，以外と身近なところに応用があったりします．SATソルバは数独を解くだけじゃなくて，プログラムの停止性の判定に使うとか，いろいろな応用を考えることができる良いものです．普通，SATソルバはCNFという論理式の特殊な形を取り扱います．日本語だと乗法標準形とか言うらしいですけど，別にこの言葉は忘れても良いと思います．詳しくはWikipediaでも見てもらえれば良いのですが，CNFは，変数かそのnot付けたやつ，をorで結んだやつ，をandで結んだやつ，という意味です． CNF ::= c1 && ... && c2 c ::= l1 || ... || l2 l ::= x | !x 任意の論理式(変数(x)とor(||)とand(&&)と「な
