導出原理 (Resolution Principle) - ロビンソン

導出原理は、節形式の論理式から、相補的なリテラルを消去して新しい節を導く推論規則である。反駁では、元の集合から空節を導けるかを調べ、充足不能性を示す。

仕組みと確認

節、リテラル、選択した相補対、導出された節を証明ログへ残す。SATソルバーでは単位伝播や学習節と組み合わせ、導出が元の制約の論理的帰結であることを検査する。

限界と注意点

導出できることと、探索が効率的であることは別である。入力のCNF化が意味を保つか、冗長な節が増えていないか、タイムアウトを未判定として扱っているかを確認する。