CNF論理式の充足・割当探索
バグ・不具合を報告
CNFの節表を入力し、既知割当のもとで充足モデルの有無を調べる。
空の節集合はSAT、空節を含む式はUNSATです。入力表はローカルで処理します。
項目を入力・選択してから「計算する」を押してください。
必要な入力・選択は0項目です。
計算結果
充足判定
—
- 使用操作数
- —
- 分岐数
- —
値を入力して計算してください。
この計算機は使いやすかったですか?
回答はサイト改善のために保存します。入力値・計算結果は送りません。
ありがとうございます。よかったら、上の共有ボタンからこの計算機を紹介しませんか?
計算方法・適用範囲・出典
計算方法
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。