CNF論理式の充足・割当探索

CNFの節表を入力し、既知割当のもとで充足モデルの有無を調べる。

空の節集合はSAT、空節を含む式はUNSATです。入力表はローカルで処理します。

項目を入力・選択してから「計算する」を押してください。

必要な入力・選択は0項目です。

節とリテラル任意
行節ID変数ID 任意符号 任意操作
1
2

3列を左端の欄へタブ区切りで貼り付けられます。500行まで。

同じ節IDの行はOR、異なる節はANDです。節IDだけの行は空節を意味します。節は最大100個です。

変数の宣言(任意)任意
行変数ID操作
1

1列を左端の欄へタブ区切りで貼り付けられます。24行まで。

式に現れる変数は自動認識します。式に出現しない変数も割当結果に含めたい場合に入力します。

既知の真偽値(任意)任意
行変数ID真偽値操作
1

2列を左端の欄へタブ区切りで貼り付けられます。24行まで。

既知値は探索中に変更しません。同じ変数へ矛盾する既知値は指定できません。

未入力なら100000操作。1~100000の整数。上限到達時はUNKNOWNです。


計算結果

値を入力して計算してください。

お気に入り一覧

計算方法・適用範囲・出典

計算方法

CNF=節(リテラルのOR)のAND。既知割当を固定し、単位伝播で確定値を追加します。矛盾した分岐は戻って反対値を探索します。SATは全節を完成割当で再評価したときのみ返し、UNSATは全分岐が矛盾したときのみ返します。操作上限・取消はUNKNOWNです。

SAT・UNSAT・UNKNOWNの判定、充足時の完成割当、操作数、分岐数。

計算例(架空の数値)

例:(a∨b)∧(¬a∨b)∧(¬b) はUNSAT。最後の(¬b)を除けばb=真でSAT。

適用対象と限界

最大24変数・100節の有限な命題論理のCNF。一般の数式評価、量化論理、SMT、最適化、充足割当の列挙、巨大なDIMACSファイルの読込は対象外です。。

採用した方式

  • DPLL(v1.0):対象範囲 24変数・100節・500リテラル行、操作上限100000/適用地域 global

方法と出典

方法:DPLL(単位伝播・辞書順で真→偽の分岐)v1.0。データ記録日:2026-11-14。