satisfiability

1熱

1答えて

私は以下の問題があります：私は論理的に等価にならなければならない2つの命題式を持っています。ただ、それらのうちの1つは変数が任意の命題式に置き換えられるという意味で「変数」を含む。問題は今、論理的な等価性が真となるように、変数の実際の置き換えを見つける必要があるということです。例：（^〜B）またはX =ここ、xは変数を表します。それはなったように、この論理等価性は、^ BとXを交換することに

5熱

1答えて

ブール式の最小化はNP完全ですか？

私はブールの充足可能性がNP完全であることを知っていますが、ブール式の最小化/簡略化です。これは記号式で与えられた式を取って、私は、充足可能性から最小化への削減があるとは確信していませんが、おそらくそこにいるように感じます。誰かが確かに知っていますか？

1熱

1答えて

ボディには、貪欲な充足可能性（GSAT）とシミュレーテッドアニーリングの充足性（SA-SAT）Javaアルゴリズムがありますか？

私はJavaで実装されたGSATとSA-SATアルゴリズムを探しています。どんな肉体についても知っていますか？ありがとうございます。

3熱

1答えて

z3から間違った結果

私はZ3 SMTソルバーで次のことを証明しようとしています：((x*x) + x) = ((~x * ~x) + ~x)。これは、Cプログラミング言語のオーバーフローセマンティックのために正しいです。 Z3から (declare-fun a() Int) (define-fun myadd ((x Int) (y Int)) Int (mod (+ x y) 4294967296)) (d

5熱

1答えて

検証アルゴリズムをSAT問題に変換するコンパイラ

SATがNP完全であるという証明は建設的な証明であるため、プログラムとして実装することが可能である必要があります。誰もこれをしましたか？私は入力としてプログラム（真または偽を返す）を取り、SAT式を出力するプログラム（コンパイラ）を探しています。たとえば、コンパイラは入力として次のプログラム（pythonic構文で表示しますが、言語は問題ありません）を入力してSAT式を出力できます。 SAT式

8熱

1答えて

制約解消のCSPソルバーに対するSMTソルバーの利点は何ですか？

SMT-Solverは制約解消に使用できます。われわれが知っているように、CSPソルバーは長年の制約解消のためのものでもあります。では、CSPソルバーに比べてSMTソルバーの利点は何ですか？

6熱

1答えて

ブール充足可能性 - アルゴリズム

ブール式：（x_ {1}またはx_ {2}）、（x_ {3}またはx_ {4}）、.....および（x_ {2r-1 x_ {i} {p_ {1}、p_ {2}、... p_ {99}、〜p_ {1}、〜p_ { 2}、...〜p_ {99}}となりました。x_ {i}の数式が真であるかどうかを判断する必要があります。私はそれが一般に計算上困難であることを知っています。しかし、私はこの特定の問題

1熱

1答えて

孤立したEXISTS句のskolemisationはどのように機能しますか？

私が持っている場合と同様に式：EはFAの外にある場合と交換してください：（=が存在するFA =すべての場合/ E） FAx FAy (Ez(!A(x,z) v !A(y,z)) v B(x,y)) skolemisationののルールがあると言います定数または EがFAの内側にある場合FAの外側のすべての変数を引数として含む新しい関数で置換されます。この場合、私は何をしますか？ Exis

12熱

2答えて

SATソルバーを使用してすべてのソリューションを見つけることはできますか？

私はquite interesting questionだと思った答えを書いたが、不幸にも質問を投稿者が削除する前に投稿した。私は質問の要約と私の答えをここに再掲載しています。それが他の誰にとっても役に立つかもしれない場合に備えて。結合標準形でブール式を指定すると、解（式を満たす変数の代入）または問題が満たされないという情報が返されるSATソルバーがあるとします。このソルバーを使用してを見つけ

1熱

1答えて

SAT前処理用のハッシュ関数

節データベースで構成されるSATインスタンスの前処理中に、すべての変数に単語を割り当てる必要があります。ハッシュ関数は、各変数について、16の最上位ビット（MSB）のうちの1つのビットと、16の最下位ビット（LSB）のうちの1つのビットを除いて、0からなる32ビットワードのみを返します。変数。節の署名は、すべての変数のハッシュ関数値のビットごとの論理和です。このハッシュ関数を実装するにはどうすれ