問題タブ [sat-solvers]

SAT（ブール充足可能性問題）ソルバーで読むのに適したドキュメントは何ですか。Googleで良い資料を見つけることができませんでした。私が見つけたドキュメントは、鳥瞰図、高度すぎる、または破損したPDFファイルのいずれかでした...

最新の実用的なSATソルバーのアルゴリズムについて学ぶために、どの論文/ドキュメントをお勧めしますか？

私はsat4jソルバーに全く慣れていません..

一部のcnfファイルを入力として指定する必要があると書かれています

ルールを入力として与え、それが満足できるかどうかを取得する方法はありますか?

私のルールは次のようなものになります：

sat4jソルバーを使用してこれを解決する方法を教えてもらえますか?

ブール式の充足可能性をチェックするために sat ソルバーを使用する必要があります..

このような複雑なブール式があります

satソルバーに直接渡すことができる自動cnfファイルコンバーターはありますか?

cnf形式のファイルを読んだのですが、この式を.cnfファイルでどのように表現すればよいのでしょうか? 括弧内に接続詞があると混乱し、 --> と <-> をどのように表現するか? 私を助けてください

でsatソルバーを見つけました

http://code.google.com/p/aima-java/

次のコードを試して、dpllsolverを使用して式を解決しました

入力は

CNFトランスはそれをに変換します

ロジックの他の部分は考慮せず、最初の用語のみを考慮します。正しく機能させる方法は？

他のsatソルバーがそれを行うことができるかどうか私に提案してください

私はこのツールに代わるコードとオープン ソースによる SMT Z3 の使用法 (DbC など) の実用的な例に興味を持ち、探しています。実際、同様の Z3 形式解法ツールに興味がありますが、

• オープンソースでなければならない
• 低レベル (API) と高レベル (テキスト スクリプト) の両方の対話を提供する
• SMT-LIBをサポート
• Java、Python、Ruby、Vala 、およびHaskell以外の言語のツール/書き込み/言語に適している (使用可能)
• 契約による設計（DbC）、静的型検証など、それに基づく安定した（実際に使用できる）ツールがあります。

SMT-LIB ホームページ (詳細については bit.ly バンドルを参照) によると、2010 SMT ソルバーのリストは次のとおりです。 UCLID、veriT、Yices、Z3."

それらのいずれかを実際に使用することについてフィードバックをお寄せください (コード例が最適です)。

最後に、それとGHCの可能性との比較に関する情報は役に立ちますが、実装例(言語の「機能」ではない)がある場合に限ります。

Z3 に関する詳しい情報はこちらhttp://bit.ly/bundles/ewiger/1

任意の命題式 PHI (いくつかの変数に対する線形制約) が与えられた場合、各変数の (近似) 上限と下限を決定する最良の方法は何ですか?

一部の変数は制限されていない場合があります。この場合、アルゴリズムは、これらの変数に上限/下限がないと結論付ける必要があります。

例えば、PHI = (x=3 AND y>=1)。x の上限と下限は両方とも 3 です。y の下限は 1 で、y には上限がありません。

これは非常に単純な例ですが、一般的な解決策はありますか (おそらく SMT ソルバーを使用)?

Z3 SMT Solver で次のことを証明しようとしています: ((x*x) + x) = ((~x * ~x) + ~x). これは正しいです。これは、C プログラミング言語のオーバーフロー セマンティックのためです。

今、私は次の smt-lib コードを書きました:

z3 からの出力は次のとおりです。

ここで私の質問: 結果が「unsat」になるのはなぜですか? コード内の simple コマンドは、myfun1 と myfun2 が同じ結果になるように有効な割り当てを取得できることを示しています。

私のコードに何か問題がありますか、それとも z3 のバグですか?

誰でも私を助けてください。どうも

メソッドを介して制御フローパスを列挙し、整数変数の範囲制約を計算できるオープンソースのJava解析ツールはありますか？（土ソルバーも素晴らしいでしょう）

- 編集 -

これがこの質問のきっかけとなった答えです。

これは私が考えているツールの商用バージョンです。

私の質問は-最も近いオープンソースに相当するものは何ですか？

ウィキペディアで説明されているように、C++でDPLLアルゴリズムを実装しています。

しかし、ひどいパフォーマンスをしています。このステップでは：

現在、私はのコピーを作成することを避けようとしてΦいますが、代わりに、lまたはnot(l)の唯一のコピーを追加して、/if 'sが戻っΦたときにそれらを削除します。これはアルゴリズムを壊して間違った結果を与えるようです（セットがであるとしても）。DPLL()falseUNSATISFIABLESATISFIABLE

このステップで明示的なコピーを回避する方法に関する提案はありますか？

C++ または haskell で記述された SAT ソルバー ライブラリまたはプログラムが必要です。なぜそれを選択するのか、そのライブラリ/プログラムの長所と短所は何かを知りたいです。できるだけ速く、使いやすくする必要があります。

ご回答有難うございます！