このサイトの範囲から少し外れているかもしれませんが、ここにいる十分な数の人がこれを知っているので、試してみることにしました.
3-CNF 句のセットがあるとします
S = {Clause1, Clause2} = {<x1 or x2 or not x3>, <x4 or x5 or x6>}
各変数範囲オーバー{0,1}
S にとって満足のいく割り当てはいくつありますか? 一般に、S のサイズが k の場合、S に対して満足のいく割り当てはいくつありますか?
これは、数を数えるということと同じくらい、3 選言節に対する満足のいく代入とは何かについての質問です。たとえば
、 があるだけの場合、2 3 = 8 通りの代入が可能です。
(111),(011),(101),(110),(100),(010),(001),(000)
しかし、これらのうちどれが満足のいく割り当てですか?