複数の仮定を用いて解く

Question

変数が(a,b,c,d,e,f,g)のCNF式があるとします。 SATソルバを使用して(d,e,f)の割り当てを見つけるにはどうすれば{a,b,c,g} = {1,0,0,1}と{a,b,c,g} = {1,1,1,1}が与えられますか？それが1つの仮定だった場合、{d,e,f}の代入を見つけるためにソルトソルバを呼び出すことは簡単です（たとえば、CNFに単位句を追加することによって）。しかし、複数の仮定がある場合はどうすればよいでしょうか？これは可能ですか？

Answer 1

ここでは、ハロードがあなたに説明しようとしていたことについてのステップがあります。変数a、b、c、d、e、f、gにはCNF式Fがあります。

1. Gに重複G.
2. を呼び出し、式を複製し、BB、CCとC、およびGGとGとB、A-Aと変数aを置き換えます。
3. （a、b、c、g）=（1,0,0,1）になるようにFに単位節を追加します。
4. （aa、bb、cc、gg）=（1,1,1,1）となるようにGに単位句を追加します。
5. 式FとGを連結し、結果をSATソルバに入力します。

ソルバーは、（a、b、c、g）と（aa、bb、cc、gg）のプリセット値と一致する満足のいく割り当てを見つけます。

Answer 2

実用的な答えが必要なのか、またはが面白いかはっきりしない理論的な答え。私は実用的に行くつもりです。

仮定の各セットについて、その仮定のセット（example）の仮定を使って解をサポートするソルトソルバーを呼び出します。同じソルバーインスタンスでこれを順番に実行します。

長所：

• あなたは仮定の相互排他的なセットの充足を混在させないでください。仮説Aの集合を式Fに、他の集合A 'をFについてunsatとすると、ソルバへの各呼び出しは、それらの仮定が満たされているかどうかを示します。
• 2回目のコールでは、最初のコールからの学習済みの句が残ります。中間学習句は同じ変数について話します。 （注：もし、Fが変数Xを超え、Gが変数Yを超えていて、Yが変数を共有していない、別の式F & Gを持っているならば、resolution - CDCLで使われている推論規則はFとGを混ぜた句を得ることができません。 。2つの混合代わりの1つのインスタンスがUNSAT証明し、早期に停止する方がはるかに簡単でない限り、それらを離れて分割する明白な利益はありません）

短所：

• インスタンスAがで解決することは困難である場合練習ではありますが、A 'は自明ですが、Aにはまってしまうかもしれません。
• 2つ以上のインスタンスがある場合、あなたはできるだけ早く解決したいと思っています。

これはわかりやすい回答ですが、試してみる価値があります。それが失敗すれば、あなたはw.r.tを解決するような魅力的なことをやってみることができます。仮定はA union A'であり、それがAのこの戦略に落ち着かず、A 'の戦略に落ち着いていない場合に限る。これはあなたの例では役に立ちません。(a,b,c,g) = (1,0,0,1)と(a,b,c,g) = (1,1,1,1)は互いに排他的です。