３SAT その３

今回は3SATの三回目の説明です。できれば、今回で終わりにしたいので、それこそ、さんさんさっと済ませたいですね。はい、またも駄洒落です。予告通りですよね？今回は結構大変なので、余裕がないんです。いつにもまして、つまらないのはそのせいです。多分………。

さて、前回（３SAT　その２）は、

SAT∝3SAT

となるように、SATのブール変数の集合Uと節集合Cから３SATのブール変数U'と節集合C'

とする時に、節C'jの要素の数｜C'j｜が必ず3になるような変換を一通り説明したのですが、前回Cjの要素の数kが3より大きい時の証明が残っていました。もう一度その変換式を見てみると、

k＞3のとき（再掲）

でした。これが、Cjを論理式にした式、

　z1∨z2∨…∨zk　　　　　（１）

と等しくなるという事を証明する、というのが今回の説明の趣旨です。

さて、第一段階として、ある論理式、（例えば、ここでは上記式（１））を真とするような関数tを真理関数という言い方をします。ここでは、C'jのすべての節が真になるということを満たす真理関数t'をC'jをの各節ごとに求めていきます。

もう少しだけ説明を加えると、たとえば、真理関数t=z1∨z2は、t=Tであれば、上記式（１）を真にしますね。そのような真理関数tがあったとして、求めるべき、C'jのすべての節が真になるということを満たす真理関数t'、というのは、一般的に次のように場合分けして定義すればいいことになります。

１）t(z1)またはt(z2)が真

とする。

※注）これは、上記C'jを構成する式の第一項部分

に相当します。

２）t(zk-1)またはt(zk)が真

とする。

※注）これは、上記C'jを構成する式の第三項部分

に相当します。

３）3≦l≦k-2なるlについてt(zl)が真

とする。

※注）これは、上記C'jを構成する式の第二項部分

に相当します。

第二段階では、このように定義したあと、逆に、このC'jを真とするような真理関数t'があったときに、これが、論理式（１）と等しくなるかどうかを見ていきます。

なかなか、さんさんさっとっとは行かないですね。ちなみに、九州のある地方では、「この席は私が取ってるの」、というのは方言で、「こん席は私がとっとっと」、と言います。「窓からすきま風が入ってきてすーすーする」というのは、「すーすーすー」です。はい、どうでもいいですね。では、もう少しがんばろうと思います。

さて、C'jをそのまま論理式に書き換えると、次のようになります。

￢A∨B=A⊃Bという事より上の式は次のように書き換えられ、

充足問題では、上の式の最初の部分が、

　　

と書き換える事ができるので、これを最後まで繰り返すと、

　z1∨z2∨…∨zk　　　　

が出てくる事になります。

したがって、第二段階の結論としてはこのC'jを真とするような真理関数t'の真理変数をz1,z2,…,zkに制限したものをtとすれば、tは式（１）を満たす真理関数と言う事になります。

さて、全体を振り返れば、SATから3SATへの変形の手順は、多項式時間以内で終了する事は明らかですから、

SAT∝3SAT

つまり、3SATはNP-完全であることが証明されました。

参考文献：「PとNP」竹内外史　日本評論社  p.15-p.17